## 147 - Dollars

Moderator: Board moderators

Aesthiri
New poster
Posts: 3
Joined: Sun Dec 01, 2002 5:02 am
Location: Sydney

### Re: clarify

M[j] = the total number of combinations that make up the value (i+1) * 5c, with denominations[j] as the maximum possible denomination used in those combinations (so it also includes the combinations consisting of only lesser denominations).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
When I try to run your program, it tells me that main is not public.

I did match it with my AC C program.. so I made it public and sent it to the judge, and it got AC.. =)

Aesthiri
New poster
Posts: 3
Joined: Sun Dec 01, 2002 5:02 am
Location: Sydney
Great, thanks!

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

### 147, I really cannot believe it!

I really don't understand why the judge says WA. can anybody help me?

[cpp]#include <iostream>
#include <memory>
using namespace std;
typedef unsigned long mytype;

const int nNumCoins = 0xb; // 11
const int nCoinsDenom[]= {10000,5000,2000,1000, 500, 200, 100, 50, 20, 10, 5};
const int nArraySize = 1001;
static mytype ulNumWays[nNumCoins][nArraySize];

int main();
mytype GetNumberOfWays(int nAmountNeeded,int depth);

int main()
{
double AmountInput;
int nAmountNeeded;
mytype ulCounter = 0;
memset((void *)ulNumWays,0,(sizeof(ulNumWays[0][0])*nArraySize*nNumCoins));

cout.flags(ios::right);
cout.setf(ios::fixed,ios::floatfield);

while(true)
{
cin>>AmountInput;
if(AmountInput == 0.0) break; // end of program
nAmountNeeded = (int)(100.0*AmountInput);
ulCounter = 0;
ulCounter = GetNumberOfWays(nAmountNeeded,0) ;

cout.precision(2);
cout.width(5);
cout<<AmountInput;
cout.precision(0);
cout.width(12);
cout<<ulCounter<<endl;

}
cout<<endl;

return 0;
}

mytype GetNumberOfWays(int nAmountNeeded,int depth)
{
int i, nMaxNumCoins2Take,nNewAmountNeeded,nTemp;
mytype ulCounter = 0;

if((nNumCoins - 1) == depth )
{
return 1;
}

nMaxNumCoins2Take = (!nAmountNeeded) ? 0 : (nAmountNeeded/nCoinsDenom[depth]);

for(i = 0; i <= nMaxNumCoins2Take; i ++)
{
nNewAmountNeeded = nAmountNeeded - i*nCoinsDenom[depth];
nTemp = nNewAmountNeeded/5;

ulNumWays[depth + 1][nTemp] = (ulNumWays[depth + 1][nTemp]) ?
ulNumWays[depth + 1][nTemp] : GetNumberOfWays(nNewAmountNeeded,depth + 1);

ulCounter+= ulNumWays[depth + 1][nTemp];
}

return ulCounter;
}

