10638 - The Trip II

technobug · Post by **technobug** » Thu Apr 08, 2004 2:50 am

Humm... I dunno if I am missing something here...

Am I supposed to use a greedy algo which generates the average and easily finds out the number of payments which can have one cent diff? I tried the following although it did not work out...

[cpp]
#include <stdio.h>

int main(char **argv,int argc) {

int c, i, countUp, countDown, countEquals;
double n[10], total, novaMedia;
while(true) {

scanf(" %d",&c);
if(c==0) break;
total = 0; countUp = 0; countDown = 0; countEquals = 0;

for(i = 0; i != c; i++) {
scanf(" %lf", &n);
total += n;
}

novaMedia = (total / c * 100);
novaMedia = ((int) novaMedia) / 100.0;

for(i = 0; i != c; i++) {

// trocar para >= 0.02??
if(n < novaMedia) {
countDown++;
} else if(n > novaMedia) {
countUp++;
} else {
countEquals++;
}

}

if(countUp + countEquals == c || countDown + countEquals == c) {
// ignorar
printf("0\n");
} else {
printf("%d\n", countUp > countDown ? countUp : countDown);
}

}

return 0;

}[/cpp]

marian · Post by **marian** » Thu Apr 15, 2004 5:44 pm

Try this input:

Code: Select all

technobug · Post by **technobug** » Fri Apr 16, 2004 12:36 am

oops.....

thanks... i will try to figure it out, should be easy though

hujialie · Post by **hujialie** » Thu May 06, 2004 4:53 pm

Hi,I am facing difficulity while solving this problem, could anyone give
some hints?

I try to devide students into maximal number of groups such that each
group's average cost is the same as the total average cost(diff<0.01),
then the answer is n-m(m is the maximal group number), is this idea
correct, or I miss sth?

Thx.

Adrian Kuegel · Post by **Adrian Kuegel** » Thu May 06, 2004 6:39 pm

I try to devide students into maximal number of groups such that each
group's average cost is the same as the total average cost(diff<0.01),
then the answer is n-m(m is the maximal group number), is this idea
correct, or I miss sth?

Yes, basically this is how I solved the problem. I used backtracking to find maximal number of groups, but avoided permutations of people inside groups or permutations of the groups themselves. And to check if I can build a group of some people, the sum of their spendings must be >= floor(average spendings of all people)*groupsize and <= ceil(average spendings of all people)*groupsize.

hujialie · Post by **hujialie** » Fri May 07, 2004 7:17 am

Thank you for your reply!

Accepted after all

I made such mistake, that I thought as long as one group are available,
after choosing this group, the remaining group is also available, that's
wrong since 1 cent's rounding in this problem.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Mon Aug 23, 2004 8:19 pm

I don't really know where I am wrong here. Could anyone tell me what is AC output for those test cases?

Input:

3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
4
15.00
15.00
15.00
10.00
2
0.95
0.93
4
10.00
10.00
2.00
6.00
1
1.00
7
0.10
0.51
0.51
0.51
0.98
1.00
2.01
10
0.10
0.51
0.51
0.51
0.98
1.00
2.00
3.09
10.00
20.01
4
10.00
10.00
2.00
6.00
5
0.00
0.51
0.51
0.51
0.98
6
2041.98
5759.84
2449.14
3388.43
3992.28
5142.12
4
4183.87
8045.40
1441.48
6142.48
8
2093.84
6435.96
1051.21
2207.88
3819.45
4279.77
6963.44
54.33
10
8412.99
6346.76
3885.59
9008.48
3562.83
1591.23
9250.90
628.17
4952.52
7676.59
7
1001.46
1818.96
6948.21
2667.61
8276.37
7963.79
6051.86
3
5291.20
1274.90
8362.15
6
8941.79
7679.37
1743.40
7934.94
5445.65
6616.13
1
187.53
7
4626.53
4358.32
4594.24
8632.79
2526.31
6163.63
1688.43
3
7397.97
3429.42
4529.81
3
9617.91
8900.10
30.36
6
1234.83
1802.39
7161.77
8573.38
6623.40
8912.83
7
6446.38
3490.13
7863.70
4823.33
8460.29
1380.84
1270.46
7
4111.64
2458.51
5541.72
7464.13
8505.14
4936.51
8759.65
3
2096.25
4378.63
9092.86
6
3282.13
4658.69
4057.10
9217.93
82.70
7694.91
10
325.58
2922.69
8093.13
715.89
6899.76
8162.95
4634.29
8078.27
4518.90
919.45
8
2167.73
632.76
4995.50
2093.55
5296.61
9687.55
3796.15
4356.60
5
7393.11
8146.69
6336.20
2932.74
7300.30
3
8885.39
6817.90
4205.18
7
106.58
6167.76
4593.79
2856.64
6484.93
976.16
5195.59
5
3752.47
574.36
1019.48
1758.83
9930.46
4
285.65
4648.40
1794.63
914.48
4
5761.55
2931.14
8894.11
4240.89
9
5666.12
1837.55
7336.96
7204.60
6604.36
8120.50
5129.35
1301.18
425.17
5
7700.97
9943.85
490.10
2321.44
4844.78
2
6138.34
5465.70
8
464.62
1011.22
3536.30
2358.10
554.44
999.90
6703.25
1507.18
9
5049.13
7300.89
7764.29
7314.46
6168.70
990.21
1264.80
5783.83
711.32
9
1446.34
4066.36
9320.97
1668.87
7899.77
410.99
2619.80
9115.88
5170.89
9
8981.84
3314.40
9584.40
7436.96
7014.80
653.99
6435.10
1049.70
5523.38
2
4037.83
9417.27
10
6364.13
4093.34
5137.61
625.81
4261.70
4481.87
2251.80
9915.72
894.84
7454.40
4
2340.86
8352.20
5872.74
9724.44
7
7039.86
3342.73
1290.17
9574.25
777.85
2497.64
5427.93
9
1870.12
5635.27
8841.84
8880.54
6581.34
8079.83
5735.40
4797.64
8004.14
7
3199.39
9536.48
7688.91
9974.51
7098.67
5824.20
7383.59
1
7749.95
5
813.74
6823.32
8874.98
223.80
4163.66
4
3645.10
8811.24
999.61
6205.20
7
1039.34
5038.63
469.90
8656.39
9406.82
6831.73
3630.90
9
5755.77
5089.42
3950.69
7677.98
5271.48
4810.98
7552.75
137.89
8246.19
1
1270.81
4
6252.94
9256.50
4551.55
7350.51
9
5387.51
7989.88
6281.88
9931.80
1022.21
7349.37
6507.28
6286.20
8403.86
4
9451.38
5557.40
7108.69
4616.94
2
219.47
5442.76
3
5073.40
247.69
9687.65
8
6328.18
6825.87
2925.34
8750.37
7411.60
2438.77
7456.15
9993.70
8
9734.49
9535.10
502.32
9486.73
1826.93
3438.89
9425.77
9312.91
5
3510.11
6495.24
2006.10
2225.40
7715.10
4
7690.42
1992.87
4126.45
2415.63
1
2185.34
9
8258.63
7993.58
5590.30
7944.79
2869.43
626.83
9625.82
9961.68
230.42
6
4919.73
3117.80
250.85
513.30
9580.90
2537.94
6
1575.00
7041.84
4601.69
5175.41
1212.10
7818.63
4
4275.63
7574.25
2523.35
1554.63
6
7091.86
9377.46
6315.56
8800.75
6192.98
5141.91
7
5477.30
9629.35
6338.35
1195.64
769.80
8057.59
2878.40
4
6057.27
3334.95
3580.52
7892.56
10
8941.63
5893.50
8352.57
2957.47
902.48
3596.90
2008.60
4756.39
9413.35
8134.22
10
6788.19
4843.68
7510.64
9293.99
6925.21
6441.60
7386.37
5018.93
7153.83
266.71
5
2197.56
1875.51
7948.58
7000.36
2407.81
3
3327.25
4795.84
3640.22
7
5180.57
7870.89
8923.42
5385.75
7142.67
6561.21
4013.96
7
5599.50
2456.40
5953.57
7695.89
5880.53
6533.83
1961.83
1
5905.12
5
7672.49
6370.18
1215.47
3459.97
6995.40
5
9298.74
1427.42
3903.49
1764.81
4649.81
1
6318.32
3
7080.85
3217.77
8667.27
1
5829.89
5
2981.21
8321.42
5022.10
2709.47
6638.26
9
1944.47
7659.56
1538.74
6808.38
9641.54
5817.11
1499.84
5649.95
551.63
3
5662.88
477.59
3407.23
10
6039.96
1787.28
1706.46
9997.11
9450.40
4131.17
5693.60
232.35
1419.47
8310.90
8
392.30
5800.88
9795.85
1303.65
4955.20
1137.67
3107.40
6613.91
5
7552.20
4700.60
6003.27
967.85
8076.66
4
4291.50
8450.90
9053.10
4808.92
7
426.60
3709.96
7679.90
1584.16
9105.95
1193.64
8346.50
2
5330.70
1577.76
9
8408.20
2635.50
3274.40
705.90
5246.30
4708.27
1294.20
810.71
2941.58
3
3628.27
678.62
889.21
10
5849.41
973.30
2358.91
6221.77
5620.51
5862.84
2563.40
8961.80
2645.62
9411.21
9
5013.20
2210.85
9264.60
5751.30
4960.96
4971.79
7369.30
4500.76
2287.15
3
736.79
2955.10
4503.55
5
4028.20
6212.54
3306.16
1979.99
5484.63
3
7054.00
507.49
9140.52
6
6191.69
6943.17
3143.83
2801.75
634.90
6207.31
6
4287.27
634.47
1301.31
228.98
4980.96
7379.90
5
7032.83
1573.30
7987.40
8511.65
9053.23
3
1642.28
8908.91
8478.83
9
3816.21
8928.90
1431.52
5031.98
4134.98
4810.85
3755.66
8222.52
6373.49
8
272.40
4345.37
1978.20
1438.47
6679.64
3480.82
9282.16
7796.96
9
7143.78
2647.86
3923.65
4648.55
8190.43
1427.28
4845.00
6565.81
9171.13
6
4495.19
4318.49
2043.45
6939.00
7268.36
5022.47
3
6252.12
4827.15
4346.65
6
5115.85
8884.86
80.32
3269.47
2936.38
8475.21
3
2866.40
793.77
4318.30
8
3684.17
8732.35
3089.56
7951.48
4919.70
7011.25
8826.41
5883.17
10
2633.89
7340.57
9851.52
3183.80
8536.12
4442.30
9684.59
9977.25
6209.88
5407.37
0

