a015: 矩陣的翻轉

2019-08-03

內容

已知一(m x n)矩陣 A，我們常常需要用到另一個將 A 中之行與列調換的矩陣。這個動作叫做矩陣的翻轉。舉例來說，若

A = [3 1 2]
       [8 5 4]
則
AT = [3 8]
        [1 5]
        [2 4]

現在請您針對所讀取到的矩陣進行翻轉。

輸入

第一行會有兩個數字，分別為列(row)<100 和行(column)<100，緊接著就是這個矩陣的內容

2 3
3 1 2
8 5 4

輸出

直接輸出翻轉後的矩陣

3 8
1 5
2 4

解題思路

讀取時案行讀取，存成一個二維陣列，輸出時案列輸出。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>

int row = 0, col = 0 , matrix[100][100];

int main()
{
    while (scanf(" %d %d", &row, &col) == 2)
    {
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
                scanf(" %d", &matrix[j][i]);
        }
        for (int i = 0; i < col; i++)
        {
            for (int j = 0; j < row; j++)
                printf("%d ", matrix[i][j]);
            putchar('\n');
        }
    }
    return 0;
}

a013: 羅馬數字

2019-08-02

內容

如果生活在數世紀之前的古羅馬，你應該用過 V 來表示五。V 和 5 這兩個符號都可以用來表示數目五。用來表示數目的符號稱作數字。而羅馬人用來表示數目的符號就是羅馬數字。

以下是七個基本的羅馬數字︰

羅馬數字	數目
I	1
V	5
X	10
L	50
C	100
D	500
M	1,000

所有其他的數目都是由這些數字組合而成。數目都是由左寫到右，通常值是等於組成的羅馬數字加起來。

例如十七可以表示為

X+V+I+I=XVII
10+5+1+1=17

表示羅馬數字可以使用減法來取代加法的規則。例如四可以不用四個一相加來表示 IIII，而採用五減一來表示 IV。利用這類規則，羅馬人能夠減化許多數目的表示方式，例如 IX 取代 VIIII 表示 9，及 CD 取代 CCCC 表示 400。

今日我們並不確定羅馬符號的起源為何。例如符號 V 的起源主要有兩個理論。有些學者認為五最早是用握拳、拇指在外的手勢來表示。最後以象形文字書寫而簡化為 V。

另一個理論認為 X 源自在 10 條線加上交叉線。因此五可以表示為 X 的一半，或是 V。

羅馬數字可以很容易地用來相加或相減，但算起乘除法就相當不順手。這就是為什麼現在羅馬數字並不常用的原因了。

問題
然而，羅馬數字還是經常用於書本章節及頁碼的編號。在這一題工作是讀入兩個正整數，然後輸出兩個數字差的絕對值。所有的數字都必須以羅馬數字來表示。而連續四個相同符號出現時，必須用減法規則來化簡之。

輸入

每個輸入檔中會有一個或以上的測試資料。每一行由兩個數字組成一筆測試資料，且所有數字將會小於 4,000。檔案最後會以符號 ## 表示結束。

I I
MM II
#

輸出

每筆測試資料的答案必須輸出到檔案中，並且換行。如果答案為零，則須輸出字串 ZERO。

ZERO
MCMXCVIII

解題思路

先將輸入的羅馬數字逐個轉成 int，並處理當前字元大於前一字元的例外情況，得到兩個整數相減後取絕對值即為答案，最後將答案用建好的表配合迴圈重新轉回羅馬數字輸出

完整程式碼

AC (1ms, 76KB)

#include<stdio.h>

typedef struct node
{
    char Str[3];
    int Val;
}Node;

int n, m, gap;
Node table[13] = { {"M" , 1000} , {"CM" , 900} ,{"D" , 500} ,{"CD" , 400}
                  ,{"C" , 100} ,{"XC" , 90} ,{"L" , 50} ,{"XL" , 40}
                  ,{"X" , 10} ,{"IX" , 9} ,{"V" , 5} ,{"IV" , 4} ,{"I" , 1} };

char strN[10], strM[10], strGap[10], * ptGap;

int toNum(char* src)
{
    char* pt = src - 1;
    int res = 0, prev, curr = 0;
    while (*(++pt))
    {
        prev = curr;
        if (*pt == 'I') curr = 1;
        else if (*pt == 'V') curr = 5;
        else if (*pt == 'X') curr = 10;
        else if (*pt == 'L') curr = 50;
        else if (*pt == 'C') curr = 100;
        else if (*pt == 'D') curr = 500;
        else if (*pt == 'M') curr = 1000;
        //
        if (prev < curr)
            res += curr - (prev << 1);
        else
            res += curr;
    }
    return res;
}

int main()
{
    while (scanf(" %s %s", strN, strM) == 2 && strN[0] != '#')
    {
        n = toNum(strN), m = toNum(strM);
        gap = n > m ? n - m : m - n;
        if (gap)
        {
            ptGap = strGap;
            for (int i = 0; i < 13; i++)
            {
                while (gap >= table[i].Val)
                {
                    char* tmp = table[i].Str - 1;
                    while (*(++tmp))
                        * ptGap++ = *tmp;
                    gap -= table[i].Val;
                }
            }
            *ptGap = '\0';
            puts(strGap);
        }
        else
        {
            puts("ZERO");
        }
    }
    return 0;
}