[/cpp]
Last edited by Experimenter on Fri Jun 13, 2003 11:09 am, edited 2 times in total.
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
I don't know maybe this is helpful. this is the output for my program
0.05 1
0.10 2
0.15 2
0.20 4
0.25 4
0.30 6
0.35 6
0.40 9
0.45 9
0.50 13
0.55 13
0.60 18
0.65 18
0.70 24
0.75 24
0.80 31
0.85 31
0.90 39
0.95 39
1.00 50
1.05 50
1.10 62
1.15 62
1.20 77
1.25 77
1.30 93
1.35 93
1.40 112
1.45 112
1.50 134
1.55 134
1.60 159
1.65 159
1.70 187
1.75 187
1.80 218
1.85 218
1.90 252
1.95 252
2.00 293
2.05 293
2.10 337
2.15 337
2.20 388
2.25 388
2.30 442
2.35 442
2.40 503
2.45 503
2.50 571
2.55 571
2.60 646
2.65 646
2.70 728
2.75 728
2.80 817
2.85 817
2.90 913
2.95 913
3.00 1022
3.05 1022
3.10 1138
3.15 1138
3.20 1267
3.25 1267
3.30 1403
3.35 1403
3.40 1552
3.45 1552
3.50 1714
3.55 1714
3.60 1889
3.65 1889
3.70 2077
3.75 2077
3.80 2278
3.85 2278
3.90 2492
3.95 2492
4.00 2728
4.05 2728
4.10 2977
4.15 2977
4.20 3248
4.25 3248
4.30 3532
4.35 3532
4.40 3838
4.45 3838
4.50 4166
4.55 4166
4.60 4516
4.65 4516
4.70 4888
4.75 4888
4.80 5282
4.85 5282
4.90 5698
4.95 5698
5.00 6149
5.05 6149
5.10 6622
5.15 6622
5.20 7130
5.25 7130
5.30 7660
5.35 7660
5.40 8225
5.45 8225
5.50 8825
5.55 8825
5.60 9460
5.65 9460
5.70 10130
5.75 10130
5.80 10835
5.85 10835
5.90 11575
5.95 11575
6.00 12368
6.05 12368
6.10 13196
6.15 13196
6.20 14077
6.25 14077
6.30 14993
6.35 14993
6.40 15962
6.45 15962
6.50 16984
6.55 16984
6.60 18059
6.65 18059
6.70 19187
6.75 19187
6.80 20368
6.85 20368
6.90 21602
6.95 21602
7.00 22913
7.05 22913
7.10 24277
7.15 24277
7.20 25718
7.25 25718
7.30 27212
7.35 27212
7.40 28783
7.45 28783
7.50 30431
7.55 30431
7.60 32156
7.65 32156
7.70 33958
7.75 33958
7.80 35837
7.85 35837
7.90 37793
7.95 37793
8.00 39857
8.05 39857
8.10 41998
8.15 41998
8.20 44247
8.25 44247
8.30 46573
8.35 46573
8.40 49007
8.45 49007
8.50 51549
8.55 51549
8.60 54199
8.65 54199
8.70 56957
8.75 56957
8.80 59823
8.85 59823
8.90 62797
8.95 62797
9.00 65918
9.05 65918
9.10 69147
9.15 69147
9.20 72523
9.25 72523
9.30 76007
9.35 76007
9.40 79638
9.45 79638
9.50 83416
9.55 83416
9.60 87341
9.65 87341
9.70 91413
9.75 91413
9.80 95632
9.85 95632
9.90 99998
9.95 99998
10.00 104561
10.05 104561
10.10 109271
10.15 109271
10.20 114178
10.25 114178
10.30 119232
10.35 119232
10.40 124483
10.45 124483
10.50 129931
10.55 129931
10.60 135576
10.65 135576
10.70 141418
10.75 141418
10.80 147457
10.85 147457
10.90 153693
10.95 153693
11.00 160188
11.05 160188
11.10 166880
11.15 166880
11.20 173831
11.25 173831
11.30 180979
11.35 180979
11.40 188386
11.45 188386
11.50 196052
11.55 196052
11.60 203977
11.65 203977
11.70 212161
11.75 212161
11.80 220604
11.85 220604
11.90 229306
11.95 229306
12.00 238344
12.05 238344
12.10 247641
12.15 247641
12.20 257274
12.25 257274
12.30 267166
12.35 267166
12.40 277394
12.45 277394
12.50 287958
12.55 287958
12.60 298858
12.65 298858
12.70 310094
12.75 310094
12.80 321666
12.85 321666
12.90 333574
12.95 333574
13.00 345911
13.05 345911
13.10 358584
13.15 358584
13.20 371686
13.25 371686
13.30 385124
13.35 385124
13.40 398991
13.45 398991
13.50 413287
13.55 413287
13.60 428012
13.65 428012
13.70 443166
13.75 443166
13.80 458749
13.85 458749
13.90 474761
13.95 474761
14.00 491314
14.05 491314
14.10 508296
14.15 508296
14.20 525819
14.25 525819
14.30 543771
14.35 543771
14.40 562264
14.45 562264
14.50 581298
14.55 581298
14.60 600873
14.65 600873
14.70 620989
14.75 620989
14.80 641646
14.85 641646
14.90 662844
14.95 662844
15.00 684717
15.05 684717
15.10 707131
15.15 707131
15.20 730220
15.25 730220
15.30 753850
15.35 753850
15.40 778155
15.45 778155
15.50 803135
15.55 803135
15.60 828790
15.65 828790
15.70 855120
15.75 855120
15.80 882125
15.85 882125
15.90 909805
15.95 909805
16.00 938319
16.05 938319
16.10 967508
16.15 967508
16.20 997531
16.25 997531
16.30 1028229
16.35 1028229
16.40 1059761
16.45 1059761
16.50 1092127
16.55 1092127
16.60 1125327
16.65 1125327
16.70 1159361
16.75 1159361
16.80 1194229
16.85 1194229
16.90 1229931
16.95 1229931
17.00 1266654
17.05 1266654
17.10 1304211
17.15 1304211
17.20 1342789
17.25 1342789
17.30 1382201
17.35 1382201
17.40 1422634
17.45 1422634
17.50 1464088
17.55 1464088
17.60 1506563
17.65 1506563
17.70 1550059
17.75 1550059
17.80 1594576
17.85 1594576
17.90 1640114
17.95 1640114
18.00 1686891
18.05 1686891
18.10 1734689
18.15 1734689
18.20 1783726
18.25 1783726
18.30 1833784
18.35 1833784
18.40 1885081
18.45 1885081
18.50 1937617
18.55 1937617
18.60 1991392
18.65 1991392
18.70 2046406
18.75 2046406
18.80 2102659
18.85 2102659
18.90 2160151
18.95 2160151
19.00 2219134
19.05 2219134
19.10 2279356
19.15 2279356
19.20 2341069
19.25 2341069
19.30 2404021
19.35 2404021
19.40 2468464
19.45 2468464
19.50 2534398
19.55 2534398
19.60 2601823
19.65 2601823
19.70 2670739
19.75 2670739
19.80 2741146
19.85 2741146
19.90 2813044
19.95 2813044
20.00 2886726
20.05 2886726
20.10 2961899
20.15 2961899
20.20 3038856
20.25 3038856
20.30 3117304
20.35 3117304
20.40 3197536
20.45 3197536
20.50 3279552
20.55 3279552
20.60 3363352
20.65 3363352
20.70 3448936
20.75 3448936
20.80 3536304
20.85 3536304
20.90 3625456
20.95 3625456
21.00 3716729
21.05 3716729
21.10 3809786
21.15 3809786
21.20 3904964
21.25 3904964
21.30 4001926
21.35 4001926
21.40 4101009
21.45 4101009
21.50 4202213
21.55 4202213
21.60 4305538
21.65 4305538
21.70 4410984
21.75 4410984
21.80 4518551
21.85 4518551
21.90 4628239
21.95 4628239
22.00 4740436
22.05 4740436
22.10 4854754
22.15 4854754
22.20 4971581
22.25 4971581
22.30 5090529
22.35 5090529
22.40 5211986
22.45 5211986
22.50 5335952
22.55 5335952
22.60 5462427
22.65 5462427
22.70 5591411
22.75 5591411
22.80 5722904
22.85 5722904
22.90 5856906
22.95 5856906
23.00 5993859
23.05 5993859
23.10 6133321
23.15 6133321
23.20 6275734
23.25 6275734
23.30 6420656
23.35 6420656
23.40 6568529
23.45 6568529
23.50 6719353
23.55 6719353
23.60 6873128
23.65 6873128
23.70 7029854
23.75 7029854
23.80 7189531
23.85 7189531
23.90 7352159
23.95 7352159
24.00 7518241
24.05 7518241
24.10 7687274
24.15 7687274
24.20 7859761
24.25 7859761
24.30 8035199
24.35 8035199
24.40 8214091
24.45 8214091
24.50 8396437
24.55 8396437
24.60 8582237
24.65 8582237
24.70 8771491
24.75 8771491
24.80 8964199
24.85 8964199
24.90 9160361
24.95 9160361
25.00 9360548
25.05 9360548
25.10 9564189
25.15 9564189
25.20 9771855
25.25 9771855
25.30 9982975
25.35 9982975
25.40 10198120
25.45 10198120
25.50 10417290
25.55 10417290
25.60 10640485
25.65 10640485
25.70 10867705
25.75 10867705
25.80 11098950
25.85 11098950
25.90 11334220
25.95 11334220
26.00 11574161
26.05 11574161
26.10 11818127
26.15 11818127
26.20 12066764
26.25 12066764
26.30 12319426
26.35 12319426
26.40 12576759
26.45 12576759
26.50 12838763
26.55 12838763
26.60 13105438
26.65 13105438
26.70 13376784
26.75 13376784
26.80 13652801
26.85 13652801
26.90 13933489
26.95 13933489
27.00 14219576
27.05 14219576
27.10 14510334
27.15 14510334
27.20 14806491
27.25 14806491
27.30 15107319
27.35 15107319
27.40 15413546
27.45 15413546
27.50 15725172
27.55 15725172
27.60 16042197
27.65 16042197
27.70 16364621
27.75 16364621
27.80 16692444
27.85 16692444
27.90 17025666
27.95 17025666
28.00 17365104
28.05 17365104
28.10 17709941
28.15 17709941
28.20 18060994
28.25 18060994
28.30 18417446
28.35 18417446
28.40 18780114
28.45 18780114
28.50 19148998
28.55 19148998
28.60 19524098
28.65 19524098
28.70 19905414
28.75 19905414
28.80 20292946
28.85 20292946
28.90 20686694
28.95 20686694
29.00 21087571
29.05 21087571
29.10 21494664
29.15 21494664
29.20 21908886
29.25 21908886
29.30 22329324
29.35 22329324
29.40 22756891
29.45 22756891
29.50 23191587
29.55 23191587
29.60 23633412
29.65 23633412
29.70 24082366
29.75 24082366
29.80 24538449
29.85 24538449
29.90 25001661
29.95 25001661
30.00 25473024
30.05 25473024
30.10 25951516
30.15 25951516
30.20 26438159
30.25 26438159
30.30 26931931
30.35 26931931
30.40 27433854
30.45 27433854
30.50 27943928
30.55 27943928
30.60 28462153
30.65 28462153
30.70 28988529
30.75 28988529
30.80 29523056
30.85 29523056
30.90 30065734
30.95 30065734
31.00 30617701
31.05 30617701
31.10 31177819
31.15 31177819
31.20 31747226
31.25 31747226
31.30 32324784
31.35 32324784
31.40 32911631
31.45 32911631
31.50 33507767
31.55 33507767
31.60 34113192
31.65 34113192
31.70 34727906
31.75 34727906
31.80 35351909
31.85 35351909
31.90 35985201
31.95 35985201
32.00 36629049
32.05 36629049
32.10 37282186
32.15 37282186
32.20 37945879
32.25 37945879
32.30 38618861
32.35 38618861
32.40 39302399
32.45 39302399
32.50 39996493
32.55 39996493
32.60 40701143
32.65 40701143
32.70 41416349
32.75 41416349
32.80 42142111
32.85 42142111
32.90 42878429
32.95 42878429
33.00 43626706
33.05 43626706
33.10 44385539
33.15 44385539
33.20 45156331
33.25 45156331
33.30 45937679
33.35 45937679
33.40 46730986
33.45 46730986
33.50 47536252
33.55 47536252
33.60 48353477
33.65 48353477
33.70 49182661
33.75 49182661
33.80 50023804
33.85 50023804
33.90 50876906
33.95 50876906
34.00 51743519
34.05 51743519
34.10 52622091
34.15 52622091
34.20 53514174
34.25 53514174
34.30 54418216
34.35 54418216
34.40 55335769
34.45 55335769
34.50 56266833
34.55 56266833
34.60 57211408
34.65 57211408
34.70 58169494
34.75 58169494
34.80 59141091
34.85 59141091
34.90 60126199
34.95 60126199
35.00 61126532
35.05 61126532
35.10 62140376
35.15 62140376
35.20 63169445
35.25 63169445
35.30 64212025
35.35 64212025
35.40 65269830
35.45 65269830
35.50 66342860
35.55 66342860
35.60 67431115
35.65 67431115
35.70 68534595
35.75 68534595
35.80 69653300
35.85 69653300
35.90 70787230
35.95 70787230
36.00 71938274
36.05 71938274
36.10 73104543
36.15 73104543
36.20 74287926
36.25 74287926
36.30 75486534
36.35 75486534
36.40 76702256
36.45 76702256
36.50 77935092
36.55 77935092
36.60 79185042
36.65 79185042
36.70 80452106
36.75 80452106
36.80 81736284
36.85 81736284
36.90 83037576
36.95 83037576
37.00 84358059
37.05 84358059
37.10 85695656
37.15 85695656
37.20 87052444
37.25 87052444
37.30 88426346
37.35 88426346
37.40 89819439
37.45 89819439
37.50 91231723
37.55 91231723
37.60 92663198
37.65 92663198
37.70 94113864
37.75 94113864
37.80 95583721
37.85 95583721
37.90 97072769
37.95 97072769
38.00 98583286
38.05 98583286
38.10 100112994
38.15 100112994
38.20 101664171
38.25 101664171
38.30 103234539
38.35 103234539
38.40 104826376
38.45 104826376
38.50 106439682
38.55 106439682
38.60 108074457
38.65 108074457
38.70 109730701
38.75 109730701
38.80 111408414
38.85 111408414
38.90 113107596
38.95 113107596
39.00 114830739
39.05 114830739
39.10 116575351
39.15 116575351
39.20 118343924
39.25 118343924
39.30 120133966
39.35 120133966
39.40 121947969
39.45 121947969
39.50 123785933
39.55 123785933
39.60 125647858
39.65 125647858
39.70 127533744
39.75 127533744
39.80 129443591
39.85 129443591
39.90 131377399
39.95 131377399
40.00 133337896
40.05 133337896
40.10 135322354
40.15 135322354
40.20 137333501
40.25 137333501
40.30 139368609
40.35 139368609
40.40 141430406
40.45 141430406
40.50 143518892
40.55 143518892
40.60 145634067
40.65 145634067
40.70 147775931
40.75 147775931
40.80 149944484
40.85 149944484
40.90 152139726
40.95 152139726
41.00 154364634
41.05 154364634
41.10 156616231
41.15 156616231
41.20 158897494
41.25 158897494
41.30 161205446
41.35 161205446
41.40 163543064
41.45 163543064
41.50 165910348
41.55 165910348
41.60 168307298
41.65 168307298
41.70 170733914
41.75 170733914
41.80 173190196
41.85 173190196
41.90 175676144
41.95 175676144
42.00 178195006
42.05 178195006
42.10 180743534
42.15 180743534
42.20 183324976
42.25 183324976
42.30 185936084
42.35 185936084
42.40 188580106
42.45 188580106
42.50 191257042
42.55 191257042
42.60 193966892
42.65 193966892
42.70 196709656
42.75 196709656
42.80 199485334
42.85 199485334
42.90 202293926
42.95 202293926
43.00 205138964
43.05 205138964
43.10 208016916
43.15 208016916
43.20 210931314
43.25 210931314
43.30 213878626
43.35 213878626
43.40 216862384
43.45 216862384
43.50 219882588
43.55 219882588
43.60 222939238
43.65 222939238
43.70 226032334
43.75 226032334
43.80 229161876
43.85 229161876
43.90 232327864
43.95 232327864
44.00 235534136
44.05 235534136
44.10 238776854
44.15 238776854
44.20 242059856
44.25 242059856
44.30 245379304
44.35 245379304
44.40 248739036
44.45 248739036
44.50 252139052
44.55 252139052
44.60 255579352
44.65 255579352
44.70 259059936
44.75 259059936
44.80 262580804
44.85 262580804
44.90 266141956
44.95 266141956
45.00 269747558
45.05 269747558
45.10 273393444
45.15 273393444
45.20 277083780
45.25 277083780
45.30 280814400
45.35 280814400
45.40 284589470
45.45 284589470
45.50 288408990
45.55 288408990
45.60 292272960
45.65 292272960
45.70 296181380
45.75 296181380
45.80 300134250
45.85 300134250
45.90 304131570
45.95 304131570
46.00 308177856
46.05 308177856
46.10 312268592
46.15 312268592
46.20 316408294
46.25 316408294
46.30 320592446
46.35 320592446
46.40 324825564
46.45 324825564
46.50 329107648
46.55 329107648
46.60 333438698
46.65 333438698
46.70 337818714
46.75 337818714
46.80 342247696
46.85 342247696
46.90 346725644
46.95 346725644
47.00 351257446
47.05 351257446
47.10 355838214
47.15 355838214
47.20 360472836
47.25 360472836
47.30 365156424
47.35 365156424
47.40 369893866
47.45 369893866
47.50 374685162
47.55 374685162
47.60 379530312
47.65 379530312
47.70 384429316
47.75 384429316
47.80 389382174
47.85 389382174
47.90 394388886
47.95 394388886
48.00 399454734
48.05 399454734
48.10 404574436
48.15 404574436
48.20 409753274
48.25 409753274
48.30 414985966
48.35 414985966
48.40 420277794
48.45 420277794
48.50 425628758
48.55 425628758
48.60 431038858
48.65 431038858
48.70 436508094
48.75 436508094
48.80 442036466
48.85 442036466
48.90 447623974
48.95 447623974
49.00 453276316
49.05 453276316
49.10 458987794
49.15 458987794
49.20 464764106
49.25 464764106
49.30 470599554
49.35 470599554
49.40 476499836
49.45 476499836
49.50 482464952
49.55 482464952
49.60 488494902
49.65 488494902
49.70 494589686
49.75 494589686
49.80 500749304
49.85 500749304
49.90 506973756
49.95 506973756
50.00 513269191
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
anyway guys, I think I would not get snow from you even if it was winter.
the problem was that our very clever judge cannot round properly. instead of this

