d153: 六、智力测验

內容 ：
    在Z先生的牧场中，做一头“光明的奶牛”不仅要称体重，还需要考智力。一年一度的智力测验要求极为严格，大约只有一半的奶牛可以通过。则于参加考试的奶牛数量众多，因此如何    划定智力测验“通过线”令Z先生头痛不已，于是他请你解这一难题。
    每只参加测验的奶牛都会得到一个分数（从0到100的整数），将所有的成绩按从高到低的顺序排好后，处在中间位置的分数将会作为“参考分数”提供给Z先生，以便让他决定“通过线”。如果参加测验的奶牛的数目是偶数的话，处于中间的位置的分数将会有两个，此时“参考分数”是其中较小的一个。

輸入說明 ：
    输入第一行是一个整数T（1 <= T <= 100)，表示测试数据的总数。
    每组测试数据的第一行是一个整数N（1 <= n <= 40000），表示参加测验的奶牛的数目。以下的N行依次给出N只奶牛测验的成绩，每行有一个0至100的正整数。

輸出說明 ：
    每组测试数据都输出一个答案，输出“参考分数”。

範例輸入 ：
1
6
97
45
78
62
81
79

範例輸出 ：
78

程式碼 ：

#include <stdio.h>

void swap(int *a, int *b)
{
    int c;
    c = *a;
    *a = *b;
    *b = c;
}

int partition(int arr[], int left, int right) 
{     
    int i, j, s;
    s = arr[right];
    i = left - 1;
     
    for(j = left; j < right; j++)
    {
        if(arr[j] > s)
        {
            i++;
            swap(&arr[i], &arr[j]);           
        }
    }

    swap(&arr[i+1], &arr[right]);
    return i+1;
}

void quicksort(int arr[], int left, int right) 
{     
    int q;     
    
    if(left < right) 
    {         
        q = partition(arr, left, right);         
        quicksort(arr, left, q-1);         
        quicksort(arr, q+1, right);     
    } 
}


int main(void) 
{
    int i, n, times, arr[40000];
    
    scanf("%d",&times);
    while(times--)
    {
        scanf("%d",&n);
        
        for(i=0; i<n; i++)
            scanf("%d",&arr[i]);
            
        quicksort(arr, 0, n-1);
                
        printf("%d\n",arr[n/2]);        
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=d153

d124: 3的倍数

內容 ：
    20XX年，pascal語言有多了一種新的整型int128。它能够運算10000位的超大數據。
    今天我們的任務就是：輸入一个類型為int128的數字ｎ（-10^10001 <= n <= 10^10001）。
    判斷它是否為3的倍數。

輸入說明 ：
    輸入檔中有多个數據，每組數據占一行，是輸入的數 n 。

輸出說明 ：
    輸出 n 是否为3的倍數。
    若是，輸出yes；若不是，輸出no。

範例輸入 ：
3
-7
0

範例輸出 ：
yes
no
yes

程式碼 ：

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

int main()
{
    int i, len, sum, isminus;
    char s[10020];
    
    while(scanf("%s",s)==1)
    {
        if(s[0] == '-')
            isminus = 1;
        else
            isminus = 0;
        
        sum = 0;
        len = strlen(s);
        
        for(i=isminus; i<len; i++)
            sum += s[i] - '0';
        
        if(sum % 3 == 0)
            printf("yes\n");
        else
            printf("no\n");
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=d124

a289: Modular Multiplicative Inverse

內容 ：
    一整數a 對模數n之模反元素是指滿足以下公式的整數b

    a^-1 ≡ b        (mod n)

    也可以寫成以下的式子

    ab ≡ 1        (mod n)

    現在給定兩個數字a,n，求一個最小正整數b，若不存在則輸出”No Inverse”

輸入說明 ：
    有多筆測資，每組第一行有兩個數字a,n，(1 ≦ a,n ≦ 100,000,000)

輸出說明 ：
    一個最小正整數 b，若不存在則輸出” No Inverse”

範例輸入 ：
79 62
96 47
49 28

範例輸出 ：
11
24
No Inverse

程式碼 ：

#include<stdio.h>

int main()
{
    int a, n, quotient, remainder, temp_a, temp_b, temp_c, temp_n;
    
    while(scanf("%d%d",&a,&n)==2)
    {
        if(n == 1)
        {
            printf("No Inverse\n");
            continue;
        }
        
        temp_n = n;
        temp_a = 0;
        temp_b = 1;
        temp_c = 1;
        
        while(1)
        {
            quotient = temp_n / a;
            remainder = temp_n % a;
            if(remainder == 0)
            {
                if(a == 1)
                    printf("%d\n",temp_c<0?(temp_c+n):temp_c);
                else
                    printf("No Inverse\n");
                break;
            }
            temp_n = a;
            a = remainder;
            
            temp_c = (temp_a - quotient*temp_b) % n;
            
            temp_a = temp_b;
            temp_b = temp_c;
        }
    }
    
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=a289

a282: 認真念書

內容 ：
    我最喜歡念書了！
    2000頁的課本耶！
    我下一頁應該要念哪一頁呢QQ

輸入說明 ：
    多組輸入以EOF結束
    每組輸入一開始有一個數字n(0 <= n <= 1000)代表你以前看過幾頁（可能重複）
    接下來n個1~2000的正整數代表你看過哪幾頁

輸出說明 ：
    一個數字，代表你下一頁應該看哪一頁
    也就是這本書裡面第一頁你沒看過的

範例輸入 ：
5
1 3 4 5 6
4
1 2 3 4
5
2 3 4 5 6

範例輸出 ：
2
5
1

程式碼 ：

#include <stdio.h>

int main(int argc, const char * argv[])
{
    int i,n,temp,arr[2001];

    while (scanf("%d",&n)==1) {

        for (i=1; i<2001; i++)
            arr[i] = 0;

        for (i=0; i<n; i++) {
            scanf("%d",&temp);
            arr[temp] = 1;
        }
        for (i=1; arr[i]==1; i++);
        printf("%d\n",i);
    }
    return 0;
}

http://zerojudge.tw/ShowProblem?problemid=a282