-
Notifications
You must be signed in to change notification settings - Fork 0
/
day9_1.py
1019 lines (1013 loc) · 8.99 KB
/
day9_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
from itertools import combinations
class Day9_1:
input = """4
10
17
48
18
24
14
33
6
34
47
29
2
38
45
27
40
22
43
35
49
5
1
9
3
7
15
10
4
11
8
12
75
13
6
53
14
20
23
16
52
24
27
17
18
40
57
5
19
9
21
22
33
38
45
31
35
43
25
42
26
30
53
32
48
36
39
50
71
37
14
55
54
23
40
61
44
90
94
46
45
82
58
49
56
63
68
136
87
51
127
53
59
153
77
138
79
98
74
130
114
89
91
171
209
122
121
119
100
104
152
151
110
112
125
132
127
133
156
187
153
163
165
216
241
180
191
195
204
229
226
210
212
237
360
351
328
422
239
252
580
260
289
309
316
379
423
371
403
375
390
407
399
414
436
438
449
820
476
491
785
890
684
499
794
549
569
625
680
959
1048
746
802
866
765
789
806
813
975
1500
1194
998
1278
990
1426
1068
1124
1305
1288
1597
1315
1249
1371
1445
1721
2482
1511
1554
1571
1578
1595
1874
3295
2318
2058
2639
1988
2649
2114
3092
3445
2373
2537
3711
4220
4910
3082
3173
2956
3065
3106
4376
3125
3932
7665
3469
3862
7458
6265
4046
5070
4102
4487
4651
6231
5329
6399
6642
6793
6987
8034
6021
6062
14299
10641
7593
9002
6594
7331
7571
7515
12327
8148
8533
8589
12057
10164
15479
9980
14235
11391
12615
16185
12083
12656
13352
13393
21814
16126
20231
23516
13925
14109
14846
16737
17679
18128
25626
22458
27502
24215
21371
22063
22636
24006
23474
44239
28198
25435
34865
26745
31604
28771
30662
50834
32237
28034
31788
31583
40137
35807
39499
43434
43829
44007
45377
44699
45537
62450
76039
54136
70984
57407
53469
54779
90586
58696
68171
59617
59822
60271
63371
67390
75412
75306
88811
134002
90914
87836
88706
120843
142947
115050
107605
108248
108915
120859
110876
112165
114396
122988
118313
196271
120093
127212
127661
130761
142696
150718
163142
199687
273457
205310
230783
221080
215853
216520
217163
336071
219124
261594
358444
223041
293903
232709
238406
245525
247305
346614
254873
258422
438093
293414
368452
386183
428351
421163
438894
807346
434977
555195
435644
480014
442165
680502
591153
468566
679585
1026199
706972
686773
492830
502178
513295
693767
626874
661866
714577
821827
814534
856140
934995
870621
903543
877142
1421549
993309
972844
1173332
961396
1497495
970744
1314657
1015473
1200068
995008
1487838
1129052
1529111
1288740
1341451
1376443
1536404
1685155
2616890
1726761
1747763
1774164
1838538
1847886
1965752
2170812
1943588
2507148
2309665
2470503
2010481
2514725
2144525
2482846
2124060
4018698
2976938
3255872
2630191
2717894
2912847
3221559
3474524
3622050
4565780
4288889
3944976
3686424
3791474
3909340
3954069
4067648
4640672
4155006
4268585
4134541
4606906
4774716
4754251
7200848
5348085
6931007
7567026
9503091
5630741
6134406
6696083
7160948
7308474
8356537
10237647
7841430
7477898
7863409
7976988
8021717
8909257
8289547
8403126
8741447
10102336
10909122
9528967
10384992
12509033
15002378
11765147
15450495
12326824
14033867
13612304
14673071
19817507
15285462
16130977
15319328
15341307
15454886
15840397
19631303
30626769
17144573
16692673
24848295
18270414
19913959
20438089
31290892
27794495
24091971
25377451
28909720
25939128
29874264
27646171
28285375
29958533
30604790
30660635
30774214
54752606
39932368
31295283
32533070
52642790
40784644
58568709
68217743
38184373
38708503
40352048
44530060
49469422
50031099
80717012
54848848
53585299
54224503
55931546
57604704
83134223
69313293
61265425
73317714
131886423
109245661
63828353
79060551
70717443
76892876
78536421
99973928
82714433
83238563
84882108
70639851
93999482
99500521
103616398
107809802
134545796
124941946
117196971
130578718
118870129
125093778
131905276
131982868
161250854
146542786
159607309
140721229
239792670
147532727
149176272
153354284
228558344
153878414
202622719
178881590
164639333
285337152
203116919
211426200
225006773
236067100
272626505
375101130
243963907
285861282
256999054
279438003
272704097
287264015
311182119
302530556
288253956
296708999
351798991
428614275
365304614
318517747
332760004
611168230
447080826
367756252
428123692
583973014
436432973
461073873
749611382
500962961
516668004
773667058
589794571
529703151
552142100
559968112
575517971
584962955
717103605
683822361
615226746
1076480932
746641439
698064618
651277751
916733018
1036591844
1301753482
864556665
889197565
1026227544
897506846
990777024
1017630965
1030666112
1076636116
1081845251
1626386415
1112110212
1798948856
1135486083
1160480926
1200189701
1266504497
1381886979
1313291364
1349342369
1397919190
1568010769
1515834416
1753754230
1762063511
1855333689
1786704411
2126263107
1888283870
1915137811
2072622275
2461452581
2107302228
2158481367
2217331334
2247596295
3314783272
4450269355
2295967009
2360670627
2513481065
2579795861
6667600689
2662633733
2747261559
3159982701
3894006639
5473264639
3548767922
4004035745
8740222964
3674988281
4373859402
3803421681
3987760086
4179924503
4265783595
7765052627
6162517112
4464927629
4543563304
4874151692
4656637636
4875762870
7389243935
7621413251
5242429594
5409895292
7425766296
8159790234
6708750623
8437569943
8013695551
10342441615
7478409962
11064232216
10819154748
11801337754
8460059317
8167684589
8445708098
8730711224
19224022450
9008490933
9121565265
15938469279
15146320566
12278050887
10118192464
15549034169
11951180217
13256125145
12118645915
14876435212
14187160585
14722446174
16897629260
15646094551
15924118060
29833255136
16613392687
16627743906
31620075434
16898395813
33946468624
17176419322
19239757729
18130056198
19126683397
21072745482
22069372681
27000497061
22236838379
35867501635
24069826132
25207305362
32382808542
32544490364
32259487238
66490958988
30646564234
49750131632
31570212611
32537510747
33241136593
33511788500
38249164804
34074815135
36138153542
36303102719
51499244967
64920319289
37256739595
40199428879
43142118163
73124241230
124623486197
46306664511
49277131494
54716390366
56777517973
62906051472
62216776845
63184074981
63887700827
64107723358
64811349204
65082001111
115606968325
66752925093
67586603635
105010778083
70212968677
72441256261
79445220882
77456168474
80398857758
89448782674
126793752299
92419249657
95583796005
101023054877
103084182484
116030056587
127717400676
119961592954
125122828317
145042772109
127071775808
127995424185
128919072562
129893350315
131834926204
134339528728
136965893770
147031824517
239451074174
142654224938
166904951148
156901389356
169847640432
172818107415
181868032331
198667978489
223579220190
196606850882
204107237361
219114239071
243101832395
330946379610
245084421271
252194604125
343710750598
270649649123
376416967944
260753998766
438119052663
271305422498
276993753666
279620118708
289686049455
380480609546
299555614294
353508240238
326749029788
434062636456
516528858013
378474883213
610566498318
400714088243
522078174937
578943633913
550060618681
488186253666
670459780386
547643402789
589241663749
531403647889
537747752432
532059421264
765180007332
548299176164
918228361978
579175733002
569306168163
616435079243
680257270026
957650616215
1129004252594
858808451052
812537519669
932117736132
779188971456
888900341909
1158119366915
1577717527001
1158547831912
1019589901555
1020245674930
1228556446190
1063463069153
2641180596154
1127474909166
1069807173696
1080358597428
1117605344327
1706418543079
1148481901165
1185741247406
1296692349269
1395624050699
2075881320725
2074641589315
1591726491125
1671345970721
2691591645651
1995580805285
1952363411062
2275956810331
2039835576485
2083052970708
2083708744083
2523098959865
2147720584096
2266099844834
4766233234966
2187412518023
2150165771124
2303346591733
2777467738531
2266087245492
2334223148571
2445174250434
2482433596675
2692316399968
2987350541824
3937433216213
3263072461846
3544089902187
4194444930586
3947944216347
4233218741832
3992198987547
4349152815542
6124845734236
6067188862052
4231429328179
4297886355220
4335133102119
5137516312948
5321573690395
4337578289147
5111690887102
4569433837225
4600310394063
4711261495926
5708246712280
6820011885822
5745506058521
5679666941792
6250423003670
7457517392432
6807162364033
7492034118534
9656706792514
7940143203894
8223628315726
11376596201258
8672711391266
9409577242322
9475094602095
10314939895746
8633019457339
10017245230939
9921884084458
18947959353085
8907012126372
13070434889492
10308557106343
14615258838652
10390928437718
14380958103546
11425173000313
11930089945462
12486829305825
19293991669858
14264679756465
16847155330266
15715662434260
21033302993772
22321018383180
18147805993361
27140835434573
19939129315397
17540031583711
24655608194183
18554903541797
18650264688278
18828896210830
19215569232715
19297940564090
22795386412168
37852844105887
24689515209889
21816101438031
22877757743543
23355262945775
23912002306138
26194769701927
26751509062290
41528022431821
37479160899108
35497420018544
33255694017971
36094935125508
35687837577072
39356133021742
36190296271989
36368927794541
36755600816426
41706653954373