[cpp]
nAmountNeeded = (int)(100.0*AmountInput);
[/cpp]
there should have been this
[cpp]
nAmountNeeded = (int)(100.0*AmountInput + 0.5);
[/cpp]
this is the final code
[cpp]
#include <iostream>
#include <memory>
using namespace std;
typedef unsigned long mytype;

const int nNumCoins = 0xb; // 11
const int nCoinsDenom[]= {10000,5000,2000,1000, 500, 200, 100, 50, 20, 10, 5};
const int nArraySize = 1001;
static mytype ulNumWays[nNumCoins][nArraySize];

int main();
mytype GetNumberOfWays(int nAmountNeeded,int depth);

int main()
{
double AmountInput;
int nAmountNeeded;
mytype ulCounter = 0;
memset((void *)ulNumWays,0,(sizeof(ulNumWays[0][0])*nArraySize*nNumCoins));

cout.flags(ios::right);
cout.setf(ios::fixed,ios::floatfield);

while(true)
{
cin>>AmountInput;
if(AmountInput == 0.0) break; // end of program
nAmountNeeded = (int)(100.0*AmountInput + 0.5);
ulCounter = 0;
ulCounter = GetNumberOfWays(nAmountNeeded,0) ;

cout.precision(2);
cout.width(5);
cout<<AmountInput;
cout.precision(0);
cout.width(12);
cout<<ulCounter<<endl;

}

return 0;
}

