1192.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1192 on 2005-09-23 at 19:08:45 */ 
#include <stdio.h>
#include <string.h>

const int paper[] = {2000, 1000, 400, 200, 100, 40, 20, 10, 4, 2, 1};

int main()
{
    char value[5];
    double c[6001][11];
    int i, j, v, r;
    
    for(i = 10; i >= 0; i--) {
        for(j = 1; j <= 6000; j++) {
            if(i == 10 || j == 1) {
                c[j][i] = 1;
            } else {
                if(j < paper[i]) {
                    c[j][i] = c[j][i+1];
                } else if(j == paper[i]) {
                    c[j][i] = 1 + c[j][i+1];
                } else {
                    c[j][i] = c[j-paper[i]][i] + c[j][i+1];
                }    
            }    
        }
    }    
    while(scanf("%s", value) == 1) {
        r = strlen(value);
        v = 0;
        for(i = 0; i < r; i++) { 
            if(value[i] >= '0' && value[i] <= '9') {
                v = v * 10 + value[i] - '0';
            }
        }
        v /= 5;
        if(v == 0) {
            return 0;
        } else {
            for(i = 0; i < 11; i++) {
                if(paper[i] <= v) {
                    printf("%6s%17.0lf\n", value, c[v][i]);
                    break;
                }    
            }
        }
    }
    
    return 0;
}