11120 - Very Funny Mr. Feynman

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

Moderator: Board moderators

Post Reply
mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

11120 - Very Funny Mr. Feynman

Post by mrahman » Mon Oct 16, 2006 8:02 am

Hi,

I have solved the problem using Brute Force Method. At first I am trying to find out a Mathematical Solution or A formula but after spending hours of time I have failed. Is there any possiblity to have a mathematical Solution of this problem.

Thanks in advance

Sorry for my poor english.
Practice Makes a man perfect

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Oct 16, 2006 8:49 am

I think that it can't be predicted is a property of irrational number.

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Mon Oct 16, 2006 10:56 am

sclo wrote:I think that it can't be predicted is a property of irrational number.
The fact that a number is irrational has nothing to do with whether we can "predict" its digits by a simple formula or not. (For example, there is an explicit expression for the nth hexadecimal digit of pi).
That said, I don't know what significance prime numbers have in this problem. I solved it by calculating several square roots, and my method applies equally well to non-primes. (And anyway any method working for primes should be easily adaptable to work for all integers). I wonder what the problemsetter had in mind.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Oct 16, 2006 11:18 am

I don't know if there is a mathematical formula for that, but it could well be.
About the fact that I chose prime numbers: I wanted to make sure the square roots were truely irrational, I wanted to give the maximum prefix length in the description by giving a concrete example, and I wanted a big enough range to rule out precalculation. I just had to pick something, and the prime numbers upto 1000000 was the first that came to mind. But I could have equally well chosen 'the non-square numbers between 487656431 and 500036512', for instance. So seek nothing more behind it.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Oct 18, 2006 2:21 am

Now that I think about it, one has to use some big integer arithmetic to solve this problem, so the input number could be arbitrarily large. Maybe it is ok if it is a perfect square when the square root has thousands of digits. But then again, those are not irrationals.

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword » Thu Jan 04, 2007 3:06 pm

anyone can give me some i/o samples?
thanks!!!

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Location: Bangladesh
Contact:

Post by mrahman » Wed Jan 17, 2007 4:02 am

Hi mysword,

I have no Idea about any critical I/O about this problem.

Here is some sample I/O

Input:

Code: Select all

2
3
5
7
11
13
19
23
29
31
37
41
43
47
Output:

Code: Select all

2 149 9
3 77 0
5 129 4
7 127 8
11 180 4
13 3 5
17 466 6
19 49 4
23 36 9
29 50 8
31 158 3
37 19 9
41 51 8
43 13 0
47 79 9
Hope this will help.
Practice Makes a man perfect

fsps60312
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 11120 - Very Funny Mr. Feynman

Post by fsps60312 » Thu Aug 06, 2015 4:28 am

Hey, I got WA but have no idea where I'm going wrong. After compare more than 50000 cases with uDebug, I found several difference.
One of these is 360037
I use calculator to get square root and it returns 600.03083254112867295724210327206
so the answer should be 360037 1 0, right?
but uDebug gives 360037 516 6
Isn't the answer be the first occurrence of three identical digits?
or just the problem in the judge?
I've reviewed the problem statements again and again...
Somebody help me!
here are all the cases I have problem with
input:

Code: Select all

300043
320083
360037
520043
720019
770039
my output:

Code: Select all

300043 239 3
320083 205 6
360037 1 0
520043 12 9
720019 6 3
770039 54 5
uDebug output:

Code: Select all

300043 718 8
320083 703 0
360037 516 6
520043 527 8
720019 1089 8
770039 870 9
all the other below 861948 are the same

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 11120 - Very Funny Mr. Feynman

Post by dibery » Thu Aug 06, 2015 1:03 pm

My accepted program gives the same answer as yours.

I also checked with a calculator, your answer for 360037 is correct.
Life shouldn't be null.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11120 - Very Funny Mr. Feynman

Post by uDebug » Thu Aug 06, 2015 1:37 pm

fsps60312g wrote:Hey, I got WA but have no idea where I'm going wrong. After compare more than 50000 cases with uDebug, I found several difference.
One of these is 360037
I use calculator to get square root and it returns 600.03083254112867295724210327206
so the answer should be 360037 1 0, right?
but uDebug gives 360037 516 6
Isn't the answer be the first occurrence of three identical digits?
or just the problem in the judge?
I've reviewed the problem statements again and again...
Somebody help me!
Sorry for the inconvenience. You are right. The code we had on uDebug was wrong - even though it was AC.

Thanks to the generosity of dibery, this has now been fixed. Please see