mytype GetNumberOfWays(int nAmountNeeded,int depth)
{
int i, nMaxNumCoins2Take,nNewAmountNeeded,nTemp;
mytype ulCounter = 0;

if((nNumCoins - 1) == depth )
{
return 1;
}

nMaxNumCoins2Take = (!nAmountNeeded) ? 0 : (nAmountNeeded/nCoinsDenom[depth]);

for(i = 0; i <= nMaxNumCoins2Take; i ++)
{
nNewAmountNeeded = nAmountNeeded - i*nCoinsDenom[depth];
nTemp = nNewAmountNeeded/5;

ulNumWays[depth + 1][nTemp] = (ulNumWays[depth + 1][nTemp]) ?
ulNumWays[depth + 1][nTemp] : GetNumberOfWays(nNewAmountNeeded,depth + 1);

ulCounter+= ulNumWays[depth + 1][nTemp];
}

return ulCounter;
}

[/cpp]
it would be great if you replied this post. really.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### That is how you always round!

If you don't round it like that, then it won't work whenever you use doubles. Second solution: use precision(0) on floats so it rounds to the nearest integer

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
http://acm.uva.es/board/viewtopic.php?t ... hlight=147
http://acm.uva.es/board/viewtopic.php?t ... hlight=147
http://acm.uva.es/board/viewtopic.php?t ... hlight=147 etc.

