PKU 1001, 1014, 1519, 2229, 2663

ブログに貼っていなかった分と、今日解いたものを載せておきます.
AOJはつまりつつあります. 実力つけなければ.
1001
Implementation.

#include <stdio.h>
#include <string.h>

int max(int a, int b)
{
    return (a > b ? a : b);
}

int main(void)
{
    char str[1024], next[1024];
    int result[1024];
    int n;
    int i, j;
    int decimalPoint;
    int len, mul;
    int carry;
    
    while (scanf("%s%d", str, &n) != EOF){
        i = 0;
        
        while (str[i] != '.' && str[i] != '\0'){
            i++;
        }
        if (str[i] == '.'){
            decimalPoint = strlen(&str[i]) - 1;
            strcpy(&str[i], &str[i + 1]);
        }
        else {
            decimalPoint = 0;
        }
        
        decimalPoint *= n;
        sscanf(str, "%d", &mul);
        
        for (i = 0; i < n - 1; i++){
            j = strlen(str);
            next[j--] = '\0';
            carry = 0;
            while (j >= 0){
                result[j] = mul * (int)(str[j] - '0') + carry;
                carry = 0;
                if (result[j] > 9){
                    carry = result[j] / 10;
                    result[j] %= 10;
                }
                next[j] = result[j] + '0';
                j--;
            }
            if (carry){
                sprintf(str, "%d%s", carry, next);
            }
            else {
                sprintf(str, "%s", next);
            }
        }
        
        len = max(strlen(str), decimalPoint) + 1;
        
        next[len--] = '\0';
        i = strlen(str) - 1;
        while (len >= 0){
            if (!decimalPoint){
                next[len] = '.';
            }
            else if (i >= 0){
                next[len] = str[i--];
            }
            else {
                next[len] = '0';
            }
            decimalPoint--;
            len--;
        }
        
        i = strlen(next) - 1;
        
        while (next[i] == '0'){
            next[i--] = '\0';
            if (next[i] == '.'){
                next[i] = '\0';
                break;
            }
        }
        
        printf("%s\n", next);
    }
    
    return (0);
}

1014

DPなはず.最悪ケースがO(#stone)なので、TLEします. 明日もう一度考察.

#include <stdio.h>
#include <string.h>

int min(int a, int b)
{
    return (b > a ? a : b);
}

int main(void)
{
    int count;
    int sum, s;
    int i, j, k;
    int a[6], arr[20000];
    char dp[60001];
    
    count = 0;
    while (1){
        scanf("%d%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &a[4], &a[5]);
        
        if (a[0] + a[1] + a[2] + a[3] + a[4] + a[5] == 0){
            break;
        }
        
        sum = k = 0;
        for (i = 0; i < 6; i++){
            sum += (i + 1) * a[i];
            for (j = 0; j < a[i]; j++){
                arr[k++] = i + 1;
            }
        }
        
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        s = 0;
        for (i = 0; i < k; i++){
            s += arr[i];
            for (j = arr[i]; j <= min(s, sum / 2); j++){
                dp[j] |= dp[j - arr[i]];
            }
            if (dp[sum / 2]){
                break;
            }
        }
        
        printf("Collection #%d:\n%s\n\n", ++count, !(sum & 1) && dp[sum / 2] ? "Can be divided." : "Can't be divided.");
    }
    
    return (0);
}

1519
Implementation.

#include <stdio.h>

int main(void)
{
    char str[1024];
    int ans;
    int i;
    
    while (1){
        scanf("%s", str);
        
        if (str[0] == '0'){
            break;
        }
        
        ans = 999;
        while (ans >= 10){
            ans = i = 0;
            
            while (str[i] != '\0'){
                ans += str[i++] - '0';
            }
            sprintf(str, "%d", ans);
        }
        
        printf("%d\n", ans);
    }
    return (0);
}

2229
DP.

#include <stdio.h>
#include <string.h>

int main(void)
{
    int i, j;
    int num;
    static int ans[1000001];
    
    scanf("%d", &num);
    
    ans[0] = 1;
    
    for (i = 1; i <= num; i *= 2){
        for (j = 0; j + i <= num; j++){
            ans[j + i] += ans[j];
            if (ans[j + i] >= 1000000000){
                ans[j + i] -= 1000000000;
            }
        }
    }
    
    printf("%d\n", ans[num]);
    
    return (0);
}

2663
bitDP.

#include <stdio.h>
#include <string.h>

int dp[2][8];

int main(void)
{
    int i, j, k;
    int n;
    int *crt, *next, *temp;
    int used;
    
    while (1){
        scanf("%d", &n);
        
        if (n == -1){
            break;
        }
        crt = dp[0];
        next = dp[1];
        
        crt[0] = 1;
        
        for (i = n - 1; i >= 0; i--){
            for (j = 2; j >= 0; j--){
                for (used = 0; used < 1 << 3; used++){
                    if ((used >> j) & 1){
                        next[used] = crt[used & ~(1 << j)];
                    }
                    else {
                        int res = 0;
                        
                        if (j + 1 < 3 && !((used >> (j + 1)) & 1)){
                            res += crt[used | 1 << (j + 1)];
                        }
                        if (i + 1 < n){
                            res += crt[used | 1 << j];
                        }
                        next[used] = res;
                    }
                }
                for (k = 0; k < 1 << 3; k++){
                    crt[k] ^= next[k];
                    next[k] ^= crt[k];
                    crt[k] ^= next[k];
                }
            }
        }
        
        printf("%d\n", crt[0]);
    }
    
    return (0);
}