ロシアコードカップ：最初の段階のタスクの中で最も興味深い

5月8日に、全ロシアプログラミングカップロシアコードカップの最初の予選ラウンドが行われました 。 ラウンドの勝者はYevgeny Kapunで、彼は130分のペナルティ時間で5つの問題をすべて解決しました。



合計756人が最初の予選に参加しました。 ラウンドの結果によると、最高200人の参加者が、6月19日に開催される予選ラウンドに参加することが許可されました。



5月14日と15日に、2回目と3回目の資格審査が行われ、さらに400名が選出されます。



この記事では、RCCの第1段階のさまざまな統計を分析し、タスクを分析して、ツアー中に受け取った最もよくある質問に答えます。







参加者を解決するために、審査員は5つのタスクを提案しました。 少なくとも1つの問題が691人の参加者によって解決されました。 問題Aが最も簡単であることが判明し、685人の参加者がそれを解決しました。 一般的に、正しい決定は次のタスクに従って配布されました。





図1.問題の正しい解決策の数。



図からわかるように、タスクA、B、およびCは大多数の参加者に送信されましたが、DおよびEははるかに複雑であることが判明しました。 これらのタスクは、3つの簡単な問題を解決し、2つの困難な問題の少なくとも1つが予選ラウンドへのアクセスを保証する、資格認定の成功の鍵となりました。



しかし、3つの問題を解決した参加者は、問題解決の高速性を実証するために必要でした。 200位の「カットオフ」はペナルティ時間に応じて行われました。3つのタスクで予選ラウンドに参加するには、141時間以下のペナルティ時間、つまり1つのタスクに平均23.5分を費やす必要がありました。





図2.解決されたタスクの数に応じた参加者の数。



タスクBで最大の試行が行われたのは1952年でしたが、成功したのは約461で、約24％でした。 一般に、タスクで成功した試行の割合は次のようになります。





図3.タスクで成功した試行の割合。



問題Cを解決した参加者は少なかったものの、問題Bに比べて問題が少なかったことがわかります。



ロシアコードカップの参加者が使用したプログラミング言語の統計を見るのは興味深いです。 合計数量を円グラフに転送すると、次の図が表示されます。



図4.プログラミング言語に応じた決定の数。



GNU Cはかなり大きな差でリーダーであり、JavaとC＃の占有率は合計で約3分の1で、他の言語ではさらに少ないアプローチが行われています。



興味深いことに、長い演算を必要とする5番目のタスクは、主にJavaで解決されました。



一般に、送信された決定の、競争の議事録による分布は、次のチャートで見ることができます。



図4.競技の時間に応じたアプローチの数。



最初の数分で参加者がタスクを読んだ後、強い参加者の大部分が最初のタスクに対処したときに急激な急増があり、わずかに減少し、その後、アプローチの数は毎分30から50の範囲であり、ラウンドの終わりには最大90の急増が見られました。 同時に、競争の始めに正しい決定が主に検証のために送られた場合、正しい決定の割合は着実に減少しました。 次のグラフは、競争の議事録に応じて、検証のために送信された決定のうち正しい決定の割合の依存性を示しています。



図5.競争の時間に応じた成功したアプローチの割合。



タスクの解析



タスクA.文字列の連結

多くのアプリケーションでは、さまざまな文字列操作が必要です。 2つのかなり一般的な操作は、行の広がりと2つ以上の行の連結です。

文字列sの反転の結果、文字列s ^Rが取得されます。これは、sと同じ文字で構成されていますが、逆の順序になっています。 たとえば、文字列「abcde」を展開した結果、文字列「edcba」が取得されます。 さらにこの問題では、表記s ^Rの代わりに表記（s）が使用されます。

2つの文字列sとtを連結した結果、文字列s ^tを取得します。文字列sの文字が最初に書き込まれ、次に文字列tの文字が書き込まれます。 同様に、3、4、またはそれ以上のストリングの連結が定義されています。 たとえば、文字列「abc」と「cda」を連結すると、文字列「abccda」になります