Try to use the "Search" function of the board before you post any new topics, plz.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

### Re: That is how you always round!

paulhryu wrote:If you don't round it like that, then it won't work whenever you use doubles. Second solution: use precision(0) on floats so it rounds to the nearest integer
Thanks.
is it a problem with Unix only? becuase I suspect with Windows it works fine, actually I've not tried but if i make an array of answers and send it to the judge and start taking the answers from array it will work.
besides, precision(0) is used with cout, isn't it? and I changed the one that uses rounding input.
it would be great if you replied this post. really.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### Needless to say, these are errors

I actually had it happen on my Windows CodeWarrior compiler on this 147 problem (which is insanely easy, if you ask me) which is why I figured out I had to round on here. Really, try it explicitly with the following code, which will test for such rounding problems:

[cpp]#include <iostream.h>
#include <fstream.h>

#ifndef ONLINE_JUDGE
ifstream ins("input.dat");
ofstream outs("output.dat");
#else
#define ins cin
#define outs cout
#endif

int main() {
double a;

while(ins >> a) {
outs << a * 100 << " " << ((int) (a * 100)) << endl;
}
}[/cpp]

Now enter the following input:
0.40
0.41
0.42
0.43
0.44
0.45
0.46
0.47
0.48
0.49
0.50
0.51
0.52
0.53
0.54
0.55
0.56
0.57
0.58
0.59

