Test Message

c268: 簡單的三角形

內容

電仁今天以國手的身份來到了某間學校擔任特別講師。由於他覺得下面的學員們實在是太弱了，他決定先從簡單的三角形開始教起。”三角形是由三條線段順次首尾相連，或不共線的三點兩兩連接，所組成的一個閉合的平面圖形，是最基本的多邊形…”電仁發現即使使用了那麼淺白的文字說明，下面的學員們似乎還是不懂他在講甚麼。於是他想到了個好辦法，讓學生們實際拿東西拼成三角形就可以加深大家的印象了!電仁晚上回到自己的宿舍，決定從宿舍拿一些長條形的磁鐵隔天帶去學校給學生們拿來拼三角形(他在宿舍門前按門鈴時不小心釋放身體裡的電流把門鈴燒壞了，這又是另一個故事了…)

電仁拿了 n 根長磁鐵條前往學校，在路上時他想到一件可怕的事：會不會這些長磁鐵條中沒有任何 3 根磁鐵條能拼成一個三角形啊!畢竟構成三角形需要滿足一個基本性質，也就是任兩邊的和要大於第三邊。如果他只拿了長度為 1,5,10,20 的四根磁鐵，不管拿哪 3 條出來都無法構成三角形!由於電仁可能帶著許多磁鐵條，沒辦法迅速心算驗證，請你幫忙判斷電仁帶的 n 根磁鐵條中，有沒有任何 3 根可以構成一個三角形。

輸入

第一行有一個整數 T 代表有 T 筆資料。接下來兩行是第一筆資料：第一行有一個整數 n 代表電仁帶了幾根磁鐵條；第二行有 n 個整數 ai 代表每一根磁鐵條的長度。再接下來兩行是第二筆測試資料，依此類推。

(T≦5,1≦n≦5*107,1≦ai≦109)

3
3
3 4 5
4
1 5 10 20
3
10 10 10

輸出

輸出共 T 行。對於每一筆資料輸出一行代表這筆資料的 n 根磁鐵條中，有沒有任何 3 根可以構成一個三角形。有的話輸出 YES，否則輸出 NO。

YES
NO
YES

解題思路

先把當有 n 個磁鐵條時，能夠"不"組合成三角形的的最小長度組合列出來

n = 3 {1, 1, 2}
n = 4 {1, 1, 2, 3}
n = 5 {1, 1, 2, 3, 5}
n = 6 {1, 1, 2, 3, 5, 8}
…

發現最小組合剛好是費式數列，而當 n 為 45 時數列末項為 1134903170 (費式數列第 45 項)

n = 45 {1, 1, 2, 3, ….701408733, 1134903170}

由於輸入說明中磁鐵條最長為 109，但當有 45 條磁鐵條時，必須有長度大於 1134903170 的磁鐵條才可能"不"形成三角形，所以當 n >= 45 時必定會形成三角形。

既然已經知道在這題 n >= 45 時必定會形成三角形，那麼當 n >= 45 時就不必對該筆測資進行判斷，輸出 YES 後把該筆測資的磁鐵條長度資料全部捨棄掉讀取下筆測資即可。

完整程式碼

AC (38ms, 1.1MB)
#include <stdio.h>
#include <stdlib.h>
#define MAX 1048576

int t, n, list[50];
char s[MAX + 10], isTriangle;

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

int main()
{
    while (scanf(" %d", &t) == 1)
    {
        while (t--)
        {
            scanf(" %d", &n);
            if (n > 44)
            {
                getchar();
                do
                {
                    s[MAX - 2] = -1;
                } while (fgets(s, MAX, stdin)[MAX - 2] != EOF);
                puts("YES");
            }
            else
            {
                isTriangle = 0;
                for (int i = 0; i < n; i++)
                    scanf(" %d", &list[i]);
                qsort(list, n, sizeof(int), cmp);
                for (int i = 2; i < n; i++)
                {
                    if (list[i - 2] + list[i - 1] > list[i])
                    {
                        isTriangle = 1;
                        break;
                    }
                }
                puts(isTriangle ? "YES" : "NO");
            }
        }
    }
    return 0;
}
閱讀更多

