Quiz 10
===
# [A]
## Code

#include <stdio.h>
#include <math.h>

int get_balls_count(int pegs);

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        if(n == 1){
            printf("There is %d ball on %d peg.\n", get_balls_count(n), n);
        }
        else{
            printf("There are %d balls on %d pegs.\n", get_balls_count(n), n);
        }
    }

    return 0;
}

int get_balls_count(int pegs){
    int top[201] = {0};
    int balls = 1;
    int curr_peg = 1;

    while(curr_peg <= pegs){
        for(curr_peg=1; curr_peg<=pegs; curr_peg++){
            if(!top[curr_peg] || (fabs(sqrt(top[curr_peg] + balls) - (int)sqrt(top[curr_peg] + balls)) < pow(10, -36))){
                top[curr_peg] = balls;
                balls++;
                break;
            }
        }
    }

    return balls-1;
}

# [B]
## Code

#include <stdio.h>
#include <stdlib.h>

int to_bin(int* bin, int n);
int get_distance(int* bin, int len);
void print_all(int n, int h);

int main(){
    int cases;
    int n, h, len;
    int printed = 0;
    scanf("%d", &cases);

    for(int i=0; i<cases; i++){
        if(printed){
            puts("");
        }
        else{
            printed = 1;
        }
        
        scanf("%d %d", &n, &h);
        char* bin = calloc(17, sizeof(int));
        len = to_bin(bin, n);
        print_all(n, h);

        free(bin);
    }

    return 0;
}

int to_bin(int* bin, int n){ //change decimal to binary
    int len = 0;
    while(n >= 2){
        bin[len] = n & 1;
        n /= 2;
        len++;
    }

    bin[len] = n;
    len++;

    return len;
}

int get_distance(int*  bin, int len){
    int distance = 0;
    for(int i=len-1; i>-1; i--){
        if(bin[i]){
            distance++;
        }
    }

    return distance;
}

void print_all(int n, int h){
    int* curr_bin;
    int curr_len;
    int curr = 1;

    while(1){
        curr_bin = calloc(n, sizeof(int));
        curr_len = to_bin(curr_bin, curr);
        
        if(curr_len > n){
            break;
        }

        if(get_distance(curr_bin, n) == h){
            for(int i=0; i<n-curr_len; i++){
                printf("0");
            }

            for(int i=curr_len-1; i>-1; i--){
                printf("%d", curr_bin[i] != 0);
            }
            puts("");

            free(curr_bin);
        }

        curr++;
    }
}

# [C]
## Code
此題需使用tail recursion，否則將會有runtime error。
因此題 $n <= 100$，有overflow的問題，故需使用陣列已儲存結果。類似題目可參考[Quiz 09 [C]](https://hackmd.io/vSyIWBTNRuSU-p5Vu7rYNA#C)

#include <stdio.h>
#include <stdlib.h>
#define SIZE 20

unsigned int* max_discon_sets(unsigned int num1[], unsigned int num2[], unsigned int num3[], int n);

int main(){
    int n;
    unsigned int *num1, *num2, *num3, *result;
    int printed;

    while(scanf("%d", &n) != EOF) {
        printed = 0;

        num1 = calloc(SIZE, sizeof(unsigned int));
        num2 = calloc(SIZE, sizeof(unsigned int));
        num3 = calloc(SIZE, sizeof(unsigned int));

        num1[0] = 1;
        num2[0] = 2;
        num3[0] = 2;
        
        result = max_discon_sets(num1, num2, num3, n);

        for(int i=SIZE-1; i>=0; i--){
            if(result[i]){
                if(printed){
                    printf("%08u", result[i]);
                }
                else{
                    printf("%u", result[i]);
                    printed = 1;
                }
            }
        }

        puts("");
        
        free(num1);
        free(num2);
        free(num3);
    }

    return 0;
}

unsigned int* max_discon_sets(unsigned int num1[], unsigned int num2[], unsigned int num3[], int n){
    if(n == 1){
        return num1;
    }
    else if(n == 2){
        return num2;
    }
    else if(n == 3){
        return num3;
    }

    unsigned int* sum = calloc(SIZE, sizeof(unsigned int));
    //num1 + num2
    unsigned int tmp_result;
    int carry = 0;
    for(int i=0; i<SIZE; i++){
        if(!num1[i] && !num2[i]){
            sum[i] = carry;
            break;
        }
        tmp_result = num1[i] + num2[i] + carry;
        sum[i] = tmp_result % 100000000;
        carry = tmp_result / 100000000;
    }

    if(n == 4){
        return sum;
    }
    return max_discon_sets(num2, num3, sum, n-1);   
}

###### tags: `程設一quiz`