Basically, all it does is input x, then first print out 100 * x, and then the integer rounded version of 100 * x.

I get the output (* indicates presence of rounding error):
40 40
41 40 *
42 41 *
43 42 *
44 44
45 45
46 46
47 46 *
48 47 *
49 48 *
50 50
51 51
52 52
53 53
54 54
55 55
56 56
57 56 *
58 57 *
59 58 *

Needless to say, the occurence of rounding errors is not supposed to happen. Doesn't mean you shouldn't prevent them from happening.

The reason why, which is what I'm sure you want to know is simple: double precision is in binary floating point, which means fractions which are terminating in base 10 may be infinite in base 2, which is the case with numbers such as .57, which is 57/100, which is a repeating fraction in base 2 (as are all fractions which have denominators w/ factors other than 2).

To simplify, suppose you had a number 1/3 in base 10 and you were taking it to 10th decimal point. Then, 1/3=.3333333333. If you went 1/3 * 3 = .9999999999, which rounds to 1 if you print it out. However, if you type cast it to (int), it removes the fractional portion and leaves just the integer portion, which is 0.

Kind of a long response, but the moral of the story is, in fixed based floating point representations, always rounding error will occur. You should always think about using an error margin (say, .0000000001) to make sure your outputs are good.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
ok, thanks very much indeed. it was really helpful - I am telling you.
it would be great if you replied this post. really.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore
It is actually possible to solve the problem without using floating point real numbers. That way, you will not face problems such as inaccuracy. Try to use integers as far as possible.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
ec3_limz wrote:It is actually possible to solve the problem without using floating point real numbers. That way, you will not face problems such as inaccuracy. Try to use integers as far as possible.
not to worry. that's what I actually did. the floating problem comes at this stage

