Test Message

d566: 秒殺率

內容

大韜自從成為題目管理員以後，
便積極的把平時靈機一動的想法出成題目上傳到 ZeroJudge。
但是他出的題目太簡單了，
題目總是通過率百分之百！

有一天他查看解題紀錄的時候發現，
同樣通過率百分之百的兩個題目，
有的會讓使用者第一次就 AC，
而其他可能大部分使用者會有幾次嘗試發生 WA、NA 以後才會 AC。

我們定義：
「如果一個使用者在第一次 Submit 就 AC 一個題目，就是他”秒殺”了這題」。
現在有一張從 ZeroJudge 上擷取的解題紀錄表，
而「秒殺率 = 秒殺人數 ÷AC 人數」，
大韜想請你分析一下這題的秒殺率是多少？

輸入

共計四個測資點，每個測資點只有一組測試資料。

第一行有整數 n(1<=n<=10000)，表示接下來的解題紀錄表有 n 行。
從第二行開始，每行有”解題者帳號”<空格>”解題狀況”。
解題者帳號由小於 30 字元的大寫字母、小寫字母、數字組成，並且大小寫視為不同。
解題狀況則有 AC、NA、WA、TLE、CE 五種
並且請注意，此處的解題紀錄”排在前面”的資料代表時間”越晚”(與 ZJ 實際狀況同)

30
BonBon CE
BonBon CE
BonBon CE
duckingod AC
duckingod AC
BonBon CE
BonBon CE
BonBon CE
BonBon CE
BonBon CE
e196819 TLE
e196819 NA
ws124310 AC
BonBon CE
BonBon CE
BonBon CE
BonBon CE
ws124310 NA
duckingod AC
BonBon CE
BonBon CE
BonBon CE
duckingod AC
duckingod AC
ws124310 NA
ws124310 TLE
e196819 CE
e196819 TLE
e196819 AC
jack1 AC

輸出

請輸出秒殺人數 ÷AC 人數，以百分比為單位。
(保證輸出的百分比會是整數，並且 AC 人數必定大於 0)

75%

解題思路

用 Hash Table 存使用者，每個使用者有 AC 和 FAC 兩個變數，分別代表 AC 過和第一次就 AC 兩種情況，接著按照題目規則存入使用者資訊即可。

注意！題目中越晚輸入的資料代表越早解題，以範例測資來說， jack1 是第一個解完的，再來才是 e196819。

完整程式碼

AC (4ms, 456KB)
#include <stdio.h>
#include <string.h>
#define BUKCNT 3371
#define BUKSIZ 10010

typedef struct
{
    unsigned int Next;
    char Name[30], AC, FAC;
} Node;

unsigned int buckets[BUKCNT], lastNode;
Node dict[BUKSIZ];

unsigned int Hash(char src[])
{
    unsigned int hash = 0;
    while (*src++)
    {
        hash ^= (~((hash << 11) ^ *(src) ^ (hash >> 5)));
        if (*src++) break;
        hash ^= ((hash << 7) ^ *(src) ^ (hash >> 3));
    }
    return (hash & 0x7FFFFFFF);
}

void addNode(char name[], char status[])
{
    int Key = Hash(name);
    int targetBuk = Key % 3371, currNode = buckets[targetBuk];
    while (currNode)
    {
        if (!strcmp(dict[currNode].Name, name))
        {
            if (status[0] == 'A')
                dict[currNode].AC = 1;
            dict[currNode].FAC = (status[0] == 'A');
            return;
        }
        currNode = dict[currNode].Next;
    }
    currNode = ++lastNode;
    dict[currNode].Next = buckets[targetBuk];
    buckets[targetBuk] = currNode;
    strcpy(dict[currNode].Name, name);
    dict[currNode].AC = dict[currNode].FAC = (status[0] == 'A');
}

int main()
{
    int n, FAC = 0, AC = 0;
    char name[30], status[4];
    scanf(" %d", &n);
    for (int i = n; i; i--)
    {
        scanf(" %s %s", name, status);
        addNode(name, status);
    }
    for (int i = n; i; i--)
    {
        if (dict[i].FAC)
            FAC += 100, AC++;
        else if (dict[i].AC)
            AC++;
    }
    printf("%d%%", FAC / AC);
    return 0;
}
閱讀更多

