#include<bits/stdc++.h>
#define 悴んだ心_ふるえる眼差し int 
#define 世界で_僕は_ひとりぼっちだった a
#define 散ることしか知らない春は ,
#define 毎年_冷たくあしらう b;
#define 暗がりの中_一方通行に cin
#define ただ_ただ_言葉を書き殴って >>a
#define 期待するだけ_むなしいと分かっていても >>b;
#define 救いを求め続けた_せつなくて_いとおしい int sum
#define 今ならば_分かる気がする_しあわせで_くるおしい =
#define あの日泣けなかった僕を_光は_やさしく連れ立つよ a+b;
#define 雲間をぬって_きらりきらり_心満たしては_溢れ cout
#define いつしか頬を_きらりきらり_熱く_熱く濡らしてゆく <<
#define 君の手は_どうしてこんなにも温かいの sum;
#define ねぇお願い_どうかこのまま_離さないでいて return 0;

using namespace std;
int main(){
    悴んだ心_ふるえる眼差し 世界で_僕は_ひとりぼっちだった 散ることしか知らない春は 毎年_冷たくあしらう
    暗がりの中_一方通行に ただ_ただ_言葉を書き殴って 期待するだけ_むなしいと分かっていても
    救いを求め続けた_せつなくて_いとおしい 今ならば_分かる気がする_しあわせで_くるおしい あの日泣けなかった僕を_光は_やさしく連れ立つよ
    雲間をぬって_きらりきらり_心満たしては_溢れ いつしか頬を_きらりきらり_熱く_熱く濡らしてゆく 君の手は_どうしてこんなにも温かいの
    ねぇお願い_どうかこのまま_離さないでいて
}

以下參考測資對於已AC的 Submission 411903 將造成WA。
事實上用random_shuffle去產生一些測資，會發現該Submission的作法對於1499個箱子很常呼叫Med3()超過7777次。
該Submission的作法應該與多數人提交的作法相似，蠻容易被卡掉的。

參考測資:

Called Med3() 10284 times
Numbers inside the 1499 boxes:
108 74 1406 584 159 151 1081 1317 1264 984 1371 1363 1130 543 680 1083 1336 1068 155 918 110 696 1022 88 1475 363 6 411 1353 727 297 149 950 9 712 1325 568 219 111 1461 497 768 2 37 1452 736 19 162 223 959 1177 625 1154 522 490 247 743 1251 1242 1471 402 106 617 613 1379 751 258 113 83 142 451 1093 693 1408 928 415 774 1446 389 256 666 485 1391 908 243 287 16 1465 332 75 1215 1125 114 1119 131 721 1133 972 1170 864 487 957 5 1021 1493 795 1074 899 1326 1272 1141 160 70 577 675 230 447 1006 1351 261 128 1029 1357 266 640 286 1304 432 1283 1015 596 1239 1425 755 963 1091 1149 762 637 269 1494 1301 676 1331 172 1126 413 461 603 1407 1174 772 566 998 501 1276 218 1373 598 312 245 1447 274 1098 655 1197 1462 17 623 639 190 1291 694 295 1427 1440 1148 1458 499 42 1142 699 1280 351 541 668 1094 803 466 888 688 212 1302 359 164 421 790 1355 46 690 321 789 1162 630 569 582 1274 559 456 868 512 284 213 1038 537 965 1261 1362 1341 682 547 1005 1157 851 464 189 713 1403 345 1313 66 146 1360 697 632 609 1398 1456 1399 12 612 1016 1277 181 1328 158 383 1449 39 130 937 334 1285 436 85 1323 1203 1070 954 1364 1072 777 282 709 265 231 992 1150 936 91 33 1275 1019 1090 81 553 457 763 924 576 518 281 495 554 208 403 433 510 874 488 279 69 1257 170 555 594 1405 1438 483 1028 1108 228 1484 634 614 349 1122 714 234 801 1359 467 610 1088 706 646 686 546 1400 283 1120 453 733 1235 310 620 1286 633 120 1454 931 141 970 390 1392 72 1279 329 895 1143 534 1463 572 1287 1222 263 1404 842 94 747 975 203 498 337 362 1236 254 1335 1210 98 1492 540 477 249 204 1310 193 592 663 856 1232 1290 259 1051 915 933 222 1188 616 764 538 31 1466 444 578 588 802 1381 671 1000 358 1056 838 1041 1032 551 778 1 909 324 446 1076 825 1432 115 82 1166 754 855 288 1266 326 857 29 1343 739 163 638 1010 823 23 285 132 1483 51 235 816 1200 177 1078 1347 291 887 1334 976 591 808 173 1376 590 1289 225 780 1191 1374 793 1209 1030 544 355 519 955 597 729 999 1144 811 135 564 11 658 397 1087 1320 1186 1444 420 198 1173 628 404 1487 1455 1499 491 1121 77 127 1099 270 849 361 807 4 701 1383 121 1189 253 611 608 1161 914 1097 1003 1344 883 86 468 891 503 993 241 758 643 1063 724 28 1388 980 301 1134 161 798 1212 872 940 1390 105 103 1319 35 618 293 1045 1001 817 995 1268 304 65 438 298 1065 1298 1473 1061 1488 508 1385 1042 728 1013 1327 1084 644 1106 117 1101 248 1413 1233 507 1039 1123 430 1457 935 1047 1423 476 710 1055 1433 979 527 20 604 469 988 916 143 635 169 708 845 1282 1180 440 139 1115 1472 196 1007 260 656 463 371 1037 575 991 192 587 705 571 898 698 1089 207 894 725 1311 21 320 750 536 930 458 645 1396 378 513 123 474 958 494 237 837 1337 836 629 966 1402 532 56 496 7 62 273 964 631 486 422 129 1464 1206 996 45 850 1198 369 1135 756 1308 589 665 1442 1017 366 570 101 796 1416 775 813 922 1418 1217 367 1397 685 60 1485 57 1478 956 702 26 54 1307 333 481 454 1151 387 364 1245 49 267 325 331 1018 1426 726 670 760 36 153 157 180 424 1340 770 505 165 1474 380 786 1035 1346 147 586 445 1225 619 947 848 425 642 810 1178 759 280 732 152 830 303 178 791 761 80 944 806 347 148 649 328 515 392 1201 294 250 1221 948 875 489 1004 275 523 509 771 1324 276 731 1082 1329 356 1422 1496 1294 13 969 627 878 1034 1338 1443 442 684 18 1124 1477 449 865 313 1059 1293 1259 961 493 1267 677 858 986 400 662 1445 1393 323 934 1250 967 1109 879 426 562 1476 25 903 746 938 395 580 844 511 1025 783 615 641 55 1167 561 126 1243 292 1369 520 1080 1495 809 831 1254 418 794 982 929 122 1139 1077 242 1092 1333 209 1295 1375 744 1434 1011 1172 822 890 1009 983 902 1380 1356 805 197 1252 1155 832 319 1439 829 1086 166 784 199 338 734 431 1073 839 1229 1095 654 1112 1453 1040 622 322 79 470 1470 15 861 1062 1389 952 240 921 24 376 144 524 781 835 410 465 405 394 133 1342 1240 300 278 927 1421 179 1367 542 336 125 1218 1179 773 188 302 102 1249 1262 1053 893 1048 1164 1044 119 58 252 1024 535 1192 953 174 824 549 370 448 516 973 1075 1330 374 201 911 416 44 828 471 186 660 1153 305 1204 257 687 500 1008 1031 1137 97 1417 862 827 1377 1185 386 583 307 1114 877 1288 517 1428 932 408 1136 187 372 1368 1129 1085 1306 913 377 315 753 723 1382 50 168 1469 388 814 636 211 1497 873 1100 1482 548 398 1435 717 650 1352 1117 236 1348 191 667 171 704 1255 560 232 76 846 492 748 606 1378 484 1147 945 316 1027 1468 602 648 443 1395 1237 1450 834 951 942 427 1234 1079 1012 73 563 1350 820 1160 819 707 917 78 1228 373 1491 719 1026 393 901 906 1441 741 227 853 357 1033 53 1409 1183 910 194 905 264 1193 585 1489 314 740 340 1273 229 735 353 981 409 971 318 112 109 14 1467 52 1158 423 1138 1358 1002 459 826 450 1297 1194 271 521 679 379 1411 815 89 87 1168 889 1260 375 382 593 621 368 206 904 92 653 841 145 1202 10 939 1216 150 226 896 30 1430 1208 525 352 1169 923 1258 1052 974 695 156 989 912 1156 435 745 306 659 506 1103 1146 1419 1118 847 1296 8 202 715 99 1187 22 71 1195 920 47 1498 391 118 946 769 581 214 776 765 1182 876 854 866 800 472 100 399 907 1060 1451 716 246 692 657 1284 1459 1269 1223 689 460 224 412 317 925 674 1365 859 664 669 296 752 757 766 1159 539 1481 1181 779 233 1054 1207 38 239 871 1318 1412 1226 185 530 1231 140 1431 1309 787 700 176 59 595 601 27 720 880 1270 93 175 407 882 1211 64 599 251 124 1349 184 1401 767 195 429 1387 1410 579 1415 788 1196 962 67 799 478 1436 479 1227 792 1248 1111 1107 1480 1171 1105 818 210 919 344 217 1263 1050 434 342 277 1127 183 785 1043 455 262 1420 401 1370 1460 558 722 892 1332 567 137 63 482 1490 360 843 116 1219 475 672 1116 673 40 452 1165 1220 48 531 1071 949 1128 869 289 994 1448 651 1299 1064 1479 95 1253 104 1110 1230 821 985 327 255 833 61 661 647 1057 1366 678 652 437 1152 1205 600 154 272 742 1020 1361 607 441 738 96 341 339 1190 414 1305 343 711 529 1271 730 1066 683 167 381 1414 990 335 330 867 573 396 268 1036 804 514 1140 852 1300 406 1278 557 1199 1345 897 737 244 1224 1314 238 220 1131 502 960 41 473 886 1163 1214 624 1096 480 1238 385 703 1339 718 1247 215 782 941 997 1104 968 419 1486 84 797 1322 1113 681 1292 3 216 1312 884 1429 556 32 1372 354 384 626 1058 1281 348 1394 1184 900 885 428 840 1023 1213 1265 1145 200 533 528 1049 1384 43 462 545 526 1175 1102 68 1069 1176 1315 605 1256 552 308 1316 749 977 881 565 574 1132 978 691 1244 870 417 34 134 926 350 1386 346 1241 943 439 90 107 550 311 1014 309 1424 1321 812 1067 290 205 863 1303 138 221 504 1437 1046 860 1354 299 987 1246 182 365 136