c221: A+B problem (駭客題)

內容

給定兩個數字 a,b(0<=a,b<=10^12)，請輸出 a+b 的值

#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
cout<<a+b<<'\n';
}

請輸出一組合法的 a,b，使上述程式輸出錯誤答案

輸入

兩個數字 a,b(0<=a,b<=10^12)

1 1

輸出

a+b 的值

2

解題思路

簡單的程式觀念題，讓 int a 或 int b 超過 2147483647 (231-1) 產生溢位即可。

完整程式碼

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

int main()
{
    printf("100000000000 100000000000\n");
    return 0;
}
閱讀更多

c188: 拉瑪努金的逆襲

內容

在電影「天才無限家」(The Man Who Knew Infinity)裡，拉瑪努金到了劍橋拜入 Hardy(哈代)門下。師徒倆一個充滿創意與洞察，一個善於嚴謹驗證。兩個人合作無間，創造了許多突破性的進展。但，學術圈同儕並不太認同他的研究。

Hardy 為了找到更多人支持他，帶著拉馬努金找了劍橋組合學大師 MacMahon 挑戰組合數學。

問題如下：一個整數可以由另一些整數的和來表示。比如 4

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

總共可以找到 5 種方式來表達。計為 P(4) = 5

他們找了 MacMahon 挑戰 P(200) ，當兩人到約定時間，同時翻開手底答案時， MacMahon 大為震驚。從此對拉馬努金從原本不屑一顧，轉而大力支持他成為劍橋研究員。

問題來了，你還記得 P(200) 是多少嗎？在當年只能手算的年代裡，能算到 P(200)已經是大師級了，時至今日，電腦可以幫助我們大量運算，快速的得到答案。

所以請你用程式計算出來吧。

輸入

輸入有多行，每一行有一個正整數 n (n <= 200)，代表待組合的數。

0
1
200

輸出

請輸出共可以有多少種方法可以組合出這個數。也就是 P(n)

1
1
3972999029388

解題思路

先把前幾項列出來

P(1) = 1
P(2) = 1+1, 2
P(3) = 1+1+1, 2+1, 3
P(4) = 1*4, 2+1+1, 2+2, 3+1, 4
P(5) = 1*5, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5
P(6) = 1*6, 2+1+1+1+1, 2+2+1+1, 2+2+2, 3+1+1+1, 3+2+1, 3+3, 4+1+1, 4+2, 5+1, 6

不要看開頭和結尾(全部都是 1 和自己本身)觀察上面規律會發現

P(3) 2 + P(1)的那一項
P(4) 2 + P(2)的那兩項，3 + P(1)的那一項
P(5) 2 + P(3)的那三項，3 + P(2)的那兩項，4+P(1)的那一項。
…

之後同理類推，就可以列出下表

P P(1) P(2) P(3) P(4) Sum (所有 P + 2)
P(1) 0 0 0 0 1 (2 - 1)
P(2) 1 0 0 0 2 (3 - 1)
P(3) 1 0 0 0 3
P(4) 1 1 0 0 5
P(5) 1 1 1 0 7
P(6) 1 1 1 1 11

其中 P(1) 和 P(2) 是特例，
P(1) 的所有 1 相加和自己本身相同，所以要-1
P(2) 則是因為他的全部都是 1 和 1 + P(1) 重疊到了，所以也要-1

得到規律後按照規律建成表之後查表輸出答案即可。

完整程式碼

AC (2ms, 80KB)
#include <stdio.h>
#define MAX 201

int main()
{
    unsigned long long int list[MAX] = { 1 };
    int n;
    for (int i = 1; i < MAX; i++)
    {
        for (int j = i; j < MAX; j++)
            list[j] += list[j - i];
    }
    while (scanf(" %d", &n) == 1)
    {
        printf("%llu\n", list[n]);
    }
    return 0;
}
閱讀更多