d563: 等值首尾和

內容

假設有一個陣列 x[]，它有 n 個元素，每一個都大於零；我們說 x[0]+x[1]+…+x[i]是個前段和(Prefix Sum)，而 x[j]+x[j+1]+…+x[n-1]則是個後段和(Suffix Sum)。請寫一個程式，求出 x[]中有多少組相同的前段和與後段和。

(上述文字、題目來自名題精選百則 - 冼鏡光著 - 儒林出版)

輸入

每個測資檔只有一組測資，共兩行。
第一行整數 n(1<=n<=100000)代表數列有幾個數字
第二行有 n 個正整數(A1,A2,…,An)，並且全部總合小於 2147483647，以空格隔開

–

範例測資 3,6,2,1,4,5,2 有三組等值首尾和，分別是：

11 = 3+6+2 = 2+5+4

12 = 3+6+2+1 = 2+5+4+1

23 = 3+6+2+1+4+5+2 = 2+5+4+1+2+6+3 (全部陣列的和，也代表答案至少有一組)

7
3 6 2 1 4 5 2

輸出

等值首尾和的數目

3

解題思路

兩指針分別指向陣列頭尾，然後比較累加的值是否相同，若是相同數量加一，反之則將累加較小的指針向另一邊偏移一個元素並加上該元素，如此循環直到某指針脫離陣列，輸出答案即可。

完整程式碼

AC (11ms, 472KB)
#include <stdio.h>

int list[100010];

int main()
{
    int n, sumL, sumR, count = 0;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++)
        scanf(" %d", list + i);
    sumL = list[0], sumR = list[n - 1];
    for (int l = 0, r = n - 1; l < n && ~r;)
    {
        if (sumL > sumR)
            sumR += list[--r];
        else if (sumR > sumL)
            sumL += list[++l];
        else
        {
            sumR += list[--r];
            sumL += list[++l];
            count++;
        }
    }
    printf("%d\n", count);
    return 0;
}
閱讀更多

d562: 山寨版磁力蜈蚣

內容

遊戲洛克人有一個 BOSS 叫做磁力蜈蚣。
現在山寨版磁力蜈蚣出現了，顯然設計得比本尊弱得很多：
它身上所有的節是由一個個附有數字的磁鐵所組成，
並且會暫時分解自己身上所有的節散落來攻擊玩家。
但是有一天它發現它身上的節居然隨著絕招的使用越來越少！

每次山寨版磁力蜈蚣將自己分解時，會讓所有磁鐵的排列順序倒轉。
例如原本是：1 2 3 4 5，那麼倒轉後便成了 5 4 3 2 1
但是現在每次分解前便會先遺失第一節磁鐵，
也就是原本：1 2 3 4 5，會遺失 1，
剩下的磁鐵倒轉後是 5 4 3 2
下次分解會遺失 5，剩下的倒轉成了 2 3 4
，再遺失 2，成了 4 3，最後剩下 3 便無法分解。

請利用程式來模擬這個過程。

輸入

共計三個測資點。
每組測資有兩行
第一行有整數 n(0<n<100)代表有幾個數,
第二行有 n 個數 A1…An(0<An<100)表示每個磁鐵上的數字

5
99 77 66 44 11
7
1 98 95 52 56 34 43

輸出

第一行請輸出最一開始的狀態
第二行開始，輸出「刪去第一項後，全部倒轉的結果」
直到數字只剩下一個為止

99 77 66 44 11
11 44 66 77
77 66 44
44 66
66

1 98 95 52 56 34 43
43 34 56 52 95 98
98 95 52 56 34
34 56 52 95
95 52 56
56 52
52

解題思路

用迴圈模擬題目敘述的流程即可。

完整程式碼

正常版

AC (0.3s, 116KB)
#include <stdio.h>

