AT_ahc053_a.[AHC053A] Random Sum Game

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 张空白卡片，以及一个随机数生成器，每次独立等概率地生成 $M$ 个在 $L$ 到 $U$ 间（包含两端）的整数。

你可以利用这些物品进行如下游戏：

首先，你可以任选 $N$ 个在 $1$ 到 $U$ 之间（包含两端）的整数 $A_1, \dots, A_N$ ，并将 $A_i$ 写在第 $i$ 张卡片上。
接着，使用随机数生成器生成 $M$ 个整数 $B_1, \dots, B_M$ 。
你可以丢弃任意数量（可以为零）的卡片，并将剩下的卡片分成 $M$ 个堆（每个堆可以为空）。

本游戏的目标是使得第 $j$ 堆卡片上数字的和尽可能接近 $B_j$ 。

输入格式

首先，标准输入给出 $N, M, L, U$ 。

$N$ $M$ $L$ $U$

接下来，你需要输出你写在第 $i$ 张卡片上的整数 $A_i$ ，即：

$A_1$ $A_2$ $\dots$ $A_N$

然后，标准输入会给出 $B_1, \dots, B_M$ 。注意，你必须在读入 $B_1, \dots, B_M$ 之前先输出 $A_1, \dots, A_N$ 。

$B_1$ $B_2$ $\dots$ $B_M$

最后，令 $X_i = 0$ 表示你决定丢弃第 $i$ 张卡片，否则 $X_i$ 为该卡片所属的堆编号，则输出如下内容：

$X_1$ $X_2$ $\dots$ $X_N$

所有输出均须以换行结尾，并且必须及时刷新标准输出。 否则你的提交可能被判为 TLE。

输出格式

（见上文，严格按照流程输出。）

输入输出样例

输入#1

500 50 998000000000000 1002000000000000
998048751022181 998097465238075 998160669164017 998231311927150 998239693029031 998356130354587 998446906912252 998555170329840 998587344209968 998743301391436 998760667153740 998947286002826 998981740663966 999002845061505 999059061039867 999128286657558 999297656665943 999358823245113 999383413043563 999640703784442 999733472254114 999790366912377 999873266864151 999911534238464 999985985322908 1000010039870477 1000155426700245 1000265729136158 1000462334004741 1000565907102777 1000908034069731 1000951689976892 1000957188499933 1001083800047313 1001089587866566 1001202738050092 1001213435143294 1001225125980911 1001264019997723 1001404093183272 1001438327970254 1001443079569383 1001470062137717 1001585047564559 1001647141491385 1001664377029572 1001719343473297 1001731992430657 1001856451123514 1001928070662947

输出#1