c186: 蝸牛老師的點名單

內容

蝸牛老師新開了一門課，第一堂課時拿了一張白紙讓學生簽到。現在他需要用簽到單上的名字製作一份點名單。

輸入

輸入只有一行，含有 n 個 (1 ≤ n ≤ 30) 以空白隔開的學生名字。所有名字均由字母組成。

John Mary Steve David

輸出

將每個名字單獨輸出於一行。

John
Mary
Steve
David

解題思路

簡單的輸入輸出。

完整程式碼

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

int main()
{
    char s[100];
    while (scanf(" %s", s) == 1)
    {
        puts(s);
    }
    return 0;
}
閱讀更多

c185: Hey Jude

內容

《嘿，朱迪》（英語：Hey Jude）是一首披頭四樂團的歌曲，由保羅·麥卡尼創作，署名為藍儂-麥卡尼。該謠曲原名為「Hey Jules」，是麥卡尼為安慰約翰·藍儂之子朱利安在他父母離婚期間所作。《嘿，朱迪》開始於由麥卡尼人聲和鋼琴組成的主歌-過門結構，之後其他樂器陸續加入。第四段主歌過後，該歌曲在一段長度超過 4 分鐘的尾聲段中淡出。

現在，你也來寫首歌安慰其他的人吧！

輸入

輸入只有一行，含有你要安慰的人的名字。

You

輸出

輸出用所輸入的人名來取代「Hey Jude」中的「Jude」。

Hey You

解題思路

簡單的輸入輸出。

完整程式碼

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

int main()
{
    char s[1000] = "Hey ";
    while (gets(s + 4) != NULL)
    {
        puts(s);
    }
    return 0;
}
閱讀更多

c184: 盈虧互補

內容

畢達哥拉斯及其門徒稱 6 及 28 為完全數 (或稱為完美數)，因為它們都等於其真因數的和：

6 的真因數：1、2、3 其和為 1+2+3 = 6

28 的真因數：1、2、4、7、14 其和為 1+2+4+7+14 = 28

所以，一個正整數的真因數和等於它本身時，我們就稱它為完全數！

但是「人有悲歡離合，月有陰晴圓缺，此事古難全」，完全數也一樣。2016 年 1 月所發現的第 49 個完全數已經是 44,677,235 位數了。因此絕大多數的整數不是「盈數」就是「虧數」。

盈數：真因數和大於整數本身。例如 12 的真因數和 1+2+3+4+6 = 16，大於 12 本身。

虧數：真因數和小於整數本身。例如 15 的真因數和 1+3+5 = 9，小於 15 本身。

雖然大多數的整數都不是完全數，但是如果我們可以找到一對盈數與虧數，彼此互為對方的真因數和，那麼它們就可以透過互補而成為完美。我們稱這樣的一對盈數與虧數為「友好數」。

例如：
220 的真因數和 1+2+4+5+10+11+20+22+44+55+110 = 284
284 的真因數和 1+2+4+71+142 = 220

畢達哥拉斯曾說：「朋友是你靈魂的倩影，要像 220 與 284 一樣親密。」

輸入

輸入檔中有許多行，每行有一個數字 n (2 ≤ n ≤ 1000000)，n = 0 代表檔案結束，不需要對這個 0 輸出任何東西。

6
220
12
0

輸出

對輸入的每個數 n，如果 n 是完全數，請輸出 =n。否則請找出是否存在某個數 m，使得 n 和 m 是友好數。如果有，請輸出 m，，否則輸出 0。每個輸出都佔一行

=6
284
0

解題思路

求出除了自己的因數和，判斷該值是否為完美數，若是輸出、若否則再取該值除了自己的因數和，如果該因數和與輸入相同則為友好數。

求因數和時可以用開根號減少判斷次數。

完整程式碼

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

int factorSum(int src)
{
    int end = sqrt(src), res = end * end == src ? 1 - end : 1;
    for (int i = 2; i <= end; i++)
    {
        if (!(src % i))
            res += i + src / i;
    }
    return res;
}

