c381: 聖經密碼

內容

1980 年代，以色列希伯來大學的數學家 Eliyahu Rips 和物理學家 Doron Witstum 利用電腦高速計算對比 (一套精密的數學運算模式)，挑選聖經時代以來的 32 位知名人物，結果發現他們的名字和出生與死亡日期在《創世記》中都是編在一起的。後來他們把整本希伯來文聖經原文去除了所有字間距，連貫成總長 304805 個字 (因為根據傳說，摩西從上帝手中接受的聖經就是「字字相連，無一中斷」)，採用電腦跳躍碼方式，在字串中尋找名字、單詞和詞組，最終找到了一系列相關信息。

現在，你也拿到了另一個不知名的古文獻，其中含有 n 個單字，你的任務是要把文中的文字「字字相連」，再依電腦所提供的 m 個整數 A1, A2, …, Am，從這個長字串找出第 A1, A2, …, Am 個字母併成一個單字。

例如
所收到的文獻為：the quick brown fox jumps over the lazy dog
連接成一個長字串：thequickbrownfoxjumpsoverthelazydog
電腦提供的線索為：33, 11, 34, 19, 21, 33, 30, 32
所併成的單字：doomsday

輸入

輸入檔中有多組測試資料。

每組測試資料的第一行是兩個正整數 n(<1000001), m(<101)。接下來的 n 行每行有一個英文單字，每個單字的長度不超過 100。最後一行有 m 個以空白隔開的正整數，所提供的數字不會超過字串的總長度。

當 n, m 均為 0 表示檔案結束，不須處理這組輸入。

9 8
the
quick
brown
fox
jumps
over
the
lazy
dog
33 11 34 19 21 33 30 32
0 0

輸出

對於每組測試資料，請輸出所擷取的文字於一行。

doomsday

解題思路

簡單的字串串接，因為資料龐大所以用一指標指向輸入位址，用 gets() 讀取輸入，再用 strlen() 取得該次輸入長度，將原指標和其相加即為下次輸入位置。

輸入完後查表輸出即可。

注意！ Visual Studio 等較新的編譯器會將 gets() 讀入字串時會將'\n'字元保留，但 ZeroJudge 不會。

完整程式碼

AC (13ms, 4.9MB)

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

char list[60000010], ans[101], * input;

int main()
{
    int n, m, tmp;
    while (scanf(" %d %d", &n, &m) == 2 && n + m)
    {
        getchar();
        input = list;
        int length = 0;
        for (int i = 0; i < n; i++)
        {
            gets(input);
            input += strlen(input);
        }
        for (int i = 0; i < m; i++)
        {
            scanf(" %d", &tmp);
            ans[i] = list[tmp - 1];
        }
        ans[m] = 0;
        puts(ans);
    }
    return 0;
}