4878135165674 172326132447595 37202234641402 179431630606157 22367690958241 99398565411526 17824324247087 29396577708895 113399743264687 145547105190040 64947716130460 8041491659091 186153140838491 161417555344578 163364200886004 38071391044721 182539431643788 93757006550779 11996636103012 183402070330078 89607863964449 27786275008532 69239822830324 49136120231533 95672288635106 107879106347250 186786221154355 160297039407090 173676609992710 123239816937288 147732083343410 160832428921840 56470747210805 82117224411351 128423650493987 154633872721597 165169521845991 70255087030182 186572488881683 85439423821558 58152155997326 113618217535512 23882336450073 29752867394401 40457796217587 88890100631976 181087482270344 179986532653780 186706357607984 162995007233097 51685901010151 34543683177733 184821641872661 9922581656873 118951828724908 172903355502154 158679627525888 137644767545187 1484850762556 196534224073290 121459351324523 168299978302008 60944453351792 98306564918571 98768117836360 32112998518513 22997838188543 16455218429428 184259712368439 95537956840974 20919714353586 72020282672271 196247456599359 73941973388422 149236730610450 52485558481602 43493879692637 111603487439157 91759098122681 106715798633341 25210134755121 168300981395261 68340092630266 7430989215844 255948408716 97897054411036 130970562942448 44234375773267 66688744234018 80363807275344 999759229847 78846688047077 35850416458440 118583097897305 41122108594995 116303652201362 100061923053820 82501051140921 133357886790151 55090967001663 131304026084121 136925409307094 173368272000661 41626860889009 121428782438741 115572283528675 146423877816698 138031240524283 6717105403927 96608107714415 181007758631780 163877461949056 58454026019942 173196381965721 83828254837946 27365965733613 123357685059832 152596661570638 168772870853853 183312512983498 72099524059729 156563719085081 37888171573095 86554156846695 93147007113874 171469180745630 14097649901745 31642505205254 713423490455 88132079701089 124545849345520 187043575495050 36946902864744 177309905024870 72530014930894 169674427938233 195621165200923 140576224915409 99274073814560 102951256656572 172002076869867 59678511021248 75194562569283 9626630468247 105910621886896 94062638028883 122389468398863 46609092476282 4985552734866 61080368992110 53508526864073 172110906291877 176877471908897 14298711632677 142156157487527 150831453521045 183576069482621 52371179625372 1412906974299 189653636558272 51220025173479 148975694622164 181724306775374 89744964521615 131295610053372 2590815627792 192328196506106 39337115429624 170946916963496 39099297719195 128886977076631 25857457400956 60828845467996 137937772601196 186539553326175 118628720437323 22740560815040 32127562955244 111376849651706 145257937590880 110723236219145 83330438465209 82268448952537 90779305894112 90066039098188 147095579827980 21270390659068 178279531945620 188702608162194 138970675846999 179199841047764 10505540671149 127263507906826 33779747700612 71591466780914 174617160129776 15220613853398 52591103564346 169360727859377 169108191893272 100132914534280 28723473275891 145508315896063 93814367491764 144414660116168 182070949734662 40102232584838 119636928819560 158407162710531 68625771826872 184870633286453 115922564933721 182922994791461 18516054760902 14288014986112 49731205356588 10556409317904 170574585419890 122955587097328 85732667255915 96356425915233 11774646353401 178614301383248 82558769381361 134697814075593 110565440004523 144177805777389 125842285793939 8465244499153 94053608125699 39611240421516 122771385439740 61418965802239 13803310002798 17153208186981 119693183026114 108963986033121 65747076614118 2671683167441 100014888277582 70208418523084 159454683955675 112790013691428 6328351676530 156349227922601 33481921959577 170856378368027 175855067043622 137190398191239 83044982447778 186978987219399 103958506918023 45093201844654 161534205407947 50558485129243 36756822846247 153489552211551 50976437431565 41742725652071 81157600953482 82743905702820 57463466072779 16864262492832 171031317985052 28552729328470 112418729957187 64856983187947 32283214334592 184882565676855 70921420401542 197531816179421 66260899495672 60031062654143 128561855849628 83296671384322 188072074415948 178231361352151 139601346027959 12824871094282 174441381840862 180581455884322 111422528264219 74908013766526 134746087433292 150824226252954 3035807639624 182056318780230 134568379722977 14996909923429 182622933284308 16733112125628 95372276370077 143158533546015 56806235477872 167805618225379 140635352935877 67576911563512 138808628160563 126060203974782 20634421177558 126346362865335 98784836561996 169028717310920 170932178231975 19172454215188 84386611637990 9255070357080 7975051479486 132340262678558 170774679947766 192104077767922 108745972848169 28251722938866 101231189697417 151177096307487 179791735550912 132045208186974 129700386641024 144403539116628 120079072529471 130711033054180 65505445939571 46016715076369 129171288926382 2890937548515 145968870552900 8473245816885 98721972867807 72808700369821 72363694581243 14219803286375 135982890036939 59216277883645 17875239026147 126050561885428 3793867036083 25069188909350 117454914636137 71825141386803 131938644075847 62919626819569 114044609539001 162386374310262 191558861552155 88417991497924 134350026539719 139240241374351 118122484902032 135969169383890 135383435476544 135236033638258 186001980751576 12331091837718 80965586517937 161492734633433 146948578829553 12322916148648 106326973402872 49157653543345 10248771076624 153621218916668 195198717780981 119314003745779 8260621590103 88788369013311 126948859664262 198030790502127 83796285967079 30731003849877 118036767880863 156966579482908 106944110944473 21556972876621 182306346940970 170450729202618 179189998727061 32945344398161 17666227026372 103276778263200 9981772578193 172192988856161 65323463579776 102185261498215 150486758294142 168272143224048 123666132438239 147950832737525 171402302238576 198700117919153 167290691980569 168129944540979 117552381019941 187585757097214 175141758043647 130145830770936 57991522347982 154471218782648 27219258762438 21367282114513 19070893688260 175793297364949 198958857319612 136337706007903 107891186620455 169338983484102 85474384580638 83482727117575 67994458181177 195451885960117 114463291839175 48014878655077 143818768310668 35873448699819 177890742562013 96335264389904 170866019123168 98181817198380 116006884690068 168203744273897 4339556785459 7240291505220 185055391999168 108456222200551 161118035855103 24197494785580 70383345957319 121822320201028 137697714709924 83491962095088 149793354643819 27194438908817 26043949921522 10769139969436 88529055839894 40746686837330 137444894997926 154611019704281 121037097818825 181201284000346 128259672114033 8234686502222 150406687151262 21828408625836 105236136708969 157017081160908 55151537773195 89897755449857 193497441845784 138839670436556 163754806508898 6130465987016 68846536751091 161010225663027 43787287494878 79370144078391 47716191961908 74151658516207 49351614882612 124933582980482 123710529331129 101337398892978 142083098747328 36743418081469 149196407314378 51944332582786 145669941720490 56597917020857 12426505177843 156071139797657 31098037318727 16899910384718 135564146864309 96155571382511 166761714979224 119660585662407 116556521900921 13075867757727 171927078030575 86516005760349 52334884486392 149027530548370 104989284110206 154360637696623 71358775898907 180832050301676 116945212143556 95494443632798 10760652483995 53199554778214 151072121271245 42638833672648 130633371745118 9959284633009 50002383926970 196370811167142 7381860299092 57108437698439 172561772310397 119680733426256 174053340728435
12 42 0 0 37 11 28 38 18 26 48 29 2 37 22 35 27 15 25 1 2 18 26 46 47 45 4 0 6 4 19 15 13 37 49 30 45 30 24 14 45 20 46 31 30 37 13 28 17 28 3 23 44 10 46 7 27 35 21 48 6 9 26 46 15 37 23 0 23 30 29 34 45 36 5 25 28 28 20 18 8 43 47 36 15 25 8 46 0 13 34 25 41 28 30 41 22 43 31 40 44 41 2 30 30 15 46 21 40 13 9 7 29 4 50 43 50 40 40 23 5 12 22 37 44 27 33 49 45 30 11 18 11 11 30 36 25 43 34 33 39 36 38 43 46 21 43 0 5 49 0 21 47 27 27 20 40 21 8 29 13 3 29 17 39 41 50 20 4 43 18 9 15 36 44 2 48 20 13 1 25 39 7 38 40 20 31 16 3 6 28 4 9 40 46 16 22 8 10 4 24 18 40 16 44 48 21 16 11 7 50 24 32 4 2 33 5 11 3 11 4 5 38 20 34 22 39 6 25 18 44 39 9 49 29 38 6 21 4 28 37 24 32 48 2 8 10 42 33 42 33 45 11 34 44 34 48 0 23 21 11 45 24 18 21 47 31 23 19 6 9 38 13 36 42 20 36 1 18 1 45 27 33 50 39 25 47 43 15 3 25 46 6 14 43 10 48 26 40 9 7 5 18 48 41 20 9 46 16 28 6 22 31 19 32 26 40 12 24 37 17 7 12 3 1 35 19 26 41 15 50 42 38 44 7 41 15 5 47 7 44 20 3 0 22 32 33 0 38 22 46 43 26 31 11 28 8 6 26 4 32 2 7 19 28 37 5 0 5 40 33 45 10 18 41 15 44 24 31 17 4 31 36 17 25 11 15 44 32 41 27 29 6 29 8 4 10 23 42 19 37 0 46 5 27 26 46 13 23 12 46 22 49 39 42 31 45 27 24 0 49 19 30 29 32 0 30 21 49 9 44 22 37 48 42 1 37 38 1 5 13 44 12 43 17 10 38 27 26 27 8 47 50 49 19 44 4 32 4 2 2 6 26 3 49 20 41 34 29 47 43 31 12 38 19 17 21 42 27 15 48 32 24 2 31 7 45 39 26 26 33 38 1 40 32 42 23 40 25 11

说明/提示

评分方式

设第 $j$ 堆卡片上数字的和为 $S_j$ ，定义误差 $E = \sum_{j=1}^M |S_j - B_j|$ 。则你的得分为 $\mathrm{round}((20 - \log_{10}(1 + E)) \times 5 \times 10^7)$ 。

一共有 $150$ 组测试数据，提交的总得分为所有测试数据的得分总和。如果在某些测试点输出不合法或超时，整份提交将被判为 WA 或 TLE，得分为 $0$ 。比赛时只计最高得分，不进行赛后系统测试。多名选手得分相同，则算并列，不区分提交时间先后。

输入生成方式

$N = 500, M = 50, L = 10^{15} - 2 \times 10^{12}, U = 10^{15} + 2 \times 10^{12}$
生成 $M$ 个在 $L$ 到 $U$ 之间（包含两端）的整数，独立均匀随机，记为 $B_1, \dots, B_M$ ，并升序排列。

工具（输入生成器与可视化工具）

网页版：功能比本地版更强，还提供动画展示。
本地版：需有 Rust 语言编译环境。
- Windows 预编译版：如果你不熟悉 Rust 环境，请使用此工具。

请注意，比赛期间禁止公开可视化结果、讨论解法或相关想法。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页