あなたの仕事は、いくつかの行を連結した結果を決定することです。そのいくつかは拡張する必要があります。



入力形式



入力は、小文字のラテン文字と括弧のみを含む1行で構成されます。 その長さは200文字を超えません。 この行は、いくつかの行を連結したもので、その一部は拡張する必要があります。

各開始ブラケットの右側の所定の行には閉じがあり、各閉じブラケットの左側には開始があり、対応する開始ブラケットと終了ブラケットの間に他のブラケットはなく、少なくとも1つの文字が必要です。



出力形式



連結の結果を出力します。



解決策



このタスクは、競争で最も簡単でした。 制限は非常に小さく、合理的な方法で問題を解決できます。 たとえば、文字列を読み取り、区切り文字として括弧を使用してフラグメントに分割し、すべての偶数ブロックを展開します。 正規表現処理が組み込まれた言語（Perlなど）では、この問題の解決策は一般に特にコンパクトで自然に見えます。



ロシアコードカップで利用可能なすべてのプログラミング言語でこの問題の解決策を提供します。 同時に、標準の入力ストリームからデータを読み取る方法に注意を払いましょう。多くの参加者が、入力データを取得する場所についての質問をコンテスト中に尋ねました。



最適なソリューションであるとは主張していません。逆の場合でも、異なる言語でわずかに異なるソリューションを提供しようとしました。



Java：

import java.io.*; public class concat_as { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); String[] s = in.readLine().split("[()]"); for (int i = 0; i < s.length; i++) { if (i % 2 == 0) { System.out.print(s[i]); } else { System.out.print(new StringBuilder(s[i]).reverse()); } } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

C ++：

 #include <string> #include <iostream> #include <algorithm> using namespace std; int main () { string s; cin >> s; int l = 0; while (l < s.length()) { if (s[l] == '(') { int r = l; while (s[r] != ')') r++; string tmp = s.substr(l + 1, r - l - 1); reverse(tmp.begin(), tmp.end()); cout << tmp; l = r + 1; } else { cout << s[l]; l++; } } return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