int main()
{
    int n, list[100], s, e;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        s = 0, e = n - 1;
        while (s <= e)
        {
            for (int i = e; i >= s; i--)
                printf("%d ", list[i]);
            putchar('\n');
            e--;
            for (int i = s; i <= e; i++)
                printf("%d ", list[i]);
            putchar('\n');
            s++;
        }
    }
    return 0;
}

輸出優化版

AC (0.1s, 100KB)
#include <stdio.h>

inline void putUInt(register unsigned int src, const char suffix)
{
    register unsigned int div;
    char buffer[12], * st = buffer + 10;
    *st = suffix, * (st + 1) = 0;
    do
    {
        *(--st) = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(st, stdout);
}

int main()
{
    int n, list[100], s, e;
    while (scanf(" %d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d", &list[i]);
        s = 0, e = n - 1;
        while (s <= e)
        {
            for (int i = s; i <= e; i++)
                putUInt(list[i], ' ');
            putchar('\n');
            s++;
            for (int i = e; i >= s; i--)
                putUInt(list[i], ' ');
            putchar('\n');
            e--;
        }
    }
    return 0;
}
閱讀更多

d561: 被秒殺的四捨五入

內容

拿氣溫來說，攝氏 15 度和攝氏 15.05 度的差距對人來說差異實在不大，有了數學概數的觀念，我們可以透過四捨五入法來得到一個數字的估計值，進而方便統計。
現在請你將一些小數利用程式來四捨五入。

輸入

共計三個測資點，每個測資檔中有多行小數 n(-1<=n<=1)，至多小數點以下有 100 位數

1.00000
0.5
0.715
0.1234567890
-0.995

輸出

請輸出四捨五入至小數點以下第二位的結果

1.00
0.50
0.72
0.12
-1.00

解題思路

簡單的字串處理，注意當測資小於 -0.005 時要輸出 0.000 而不是 -0.00。

完整程式碼

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

char buffer[110], * num;

int main()
{
    while (scanf(" %s", buffer) == 1)
    {
        num = buffer[0] == '-' ? buffer + 1 : buffer;
        if (num[3] == '\0')
            num[3] = '0', num[4] = '\0';
        else if (num[4] >= '5')
            num[3]++;
        for (int i = 3; ~i; i--)
        {
            if (num[i] > '9')
            {
                if (num[i - 1] == '.') num[i - 2]++;
                else num[i - 1]++;
                num[i] = '0';
            }
            else break;
        }
        num[4] = '\0';
        puts((num[0] == '0' && num[2] == '0' && num[3] == '0') ? "0.00" : buffer);
    }
    return 0;
}
閱讀更多

d559: 班號

內容

在北市師大附中，每個班都有一個屬於自己的班號，例如 188 班、1100 班…
而利用 C 語言的 printf 函式便能將整數變數輸出到螢幕上，
現在請你實作這個基本輸出。

輸入

測資中有多行整數 n(1<=n<=1261)

1252
1000

輸出

請對應每個 n 輸出一行：
‘C’ can use printf(“%d”,n); to show integer like XXXX
(請參考範例輸出)

‘C’ can use printf(“%d”,n); to show integer like 1252
‘C’ can use printf(“%d”,n); to show integer like 1000

解題思路

簡單的字串輸出。

完整程式碼

AC (1ms, 100KB)
#include <stdio.h>

int main()
{
    int n;
    while (scanf(" %d", &n) == 1)
    {
        printf("'C' can use printf(\"%%d\",n); to show integer like %d\n", n);
    }
    return 0;
}
閱讀更多

d555: 平面上的極大點

內容 d555: 平面上的極

在平面上如果有兩個點 ( x , y ) 與 ( a , b ),我們說 ( x , y ) 支配(Dominate)了

( a , b )這就是指 x ≧ a 而且 y ≧ b；用圖來看就是 ( a , b ) 座落在以 ( x , y ) 為右上角的
一點無的區域中。

對於平面上的任意一個有限點集合而言，一定存在有若干個點，它們不會被

集合中的內一點所支配，這些個數就構成一個所謂的極大集合。請寫一個程式，
讀入一個新的集合，找出這個集合中的極大值。

※簡單的說 若找不到一點在 ( x , y ) 的右上方,則 ( x , y ) 就要輸出

輸入

每個測資的第一行有一個數字 N ( 1 ≦ N ≦ 50,0000 )，代表接下來有 N 行，
每行上有兩個數字 x , y ( 0 ≦ X,Y ≦ 100000 )
分別代表一點的 X 軸座標，與 Y 軸座標。

11
0 8
1 10
3 4
4 6
4 9
5 8
6 9
7 5
8 7
9 8
10 6

輸出

請依照 X 軸的大小,由小輸出至大,剩餘的請參考 Sample Out。

Case 1:
Dominate Point: 4
(1,10)
(6,9)
(9,8)
(10,6)

提示

img1

解題思路

  1. 最極端的點 (x 或 y 最大的點) 必為支配點，因為沒有其他點比他的 x(或 y)大。

  2. 如果要判斷 a 點是否支配於 b 點，只要判斷 a 點的 x 和 y 是否皆小於 b 點即可。

所以藉由第一個規則，就可以先找出第一個支配點，再用第二個規則找出不被已知支配點支配的新支配點，如此循環找査直到所有點都被判斷過即可。

Ex:

  1. x 最大 (暫稱他為第一支配點)
  2. x 比第一支配點的 x 還小，但 y 比第一支配點的 y 大 (暫稱他為第二支配點)
  3. x 比第二支配點的 x 還小，但 y 比第二支配點的 y 大 (暫稱他為第三支配點)
  4. x 比第三支配點的 x 還小，但 y 比第三支配點的 y 大
  5. …

而由於已知第一支配點的 x 為本組數列之最大值，故判斷時只需要判斷 y 即可。

完整程式碼

AC (0.2s, 7.7MB)
#include <stdio.h>
#include <stdlib.h>
#define MAX 500000

typedef struct Point
{
    int x, y;
} Point;

Point list[MAX];

int cmp(const Point* lhs, const  Point* rhs)
{
    return (*rhs).x != (*lhs).x ? (*rhs).x - (*lhs).x : (*rhs).y - (*lhs).y;
}

int main()
{
    int n, len, yMax;
    for (int kase = 1; scanf(" %d", &n) == 1; kase++)
    {
        for (int i = 0; i < n; i++)
            scanf(" %d %d", &list[i].x, &list[i].y);
        qsort(list, n, sizeof(Point), cmp);
        yMax = list[0].y, len = 1;
        for (int i = 1; i < n; i++)
        {
            if (list[i].y > yMax)
            {
                list[len++] = list[i];
                yMax = list[i].y;
            }
        }
        printf("Case %d:\nDominate Point: %d\n", kase, len);
        for (int i = len - 1; ~i; i--)
            printf("(%d,%d)\n", list[i].x, list[i].y);
    }
    return 0;
}
閱讀更多

d550: 物件排序

內容

Excel 的排序，使用上真是有點麻煩
現在請你先對第一列先做排序，
若還是相同，再比較第二列 …類推 ( 由小 → 大)

輸入

每組輸入的第一行會有兩個數字 N M ( 1 ≦ N ≦ 1,0000 , 1 ≦ M ≦ 200 )

分別代表接下來有 N 行 , 每行上有 M 個數字 P ( 0 ≦ P ≦ 2147483647 )

8 3
1 1 2
1 0 1
1 1 1
1 3 2
1 3 5
2 1 1
2 3 2
2 1 4

輸出

請輸出排序後的結果。

1 0 1
1 1 1
1 1 2
1 3 2
1 3 5
2 1 1
2 1 4
2 3 2

解題思路

簡單的逐個比較排序，本題重點在於如何提升排序速度。

將輸入的資料存入一個二微陣列 L，再用一個一維指標陣列 S 去指向 L 的開頭，如此一來排序時只要交換 S[i] 指標指向的位置就能表示整個陣列 L[i] 的互換。

本題輸入輸出量很大，可以考慮做 IO 優化。

完整程式碼

正常版

AC (0.4s, 7.9MB)
#include <stdio.h>
#include <stdlib.h>
#define ROW 10000
#define COL 200

int n, m, list[ROW][COL], * sort[ROW];

int cmp(const int** lhs, const int** rhs)
{
    for (int i = 0; i < m; i++)
    {
        if ((*lhs)[i] > (*rhs)[i])
            return 1;
        else if ((*lhs)[i] < (*rhs)[i])
            return -1;
    }
    return 0;
}

int main()
{
    for (int i = 0; i < ROW; i++)
        sort[i] = list[i];
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                scanf(" %d", &list[i][j]);
        }
        qsort(sort, n, sizeof(int*), cmp);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                printf("%d ", sort[i][j]);
            putchar('\n');
        }
    }
    return 0;
}

