10198 - Counting
Moderator: Board moderators
10198 Counting
Can anyone tell me how to solve this?
-
Larry
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
It's not too hard to see the recurrence relations.. and once you got that, you can easily solve it using DP...
This is like a really simple textbook counting example. It extends how you would do fib sequence.. so maybe you should consult a textbook or online... if you still have no idea, feel free to message me..
This is like a really simple textbook counting example. It extends how you would do fib sequence.. so maybe you should consult a textbook or online... if you still have no idea, feel free to message me..
-
Dmytro Chernysh
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
-
Dominik Michniewski
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
Could you tell me how you get this recurency ?
I try to find this recurrency , but I fails ... and I think about more complicated version of this
Best regards
DM
I try to find this recurrency , but I fails ... and I think about more complicated version of this
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
Daniel Chia
- New poster
- Posts: 12
- Joined: Mon Jul 29, 2002 3:04 pm
- Contact:
This might be a little late, but i just thought i'll try and explain his algo..
let f(n) denote the no of ways to make numbers with the sum n. The number of ways to make n is the same as the number of ways to make n-1 + no of ways to make n-2 + no of ways to make + no of ways to make n-3 + no of ways to make n-4. However since 4 = 1, it is basically
f(n) = 2 * f(n-1) + f(n-2) + f(n-3)
let f(n) denote the no of ways to make numbers with the sum n. The number of ways to make n is the same as the number of ways to make n-1 + no of ways to make n-2 + no of ways to make + no of ways to make n-3 + no of ways to make n-4. However since 4 = 1, it is basically
f(n) = 2 * f(n-1) + f(n-2) + f(n-3)
-
ravingavin
- New poster
- Posts: 21
- Joined: Sun Sep 14, 2003 11:44 pm
- Location: USA
- Contact:
10198
Well, I've got the recursion function going for this problem, and my formula works really well. I saved all the values of f(n) into an array which works out or the values of n >0 and n<1000 before the user inputs the number, so when n is called in the recursion function, it calls the array, array[n]. I found this method to be dramatically faster than calculating the value on-the-fly.
I'm still suffering problems. When I type in the number 999, the output number is something like 384 digits long. Because there are such large numbers, it takes a while for the computer to calculate every value for n.
How would I speed up my program. I don't know much about data structures, so any help/direction would be greatly appreciated. I always get time limit exceeded:(
I'm so close, but no cigar!
Thanks
GCS
I'm still suffering problems. When I type in the number 999, the output number is something like 384 digits long. Because there are such large numbers, it takes a while for the computer to calculate every value for n.
How would I speed up my program. I don't know much about data structures, so any help/direction would be greatly appreciated. I always get time limit exceeded:(
I'm so close, but no cigar!
Thanks
GCS
10198 - Counting
I'm trying to solve the problem n
-
chervensky
- New poster
- Posts: 4
- Joined: Wed Oct 22, 2003 9:11 pm
quick help
hey
use an array saveF[10001], to save already the computed values of f(k)
otherwise you compute the same values over and over, and it is veeeery slow
use an array saveF[10001], to save already the computed values of f(k)
otherwise you compute the same values over and over, and it is veeeery slow
-
chervensky
- New poster
- Posts: 4
- Joined: Wed Oct 22, 2003 9:11 pm
big nubmers
also, there are going to be very big numbers (being 64 bit ) after k becomes 70-80
nick
nick
The recurrence of 10198
Hy Dmytro_Chernysh,
I would like to know if you got Accepted using this recurence:
f[1]:=2;
f[2]:=5;
f[3]:=13;
f[n]:=2*f[n-1]+f[n-2]+f[n-3].
I'm asking because I tried do use it, but I got WA.
Maybe, I am having problems like ravingavin. The numbers became very big and their representation can be done in a wrong way. My code is in C++. What can I do to solve this problem?
Besides that, I have a doubt:
when n=4, the output is 2 or 33?
And, can you send me some input examples?
Thanks,
Charlla
--------
My code is:
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
//#include<io.h>
unsigned long vetor_T[1000];
int cont;
void calcula()
{
vetor_T[0]=2;
vetor_T[1]=5;
vetor_T[2]=13;
while (cont<1000)
{
vetor_T[cont]=2*vetor_T[cont-1]+vetor_T[cont-2]+vetor_T[cont-3];
cont++;
}
}
int main()
{
int n;
cont=3;
calcula();
#ifndef ONLINE_JUDGE
close (0); open ("DATA.IN", O_RDONLY);
close (1); open ("DATA.OUT", O_WRONLY | O_CREAT, 0600);
#endif
while (scanf ("%d",&n)>0){
printf ("%lu\n", vetor_T[n-1]);
}
return 0;
}
And the numbers I tried (my input) are:
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
And output for those numbers were:
2
5
13
2
84
214
545
1388
3535
9003
22929
58396
148724
378773
964666
2456829
6257097
15935689
40585304
103363394
263247781
670444260
1707499695
53724135
2485392225
2437040984
3118231032
2568960681
2103258786
1303774693
2984801557
786702001
1567012956
2610562174
3279872009
2147384556
1595268703
27859379
3798372017
629937524
791139148
1715620541
557350458
3621460605
925957617
1735759001
3723968928
1519719882
4204200397
767187716
2963328415
2308110351
4051769537
490075952
3045064496
2042039889
3324252930
3145675653
3067709533
4015413057
1359309412
1211806822
3503368817
987919276
2396046895
693447291
475893457
4041281100
661968356
1546143973
3500570106
619317949
1990382681
3805686121
1631138280
468410770
2078678645
1961939044
2176000207
4097650807
3743306273
875361672
1001745832
2327192313
2236524834
3507020517
2987823589
3129257937
4163425388
1559030414
1820809561
774140332
633153343
3861256579
539872241
1279187108
2664535740
2853163533
1060115322
3342962621
2009269505
4126649657
720629552
3282210970
2821766557
1056439044
3921888319
3132047647
2652488065
3768977504
437588832
3001675937
1619983618
2384264709
800254381
1309789793
1509131380
833339638
190633153
2723737324
2176480143
2972363467
2255009809
1068928636
3070263252
874530357
1593285306
2836396925
3845642217
3531032073
859201400
505142498
1105551173
3575446244
171651567
729333255
910797025
2722578872
2790320728
624082761
2466097826
4051631845
2603509685
3134814449
39868540
1523093918
1925903529
1119802220
1393634591
1538007635
1294484785
1225644500
988814124
202790237
2620039098
2136715261
2801292561
1769404889
4181850304
49496170
1755280237
3446939652
108721119
1124694831
1510083137
4253582224
2552007824
2277746417
2771148290
1782116229
23192573
304682369
2414673540
862254726
148898065
3574724396
3865634287
2864956443
285369681
3006362796
573117124
142999429
3865478778
4152106813
3722757241
2578198185
146358536
2298705202
3026999829
4204096100
848995343
339152023
1436428193
4061003752
1307653128
3817770905
119296802
1069050341
1780201093
453782033
3756815500
1157679534
2230989305
786539052
666779647
56120355
1565559409
3854018820
739782812
2604176557
1212220154
1473432381
2468294177
3327273593
2006339152
1218311482
3475268413
1585252868
3569118335
3608823359
3782083329
1857206464
2515385024
2080125249
4237874690
186357765
2395748173
625794209
3833694356
2098996502
67546977
1772817516
1417211215
379819627
3949667985
1106432220
2247384756
960935125
980719930
874792445
3691239945
648057673
1567180440
3178691202
4277653221
416276196
3993929519
4091853863
4003978849
3208839192
1628609208
1880101865
7717538
3524146149
346177109
4224217905
3728824476
3438109374
1944359241
2465717740
1723969503
3563048691
2725850033
2148783668
1996531468
277762045
405871930
3086037373
2560741425
23457561
1398726624
1086684938
3595554061
1086585092
2560441887
1213088335
1778236353
3035035632
471461360
1461227409
2133984514
1905690501
3111625629
1672991681
4068332196
36379814
1519116209
2847977132
2956482991
1690124731
594774993
1541190412
1072313252
4280591909
2584752890
1932476349
2140362905
208020457
193912872
2736209106
1579384245
1793923172
3608472399
2000317623
813096225
2940015176
103509608
3960130617
2373851426
221408485
2481831717
3263956049
641217708
2733255886
781750937
643008172
506055871
2436870851
1727838449
2103636324
4077014652
3395569485
86888058
3351392957
1595308865
2333931449
1024630128
1683533274
2430660829
3274517764
2073295039
1261834079
3576513665
1898221856
44856864
1269481953
187075330
1688489477
538568941
2952702689
3837496500
2576330038
3352924673
234773996
2103835407
3500402187
749479185
2808228668
1276404116
1815548789
3420763066
1343544445
3628433449
3431239817
3244522936
663817250
3708429957
2735265508
1252843631
359448135
412038113
2436367992
1349254936
1251948681
1994552994
2295342309
3542218997
2784398705
2816424124
3369531358
3749950953
800955500
131458719
518856595
1970127409
295602836
3080189676
4131142301
3048142522
422715133
3729747793
2340418649
243365632
2261930410
2812677805
3835684356
4156042335
2075544943
3552881985
452449360
2238358352
4187080753
2475034626
2785573765
3643328317
3957330433
1458661060
1928046278
682149457
456038956
3522273647
3887768411
3163914833
852969836
167688324
57294021
1135246202
2495474749
1888522425
3112798505
2019659592
450705522
1738901845
1653201508
1201043087
1499222231
1557721761
1520741544
1803459784
2390415577
3810065186
3224071141
4058688453
2266611345
3226047692
4187460590
982678329
788930348
2453032319
2382706019
3712407409
3670618564
551448668
4190956013
4014044666
4180559421
3681217633
2672137465
321150096
2700687994
4099696253
2631296004
3473041663
792173695
3393717761
2462716288
521389440
2604245633
3897629698
2330959877
2573860493
2786375969
1887637716
545577302
1470200993
1078649708
4173077711
2305071531
1271935889
432086428
146212980
1996448277
276228666
2695118589
3367946825
1117306313
4002710744
3900740034
36595237
3681673956
2710748591
549831783
3197118817
1064883416
1581750136
3130535209
317769378
1052856805
1259050901
3888727985
1499429084
3851669758
206594697
1469320940
2701939039
2784826419
1150978225
3493754612
2333379276
721556797
2975280186
415561853
232993393
3856828825
4067245600
3634378826
2307930189
3727550212
512507551
2765528207
1181179585
1345427632
2342595760
2916831441
931751682
2827963269
914575069
1293897793
2035366628
1984238822
3002774769
1435220396
3562487087
2973034747
2353842385
2653272012
2043486564
504152933
1410097146
1072866493
4059983065
2012995177
568905320
2915821586
4118576373
3131945060
413386191
3782326519
2520049697
645877512
3299163944
1174320505
1998715170
4175947493
2934996069
3454720209
1135482092
70745870
436726745
2079681452
371868223
3260144643
381904369
100854308
3843757628
3875306637
3105290618
1044743613
480149889
815366713
3155626928
3311803162
2004665373
1886826244
500186431
596897183
3580807041
3963730400
3515230432
1690096417
2269219074
1153830405
1972009005
3072100193
680105204
2109352310
3675942721
1551408364
298177167
1528738123
612094481
3051104252
3948073812
2969411765
53099706
2728717693
4184979561
2561841929
3447446520
756812642
3227946437
2070217444
3830226671
73715335
1752907489
3114789688
3761234904
3800232393
1591587490
2154707685
1111300661
1673929201
2318899452
3128061470
1659017001
175060332
842231839
3518541011
3759406897
3289652052
972350124
403824605
774684090
2925542909
2734627217
579546841
2524296512
4067799786
2649508333
3301178372
434762975
2525245359
196497473
3353003280
837814800
930163057
1756176898
985364357
362101373
3465744001
3983986436
3205883654
976595857
553127212
993766639
3517256347
4286439249
198999596
3906727492
3708959237
2933710970
598206781
3544116473
2030216105
3907788168
505007026
2653051029
1128962660
1121016079
1729078551
1413168545
1381464424
1610208648
1720082969
2136871714
3309067749
1885155589
626316049
2151888140
2520280622
3523798137
3129830444
3713805055
1196336803
646374513
1907923588
1363591196
986513197
949573882
4249252157
1844656801
298205049
2395351760
2638598074
3675785661
3795586564
1020654975
922747583
2366769409
2381974080
3758497856
3675804609
607179266
58726405
105469389
876844449
1917884692
523115926
3840960993
1532988012
3135085647
3054185707
2186510481
1972357724
595477044
1054854997
382577466
2415486973
1973439113
2449975369
698942232
1526331650
1906613605
1743533796
2625045551
310303911
694219873
28821912
1062167608
2847377001
2490776226
301162469
1645510869
1787993137
1227692316
1593921342
1908560841
2343768044
3895050975
3452496243
258909617
3570399156
2262269580
4058880637
1065528122
4157239165
553985201
2035770393
192830560
2975416714
3884467085
2347246852
2964442911
3570665167
3863085505
1376377200
1596570480
4137636369
2658285826
2460843909
3127675421
2784545985
2567676708
2457640230
1677568561
4085486764
3716247727
310648891
4128064977
3693091980
3234963236
1406181541
1150483706
2647144893
3555987737
2319669481
2252537000
1790796626
3858832437
3171063908
3401822287
948639031
4175196961
4110920648
460775400
617733817
1512196386
4102901989
1745799589
516762961
2587260204
3142115662
798319897
3031048364
1412597695
2359596355
572904177
623035108
4178570748
963146189
2432930938
1417644221
1936398273
3428404409
1620916720
16701530
787756893
3213132036
2935755199
1282464735
123882113
171016864
1748380576
3791660129
912783106
3070639621
2255787885
4200031201
841588020
3844027830
4139740289
80194540
3849189903
3328380043
1996209937
2580055228
1894765844
4070829557
4026545594
1133784701
1775009961
120415625
3149625912
3899710114
2479527173
3418455780
331246959
2265509575
3985754593
1978331128
1617991832
610134793
521625250
3271377125
3379546997
1962161777
1985313084
722400350
1097308265
607362668
3034433951
3478571539
2009005105
1941081108
779804268
1214727453
855372986
3705277693
890721233
2047125849
100316032
3138479146
4129432877
2907726340
198462815
3139117551
794489665
631592400
901824720
3229731505
3697912834
2937447301
4212604349
2175666945
2911450948
3621238598
3739660497
1127108652
1025181807
2622165467
3101654097
1260720876
3950294020
3673028421
3967137146
2672694845
100653369
2546171433
3570723784
1198337778
4218603477
321366628
1764707215
3774417239
1044973729
3334104616
2897665608
1584474969
810785570
1808744421
1717782085
1760126865
2751812940
391600238
1000172985
848791852
3089356927
3732711395
2813636977
3859407684
1380261852
843633773
2631969786
3192867901
1271404769
4072679929
4019697936
498578682
499600637
1222510596
3443200511
18577663
407899137
4277576448
391695104
1173898497
2722101250
2714828805
735722765
2613408289
87433556
3523998166
1158903585
1634271596
3656477647
1516195883
4028173713
344119068
1937640436
3952606357
1597037626
494387453
2243451593
2283360969
3009593688
1956065346
615150757
1900993252
2078235311
2377647335
144588641
450092632
3422421240
3144556457
1571692194
1120427493
2662136341
3721425073
2635479388
3064585598
3896141065
607445228
3880649823
3674951347
3248063153
1166825588
666731084
1453383613
445356602
3010827901
3625428721
2117107353
2280536736
1713674954
3530026701
2464330500
1582428063
569278735
890348737
3932404272
734501424
1996788561
70548226
2872386437
3517142365
1387284801
574163812
1757787494
1182056305
401096620
3742037039
477292411
802751185
1529864524
44805348
2422226405
2124155386
2420375229
797197657
1843958633
2610522856
3567234706
2999016309
3585855588
853060303
3996025207
3841031713
3941214344
2834583720
566511609
3613853986
2038868709
3963135717
694092241
3095221612
2257736590
4009819737
487695788
2947980607
1803542147
2747793393
1657174948
3570718140
2956470029
2550898554
3039050685
2995535361
2991085369
3426822192
4250330522
I would like to know if you got Accepted using this recurence:
f[1]:=2;
f[2]:=5;
f[3]:=13;
f[n]:=2*f[n-1]+f[n-2]+f[n-3].
I'm asking because I tried do use it, but I got WA.
Maybe, I am having problems like ravingavin. The numbers became very big and their representation can be done in a wrong way. My code is in C++. What can I do to solve this problem?
Besides that, I have a doubt:
when n=4, the output is 2 or 33?
And, can you send me some input examples?
Thanks,
Charlla
--------
My code is:
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
//#include<io.h>
unsigned long vetor_T[1000];
int cont;
void calcula()
{
vetor_T[0]=2;
vetor_T[1]=5;
vetor_T[2]=13;
while (cont<1000)
{
vetor_T[cont]=2*vetor_T[cont-1]+vetor_T[cont-2]+vetor_T[cont-3];
cont++;
}
}
int main()
{
int n;
cont=3;
calcula();
#ifndef ONLINE_JUDGE
close (0); open ("DATA.IN", O_RDONLY);
close (1); open ("DATA.OUT", O_WRONLY | O_CREAT, 0600);
#endif
while (scanf ("%d",&n)>0){
printf ("%lu\n", vetor_T[n-1]);
}
return 0;
}
And the numbers I tried (my input) are:
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
And output for those numbers were:
2
5
13
2
84
214
545
1388
3535
9003
22929
58396
148724
378773
964666
2456829
6257097
15935689
40585304
103363394
263247781
670444260
1707499695
53724135
2485392225
2437040984
3118231032
2568960681
2103258786
1303774693
2984801557
786702001
1567012956
2610562174
3279872009
2147384556
1595268703
27859379
3798372017
629937524
791139148
1715620541
557350458
3621460605
925957617
1735759001
3723968928
1519719882
4204200397
767187716
2963328415
2308110351
4051769537
490075952
3045064496
2042039889
3324252930
3145675653
3067709533
4015413057
1359309412
1211806822
3503368817
987919276
2396046895
693447291
475893457
4041281100
661968356
1546143973
3500570106
619317949
1990382681
3805686121
1631138280
468410770
2078678645
1961939044
2176000207
4097650807
3743306273
875361672
1001745832
2327192313
2236524834
3507020517
2987823589
3129257937
4163425388
1559030414
1820809561
774140332
633153343
3861256579
539872241
1279187108
2664535740
2853163533
1060115322
3342962621
2009269505
4126649657
720629552
3282210970
2821766557
1056439044
3921888319
3132047647
2652488065
3768977504
437588832
3001675937
1619983618
2384264709
800254381
1309789793
1509131380
833339638
190633153
2723737324
2176480143
2972363467
2255009809
1068928636
3070263252
874530357
1593285306
2836396925
3845642217
3531032073
859201400
505142498
1105551173
3575446244
171651567
729333255
910797025
2722578872
2790320728
624082761
2466097826
4051631845
2603509685
3134814449
39868540
1523093918
1925903529
1119802220
1393634591
1538007635
1294484785
1225644500
988814124
202790237
2620039098
2136715261
2801292561
1769404889
4181850304
49496170
1755280237
3446939652
108721119
1124694831
1510083137
4253582224
2552007824
2277746417
2771148290
1782116229
23192573
304682369
2414673540
862254726
148898065
3574724396
3865634287
2864956443
285369681
3006362796
573117124
142999429
3865478778
4152106813
3722757241
2578198185
146358536
2298705202
3026999829
4204096100
848995343
339152023
1436428193
4061003752
1307653128
3817770905
119296802
1069050341
1780201093
453782033
3756815500
1157679534
2230989305
786539052
666779647
56120355
1565559409
3854018820
739782812
2604176557
1212220154
1473432381
2468294177
3327273593
2006339152
1218311482
3475268413
1585252868
3569118335
3608823359
3782083329
1857206464
2515385024
2080125249
4237874690
186357765
2395748173
625794209
3833694356
2098996502
67546977
1772817516
1417211215
379819627
3949667985
1106432220
2247384756
960935125
980719930
874792445
3691239945
648057673
1567180440
3178691202
4277653221
416276196
3993929519
4091853863
4003978849
3208839192
1628609208
1880101865
7717538
3524146149
346177109
4224217905
3728824476
3438109374
1944359241
2465717740
1723969503
3563048691
2725850033
2148783668
1996531468
277762045
405871930
3086037373
2560741425
23457561
1398726624
1086684938
3595554061
1086585092
2560441887
1213088335
1778236353
3035035632
471461360
1461227409
2133984514
1905690501
3111625629
1672991681
4068332196
36379814
1519116209
2847977132
2956482991
1690124731
594774993
1541190412
1072313252
4280591909
2584752890
1932476349
2140362905
208020457
193912872
2736209106
1579384245
1793923172
3608472399
2000317623
813096225
2940015176
103509608
3960130617
2373851426
221408485
2481831717
3263956049
641217708
2733255886
781750937
643008172
506055871
2436870851
1727838449
2103636324
4077014652
3395569485
86888058
3351392957
1595308865
2333931449
1024630128
1683533274
2430660829
3274517764
2073295039
1261834079
3576513665
1898221856
44856864
1269481953
187075330
1688489477
538568941
2952702689
3837496500
2576330038
3352924673
234773996
2103835407
3500402187
749479185
2808228668
1276404116
1815548789
3420763066
1343544445
3628433449
3431239817
3244522936
663817250
3708429957
2735265508
1252843631
359448135
412038113
2436367992
1349254936
1251948681
1994552994
2295342309
3542218997
2784398705
2816424124
3369531358
3749950953
800955500
131458719
518856595
1970127409
295602836
3080189676
4131142301
3048142522
422715133
3729747793
2340418649
243365632
2261930410
2812677805
3835684356
4156042335
2075544943
3552881985
452449360
2238358352
4187080753
2475034626
2785573765
3643328317
3957330433
1458661060
1928046278
682149457
456038956
3522273647
3887768411
3163914833
852969836
167688324
57294021
1135246202
2495474749
1888522425
3112798505
2019659592
450705522
1738901845
1653201508
1201043087
1499222231
1557721761
1520741544
1803459784
2390415577
3810065186
3224071141
4058688453
2266611345
3226047692
4187460590
982678329
788930348
2453032319
2382706019
3712407409
3670618564
551448668
4190956013
4014044666
4180559421
3681217633
2672137465
321150096
2700687994
4099696253
2631296004
3473041663
792173695
3393717761
2462716288
521389440
2604245633
3897629698
2330959877
2573860493
2786375969
1887637716
545577302
1470200993
1078649708
4173077711
2305071531
1271935889
432086428
146212980
1996448277
276228666
2695118589
3367946825
1117306313
4002710744
3900740034
36595237
3681673956
2710748591
549831783
3197118817
1064883416
1581750136
3130535209
317769378
1052856805
1259050901
3888727985
1499429084
3851669758
206594697
1469320940
2701939039
2784826419
1150978225
3493754612
2333379276
721556797
2975280186
415561853
232993393
3856828825
4067245600
3634378826
2307930189
3727550212
512507551
2765528207
1181179585
1345427632
2342595760
2916831441
931751682
2827963269
914575069
1293897793
2035366628
1984238822
3002774769
1435220396
3562487087
2973034747
2353842385
2653272012
2043486564
504152933
1410097146
1072866493
4059983065
2012995177
568905320
2915821586
4118576373
3131945060
413386191
3782326519
2520049697
645877512
3299163944
1174320505
1998715170
4175947493
2934996069
3454720209
1135482092
70745870
436726745
2079681452
371868223
3260144643
381904369
100854308
3843757628
3875306637
3105290618
1044743613
480149889
815366713
3155626928
3311803162
2004665373
1886826244
500186431
596897183
3580807041
3963730400
3515230432
1690096417
2269219074
1153830405
1972009005
3072100193
680105204
2109352310
3675942721
1551408364
298177167
1528738123
612094481
3051104252
3948073812
2969411765
53099706
2728717693
4184979561
2561841929
3447446520
756812642
3227946437
2070217444
3830226671
73715335
1752907489
3114789688
3761234904
3800232393
1591587490
2154707685
1111300661
1673929201
2318899452
3128061470
1659017001
175060332
842231839
3518541011
3759406897
3289652052
972350124
403824605
774684090
2925542909
2734627217
579546841
2524296512
4067799786
2649508333
3301178372
434762975
2525245359
196497473
3353003280
837814800
930163057
1756176898
985364357
362101373
3465744001
3983986436
3205883654
976595857
553127212
993766639
3517256347
4286439249
198999596
3906727492
3708959237
2933710970
598206781
3544116473
2030216105
3907788168
505007026
2653051029
1128962660
1121016079
1729078551
1413168545
1381464424
1610208648
1720082969
2136871714
3309067749
1885155589
626316049
2151888140
2520280622
3523798137
3129830444
3713805055
1196336803
646374513
1907923588
1363591196
986513197
949573882
4249252157
1844656801
298205049
2395351760
2638598074
3675785661
3795586564
1020654975
922747583
2366769409
2381974080
3758497856
3675804609
607179266
58726405
105469389
876844449
1917884692
523115926
3840960993
1532988012
3135085647
3054185707
2186510481
1972357724
595477044
1054854997
382577466
2415486973
1973439113
2449975369
698942232
1526331650
1906613605
1743533796
2625045551
310303911
694219873
28821912
1062167608
2847377001
2490776226
301162469
1645510869
1787993137
1227692316
1593921342
1908560841
2343768044
3895050975
3452496243
258909617
3570399156
2262269580
4058880637
1065528122
4157239165
553985201
2035770393
192830560
2975416714
3884467085
2347246852
2964442911
3570665167
3863085505
1376377200
1596570480
4137636369
2658285826
2460843909
3127675421
2784545985
2567676708
2457640230
1677568561
4085486764
3716247727
310648891
4128064977
3693091980
3234963236
1406181541
1150483706
2647144893
3555987737
2319669481
2252537000
1790796626
3858832437
3171063908
3401822287
948639031
4175196961
4110920648
460775400
617733817
1512196386
4102901989
1745799589
516762961
2587260204
3142115662
798319897
3031048364
1412597695
2359596355
572904177
623035108
4178570748
963146189
2432930938
1417644221
1936398273
3428404409
1620916720
16701530
787756893
3213132036
2935755199
1282464735
123882113
171016864
1748380576
3791660129
912783106
3070639621
2255787885
4200031201
841588020
3844027830
4139740289
80194540
3849189903
3328380043
1996209937
2580055228
1894765844
4070829557
4026545594
1133784701
1775009961
120415625
3149625912
3899710114
2479527173
3418455780
331246959
2265509575
3985754593
1978331128
1617991832
610134793
521625250
3271377125
3379546997
1962161777
1985313084
722400350
1097308265
607362668
3034433951
3478571539
2009005105
1941081108
779804268
1214727453
855372986
3705277693
890721233
2047125849
100316032
3138479146
4129432877
2907726340
198462815
3139117551
794489665
631592400
901824720
3229731505
3697912834
2937447301
4212604349
2175666945
2911450948
3621238598
3739660497
1127108652
1025181807
2622165467
3101654097
1260720876
3950294020
3673028421
3967137146
2672694845
100653369
2546171433
3570723784
1198337778
4218603477
321366628
1764707215
3774417239
1044973729
3334104616
2897665608
1584474969
810785570
1808744421
1717782085
1760126865
2751812940
391600238
1000172985
848791852
3089356927
3732711395
2813636977
3859407684
1380261852
843633773
2631969786
3192867901
1271404769
4072679929
4019697936
498578682
499600637
1222510596
3443200511
18577663
407899137
4277576448
391695104
1173898497
2722101250
2714828805
735722765
2613408289
87433556
3523998166
1158903585
1634271596
3656477647
1516195883
4028173713
344119068
1937640436
3952606357
1597037626
494387453
2243451593
2283360969
3009593688
1956065346
615150757
1900993252
2078235311
2377647335
144588641
450092632
3422421240
3144556457
1571692194
1120427493
2662136341
3721425073
2635479388
3064585598
3896141065
607445228
3880649823
3674951347
3248063153
1166825588
666731084
1453383613
445356602
3010827901
3625428721
2117107353
2280536736
1713674954
3530026701
2464330500
1582428063
569278735
890348737
3932404272
734501424
1996788561
70548226
2872386437
3517142365
1387284801
574163812
1757787494
1182056305
401096620
3742037039
477292411
802751185
1529864524
44805348
2422226405
2124155386
2420375229
797197657
1843958633
2610522856
3567234706
2999016309
3585855588
853060303
3996025207
3841031713
3941214344
2834583720
566511609
3613853986
2038868709
3963135717
694092241
3095221612
2257736590
4009819737
487695788
2947980607
1803542147
2747793393
1657174948
3570718140
2956470029
2550898554
3039050685
2995535361
2991085369
3426822192
4250330522
Re: big nubmers
Hey,
How can I solve this problem??? I mean, what can I do when, after k becomes 70-80, and the numbers become very big (being 64 bit )????
Thanks,
Charla
--------------
My code is:
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include<io.h>
unsigned long vetor_T[1000];
int cont;
void calcula()
{
vetor_T[0]=2;
vetor_T[1]=5;
vetor_T[2]=13;
while (cont<1000)
{
vetor_T[cont]=2*vetor_T[cont-1]+vetor_T[cont-2]+vetor_T[cont-3];
cont++;
}
}
int main()
{
int n;
cont=3;
calcula();
#ifndef ONLINE_JUDGE
close (0); open ("DATA.IN", O_RDONLY);
close (1); open ("DATA.OUT", O_WRONLY | O_CREAT, 0600);
#endif
while (scanf ("%d",&n)>0){
printf ("%lu\n", vetor_T[n-1]);
}
return 0;
}
How can I solve this problem??? I mean, what can I do when, after k becomes 70-80, and the numbers become very big (being 64 bit )????
Thanks,
Charla
--------------
My code is:
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include<io.h>
unsigned long vetor_T[1000];
int cont;
void calcula()
{
vetor_T[0]=2;
vetor_T[1]=5;
vetor_T[2]=13;
while (cont<1000)
{
vetor_T[cont]=2*vetor_T[cont-1]+vetor_T[cont-2]+vetor_T[cont-3];
cont++;
}
}
int main()
{
int n;
cont=3;
calcula();
#ifndef ONLINE_JUDGE
close (0); open ("DATA.IN", O_RDONLY);
close (1); open ("DATA.OUT", O_WRONLY | O_CREAT, 0600);
#endif
while (scanf ("%d",&n)>0){
printf ("%lu\n", vetor_T[n-1]);
}
return 0;
}
-
Dmytro Chernysh
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
