Quiz 05
===
# Problem A
## code

#include <stdio.h>

int main(){
    int c, len, n; //input
    int sum;
    int printed;

    while(1){
        scanf("%d %d", &c, &len);
        if(!len){
            break;
        }

        sum = 0;
        printed = 0;

        for(int i=0; i<len; i++){
            scanf("%d", &n);
            if(n<=c){
                sum += n;

                //print
                if(!printed){
                    printf("%d ", n);
                    printed = 1;
                }
                else if(n<0){
                    printf("- %d ", n*(-1));
                }
                else{
                    printf("+ %d ", n);
                }
            }
        }

        if(printed){
            printf("= %d\n", sum);
        }
        else{
            puts("All values have been filtered out.");
        }
    }

    return 0;
}

# Problem B
## description
A special game of subtraction is to find the minimum times of subtraction for letting the sequence 1, 2, 3, ..., n becomes a zero sequence 0, 0, 0, ..., 0. When taking subtraction, a limit must be satisfied: the subtraction can be made on any elements of the sequence, but each time only one subtracted value can be chosen for all the elements. For example, consider the sequence:
1, 2, 3, 4
We need at least three times to let all values in the sequence become zero, e.g.,
0, 2, 2, 4 (subtract 1 and 3 by 1)
0, 0, 0, 2 (subtract 2, 2, and 4 by 2)
0, 0, 0, 0 (subtract 2 by 2)
Write a program to calculate the minimum times of subtraction required for an arbitrary value of input 𝑛.

**input**
The input starts with an integer 𝑚 indicating the number of cases. Each case contains one integer value 𝑛.

**output**
For each case, output the minimum times of subtraction required for obtaining the zero sequence as mentioned above.

**Example**
| input | output |
| ----- | ------ |
| 3 4 16 255 | 3 5 8 |

## explanation - 1
由上表可發現規律：
每個數字為0前，其數字皆為2^x, x>=0
==1==: 1=2^0^，共有1個1
==2 2==: 2=2^1^，共有2個2
==4 4 4 4==: 4=2^2^，共有4個4
==8 8 8 8 8 8 8 8==: 8=2^3，共有8個8

上述可整理為下：
可發現count=x+1
故找出n最後的數字為2的幾次方，再將次方數加一即為所求。

亦可視為：
2^0^ + 2^1^ + 2^2^ + ... + 2^x^ >= n
找出x的最小值並加上1

## explanation - 2: 進一步說明上方所發現的規律

以n=16為例，先將數列的數字轉為2進位
| base 10 | 1 | 2 | ... | 15 | 16 |
|:-------:|:-----:|:-----:|:---:|:-----:|:-----:|
| base 2 | 00001 | 00010 | ... | 01111 | 10000 |

接著，執行subtraction
每輪執行減法時，從左至右（亦可由右至左，在此以前者做說明）判斷sequence中數字的每一位數是否為1，若為1，則做減法，使得此為數減為0。

舉例： 11(base-10) = 1011(base-2)
1. 由左數來的第一位數（2^0^）為1，故將其減去2^0^ 使得此數字變為1010
2. 由左數來的第二位數（2^1^）為1，故將其減去2^1^ 使得此數字變為1000
3. 由左數來的第三位數（2^2^）為0，故不需做任何減法
4. 由左數來的第四位數（2^3^）為1，故將其減去2^3^ 使得此數字變為0000

此數列為連續正整數，每個為數皆需要被做減的動作（每個位數，數列中必有數字的此位數之值為1），故若欲將數列的每個數減為0，最少減法次數為n轉為二進位時之位數數量

亦可視為：
2^0^ + 2^1^ + 2^2^ + ... + 2^x^ >= n
找出x的最小值並加上1

### 深入思考：為何是將數列之數字轉為2進位，非其他的？
舉例來說，如果將數列之數轉為3進位
|base 10| 1 | 2 | 3 | 4 | 5 | 6 |
|:-----:|:-:|:-:|:-:|:-:|:-:|:-:|
|base 3|001|002|010|011|012|020|

執行減法時，以第一位數（3^0^）做説明
若要將1、4的第一位數轉為0，須減3^0^x1；
若要將2、5的第一位數轉為0，須減3^0^x2；
需要執行兩次動作才可將數列中的每個數之最低為轉為0

且將6(base 10)轉為二進位及三進位比較：
110(base 2)：最高次為2^2^，需執行2+1=3次
020(base 3)：最高次為3^1^，又因每個位數有1, 2這2種非0數之可能，需執行(1+1)*2=4次

由此可知，當數列之數轉為base 2時，才能夠獲得最少執行次數。

## code

#include <stdio.h>

int main(){
    int m, n; // m=number of cases, n=sequence
    int gp, two_pow, x;
    scanf("%d", &m);

    for(int i=0; i<m; i++){
        scanf("%d", &n);

        //finding the smallest x
        x = 0;
        gp = 0;
        two_pow = 1;
        while(gp < n){
            gp += two_pow;
            two_pow *= 2;
            x++;
        }

        printf("%d\n", x);
    }
    
    return 0;
}

# Problem C
## code

#include <stdio.h>

int main(){
    int LB, UB; //lower bound | upper bound
    int a, b, c, d; // ax + by [d] c | d: 1=< -1=>
    int count;

    while(1){
        scanf("%d %d %d %d %d %d", &LB, &UB, &a, &b, &c, &d);
        if(!LB && !UB && !a && !b && !c && !d){
            break;
        }

        count = 0;
        for(int x=LB; x<=UB; x++){
            for(int y=UB; y>=LB; y--){
                if((d==1) && ((a*x + b*y) <= c)){
                    count++;
                }
                else if((d==-1) && ((a*x + b*y) >= c)){
                    count++;
                }
            }
        }

        printf("The square area within %d to %d satisfying ", LB, UB);
        if(b>=0){
            printf("%dx+%dy", a, b);
        }
        else{
            printf("%dx%dy", a, b);
        }

        if(d==1){
            printf("<=%d is %d.\n", c, count);
        }
        else{
            printf(">=%d is %d.\n", c, count);
        }
    }
}

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