IO 優化版

AC (0.1s, 8.9MB)
#include <stdio.h>
#include <stdlib.h>
#define BUFSIZ 1048576
#define ROW 10000
#define COL 200

int n, m, list[ROW][COL], * sort[ROW];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int cmp(const int** lhs, const int** rhs)
{
    for (int i = 0; i < m; i++)
    {
        if ((*lhs)[i] > (*rhs)[i])
            return 1;
        else if ((*lhs)[i] < (*rhs)[i])
            return -1;
    }
    return 0;
}

void putUInt(register int src, const char suffix)
{
    char buf[12], * bufTop = buf + 10;
    register int div;
    buf[10] = suffix, buf[11] = 0;
    do
    {
        *--bufTop = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(bufTop, stdout);
}

int main()
{
    for (int i = 0; i < ROW; i++)
        sort[i] = list[i];
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                readUInt(&list[i][j]);
        }
        qsort(sort, n, sizeof(int*), cmp);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                putUInt(sort[i][j], ' ');
            putchar('\n');
        }
    }
    return 0;
}
閱讀更多

d532: 文文的求婚 (三)

內容

經過了一番苦練之後，文文終於可以很流利地用英文回答有關閏平年的問題，心想珊姍現在應該會答應他的求婚了吧。當文文開心地來找珊珊時，珊珊為了確保她後半輩子的幸福，給了他另一個問題：”I will marry you if you can tell me how many leap years there are between year a and year b, inclusive.” 意思是「如果你可以告訴我西元 a 年和 b 年之間 (含) 有幾個閏年，我就嫁給你！」

