4月には、iPad mini 2、iPod nano、iPod shuffleなどの魅力的な賞品を獲得するために、再び彼ら自身を証明する機会が与えられます。 ありふれた材料賞に加えて、不可欠な名誉と尊敬に加えて、最初のテクノキューブ（I学位の卒業証書）の受賞者は、MIPTおよびMSTUの学部および専門プログラムへの入学のために最大8つの追加ポイントを受け取ります。 N.E.バウマン、および受賞者（IIおよびIII学位の卒業証書）-6つの追加ポイント。 子どもたちはすでに一流のITスペシャリストと知り合うことができ、将来的にはモスクワの最高の技術大学の1つでの研究と、テクノパークとテクノトレックの追加の教育プログラムを組み合わせることになるでしょう。
「テクノクボックは重要な社会的イニシアチブです。オリンピアードのおかげで、才能のある若いプログラマーは国の主要な技術大学に入学する機会がさらに増えます。 私たちは、学生や学童にできるだけ多くの機会を与え、大企業での仕事に必要な知識や実践を獲得したり、独自のプロジェクトの開発を開始したりするために体系的に取り組んでいます。 大学との教育プロジェクト（テクノパーク、テクノスフィア、テクノトレック）、ITチャンピオンシップ、そしてテクノカブはこのリストを補充します。これは、「Dmitry Dmitry21 Voloshin、研究教育ディレクター、Mail.Ruグループ。
今年の参加者と、将来のテクノカップの準備をしたい人のために、タスクの議論を行います。
A.最大の上昇
尾根の輪郭は、記号「。」（空のスペース）と「*」（山の一部）の長方形の表の形式で概略的に定義されます。 テーブルの各列には、少なくとも1つのアスタリスクが含まれています。 文字「*」のいずれかがマトリックスの最下行にあるか、そのすぐ下に別の文字「*」があることが保証されています。
...........
.........*.
.*.......*.
**.......*.
**..*...**.
***********
山脈の画像の例
観光ルートは、左から右へ山全体を通過します。 毎日、観光客は右に移動します-回路図画像の隣の列に移動します。 もちろん、彼は山の最高点に登る（または落ちる）たびに、対応する列にあります。
最初に観光客が最初の列の最高地点にあり、最後の列の最高地点でルートを終了することを考慮して、2つの量を見つけます。
- 1日の最大上昇（尾根のプロファイルに1つの上昇がない場合は0に等しい）、
- 1日あたりの最大降下（山のプロファイルに降下が1つもない場合は0に等しい）。
解決策 。 この問題を解決するために、各山の高さを計算し、配列h []に格納します 。ここで、 h [j]はj番目の山の高さに等しくなります。 これを行うには、特定の行列をバイパスし、行iおよび列j （行と列のインデックスが0）の要素がアスタリスクに等しい場合、 j番目の山の高さを更新します。h [j] = max（h [j]、 n-i） 。 0からm-2までの列を単純に反復し、現在の列がjである場合、最大上昇または最大下降を値| h [j + 1]-h [j] |で更新します。 。
ソリューション例
int n, m; int h[N]; char c; void solve() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> c; if (c == '*') { h[j] = max(h[j], n - i); } } } int maxU = 0, maxD = 0; for (int i = 0; i < m - 1; i++) { int diff = h[i + 1] - h[i]; if (diff > 0) { maxU = max(maxU, diff); } else { maxD = max(maxD, -diff); } } cout << maxU << ' ' << maxD << endl; }
B.テーブルを組み立てる
Vasyaはn個の脚を持つテーブルを購入しました。 各脚は、互いに接続する2つの部分で構成されています。 各部分は任意の正の長さにすることができますが、 2n個の部分すべてから同じ長さのn個の脚を作成できることが保証されています。 脚をコンパイルするとき、任意の2つのパーツを互いに接続できます。 最初に、テーブルのすべての脚が分解され、ランダムな順序で長さ2nの部分が与えられます。
Vasyaがテーブルのすべての脚を収集し、それらがすべて同じ長さになるようにし、指定された2n個のピースを正しい方法でペアに分割します。 各脚は正確に2つの部分で構成されている必要があり、1つの部分だけを脚として使用することはできません。
解決策 。 この問題を解決するために、まず1つの組み立てられたテーブル脚の長さを計算し、変数lenに保存します（len = sum / n 、ここでsumはすべての部品の合計長、 nはテーブル脚の数）。 脚のすべての部分の長さを配列[]に保存し、昇順に並べ替えます。 次に、0からn -1までの変数iの区間の部分を整理し、それに応じて（a [i]、len-a [i]）の形式のペアを出力します。
ソリューション例
int n, len, sum; int a[N]; int main() { cin >> n; for (int i = 0; i < 2 * n; i++) { cin >> a[i]; sum += a[i]; } len = sum / n; sort(a, a + 2 * n); for (int i = 0; i < n; i++) { cout << a[i] << ' ' << len - a[i] << endl; } }
C.ロボットの経路
n行m列で構成される長方形の市松模様のフィールドが表示されます。 このフィールドには、次のような一連の文字「*」が含まれています。
- サイクルをバイパスするには、各セルを1回だけアクセスし、そのたびに1セルずつ上下、左右に移動します。
- サイクルには自己交差とセルフタッチが含まれていません。つまり、サイクルの2つのセルは、サイクルに沿って移動するときに隣接する場合にのみ隣接します（コーナーに沿ったセルフタッチも禁止されます）。
有効なループの例を次に示します。
サイクル以外のフィールドのすべてのセルには、記号「。」が含まれています。 フィールドには1つのサイクルがあります。 ロボットは、サイクル以外の細胞を訪れることができません。
サイクルのセルの1つにロボットがあります。 このボックスには「S」のマークが付いています。 ロボットがループを回避するための一連のコマンドを見つけます。 可能な4つのコマンドはそれぞれ文字でエンコードされ、1つのセルによるロボットの動きを示します。
- 「U」-セルを上に移動し、
- 「R」-右側のセルに移動し、
- 「D」-ケージを下に移動し、
- 「L」-左のセルに移動します。
ロボットは、各セルを正確に1回ずつ巡回して、サイクルを回る必要があります（開始点を除き、ロボット内でパスを開始および終了します）。
探しているコマンドのシーケンスを見つけます。ループ内の任意の方向が許可されます。
解決策。 最初に、ロボットの開始位置を見つけて保存し、値をアスタリスクの開始位置に割り当てます。 条件により、自己交差とセルフタッチなしで破線が指定されるため、次のアルゴリズムは真です：アスタリスクが含まれる現在のセルに隣接するセルがある場合、値がアスタリスクに等しい次のセルに移動し、その値をポイントに割り当てます（この場合、方向に対応する文字を印刷します私たちが交差した）。 この場合、隣接するセルは、現在のセルにアクセスしたセルとは異なる必要があります。 アスタリスクが付いた隣接セルがない場合、ポリライン全体をバイパスしているため、プログラムを終了する必要があります。
ソリューション例
int n, m, sx, sy; char a[N][N]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; char dir[] = {'U', 'D', 'L', 'R'}; void solve() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; if (a[i][j] == 'S') { sx = i, sy = j; } } } a[sx][sy] = '*'; int px = -1, py = -1; while (true) { bool wasMove = false; for (int i = 0; i < 4; i++) { int nx = sx + dx[i]; int ny = sy + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } if (a[nx][ny] != '*') { continue; } if (nx == px && ny == py) { continue; } a[nx][ny] = '.'; px = sx, py = sy; sx = nx, sy = ny; cout << dir[i]; wasMove = true; break; } if(wasMove) { break; } } puts(""); }
D.犬とボウル
座標線上にn匹の犬が座っており、 i番目の犬は点x iにいます。 さらに、ライン上に食物が入ったm個のボウルがあり、ラインu j上の各座標と時間t jがわかっているため、ボウル内の食物は冷めて味がなくなります。 これは、犬が厳密にt jよりも大きい時間にボウルに走った場合、食べ物が冷えて犬が食べないことを意味します。
各犬が1の速度で走ることを考慮して、食べることができる犬の最大数を見つけます。 犬があなたが指し示す鉢まで走ることを考慮してください。 2匹以上の犬は1つのボウルから食べることができません。
犬は互いに追い越すことができます。つまり、犬の1匹が食べるのをやめた場合、もう1匹は彼女のそばを通り過ぎて別のボウルに着くことができます。
解決策 。 各ボウルがセグメント[u j -t j 、u j + t j ]として表される場合、 i番目の犬は、 u j -t j≤x i≤u j + t jであればjボウルから食べることができます。
私たちは熱心に問題を解決します。 左端の犬と彼女が食べることができるボウルを考えてみましょう。 そのようなボウルがない場合、犬は食べることができません。 そうでない場合は、左端の犬が利用できるボウルから、右端が左端のボウルを選択します。 さらに、この犬とこのボウルを考慮せず、同様に推論を続けます。
そのような欲が最適な答えにつながることは簡単にわかります。
- 左端の犬が食べることができる場合、それを食べることは意味がありません。これは、1つのボウルを削除し、1つのボウルへの反応を悪化させるためです。
- 左端の犬が食べることができるボウルを検討してください。 これらのボウルはすべて、残りの犬が利用できますが、右の境界線が左に遠すぎる犬は例外です。 したがって、ボウルを取りたい場合（そして、ポイント1から実行する価値があると既に理解している場合）、右端が一番左のボウルを取る方が収益性が高いため、右側の犬の選択を悪化させることはありません。
このタスクでは、他の貪欲さを書くこともできますが、多くは間違っています。
これを実現するために、犬とボウルを（左端から）左から右に並べ替えます。 左から右に進み、「ボウルが出現しました」（この場合、その右端をデータ構造に追加します）および「犬が出現しました」（データ構造で犬に最も適した左端を見つける必要があります）のイベントを処理します。
難易度：データ構造に応じてO （ n log n ）またはO （ n ）（* set *またはqueue ）。
C ++ソリューション
ソリューション例
const int N = 200200; int n, m; int x[N]; int u[N], t[N]; bool read() { if (!(cin >> n >> m)) return false; forn(i, n) assert(scanf("%d", &x[i]) == 1); forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2); return true; } pti segs[N]; void solve() { forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]); sort(x, x + n); sort(segs, segs + m); int ans = 0; multiset<int> z; for (int i = 0, j = 0; i < n; ) { if (j < m && segs[j].x <= x[i]) { z.insert(segs[j].y); j++; } else { auto it = z.lower_bound(x[i]); i++; if (it != z.end()) { ans++; z.erase(it); } } } cout << ans << endl; }
E.番号を集める
非負の整数kおよびnの非負の整数a 1 、 a 2 、...、 a nが与えられた場合 。 これらの数字のいくつかを任意の順序で次々と書き留め、場合によってはそれらのいくつかを数回使用し（まったく使用しない）、 kで割り切れる最短の（数字の数だけ）数を決定する必要がありますそれは不可能です。
解決策。 いつでも答えを作成するときは、現在のプレフィックスをkで割った残りだけが重要であることに注意してください。 実際、現在の応答プレフィックスにrに等しいkで割った余りがある場合、プレフィックスに数値a iを割り当てると、この余りは数値rの kで割った余りに等しくなります。•10 l i + a i （ l iはレコードの桁数番号a i ）。
次に、明らかに、レコード内の最小桁数を使用するこのような操作による除算から剰余を取得することに関心があります。 もちろん、空のプレフィックスを使用してすぐに剰余0を取得できるため、剰余0については2番目に大きい答えに関心があります。
上記のすべてにより、 k頂点（それぞれ、0からk -1、残基）でグラフを作成できます。そのエッジは、番号a iによって決定されます：頂点vから頂点まで
これは、長さがl iの場合、 l i桁を追加することにより、剰余vのプレフィックスから剰余uのプレフィックスを取得できることを意味します。 このグラフの一部のa iが同じエッジ（現在はnk ）に対応することに気付くのは簡単です-これらは同じ10進表記とkによる除算の残りの数値であるため、この基準で一意の数値のみを残す必要があります（ありません） 10 kを超える）、エッジの数は10 k 2を超えません。
ここで必要なのは、構築されたグラフで頂点0からそれ自体までの最短の空でないパスの長さを見つけることです。 このような不快な循環を避けるために、頂点0と同じ出力エッジを持つ追加の頂点kを追加します。そのような剰余には空のプレフィックスしか付けられないと仮定します。 これで、問題は頂点kから頂点0までの最短経路を見つけることになり、 O（k 2 ）のダイクストラのアルゴリズムで解決できます。 ただし、問題の特異性により、理論的には大きなO（k 3 ）を持っていますが、Ford-Bellmanアルゴリズム（正しいカットオフを使用）によるソリューションもすべてのテストに合格します。
問題の回答の回復は、最短回答で必要な遷移が行われたエッジを形成する各頂点の追加番号を保存することを除いて、かなり標準的です。
ダイクストラアルゴリズムソリューション
ソリューション例
for (int i = 0; i < n; ++i) { int x; assert(scanf("%d", &x) == 1); any[x % k][length(x)] = x; } p10[0] = 1; for (int i = 0; i + 1 < P; ++i) p10[i + 1] = (p10[i] * 10) % k; for (int i = 0; i <= k; ++i) { d[i] = int(1e9); p[i] = -1; used[i] = false; } d[k] = 0; while (true) { int v = -1; for (int i = 0; i <= k; ++i) if (!used[i] && (v == -1 || d[v] > d[i])) v = i; if (v == -1) break; if (v == 0) break; used[v] = true; for (int r = 0; r < k; ++r) for (int l = 0; l < P; ++l) if (any[r][l] != -1) { int to = (v * p10[l] + r) % k; if (d[to] > d[v] + l) { d[to] = d[v] + l; p[to] = v; w[to] = any[r][l]; used[to] = false; } } } if (p[0] == -1) { puts("NO"); } else { puts("YES"); vector <int> res; int v = 0; do { res.push_back(w[v]); v = p[v]; } while (v != k); reverse(res.begin(), res.end()); for (auto x: res) printf("%d", x); }
A.お気に入りのPolycarp番号
Polycarpは、プログラマーおよび学位2のファンになることを夢見ています。 2つの数字の中で、彼は数字2の大きな力で割った数字が好きです。
正の整数a 1 、 a 2 、...、 a nのシーケンスが与えられた場合、 r-シーケンス内の数字の少なくとも1つが割り切れる最大次数2を見つける必要があります。 さらに、 rで割った数a iの数を印刷する必要があります。
解決策。 この問題を解決するには、2のべき乗が急速に増加し、10 9を超えない数を分割できる2の最大次数が29であるという事実を利用する必要があります。したがって、現在の数が分割される2の最大次数を見つける必要があります、この最大次数で回答を更新します。
ソリューション例
int n, x; int main() { cin >> n; int ans = -1, cnt = 0; for (int i = 0; i < n; i++) { cin >> x; int cur = 1, power = 0; while (true) { cur *= 2; if (x % cur) break; power++; } if (ans < power) { ans = power; cnt = 1; } else if (ans == power) { cnt++; } } cout << ans << ' ' << cnt << endl; }
B.フロア
nの入り口の家があり、各入り口にはm階があり、各入り口の各階には正確にkのアパートがあります。 したがって、この家にはn•m•kのアパートメントしかありません。 自然に1からn•m•kの番号が付けられます。つまり、最初の入り口の1階の最初のアパートの番号は1、最初の入り口の2階の最初のアパートの番号はk + 1となります。 この家の特徴は丸いことです。 つまり、時計回りに移動すると、入口番号1の後に入口番号2があり、入口番号3が続き、入口番号nまで続きます。 入口番号nの後に、再び入口番号1があります。
エドワードはアパートaに、ナターシャはアパートbに住んでいます。 1階への階段の上下への遷移には5秒かかり、入り口のドアから隣の入り口のドアへの遷移には15秒かかり、1つの入り口の同じ階内での遷移は即座に発生します。 また、家のすべての入り口にエレベーターがあります。 それは次のように配置されています。それは常に呼び出しの10秒後に到着し、乗客を1階上または下に動かすために、エレベーターは1秒を費やします。 着陸と着陸は即座に行われます。
エドワードがナターシャのアパートまでの最短時間を見つけるのを手伝ってください。 エドワードは、対応する入り口の1階からのみ入り口を出ることができることを考慮してください（これは即座に起こります）。 エドワードが何らかの入り口のドアの前に立っている場合、彼はそこに入り、この入り口の1階にすぐに現れることができます（これも即座に起こります）。 エドワードは家をどの方向に回るかを選択できます。
解決策。 この問題を解決するには、条件に書かれていることを慎重に実装する必要がありました。 主な難しさは、アパート番号によって入り口番号と階番号を決定することでした。 これは次のように行うことができます。家の入り口がn個 、各入り口がm階、各階がk個のアパートの場合、アパート番号aは入り口番号（ a -1）/（ m•k ）にあり、フロア番号（（a-1）％（m•k））/ k 、およびこれらの番号は0でインデックス付けされており、さらに計算するのに便利です。 入り口と階数を決定した後、2つのケースを検討する必要がありました：エドワードとナターシャの入り口番号が等しい場合（その後、エレベーターに乗るのと階段を上下するのにどちらが最適かを選択する必要がありました）およびこれらの数が異なる場合家が丸いこと、そして正しい方向を選択してください）。
ソリューション例
int n, m, k, a, b; int main() { cin >> n >> m >> k >> a >> b; a--, b--; int p1 = a / (m * k), p2 = b / (m * k); int f1 = (a % (m * k)) / k, f2 = (b % (m * k)) / k; if (p1 == p2) { cout << min(abs(f1 - f2) + 10, abs(f1 - f2) * 5) << endl; } else { if(p1 > p2) swap(p1, p2); cout << min((p2 - p1) * 15, (p1 + n - p2) * 15) + min(f1 * 5, 10 + f1) + min(f2 * 5, 10 + f2) << endl; } }
C.印刷条件
Nチームがプログラミングコンテストの準備のためにトレーニングに参加しました。 各チームのコーチがトレーニングを受け、 i番目のチームのタスクのセットはiページを取ります。 トレーナーには、両面がきれいなx枚の用紙と片面だけがきれいなy枚の用紙があります。 最初のタイプのシートに条件を印刷する場合、タスクの条件から2ページを印刷できます。2番目のタイプのシートに印刷する場合は1ページのみです。 もちろん、2つの異なるタスクセットの条件をシートに印刷することはできません。 両面がきれいなシートを使用する場合、両面に状態を印刷する必要はなく、片方がきれいなままである可能性があることに注意してください。
コーチが完全なタスクセットを印刷できるチームの最大数を決定する必要があります。
解決策。 まず、タスクセットの指定されたサイズを減少しない順序で並べ替えます。 次に、タスクセットの並べ替えを最小のものから開始する必要があります。 現在のセットを印刷できない場合、次のセットは印刷することを保証できません。そのため、回答を印刷してアルゴリズムを終了する必要があります。 そうでない場合は、現在のセットを印刷し、回答を1つ増やして次のセットに進む必要があります。 各セットは、次のように最適に印刷されます。 xを両面シートの残りの数、 yを片面シートの残りの数、 aを現在のタスクセットのページ数とします。 x = 0およびy = 0の場合、現在のセットを印刷することはできません。 aが奇数でy > 0の場合、片面シートに1ページを印刷し、 aおよびyを1つ減らします。それ以外の場合、aが奇数でx > 0の場合、両面シートに1ページを印刷し（これは使用しません）、 aおよびxを削減しますユニットごと。 現在、aは常に偶数です。 したがって、最初に両面シートを印刷に使用し、十分なシートがない場合は片面シートを使用することが有利です。 片面シートが十分にない場合、現在のセットを印刷できません。
ソリューション例
int n, x, y; int a[N]; bool can(int a) { if (a % 2) { if (y > 0) a--, y--; else if (x > 0) a--, x--; else return false; } if (x * 2 >= a) { x -= a / 2; return true; } a -= 2 * x, x = 0; if (y >= a) { y -= a; return true; } return false; } int main() { cin >> n >> x >> y; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int ans = 0; for (int i = 0; i < n; i++) if(can(a[i])) ans++; else break; cout << ans << endl; }
D.メモリの最適化
コンピューターのメモリは、1列に配置されたn個のセルで構成されます。 セルに左から右に1〜nの番号を付けます。 各セルについて、それがフリーであるか、または任意のプロセスに属しているかどうかがわかります（この場合、属するセルはわかっています）。
各プロセスでは、それに属するセルがメモリ内の連続したセクションを占めることが知られています。 「ビジーセルから空きセルにデータを書き換え、現在はビジーなセルを空きと見なす」タイプの操作を使用して、プロセスに属するすべてのセルをコンピューターのメモリの先頭に配置する必要があります。 , ( ) .
, . , , . , , i , j , .
, , - .
解決策。 , . , , ( ) , . : , pos1 pos2 , pos1 , pos2 , pos1. , — , - , , ( , ).
int n; int a[N], need[N]; int szneed; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] != 0) need[szneed++] = a[i]; } int ans = 0; for (int i = 0; i < n; i++) { if (need[i] != 0 && need[i] != a[i]) ans++; } cout << ans << endl; }
E.
n . , , .
, , x i , . , d i , i - . , i - x i + d i . , , .
, , a . . , .
, a . , . , a .
, ( ) . - , , , , .
. , — , , . , a .
. mid — . cnt — , . set'a, , , .
( , ). set' , , , set ans. , set' , , set' .
, set' ans. ans a , mid , mid . ans.
int n, a; vector<pair<pair<int, int>, int > > v; set<pair<int, int> > s; vector<int> ans; int ok (int x) { s.clear(); ans.clear(); for (int i = 0; i < n; i++) { int l = v[i].first.first, r = v[i].first.second; while (!s.empty() && s.begin()->first <= l) { ans.push_back(s.begin()->second); s.erase(s.begin()); } if ((int)s.size() + 1 <= x) s.insert(mp(r, v[i].second)); else { s.insert(make_pair(r, v[i].second)); set<pair<int, int> > :: iterator it = s.end();--it; s.erase(it); } } while (!s.empty()) { ans.push_back(s.begin()->second); s.erase(s.begin()); } return (int)ans.size(); } int main() { cin >> n >> a; v.resize(n); for (int i = 0; i < n; i++) cin >> v[i].first.first >> v[i].first.second, v[i].first.second += v[i].first.first, v[i].second = i; sort(v.begin(), v.end()); int l = 0, r = a; while (r - l > 1) { int mid = (l + r) / 2; if(ok(mid) >= a) r = mid; else l = mid; } ok(r); cout << r << endl; for (int i = 0; i < a; i++) cout << ans[i] + 1 << ' '; cout << endl; }
では最初の予選ラウンドの 929人が参加しました。最良の結果は Vladislav Makeev（モスクワ、ロシア）によって示されました。2位と3位は、ロスティスラフ・ベリチコ（ロシア、スタヴロポリ）とローマゴルブノフ（モスクワ、ロシア）が獲得しました。
2回目の予選では686人が集まりました。格差が大きいので、評価表の 1位は Vlad Mosko（ホメリ、ベラルーシ）でした。2位および3位-ナザルベクアルティバイ（カザフスタン、アクトベ）およびウラジミールロマノフ（モスクワ、ロシア）。
もう一度、私たちはすべてのファイナリストを祝福し、来年の新しい参加者を楽しみにしています。