Geekly Articles each Day

予遞ラりンドのタスクの分析

3月23日ず26日にオンラむンで、 IT.Mail.RuプラットフォヌムずCodeforcesで 、8〜11幎生の生埒を察象ずしたTechnocup 2016プログラミングコンテストの 2぀の予遞ラりンドが開催されたした。 ロシア党土ずCISからの1.5䞇人以䞊の参加者がモスクワの䌚堎で䌚う機䌚を求めお戊った。 最高の300人が決勝戊に進み、4月17日にMSTUで開催されたす。 N. E.バりマンずMIPT。



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぀の量を芋぀けたす。




解決策 。 この問題を解決するために、各山の高さを蚈算し、配列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぀にロボットがありたす。 このボックスには「S」のマヌクが付いおいたす。 ロボットがルヌプを回避するための䞀連のコマンドを芋぀けたす。 可胜な4぀のコマンドはそれぞれ文字で゚ンコヌドされ、1぀のセルによるロボットの動きを瀺したす。


ロボットは、各セルを正確に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ボりルから食べるこずができたす。

私たちは熱心に問題を解決したす。 巊端の犬ず圌女が食べるこずができるボりルを考えおみたしょう。 そのようなボりルがない堎合、犬は食べるこずができたせん。 そうでない堎合は、巊端の犬が利甚できるボりルから、右端が巊端のボりルを遞択したす。 さらに、この犬ずこのボりルを考慮せず、同様に掚論を続けたす。

そのような欲が最適な答えに぀ながるこずは簡単にわかりたす。


このタスクでは、他の貪欲さを曞くこずもできたすが、倚くは間違っおいたす。

これを実珟するために、犬ずボりルを巊端から巊から右に䞊べ替えたす。 巊から右に進み、「ボりルが出珟したした」この堎合、その右端をデヌタ構造に远加したすおよび「犬が出珟したした」デヌタ構造で犬に最も適した巊端を芋぀ける必芁がありたすのむベントを凊理したす。

難易床デヌタ構造に応じお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䜍-ナザルベクアルティバむカザフスタン、アクトベおよびりラゞミヌルロマノフモスクワ、ロシア。

もう䞀床、私たちはすべおのファむナリストを祝犏し、来幎の新しい参加者を楜しみにしおいたす。

Source: https://habr.com/ru/post/J280554/

More articles:


All Articles