輸入

輸入只有一行，含有兩個由空白隔開的整數 a, b (1752<a≤b≤10000)。

2012 2016

輸出

請輸出一個整數代表 a 年與 b 年之間有幾個閏年。

2

解題思路

簡單的迴圈配合條件判斷。

完整程式碼

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

int main()
{
    int n, m, cont = 0;
    scanf(" %d %d", &n, &m);
    for (int i = n; i <= m; i++)
    {
        if (!(i % 400) || (i % 100) && !(i % 4))
            cont++;
    }
    printf("%d\n", cont);
    return 0;
}
閱讀更多

d527: 程式設計師的面試問題(三)

內容

在一條街上有五棟不同顏色的房子由左而右是第 1 棟到第 5 棟，
各住著不同國籍的人，各喝不同的飲料，各抽不同牌子的菸，各養不同的寵物，
給你線索和人事物的編號，請以特定格式輸出符合所有線索的所有可能。

線索：

  1. 英國人住在紅色的房子。
  2. 瑞典人養狗。
  3. 丹麥人喝茶。
  4. 綠色房子在白色房子的左邊。
  5. 綠色房子的主人喝咖啡。
  6. 抽寶馬香菸的人養鳥。
  7. 黃色房子的主人抽七星香菸。
  8. 中間那棟房子(第 3 棟)的主人喝牛奶。
  9. 挪威人住在第 1 棟房子。
  10. 抽長壽香菸的人住在養貓的人的隔壁。
  11. 養馬的人住在抽七星香菸的人的隔壁。
  12. 抽萬寶路香菸的人喝啤酒。
  13. 德國人抽 Dunhill 香菸。
  14. 挪威人住在藍色房子的隔壁。
  15. 抽長壽香菸的人有一個喝水的鄰居。