http://www.udebug.com/UVa/11120

If you think something's not right on uDebug, please feel free to reach out. We'll do our best to fix things ASAP.

Thank you.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 11120 - Very Funny Mr. Feynman

Post by dibery » Thu Aug 06, 2015 1:42 pm

Some cases.

Input:

Code: Select all

235661
633067
623719
899183
454579
473911
622151
319201
295937
697967
581099
692297
471749
360907
147799
107903
223291
133813
113723
506047
415567
109619
163433
543889
571303
361033
602891
68899
9137
131611
509767
738811
387551
465541
926171
149749
333973
167033
832763
168491
495757
723169
14479
296819
836347
38303
451331
276949
643187
889687
618349
621619
40927
235891
827809
252181
573557
363683
798397
956261
843793
576019
185327
439949
168481
672787
62987
851573
352367
788377
856487
205783
874277
387679
616073
589241
358447
82129
631529
891509
603257
360307
189697
474197
386651
99289
995173
603443
391073
27739
265757
284723
580033
999067
573829
851957
397907
910109
319049
429521
892103
548417
327889
572399
187067
414097
957413
57527
574913
279397
8887
202907
369917
362407
139273
256589
240829
254279
3793
49463
883
569507
362237
854647
551689
213253
47713
111857
465797
36037
184477
509317
602909
334403
881141
44809
924757
83243
251143
219031
777143
645019
529259
595087
898853
937819
465337
651649
333737
667019
555209
123457
657121
911951
646619
93077
347141
978689
889937
129893
248189
703691
334787
385631
12479
40111
25633
406817
776267
65609
26833
585413
68447
178853
125387
417863
438961
482957
590407
659171
831217
492007
367243
570569
659621
239947
323927
289489
256577
94033
603203
849349
128341
331943
767827
189353
212383
563041
266083
245039
122651
176557
314719
97961
602033
395513
17539
300733
532981
432479
173191
25747
343631
16871
428731
84143
49921
39709
611207
477551
67733
572683
14831
616639
945359
455291
432721
507589
471719
581099
206351
726469
113969
875491
185753
284831
540157
229937
210299
356287
157519
736187
84653
91373
868957
558721
582721
53087
402763
47189
548441
482387
693571
352771
9041
267647
197159
855059
778123
420361
433151
146849
145633
439753
901501
96223
245981
295861
317411
770767
826379
871931
581473
322781
270307
597407
306347
735043
315011
109357
643439
601589
629203
795659
438611
246193
16349
48131
620297
755707
837509
830789
730447
6299
793453
694951
982381
967003
928273
478901
732829
594959
841391
538151
727733
850303
365327
58147
507953
91711
277177
989939
773231
569417
362177
315449
621833
429889
23887
943913
146249
133087
840941
665213
19417
540461
887717
349663
222059
134669
381853
240319
874091
517553
733339
727729
369991
317419
286771
304151
880513
727183
320669
697447
803497
670049
973631
790261
253369
469757
753421
837737
307339
302297
776851
765181
525961
130783
429197
239857
139091
939391
909061
790871
593531
381347
538817
577397
152563
40801
822989
238331
848251
24107
848933
459223
823051
64853
555391
665311
242863
20477
291721
536243
881249
958933
990151
57143
631307
108677
982021
348287
222293
44053
849539
620869
180241
464327
224261
479821
143243
621143
61261
32803
131231
473911
347707
347779
472133
86183
403951
276401
908927
847073
845623
917993
406013
92569
430007
13417
250199
618131
374069
52189
762877
39719
491669
123941
25747
627593
782267
364873
724519
593261
688147
474049
561917
3457
674123
510217
772349
115117
239753
850537
17491
498439
670177
36821
634279
539207
599
208627
220673
312203
828013
121453
862181
655223
32911
782123
34781
67577
924361
172633
902639
372013
554383
917591
163129
906391
958673
538249
19267
947561
777871
197741
840757
325153
831503
895579
227207
399173
125029
296117
343303
319147
574733
452531
329431
807629
307693
415937
562349
836369
388253
574969
396647
634177
266293
139547
746749
811171
870059
650779
921643
61979
105137
66763
863887
444641
327071
484411
555521
936181
113131
369137
351343
668153
73291
12653
249217
40459
637933
135479
460903
718937
283369
839791
856469
20353
866093
79691
464467
451331
759047
666437
790087
806317
620813
801817
576299
687581
846721
525439
941791
499183
421621
192307
156089
363359
938947
199403
608701
701179
836821
89387
901447
740903
666727
682153
934799
814643
257443
231481
415061
488401
570131
662443
716143
295949
960173
720179
12569
627667
424903
105229
562129
545087
435859
752303
803819
458621
444517
480941
430741
491797
225343
603443
949667
671647
558937
27581
922261
246319
545213
159521
64679
641747
94441
854467
337343
897527
801011
740099
822763
87253
179083
156733
909107
462677
72469
264283
640649
888499
87281
375029
873553
566521
148439
298169
33563
411799
124087
769033
468773
322919
307367
271043
561307
764857
461819
164191
119671
450217
704287
786431
159473
466997
76163
775513
197773
368273
812857
108949
81931
315013
270631
332611
30851
228757
749347
909611
198997
206749
305401
296489
619397
534283
319829
25999
408841
305761
139177
884077
817457
724991
616243
254329
814063
71453
59093
814337
4729
496841
798097
446081
176153
579961
319601
482039
167021
978049
445589
924659
618301
351773
527753
252667
840911
238213
829319
64231
249383
925597
758003
796139
356749
76949
148639
522637
329789
852641
600367
661187
321383
437237
992983
502973
170857
314113
837847
602141
513739
686639
550553
558121
774997
69379
588911
827269
7607
383011
831731
893413
976301
27407
376589
563051
167891
786173
323837
371941
327599
256577
683933
706523
377711
258299
340103
705209
453239
83137
231901
763967
429917
36713
237073
15289
374557
248869
568709
259603
721229
942041
853837
363917
278149
756179
523777
395201
847367
173359
474533
269651
839437
556723
126223
237563
443587
797399
272171
440807
275573
277247
206027
323377
210499
856099
457571
210113
426353
76543
767489
754531
254911
102103
476743
353891
745243
103399
419623
909133
967111
527993
162523
129127
455989
850891
297907
475753
887143
740671
538399
652837
683479
658807
549091
622019
542141
686989
356701
202393
638689
688661
183581
292483
905297
107377
958163
746939
155719
36493
83047
615259
618337
801611
135211
776327
972443
962537
11701
436279
819719
177953
850781
225493
475807
942043
81973
371179
847729
894547
183823
135637
1217
2311
704861
752831
842419
744661
795643
993611
898921
728843
412627
112757
158293
596899
587017
901399
172009
638177
192799
50707
799031
65011
334387
991201
363373
911173
832681
527729
357421
76757
585283
440809
707711
427001
616897
622241
9157
837283
725653
856721
691637
840163
53299
965983
600247
693799
488473
527099
659353
574963
388697
572437
166603
773599
303283
56443
572419
718999
371387
920539
400199
210401
420853
165961
461689
499591
108343
691997
741569
780371
397357
828701
855521
776983
349121
337537
635339
428851
400441
50047
311021
114451
808399
63727
855521
255127
108991
42443
869863
649801
215087
138661
235979
351397
401243
601021
526637
949607
95731
311323
408211
312161
15031
626783
619027
496763
384773
82471
110237
597437
846233
989839
642241
51941
315751
617119
980593
467147
440987
301057
786829
91621
607363
798911
204859
617579
699169
305603
185167
335381
641639
86143
667463
414019
165883
480647
786077
105517
287537
922463
128257
470413
501409
460081
379699
759467
658943
104207
448703
57751
82499
934523
66413
308701
509581
77699
0
Output:

Code: Select all

235661 42 5
633067 10 2
623719 224 5
899183 104 2
454579 455 8
473911 21 3
622151 193 6
319201 121 7
295937 3 0
697967 3 4
581099 13 9
692297 158 2
471749 9 8
360907 98 2
147799 2 4
107903 391 4
223291 33 8
133813 24 0
113723 162 7
506047 195 6
415567 21 7
109619 232 7
163433 36 9
543889 205 3
571303 112 6
361033 80 7
602891 302 5
68899 311 6
9137 72 0
131611 27 4
509767 19 4
738811 8 6
387551 57 2
465541 65 1
926171 4 7
149749 41 2
333973 41 1
167033 147 7
832763 16 9
168491 105 7
495757 73 8
723169 92 6
14479 75 7
296819 87 8
836347 57 9
38303 22 6
451331 126 8
276949 267 5
643187 68 0
889687 41 8
618349 40 5
621619 82 7
40927 53 9
235891 169 8
827809 31 3
252181 69 4
573557 10 7
363683 31 3
798397 280 2
956261 115 9
843793 58 5
576019 56 4
185327 277 6
439949 35 0
168481 47 0
672787 106 8
62987 8 0
851573 9 4
352367 17 8
788377 63 7
856487 59 5
205783 6 1
874277 431 6
387679 87 3
616073 48 9
589241 53 6
358447 50 1
82129 33 7
631529 25 6
891509 190 7
603257 85 9
360307 144 3
189697 35 9
474197 159 0
386651 81 0
99289 60 6
995173 230 5
603443 30 2
391073 69 7
27739 71 1
265757 49 7
284723 218 9
580033 36 3
999067 0 9
573829 134 1
851957 19 2
397907 7 0
910109 41 7
319049 40 4
429521 43 4
892103 8 3
548417 152 5
327889 41 2
572399 43 2
187067 81 3
414097 402 1
957413 204 1
57527 34 4
574913 137 3
279397 121 2
8887 15 6
202907 9 2
369917 32 9
362407 55 3
139273 181 7
256589 80 5
240829 15 4
254279 146 1
3793 291 4
49463 0 2
883 57 2
569507 26 6
362237 136 0
854647 25 8
551689 105 5
213253 39 9
47713 210 0
111857 136 0
465797 103 4
36037 255 7
184477 44 4
509317 20 5
602909 27 1
334403 27 0
881141 5 1
44809 31 8
924757 78 8
83243 32 9
251143 185 8
219031 42 7
777143 221 8
645019 11 6
529259 62 0
595087 156 6
898853 132 7
937819 317 8
465337 313 0
651649 227 6
333737 457 7
667019 78 4
555209 87 6
123457 151 1
657121 5 0
911951 59 1
646619 239 3
93077 41 5
347141 139 6
978689 449 4
889937 14 9
129893 15 6
248189 31 4
703691 174 9
334787 18 3
385631 71 2
12479 0 1
40111 274 0
25633 115 0
406817 35 7
776267 282 1
65609 207 9
26833 13 2
585413 329 5
68447 78 9
178853 50 2
125387 14 3
417863 222 4
438961 84 7
482957 30 8
590407 86 5
659171 166 5
831217 162 1
492007 119 9
367243 8 5
570569 592 7
659621 220 0
239947 544 3
323927 115 8
289489 14 9
256577 14 6
94033 162 7
603203 2 6
849349 31 1
128341 51 7
331943 98 2
767827 334 7
189353 29 5
212383 28 6
563041 94 5
266083 97 7
245039 62 7
122651 334 7
176557 83 7
314719 79 8
97961 20 4
602033 406 5
395513 78 7
17539 28 6
300733 36 2
532981 16 4
432479 210 6
173191 5 2
25747 159 6
343631 103 4
16871 3 8
428731 47 3
84143 28 3
49921 38 9
39709 109 7
611207 107 2
477551 201 1
67733 107 9
572683 73 5
14831 52 8
616639 8 9
945359 685 5
455291 33 9
432721 45 1
507589 78 7
471719 46 3
581099 13 9
206351 30 7
726469 329 4
113969 27 8
875491 29 4
185753 73 9
284831 67 3
540157 74 6
229937 188 7
210299 119 9
356287 115 6
157519 116 8
736187 133 0
84653 92 8
91373 13 6
868957 40 9
558721 61 1
582721 55 8
53087 56 2
402763 36 9
47189 220 8
548441 48 6
482387 7 5
693571 37 4
352771 118 7
9041 26 6
267647 269 8
197159 0 4
855059 20 0
778123 10 7
420361 29 1
433151 245 7
146849 11 7
145633 55 8
439753 137 8
901501 174 9
96223 327 1
245981 90 3
295861 92 8
317411 26 3
770767 4 3
826379 13 8
871931 9 2
581473 28 4
322781 67 6
270307 29 1
597407 81 8
306347 70 2
735043 28 1
315011 62 8
109357 59 3
643439 190 7
601589 53 5
629203 69 9
795659 111 8
438611 318 2
246193 71 5
16349 163 0
48131 92 1
620297 8 0
755707 216 8
837509 125 7
830789 45 9
730447 111 2
6299 294 6
793453 46 4
694951 75 9
982381 141 0
967003 245 3
928273 239 6
478901 13 5
732829 31 0
594959 196 0
841391 239 4
538151 180 4
727733 36 0
850303 31 3
365327 88 5
58147 110 2
507953 202 1
91711 17 7
277177 436 8
989939 194 2
773231 468 3
569417 74 3
362177 65 9
315449 65 6
621833 130 6
429889 227 2
23887 162 6
943913 117 2
146249 250 7
133087 72 1
840941 438 9
665213 226 0
19417 30 5
540461 30 9
887717 206 2
349663 100 5
222059 99 6
134669 78 7
381853 207 4
240319 67 2
874091 234 6
517553 45 1
733339 23 0
727729 20 1
369991 291 3
317419 230 4
286771 171 5
304151 168 3
880513 53 6
727183 19 2
320669 94 8
697447 57 5
803497 43 5
670049 65 0
973631 587 1
790261 0 8
253369 303 6
469757 7 1
753421 623 6
837737 198 1
307339 47 4
302297 110 5
776851 34 1
765181 12 2
525961 25 4
130783 241 6
429197 92 1
239857 198 4
139091 183 6
939391 92 0
909061 54 3
790871 10 3
593531 217 3
381347 162 2
538817 27 5
577397 86 3
152563 55 3
40801 208 3
822989 219 2
238331 69 1
848251 152 3
24107 37 0
848933 460 8
459223 287 6
823051 36 0
64853 75 4
555391 18 5
665311 347 7
242863 50 0
20477 228 4
291721 158 9
536243 64 9
881249 51 6
958933 321 5
990151 249 5
57143 158 3
631307 84 4
108677 49 3
982021 154 5
348287 20 0
222293 42 4
44053 3 8
849539 72 5
620869 118 3
180241 35 3
464327 466 7
224261 161 8
479821 186 2
143243 69 5
621143 61 6
61261 198 3
32803 2 1
131231 97 4
473911 21 3
347707 3 6
347779 208 4
472133 23 7
86183 129 2
403951 146 4
276401 17 1
908927 84 5
847073 27 7
845623 98 8
917993 23 7
406013 18 9
92569 19 7
430007 126 8
13417 29 6
250199 65 4
618131 9 4
374069 12 4
52189 242 2
762877 32 6
39719 227 5
491669 67 0
123941 249 1
25747 159 6
627593 55 9
782267 108 8
364873 65 8
724519 116 3
593261 51 5
688147 21 7
474049 195 8
561917 79 5
3457 56 3
674123 23 1
510217 184 5
772349 65 8
115117 33 7
239753 103 4
850537 1 2
17491 58 3
498439 95 0
670177 8 0
36821 132 0
634279 57 4
539207 16 4
599 76 4
208627 23 5
220673 247 4
312203 162 5
828013 449 6
121453 56 0
862181 71 8
655223 285 5
32911 14 3
782123 158 2
34781 286 8
67577 19 6
924361 63 5
172633 11 0
902639 105 1
372013 104 7
554383 142 2
917591 420 5
163129 88 2
906391 18 7
958673 181 1
538249 219 5
19267 18 6
947561 457 5
777871 233 8
197741 0 4
840757 27 2
325153 59 3
831503 67 7
895579 146 0
227207 2 6
399173 104 7
125029 133 2
296117 16 4
343303 159 0
319147 30 1
574733 3 1
452531 183 1
329431 7 0
807629 71 8
307693 346 0
415937 384 9
562349 290 2
836369 328 3
388253 42 3
574969 8 3
396647 26 7
634177 25 8
266293 56 1
139547 47 8
746749 128 6
811171 315 8
870059 18 9
650779 41 4
921643 36 2
61979 53 8
105137 141 4
66763 95 6
863887 106 5
444641 0 6
327071 213 9
484411 87 2
555521 16 5
936181 80 1
113131 141 8
369137 66 9
351343 88 1
668153 35 6
73291 231 8
12653 5 5
249217 354 8
40459 19 4
637933 136 3
135479 101 6
460903 24 3
718937 115 2
283369 304 3
839791 5 1
856469 130 7
20353 167 0
866093 122 3
79691 112 6
464467 25 0
451331 126 8
759047 62 1
666437 253 5
790087 0 8
806317 297 6
620813 52 3
801817 152 2
576299 12 5
687581 115 0
846721 38 4
525439 15 0
941791 296 7
499183 115 8
421621 175 1
192307 21 3
156089 55 8
363359 98 3
938947 194 6
199403 420 7
608701 368 6
701179 29 2
836821 9 3
89387 439 4
901447 12 7
740903 297 3
666727 58 0
682153 159 1
934799 120 6
814643 131 9
257443 112 2
231481 73 8
415061 32 3
488401 71 3
570131 16 8
662443 93 1
716143 16 3
295949 26 4
960173 144 8
720179 18 7
12569 3 1
627667 156 6
424903 87 5
105229 202 9
562129 71 5
545087 4 0
435859 24 8
752303 10 0
803819 9 1
458621 29 6
444517 0 6
480941 183 7
430741 164 7
491797 208 7
225343 57 5
603443 30 2
949667 54 7
671647 12 5
558937 154 0
27581 42 6
922261 41 2
246319 233 4
545213 78 0
159521 12 9
64679 131 1
641747 154 7
94441 7 4
854467 66 9
337343 17 2
897527 32 8
801011 40 4
740099 72 2
822763 20 1
87253 28 2
179083 170 8
156733 114 0
909107 363 9
462677 99 2
72469 63 7
264283 21 6
640649 7 2
888499 11 5
87281 31 2
375029 32 4
873553 20 3
566521 44 1
148439 119 1
298169 211 3
33563 41 0
411799 127 8
124087 42 1
769033 52 3
468773 5 9
322919 14 5
307367 41 8
271043 42 7
561307 197 6
764857 20 6
461819 86 9
164191 52 3
119671 95 5
450217 223 7
704287 44 2
786431 48 5
159473 8 6
466997 164 9
76163 13 0
775513 405 9
197773 0 4
368273 31 0
812857 197 3
108949 185 6
81931 284 7
315013 118 4
270631 3 2
332611 145 1
30851 74 3
228757 153 7
749347 193 5
909611 9 2
198997 134 7
206749 140 5
305401 158 4
296489 89 8
619397 7 8
534283 20 9
319829 32 6
25999 232 7
408841 31 4
305761 153 0
139177 43 8
884077 139 0
817457 290 7
724991 34 7
616243 43 6
254329 108 5
814063 41 0
71453 34 9
59093 44 3
814337 157 5
4729 14 7
496841 46 1
798097 351 4
446081 248 2
176153 30 5
579961 98 9
319601 278 2
482039 9 1
167021 230 2
978049 89 2
445589 249 9
924659 193 5
618301 134 7
351773 196 8
527753 104 7
252667 10 0
840911 8 5
238213 37 5
829319 29 7
64231 102 6
249383 91 6
925597 148 0
758003 180 5
796139 47 2
356749 60 8
76949 59 0
148639 65 1
522637 572 7
329789 62 9
852641 56 1
600367 70 0
661187 42 8
321383 16 9
437237 106 8
992983 158 7
502973 45 5
170857 38 1
314113 200 1
837847 82 9
602141 213 7
513739 79 9
686639 87 5
550553 222 9
558121 46 0
774997 30 1
69379 112 7
588911 67 8
827269 125 1
7607 37 7
383011 102 2
831731 138 2
893413 13 1
976301 86 6
27407 2 5
376589 114 2
563051 103 6
167891 57 1
786173 2 6
323837 142 8
371941 22 9
327599 126 4
256577 14 6
683933 16 1
706523 158 9
377711 319 4
258299 257 5
340103 55 9
705209 61 5
453239 203 6
83137 132 4
231901 49 7
763967 121 8
429917 137 1
36713 162 7
237073 21 1
15289 53 1
374557 174 6
248869 211 8
568709 87 3
259603 87 6
721229 62 0
942041 113 3
853837 18 1
363917 91 3
278149 72 8
756179 353 7
523777 140 1
395201 289 0
847367 251 6
173359 563 3
474533 1 8
269651 25 3
839437 134 3
556723 121 1
126223 56 6
237563 17 4
443587 0 6
797399 93 9
272171 34 7
440807 94 0
275573 74 7
277247 275 3
206027 114 7
323377 124 3
210499 7 0
856099 197 6
457571 99 6
210113 43 0
426353 265 7
76543 2 6
767489 108 5
754531 81 3
254911 248 5
102103 21 7
476743 74 2
353891 86 1
745243 159 5
103399 8 8
419623 49 8
909133 77 7
967111 126 1
527993 143 4
162523 352 5
129127 81 7
455989 14 6
850891 277 3
297907 55 2
475753 104 0
887143 58 0
740671 249 4
538399 394 0
652837 398 1
683479 26 7
658807 46 3
549091 14 4
622019 129 7
542141 59 4
686989 29 4
356701 87 9
202393 241 3
638689 169 8
688661 251 3
183581 18 3
292483 37 9
905297 31 8
107377 16 8
958163 66 5
746939 35 7
155719 559 7
36493 21 0
83047 122 3
615259 255 1
618337 40 6
801611 8 4
135211 44 4
776327 47 1
972443 122 2
962537 17 0
11701 9 6
436279 48 8
819719 80 3
177953 26 2
850781 50 3
225493 97 9
475807 181 9
942043 164 3
81973 8 3
371179 63 1
847729 6 9
894547 33 1
183823 177 0
135637 43 0
1217 202 6
2311 174 4
704861 5 0
752831 63 6
842419 421 1
744661 247 3
795643 292 6
993611 115 4
898921 5 4
728843 9 9
412627 226 7
112757 118 4
158293 415 2
596899 29 8
587017 390 7
901399 275 4
172009 224 2
638177 76 5
192799 4 8
50707 141 1
799031 39 7
65011 29 2
334387 34 9
991201 89 3
363373 71 5
911173 500 4
832681 48 0
527729 74 0
357421 43 8
76757 37 6
585283 33 7
440809 559 0
707711 286 4
427001 11 4
616897 93 9
622241 1 8
9157 52 0
837283 322 6
725653 24 1
856721 73 5
691637 24 0
840163 123 1
53299 57 2
965983 30 1
600247 268 2
693799 127 3
488473 105 6
527099 126 5
659353 18 2
574963 63 1
388697 88 3
572437 78 0
166603 106 6
773599 29 4
303283 256 5
56443 27 4
572419 16 1
718999 72 7
371387 218 0
920539 114 6
400199 318 1
210401 49 9
420853 142 7
165961 39 9
461689 352 8
499591 42 6
108343 18 1
691997 237 6
741569 18 8
780371 47 2
397357 37 4
828701 56 5
855521 155 4
776983 152 3
349121 269 2
337537 24 1
635339 63 2
428851 283 0
400441 295 1
50047 82 4
311021 130 9
114451 138 9
808399 13 2
63727 26 2
855521 155 4
255127 8 0
108991 8 9
42443 206 7
869863 213 4
649801 64 4
215087 203 4
138661 115 9
235979 84 1
351397 204 1
401243 75 5
601021 18 0
526637 26 7
949607 8 8
95731 145 6
311323 44 5
408211 7 2
312161 15 4
15031 35 0
626783 106 4
619027 23 2
496763 44 9
384773 255 8
82471 164 7
110237 7 7
597437 38 2
846233 99 5
989839 197 9
642241 291 6
51941 20 6
315751 18 6
617119 250 5
980593 36 8
467147 45 8
440987 46 0
301057 95 6
786829 95 0
91621 8 9
607363 116 8
798911 62 2
204859 250 7
617579 23 0
699169 42 6
305603 172 9
185167 80 3
335381 111 0
641639 8 9
86143 185 4
667463 30 2
414019 46 8
165883 127 0
480647 35 7
786077 142 0
105517 247 5
287537 529 5
922463 67 2
128257 55 8
470413 4 6
501409 515 7
460081 116 3
379699 216 3
759467 73 4
658943 19 5
104207 404 8
448703 352 2
57751 68 1
82499 180 3
934523 565 3
66413 198 1
308701 0 5
509581 270 7
77699 25 5
Life shouldn't be null.