a010: 因數分解

2019-08-01

內容

各位在國小時都學過因數分解，都瞭解怎麼樣用紙筆計算出結果，現在由你來敎電腦做因數分解。

因數分解就是把一個數字，切分為數個質數的乘積，如 12=2^2 * 3

其中, 次方的符號以 ^ 來表示

輸入

一個整數, 大於 1 且小於等於 1000000

20
17
999997

輸出

一個字串

2^2 _ 5
17
757 _ 1321

解題思路

從 2 開始往上試除，若可以整除輸入值則將輸入值除以試除值，若無則試除值+1，如此循環直至試除值大於剩下的輸入值。

完整程式碼

AC (3ms, 92KB)

#include <stdio.h>

int num, count;
char output[10000], * oPt;

int main()
{
    while (scanf(" %d", &num) == 1)
    {
        oPt = output;
        for (int i = 2; i <= num; i++)
        {
            while (!(num % i))
            {
                num /= i;
                count++;
            }
            if (count)
            {
                if (count == 1)
                    oPt += sprintf(oPt, "%d * ", i);
                else
                    oPt += sprintf(oPt, "%d^%d * ", i, count);
                count = 0;
            }
        }
        *(oPt - 3) = 0;
        puts(output);
    }
    return 0;
}

a009: 解碼器

2019-08-01

內容

在密碼學裡面有一種很簡單的加密方式，就是把明碼的每個字元加上某一個整數 K 而得到密碼的字元（明碼及密碼字元一定都在 ASCII 碼中可列印的範圍內）。例如若 K=2，那麼 apple 經過加密後就變成 crrng 了。解密則是反過來做。這個問題是給你一個密碼字串，請你依照上述的解密方式輸出明碼。

至於在本任務中 K 到底是多少，請自行參照 Sample Input 及 Sample Output 推出來吧！相當簡單的。

輸入

每筆測試資料一列。每列有 1 個字串，就是需要解密的明碼。