數字編號：

  1. 紅色房子
  2. 綠色房子
  3. 白色房子
  4. 黃色房子
  5. 藍色房子
  6. 英國人
  7. 瑞典人
  8. 丹麥人
  9. 挪威人
  10. 德國人
  11. 茶
  12. 咖啡
  13. 牛奶
  14. 啤酒
  15. 水
  16. 寶馬香菸
  17. 長壽香菸
  18. 萬寶路香菸
  19. Dunhill 香菸
  20. 七星香菸
  21. 狗
  22. 鳥
  23. 貓
  24. 馬
  25. 魚

輸入

無

無

輸出

輸出的特定格式：
House Color Nation Drink Cigarette Pet
H1 <填數字> 9 <填數字> <填數字> <填數字>
H2 <填數字> <填數字> <填數字> <填數字> <填數字>
H3 <填數字> <填數字> <填數字> <填數字> <填數字>
H4 <填數字> <填數字> <填數字> <填數字> <填數字>
H5 <填數字> <填數字> <填數字> <填數字> <填數字>

以上述格式輸出，標頭要輸出，每一欄位為 10 個字元(包含標頭)，靠右對齊。
<填數字>代表要配合線索求出該填的數字編號。
比如 9.挪威人住在第 1 棟，所以我已經把 Nation 對應到 H1(第 1 棟房子)的欄位填上 9(挪威人)。
請你完成這個表格，且要輸出符合所有線索並且可以完成這個表格的所有可能。
輸出並不包含空白行，連標頭一直輸出即可。

無

解題思路

DFS 窮舉所有可能，並按照題意進行剪枝。

本題困難點在於窮舉，因為要在窮舉所有物品的遞迴中再窮舉共 5 次房子的排列組合，而且又要保留進度，所以必須要用 5 個迴圈來窮舉房子的排列組合，具體方法見下方程式碼。

完整程式碼

AC (2ms, 80KB)
#include <stdio.h>
#define Color 0
#define Nation 1
#define Drink 2
#define Cigar 3
#define Pet 4

int house[7][5], isUse[7][5];

char dfs(int obj)
{
    if (obj == 1)
    {
        for (int i = 1; i <= 5; i++)
        {
            if ((house[i][Color] == 2 && house[i + 1][Color] != 3))
                return 0;
        }
    }
    if (obj == 2)
    {
        for (int i = 1; i <= 5; i++)
        {
            if ((house[1][Nation] != 9) || (house[i][Nation] == 6 && house[i][Color] != 1) ||
                (house[i][Nation] == 9 && !(house[i - 1][Color] == 5 || house[i + 1][Color] == 5)))
                return 0;
        }
    }
    else if (obj == 3)
    {
        for (int i = 1; i <= 5; i++)
        {
            if ((house[3][Drink] != 13) || (house[i][Nation] == 8 && house[i][Drink] != 11) ||
                (house[i][Color] == 2 && house[i][Drink] != 12))
                return 0;
        }
    }
    else if (obj == 4)
    {
        for (int i = 1; i <= 5; i++)
        {
            if ((house[i][Color] == 4 && house[i][Cigar] != 20) || (house[i][Cigar] == 18 && house[i][Drink] != 14) ||
                (house[i][Nation] == 10 && house[i][Cigar] != 19) || (house[i][Cigar] == 17 && !(house[i - 1][Drink] == 15 || house[i + 1][Drink] == 15)))
                return 0;
        }
    }
    else if (obj == 5)
    {
        for (int i = 1; i <= 5; i++)
        {
            if ((house[i][Nation] == 7 && house[i][Pet] != 21) || (house[i][Cigar] == 16 && house[i][Pet] != 22) ||
                (house[i][Cigar] == 17 && !(house[i - 1][Pet] == 23 || house[i + 1][Pet] == 23)) ||
                (house[i][Pet] == 24 && !(house[i - 1][Cigar] == 20 || house[i + 1][Cigar] == 20)))
                return 0;
        }
        return 1;
    }
    const int ft = obj * 5;
    char isUse[7] = { 0 };
    for (int t1 = 1; t1 <= 5; t1++)
    {
        house[1][obj] = ft + t1;
        isUse[t1] = 1;
        for (int t2 = 1; t2 <= 5; t2++)
        {
            if (isUse[t2]) continue;
            house[2][obj] = ft + t2;
            isUse[t2] = 1;
            for (int t3 = 1; t3 <= 5; t3++)
            {
                if (isUse[t3]) continue;
                house[3][obj] = ft + t3;
                isUse[t3] = 1;
                for (int t4 = 1; t4 <= 5; t4++)
                {
                    if (isUse[t4]) continue;
                    house[4][obj] = ft + t4;
                    isUse[t4] = 1;
                    for (int t5 = 1; t5 <= 5; t5++)
                    {
                        if (isUse[t5]) continue;
                        house[5][obj] = ft + t5;
                        if (dfs(obj + 1))
                            return 1;
                        break;
                    }
                    isUse[t4] = 0;
                }
                isUse[t3] = 0;
            }
            isUse[t2] = 0;
        }
        isUse[t1] = 0;
    }
    return 0;
}