fsps60312
New poster
Posts: 16
Joined: Sun Jan 25, 2015 5:46 pm

Re: 11120 - Very Funny Mr. Feynman

Post by fsps60312 » Thu Aug 06, 2015 2:18 pm

How come I got WA :(
All prime numbers below 1000000 tested, no difference with AC output(Thanks dibery :D
somebody please tell me why :(

Code: Select all

#include<cstdio>
#include<vector>
#define termin(x,...) {printf(x,##__VA_ARGS__);while(1){}}
using namespace std;
int N;
struct Deq
{
	vector<char> db;
	int l, r;
	Deq() : l( 0 ), r( -1 ) { db.clear(), db.resize( 2 ); }
	void clear()
	{
		db.clear();
		db.resize( 2 );
		l = 0, r = -1;
	}
	int size() { return ( ( r - l + 1 ) % db.size() + db.size() ) % db.size(); }
	void pop_back()
	{
		if( !size() ) termin( "pop_back size==%d\n", size() );
		r--;
		if( r < 0 ) r += db.size();
	}
	void pop_front()
	{
		if( !size() ) termin( "pop_front size==%d\n", size() );
		l++;
		if( l >= db.size() ) l -= db.size();
	}
	void expandsize()
	{
		vector<char> tdb;
		tdb.resize( db.size() * 2 );
		for( int i = 0; i < size(); i++ ) tdb[ i ] = ( *this )[ i ];
		int sz = size();
		l = 0, r = sz - 1;
		db = tdb;
	}
	void push_back( char v )
	{
		if( size() + 1 == db.size() ) expandsize();
		r++; r %= db.size();
		db[ r ] = v;
	}
	void push_front( char v )
	{
		if( size() + 1 == db.size() ) expandsize();
		l--; if( l < 0 ) l += db.size();
		db[ l ] = v;
	}
	char front()
	{
		if( !size() ) termin( "front size==%d\n", size() );
		return db[ l ];
	}
	char back()
	{
		if( !size() ) termin( "back size==%d\n", size() );
		return db[ r ];
	}
	char &operator[] ( int idx )
	{
		if( idx < 0 || idx >= size() ) termin( "idx==%d size()==%d\n", idx, size() );
		return db[ ( l + idx ) % db.size() ];
	}
};
void show( Deq a ) { for( int i = a.size() - 1; i >= 0; i-- ) printf( "%d", a[ i ] ); }
bool Nolarger( Deq &d1, Deq &d2 )//<=
{
	if( d1.size() != d2.size() ) return d1.size() < d2.size();
	for( int i = d1.size() - 1; i >= 0; i-- ) if( d1[ i ] != d2[ i ] ) return d1[ i ] < d2[ i ];
	return true;
}
void castdigit( Deq &to, Deq &from )
{
	if( !from.size() ) to.push_front( 0 );
	else to.push_front( from.back() ), from.pop_back();
	while( to.size()&&!to.back() ) to.pop_back();
}
void Add( Deq &d, char carry )
{
	if( carry < 0 || carry > 9 ) termin( "Add: carry=%d\n", carry );
	for( int i = 0; i < d.size(); i++ )
	{
		d[ i ] += carry; carry = 0;
		if( !d[ i ] / 10 ) break;
		carry = d[ i ] / 10;
		d[ i ] %= 10;
	}
	if( carry ) d.push_back( carry );
}
void Mul( Deq &d, char v )
{
	if( v < 0 || v > 9 ) termin( "Mul: v=%d\n", v );
	char carry = 0;
	for( int i = 0; i < d.size(); i++ )
	{
		d[ i ] *= v;
		d[ i ] += carry;
		carry = d[ i ] / 10;
		d[ i ] %= 10;
	}
	if( carry ) d.push_back( carry );
	while( d.size()&&!d.back() ) d.pop_back();
}
void Sub( Deq &d, Deq &m )
{
	if( !Nolarger( m, d ) )
	{
		show( d ); puts( "" );
		show( m ); puts( "" );
		termin( "Sub: m>d\n" );
	}
	char carry = 0;
	Deq td = d, tm = m;
	for( int i = 0; carry || i < m.size(); i++ )
	{
		if( i == d.size() )
		{
			puts( "" );
			show( d ); puts( "" ); show( m ); puts( "" );
			show( td ); puts( "" ); show( tm ); puts( "" );
			termin( "carry=%d d.size()=%d m.size()=%d\n", carry, d.size(), m.size() );
		}
		if( i < m.size() ) d[ i ] -= m[ i ];
		d[ i ] += carry; carry = 0;
		while( d[ i ] < 0 ) d[ i ] += 10, carry--;
	}
	if( carry ) termin( "carry=%d\n", carry );
	while( d.size()&&!d.back() ) d.pop_back();
}
Deq Addmul( Deq d, char v )
{
	Add( d, v );
	Mul( d, v );
	return d;
}
void solve()
{
	printf( "%d ", N );
	Deq n, add, sub, tmp;
	while( N )
	{
		n.push_back( N % 10 );
		N /= 10;
	}
	if( !n.size() ) termin( "!n.size()\n" );
	castdigit( sub, n );
	if( n.size() % 2 ) castdigit( sub, n );
	char v, now = -1, cnt = 0, r, m;
	int pos = 0;
	while( 1 )
	{
		add.push_front( 0 );
		v = 0, r = 9;
		while( r > v )
		{
			m = ( v + r + 1 ) >> 1;
			if( Nolarger( tmp = Addmul( add, m ), sub ) ) v = m;
			else r = m - 1;
		}
		Sub( sub, tmp = Addmul( add, v ) );
		Add( add, v ), Add( add, v );
		if( v == now ) cnt++;
		else now = v, cnt = 1;
		pos++;
		if( cnt == 3 )
		{
			printf( "%d %d\n", pos - 3, now );
			return;
		}
		castdigit( sub, n );
		castdigit( sub, n );
	}
}
int main()
{
	while( scanf( "%d", &N ) == 1 && N )
	{
		solve();
	}
	return 0;
}

Post Reply

Return to “Volume 111 (11100-11199)”