問題一覧 > スコア問題

No.5020 Averaging

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 101
作問者 : e869120 / テスター : butsurizuki
お気に入りにしたユーザー ProblemId : 10690 / 自分の提出
問題文最終更新日: 2024-02-25 13:30:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder score contest 9 (順位表) の他の問題:

Note

The execution time limit is 1 second.
Also, please note that depending on the condition of the judge, the displayed execution time may be larger by up to about 0.05 to 0.1 seconds.

Problem Statement

There are $N$ cards placed on a desk, numbered from $1$ to $N$.
Each card has random $18$-digit integers written on its front and back: card $i$ $(1 \leqq i \leqq N)$ has the integer $A_i$ written on its front and the integer $B_i$ written on its back.

By performing the following operation at most $50$ times, make the integers written on the front and back of card $1$ as close to $5 \times 10^{17}$ as possible. Here, $\lfloor x \rfloor$ denotes $x$ with its fractional part truncated.

  • Choose $2$ cards $u, v$ $(1 \leqq u, v \leqq N, u \neq v)$.
  • Let $a, b$ be the integers currently written on the fronts of cards $u, v$. Rewrite the integers on the fronts of cards $u, v$ to $\lfloor (a+b)/2 \rfloor$.
  • Let $c, d$ be the integers currently written on the backs of cards $u, v$. Rewrite the integers on the backs of cards $u, v$ to $\lfloor (c+d)/2 \rfloor$.

Input

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

Output

Let $X$ be the number of operations, and let $u_i, v_i$ be the numbers of the $2$ cards chosen in the $i$-th operation $(1 \leqq i \leqq X)$. Output in the following format.

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

Constraints

  • $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$ are chosen uniformly at random from the integers satisfying the constraints

Scoring

Let $V_1, V_2$ be the absolute differences between $5 \times 10^{17}$ and the integers written on the front and back of card $1$, respectively, after all operations are finished.
Then, the score is $\lfloor 2000000 - 100000 \log_{10} (\max(V_1, V_2) + 1) \rfloor$ points.
(In the unlikely event that $\max(V_1, V_2) = 0$, you get $2000050 - X$ points, where $X$ is the number of operations.)

However, if your output is invalid, it is judged as WA. An invalid output means any of the following.

  • The output does not follow the output format. In particular, it has $u_i = v_i$.
  • More than $50$ operations are performed.

There are $50$ test cases in total, and the sum of the scores over all test cases is the score of the submission.
The maximum score is $1$ hundred million points. How many points can you get?

Tools

* The tester takes "the input of a test case" and "your output", in this order, and displays whether the format is correct as well as the score. For details, see the comments at the beginning of the program.


Sample

Sample 1
Input
4
330000000000000000 470000000000000000
420000000000000000 280000000000000000
560000000000000000 540000000000000000
770000000000000000 690000000000000000
Output
3
2 3
2 4
1 2

In this sample output, the operations change the integers written on cards $1, 2, 3, 4$ as follows.

  • Before the operations
    • Front: $3.3 \times 10^{17}$, $4.2 \times 10^{17}$, $5.6 \times 10^{17}$, $7.7 \times 10^{17}$
    • Back: $4.7 \times 10^{17}$, $2.8 \times 10^{17}$, $5.4 \times 10^{17}$, $6.9 \times 10^{17}$
  • After the $1$st operation
    • Front: $3.3 \times 10^{17}$, $4.9 \times 10^{17}$, $4.9 \times 10^{17}$, $7.7 \times 10^{17}$
    • Back: $4.7 \times 10^{17}$, $4.1 \times 10^{17}$, $4.1 \times 10^{17}$, $6.9 \times 10^{17}$
  • After the $2$nd operation
    • Front: $3.3 \times 10^{17}$, $6.3 \times 10^{17}$, $4.9 \times 10^{17}$, $6.3 \times 10^{17}$
    • Back: $4.7 \times 10^{17}$, $5.5 \times 10^{17}$, $4.1 \times 10^{17}$, $5.5 \times 10^{17}$
  • After the $3$rd operation
    • Front: $4.8 \times 10^{17}$, $4.8 \times 10^{17}$, $4.9 \times 10^{17}$, $6.3 \times 10^{17}$
    • Back: $5.1 \times 10^{17}$, $5.1 \times 10^{17}$, $4.1 \times 10^{17}$, $5.5 \times 10^{17}$

After the operations are finished, the differences between $5 \times 10^{17}$ and the integers written on the front and back are $V_1 = 2 \times 10^{16}, V_2 = 10^{16}$, respectively.
Therefore, you get $\lfloor 2000000 - 100000 \times \log_{10}(\max(2 \times 10^{16}, 10^{16}) + 1) \rfloor = 369897$ points.

Note that this case has $N = 4$ and does not satisfy the constraints of this problem.

Sample 2
Input
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
Output
5
23 28
21 37
21 23
2 21
1 2

This sample input satisfies the constraints of this problem.

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