12442 - Forwarding Emails

All about problems in Volume 124. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12442 - Forwarding Emails

Post by brianfry713 » Tue Feb 28, 2012 10:57 am

Here's some random input:

Code: Select all

1
5000
1 402
2 2505
3 3724
4 4824
5 2640
6 3502
7 2449
8 3089
9 122
10 2224
11 4262
12 4878
13 4
14 4911
15 104
16 3633
17 1784
18 2913
19 574
20 4289
21 3879
22 4603
23 4659
24 1408
25 4090
26 4546
27 1352
28 1743
29 3647
30 3871
31 3470
32 2338
33 1881
34 4621
35 2647
36 2538
37 2357
38 3407
39 4766
40 1773
41 1494
42 1349
43 1843
44 4652
45 2003
46 346
47 4063
48 1006
49 2589
50 1753
51 1526
52 2293
53 4930
54 729
55 1074
56 4076
57 1884
58 1281
59 3735
60 791
61 2188
62 497
63 2634
64 1506
65 3214
66 771
67 3664
68 1564
69 2939
70 508
71 165
72 1943
73 3085
74 3556
75 4171
76 1009
77 3886
78 1996
79 4617
80 447
81 2210
82 4099
83 292
84 1881
85 1840
86 3169
87 4971
88 3166
89 3556
90 1970
91 2276
92 3594
93 4397
94 1645
95 3514
96 4311
97 1744
98 3362
99 2133
100 710
101 590
102 1765
103 3027
104 2244
105 3249
106 4306
107 1344
108 1720
109 1595
110 2083
111 3764
112 619
113 606
114 742
115 2481
116 2097
117 3200
118 1792
119 90
120 2009
121 3905
122 985
123 719
124 1587
125 4724
126 2051
127 3857
128 4783
129 50
130 449
131 1961
132 732
133 2813
134 42
135 3418
136 3884
137 1389
138 420
139 1013
140 1993
141 4521
142 1834
143 3314
144 4096
145 1964
146 2970
147 2308
148 1339
149 3544
150 3509
151 3392
152 2710
153 2580
154 1203
155 1689
156 3034
157 3474
158 3847
159 3506
160 4093
161 4156
162 1169
163 2489
164 4787
165 503
166 39
167 925
168 4097
169 4422
170 1685
171 1388
172 3591
173 796
174 4524
175 3264
176 2002
177 1864
178 887
179 1738
180 3045
181 223
182 2741
183 2082
184 1426
185 3631
186 1114
187 4693
188 4612
189 2755
190 3586
191 4324
192 1694
193 276
194 4621
195 2498
196 1804
197 4370
198 2702
199 4877
200 3778
201 2550
202 4951
203 2437
204 4052
205 426
206 314
207 3186
208 2292
209 4105
210 2855
211 2905
212 595
213 3422
214 807
215 4231
216 4548
217 2377
218 4839
219 119
220 2854
221 2447
222 846
223 2141
224 577
225 4094
226 4392
227 601
228 4553
229 664
230 279
231 1065
232 1853
233 4447
234 4031
235 2791
236 1853
237 1230
238 755
239 974
240 3460
241 4642
242 2984
243 4636
244 3189
245 4301
246 515
247 3984
248 4680
249 236
250 2650
251 1081
252 3606
253 3352
254 1334
255 4649
256 1101
257 2733
258 1291
259 1470
260 2981
261 2061
262 4611
263 4868
264 2528
265 3420
266 2666
267 4773
268 4753
269 2985
270 2857
271 1764
272 4757
273 796
274 1665
275 156
276 2572
277 1210
278 518
279 4162
280 4253
281 4592
282 2796
283 595
284 3870
285 2010
286 2578
287 4230
288 1205
289 1869
290 1032
291 2179
292 2027
293 1374
294 4585
295 1447
296 3675
297 2163
298 1756
299 935
300 4420
301 1385
302 254
303 4375
304 3174
305 3132
306 3231
307 4934
308 4875
309 3726
310 2515
311 415
312 672
313 3335
314 1494
315 4103
316 1900
317 4685
318 4430
319 1335
320 3400
321 4589
322 2303
323 4259
324 2320
325 1693
326 3099
327 2734
328 678
329 892
330 2816
331 3897
332 3905
333 1755
334 1395
335 4540
336 4657
337 4635
338 515
339 1332
340 4571
341 1556
342 1342
343 508
344 1900
345 1488
346 785
347 1841
348 3928
349 470
350 2782
351 346
352 2335
353 4643
354 2980
355 4112
356 2963
357 3594
358 2859
359 113
360 4235
361 4940
362 3874
363 1131
364 3128
365 4913
366 743
367 4581
368 1889
369 2286
370 3625
371 4569
372 4613
373 4036
374 3502
375 1988
376 3441
377 1783
378 5
379 306
380 4457
381 2038
382 3564
383 3753
384 2087
385 661
386 4947
387 161
388 584
389 1582
390 869
391 1657
392 2754
393 2380
394 712
395 3487
396 11
397 1313
398 1017
399 1338
400 3164
401 2378
402 63
403 1368
404 1250
405 3710
406 3331
407 187
408 2192
409 4217
410 2575
411 2035
412 212
413 4754
414 2343
415 4386
416 2191
417 3079
418 97
419 3165
420 3210
421 803
422 238
423 2299
424 4040
425 1483
426 94
427 992
428 123
429 2326
430 4453
431 1212
432 2488
433 194
434 1440
435 2856
436 845
437 411
438 2104
439 1447
440 4521
441 2757
442 2162
443 3941
444 760
445 1766
446 3770
447 1749
448 3661
449 3326
450 1111
451 4229
452 4581
453 3001
454 2500
455 1131
456 3597
457 1962
458 4880
459 3588
460 4404
461 4996
462 4490
463 4231
464 147
465 1751
466 2509
467 358
468 1140
469 3472
470 44
471 2849
472 771
473 876
474 102
475 3140
476 840
477 2665
478 124
479 1233
480 3954
481 1487
482 4260
483 4233
484 4249
485 1660
486 1201
487 23
488 1401
489 3909
490 2435
491 1728
492 4544
493 4165
494 1214
495 748
496 4243
497 995
498 4775
499 4052
500 2710
501 1078
502 1980
503 2545
504 455
505 545
506 1535
507 1104
508 4708
509 2937
510 4264
511 2179
512 1176
513 2939
514 278
515 2109
516 1993
517 643
518 1236
519 2324
520 2115
521 949
522 2956
523 2937
524 2547
525 3071
526 3194
527 482
528 4231
529 3026
530 1931
531 137
532 198
533 4622
534 4143
535 4121
536 4098
537 1922
538 1885
539 3436
540 3970
541 2756
542 219
543 453
544 2162
545 1305
546 4301
547 4077
548 40
549 837
550 1987
551 2710
552 857
553 2394
554 666
555 1710
556 890
557 928
558 4519
559 3208
560 3487
561 2747
562 2482
563 1908
564 92
565 4108
566 1243
567 1554
568 4535
569 1716
570 697
571 4789
572 4222
573 4374
574 66
575 3319
576 4499
577 4543
578 389
579 2698
580 4691
581 2151
582 1909
583 2417
584 4823
585 4429
586 4302
587 985
588 1494
589 4345
590 3748
591 4425
592 2799
593 2520
594 4834
595 3060
596 1912
597 2555
598 1159
599 210
600 4535
601 461
602 4976
603 3265
604 1073
605 1898
606 2536
607 1325
608 4563
609 1973
610 4142
611 3503
612 2873
613 3066
614 4637
615 1101
616 4790
617 1930
618 1936
619 3507
620 3930
621 1894
622 1623
623 589
624 4587
625 1383
626 2086
627 286
628 1799
629 2249
630 2476
631 4136
632 79
633 1914
634 1944
635 2625
636 3209
637 3048
638 763
639 4366
640 2709
641 3366
642 2874
643 2743
644 1542
645 1762
646 404
647 1776
648 4011
649 2163
650 3668
651 867
652 4764
653 3224
654 4680
655 576
656 2044
657 2836
658 3062
659 1137
660 3311
661 2197
662 279
663 3958
664 175
665 3223
666 2711
667 1627
668 3931
669 2571
670 4933
671 678
672 2885
673 3884
674 2346
675 1317
676 884
677 4524
678 1753
679 2510
680 3658
681 407
682 1474
683 2214
684 4674
685 4482
686 863
687 3418
688 3921
689 4755
690 1827
691 616
692 3828
693 3060
694 603
695 1669
696 3108
697 3230
698 3731
699 3233
700 742
701 4936
702 1132
703 3704
704 751
705 2598
706 3725
707 3333
708 808
709 90
710 2541
711 2643
712 1863
713 4824
714 3349
715 2511
716 1738
717 2150
718 1068
719 123
720 1442
721 85
722 1586
723 3096
724 955
725 4685
726 660
727 760
728 1339
729 3926
730 1172
731 4022
732 2717
733 1072
734 1000
735 2876
736 4380
737 183
738 2974
739 2089
740 3737
741 4027
742 1902
743 3017
744 3747
745 817
746 3361
747 213
748 4420
749 3044
750 1699
751 739
752 1808
753 4381
754 1811
755 1748
756 1547
757 2229
758 2706
759 2337
760 1324
761 2947
762 2053
763 1089
764 4575
765 4139
766 3851
767 858
768 1200
769 651
770 3921
771 1042
772 578
773 1303
774 2227
775 1566
776 769
777 3421
778 1512
779 3363
780 2142
781 625
782 4339
783 4027
784 203
785 2645
786 4574
787 4561
788 2215
789 589
790 3893
791 808
792 24
793 3220
794 2010
795 1620
796 1860
797 3771
798 3344
799 202
800 304
801 2231
802 3921
803 240
804 4927
805 1127
806 1766
807 2686
808 4219
809 1260
810 4335
811 3727
812 3281
813 3858
814 2301
815 132
816 3884
817 2698
818 1730
819 4749
820 4935
821 3267
822 1232
823 2523
824 89
825 1670
826 4810
827 4869
828 869
829 1388
830 4563
831 665
832 4584
833 340
834 1224
835 1686
836 1667
837 2021
838 1347
839 2768
840 1662
841 2647
842 1745
843 3202
844 1115
845 3741
846 4079
847 3947
848 3010
849 1039
850 881
851 3777
852 3500
853 3031
854 1515
855 775
856 183
857 3543
858 1476
859 681
860 4439
861 3566
862 3190
863 802
864 3476
865 1727
866 604
867 2347
868 3831
869 2514
870 2574
871 1253
872 4248
873 538
874 3550
875 230
876 1290
877 620
878 1398
879 1366
880 3611
881 4225
882 1899
883 4542
884 4769
885 1487
886 4147
887 3317
888 2187
889 1493
890 4736
891 2950
892 1705
893 153
894 4111
895 3382
896 78
897 416
898 985
899 900
900 1132
901 1854
902 323
903 3866
904 4315
905 1768
906 2828
907 4857
908 2321
909 2889
910 1871
911 2983
912 4385
913 886
914 4262
915 781
916 1924
917 3918
918 623
919 1154
920 379
921 3884
922 171
923 2149
924 1392
925 2190
926 4564
927 3386
928 4984
929 780
930 4416
931 4649
932 1903
933 3943
934 3228
935 2672
936 1074
937 4504
938 1675
939 741
940 4984
941 3034
942 3115
943 4180
944 4334
945 482
946 2935
947 924
948 4418
949 3428
950 4423
951 4966
952 4875
953 4238
954 3661
955 1732
956 3492
957 822
958 4014
959 1957
960 1899
961 126
962 131
963 1001
964 3554
965 4474
966 4493
967 3714
968 1807
969 4221
970 2566
971 2832
972 2011
973 1298
974 2664
975 1681
976 740
977 2182
978 1615
979 3391
980 4536
981 2856
982 1239
983 4383
984 3461
985 1299
986 382
987 4272
988 4678
989 1579
990 1976
991 3308
992 2454
993 2384
994 2066
995 4811
996 2910
997 3408
998 3758
999 989
1000 2479
1001 827
1002 3437
1003 1054
1004 524
1005 4670
1006 4649
1007 955
1008 3236
1009 3949
1010 2133
1011 3600
1012 2452
1013 417
1014 115
1015 4999
1016 4551
1017 1239
1018 3427
1019 2471
1020 2150
1021 1291
1022 957
1023 4100
1024 1731
1025 1584
1026 1566
1027 4967
1028 2574
1029 4964
1030 4834
1031 3902
1032 796
1033 4684
1034 512
1035 4633
1036 4901
1037 2098
1038 3565
1039 299
1040 3097
1041 3484
1042 91
1043 211
1044 241
1045 1542
1046 1423
1047 4024
1048 1960
1049 1738
1050 1224
1051 1280
1052 1620
1053 263
1054 1062
1055 2283
1056 3605
1057 721
1058 1968
1059 2341
1060 381
1061 1314
1062 3151
1063 3605
1064 2615
1065 2327
1066 1205
1067 1865
1068 1661
1069 3233
1070 345
1071 3844
1072 1943
1073 2404
1074 2567
1075 3863
1076 1927
1077 853
1078 2432
1079 578
1080 4960
1081 2817
1082 3646
1083 387
1084 1296
1085 2134
1086 958
1087 2540
1088 2119
1089 1807
1090 4525
1091 2936
1092 3853
1093 4644
1094 1841
1095 176
1096 1721
1097 561
1098 4210
1099 4908
1100 444
1101 2880
1102 3917
1103 779
1104 93
1105 2213
1106 24
1107 2257
1108 3391
1109 248
1110 3801
1111 947
1112 4524
1113 1769
1114 2076
1115 3003
1116 1438
1117 1186
1118 1271
1119 3022
1120 3447
1121 2220
1122 153
1123 1748
1124 664
1125 2536
1126 3536
1127 2115
1128 3190
1129 3988
1130 1558
1131 516
1132 4020
1133 2935
1134 2051
1135 882
1136 1955
1137 416
1138 2570
1139 2437
1140 4812
1141 808
1142 3161
1143 813
1144 1837
1145 4035
1146 1618
1147 2166
1148 937
1149 3344
1150 1684
1151 305
1152 3843
1153 3139
1154 3093
1155 4898
1156 3863
1157 2887
1158 124
1159 4389
1160 3656
1161 4788
1162 4064
1163 1366
1164 3852
1165 1085
1166 2792
1167 1594
1168 4631
1169 880
1170 1688
1171 40
1172 4731
1173 3371
1174 4235
1175 958
1176 4133
1177 3354
1178 3856
1179 4260
1180 3945
1181 1679
1182 2467
1183 2789
1184 2492
1185 472
1186 4174
1187 1196
1188 3447
1189 1537
1190 1425
1191 3678
1192 3974
1193 1760
1194 386
1195 2421
1196 2649
1197 3457
1198 2810
1199 2284
1200 4795
1201 4724
1202 1060
1203 2484
1204 1722
1205 3098
1206 4961
1207 4578
1208 446
1209 2600
1210 21
1211 2083
1212 2754
1213 3928
1214 1148
1215 1425
1216 3168
1217 4338
1218 3844
1219 1741
1220 4865
1221 1862
1222 1614
1223 4285
1224 1727
1225 1211
1226 1199
1227 597
1228 1417
1229 963
1230 3688
1231 1042
1232 4626
1233 2739
1234 260
1235 2847
1236 1509
1237 1871
1238 1163
1239 2956
1240 824
1241 3782
1242 4731
1243 1350
1244 4881
1245 2122
1246 4129
1247 1886
1248 4332
1249 3492
1250 3003
1251 598
1252 943
1253 2593
1254 1621
1255 2558
1256 2569
1257 2458
1258 4448
1259 4481
1260 1603
1261 334
1262 123
1263 2112
1264 714
1265 1371
1266 2459
1267 4159
1268 3155
1269 3869
1270 2495
1271 2675
1272 3512
1273 4009
1274 4975
1275 2204
1276 698
1277 529
1278 3826
1279 2959
1280 3456
1281 2492
1282 353
1283 486
1284 3842
1285 1689
1286 1806
1287 944
1288 1561
1289 1600
1290 3949
1291 4212
1292 3533
1293 2485
1294 3520
1295 4499
1296 2285
1297 3566
1298 1330
1299 1627
1300 3509
1301 4458
1302 2013
1303 2170
1304 3746
1305 3879
1306 310
1307 2843
1308 455
1309 1436
1310 1177
1311 2286
1312 1726
1313 4120
1314 1669
1315 3692
1316 1934
1317 1970
1318 4359
1319 1278
1320 672
1321 3412
1322 1119
1323 4906
1324 4817
1325 2457
1326 2461
1327 1276
1328 3010
1329 2393
1330 2489
1331 662
1332 3717
1333 1034
1334 3314
1335 4623
1336 2228
1337 2640
1338 4147
1339 1754
1340 4207
1341 3115
1342 5000
1343 2253
1344 4365
1345 3488
1346 4591
1347 3833
1348 2791
1349 4505
1350 4233
1351 254
1352 1627
1353 2051
1354 3835
1355 2213
1356 508
1357 1485
1358 4743
1359 620
1360 2227
1361 1993
1362 239
1363 4408
1364 2915
1365 743
1366 4527
1367 1486
1368 2952
1369 1872
1370 3725
1371 3346
1372 4632
1373 1101
1374 542
1375 3376
1376 483
1377 4100
1378 4177
1379 2332
1380 3499
1381 4368
1382 4951
1383 4549
1384 3925
1385 3319
1386 74
1387 1764
1388 2843
1389 2072
1390 1343
1391 1340
1392 2479
1393 1571
1394 338
1395 2457
1396 1769
1397 2540
1398 1749
1399 1480
1400 2006
1401 1193
1402 3036
1403 1779
1404 3442
1405 4860
1406 3815
1407 4251
1408 913
1409 1587
1410 649
1411 553
1412 3133
1413 3720
1414 2482
1415 1988
1416 653
1417 2149
1418 4227
1419 115
1420 1322
1421 3713
1422 1338
1423 3650
1424 1664
1425 3462
1426 571
1427 240
1428 1365
1429 1579
1430 1465
1431 2324
1432 3061
1433 2502
1434 1451
1435 851
1436 3727
1437 1895
1438 847
1439 4614
1440 3521
1441 3955
1442 889
1443 3645
1444 114
1445 1974
1446 275
1447 3517
1448 697
1449 2844
1450 2289
1451 2485
1452 1184
1453 4330
1454 4829
1455 115
1456 1218
1457 1758
1458 369
1459 3508
1460 3549
1461 3519
1462 1329
1463 2264
1464 262
1465 1217
1466 1280
1467 4672
1468 3824
1469 4244
1470 51
1471 203
1472 4851
1473 945
1474 4460
1475 72
1476 155
1477 3170
1478 4115
1479 174
1480 3966
1481 1417
1482 2153
1483 3189
1484 4472
1485 4355
1486 2516
1487 1826
1488 1353
1489 3343
1490 88
1491 1941
1492 1044
1493 4981
1494 4328
1495 2641
1496 2846
1497 1060
1498 3247
1499 356
1500 1190
1501 3986
1502 1486
1503 4769
1504 1159
1505 3805
1506 2686
1507 2061
1508 2848
1509 187
1510 4886
1511 4288
1512 2966
1513 4511
1514 1876
1515 461
1516 1973
1517 390
1518 3505
1519 548
1520 2453
1521 1002
1522 774
1523 2302
1524 3513
1525 3408
1526 2509
1527 2702
1528 2768
1529 660
1530 3598
1531 3164
1532 2280
1533 1386
1534 1584
1535 4473
1536 2926
1537 3601
1538 4559
1539 1974
1540 2540
1541 2448
1542 400
1543 905
1544 765
1545 2218
1546 1451
1547 3553
1548 673
1549 4780
1550 3910
1551 509
1552 770
1553 2390
1554 2786
1555 4991
1556 1397
1557 907
1558 516
1559 292
1560 982
1561 2360
1562 4634
1563 4928
1564 4991
1565 659
1566 4319
1567 1066
1568 3132
1569 2798
1570 1068
1571 3742
1572 1290
1573 523
1574 4626
1575 2901
1576 1402
1577 2859
1578 3943
1579 1756
1580 1217
1581 1971
1582 1457
1583 4540
1584 1297
1585 2541
1586 841
1587 1624
1588 1715
1589 4394
1590 2974
1591 3444
1592 2340
1593 4551
1594 3839
1595 4060
1596 1250
1597 1882
1598 1862
1599 4587
1600 1881
1601 3619
1602 3355
1603 4178
1604 349
1605 153
1606 2455
1607 4093
1608 1353
1609 2428
1610 4607
1611 645
1612 719
1613 1695
1614 4710
1615 3560
1616 1645
1617 3327
1618 3229
1619 3388
1620 625
1621 3467
1622 2293
1623 2984
1624 1202
1625 2016
1626 1765
1627 4874
1628 3988
1629 3316
1630 4890
1631 3157
1632 2559
1633 2954
1634 2329
1635 4372
1636 1741
1637 3678
1638 486
1639 415
1640 3649
1641 3476
1642 2124
1643 4269
1644 2267
1645 2828
1646 2084
1647 4174
1648 2161
1649 2510
1650 3299
1651 3111
1652 3482
1653 4853
1654 3790
1655 933
1656 2213
1657 1098
1658 4309
1659 369
1660 4729
1661 843
1662 1669
1663 4732
1664 4126
1665 3399
1666 3146
1667 1739
1668 3108
1669 2944
1670 4169
1671 3988
1672 4688
1673 4212
1674 1359
1675 1198
1676 1261
1677 4670
1678 1048
1679 761
1680 3591
1681 4966
1682 3168
1683 1987
1684 1644
1685 1264
1686 2353
1687 4387
1688 2500
1689 978
1690 2403
1691 3750
1692 1896
1693 2635
1694 1683
1695 3651
1696 1140
1697 4421
1698 4003
1699 3879
1700 4317
1701 3531
1702 4526
1703 2568
1704 2600
1705 1198
1706 4380
1707 3627
1708 2456
1709 1383
1710 3941
1711 341
1712 2444
1713 1127
1714 1792
1715 3113
1716 988
1717 2077
1718 4486
1719 4440
1720 3411
1721 4044
1722 886
1723 3174
1724 421
1725 2313
1726 1520
1727 4601
1728 531
1729 245
1730 1760
1731 2980
1732 2724
1733 267
1734 2919
1735 4820
1736 4878
1737 454
1738 2879
1739 3983
1740 3699
1741 190
1742 4774
1743 97
1744 2425
1745 769
1746 3100
1747 1119
1748 3157
1749 4409
1750 3011
1751 4940
1752 3983
1753 1655
1754 1218
1755 107
1756 3500
1757 4618
1758 1694
1759 4275
1760 2733
1761 3908
1762 4165
1763 3808
1764 1423
1765 4930
1766 1429
1767 4464
1768 1674
1769 4601
1770 2714
1771 683
1772 3453
1773 3129
1774 1876
1775 2472
1776 814
1777 769
1778 207
1779 1968
1780 1439
1781 2443
1782 2219
1783 3511
1784 1568
1785 1667
1786 3383
1787 418
1788 1554
1789 4046
1790 4651
1791 1224
1792 907
1793 2160
1794 3403
1795 3441
1796 2353
1797 200
1798 748
1799 1645
1800 381
1801 1538
1802 1778
1803 720
1804 2724
1805 4266
1806 4408
1807 1596
1808 2769
1809 2308
1810 2828
1811 1803
1812 4451
1813 704
1814 4900
1815 2463
1816 14
1817 1023
1818 3930
1819 4265
1820 105
1821 730
1822 3765
1823 3085
1824 219
1825 2869
1826 4337
1827 4006
1828 1029
1829 3610
1830 3275
1831 663
1832 2243
1833 1530
1834 2878
1835 4212
1836 96
1837 4308
1838 3255
1839 2344
1840 1573
1841 2798
1842 389
1843 4850
1844 3777
1845 479
1846 410
1847 1375
1848 3050
1849 3962
1850 4104
1851 1245
1852 2191
1853 1873
1854 716
1855 156
1856 4561
1857 816
1858 4188
1859 157
1860 1206
1861 601
1862 4726
1863 610
1864 1111
1865 4013
1866 3247
1867 3963
1868 2272
1869 825
1870 3891
1871 1817
1872 1326
1873 4134
1874 826
1875 2627
1876 1970
1877 3175
1878 450
1879 3545
1880 772
1881 1891
1882 274
1883 2926
1884 3993
1885 847
1886 4062
1887 414
1888 2160
1889 4911
1890 4708
1891 1365
1892 1964
1893 952
1894 2903
1895 4252
1896 1446
1897 641
1898 342
1899 2366
1900 1767
1901 2780
1902 1283
1903 4306
1904 731
1905 472
1906 1621
1907 1540
1908 496
1909 1449
1910 1331
1911 2341
1912 2597
1913 3770
1914 1627
1915 3075
1916 3495
1917 2827
1918 3275
1919 4050
1920 3809
1921 1634
1922 1979
1923 112
1924 2896
1925 4121
1926 3204
1927 2624
1928 3067
1929 4672
1930 2022
1931 104
1932 24
1933 1959
1934 794
1935 3802
1936 4069
1937 2391
1938 278
1939 3885
1940 4425
1941 2378
1942 713
1943 3915
1944 4697
1945 1652
1946 3694
1947 1447
1948 372
1949 2154
1950 693
1951 2641
1952 3206
1953 3593
1954 915
1955 2715
1956 3295
1957 3676
1958 3827
1959 1340
1960 128
1961 1933
1962 3098
1963 3480
1964 4317
1965 2195
1966 2106
1967 3268
1968 2854
1969 2500
1970 1872
1971 3457
1972 409
1973 699
1974 4239
1975 1980
1976 1782
1977 3668
1978 43
1979 4641
1980 1000
1981 1958
1982 1585
1983 4176
1984 1047
1985 257
1986 35
1987 2570
1988 2186
1989 3438
1990 1821
1991 3577
1992 2429
1993 3179
1994 4545
1995 323
1996 4982
1997 2261
1998 422
1999 3187
2000 2222
2001 3142
2002 4407
2003 2633
2004 403
2005 1620
2006 4741
2007 1751
2008 1067
2009 757
2010 4761
2011 4840
2012 507
2013 4729
2014 3318
2015 811
2016 963
2017 4964
2018 3535
2019 658
2020 4729
2021 3498
2022 2899
2023 4305
2024 2377
2025 4224
2026 3102
2027 2632
2028 3503
2029 1594
2030 1764
2031 656
2032 3617
2033 3758
2034 1652
2035 2293
2036 4088
2037 3544
2038 3401
2039 1088
2040 1191
2041 2788
2042 3535
2043 3930
2044 758
2045 2236
2046 3152
2047 4283
2048 4444
2049 4002
2050 1786
2051 2761
2052 4630
2053 2141
2054 4909
2055 623
2056 3444
2057 1919
2058 3444
2059 4153
2060 1121
2061 2505
2062 22
2063 978
2064 2029
2065 2636
2066 4382
2067 2366
2068 127
2069 147
2070 3996
2071 4300
2072 4808
2073 649
2074 1899
2075 4067
2076 3975
2077 463
2078 1367
2079 3548
2080 4244
2081 3423
2082 889
2083 1212
2084 4453
2085 3317
2086 3132
2087 1848
2088 4527
2089 922
2090 1238
2091 3065
2092 98
2093 3021
2094 622
2095 2354
2096 1592
2097 1378
2098 2774
2099 4537
2100 3762
2101 1928
2102 4781
2103 2361
2104 4542
2105 2645
2106 1379
2107 4656
2108 4534
2109 1959
2110 4600
2111 3150
2112 1109
2113 4882
2114 398
2115 4331
2116 3567
2117 76
2118 2616
2119 3625
2120 2754
2121 2294
2122 1268
2123 479
2124 3154
2125 3829
2126 1038
2127 4634
2128 2001
2129 3555
2130 3375
2131 2296
2132 4633
2133 4450
2134 2220
2135 2554
2136 2228
2137 3805
2138 4930
2139 1817
2140 4543
2141 4172
2142 112
2143 2414
2144 2949
2145 2429
2146 1158
2147 1113
2148 4165
2149 3466
2150 2893
2151 4569
2152 1425
2153 2863
2154 2889
2155 1855
2156 3986
2157 4290
2158 3516
2159 4802
2160 847
2161 1791
2162 1759
2163 1517
2164 4669
2165 2323
2166 3155
2167 2264
2168 4524
2169 4940
2170 163
2171 3179
2172 3155
2173 2989
2174 661
2175 4842
2176 1825
2177 4526
2178 2648
2179 331
2180 2464
2181 2762
2182 2108
2183 198
2184 4077
2185 2602
2186 2905
2187 1582
2188 3896
2189 511
2190 233
2191 1319
2192 718
2193 2733
2194 4214
2195 3483
2196 1589
2197 4642
2198 2569
2199 2621
2200 4911
2201 3861
2202 433
2203 3106
2204 3699
2205 1099
2206 1171
2207 3607
2208 2778
2209 2817
2210 786
2211 4041
2212 964
2213 2318
2214 3591
2215 4829
2216 3797
2217 3208
2218 3455
2219 4459
2220 1602
2221 314
2222 1070
2223 3937
2224 1360
2225 2731
2226 3457
2227 2081
2228 1660
2229 3763
2230 2474
2231 1762
2232 4407
2233 822
2234 2335
2235 3699
2236 193
2237 3528
2238 4281
2239 4080
2240 4470
2241 2199
2242 3585
2243 2044
2244 2203
2245 1255
2246 2640
2247 3170
2248 4384
2249 4183
2250 3739
2251 1295
2252 876
2253 3036
2254 1134
2255 2425
2256 98
2257 3172
2258 4506
2259 2057
2260 1447
2261 656
2262 1611
2263 1498
2264 427
2265 2935
2266 498
2267 4349
2268 2139
2269 4286
2270 2361
2271 3590
2272 2705
2273 1469
2274 2853
2275 2938
2276 3420
2277 1249
2278 3164
2279 2161
2280 441
2281 2771
2282 2936
2283 2533
2284 4022
2285 2524
2286 4076
2287 981
2288 2775
2289 3222
2290 3510
2291 2121
2292 1588
2293 3493
2294 2605
2295 4879
2296 2078
2297 2144
2298 188
2299 2950
2300 3484
2301 3249
2302 3317
2303 3592
2304 4250
2305 1634
2306 4487
2307 295
2308 1185
2309 316
2310 1622
2311 1069
2312 3615
2313 4737
2314 4612
2315 698
2316 3981
2317 2517
2318 274
2319 4297
2320 2089
2321 3269
2322 3963
2323 1227
2324 3795
2325 612
2326 4722
2327 883
2328 2399
2329 3305
2330 1444
2331 1248
2332 4998
2333 2202
2334 3771
2335 3110
2336 4483
2337 4189
2338 783
2339 2833
2340 678
2341 7
2342 2753
2343 2044
2344 4498
2345 2931
2346 3506
2347 476
2348 3578
2349 2809
2350 3145
2351 315
2352 1062
2353 3255
2354 2420
2355 250
2356 3375
2357 1152
2358 1078
2359 226
2360 2992
2361 3523
2362 2640
2363 2224
2364 2727
2365 818
2366 4087
2367 3407
2368 993
2369 2089
2370 2189
2371 4077
2372 2973
2373 3552
2374 3640
2375 1917
2376 4350
2377 629
2378 2130
2379 3230
2380 4761
2381 1006
2382 4690
2383 1148
2384 4352
2385 812
2386 4819
2387 1938
2388 1006
2389 1518
2390 1107
2391 1475
2392 4253
2393 1907
2394 4619
2395 1438
2396 324
2397 4170
2398 2772
2399 1917
2400 933
2401 4030
2402 1603
2403 2008
2404 3813
2405 2913
2406 83
2407 4994
2408 639
2409 573
2410 4601
2411 2095
2412 4136
2413 1619
2414 2289
2415 3840
2416 3055
2417 3344
2418 3475
2419 1120
2420 1146
2421 1635
2422 4989
2423 2862
2424 2884
2425 4236
2426 3227
2427 2421
2428 2028
2429 702
2430 2282
2431 1138
2432 4996
2433 2437
2434 1773
2435 3844
2436 3264
2437 3807
2438 3214
2439 3960
2440 473
2441 480
2442 4011
2443 3728
2444 1616
2445 4713
2446 2838
2447 2138
2448 3307
2449 1150
2450 3471
2451 4115
2452 3762
2453 2489
2454 3798
2455 4080
2456 4172
2457 1979
2458 859
2459 4946
2460 755
2461 2909
2462 1632
2463 4987
2464 1577
2465 1221
2466 478
2467 923
2468 3554
2469 1927
2470 1412
2471 3503
2472 779
2473 3448
2474 4724
2475 2593
2476 91
2477 4484
2478 3762
2479 439
2480 1830
2481 4314
2482 3650
2483 3517
2484 584
2485 2052
2486 2903
2487 2836
2488 646
2489 3252
2490 4246
2491 2240
2492 4152
2493 1168
2494 2167
2495 2263
2496 2340
2497 454
2498 4199
2499 658
2500 4827
2501 3395
2502 2419
2503 3300
2504 2225
2505 2929
2506 197
2507 1252
2508 3233
2509 62
2510 1069
2511 613
2512 2679
2513 3041
2514 4347
2515 2428
2516 970
2517 4284
2518 4894
2519 1485
2520 2494
2521 43
2522 3819
2523 695
2524 2650
2525 3207
2526 22
2527 2978
2528 4133
2529 137
2530 3020
2531 3763
2532 85
2533 371
2534 3107
2535 675
2536 1397
2537 1722
2538 3548
2539 1191
2540 2166
2541 1760
2542 2827
2543 4545
2544 4227
2545 3175
2546 701
2547 16
2548 3612
2549 4814
2550 31
2551 4798
2552 3038
2553 4381
2554 1676
2555 4265
2556 4643
2557 381
2558 927
2559 4564
2560 3217
2561 3977
2562 3701
2563 4076
2564 2760
2565 1112
2566 2161
2567 4769
2568 59
2569 4103
2570 3212
2571 3036
2572 2338
2573 1895
2574 548
2575 3843
2576 102
2577 2924
2578 2800
2579 3377
2580 1753
2581 2804
2582 287
2583 2395
2584 1497
2585 2819
2586 2010
2587 748
2588 463
2589 641
2590 3789
2591 1370
2592 431
2593 1489
2594 1583
2595 118
2596 4047
2597 4453
2598 2173
2599 2016
2600 1816
2601 2907
2602 3907
2603 3371
2604 2515
2605 4746
2606 3296
2607 2967
2608 4985
2609 4243
2610 4191
2611 51
2612 3457
2613 3998
2614 829
2615 2738
2616 4321
2617 3215
2618 1635
2619 145
2620 585
2621 1018
2622 4893
2623 110
2624 1198
2625 4704
2626 2494
2627 236
2628 4886
2629 89
2630 4826
2631 2796
2632 3856
2633 1890
2634 3330
2635 369
2636 3769
2637 4182
2638 1318
2639 2058
2640 1942
2641 4238
2642 182
2643 53
2644 3915
2645 867
2646 4165
2647 2219
2648 1110
2649 103
2650 4748
2651 952
2652 2217
2653 2464
2654 2696
2655 593
2656 286
2657 4619
2658 3496
2659 68
2660 2138
2661 1506
2662 1909
2663 2868
2664 3547
2665 1747
2666 110
2667 2900
2668 1820
2669 3400
2670 3441
2671 4375
2672 1888
2673 1065
2674 3143
2675 330
2676 2353
2677 298
2678 4872
2679 1392
2680 2620
2681 302
2682 1769
2683 1645
2684 3907
2685 1380
2686 1541
2687 1322
2688 1832
2689 3503
2690 3390
2691 1412
2692 3183
2693 837
2694 2363
2695 1276
2696 748
2697 4826
2698 1653
2699 4566
2700 2699
2701 4823
2702 2738
2703 4189
2704 2143
2705 1720
2706 4385
2707 4498
2708 217
2709 4967
2710 1721
2711 4702
2712 2658
2713 3608
2714 1841
2715 3314
2716 3893
2717 1342
2718 3218
2719 2027
2720 1321
2721 2297
2722 3809
2723 4210
2724 494
2725 1258
2726 2429
2727 1726
2728 3975
2729 363
2730 547
2731 628
2732 2075
2733 422
2734 2742
2735 3720
2736 2874
2737 2917
2738 4004
2739 1235
2740 3951
2741 4385
2742 3796
2743 273
2744 1396
2745 3548
2746 1583
2747 4851
2748 2499
2749 188
2750 1839
2751 4657
2752 3274
2753 1243
2754 3447
2755 1598
2756 922
2757 2879
2758 2136
2759 3394
2760 3919
2761 3786
2762 4491
2763 4351
2764 1080
2765 4500
2766 2814
2767 4771
2768 4592
2769 3522
2770 3060
2771 4415
2772 1869
2773 4578
2774 2099
2775 2151
2776 2959
2777 1043
2778 2650
2779 3351
2780 3440
2781 1483
2782 1953
2783 1223
2784 3012
2785 1251
2786 4857
2787 285
2788 1145
2789 3405
2790 2754
2791 1395
2792 978
2793 3197
2794 4521
2795 4240
2796 3713
2797 435
2798 2284
2799 2870
2800 2904
2801 231
2802 2144
2803 2442
2804 4036
2805 4001
2806 572
2807 4717
2808 1056
2809 2821
2810 4438
2811 1064
2812 3802
2813 3838
2814 329
2815 3071
2816 2842
2817 3993
2818 42
2819 4792
2820 447
2821 2296
2822 538
2823 417
2824 4404
2825 4282
2826 4173
2827 12
2828 2180
2829 1579
2830 4422
2831 1034
2832 320
2833 4047
2834 911
2835 2941
2836 1794
2837 3412
2838 4616
2839 2054
2840 2504
2841 4483
2842 1211
2843 3169
2844 2225
2845 1354
2846 178
2847 1988
2848 536
2849 3548
2850 973
2851 2813
2852 3790
2853 1556
2854 2338
2855 2678
2856 2031
2857 4907
2858 3859
2859 1237
2860 1849
2861 1885
2862 3204
2863 2982
2864 2195
2865 786
2866 46
2867 4368
2868 1346
2869 2316
2870 919
2871 2298
2872 2321
2873 2182
2874 763
2875 2061
2876 3179
2877 2517
2878 2943
2879 1568
2880 2744
2881 3920
2882 4787
2883 561
2884 3063
2885 3845
2886 753
2887 4330
2888 2852
2889 4462
2890 4950
2891 343
2892 4132
2893 4361
2894 4179
2895 2910
2896 3796
2897 80
2898 1105
2899 1736
2900 2313
2901 3298
2902 153
2903 660
2904 3016
2905 2174
2906 2129
2907 811
2908 709
2909 4836
2910 3633
2911 4351
2912 2607
2913 166
2914 4487
2915 638
2916 3154
2917 2784
2918 4125
2919 1753
2920 3154
2921 3313
2922 443
2923 831
2924 2
2925 2941
2926 4255
2927 4760
2928 4034
2929 1871
2930 3108
2931 64
2932 4131
2933 2448
2934 3810
2935 2421
2936 3702
2937 4869
2938 1275
2939 3005
2940 4693
2941 3928
2942 2372
2943 3783
2944 2820
2945 1479
2946 1008
2947 965
2948 2144
2949 4984
2950 4664
2951 1277
2952 3010
2953 657
2954 4385
2955 726
2956 2237
2957 1332
2958 4013
2959 363
2960 3941
2961 1897
2962 1252
2963 581
2964 516
2965 2516
2966 1432
2967 2950
2968 3377
2969 4569
2970 4329
2971 3374
2972 2919
2973 949
2974 86
2975 1094
2976 3096
2977 3348
2978 4289
2979 2832
2980 965
2981 13
2982 3492
2983 2807
2984 53
2985 2706
2986 2374
2987 4025
2988 2589
2989 4705
2990 3940
2991 4015
2992 4719
2993 4028
2994 1751
2995 1553
2996 184
2997 1105
2998 2769
2999 394
3000 2250
3001 1064
3002 4095
3003 936
3004 4594
3005 4274
3006 3133
3007 1863
3008 4173
3009 2117
3010 1151
3011 1409
3012 11
3013 2071
3014 3004
3015 3688
3016 2804
3017 4344
3018 1613
3019 4441
3020 4572
3021 1258
3022 489
3023 3611
3024 4919
3025 1110
3026 3468
3027 2640
3028 547
3029 2785
3030 3387
3031 4026
3032 3292
3033 4572
3034 629
3035 4569
3036 1254
3037 3057
3038 2814
3039 1153
3040 3183
3041 2612
3042 3775
3043 4625
3044 231
3045 3227
3046 2877
3047 3301
3048 469
3049 2739
3050 60
3051 285
3052 4804
3053 446
3054 733
3055 3664
3056 4112
3057 4266
3058 1576
3059 657
3060 3010
3061 1232
3062 437
3063 11
3064 2770
3065 4509
3066 3199
3067 1188
3068 3778
3069 947
3070 3873
3071 3806
3072 4953
3073 3908
3074 2817
3075 2334
3076 1429
3077 2039
3078 4804
3079 4113
3080 598
3081 1184
3082 401
3083 3130
3084 2142
3085 1748
3086 2760
3087 2409
3088 1001
3089 1131
3090 439
3091 1139
3092 4848
3093 2132
3094 2892
3095 403
3096 1637
3097 2764
3098 3030
3099 4107
3100 220
3101 2677
3102 4592
3103 789
3104 3011
3105 576
3106 950
3107 1256
3108 4758
3109 3897
3110 1307
3111 2517
3112 1410
3113 2930
3114 3700
3115 2233
3116 3199
3117 2258
3118 3878
3119 3244
3120 30
3121 1003
3122 4442
3123 2247
3124 2139
3125 4457
3126 1636
3127 2306
3128 1977
3129 1932
3130 1813
3131 1696
3132 1533
3133 1282
3134 1891
3135 1221
3136 1472
3137 2155
3138 314
3139 2022
3140 3469
3141 4655
3142 2158
3143 274
3144 4655
3145 4359
3146 2607
3147 3639
3148 1230
3149 2441
3150 4619
3151 1713
3152 550
3153 3358
3154 3771
3155 3270
3156 2922
3157 1619
3158 1495
3159 413
3160 2234
3161 2467
3162 1857
3163 4162
3164 4567
3165 3405
3166 3819
3167 4071
3168 3253
3169 393
3170 4382
3171 4488
3172 3105
3173 2257
3174 2014
3175 40
3176 3689
3177 2734
3178 4425
3179 4206
3180 4509
3181 2939
3182 3659
3183 2886
3184 768
3185 3472
3186 3553
3187 2895
3188 4705
3189 4454
3190 3891
3191 1390
3192 4522
3193 3894
3194 4424
3195 2385
3196 651
3197 3295
3198 3211
3199 4888
3200 4422
3201 2806
3202 2053
3203 2424
3204 1219
3205 1380
3206 935
3207 3680
3208 5000
3209 1652
3210 3210
3211 3096
3212 4601
3213 1859
3214 2578
3215 454
3216 4367
3217 2398
3218 1137
3219 561
3220 2092
3221 4522
3222 130
3223 727
3224 513
3225 4337
3226 2546
3227 3944
3228 2450
3229 897
3230 1848
3231 202
3232 2732
3233 2554
3234 3065
3235 1877
3236 3950
3237 3859
3238 3974
3239 4726
3240 3906
3241 3420
3242 1776
3243 2313
3244 3606
3245 1489
3246 4604
3247 2549
3248 1678
3249 427
3250 4906
3251 3699
3252 4815
3253 2949
3254 4965
3255 4631
3256 1976
3257 1172
3258 3693
3259 968
3260 1869
3261 1993
3262 4152
3263 277
3264 3396
3265 167
3266 4881
3267 2876
3268 676
3269 272
3270 3456
3271 1579
3272 2223
3273 4989
3274 2758
3275 1904
3276 3794
3277 170
3278 4782
3279 4353
3280 1958
3281 321
3282 1612
3283 2331
3284 4212
3285 3908
3286 4075
3287 4285
3288 4711
3289 1952
3290 4154
3291 2649
3292 3673
3293 4535
3294 4228
3295 160
3296 1803
3297 4485
3298 897
3299 953
3300 4643
3301 1107
3302 4863
3303 1071
3304 4009
3305 645
3306 4901
3307 4270
3308 2986
3309 4236
3310 1722
3311 3735
3312 4293
3313 3856
3314 3181
3315 133
3316 659
3317 1787
3318 4456
3319 4713
3320 1151
3321 959
3322 2452
3323 4250
3324 3537
3325 2012
3326 21
3327 279
3328 3110
3329 74
3330 3774
3331 782
3332 2262
3333 4546
3334 2696
3335 4604
3336 1311
3337 2563
3338 4107
3339 949
3340 3220
3341 4180
3342 2843
3343 1705
3344 1106
3345 3807
3346 1112
3347 1344
3348 1875
3349 1101
3350 1435
3351 4602
3352 374
3353 4322
3354 1241
3355 4502
3356 950
3357 4304
3358 3562
3359 4937
3360 2790
3361 4616
3362 3180
3363 158
3364 4367
3365 2696
3366 3315
3367 1623
3368 742
3369 4761
3370 176
3371 3288
3372 3177
3373 2541
3374 3366
3375 34
3376 3790
3377 4828
3378 4139
3379 637
3380 2381
3381 2374
3382 1347
3383 1914
3384 2976
3385 3755
3386 584
3387 694
3388 2726
3389 2327
3390 3221
3391 3241
3392 1426
3393 1875
3394 1349
3395 4667
3396 1687
3397 3172
3398 782
3399 4201
3400 2212
3401 1710
3402 2392
3403 3920
3404 731
3405 3288
3406 15
3407 3591
3408 2542
3409 800
3410 2595
3411 3421
3412 4960
3413 3583
3414 2341
3415 2302
3416 2071
3417 3658
3418 346
3419 1167
3420 2471
3421 930
3422 1844
3423 1342
3424 4224
3425 1100
3426 4608
3427 4113
3428 2470
3429 1802
3430 1755
3431 2107
3432 2124
3433 3010
3434 2483
3435 4809
3436 3920
3437 3557
3438 1783
3439 3292
3440 1101
3441 4074
3442 3247
3443 332
3444 4445
3445 3628
3446 3442
3447 75
3448 3192
3449 627
3450 3428
3451 1611
3452 3669
3453 4632
3454 1264
3455 3162
3456 4341
3457 2103
3458 1730
3459 974
3460 3204
3461 4903
3462 3907
3463 41
3464 2409
3465 905
3466 3489
3467 915
3468 4698
3469 1806
3470 512
3471 2967
3472 4832
3473 1197
3474 3086
3475 3628
3476 1458
3477 218
3478 662
3479 4908
3480 1739
3481 3268
3482 4881
3483 788
3484 3572
3485 1865
3486 2118
3487 3740
3488 685
3489 2548
3490 3452
3491 1547
3492 165
3493 106
3494 2676
3495 4246
3496 4906
3497 2281
3498 1625
3499 98
3500 240
3501 4992
3502 2487
3503 4332
3504 1298
3505 2552
3506 4894
3507 1438
3508 2939
3509 966
3510 581
3511 3408
3512 4302
3513 4019
3514 462
3515 4033
3516 955
3517 4888
3518 3611
3519 4195
3520 189
3521 2003
3522 1578
3523 816
3524 4035
3525 4384
3526 3064
3527 3119
3528 739
3529 1342
3530 3544
3531 2605
3532 924
3533 3904
3534 3272
3535 2502
3536 1953
3537 4954
3538 3658
3539 1470
3540 3850
3541 3402
3542 146
3543 3584
3544 3143
3545 1461
3546 3710
3547 545
3548 3649
3549 3196
3550 4239
3551 1073
3552 2862
3553 4032
3554 4941
3555 1959
3556 4243
3557 4872
3558 3170
3559 2259
3560 2980
3561 633
3562 4238
3563 1578
3564 4463
3565 752
3566 4626
3567 2471
3568 2922
3569 2822
3570 3390
3571 2993
3572 69
3573 1235
3574 1388
3575 1231
3576 4654
3577 977
3578 205
3579 2060
3580 1767
3581 4645
3582 4985
3583 3193
3584 1606
3585 4087
3586 533
3587 370
3588 944
3589 918
3590 1636
3591 1504
3592 185
3593 800
3594 2820
3595 1525
3596 4682
3597 925
3598 4264
3599 4918
3600 4080
3601 1455
3602 922
3603 4347
3604 3317
3605 1863
3606 2332
3607 4084
3608 1046
3609 4721
3610 888
3611 4972
3612 1512
3613 57
3614 3607
3615 3343
3616 2729
3617 1452
3618 4052
3619 3009
3620 3836
3621 903
3622 4886
3623 473
3624 679
3625 3278
3626 4025
3627 1215
3628 1138
3629 721
3630 2375
3631 1372
3632 2323
3633 1881
3634 936
3635 3480
3636 2786
3637 2605
3638 4987
3639 3346
3640 3545
3641 3176
3642 4426
3643 3424
3644 3623
3645 1515
3646 3403
3647 3139
3648 206
3649 4721
3650 4281
3651 3939
3652 1929
3653 3282
3654 3418
3655 2955
3656 1193
3657 2411
3658 619
3659 2889
3660 1359
3661 2754
3662 119
3663 4754
3664 398
3665 2585
3666 4139
3667 747
3668 1883
3669 1823
3670 570
3671 448
3672 1182
3673 2927
3674 481
3675 1775
3676 3956
3677 3465
3678 3488
3679 2851
3680 1413
3681 3692
3682 3856
3683 3901
3684 3085
3685 375
3686 3023
3687 3696
3688 1775
3689 1092
3690 4851
3691 2094
3692 3232
3693 2087
3694 1962
3695 3474
3696 4715
3697 4962
3698 4566
3699 308
3700 4401
3701 3124
3702 1125
3703 28
3704 4160
3705 4937
3706 3143
3707 880
3708 425
3709 921
3710 2335
3711 99
3712 2791
3713 2954
3714 211
3715 2840
3716 761
3717 214
3718 2414
3719 3396
3720 764
3721 1170
3722 1952
3723 3373
3724 709
3725 384
3726 2449
3727 1129
3728 4065
3729 1596
3730 685
3731 3098
3732 9
3733 1715
3734 3595
3735 4131
3736 3422
3737 4054
3738 2589
3739 4572
3740 3061
3741 3458
3742 1397
3743 2067
3744 1031
3745 4715
3746 2040
3747 2538
3748 4385
3749 3615
3750 1794
3751 2245
3752 2282
3753 880
3754 2100
3755 179
3756 4103
3757 3985
3758 191
3759 2983
3760 990
3761 1866
3762 3450
3763 3680
3764 2888
3765 3029
3766 1618
3767 1773
3768 4613
3769 3723
3770 1329
3771 3268
3772 1939
3773 813
3774 2259
3775 598
3776 535
3777 2842
3778 3039
3779 2263
3780 53
3781 4145
3782 3622
3783 1672
3784 388
3785 2429
3786 2461
3787 4741
3788 365
3789 29
3790 2791
3791 4077
3792 4361
3793 2629
3794 2223
3795 4750
3796 2446
3797 3180
3798 2153
3799 1813
3800 54
3801 597
3802 1776
3803 4557
3804 2807
3805 4832
3806 2603
3807 3443
3808 888
3809 2495
3810 669
3811 1346
3812 2357
3813 1912
3814 4834
3815 4631
3816 3817
3817 3416
3818 1570
3819 1808
3820 3765
3821 164
3822 2687
3823 3409
3824 2833
3825 4793
3826 76
3827 3379
3828 4612
3829 4097
3830 4920
3831 4397
3832 4816
3833 4588
3834 3551
3835 1694
3836 4347
3837 1871
3838 1825
3839 1794
3840 81
3841 11
3842 4425
3843 4779
3844 1121
3845 1200
3846 3872
3847 943
3848 2274
3849 3177
3850 2926
3851 3169
3852 1458
3853 1610
3854 2689
3855 4681
3856 2220
3857 2722
3858 1493
3859 1121
3860 2729
3861 2988
3862 4173
3863 256
3864 2604
3865 980
3866 1627
3867 3472
3868 225
3869 1968
3870 4195
3871 2613
3872 1065
3873 2702
3874 3186
3875 867
3876 4165
3877 2337
3878 2990
3879 3031
3880 3218
3881 3890
3882 3857
3883 3230
3884 2598
3885 4288
3886 1928
3887 617
3888 1114
3889 746
3890 2746
3891 4115
3892 3660
3893 4254
3894 3779
3895 4770
3896 2578
3897 1463
3898 3248
3899 3075
3900 2429
3901 837
3902 4312
3903 4322
3904 1385
3905 2575
3906 1155
3907 3189
3908 1721
3909 2589
3910 4911
3911 1324
3912 2450
3913 3196
3914 2450
3915 2378
3916 2379
3917 3577
3918 4917
3919 3507
3920 4993
3921 1169
3922 1650
3923 1244
3924 1909
3925 4971
3926 4950
3927 3907
3928 783
3929 2493
3930 1869
3931 2748
3932 2373
3933 3258
3934 4388
3935 1131
3936 1116
3937 2567
3938 707
3939 83
3940 660
3941 4301
3942 2157
3943 4434
3944 2039
3945 126
3946 3113
3947 3013
3948 479
3949 2443
3950 2630
3951 2364
3952 92
3953 1911
3954 1573
3955 2710
3956 1037
3957 4774
3958 3308
3959 882
3960 3132
3961 100
3962 3037
3963 977
3964 4927
3965 2610
3966 542
3967 4355
3968 1386
3969 1050
3970 1532
3971 3976
3972 1159
3973 3925
3974 748
3975 2765
3976 1955
3977 3790
3978 4465
3979 1015
3980 1259
3981 1340
3982 1301
3983 2407
3984 3533
3985 753
3986 364
3987 1522
3988 1553
3989 4448
3990 1743
3991 1285
3992 2917
3993 649
3994 2074
3995 2405
3996 2725
3997 4293
3998 4713
3999 3950
4000 1331
4001 961
4002 3255
4003 3117
4004 1534
4005 3766
4006 2923
4007 2294
4008 1349
4009 2506
4010 427
4011 4572
4012 838
4013 4759
4014 4796
4015 416
4016 1612
4017 3861
4018 287
4019 575
4020 4605
4021 178
4022 386
4023 1526
4024 2653
4025 3549
4026 4227
4027 1525
4028 118
4029 2511
4030 3919
4031 2204
4032 2504
4033 4678
4034 1626
4035 4970
4036 2352
4037 1930
4038 1342
4039 4418
4040 3767
4041 4953
4042 2374
4043 2800
4044 3186
4045 3460
4046 4251
4047 1343
4048 969
4049 1530
4050 4675
4051 2080
4052 635
4053 555
4054 2925
4055 1282
4056 627
4057 3404
4058 1486
4059 4296
4060 5000
4061 751
4062 2998
4063 4019
4064 4837
4065 1460
4066 2574
4067 725
4068 1117
4069 4711
4070 1833
4071 2406
4072 3317
4073 2737
4074 2178
4075 1536
4076 3680
4077 1252
4078 3625
4079 1776
4080 4797
4081 1999
4082 742
4083 4777
4084 2800
4085 861
4086 2531
4087 1196
4088 2686
4089 3102
4090 2455
4091 4170
4092 2893
4093 583
4094 243
4095 3608
4096 2909
4097 3145
4098 1671
4099 401
4100 1422
4101 1541
4102 4633
4103 1503
4104 4919
4105 3660
4106 3019
4107 3655
4108 976
4109 2591
4110 2013
4111 2092
4112 2728
4113 2373
4114 2856
4115 797
4116 3086
4117 1163
4118 373
4119 1352
4120 1185
4121 3359
4122 1942
4123 46
4124 4816
4125 284
4126 3707
4127 3810
4128 4894
4129 1857
4130 4057
4131 3525
4132 997
4133 1611
4134 2142
4135 4182
4136 2964
4137 4028
4138 3778
4139 373
4140 3719
4141 557
4142 3490
4143 767
4144 2844
4145 1779
4146 4608
4147 1142
4148 2188
4149 4513
4150 4169
4151 3571
4152 1157
4153 3666
4154 216
4155 113
4156 3217
4157 2987
4158 4075
4159 3164
4160 780
4161 2167
4162 3604
4163 3708
4164 356
4165 441
4166 3191
4167 4561
4168 2379
4169 3370
4170 3854
4171 1921
4172 4997
4173 2472
4174 4248
4175 1942
4176 3545
4177 4860
4178 4423
4179 4318
4180 2568
4181 4021
4182 1230
4183 4655
4184 2051
4185 1680
4186 84
4187 3145
4188 1755
4189 1882
4190 4621
4191 4365
4192 2258
4193 3649
4194 4717
4195 4964
4196 529
4197 225
4198 2912
4199 1453
4200 2913
4201 4285
4202 1162
4203 285
4204 2673
4205 1123
4206 180
4207 1236
4208 4723
4209 4190
4210 3196
4211 4981
4212 4340
4213 4875
4214 901
4215 1500
4216 11
4217 3822
4218 1565
4219 4772
4220 2247
4221 2890
4222 3185
4223 2023
4224 2222
4225 4103
4226 2993
4227 846
4228 3980
4229 528
4230 4240
4231 4561
4232 4211
4233 2941
4234 375
4235 3160
4236 1378
4237 684
4238 502
4239 4114
4240 3176
4241 936
4242 3052
4243 2471
4244 3093
4245 3791
4246 4859
4247 4370
4248 4687
4249 3859
4250 4984
4251 3505
4252 4539
4253 3534
4254 904
4255 3458
4256 3486
4257 1192
4258 3622
4259 2748
4260 3041
4261 851
4262 1057
4263 4645
4264 1162
4265 3550
4266 4216
4267 2220
4268 3450
4269 556
4270 4007
4271 1138
4272 4615
4273 3799
4274 1796
4275 1830
4276 997
4277 374
4278 349
4279 3620
4280 4606
4281 54
4282 1803
4283 3176
4284 4225
4285 4541
4286 1810
4287 2141
4288 3023
4289 2200
4290 2967
4291 305
4292 4625
4293 3463
4294 1498
4295 4130
4296 1313
4297 1937
4298 3070
4299 773
4300 1814
4301 2657
4302 54
4303 456
4304 732
4305 4477
4306 310
4307 3905
4308 1784
4309 2831
4310 3813
4311 1952
4312 2272
4313 1869
4314 925
4315 972
4316 1894
4317 3402
4318 1869
4319 2504
4320 22
4321 4168
4322 3780
4323 4000
4324 50
4325 2442
4326 4282
4327 3188
4328 485
4329 1589
4330 2369
4331 1336
4332 4084
4333 4305
4334 3121
4335 2013
4336 1064
4337 1662
4338 4461
4339 1327
4340 4228
4341 2537
4342 2884
4343 1580
4344 3279
4345 4873
4346 3893
4347 3749
4348 3148
4349 1477
4350 181
4351 3098
4352 3911
4353 433
4354 4371
4355 3111
4356 996
4357 2128
4358 4609
4359 411
4360 2339
4361 945
4362 589
4363 2879
4364 2416
4365 3382
4366 4519
4367 3401
4368 303
4369 2639
4370 4805
4371 742
4372 2695
4373 2407
4374 1707
4375 658
4376 2750
4377 558
4378 1177
4379 4489
4380 3972
4381 3434
4382 2852
4383 299
4384 309
4385 4549
4386 127
4387 607
4388 4756
4389 3755
4390 2473
4391 2841
4392 1824
4393 2412
4394 2182
4395 729
4396 2003
4397 1282
4398 4912
4399 3469
4400 4636
4401 514
4402 4266
4403 1364
4404 4723
4405 776
4406 3405
4407 2876
4408 3433
4409 2910
4410 504
4411 1495
4412 290
4413 3477
4414 4823
4415 2870
4416 730
4417 266
4418 1203
4419 896
4420 1384
4421 1475
4422 1773
4423 3469
4424 769
4425 3468
4426 274
4427 3558
4428 759
4429 33
4430 171
4431 595
4432 4960
4433 3473
4434 2387
4435 4902
4436 1197
4437 4740
4438 1106
4439 1940
4440 1546
4441 1043
4442 4659
4443 954
4444 2988
4445 4969
4446 2225
4447 4031
4448 4767
4449 4964
4450 1786
4451 3243
4452 3784
4453 879
4454 2907
4455 4629
4456 3760
4457 962
4458 3125
4459 470
4460 1586
4461 3131
4462 1301
4463 3539
4464 1859
4465 1452
4466 4459
4467 367
4468 3470
4469 1156
4470 4471
4471 4107
4472 686
4473 3756
4474 885
4475 3089
4476 4679
4477 3750
4478 4558
4479 4893
4480 4848
4481 1413
4482 1797
4483 1420
4484 301
4485 2748
4486 413
4487 747
4488 1442
4489 4229
4490 3426
4491 2550
4492 3700
4493 1547
4494 716
4495 4292
4496 442
4497 833
4498 1045
4499 2951
4500 4220
4501 579
4502 1492
4503 3986
4504 2572
4505 2094
4506 1755
4507 3859
4508 4150
4509 1870
4510 3406
4511 1062
4512 1279
4513 4618
4514 425
4515 936
4516 1561
4517 4468
4518 3752
4519 359
4520 307
4521 1980
4522 4357
4523 434
4524 4404
4525 19
4526 3529
4527 2886
4528 2897
4529 2902
4530 514
4531 652
4532 473
4533 322
4534 4136
4535 295
4536 2666
4537 4690
4538 1030
4539 1127
4540 4110
4541 38
4542 3282
4543 2125
4544 3202
4545 1851
4546 764
4547 415
4548 4886
4549 2964
4550 4718
4551 3924
4552 1606
4553 2893
4554 4966
4555 2468
4556 3099
4557 4301
4558 3417
4559 4496
4560 747
4561 2909
4562 992
4563 4719
4564 865
4565 4026
4566 2849
4567 168
4568 76
4569 78
4570 764
4571 1838
4572 1087
4573 2502
4574 2973
4575 2985
4576 624
4577 4021
4578 170
4579 1029
4580 1392
4581 2390
4582 4601
4583 1926
4584 3701
4585 489
4586 1103
4587 4776
4588 2251
4589 4808
4590 1289
4591 1675
4592 3565
4593 267
4594 1863
4595 4755
4596 2111
4597 444
4598 1082
4599 1852
4600 1044
4601 3546
4602 2557
4603 3504
4604 3504
4605 1511
4606 2594
4607 4516
4608 192
4609 2414
4610 369
4611 4421
4612 1658
4613 3071
4614 3547
4615 2592
4616 2307
4617 3025
4618 822
4619 3833
4620 1220
4621 2105
4622 3070
4623 3195
4624 3164
4625 548
4626 1578
4627 3593
4628 1477
4629 2287
4630 1023
4631 24
4632 2266
4633 628
4634 3665
4635 3812
4636 2798
4637 1761
4638 2963
4639 1279
4640 2740
4641 4540
4642 1854
4643 43
4644 1837
4645 4484
4646 514
4647 4397
4648 3899
4649 785
4650 358
4651 1516
4652 3579
4653 1163
4654 49
4655 2919
4656 4949
4657 2309
4658 1336
4659 1067
4660 4867
4661 4746
4662 3102
4663 2950
4664 288
4665 2966
4666 3383
4667 2374
4668 3624
4669 1504
4670 1155
4671 4911
4672 2701
4673 939
4674 434
4675 4707
4676 3338
4677 1417
4678 1595
4679 1525
4680 1264
4681 2874
4682 3087
4683 1712
4684 4813
4685 4655
4686 1086
4687 3797
4688 4554
4689 1444
4690 4966
4691 3617
4692 3117
4693 1810
4694 2409
4695 4330
4696 477
4697 3563
4698 137
4699 2634
4700 2009
4701 4877
4702 2411
4703 4176
4704 1776
4705 1584
4706 4341
4707 2185
4708 3952
4709 2572
4710 2936
4711 3320
4712 2402
4713 4732
4714 2886
4715 2654
4716 2364
4717 2468
4718 3178
4719 2581
4720 1638
4721 4984
4722 1051
4723 418
4724 2550
4725 3504
4726 586
4727 983
4728 2245
4729 3057
4730 2619
4731 1214
4732 1808
4733 3501
4734 321
4735 2220
4736 4918
4737 484
4738 3141
4739 1370
4740 1856
4741 1063
4742 2717
4743 4848
4744 1827
4745 232
4746 2502
4747 489
4748 1284
4749 1037
4750 1585
4751 1793
4752 1416
4753 3504
4754 1583
4755 1960
4756 3817
4757 2667
4758 74
4759 558
4760 3189
4761 3790
4762 3635
4763 3791
4764 454
4765 291
4766 1337
4767 943
4768 803
4769 2712
4770 2355
4771 1811
4772 539
4773 2557
4774 3274
4775 1520
4776 3181
4777 4635
4778 156
4779 3021
4780 2585
4781 2102
4782 955
4783 4582
4784 220
4785 792
4786 1567
4787 3294
4788 3267
4789 2406
4790 4835
4791 1135
4792 4384
4793 180
4794 66
4795 3229
4796 4474
4797 3119
4798 235
4799 259
4800 1967
4801 3223
4802 1819
4803 2475
4804 2803
4805 3534
4806 2076
4807 395
4808 4163
4809 1997
4810 1697
4811 139
4812 2990
4813 4980
4814 4877
4815 3827
4816 2833
4817 2382
4818 4184
4819 4743
4820 4917
4821 1292
4822 4543
4823 649
4824 2585
4825 1496
4826 4128
4827 3073
4828 1258
4829 4659
4830 1674
4831 1043
4832 2538
4833 1781
4834 3389
4835 669
4836 3781
4837 4727
4838 2095
4839 1904
4840 2546
4841 3367
4842 4280
4843 984
4844 3555
4845 1409
4846 785
4847 4781
4848 1078
4849 844
4850 1174
4851 3393
4852 2445
4853 2064
4854 1915
4855 4141
4856 2941
4857 653
4858 4909
4859 4224
4860 2552
4861 1204
4862 4855
4863 1518
4864 2356
4865 58
4866 3748
4867 4077
4868 155
4869 927
4870 4946
4871 3634
4872 843
4873 4226
4874 1033
4875 1619
4876 2922
4877 1051
4878 2125
4879 4740
4880 616
4881 1922
4882 552
4883 2339
4884 2794
4885 4372
4886 1631
4887 3634
4888 4030
4889 3005
4890 1740
4891 3154
4892 692
4893 2433
4894 1620
4895 3692
4896 3020
4897 4065
4898 1514
4899 931
4900 4718
4901 3140
4902 12
4903 181
4904 562
4905 956
4906 2141
4907 1363
4908 635
4909 4698
4910 566
4911 2590
4912 4847
4913 1633
4914 2923
4915 328
4916 1804
4917 3682
4918 2026
4919 3674
4920 729
4921 191
4922 3178
4923 3434
4924 4970
4925 4844
4926 227
4927 2894
4928 3832
4929 4866
4930 4838
4931 3126
4932 2200
4933 1101
4934 2614
4935 1325
4936 1893
4937 4908
4938 608
4939 703
4940 1995
4941 213
4942 83
4943 4751
4944 3552
4945 3021
4946 3408
4947 1605
4948 1698
4949 1184
4950 811
4951 18
4952 101
4953 1955
4954 4507
4955 164
4956 1895
4957 2660
4958 1946
4959 4069
4960 3916
4961 4399
4962 1211
4963 2005
4964 3102
4965 3732
4966 219
4967 2552
4968 3042
4969 2724
4970 2053
4971 2884
4972 1587
4973 3003
4974 739
4975 11
4976 2406
4977 478
4978 1003
4979 3642
4980 3588
4981 4121
4982 612
4983 3599
4984 1090
4985 4897
4986 3020
4987 1532
4988 2177
4989 4663
4990 1758
4991 2097
4992 2088
4993 2071
4994 4061
4995 3723
4996 1546
4997 4124
4998 1316
4999 2284
5000 2138
My AC code produced this output in less than 0.2 seconds:

Code: Select all

Case 1: 4068
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 12442 - Forwarding Emails

Post by mathgirl » Mon May 07, 2012 6:21 pm

My code produces the same output as above, but I m getting TLE. Any suggestions ?

Code: Select all

#include<iostream>

using namespace std;

int main()
{
	int t;
	cin >> t;
	int j = 1;
	while(j<=t)
	{
		int n;
		cin >> n;
		int forward[50001];
		int a;
		for(int i=1;i<=n;i++)
		{
			cin >> a;
			cin >> forward[a];
		}

		int len[50001] = {0};

		int high = 0,answer = 0;
		for(int i=1;i<=n;i++)
		{
			int start = forward[i],count = 1;
			bool cycle[50001] = {false};
		
			if(!len[i]) 
			{
				cycle[i] = true;
				while(!cycle[start])
				{
					cycle[start] = true;
					start = forward[start];
					count++;
				}

				if(start == i)
				{
					for(int j=1;j<=n;j++)
					{
						if(cycle[j])
							len[j] = count;
					}
				}
				else
				{
					len[i] = count;
				}

				if(count > high)
				{
					high = count;
					answer = i;
					if(count == (n-1))
						break;
				}
			}
		}

		cout << "Case " << j << ": " << answer;
		cout << "\n";

		j++;
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Tue May 08, 2012 12:08 am

Your code doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 12442 - Forwarding Emails

Post by mathgirl » Tue May 08, 2012 8:31 am

Ok. I have made modifications, i checked my output with sample I/O and the input given by u. Is there any tricky input? I m still getting TLE.

Code: Select all

#include<iostream>
#include<vector>
#include <time.h>

using namespace std;

int main()
{
	int t;
	cin >> t;
	int j = 1;
	while(j<=t)
	{
		int n;
		cin >> n;
		int forward[50001];
		int a;
		for(int i=1;i<=n;i++)
		{
			cin >> a;
			cin >> forward[a];
		}

		int len[50001] = {0};

		int high = 0,answer = 0;
		for(int i=1;i<=n;i++)
		{
			int start = i,count = 0;
			bool cycle[50001] = {false};
			vector<int> temp;
			
			if(!len[i]) 
			{
				while(!cycle[start])
				{
					if(len[start])
					{	
						count = count + len[start] + 1;
						break;
					}
					cycle[start] = true;
					temp.push_back(start);
					count++;
					len[start] = count;
					start = forward[start];
				}

				if(start == i)
				{
					if(count > high)
					{
						high = count;
						answer = i;
					}

					for(int j=0;j<temp.size();j++)
					{
						len[temp[j]] = count-1;
					}
				}
				else
				{
					for(int j=0;j<temp.size();j++)
					{
						len[temp[j]] = count - len[temp[j]];
						if(len[temp[j]] > high)
						{
							high = len[temp[j]];
							answer = temp[j];
						}
					}
				}
			}

			if(high == (n-1))
				break;
		}

		cout << "Case " << j << ": " << answer;
		cout << "\n";

		j++;
	}
	
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Wed May 09, 2012 9:26 pm

Create a test case with N=50000 and all Martians in a circle forwarding the email to the person on it's right. The output should be 1. My AC code handles that case on my machine in 0.16 sec, your code takes 3.38 sec.
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 12442 - Forwarding Emails

Post by mathgirl » Fri May 11, 2012 7:25 pm

I got AC in 0.416 sec, but I m interested to know how i can improve my algo. Is there any particular technique to be used ? I read about centrality in social networks. It sounded quite similar to this problem.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Sat May 12, 2012 6:34 am

I got AC in 0.088 sec with a recursive solution checking for cycles. If you're concerned about runtime, scanf and printf are faster than cin and cout.
Check input and AC output for thousands of problems on uDebug!

ycmario
New poster
Posts: 1
Joined: Fri Jun 15, 2012 3:39 am

Re: 12442 - Forwarding Emails

Post by ycmario » Fri Jun 15, 2012 3:41 am

In fact, you don't need recursion, since there is only one edge out of each vertex, you can use a while loop.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Fri Jul 05, 2013 12:17 pm

Input:

Code: Select all

1
3
1 3
2 3
3 1
Output should be:

Code: Select all

Case 1: 2
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Fri Jul 05, 2013 10:54 pm

Input:

Code: Select all

10
22
1 15
2 19
3 9
4 11
5 10
6 17
7 19
8 19
9 6
10 4
11 17
12 1
13 18
14 11
15 9
16 3
17 9
18 12
19 9
20 4
21 1
22 22
16
1 15
2 15
3 13
4 4
5 9
6 9
7 3
8 3
9 7
10 11
11 2
12 9
13 2
14 6
15 9
16 4
22
1 2
2 11
3 5
4 17
5 21
6 11
7 20
8 5
9 22
10 6
11 7
12 1
13 5
14 1
15 15
16 12
17 15
18 8
19 20
20 17
21 2
22 20
22
1 12
2 5
3 13
4 9
5 5
6 12
7 1
8 11
9 11
10 9
11 14
12 6
13 5
14 2
15 3
16 9
17 2
18 6
19 15
20 22
21 10
22 15
27
1 13
2 20
3 2
4 3
5 6
6 18
7 24
8 5
9 15
10 15
11 10
12 2
13 27
14 8
15 6
16 1
17 7
18 11
19 13
20 13
21 2
22 25
23 27
24 16
25 17
26 10
27 16
2
1 1
2 1
19
1 5
2 9
3 4
4 8
5 5
6 8
7 14
8 17
9 3
10 6
11 5
12 16
13 17
14 11
15 5
16 5
17 7
18 15
19 10
18
1 5
2 4
3 17
4 18
5 10
6 15
7 14
8 4
9 3
10 10
11 16
12 18
13 14
14 17
15 10
16 13
17 2
18 5
6
1 2
2 5
3 3
4 1
5 3
6 4
16
1 1
2 1
3 13
4 16
5 11
6 3
7 12
8 13
9 11
10 5
11 4
12 14
13 14
14 14
15 5
16 11
AC output:

Code: Select all

Case 1: 13
Case 2: 10
Case 3: 18
Case 4: 21
Case 5: 22
Case 6: 2
Case 7: 2
Case 8: 11
Case 9: 6
Case 10: 10
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Mon Jul 08, 2013 11:09 am

Input:

Code: Select all

1
4
1 2
2 3
3 1
4 2
output should be:

Code: Select all

Case 1: 4
Check input and AC output for thousands of problems on uDebug!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 12442 - Forwarding Emails

Post by alexiago » Sat Aug 17, 2013 12:44 am

I tried to solve this problem using DFS, starting a new iteration at each vertex and counting the max distance, I thought it would be enough as it completes within 1 sec on my laptop but I'm getting TLE. I tried another approach, starting at a vertex that hasn't been calculated its distance, I visit every neighbour until a visited node is found (i.e. cycle), and sum up the current distance to the cycle distance, but this approach has a problem when a larger sequence contains the cycle (it calculates de cycle again) so it would require to verify if the cycle it found was part of the same sequence (not sure if doing that everytime would give another TLE).
Anyway, what's the approach you used and what's the trick to pass this problem without TLE?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12442 - Forwarding Emails

Post by brianfry713 » Mon Aug 19, 2013 10:37 pm

DFS with cycle checking. It should run in O(N).
Check input and AC output for thousands of problems on uDebug!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 12442 - Forwarding Emails

Post by alexiago » Wed Sep 04, 2013 11:37 pm

My solution was accepted using this algorithm:

Find cycles using DFS and store the cycle length for every node on the cycle, for the graph below their distances would be {3, 3, 3}
1 2
2 3
3 1

If a larger path starts before a cycle, the starting distance should be reversed and include the cycle length so the starting node has the largest length, having their distances as { 5, 4, 3, 3, 3} instead of {1, 2, 3, 4, 5} - and cycles keep their cycle length not the max length.
1 2
2 3
3 4
4 5
5 3

Finally, find the max distance and print the index.

Saminur Islam
New poster
Posts: 4
Joined: Tue Dec 10, 2013 10:49 am

Re: 12442 - Forwarding Emails

Post by Saminur Islam » Tue Dec 10, 2013 12:16 pm

i cant understand why i am getting RE ..... i cant find the bug of the code..... any help would be appreciated

Code: Select all

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
using namespace std;
list<int> adj[50005];
bool visited[50005];
int counts;
void DFS_visit(int v)
{
    list<int> ::iterator it;
    if(visited[v]) return;
    if(!visited[v])
    {
        visited[v]=true;
        counts++;
    }
    for(it=adj[v].begin();it!=adj[v].end();++it)
    {
        if(!visited[(*it)])
        {
            DFS_visit(*it);
        }
    }
}

int main()
{
    //freopen("i.txt","r",stdin);
    int i,j,k,N;
    int T,P1,P2;
    cin>>T;
    for(i=1;i<=T;i++)
    {
        cin>>N;
        for(j=0;j<50005;j++)
        {
            adj[j].clear();
        }
        for(j=0;j<N;j++)
        {
            scanf("%d %d",&P1,&P2);
            adj[P1-1].push_back(P2-1);
        }
        int MR=-1;
        int Email=0;
        for(j=0;j<N;j++)
        {
            memset(visited,false, sizeof visited);
            counts=0;
            DFS_visit(j);
            if(counts>MR)
            {
                MR=counts;
                Email=j;
            }
            if(MR==counts)
            {
                if(Email<j) Email=Email;
                else Email=j;
            }
        }
        printf("Case %d: %d\n",i,Email+1);
    }
    return 0;
}

Post Reply

Return to “Volume 124 (12400-12499)”