Test Message

a053: Sagit's 計分程式

內容

sagit 是一位高中電腦老師，這學期正在教學生寫 C++程式。他的評分標準是依照每一位學生在 ZeroJudge 系統上解出的題數，去計算出對應的得分。為了不讓分數落差太大，因此他並不是採取每一題固定得分的方式，而是隨著題數增加而調整每題的得分。規則如下：

  1. 答對題數在 0~10 者，每題給 6 分。
  2. 題數在 11~20 者，從第 11 題開始，每題給 2 分。(前 10 題還是每題給 6 分)
  3. 題數在 21~40 者，從第 21 題開始，每題給 1 分。
  4. 題數在 40 以上者，一律 100 分。

如此一來，只要寫 10 題，就可以得到 60 分，寫 20 題，就可以得到 80 分，不過要得到滿分 100 分，則是要寫到 40 題，所以同學們分數的差距就大大地減少了。

不過問題來了，雖然學生們因為這樣的計分公式而大大地提升了及格率，但因為 sagit 有 600 多位學生，一個一個去計算真的是一件很吃重的工作，所以現在想請你幫他寫個程式解決這個問題。

輸入

每組測資只有一個整數 N (0<=N<=100)，代表學生在 ZeroJudge 系統上解出的題數。

10
40

輸出

印出該位同學的得分。

60
100

解題思路

簡單的 if else 判斷

完整程式碼

AC (2ms, 104KB)
#include <stdio.h>

int n;

int main()
{
    while (scanf(" %d", &n) == 1)
    {
        if (n < 10)
            printf("%d\n", n * 6);
        else if (n < 20)
            printf("%d\n", 60 + (n - 10) * 2);
        else if (n < 40)
            printf("%d\n", 80 + n - 20);
        else
            puts("100");
    }
    return 0;
}
閱讀更多

a040: 阿姆斯壯數

內容

所謂 Armstrong number 指的是一個 n 位數的整數，它的所有位數的 n 次方和恰好等於自己。

如；1634 = 14 + 64 + 34 + 44

請依題目需求在一定範圍內找出該範圍內的所有 armstrong numbers.

輸入

輸入包含兩個數字 n, m(n<m, n>0, m<=1000000)，代表所有尋找 armstrong number 的範圍

100 999
10 99

輸出

將所有範圍內的 armstrong number 依序由小到大輸出，如果沒有找到請輸出 none.

153 370 371 407
none

解題思路

先建好阿姆斯壯數表，之後用建好的表快速進行判斷。

完整程式碼

AC (23ms, 80KB)
#include <stdio.h>

int n, m , arms[20], aLen;
char hasAns;

inline int pow(int src, int p)
{
    int res = src;
    while (--p)
        res *= src;
    return res;
}

void SetArmsList()
{
    int now = 0, tmp[6], i, j, k, sum;
    for (i = 1; i < 1000000; i++)
    {
        now = i, j = k = sum = 0;
        for (; now; j++, now /= 10)
            tmp[j] = now % 10;
        for (; k < j; k++)
            sum += pow(tmp[k], j);
        if (sum == i)
            arms[aLen++] = i;
    }
}

int main()
{
    SetArmsList();
    while (scanf(" %d %d", &n, &m) == 2)
    {
        hasAns = 0;
        for (int i = 0; i < aLen && arms[i] <= m; i++)
        {
            if (arms[i] >= n)
                printf("%d ", arms[i]) , hasAns = 1;
        }
        if (hasAns)
            putchar('\n');
        else
            puts("none");
    }
    return 0;
}
閱讀更多

a038: 數字翻轉

內容

輸入任意數字，並將其數字全部倒轉

輸入

輸入包含一個整數，不超過 231

12345

輸出

輸出翻轉過後的數字

54321

解題思路

  1. 因為輸入會有多餘的 0，所以先用整數去接輸入值過濾掉前面多餘的 0
  2. 將整數用轉成字串後反轉
  3. 反轉後前面可能又會有多餘的 0，所以再將字串轉成整數後輸出

