No.5020 Averaging
タグ : / 解いたユーザー数 101
作問者 :
e869120
/ テスター :
butsurizuki
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
- Sample code (C++): https://gist.github.com/E869120/1ac9446bda7e56d645e36b6ea089198b
- Sample code (Python): https://gist.github.com/E869120/318aee53dceec70ddae8c617651800ed
- Input generator: https://gist.github.com/E869120/8a377040752ce1c98fb0fb7bca2b03ff
- Tester (C++): https://gist.github.com/E869120/172754b158c84148bbc97f6f494f048e
- Tester (Python): https://gist.github.com/E869120/b65313bec5d6e46daecc264a7593c893
- Example test cases (seed 1-50): https://drive.google.com/drive/folders/1HLh9iMP3WAPUYLsvr_LMPW6-4nVpJBEG?usp=sharing
* 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もしくは右上の雲マークをクリックしてアカウントを作成してください。