int main()
{
    int n, fs;
    while (scanf(" %d", &n) == 1 && n)
    {
        fs = factorSum(n);
        if (fs == n)
            printf("=%d\n", n);
        else
            printf("%d\n", factorSum(fs) == n ? fs : 0);
    }
    return 0;
}
閱讀更多

b982: YoJudge 預練(空間之章)

內容

前幾天看到一隻 b961 YoJudge 怪獸，感覺太強大了，所以先打 Lo 練功，期盼來日再戰 YoJudge 怪獸。
　這次任務較簡單，將以下各種格式的空間單位統一轉換為位元(bit)。 以下 x,y,z,u,v,a 皆為非負整數
可能出現的時間單位格式如下：
xgb :代表 x*10^9*8 bits, 0<=x<1000
ymb :代表 y*10^6*8 bits, 0<=y<1000
zkb :代表 z*10^3*8 bits, 0<=z<1000
ubyte :代表 u*8 bits, 0<=u<1000
z.akb :代表 z kb 又 a*100 byte, 0<=z<1000, 0<=a<10
u.vbyte :代表 u byte 又 v bits, 0<=u<1000, 0<=v<8
vbit :代表 v 位元(bit), 0<=v<8
xgym :代表 x gb 又 y mb , 0<= x,y <1000
xgymzk :代表 x gb 又 y mb 又 z kb , 0<= x,y,z <1000
ymzk :代表 y mb 又 z kb , 0<= y,z <1000

輸入

多行直到 EOF，每行只有如上題目所說的空間格式，沒有空格

987gb
654mb
123kb
56byte
34.7kb
543.2byte
7bit
87g65m
567g34m210k
90m800k

輸出

將輸入的每一行換算為位元(bit)，輸出一行整數

7896000000000
5232000000
984000
448
277600
4346
7
696520000000
4536273680000
726400000

解題思路

b981 的類題只是這題數字更大了要用 long long 存。

因為數字太大所以用位元運算加速，其實直接用乘的也能過。

完整程式碼

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

inline long long Gbit(long long src)
{
    return (src << 33) - (src << 29) - (src << 25) - (src << 24) - (src << 21)
        - (src << 19) - (src << 16) - (src << 15) - (src << 13) - (src << 12);
}

inline long long Mbit(long long src)
{
    return (src << 23) - (src << 18) - (src << 17) + (src << 12) + (src << 9);
}

inline int Kbit(int src)
{
    return (src << 13) - (src << 7) - (src << 6);
}

inline int Bit(int src)
{
    return src << 3;
}

int main()
{
    long long bits;
    int tmp;
    char str[1000];
    while (scanf(" %s", &str) == 1)
    {
        int tmp = bits = 0;
        for (int i = 0; str[i] != 0; i++)
        {
            if (str[i] >= '0' && str[i] <= '9')
            {
                tmp = (tmp << 3) + (tmp << 1) + (str[i] - '0');
            }
            else
            {
                switch (str[i])
                {
                case 'g':
                    bits += Gbit(tmp), tmp = 0;
                    break;
                case 'm':
                    bits += Mbit(tmp), tmp = 0;
                    break;
                case 'k':
                    bits += Kbit(tmp), tmp = 0;
                    break;
                case 'y':
                    bits += Bit(tmp), tmp = 0;
                case 'i':
                    bits += tmp, tmp = 0;
                    break;
                case '.':
                    if (str[i + 2] == 'k')
                        bits += Kbit(tmp) + Bit((str[i + 1] - '0') * 100);
                    else
                        bits += Bit(tmp) + (str[i + 1] - '0');
                    i += 3, tmp = 0;
                    break;
                default:
                    break;
                }
            }
        }
        printf("%lld\n", bits);
    }
    return 0;
}
閱讀更多

b981: YoJudge 預練(時間之章)

內容