具體步驟為：輸入 → 轉整，去掉前面的 0 → 轉回字串 → 反轉字串 → 再轉整，去掉前面的 0(原始字串後面的 0) → 再轉回字串輸出。

完整程式碼

AC (2ms, 128KB)
#include <stdio.h>
#include <string.h>

int input;
char src[15], rev[15], * output;

int main()
{
    while (scanf(" %d", &input) == 1)
    {
        sprintf(src, " %d", input);
        output = &rev[14];
        for (int i = 0; src[i]; i++)
        {
            *output-- = src[i];
        }
        printf("%d\n", atoi(++output));
    }
    return 0;
}
閱讀更多

a034: 二進位制轉換

內容

還記得計算機概論嗎？還記得二進位嗎？

現在我們來計算一下將一個 10 進位的數字換成二進位數字

輸入

一個十進位的數值

3
6

輸出

輸出二進位制的結果

11
110

解題思路

  1. 取目標二進制的最低位元，放到輸出
  2. 將目標右移 1 位元
  3. 判斷目標是否為 0，是就輸出答案，大於 0 則回到(1.)

完整程式碼

AC (2ms, 64KB)
#include <stdio.h>

int n;
char out[35], * ans;
int main()
{
    while (scanf(" %d", &n) == 1)
    {
        ans = &out[34];
        while (n)
        {
            *ans-- = (n & 1) + '0';
            n >>= 1;
        }
        puts(++ans);
    }
    return 0;
}
閱讀更多

a024: 最大公因數(GCD)

內容

給定兩個數字，請得出它們的最大公因數

輸入

兩個整數 大於 0, 小於 231

12 15

輸出

最大公因數為一整數

3

解題思路

利用輾轉相除法的原理，不斷的取較大數除以較小數的餘數，直到較小數變成 0 為止，較大數即為最公因式。

完整程式碼

AC (2ms, 92KB)
#include <stdio.h>
#define SWAP(x, y) \
    x = x ^ y,     \
    y = x ^ y,     \
    x = x ^ y

int m, n;

int main()
{
    while (scanf(" %d %d", &m , &n) == 2)
    {
        while (n)
        {
            m %= n;
            SWAP(m, n);
        }
        printf("%d\n", m);
    }
    return 0;
}
閱讀更多

a022: 迴文

內容

迴文的定義為正向，反向讀到的字串均相同

如：abba , abcba … 等就是迴文

請判斷一個字串是否是一個迴文？

輸入

一個字串(長度 < 1000)

abba
abcd

輸出

yes or no

yes
no

解題思路

兩指針分別指向字串頭尾，一邊判斷是否相同，一邊慢慢向中心靠攏直至左指針>=右指針，如果有不同則用 break 跳離並輸出 no。

完整程式碼

AC (2ms, 92KB)
#include <stdio.h>
#include <string.h>

char str[1000] , isNot;

int main()
{
    while (scanf(" %s", str) == 1)
    {
        isNot = 0;
        for (int i = 0, j = strlen(str) - 1; i < j; i++, j--)
        {
            if (str[i] != str[j])
            {
                isNot = 1;
                break;
            }
        }
        if (isNot)
            puts("no");
        else
            puts("yes");
    }
    return 0;
}
閱讀更多

a021: 大數運算

內容

我們都知道電腦擅長於各種數字的計算，可是，我們又知道各種程式語言的變數又都有上限，比如整數隻有 216 或 232 個。如果要計算更大的數字時又該如何計算呢? 就交給聰明的您來解決囉。

以 + 代表加法
以 - 代表減法
以 * 代表乘法
以 / 代表除法 (取商數)

輸入

兩個正整數的運算式，運算元及運算子之間以空格隔開

2222222222222222222222222 + 1111111111111111111111111
2222222222222222222222222 - 1111111111111111111111111
2222222222222222222222222 * 1111111111111111111111111
2222222222222222222222222 / 1111111111111111111111111

輸出

兩個正整數的運算結果，總長度不超過 500 個位數