C＃：

 using System; using System.Linq; class concat_as { static void Main(string[] args) { string s = Console.ReadLine(); int L, R; do { L = s.IndexOf("("); R = s.IndexOf(")"); if (L >= 0) { Console.Write(s.Substring(0, L)); Console.Write(new string( s.Substring(L + 1, R - L - 1).Reverse().ToArray())); s = s.Substring(R + 1); } } while (L >= 0); Console.WriteLine(s); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Perl：

 $s = <>; $s =~ s/\(([^)]*)\)/reverse($1)/eg; print $s
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Python

 s = raw_input() ans = '' for t in s.split('('): if ')' in t: l = t.split(')') ans += l[0][::-1] + l[1] else: ans += t print ans
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Php

 <?php $s = trim(fgets(STDIN)); $s = preg_replace('#\((\w+)\)#se', 'strrev("\1")', $s); echo "$s\n"; ?>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この問題の解決策は、PerlとPHPで特にシンプルでコンパクトであることが判明したことに注意してください。



タスクB.関税

現在、ほとんどすべてのモバイルオペレーターは、各個人が自分に最も適したものを選択できる広範な料金表を持っています。 残念ながら、この選択を手動で行うことは非常に難しいことがよくあります。



モバイルオペレーターの1つでは、各料金は3つの数値で特徴付けられます：サブスクリプション料金ci（ルーブルで設定）、最小請求可能時間単位t _i （秒で設定）、最小請求可能時間単位piのコスト（コペックで設定、1ルーブルで100コペック）。 1か月あたりの通話の合計コストは、月額料金と各発信通話のコストで構成されます。 i番目の料金を使用する場合の通話コストは、次のように計算されます。通話時間をT秒とします。 T <t _iの場合、通話コストはゼロです。 それ以外の場合、コールコストはkとp _iの積に等しくなります。ここで、kはk•t i≥Tのような最小整数です。



関税の説明と、その月の加入者の発信コールの統計情報が示されます-その数mと期間d ₁ 、...、d _m秒単位。 これらの通話の合計コストが最小になる関税を見つける必要があります。



入力形式



最初の行には、それぞれ2つの整数nとm-加入者の料金と発信コールの数（1≤n、m≤100）が含まれています。 次のn行はそれぞれ1つの関税を表し、3つの整数を含みます：c _i （0≤c i≤100）、t _i （1≤t i≤3600）、pi（0≤p i≤1000）。



最後の行には、m個の整数d ₁ 、...、d _m （1からmまでのすべてのiに対して1≤di≤3600）が含まれています。



出力形式



1つの番号を印刷する-関税番号。使用する場合、該当する月の加入者の発信通話の合計コストは最小です。 関税は、入力ファイルで指定された順序で1〜nの整数で番号付けされます。 そのような関税が複数ある場合は、それらのいずれかの番号を印刷します。



解決策



このタスクでは、条件を読むときに参加者の注意力をテストしました。 このタスクには、主に2つの「微妙な」ポイントがあります：サブスクリプション料金はルーブルで設定され、通話のコストはコペックで、通話時間を切り上げる特性：1課金単位未満の会話はゼロに切り上げられ、1課金単位を超える通話は切り上げられます。

これらの2つの点に気付いた場合、解決策は、指定された各料金で通話のコストの計算を直接実装し、最適な料金を選択することです。



問題C. Kソート



並べ替えのタスクは、指定された数値の配列（または他のオブジェクト）を昇順または降順に並べることです。 このタスクにはかなりの数のオプションがあり、その多くには非常に効率的なアルゴリズムがあります。 これらのアルゴリズムの重要なパラメーターの1つは、順序付けに必要な配列要素の交換回数です。



次に、ソートオプションを検討します。これをkソートと呼びます。 このオプションでは、1回の操作（k交換と呼ばれる）で、配列の2つの要素の値を、kだけ正確に異なる数値と交換することができます。 たとえば、元の配列の形式が[6、10、4、1、2]で、k = 3の場合、この配列は2つの操作で昇順でソートできます（最初の交換後、配列の形式は[1、10、4、6 、2]、2番目以降-[1、2、4、6、10]）。



整数の配列a ₁ 、...、a _{nが与えられ}ます。 あなたの仕事は、この配列を減少しない順序で並べるために必要なk交換の最小数を決定することです。



入力形式



最初の行には整数n（1≤n≤300）が含まれています。 2行目には、n個の整数a1、...、an（1からnまでのすべてのiに対して1≤ai≤109）が含まれます。 3行目には整数k（1≤k≤n-1）が含まれます。

出力形式



与えられた配列が、記述されたタイプの操作を使用して非減少順で順序付けられる場合、ソートに必要なk交換の最小数を出力します。 それ以外の場合は、単一の数値-1を出力します。



解決策



kを法とする位置の残りに応じて、配列をk個の部分に分割します。 これらの各部分では、隣接する要素はkの距離にあるため、互いに交換できます。 配列の異なる部分の要素は、要素間で交換できません。



ソートされた配列では、各パーツもソートされることに注意してください。 したがって、タスクは次のように要約されました。アクションの最小数のために各部分をソートし、結果の配列がソートされていることを確認します。 もしそうなら、答えはパーツをソートするために必要なアクションの総数です。 配列が順序付けられていない場合、解決策はありません。



隣接する要素のみを交換することが許可されている場合（つまり、各部分を並べ替える必要がある操作）、配列を並べ替えるのに必要なアクションの最小数を理解する必要があります。 最小限のアクション数は、バブルによる通常のソートによって実行されることがわかります。 nを並べ替える配列a [0..n-1]の長さとします。 次に、目的の交換回数で次のアルゴリズムが実行されます。



for i from 0 to n – 1:

for j from 0 to n – 2:

if a[j] > a[j + 1]:

swap(a[j], a[j + 1])







これを証明しましょう：このために、反転の数と呼ばれる配列の次の特性を考えます：位置のペアの数（i、j） 、 ここで i < j およびa [i]> a [j] 。 明らかに、ソートされた配列では、反転の数はゼロです。 一方、2つの隣接する要素を交換すると、そのようなペアの数を1つだけ変更できます。 この場合、各交換でのバブルによるソートにより、ユニットあたりの反転数が減少します。



したがって、バブルによる並べ替えの交換の数は、配列の反転の数、つまり、配列を並べ替えるために実行する必要のある交換の最小数に等しくなります。



問題D.レール



鉄道の重要なパラメーターはトラックゲージです。これは、列車が移動する2本のレール間の距離です。 鉄道で移動できる列車やその他の車の種類を決定するのは、このパラメーターです。



最近、惑星RCC-0805への宇宙遠征で、この惑星に鉄道があることがわかりました。 鉄道デポさえ発見されましたが、ゲージを決定することはまだできませんでした。 実際、この惑星の鉄道は枕木なしで敷設されているため、どの鉄道が互いに対応しているかを判断するのは必ずしも容易ではありません。



鉄道車両基地の領域におけるレールの位置の計画が与えられます。 簡単にするために、テリトリーは無限平面であり、各レールは直線として表示されると想定しています。 レールをペアに分割できる最小ゲージdを見つけて、各ペアでレールが平行になり、それらの間の距離がdに等しくなるようにする必要があります。



入力形式



最初の行には整数n（1≤n≤2000）が含まれています。 次の2n行にはそれぞれ、4つの整数x _i、1、 y _i、1、 x _i、2、 y _i、2が含まれています。これは、レールが通過する2つの異なるポイントの座標です。 すべての座標の絶対値は1000を超えません。 異なるレールに対応する直線は一致しません。



出力形式



実数-可能な限り最小のゲージを印刷します。 10 ^-6以下の精度で決定する必要があります。

任意のゲージでレールをペアに分割することが不可能な場合、タスクの要件を満たすことが不可能な場合、数値-1を印刷します。



解決策。



まず、レールを線の方向に等価クラスに分割します。平行線は1つのクラスに分類されます。 その後、各クラスで、このクラスのすべての可能なゲージ値を見つけます。 答えは可能な限り最小の距離であり、すべてのクラスに適しています。



次に、ソリューションの各段階を詳細に検討します。



等価クラスによって線を分布させるために、各線の方程式を作成します。 線が点（x ₁ 、y ₁ ）、（x ₂ 、y ₂ ）を通過するようにします。 その場合、ax + by + c = 0という形式の方程式は、a = y ₁ -y ₂ 、b = x ₂ -x ₁ 、c =-（ax ₁ + by ₁ ）のようになります。 ここで、a、b、およびcを除算することにより、線の係数を正規化すると便利です 。 現在、各行には2つの表現があります：係数に–1を掛けるまで。 各行に単一の方程式を持たせるには、「a> 0 or（a = 0 and b> 0）」という条件を追加で要求すると便利です。 この要件が満たされると、平行線のペアは同じになります（a、b）。 この表現では、線間の距離を計算することも便利です。2本の平行線ax + by + c ₁ = 0およびax + by + c ₂ = 0の場合、距離は| c ₁ -c ₂ |です。



平行線のクラスを検討してください。 それらを係数cでソートします。 最初の行を検討してください-このクラスの他の行の1つとペアになっています。 この行を調べます。 それらの間の距離をdと等しくします。 ここで、距離dにあるペアに線のパーティションを熱心に構築します。 これを実行できる場合、dは特定のクラスのトラック幅になります。 行を昇順で検討しますc。 次の直線c = c _iにまだペアがない場合、c = c _i + dの距離dで平行になります。 そのような行がある場合、問題の行とカップルで結合します。 ペアリングは、2ポインター方式を使用して線形時間で実現できます。cの増加とともにc + dも増加することに気付くのに十分です。



最後に、答えを探すことを検討してください。各クラスに可能な答えのリストがあります。 当然、それらは昇順でソートされます。 このような2つのリストは、1つのパスで簡単にクロスできます。 リストの長さの合計に比例した時間ですべてのリストの共通部分を完了すると、最小要素が問題に対する答えである共通部分リストが得られます。



アルゴリズムの実行時間を分析しましょう。 分類はO（n）で実行されます。 サイズkの特定のクラスについて、許容距離のリストはO（k ² ）で構築され、その長さはkを超えません。 したがって、最後のステップはO（n）で実行され、アルゴリズム全体はO（n ² ）で実行されます。



問題E.数字を推測する



最近、人気のあるソーシャルネットワークの1つに、アプリケーション「Guess the Number！」が登場しました。 ユーザーにはゲームが提供されます。ゲームの各レベルでは、ゲームに関するいくつかの情報から隠し番号を決定する必要があります。



特に、最も難しいレベルの1つでは、有理数x（0 <x <1）を推測する必要があります。これは、10進表記で自然数kを乗算した結果、正確に1つの変更が発生したことがわかっています。小数点の後のj番目の数字（数字は左から右の方向に1から番号が付けられます）。 この場合、小数点までの桁は変更されていません、つまり、不等式0 <k _x <1が満たされます。最初に小数点xで小数点以下の桁数を無限にできることに注意してください。



あなたの仕事は、数値i、j、kによってxの値を決定するプログラムを作成することです。



入力形式



最初の行には、3つの整数i、j、kが含まれています（1≤i <j≤1000; 2≤k≤109）。



出力形式



目的の数が存在する場合は、2つの整数を印刷します-目的の数を定義する既約分数の分子aと分母b（a、b> 0）。 それ以外の場合は、フレーズNO SOLUTIONを出力します。



解決策



最初に図sがi番目の位置にあり、図tがj番目の位置にあるとします。 次に、kを乗算した後の数は、x-10 ^–i s + 10 ^–i t-10 ^–i t + 10 ^–i sです。 したがって、望ましい数は、式kx = x-10 ^-i s + 10 ^-i t-10 ^-i t + 10 ^-i sの解です。



実際、解はsとtの特定の値に依存するのではなく、それらの差にのみ依存することに注意してください：（k-1）x =（10 ^–i -10 ^–i ）（t-s）。 さらに、s <t。 したがって、1〜9の範囲で差（t-s）を整理するだけで十分です。それぞれの差の値について、方程式の解を見つけて確認します。整数部分はゼロのままです。



転送により、上記の方程式の解が問題の解に対応しない可能性があるため、検証が必要です。



よくある質問と回答



競技中、参加者は審員に質問を送ることができました。 いくつかの質問に特に頻繁に出会ったため、この記事ではそれらに答えることにしました。



質問：検証のためにソースコードまたはコンパイル済みファイルを送信する必要がありますか？

回答：検証のためにソースコードを送信する必要があります。 テストシステム自体が参加者の決定をコンパイルし、コマンドラインはロシアコードカップのルールで指定されます



質問：データの入力元はどこですか？

回答：いわゆる標準入力ストリームからデータを入力する必要があります。 これはキーボード入力に対応します。追加のパラメーターなしで標準入力ストリームからデータを読み取るプログラムを実行すると、キーボードから入力が実行されます。

同時に、キーストロークの分析や、キーストロークに関するオペレーティングシステムメッセージの受信など、低レベルのキーボード入力は間違ったアプローチです。 読み取りは「コンソールから」である必要があります。



質問：答えはどこに入力すればよいですか？

回答は標準出力ストリームに出力する必要があります（デフォルトでは、画面に送信されます）。 繰り返しますが、低レベルのツールでこれを実行しようとしないでください。



次に、ロシア語コードカップでサポートされているすべてのプログラミング言語で標準入力ストリームを読み取り、標準出力ストリームに書き込む例を示します。



Java



入力には、System.inストリームを使用します。 Javaで入力を解析するための最も便利な手段は、BufferedReaderクラスとScannerクラスです。 BufferedReaderは読み取りが速く、大量のデータを1行ずつすばやく読み取ることができます。 スキャナーは正規表現を使用しているため低速ですが、たとえば入力から1つの数値を読み取るなど、入力文字列を非常に柔軟に解析できます。



BufferedReaderを使用して標準入力ストリームから読み取るには、プログラムに次の行を記述します。



BufferedReader in =新しいBufferedReader（新しいInputStreamReader（System.in））;



Scannerを使用して標準入力ストリームから読み取るには、プログラムに次の行を記述します。



スキャナー入力=新しいスキャナー（System.in）;



出力には、System.outを使用します。 同時に、System.outはキャッシュされません（すぐにバッファーをフラッシュします）。大量の情報を表示する必要がある場合は、PrintWriterでラップすることをお勧めします。



C ++



scanfを使用して、クラシックCを入力できます。 この関数は、標準入力ストリームからデータを読み取ります。

ストリームを介した入力は、cinストリームを使用して行われます。 デフォルトでは、標準入力ストリーム用に構成されています。 ストリームを使用した入力は、scanfを使用した入力よりも大幅に遅いため、プログラムが大量のデータを読み取る時間がない場合があることに注意してください。

出力についても、従来のprintfまたはストリーミングcoutを使用できます。 すべてのパフォーマンスノートは有効なままであり、printfはより高速です。



C＃



入力にはコンソールを使用します。 Console.ReadLine（）は、入力の次の行を読み取ります。 解析するには、split（）メソッドを使用します。 データを数値に変換するには、Convertクラスを使用します。

コンソールも出力に使用する必要があります。 たとえば、数値xを出力するには、Console.WriteLine（x）を記述できます。



Python



入力には、inputまたはraw_input関数を使用できます。 標準入力用に構成されたsys.stdinファイル記述子を使用することもできます。

出力にはprintを使用することをお勧めします。



Perl



Perlの標準入力からの入力は、<>コマンドを使用して行われます。 このコマンドは、ファイルから行を読み取り、それを返します。

出力にはprintを使用することをお勧めします。



Php



PHPの標準入力からの入力は、STDIN記述子から行われます。 次の行は、たとえば、fgetsコマンドで考慮することができます。

出力には、printまたはechoを使用できます。



さまざまな行読み込み関数を使用する場合、ドキュメントを注意深く読み、関数が行とともに改行を返すかどうかに注意することもお勧めします。 審査員のテストでは、最後を含むすべての行が改行で終わり、テストはWindows 7で行われ、Windowsで受け入れられた組み合わせは、コード13と10の文字で構成される行フィードに使用されます。



さらに、テストは自動的に行われることに注意してください。 したがって、さまざまな「入力プロンプト」を出力したり、結論を「装飾」しようとしたりしないでください。 データを入力し、問題を解決し、出力形式に従ってデータを表示する必要があります。



質問：例のテストは正しいですか？

回答：この例のテストは通常​​正しいです-事前に知らずに問題を解決する数人を含む数人がチェックします。 テスト例が正しくないと思われる場合は、条件をより注意深く読んでください。おそらく何かを誤解している可能性があります。

それでも例が間違っていると思う場合は、例に誤りがあると考える理由、どの答えが正しいか、不正確または曖昧だと思うものの詳細な説明をリクエストに含めてください。



質問：問題Xの239番目のテストは正しいですか？

回答：ほとんどの場合、テストは正しいです。 テストが間違っていると思う場合は、その理由を書いてください。 「そのようなテストは正しいテストですか？」という質問をするのは無意味です。 - «» - , .



: , ?

: , .



!



Russian Code Cup