My output:

1
2
3
1
3
0
6
9
3
3
4
3
7
9
6
2
5
0
6
2
2
5
6
6
2
5
9
7
4
2
6
4
3
3
8
4
1
7
8
8
8
1
9
3
6
8
6
0
4
3
6
8
0
3
8
3
1
2
7
7
4
3
0
8
5
5
3
5
6
3
9
9
4
2
6
6
0
4
4
0
2
0
4
8
2
9
7
4
3
6
1
8
2
9
8
2
4
2
5
5
4
2
8
7
8
5
2
5
2
7
9

little joey · Post by **little joey** » Mon Aug 23, 2004 11:54 pm

Got the same output

This is the test I used to find my errors:

Code: Select all

Code: Select all

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Aug 24, 2004 12:30 am

Thanks. I have wrong answer (3) here:

4
0.00
0.06
0.02
0.06
0

I'll try to debug it now.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Tue Aug 24, 2004 1:57 am

I fixed that bug, but still no luck. I'm tired with WA

Maybe you'll be able to spot the error.
[cpp]#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int toInt(double d){
return static_cast<int>(100.0 * d + 0.1);
}

int ceil(int p, int q){
return p / q + ((p % q == 0) ? 0 : 1);
}

// finds the smallest group with proper average and removes it from v
void improve(vector<int> & v){
for(int k = 1; k <= v.size(); ++k){ // try to get a group sized k
for(int i = 0; i < (1 << (v.size())); ++i){
int sum_included = 0; // remaining part sum
int n_included = 0;
int sum_excluded = 0; // group sum
int n_excluded = 0;

for(int j = 0; j < v.size(); ++j){
if(i & (1 << j)){
sum_excluded += v[j];
++n_excluded;
}else{
sum_included += v[j];
++n_included;
}
}

if(n_excluded != k)continue;
if(n_included != 0 && n_excluded != 0){
int lb = min(sum_included / n_included, sum_excluded / n_excluded);
int ub = max(ceil(sum_included, n_included), ceil(sum_excluded, n_excluded));
if(lb + 1 < ub)continue;
}

vector<int> new_v;

for(int j = 0; j < v.size(); ++j)
if((i & (1 << j)) == 0)
new_v.push_back(v[j]);

v = new_v;
return;
}
}
}

int main(){
while(true){
int n;
cin >> n;
if(n == 0)break;

vector<int> v;
for(int i = 0; i < n; ++i){
double d;
cin >> d;
v.push_back(toInt(d));
}

while(! v.empty()){
improve(v);
--n;
}

cout << n << endl;
}
}[/cpp]

little joey · Post by **little joey** » Tue Aug 24, 2004 9:03 am

Well, I'm too lazy to debug your code

But I found out that it gives wrong answers on these nine cases:

Code: Select all

The correct output (that can be easily verified by hand calculation) is

Code: Select all

Your answers were one too high in all these cases.
Look out for those cases with small numbers. I ran your code against a testset of 10000 randomly generated cases and it gave correct answers for all of them. So it are the small numbers that make it go wrong.

Happy hunting

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Aug 25, 2004 6:57 pm

Now I see it - I used wrong algorithm. Funny that it wouldn't fail on 10000 random cases.

Krzysztof Duleba · Post by **Krzysztof Duleba** » Wed Aug 25, 2004 7:13 pm

I changed the algo so that it fits to "7 0.01 0.08 0.07 0.09 0.02 0.00 0.02" input and got AC. Thanks!