11120 - Very Funny Mr. Feynman

mrahman · 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.

sclo · 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 · 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.

little joey · 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 · 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 · Post by **mysword** » Thu Jan 04, 2007 3:06 pm

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

mrahman · 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

Output:

Code: Select all

Hope this will help.

fsps60312 · 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

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 · 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.

uDebug · 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.

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

Some cases.

Input:

Code: Select all

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

fsps60312 · 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

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;
}

OJ Board

11120 - Very Funny Mr. Feynman

11120 - Very Funny Mr. Feynman

Re: 11120 - Very Funny Mr. Feynman

Re: 11120 - Very Funny Mr. Feynman

Re: 11120 - Very Funny Mr. Feynman

Re: 11120 - Very Funny Mr. Feynman

Re: 11120 - Very Funny Mr. Feynman