ACM HDU 1248 한 빙 왕좌(물 문제,모 함수 로 완성)

얼음 왕좌
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4537    Accepted Submission(s): 2151
Problem Description
불사 족의 요괴 왕 은 월급 을 받 았 다.죽음 의 기 사 는 N 원 짜 리 지 폐 를 받 았 다.(기억 해라.돈 이 한 장 밖 에 없다)전투 중 에 자주 죽 는 것 을 막 기 위해 자신 에 게 도 구 를 사기 로 결정 하고 임 프 상점 앞 에 왔 다.
죽음 의 기사:"나 는 도 구 를 살 거 야!"
임 프 상인:"우리 에 게 는 세 가지 도구 가 있 습 니 다.혈액 병 150 원,마법 약 200 원,무적 물약 350 원 입 니 다."
죽음 의 기사:"네,혈액 병 하나 주세요."
말 이 떨 어 지자 그 는 N 원 짜 리 큰 지 폐 를 꺼 내 임 프 상인 에 게 건 네 주 었 다.
임 프 상인:"손님 에 게 돈 을 찾 는 습관 이 없다 는 걸 깜빡 했 네.많은 돈 은 팁 으로 받 았 네.헤헤."
죽음 의 기사:"....."
죽음 의 기 사 는 돈 을 팁 으로 주 느 니 차라리 자신 이 도 구 를 좀 더 사 는 것 이 낫 겠 다 고 생각 했다.어차피 앞으로 사 야 할 것 은 일찍 사서 집에 두 는 것 도 좋 지만 팁 을 적 게 벌 게 해 야 한다 고 생각 했다.
지금 사망 한 기 사 는 적어도 임 프 상인 에 게 얼마의 팁 을 줄 지 계산 해 달라 고 한다.
 
Input
입력 한 데이터 의 첫 줄 은 하나의 정수 T(1<=T<=100)로 테스트 데이터 의 수량 을 대표 합 니 다.그 다음 에 T 줄 테스트 데이터 입 니 다.각 테스트 데 이 터 는 하나의 정수 N(1<=N<=10000)만 포함 하고 N 은 사망 기사 가 가지 고 있 는 지폐의 액면 가 를 대표 합 니 다.
주의:임 프 상점 은 문제 에서 설명 한 세 가지 도구 만 있 습 니 다.
 
Output
각 조 의 테스트 데이터 에 대해 서 는 사망 기사 가 임 프 상인 에 게 팁 으로 얼 마 를 낭비 하 는 지 출력 해 주세요.
 
Sample Input
2 900 250
 
Sample Output
0 50
 
Author
Ignatius.L
 
Recommend
Ignatius.L
 
 

#include<stdio.h>
#include<string.h>
#define MAXN 10000
int c1[MAXN],c2[MAXN];
int v[3];
void mufun(int sum,int *v)
{
    int i,j,k;
    for(i=0;i<=MAXN;i+=v[0])
         c1[i]=1;
    for(k=1;k<sum;k++)
    {
        for(i=0;i<=MAXN;i++)
        {
            for(j=0;i+j<=MAXN;j+=v[k])
               c2[i+j]+=c1[i];
        }    
        for(i=0;i<=MAXN;i++)
        {
            c1[i]=c2[i];
            c2[i]=0;
        }    
    }    
}  
int main()
{
    int n,T;
    v[0]=150;
    v[1]=200;
    v[2]=350;
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
    mufun(3,v);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int cnt=0;
        while(c1[n-cnt]==0)
        {
            cnt++;
        }  
        printf("%d
",cnt);  
    }
    return 0;    
}