我並不會這題，但有個怎麼看都是錯的方法卻能通過：

直接輸出 $C(N,3) - \sum(C(k_i,3))$，若這個值小於 0 則是 IMPOSSIBLE。

但例如說這樣的測資：

4
2
3 3

在歐式幾何公里的假設根本不可能存在只有 4 個點，但有 2 組三點貢獻，答案應該要是 IMPOSSIBLE，但程式碼輸出 2 卻能通過。這題好難啊，真的能好好判斷在給定的共線組合下，至少有多少點嗎？

[TIOJ 1347 希爾伯特的書架]
Submission 406621 和 406622 都獲得 AC，實際上為假解，無法通過以下此筆測資：

10 41 12
46 31 3 37 14 42 14 35 20 40
42 20 27 22 46 2 14 33 2

正確答案應為 158056385568438181，但以上兩個 submission 的 code 輸出結果為 158056385568438182。

經過 debug 後發現原因為某些大整數轉成double型態比較時會有精度問題，例如：

//c++
(double)(1LL<<53) == (double)((1LL<<53)+1) //true

此問題可以將double改為long double或__float128解決，即 Submission 406620 的 code。然而 128 bit 浮點數的計算時間比較久，此題時限很緊，會吃 TLE。

看了一些網路上其他 AC 的人的 code，發現也無法通過上述測資。不知道此題是否有其他能在時限內 AC 的解法？ 若沒有，是否考慮把時限設大一點讓 128 bit 浮點數計算的解法能 AC 呢？

P.S. 正確答案我是將上述 submission 的 code 轉成python作為依據，畢竟它能直接作大整數運算，就沒有浮點數精度問題了。

2313

為什麼會RE？
在本地範測是能通過的，但提交後就完全RE了。理論上來說，是不可能出現RE的情況的。
我甚至把包括輸入後面的所有部分全部註釋掉了，還是會RE。

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int N=2e7+10;
const ll INF=1e18;

struct edge
{
    int u,v,w,nxt;
}e[N<<1];
int head[N],tot;
void add(int u,int v,int w)
{
    e[++tot]=edge{u,v,w,head[u]};
    head[u]=tot;
}

int n;
int a[N],b[N];

map<int,int> mp;
int idx;
void init(int p)
{
    int x=a[p];
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
        {
            if(!mp[i]) mp[i]=++idx;
            add(p,mp[i],0),add(mp[i],p,b[p]);
            while(x%i==0) x/=i;
        }
    if(x>1)
    {
        if(!mp[x]) mp[x]=++idx;
        add(p,mp[x],0),add(mp[x],p,b[p]);
    }
}

ll dis[N],vis[N];
priority_queue<pair<ll,int> > q;
void dij()
{
    for(int i=1;i<=idx;i++) dis[i]=INF;
    q.push({0,0});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;ll w=e[i].w;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v]) q.push({-dis[v],v});
            }
        }
    }
}

ll calc(int p)
{
    int x=a[p];ll res=INF;
    for(int i=2;i<=sqrt(x);i++)
        if(x%i==0)
        {
            res=min(res,dis[mp[i]]);
            while(x%i==0) x/=i;
        }
    if(x>1) res=min(res,dis[mp[x]]);
    if(res==INF) return -1;
    return res;
}

int main()
{
    printf(">_<");
//  scanf("%d",&n),idx=n+1;
//  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//  for(int i=1;i<=n;i++) scanf("%d",&b[i]);
//  scanf("%d",&a[0]);
//  for(int i=0;i<=n;i++) init(i);
//  dij();
//  for(int i=1;i<=n;i++) printf("%lld ",calc(i));
    return 0;
}

範例2若輸出3 2 1應該也是對的，但上傳後被判wrong answer

無法訪問 http://web2.ck.tp.edu.tw/~step5/img/problem/0057/0057.rar

Sample Output 3 should be 35?

連結要從 https://tioj.ck.tp.edu.tw/problems/showproblem?problem_id=1387 改成 https://tioj.ck.tp.edu.tw/problems/1387 才能用。

Input Format 中的子任務分數有誤