3333333333333333333333333
1111111111111111111111111
2469135802469135802469135308641975308641975308642
2

解題思路

用字串模擬直式運算，除法部分先將除數位移到和被除數同位，再用連續的大數減法模擬除法除回來。

完整程式碼

AC (2ms, 96KB)
#include <stdio.h>
#include <string.h>
#define MAX 550

typedef struct node
{
    int Length, First;
    char String[MAX + 1];
}Node;

Node input1, input2;
char op, nag;

void toDigit(Node* src)
{
    src->Length = strlen(src->String);
    int i = 0;
    for (; i < src->Length; i++)
        src->String[MAX - i] = src->String[src->Length - i - 1] - '0';
    src->First = MAX - i + 1;
    for (; MAX - i >= 0; i++)
        src->String[MAX - i] = 0;
}

char cmp(Node* lhs, Node* rhs)
{
    if (lhs->Length > rhs->Length)
        return 1;
    else if (lhs->Length < rhs->Length)
        return -1;
    else
    {
        int i = 0;
        while (lhs->String[lhs->First] == rhs->String[rhs->First] && i < lhs->Length)
            i++;
        if (lhs->String[lhs->First] >= rhs->String[rhs->First])
            return 1;
        else
            return -1;
    }
}

void cale(Node* lhs, Node* rhs, Node* sum, char op)
{
    switch (op)
    {
    case '+':
        for (int i = MAX; i >= lhs->First; i--)
        {
            sum->String[i] += lhs->String[i] + rhs->String[i];
            if (sum->String[i] >= 10)
            {
                sum->String[i - 1]++;
                sum->String[i] -= 10;
            }
        }
        if (sum->String[sum->First - 1] > 0)
            sum->First--;
        break;
    case '-':
        for (int i = MAX; i >= lhs->First; i--)
        {
            sum->String[i] += lhs->String[i] - rhs->String[i];
            if (sum->String[i] < 0)
            {
                sum->String[i - 1]--;
                sum->String[i] += 10;
            }
        }
        break;
    case '*':
        for (int i = 0; i < lhs->Length; i++)
        {
            for (int j = 0; j < rhs->Length; j++)
            {
                sum->String[MAX - (i + j)] += lhs->String[MAX - i] * rhs->String[MAX - j];
                if (sum->String[MAX - (i + j)] >= 10)
                {
                    sum->String[MAX - (i + j) - 1] += sum->String[MAX - (i + j)] / 10;
                    sum->String[MAX - (i + j)] %= 10;
                }
            }
        }
        break;
    case '/':
        if (nag) return;
        sum->First = MAX;
        int i = 0, gap = lhs->Length - rhs->Length;
        if (lhs->Length > rhs->Length)
        {
            for (; i < rhs->Length; i++)
                rhs->String[lhs->First + i] = rhs->String[rhs->First + i];
            for (; lhs->First + i <= MAX; i++)
                rhs->String[lhs->First + i] = 0;
            rhs->Length = lhs->Length;
            rhs->First = MAX - rhs->Length + 1;
        }
        for (int i = 0; i <= gap; i++)
        {
            for (int i = sum->First; i < MAX; i++)
                sum->String[i] = sum->String[i + 1];
            sum->String[MAX] = 0;
            while (cmp(lhs, rhs) == 1)
            {
                for (int i = MAX; i >= lhs->First; i--)
                {
                    lhs->String[i] -= rhs->String[i];
                    if (lhs->String[i] < 0)
                    {
                        lhs->String[i - 1]--;
                        lhs->String[i] += 10;
                    }
                }
                while (lhs->String[lhs->First] == 0 && lhs->Length > 1)
                    lhs->First++, lhs->Length--;
                sum->String[MAX]++;
            }
            for (int i = MAX; i > rhs->First; i--)
                rhs->String[i] = rhs->String[i - 1];
            sum->First--;
            rhs->String[rhs->First++] = 0;
            rhs->Length--;
        }
        break;
    default:
        break;
    }
}

