Buy Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 868 Accepted Submission(s): 392
Problem Description
Imyourgod
need 3 kinds of sticks which have different sizes: 20cm, 28cm and 32cm.
However the shop only sell 75-centimeter-long sticks. So he have to cut
off the long stick. How many sticks he must buy at least.
need 3 kinds of sticks which have different sizes: 20cm, 28cm and 32cm.
However the shop only sell 75-centimeter-long sticks. So he have to cut
off the long stick. How many sticks he must buy at least.
Input
The first line of input contains a number t, which means there are t cases of the test data.
There
will be several test cases in the problem, each in one line. Each test
cases are described by 3 non-negtive-integers separated by one space
representing the number of sticks of 20cm, 28cm and 32cm. All numbers
are less than 10^6.
There
will be several test cases in the problem, each in one line. Each test
cases are described by 3 non-negtive-integers separated by one space
representing the number of sticks of 20cm, 28cm and 32cm. All numbers
are less than 10^6.
Output
The
output contains one line for each line in the input case. This line
contains the minimal number of 75-centimeter-long sticks he must buy.
Format are shown as Sample Output.
output contains one line for each line in the input case. This line
contains the minimal number of 75-centimeter-long sticks he must buy.
Format are shown as Sample Output.
Sample Input
2
3 1 1
4 2 2
3 1 1
4 2 2
Sample Output
Case 1: 2
Case 2: 3
Case 2: 3
Author
imyourgod (Special Thanks : crackerwang & Louty)
Source
题意:需要 x 根20cm,y根 28cm,z根 32cm,问最少需要多少根 75 cm的木棍才可以都分出来?
题解:贪心的去选,先选3根的,选不了了才能选2根的,最后如果还有剩才能选一根的.
这些情况分别是
20 20 28
20 20 32
20 20 20
32 28
28 28
32 32
20
28
32
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
int main()
{
int tcase,t = ;
scanf("%d",&tcase);
while(tcase--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int ans = ,a,b,c;
if(x>=&&y>=){ /// 20 20 28
a = x/,b=y;
c = min(a,b);
x=x-*c,y=y-c;
ans+=c;
}
if(x>=&&z>=){ ///20 20 32
a = x/,b = z;
c = min(a,b);
x=x-*c,z=z-c;
ans+=c;
}
if(x>=){ ///20 20 20
a = x/;
x = x%;
ans+=a;
}
if(y>=&&z>=){ ///28 32
c = min(y,z);
ans+=c;
y-=c;
z-=c;
}
if(y>=){ ///28 28
c = y/;
y = y%;
ans+=c;
}
if(z>=){///32 32
c = z/;
z = z%;
ans+=c;
}
if(x||y||z) ans++;
printf("Case %d: %d\n",t++,ans);
}
return ;
}