WA tried all the inputs of this thread...gives correct output..
Code: Select all
#include <cstdio>
#include <iostream>
#include <cstring>
int min(int x,int y){
if(x>=y){
return y;
}
else{
return x;
}
}
using namespace std;
int A,B;
int dp[10010];
int dp2[10010];
int rec(int time,int num){
int a,b,c;
if(time-A<0 && time-B <0){
return time;
}
if(dp[time]!=-1){
return dp[time];
}
else{
if(time-A<0 && time-B>=0){
return dp[time]=rec(time-B,num+1);
}
else if(time-A>=0 && time-B<0){
return dp[time]=rec(time-A,num+1);
}
else if(time-A>=0 && time-B>=0){
return dp[time]=min(rec(time-A,num+1),rec(time-B,num+1));
}
}
}
int rec2(int time,int num){
if(time<0){
return 0;
}
else if(time==0){
return num;
}
if(dp2[time]!=-1){
return dp2[time];
}
else{
int y=rec2(time-A,num+1);
int z=rec2(time-B,num+1);
if(y>=z){
return dp2[time]=y;
}
else{
return dp2[time]=z;
}
}
}
int main(){
int t;
while(cin>>A>>B>>t){
memset(dp,-1,sizeof(dp));
memset(dp2,-1,sizeof(dp2));
int y=rec(t,0);
if(y==0){
cout<<rec2(t,0)<<endl;
}
else{
cout<<rec2(t-y,0)<<" "<<y<<endl;
}
}
}