int main()
{
    while (scanf(" %s %c %s", input1.String, &op, input2.String) == 3)
    {
        Node* lhs, * rhs, sum = { 0 };
        toDigit(&input1), toDigit(&input2);
        if (cmp(&input1, &input2) == 1)
            lhs = &input1, rhs = &input2, nag = 0;
        else
            lhs = &input2, rhs = &input1, nag = 1;
        cale(lhs, rhs, &sum, op);
        while (sum.String[sum.First] == 0)
            sum.First++;
        if (sum.First > MAX || (nag && op == '/'))
            puts("0");
        else
        {
            if (nag && op == '-')
                putchar('-');
            for (int i = sum.First; i <= MAX; i++)
                sum.String[i] += '0';
            puts(&sum.String[sum.First]);
        }
    }
    return 0;
}
閱讀更多

a017: 五則運算

內容

計算五則運算式的結果，包含加、減、乘、除、餘

輸入

輸入一個字串，其中包含運算元及運算子，為了方便讀取，所有的運算子及運算元均以空格區隔。

運算元為 0 ~231 -1 的整數

運算子則包含 + - * / % 及 ( )

運算時請注意先乘除後加減及() 優先運算的計算規則

2 + 3 _ 4
2 _ ( 3 + 4 ) * 5

輸出

輸出結果。為了避免小數點誤差，所有的運算過程都不會產生小數點，可以放心使用整數進行運算

14
70

解題思路

先把輸入的中序式轉成後序式，再解析後序式轉成整數。

完整程式碼

AC (1ms, 96KB)
#include <stdio.h>
#define MAX 10000

long long stack[MAX];
char infix[MAX], postfix[MAX], pTop;

char priority(char op)
{
    switch (op)
    {
    case '*': case '/': case '%':
        return 2;
    case '+': case '-':
        return 1;
    default:
        return 0;
    }
}

void inToPostfix(char* infix, char* postfix)
{
    int sTop = 0;
    char stack[MAX] = { 0 };
    pTop = 0;
    for (int i = 0; infix[i]; i++)
    {
        switch (infix[i])
        {
        case ' ':
            break;
        case '(':
            stack[++sTop] = infix[i];
            break;
        case ')':
            while (stack[sTop] != '(')
            {
                postfix[pTop++] = stack[sTop--];
            }
            sTop--;
            break;
        case '+': case '-': case '*': case '/': case '%':
            while (priority(infix[i]) <= priority(stack[sTop]))
            {
                postfix[pTop++] = stack[sTop--];
            }
            stack[++sTop] = infix[i];
            break;
        default:
            do
            {
                postfix[pTop++] = infix[i++];
            } while (infix[i] >= '0' && infix[i] <= '9');
            postfix[pTop++] = ' ';
            i--;
        }
    }
    while (sTop)
    {
        postfix[pTop++] = stack[sTop--];
    }
    postfix[pTop++] = '\0';
}

long long cale(long long lhs, long long rhs, char op)
{
    switch (op)
    {
    case '+': return lhs + rhs;
    case '-': return lhs - rhs;
    case '*': return lhs * rhs;
    case '/': return lhs / rhs;
    case '%': return lhs % rhs;
    }
    return -1;
}

long long postfixToInt(char* postfix)
{
    stack[0] = 0;
    int sTop = 0;
    char* now = postfix - 1;
    for (int i = 0; postfix[i]; i++)
    {
        if (postfix[i] >= '0' && postfix[i] <= '9')
        {
            stack[sTop] = stack[sTop] * 10 + (postfix[i] - '0');
        }
        else if (postfix[i] == ' ')
        {
            sTop++;
        }
        else
        {
            sTop--;
            stack[sTop - 1] = cale(stack[sTop - 1], stack[sTop], postfix[i]);
            stack[sTop] = 0;
        }
    }
    return stack[0];
}

int main()
{
    while (gets(infix) != NULL)
    {
        inToPostfix(infix, postfix);
        printf("%lld\n", postfixToInt(postfix));
    }
    return 0;
}
閱讀更多
1…2324252627