1JKJ’pz’{ol’{yhklthyr’vm’{ol’Jvu{yvs’Kh{h’Jvywvyh{pvu5
1PIT’pz’h’{yhklthyr’vm’{ol’Pu{lyuh{pvuhs’I|zpulzz’Thjopul’Jvywvyh{pvu5

輸出

對每一測試資料，請輸出解密後的密碼。

*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.

解題思路

觀察輸入輸出發現每個輸出的 ASCII 碼皆是輸入的 ASCII 碼-7，故將每個字元的 ASCII 都-7 後輸出即為答案。

完整程式碼

AC (2ms, 80KB)

#include <stdio.h>

char s[10000], * c;

int main()
{
    while (gets(s) != NULL)
    {
        c = s - 1;
        while (*(++c))
            *c -= 7;
        puts(s);
    }
    return 0;
}

a007: 判斷質數

2019-08-12

內容

請判斷某數是否為質數

輸入

輸入有多組測試資料（以 EOF 結尾），每組測試資料佔一行，只包含一個整數 x, 2 ≦ x ≦ 2147483647。

測試資料至多有 200000 筆。

13
14

輸出

對於每組測試資料，如果輸入的 x 為質數，則輸出一行「質數」（不含引號）；否則輸出一行「非質數」（不含引號）。詳見範例測試資料。

質數
非質數

解題思路

先建值數表，由於一個數不包含自己的因數最大值為該數的開根號，而本題最大值為 2147483647，所以值數表最大值大於 √2147483647 (46341) 即可。

接下來每筆輸入都先判斷是否在值數表的範圍內，在範圍內就用 bsearch()查表，範圍外就從值數表第 1 項開始試除到大於 √輸入值為止。

完整程式碼

AC (0.5s, 200KB)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 47000

int primeList[5000], pLen, n;
char isPrime;

int cmp(const void* lhs, const void* rhs)
{
    return (*(int*)lhs - *(int*)rhs);
}

void SetPrimeList()
{
    char isNot[MAX] = { 0 };
    primeList[pLen++] = 2;
    for (int i = 3; i < MAX; i += 2)
    {
        if (isNot[i])continue;
        primeList[pLen++] = i;
        for (int j = i << 1; j < MAX; j += i)
            isNot[j] = 1;
    }
}

int main()
{
    SetPrimeList();
    while (scanf(" %d", &n) == 1)
    {
        isPrime = 0;
        if (n < MAX)
        {
            int* item = (int*)bsearch(&n, primeList, pLen, sizeof(int), cmp);
            isPrime = (item != NULL);
        }
        else
        {
            isPrime = 1;
            for (int i = 0, max = sqrt(n); primeList[i] <= max; i++)
            {
                if (!(n % primeList[i]))
                {
                    isPrime = 0;
                    break;
                }
            }
        }
        puts(isPrime ? "質數" : "非質數");
    }
    return 0;
}

a006: 一元二次方程式

2019-08-01

內容

求一元二次方程式 ax2+bx+c=0 的根

輸入

輸入三個整數 a, b, c

1 3 -10
1 0 0
1 1 1

輸出

Two different roots x1=?? , x2=??

Two same roots x=??

No real root

PS: 答案均為整數，若有兩個根則大者在前

Two different roots x1=2 , x2=-5
Two same roots x=0
No real root

解題思路

利用

s = b^2 - 4ac

判斷是否有實根，
若有則再判斷兩根

(-b + √s) / 2a
(-b - √s) / 2a

值是否相同

完整程式碼

AC (2ms, 140KB)

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

int a, b, c, s, sr, x1, x2;

int main()
{
    while (scanf("%d %d %d", &a, &b, &c) == 3)
    {
        s = (b * b) - (4 * a * c);
        if (s < 0)
        {
            printf("No real root\n");
            continue;
        }
        sr = sqrt(s);
        x1 = (-b + sr) / (2 * a);
        x2 = (-b - sr) / (2 * a);
        if (sr)
        {
            printf("Two different roots x1=%d , x2=%d\n", x1, x2);
        }
        else
        {
            printf("Two same roots x=%d\n", x1);
        }
    }
    return 0;
}

a005: Eva 的回家作業

2019-08-01

內容

Eva 的家庭作業裡有很多數列填空練習。填空練習的要求是：已知數列的前四項，填出第五項。因為已經知道這些數列只可能是等差或等比數列，她決定寫一個程式來完成這些練習。

輸入

第一行是數列的數目 t（0 <= t <= 20）。以下每行均包含四個整數，表示數列的前四項。約定數列的前五項均為不大於 105 的自然數，等比數列的比值也是自然數。

2
1 2 3 4
1 2 4 8

輸出

對輸入的每個數列，輸出它的前五項。

1 2 3 4 5
1 2 4 8 16

解題思路

利用等差數列每個值的差皆相同的特性判斷

完整程式碼

AC (2ms, 116KB)

#include <stdio.h>

int num[5], kase;

int main()
{
    scanf(" %d", &kase);
    while (kase--)
    {
        scanf(" %d %d %d %d", &num[0], &num[1], &num[2], &num[3]);

        if (num[1] - num[0] == num[3] - num[2])
        {
            num[4] = num[3] + num[1] - num[0];
        }
        else
        {
            num[4] = num[3] * num[1] / num[0];
        }
        printf("%d %d %d %d %d\n", num[0], num[1], num[2], num[3], num[4]);
    }
    return 0;
}

a004: 文文的求婚

2019-08-01

內容

文文為即將出國的珊珊送行，由於珊珊不喜歡別人給文文的那個綽號，意思就是嘲笑文文不夠聰明，但珊珊沒把握那個綽號是不是事實，所以珊珊決定考驗文文，於是告訴文文說，如果你能在我回國之前回答我生日那年是不是閏年，則等她回國後就答應他的求婚。文文抓抓腦袋想不出來，於是決定讓最擅長做運算的電腦來幫忙。

輸入

年份

1977

輸出

閏年或平年

平年

解題思路

先判斷 400 年，然後判斷 100 年，再判斷 4 年

完整程式碼

AC (2ms, 84KB)

#include <stdio.h>

int y;

int main()
{
    while (scanf(" %d", &y) == 1)
    {
        if (y % 400 == 0)
        {
            puts("閏年");
        }
        else if (y % 4 == 0 && y % 100 != 0)
        {
            puts("閏年");
        }
        else
        {
            puts("平年");
        }
    }
    return 0;
}

a003: 兩光法師占卜術

2019-08-01

內容

兩光法師時常替人占卜，由於他算得又快有便宜，因此生意源源不絕，時常大排長龍，他想算得更快一點，因此找了你這位電腦高手幫他用電腦來加快算命的速度。

他的占卜規則很簡單，規則是這樣的，輸入一個日期，然後依照下面的公式：
M=月
D=日
S=(M*2+D)%3

得到 S 的值，再依照 S 的值從 0 到 2 分別給與普通、吉、大吉等三種不同的運勢

輸入

月份及日期

1 1
1 2

輸出

運勢

普通
吉

解題思路

簡單的四則和邏輯判斷

完整程式碼

AC (2ms, 112KB)

#include <stdio.h>

int m, d, s;

int main()
{
    while (scanf(" %d %d", &m, &d) == 2)
    {
        s = (m * 2 + d) % 3;
        if (s == 0)
        {
            puts("普通");
        }
        else if (s == 1)
        {
            puts("吉");
        }
        else
        {
            puts("大吉");
        }
    }
    return 0;
}

a002: 簡易加法

2019-08-01

內容

請寫一個程式，讀入兩個數字，並求出它們的和。

輸入

每一組輸入有兩個整數，絕對值皆小於 106。

5 10
1 2

輸出

對於每組輸入，輸出該兩整數的和。

15
3

解題思路

簡單的加法

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int a, b;

int main()
{
    while (scanf(" %d %d", &a, &b) == 2)
    {
        printf("%d\n", a + b);
    }
    return 0;
}