問題一覧 > スコア問題

No.5020 Averaging

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 94
作問者 : e869120e869120 / テスター : butsurizukibutsurizuki
2 ProblemId : 10690 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-25 13:30:13

注意

実行時間制限は 1 秒です。
また、ジャッジの調子によって実行時間が最大 0.05～0.1 秒程度大きく表示される可能性があるのでご注意ください。

問題文

机の上に $N$ 枚のカードが置かれており、$1$ から $N$ までの番号が付けられています。
また、各カードの表裏にはランダムな $18$ 桁の整数が書かれており、カード $i$ $(1 \leqq i \leqq N)$ の表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれています。

以下の操作を $50$ 回以内行うことで、カード $1$ の表裏に書かれた整数をできるだけ $5 \times 10^{17}$ に近づけてください。ただし、$\lfloor x \rfloor$ は $x$ の小数点以下切り捨てです。

  • $2$ つのカード $u, v$ $(1 \leqq u, v \leqq N, u \neq v)$ を選ぶ。
  • カード $u, v$ の表面に現在書かれた整数を $a, b$ とするとき、カード $u, v$ の表面の整数を $\lfloor (a+b)/2 \rfloor$ に書き換える。
  • カード $u, v$ の裏面に現在書かれた整数を $c, d$ とするとき、カード $u, v$ の裏面の整数を $\lfloor (c+d)/2 \rfloor$ に書き換える。

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

操作回数を $X$、$i$ 回目の操作 $(1 \leqq i \leqq X)$ で選択する $2$ 枚のカードの番号を $u_i, v_i$ とするとき、以下の形式で出力してください。

$X$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_X$ $v_X$

制約

  • $N=45$
  • $10^{17} \leqq A_i < 10^{18}$ $(1 \leqq i \leqq N)$
  • $10^{17} \leqq B_i < 10^{18}$ $(1 \leqq i \leqq N)$
  • $A_i, B_i$ は制約を満たす整数の中から一様ランダムに選ばれる

採点方法

全操作が終了した時点におけるカード $1$ の表面，裏面に書かれた整数と $5 \times 10^{17}$ の差の絶対値をそれぞれ $V_1, V_2$ とします。
このとき、得点は $\lfloor 2000000 - 100000 \log_{10} (\max(V_1, V_2) + 1) \rfloor$ 点となります。
(万が一 $\max(V_1, V_2) = 0$ となった場合，操作回数を $X$ として，$2000050 - X$ 点が得られます)

ただし、出力が不正である場合は WA と判定されます。不正な出力とは以下を指します。

  • 出力形式に従わなかった。特に $u_i = v_i$ としてしまった。
  • $50$ 回を超える操作を行った。

テストケースは全部で $50$ 個あり，全テストケースの得点の合計が提出の得点となります。
満点は $1$ 億点です。あなたは何点取れますか？

各種ツール

※テスターは「テストケースの入力」と「あなたの出力」をこの順に受け取り、形式があっているかおよび得点を表示するものとなっています。詳しくはプログラム冒頭のコメントをご覧ください。


サンプル

サンプル1
入力
4
330000000000000000 470000000000000000
420000000000000000 280000000000000000
560000000000000000 540000000000000000
770000000000000000 690000000000000000
出力
3
2 3
2 4
1 2

この出力例では、操作を行うことでカード $1, 2, 3, 4$ に書かれた整数が次のように変化します。

  • 操作前の時点
    • 表面: $3.3 \times 10^{17}$、$4.2 \times 10^{17}$、$5.6 \times 10^{17}$、$7.7 \times 10^{17}$
    • 裏面: $4.7 \times 10^{17}$、$2.8 \times 10^{17}$、$5.4 \times 10^{17}$、$6.9 \times 10^{17}$
  • $1$ 回目の操作後
    • 表面: $3.3 \times 10^{17}$、$4.9 \times 10^{17}$、$4.9 \times 10^{17}$、$7.7 \times 10^{17}$
    • 裏面: $4.7 \times 10^{17}$、$4.1 \times 10^{17}$、$4.1 \times 10^{17}$、$6.9 \times 10^{17}$
  • $2$ 回目の操作後
    • 表面: $3.3 \times 10^{17}$、$6.3 \times 10^{17}$、$4.9 \times 10^{17}$、$6.3 \times 10^{17}$
    • 裏面: $4.7 \times 10^{17}$、$5.5 \times 10^{17}$、$4.1 \times 10^{17}$、$5.5 \times 10^{17}$
  • $3$ 回目の操作後
    • 表面: $4.8 \times 10^{17}$、$4.8 \times 10^{17}$、$4.9 \times 10^{17}$、$6.3 \times 10^{17}$
    • 裏面: $5.1 \times 10^{17}$、$5.1 \times 10^{17}$、$4.1 \times 10^{17}$、$5.5 \times 10^{17}$

操作終了後における、表面に書かれた整数、裏面に書かれた整数と $5 \times 10^{17}$ の差はそれぞれ $V_1 = 2 \times 10^{16}, V_2 = 10^{16}$ になります。
したがって、$\lfloor 2000000 - 100000 \times \log_{10}(\max(2 \times 10^{16}, 10^{16}) + 1) \rfloor = 369897$ 点が得られます。

なお、このケースは $N = 4$ であり、本問題の制約を満たさないことに注意してください。

サンプル2
入力
45
289586524206551660 997395148538617857
630842708759083208 903057009479348554
168800566543912550 338947656203965873
222224592527653776 311211471881064265
505824727473538422 449953596417203782
571686021890854646 829883490501193652
971485081335135188 273649015144196660
111593213767681689 938548193881533285
996057914557966198 214465285013333065
512642506694182882 867693120286622008
531366207406474228 545798559445071224
509470049801046195 240028387458627871
391471341433721829 584649425246804008
312558163555023756 889467022058303548
235120745469700738 337399751870273529
691232514809270268 686423861590637190
319248786888549368 150579841793085099
908586429972649265 272018288972144387
585544108629690316 359952081275789037
543305026889212081 288592130551997817
836492684205120939 550527188379179865
526926164721434493 783667829918754421
234837638419894578 881770898617875748
692508581731762487 172374432288422288
552867669703477851 632212673224090015
695765100793939871 809429556354646333
314881505542257819 301299939198161480
797869490330772218 126405017905097955
311625625888231713 968489123844792816
399380755038775673 417203257720671584
908362361211395668 664375711944810034
493404839211433446 123730441686104757
844345388663133576 617914972005338364
960415910879171012 934157361631598004
844962750654814254 526278860879008830
448414753123900015 915752247603067643
326829276890177588 122045564955653890
545999927694093931 272420410152660242
937060355446460529 588226947354262138
998450284114347813 754199297503722361
588080145009522224 223749368027749301
314286963374802948 221072242222867899
587006726109412201 631227557484822910
778568593379650583 512735661914434392
230803758947049145 788943904013153217
出力
5
23 28
21 37
21 23
2 21
1 2

この入力例は本問題の制約を満たします。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。