## 11867 - Politeness

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

Moderator: Board moderators

jakir052
New poster
Posts: 3
Joined: Sat Jun 26, 2010 11:27 am

### 11867 - Politeness

Any hints?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11867 - Politeness

there is a Nice solution to this problem ...
solve 10290 an easier version of this problem ..
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

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

### Re: 11867 - Politeness

Input:

Code: Select all

``````1000
605627373
771228035
1924759831
776568119
1616418010
1288865065
822584979
530264124
1523683647
1028354224
772901708
1060373412
1947900878
269589094
1422769571
571964291
1809690815
118216934
1365181477
1425463935
488431151
266894726
1097357720
601480340
927875928
694194406
1599987469
237678809
85500806
1871468888
1495586875
691128179
495213276
1272863058
1467696298
2111631286
414244475
142797629
494411763
1937928123
1171151854
1267313471
850817887
971569084
1536902565
126103810
1543533375
1199109732
244320744
761231204
477090019
732751895
1028125930
1574447739
1334232235
1956001858
121158497
786736056
46197019
206659303
510721297
1541783894
897787482
1005934573
667163304
218000132
970082211
1081407780
360797762
1464493974
871852255
1531949616
584323797
1722670142
356035052
2121226362
1848773952
1899568427
1172852446
2093094696
513315983
1649942465
678362944
1541441913
1076906556
2012595179
1349960123
1198065054
651847588
1396157142
1404724357
1162568885
790457389
155028192
21019810
1457620693
373028324
991102021
391544825
733826086
308112348
1263397080
118292054
892436145
838583574
474327106
866178860
539873878
226411885
2039031306
485484927
739727868
1541490124
1163847871
133686133
470913032
1028959402
1483646256
1668978086
1680806990
732319751
926218796
695892227
1522777140
1081246988
716912037
832914185
1454275312
1708014059
1224459011
40617751
2016126407
340372443
158909805
761078904
1178956018
633236912
1627257764
1718829896
859648797
1518805423
56831175
1599376666
912811899
1220679046
1733062799
1383724931
102154801
1069225408
905219370
1782961791
1801545159
1831438166
331370371
1176838651
765201506
1048282408
2009752836
71993170
608812819
1086728199
112610921
477455578
1427100643
271520727
1238534483
458573013
904757639
718308599
29919261
1764406436
89630374
86750437
1216299454
1002442273
1307429483
801878606
238683557
1409584284
1871104014
1143902927
1045062428
1525165525
827857445
1376432799
554520528
1593058951
277231559
416789716
1665052121
886044379
1503517916
1777663043
1363499957
783134911
2049183770
454550792
1241707924
806457761
1172859392
1271627185
423380549
1262489766
1358377622
1639680004
117448392
518323458
294074962
356131949
1927907742
17695328
1500034876
825486522
1542860853
180408673
54435673
2097381381
1773467624
331667233
366687449
1291036097
1217711612
1870205365
921215492
433727921
505856628
822915614
888278714
1747564552
1629373375
2061138106
871708090
2052753925
1176144224
82602064
1544950281
1293592616
600925522
1839025243
1649724565
381349617
1856720571
1002275793
1206836139
1252097776
1182684466
1261271813
1201995509
808668442
1592939046
1568682958
2099704540
663167010
1291404676
873436384
1096894931
1797261304
1696351999
1985173645
1397342209
1178241726
1898828103
121566651
1083512003
927488680
204168715
480978636
73597648
805094238
172520231
1723322214
1186443855
2029240802
578114359
245796346
1133854930
1760798826
1507068159
188366791
421983620
952523557
1757049750
374204512
1615690567
900970778
1247640897
565101851
550748434
796509248
402791848
1948090643
1974750974
154136304
2069657294
910779330
1081624984
126342362
1391757966
1155222632
931436600
1564278198
731061198
2117880455
1446035352
1309175558
216193153
432406635
922490736
1723261313
620773426
1344474356
528301222
230339528
1718678869
2143991790
1131310306
818836118
561609993
1682058741
1615345366
964401841
1482665736
1442612692
1118538145
1404839383
205908374
52679481
1531181745
1597666341
1207902114
315134697
1014460891
1938963312
285531504
313012595
1100655222
501724657
745419230
2023145958
77502322
1366192657
1220136667
605803545
1596532185
791331888
602311687
580358844
1610168006
1163921680
114933937
1078029724
2128323521
1597599673
373158768
1099378019
854955408
579067143
1152057500
238653505
29249836
212475966
553788202
1043710727
3955631
839319706
1356723322
1104610853
1341044364
2102142553
980273164
1418546686
1320851562
52926183
2024350231
769900099
844258071
479178270
1350258943
306942429
1643099950
1465192880
1384972153
1623939824
915308906
1758130921
575834195
1770264314
189714416
1727891695
2008917820
218964252
1940367662
415222374
1262674979
1944323293
1254542081
471914654
901450498
448102797
426573559
1881723662
1866649483
1747425121
1934649845
1743516067
369841572
631424268
75210689
1720100516
938366697
1718310640
1037809748
175855202
1194766816
1953118654
1933986124
1770601011
1575899321
2123700540
1351009058
1437333493
195181145
1143893072
1852555867
1457856124
940732717
959614300
1929770778
1842183216
1407717097
208860689
1576423230
1126882933
1956285810
1363589428
722915352
178643735
1995013696
798126041
1898744251
785896746
368953033
789070351
961751948
1563719849
594705358
748254424
1186837212
23121031
724471317
390362623
1460454524
919652462
1534255695
1165526743
230024938
327504765
2125141044
12312069
22204333
1385374493
221172758
1598627563
364773778
29974921
814733343
1087689130
208618656
662263392
1885815172
2107362907
1448160138
107284557
748949610
262428438
1671004407
1343654968
1010682863
710357971
1366775999
1735154180
1100720594
679746875
507322994
487492642
1845273619
737347932
814997407
1822931015
749660001
837201740
1060821860
970832760
288345655
1425595639
1000807681
1103078999
365801121
1209426337
1765342391
104132645
1169305596
1066018881
211417203
1918255206
1328447319
1882421610
1114426527
191646534
445295933
333718878
1926800714
1546016528
1013465754
286640060
2033509170
711255725
1023987993
701022929
386703092
1773647994
1538224669
1447524952
596997106
1826570324
725636943
1597804787
782165675
1091438065
659747476
400024418
1195570710
1829053072
1466043299
1406987913
1599824631
647006971
1141925875
566767510
838653505
1587221809
900486388
617970572
985754689
1913952142
904610632
871780211
477724219
1928598625
1572803140
864427311
1554762972
963544161
164468616
4276430
642630837
890105559
1602081218
1424796513
1981543624
114345046
1824820931
1029630687
1943398119
1143380583
289134952
1395739102
1790387554
1431060828
1962506612
481557411
870798989
715509352
1099527983
1856553678
481977847
2004138616
580850241
959702066
1785253593
6169733
1824129378
1192532917
969713894
1988597994
1196809348
1612344731
731219905
651406918
889657596
565279882
765751964
566994880
1594910569
561666435
1710375463
1884045521
1957405537
1353279369
1167622701
1772428501
1834836780
2038421690
340454206
786881116
1747491720
822432053
643536084
180858313
1782134119
281306029
187028046
1458779849
1473838947
1156741940
1299894195
523164647
621603024
2031114101
1174571565
1511260620
448910335
1940323529
2078255500
2043820904
354506317
1641147315
1780382777
164428206
846943036
800521831
1936856708
534296169
691459873
129827266
1321177285
291467946
952259319
1964713369
472326259
586909790
98535750
659354306
2045689640
1572374697
1816096246
1198100187
2095539344
290215622
1081730640
1122627261
1801476243
1530640975
915467143
1732248095
1426978231
1269973460
1225911763
1059877361
1434401666
2072854799
1860399192
1223774726
459667320
404375417
1353601992
1780844605
695843363
158377663
1598074326
1168169623
745287454
1696610077
1827523929
643493446
1121501126
1496136527
1841593633
1069556823
1786352150
775840626
44700436
1440344745
158997953
960167579
1025109192
1585976185
82657391
103537307
498369898
1517059058
28908459
211285442
593350136
488575779
615660859
1946952129
121936737
1311504223
2105329792
1720011063
332190198
703133598
1269137492
12230479
1346627044
243154971
1508367006
1040737030
1312711794
1147235508
1816577656
1357412230
440096605
1975575609
170096162
1465205798
1414068146
252753553
1568743105
1912438044
1769812611
1597651564
2123723486
215679100
2086227344
591900698
15147581
60680433
1903404921
2120477373
1780691496
88111471
676127324
902345341
100341950
2022754368
1145500312
1608708956
916007750
310728458
608460817
585101758
1668140688
1048557422
413193720
1838236850
366279572
1827261866
2090990404
1935022678
1592216263
1713319367
1385190594
1568456101
1928998467
1323934290
12873151
1944146048
1384614723
1916278072
1917139774
1017822572
2004389543
445783450
1920167913
2104731493
321054170
918184577
1565956802
1237061921
1228913035
26933971
1822163679
749570075
1075491393
87873751
440323278
1441770966
1915135618
383830034
1229309996
1359868233
2097149401
467016942
780840686
1878664221
1790951233
793713838
1675326621
1028082308
562508262
1444982747
2045904880
419414158
1890766197
1818589145
376662003
64336720
589290074
1942618805
1301398641
1818203109
1969552776
976078672
420289537
897560522
1063952424
860612815
191847840
831604394
1244442849
1421157836
43988979
1194108602
1888174778
824829665
925289175
1531642363
1618543503
453132149
412241024
33568118
1898114896
310662256
452982276
1641397446
2129251402
829644279
1705734166
571057828
624779437
859649159
241777290
446848565
1835727831
662066827
1344409087
752196607
1522679642
1536256927
1583801001
619638843
809931115
1627789980
1813747445
550622246
305135998
591552973
2082264609
1923679501
1044685122
347021985
1957247619
795316370
657684242
262746247
289230168
639451996
1092390527
1994964334
1210509824
1717169964
707129845
1452287114
16534881
395374029
2114353941
1360943969
1147570636
1489549935
749717248
583887990
2109188778
1559648364
64194322
1775452576
2110270610
369330320
219521901
2045051571
145526174
1264207023
244589909
2102773793
2059523393
902274151
218036393
201269914
1541726147
1310426920
48750600
604752323
880113236
755880446
2057039438
896648117
1151254475
2023909731
110108438
151341463
1365976019
859825687
735229453
1327681149
271990403
799423776
955650077
234777365
1168754096
1175171978
132345288
1314280270
291895353
376935197
1269570416
203935099
1279209348
1487606809
405205013
673451847
650550081
453955613
1278204171
1530663317
1209836059
1187759961
279827786
213606886
1064186044
389936225
364948350
282678415
1249761912
1100177803
1610359565
1521752315
1899601579
418525994
1756529680
920872028
1593697973
1888874968
87668650
1885593326
118326518
1357239066
2089528425
1397535866
697362227
347249790
2070987714
1347912308
801205404
1201708237
731091977
2011041463
241984550
1010919764
77164702
1306170594
1400855989
442113052
1588849010
503134253
1542290855
1051724927
2024886568
1294408787
1470250921
1633932600
67797167
916465246
1375323920
155465817
654574925
1493650438
1512704884
596619702
743702657
62583463
943869493
667206723
1410495772
1745074897
1868914960
2141587749
1608632712
2110899510
1005023865
1685797414
1269586456
258396206
2127910466
710951818
761530459
1522717674
1762676745
638933379
669642813
``````
AC output:

Code: Select all

``````297672945
853801893
172577017
813320687
470371014
892359468
960115269
605686457
348593589
721390249
921675714
542799293
366879794
769856660
830835489
911309666
391503500
884118598
547299333
798274290
784203133
267572882
494368890
476914397
163711993
816811254
554294964
610389390
486026606
805350439
473770168
99942913
849036585
133505780
991005862
398850941
802264661
970515662
490661313
306642863
244545314
232112163
765059792
200623820
432292085
942978187
555341498
882628847
450898338
776585163
763245754
485777331
981270982
839821627
514544820
780759550
683730363
778452931
992541786
710525125
295642116
423095547
611351189
775607860
246401819
195091587
194544976
728572304
467204337
626549611
323746724
322884176
511239944
675432947
811989489
709289253
324953314
423928285
281641046
768228385
468381080
652098442
898194037
795470226
746504908
582506718
147658958
968636599
291148529
829751153
785647679
340461893
164325925
626683539
463029489
383061980
151640112
264961653
579399946
415784949
269218295
620311490
480103653
984007602
952924033
36102237
445016540
853658568
513543761
703327686
177320001
818503010
181660354
630895493
853856805
101237306
53191620
215558312
982538740
690810039
687929903
957321571
276822810
657399909
143286421
495994959
53244550
769157685
618473802
531894932
585881226
328459391
347560649
855709765
927638361
133124322
375924260
920500979
591683391
175127373
408454715
876033408
447313948
906255690
673946446
193308982
24179766
861932557
53570042
9444857
779532512
356880100
252260331
285128327
657421271
332363883
305374982
442456828
963128069
772003350
100647656
512651503
725744057
547082081
87363985
199823260
568833097
97483874
697487982
483824231
760839655
564057051
901737441
663306787
25093471
30540904
982487897
857504870
251152693
150015972
510480013
727655224
636913344
181728395
148086220
323645599
448012327
397097184
444805180
463284533
552070133
45844940
296884262
530038446
369336691
556817866
637120423
544095252
67800189
937711365
455107844
997111216
965116688
446711086
633093587
271166613
852412720
549272389
202652656
464358638
610095230
60685255
927329681
360499538
279669300
48633264
310003001
601168421
605212247
234882060
581534850
340679008
503893274
804590259
720732989
440050335
597332137
838365837
137272392
515671911
81102455
199950381
423463499
141885570
711448883
576533094
410247246
833962593
507212284
489897187
468322096
983174128
903736916
566946471
151890877
368498298
553746163
39635215
325208920
123884302
837679254
784364768
15042698
533314819
228576146
81174462
369347031
803070971
515754806
859795183
108947500
4054979
34952326
941434243
321396517
190021690
113178065
630170132
416972819
761746670
164380649
702771353
912284468
16114323
543227487
791838811
134173273
18547196
418805756
493956298
143687764
540582141
769612717
595579729
49345389
33785026
855400803
96624480
495690607
790891736
175170593
409697476
345371526
734493943
241632191
784107054
398567448
82785842
200653912
752479289
297846588
889823075
831439665
420783590
93257281
276096087
391680005
389547954
813282733
458400586
370597700
781978106
27893667
809672723
893641440
196158986
943852443
498487525
338101352
180224009
167502624
818091258
519647455
464258808
21442347
315665211
685050940
259103158
548947186
30458391
954618779
23063669
426617270
323795004
286342739
439579894
433774608
338506018
151845869
350512651
295048183
287014396
440156142
510363638
555628067
66960385
729666366
845724671
446686585
178094971
75625990
214393641
111438438
176827312
490658750
805364784
749819573
291386681
827361746
403326223
34632690
28193874
178752892
486406859
603791947
935345098
46734025
337707569
518277036
520420636
658293221
447065475
625594482
622053166
952404076
997266075
962425276
350273893
549129235
622611118
566831046
142559102
509012764
219932362
867281586
358162723
742003696
375621191
897325176
419057474
329918919
114666119
472152095
343926732
288826795
912503030
916207578
259877441
153928705
126062732
938447358
891511946
850696323
290340193
126145998
492025214
642028030
732147626
623984502
218601621
371975780
228256813
392136660
448490675
312280388
852313427
564454373
977723103
400036522
250065122
934958811
631854362
259316195
577167276
762291835
249461113
924582447
425680174
553207674
332916240
967612202
317683167
751810630
381634498
158722277
743190481
128328905
483854244
874770715
418489273
725105642
941687845
946974544
211471350
837544032
779987876
522137340
566052174
247138762
532443997
411068902
399815140
652137381
92187194
363611438
330279108
334052437
544725061
671124270
583258865
889944241
851491758
714247226
164885146
114655001
786447965
585773648
187040767
987538842
644196711
322835533
860571965
983664958
121788162
72371828
654617831
769803812
729483160
424987278
376000308
655941909
526917104
735451976
265736751
401322995
659803561
884784040
134447860
618624135
288558020
219483761
697599712
817594904
992729173
400747911
421514845
602865607
144570940
868631222
711269690
660785900
416937137
350844314
887338784
847925567
769749915
219643330
92662559
482297037
839217121
212772494
513489145
157221788
271957373
230938530
411085262
820252389
946306185
332744508
996999733
676061430
557777168
727390593
607360245
769859959
341974968
135841728
354536135
40437177
46117877
767366730
462362748
758188120
822449921
134580556
7983550
452500826
498944202
47646552
9471052
202380628
371344073
764663482
932858762
518025298
100222186
677997106
790271384
197598666
981750374
2798156
807604035
580727703
187347832
987969168
416920156
150021841
882045075
351057861
836443791
173063478
89375251
718673956
161618195
979602810
917829703
91587877
884673261
578369144
672148175
78938314
926701434
334219283
625758071
993838341
274904329
883788791
392058686
526393470
759053995
668443118
105997514
330442451
83303853
277047185
566009126
919158762
162457148
813285654
899799463
303708032
414140090
872194051
780575321
420950776
814983042
990601136
605341055
821439929
283776326
856466930
803662557
875216048
616362211
651383243
438620966
870763848
527871833
229525571
588673199
627538373
927774013
410131173
69979638
1852566
171168831
607182196
143015353
833218760
371712135
207296380
931670309
621816454
549625007
356795377
166290251
818843525
190790101
166542135
945211540
425939662
222017325
621456408
239061291
598135803
765815641
87140516
736703842
394331168
936744241
666177567
957611490
557876724
718433962
304438948
387285612
29785503
876193372
978596104
86669258
706278158
512009793
677582105
946734616
700236716
368264158
792136743
570749804
878501151
873151771
147081756
375578879
737055494
853523527
527157196
487953789
562631876
812715949
766799010
220517807
379413578
91544469
506063832
967553113
272487154
729082898
432206471
506636038
337270801
967310676
345814220
237503316
319306637
375043897
783988169
440303591
150357300
588052941
926831611
610054183
106175318
811531559
613520918
261109155
162021542
441204487
994204069
811298628
461245754
89471282
700795505
180100368
993366101
313531589
157738192
212566036
123652973
297363669
840101334
758576624
562636010
752829003
280272760
230876578
585317564
266901564
268327325
182643579
121549203
845852286
940090778
71201226
978131973
285724533
978774998
827198366
491446378
507162927
454089518
389175862
637732279
376161875
401499271
290997812
5491395
89662211
873204865
102705631
333739663
410479362
154762191
279076250
826706793
342933234
734026914
989153694
160902978
864298393
470266568
405340960
401292185
407365896
883159965
115690856
569655756
559665252
690359251
41666176
845382568
809947407
617256306
506922716
148721145
475741322
867814084
851346594
889978478
934901350
702906257
512269826
365227597
43764481
70490141
587060543
808499296
406759541
954594652
946918952
356070071
958945356
582380932
604502552
930468126
301649641
555187199
324130928
247955117
620431390
302062227
373716036
597216837
10395669
193327468
619874164
639109038
262290332
339582737
89180941
193753803
800304650
437911981
751861004
602019221
852095886
726792692
148041626
635746920
661551089
545642061
815069381
844621003
673233870
57385252
855789079
424364469
410013432
297392266
145837914
456580410
930959387
680255939
622608701
646655566
347884387
485896380
379570883
256513801
937439196
287994081
148972979
230919694
193113584
872070285
789520448
927004902
461903256
306865073
869276712
990330092
223902864
195658206
120243548
121697513
944413450
884787274
587449344
718162269
639384570
640442278
857463751
187603895
771164386
890585482
837749235
137836632
287838240
323059772
73703904
449413301
800553898
242907900
520053295
100506769
415957166
94834490
517998077
282177453
589567564
656331896
548486570
377821703
139118374
922760001
69494812
14267285
581029174
474410249
153313430
256119381
616654013
989494455
435100727
993056832
537468759
478852015
119618577
94255232
661726811
111377535
916023850
210228600
483013728
887911088
917058376
906628388
284097510
269492900
290316783
622341997
830400569
9350407
105209466
203613257
901420625
704195889
428172115
558511551
396188722
264250427
265009673
967090939
967147286
797543677
37889809
844447197
441004659
635292177
768314164
983030295
434274261
687137765
47607367
270948232
999392506
934085798
476753788
823423889
982138396
260313964
608378427
998442162
899671299
294778648
816513536
342306351
704205707
664702693
465099436
198270558
233771805
319864052
302919402
364365634
806857604
523168111
852944752
347266563
797833684
560780319
829446413
449011452
169631917
75167716
537677913
40825920
426748422
229571354
460807970
635913924
404760739
814146713
442578535
992832544
4741240
11207632
306543333
919997948
746793256
864248550
886277282
537346813
503335729
568313114
104296321
916924368
665762475
164382008
752385088
338052510
704272940
264725770
932403420
325955912
318486602
415115632
542842231
259712869
998261289
572915640
322511379
42814921
600654883
921094020
386297057
432567329
85303120
76196942
982608039
958787835
800688187
``````
Check input and AC output for thousands of problems on uDebug!