前幾天看到一隻 b961 YoJudge 怪獸，感覺太強大了，所以先打 Lo 練功，期盼來日再戰 YoJudge 怪獸。
　這次任務較簡單，將以下各種格式的時間單位統一轉換為毫秒。 以下 x,y,z,a,b 皆為非負整數
可能出現的時間單位格式如下：
xhour :代表 x 小時, 0<=x<24
xhym :代表 x 小時又 y 分鐘, 0<=x<24, 0<=y<60
xhymzs :代表 x 小時又 y 分鐘又 z 秒, 0<=x<24, 0<=y<60, 0<=z<60
ymin :代表 y 分鐘, 0<=y<60
ymzs :代表 y 分鐘又 z 秒, 0<=y<60, 0<=z<60
zs :代表 z 秒, 0<=z<60
z.as :代表 z 秒又 a*100 毫秒, 0<=z<60, 0<=a<10
bms :代表 b 毫秒, 0<=b<1000

輸入

多行直到 EOF，每行只有如上題目所說的時間格式，沒有空格

13hour
9h20m
23h17m57s
6min
34m50s
8s
19.7s
567ms

輸出

將輸入的每一行換算為毫秒，輸出一行整數

46800000
33600000
83877000
360000
2090000
8000
19700
567

解題思路

麻煩的字串處理，遇到關鍵字時將前面得到的數字按規則轉成毫秒。

完整程式碼

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

int main()
{
    int tmp, time;
    char str[1000];
    while (scanf(" %s", str) == 1)
    {
        time = tmp = 0;
        for (int i = 0; str[i] != 0; i++)
        {
            if (str[i] >= '0' && str[i] <= '9')
            {
                tmp = tmp * 10 + (str[i] - '0');
            }
            else
            {
                switch (str[i])
                {
                case 'h':
                    time += tmp * 3600000;
                    if (str[i + 1] == 'o')
                        i += 4;
                    break;
                case 'm':
                    if (str[i + 1] == 's')
                        time += tmp, i += 2;
                    else
                        time += tmp * 60000;
                    break;
                case 's':
                    time += tmp * 1000;
                    break;
                case '.':
                    time += tmp * 1000 + (str[i + 1] - '0') * 100, i += 2;
                    break;
                default:
                    break;
                }
                tmp = 0;
            }
        }
        printf("%d\n", time);
    }
    return 0;
}
閱讀更多

b971: 等差數列

內容

給你一個等差數列的首項、末項和公差，請輸出這個等差數列。

輸入

輸入只有一行，包含首項、末項和公差等三個整數。

1 9 2

輸出

輸出等差數列，每兩項之間以空白隔開。

1 3 5 7 9

解題思路

簡單的迴圈。

完整程式碼

AC (3ms, 96KB)
#include <stdio.h>

int main()
{
    int s, e, d;
    while (scanf(" %d %d %d", &s, &e, &d) == 3)
    {
        for (; s != e; s += d)
            printf("%d ", s);
        printf("%d\n", e);
    }
    return 0;
}
閱讀更多

b970: 我不說髒話 (續)

內容

文文上次說髒話被老師罰在黑板上寫 50 遍「I don’t say swear words!」，結果他只寫了 45 遍就跑出去玩了，以為老師不會發現。這次老師要求他罰寫的每一遍都要加上編號。

輸入

輸入只有一行，其中含有一個正整數 n，代表文文被罰寫的次數。

10

輸出

輸出 n 行「I don’t say swear words!」，每行前面要有流水編號。請參考範例輸出。

  1. I don’t say swear words!
  2. I don’t say swear words!
  3. I don’t say swear words!
  4. I don’t say swear words!
  5. I don’t say swear words!
  6. I don’t say swear words!
  7. I don’t say swear words!
  8. I don’t say swear words!
  9. I don’t say swear words!
  10. I don’t say swear words!

解題思路

簡單的迴圈。

完整程式碼

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

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        printf("%d. I don't say swear words!\n", i);
    }
    return 0;
}
閱讀更多
1…1516171819…27