int main()
{
    dfs(0);
    printf("     House     Color    Nation     Drink Cigarette       Pet\n");
    printf("        H1% 10d% 10d% 10d% 10d% 10d\n", house[1][0], house[1][1], house[1][2], house[1][3], house[1][4]);
    printf("        H2% 10d% 10d% 10d% 10d% 10d\n", house[2][0], house[2][1], house[2][2], house[2][3], house[2][4]);
    printf("        H3% 10d% 10d% 10d% 10d% 10d\n", house[3][0], house[3][1], house[3][2], house[3][3], house[3][4]);
    printf("        H4% 10d% 10d% 10d% 10d% 10d\n", house[4][0], house[4][1], house[4][2], house[4][3], house[4][4]);
    printf("        H5% 10d% 10d% 10d% 10d% 10d\n", house[5][0], house[5][1], house[5][2], house[5][3], house[5][4]);
    return 0;
}
閱讀更多

d526: Binary Search Tree (BST)

內容

某次測驗的第 29 題

內容如下 :
將下列建值輸入，直接建立一個二元搜尋樹， 368,115,121,88,741,762,801,34,41,511,60,欲找建值為 34 的節點，從 368 節點為第一次起算，需要做幾次比較 ?

(A) 2 (B) 3 (C) 4 (D) 5

只是想請你建出一個二元搜尋樹，並輸出此樹的前序搜尋 (中左右)

輸入

輸入的每一行有一個數字 N ( 1 ≦ N ≦ 1000 )

接下來會建入 N 個數字 M ( 1 ≦ M ≦231-1 ) ，且沒有數字會重複

11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

輸出

輸出該樹的前序搜尋結果。

368 115 88 34 41 60 121 741 511 762 801
5 2 4 10 9 15

解題思路

實作二分搜索樹。

完整程式碼

AC (28ms, 128KB)
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int value;
    struct Node* lhs, * rhs;
}Node;

inline Node* newNode(int value)
{
    Node* res = malloc(sizeof(Node));
    res->value = value;
    res->lhs = res->rhs = NULL;
    return res;
}

inline void setNode(Node* now, int value)
{
    for (;;)
    {
        if (value < now->value)
        {
            if (now->lhs)
                now = now->lhs;
            else
            {
                now->lhs = newNode(value);
                break;
            }
        }
        else
        {
            if (now->rhs)
                now = now->rhs;
            else
            {
                now->rhs = newNode(value);
                break;
            }
        }
    }
}

void serchNode(Node* now)
{
    if (now)
    {
        printf("%d ", now->value);
        serchNode(now->lhs);
        serchNode(now->rhs);
        free(now);
    }
}

int main()
{
    int n, tmp;
    while (scanf(" %d", &n) == 1)
    {
        Node root = { 0 };
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &tmp);
            setNode(&root, tmp);
        }
        serchNode(root.rhs);
        putchar('\n');
    }
    return 0;
}
閱讀更多
1…678910…27