[cpp]
cin>>AmountInput;
if(AmountInput == 0.0) break; // end of program
nAmountNeeded = (int)(100.0*AmountInput + 0.5);
[/cpp]
I cannot think of a way to solve the problem without using at least one floating number, as the input is given in float format. u can solve the problem itself in integers, BUT the input and output are in floating format!
называется - слышал звон, да не знает где он!
it would be great if you replied this post. really.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

### I beg to differ

I don't really agree with either of you. You can do it without doubles at all, but then, that is a hassle in itself.

Not using it would look like this:

int intpart, input;
char ch1, ch2;

ins >> intpart; // Get integer part of the input
ins >> ch1; // Decimal point, we can trash this
ins >> ch1 >> ch2; // Get the two digits, as characters
input = intpart * 100 + (ch1 - '0') * 10 + (ch2 - '0');

The above can be adapted in various ways... don't recommend it though. Too much hassle. Use doubles to get the input, then round it with the proper rounding algorithm, taking into account possible errors.

But in the problem itself, if you don't need floating point, don't use it. I've noticed in some other problems that you can get a question right just by switching everything to integers instead of floating point, using the exact same algorithm. Number 143 (Orchard Trees) comes to mind, although I did use floating point for input then used (int) (100 * a + .5) which is what you should do because it's so much easier than the character based input I showed above.