658 - ISeaTeL Cup 1213 Scoreboard

Time

2014/12/13 19:00:00 2014/12/13 22:00:00

Clarification

# Problem Asker Description Reply Replier Reply Time For all team

10300 - PA - 凱薩與加解密法   

Status  |  Limits Submit

Description

凱薩大帝是個好大喜功的人，總是喜歡四處征戰
搞的烽火四起，舉國上下民不聊生
終於凱薩手下的兩位大將軍看不過他的作風
決定偷偷密謀，打算一舉推翻凱薩
所以他們的訊息通通用了一個軍師推薦的加解密法，其行為如下
當加密鑰匙為 3 的時候
原文：ABCDEFG
密文：DEFGHIJ
說穿了就是對字母做位移的動作

當然，凱薩大帝也不是省油的燈
在攔截了一堆密文以後，他也發現了這個規律
再破解了兩位將軍的訊息後
成功的鎮壓了這次的反抗

驕傲的凱薩大帝為了凸顯自己的功績
除了把這種加解密法以自己的名字命名為「凱薩加密法」外
更把這起事件的記錄用這種方法加密

歷史學家為了破解出當時的文件
所以特別邀請你來幫忙
透過寫一隻程式來處理這套加解密法

Input

有多筆測試資料，每一行為一筆測資
測資有三個部分：Type Key Text
Type 有兩種：
    1. 'H' 代表你需要利用 Key 來加密 Text
    2. 'S' 代表你需要利用 Key 來解密 Text
Key 是一個三十二位元的非負整數 (2147483647 >= Key >= 0)
Text 全部由大寫字母組成，最大長度不超過 100 (|Text| <= 100)

Output

每筆測資請根據 Input 的 Type 來輸出一行答案，為加密或解密後的文字(皆為大寫英文字母)
請注意，輸出的時候不要忘記換行囉！

Sample Input  Download

Sample Output  Download

Tags




Discuss




10321 - PB - 教室排排坐   

Status  |  Limits Submit

Description


海帶意外發現在某些課堂上都有奇怪的趨勢
同學們除了很容易遲到/翹課以外
更喜歡從教室後面開始坐起
在發現這個趨勢以後
海帶希望能請你寫個一隻程式
來模擬大家入座時候的情形

Input

有多筆測試資料，每一行為一筆測資
每筆測資只會有一個數字 N (34 >= N >= 0)，代表課堂裡的人數

Output


請根據教室裡的人數並依照下面的圖形來印出座位的情形
+-------------------------+
|#.#.#.#.#.#.#.#.#.#.#...||
|#.#.#.#.#.#.#.#.#.#.#...||
|#.....................T.||
|#.#.#.#.#.#.#.#.#.#.#...||
+-------------------------+
# 代表是空位, P 代表一個人, T 代表教授
第一個人從圖形的最左上方開始入座
其他的人則是依序從上到下，從左到右入座
詳細請看範例測資。

注意！！！每筆測資後要空一行

Sample Input  Download

Sample Output  Download

Tags




Discuss




10322 - PC - 費式數列與矩陣快速冪   

Status  |  Limits Submit

Description

費式數列相信大家應該都略有耳聞
在要求的項數非常小的時候，我們可以很輕鬆的算出來
可是當我要連續問好幾個很大的項數呢？

一般來說，我們會先寫最簡單的寫法：$ fib_{n} = fib_{n-1} + fib_{n-2} $
但是這種寫法在每次的詢問都從 $n$ 開始往下算到直到終止條件 $fib_{1}$, $fib_{2}$為止
會非常浪費時間

發現太浪費時間以後，我們換個方法來優化
我們可以用很大的記憶體來把算過的都記起來
可惜的事，這樣還是會太慢（試想 n 是 2147483647 的時候）

在上面講的這兩種方法都是對的，只可惜速度差了點
因此，為了處理這次的問題
我們要教大家一個有趣的東西 - 矩陣快速冪

或許你心中會有個疑問，費式數列跟矩陣能扯上什麼關係？
我們把費式數列改寫一下：
$\begin{bmatrix} fib_{n+1} \\ fib_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} fib_{n-1} \\ fib_{n-2} \end{bmatrix}$
這樣是不是就能看到矩陣的性質出來了呢？

透過展開與矩陣的性質，我們可以再次改寫費式數列：
$\begin{bmatrix} fib_{n+1} \\ fib_{n} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^ {n} \times \begin{bmatrix} 1 \\ 0 \end{bmatrix}$
很明顯的可以發現，現在我們的程式變成是只要連乘 $n$ 次的 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ 就可以得到答案了！

事實上，如果遇到 $n$ 是 2147483647這麼大的話，連乘這麼多次還是不夠快。

因此，這時候就要來介紹我們的好朋友 - 快速冪
對一個 32-bit 的整數，我們可以用 bit map 的方式表現它
$0 => 00000000 00000000 00000000 00000000$
$1 => 00000000 00000000 00000000 00000001$
$2147483647 => 01111111 11111111 11111111 11111111$

這時候我們如果要算以下這個式子可以這樣算
$x^{n}, n = 87$
$87 => 00000000 00000000 00000000 01010111$
對 $87$ 而言，第 $0, 1, 2, 4, 6$ 個 bit 是 $1$
再次轉換一下這個方程式： $x^{87} = 1 \times x^{2^{0}} \times x^{2^{1}} \times x^{2^{2}} \times x^{2^{4}} \times x^{2^{6}}$ 因此可以推導出一個結論：
從第零個 bit 開始往前掃，如果該 bit 是 $1$ 就把當前的 $x$ 乘進去答案裡，接著再把 $x$ 平方，繼續到最後一個 bit，最後我們就能得到答案了。

說明到此結束，本題希望大家能實作這個矩陣快速冪來求出費式數列。

下面這個程式碼是再算普通次方版本的快速冪寫法，希望能幫助你理解快速冪的概念：

Input

有多筆測試資料，每一行為一筆測資
每筆測資只會有一個數字 $n (1 <= n < 2^{31})$，代表要求 $fib(n)$

Output

注意，因為數字可能會非常非常巨大
請千萬不要忘記把答案取 $mod$ $100000007$ 噢！

Sample Input  Download

Sample Output  Download

Tags




Discuss




10344 - PD - 海帶的書櫃   

Status  |  Limits Submit

Description

海帶是一個學富五車，讀書破萬卷的人。
他的書櫃總是擺滿了各門各類的圖書。
雖然海帶的腦容量無限，但是書櫃的空間有限。
隨著海帶知識的增長，書櫃所剩下的空間也日漸減少。
無私的海帶決定把他所有的書捐出來，建一棟圖書館分享他曾經學過的知識。
為了讓讀者輕易的找到自己想要的書，海帶採取了ISeaTeL式的圖書管理方式。
觀察力強的海帶發現到他所有的書名皆由三個英文單字所組成，於是便決定取書名三個英文單字的第一個字母來分門別類，並以統一以大寫表示。

以下為一些分類的範例：
Introduction to Loli => ITL
The Little Prince => TLP
The Blue Bird => TBB
A Christmas Carol => ACC
Impossible Time Limit => ITL
.
.
.
由上例不難看出Introduction to Loli 和 Impossible Time Limit 有著相同的ITL字首，根據ISeaTeL的圖書管理標準，它們應該會被歸為同一類。

- - - - - -

圖書館的完工在即，海帶卻遲遲尚未得知他的藏書應該分為幾類。
為了後續的作業方便，給你海帶的藏書清單，你能幫海帶算出那些書總共應該分成幾類嗎？


Input

測資的第一行有一個正整數 T (T<=15)，代表測試資料的組數。
每一組測試資料的第一行為一個正整數 N (N<=500000)，代表海帶的藏書總數。
接下來的 N 行，每一行代表一本書的書名。
書名以三個大小寫英文組成的英文單字表示，英文單字間以單個空白分隔。
每一行皆不會超過100個字元。

本題測資龐大，請使用快速的 I/O

Output

對於每一組測試資料，請輸出一行整數 Ｃ。
代表海帶的 N 本藏書可被歸為 Ｃ 個類別。

Sample Input  Download

Sample Output  Download

Tags




Discuss




10345 - ＰＥ　-　Ｓｕｂｍｉｔ　Ｔｈｅ　Ｃ   

Status  |  Limits Submit

Description

/*
 * But outer SPACE,
 * At least this far,
 * For all the fuss
 * Of the populace
 * Stays more popular
 * Than populous
 */
#include 
#include 
#include 
#include 
using namespace std;

struct edge {
    int to;
    char op, num;
} E;
map<int, edge> M;
int len;
char path[1000];

void V(char puzzle[3][3], int k) {
    int temp = puzzle[2][k];
    puzzle[2][k] = puzzle[1][k], puzzle[1][k] = puzzle[0][k], puzzle[0][k] = temp;
}

void H(char puzzle[3][3], int k) {
    int temp = puzzle[k][0];
    puzzle[k][0] = puzzle[k][1], puzzle[k][1] = puzzle[k][2], puzzle[k][2] = temp;
}

int toint(char puzzle[3][3]) {
    int state = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            state = state * 10 + puzzle[i][j];
    return state;
}

void toarray(char puzzle[3][3], int state) {
    for (int i = 2; i >= 0; i--)
        for (int j = 2; j >= 0; j--)
            puzzle[i][j] = state % 10, state /= 10;
}

void findpath(int state) {
    if (state == 123456789) {
        path[len] = 0;
        return;
    }
    edge e = M[state];
    path[len] = e.op;
    path[len + 1] = e.num;
    len += 2;
    findpath(e.to);
}

int main() {
    int state = 123456789;
    queue Q;
    Q.push(state);
    while (!Q.empty()) {
        state = Q.front();
        Q.pop();
        for (int i = 0; i < 3; i++) {
            char temp[3][3];
            int now;
            toarray(temp, state);
            V(temp, i);
            now = toint(temp);
            if (M.find(now) == M.end()) {
                E.to = state, E.op = 'V', E.num = '1' + i;
                M[now] = E;
                Q.push(now);
            }
            toarray(temp, state);
            H(temp, i);
            now = toint(temp);
            if (M.find(now) == M.end()) {
                E.to = state, E.op = 'H', E.num = '1' + i;
                M[now] = E;
                Q.push(now);
            }
        }
    }
  　int x;
    while (scanf("%d", &x), x) {
        int r = x;
        for (int i = 0; i < 8; i++)
            scanf("%d", &x), r = r * 10 + x;
        if (M.find(r) == M.end())
            puts("Not solvable");
        else {
            len = 0;
            memset(path, 0, sizeof(path));
            findpath(r);
            printf("%d", len / 2);
            if (len) {
                putchar(32);
                puts(path);
            }
        }

    }
    return 0;
}

Input

Output

Sample Input  Download

Sample Output  Download

Tags




Discuss




10360 - PF - Wrong Hole   

Status  |  Limits Submit

Description

Wrong Hole 是一個非常知名的演算法。
其演算法的精髓即為一個元素常常會映射到某一個元素。

經過海帶的神分析後發現，所有數字經過 Wrong Hole 演算法處理之後都會得到 10361 這一個 magic number！

現在給你一些數字，你能告訴我它經過 Wrong Hole 演算法所得到的結果嗎？

Input

有多筆測試資料，每一行為一筆測資
每筆測資只會有一個數字 X (0 < X < 10100)
題目保證數字的開頭必不為 0

Output

對於每一筆測資輸出一行整數
代表 X 經過 Wrong Hole 演算法運算之後所得到的結果

Sample Input  Download

Sample Output  Download

Tags




Discuss




10362 - PG - Logic Design   

Status  |  Limits Submit

Description

以下是三個常用的基本邏輯閘及其真值表

而在C語言中也有對應的位元運算子可使用
AND: &
OR: |
XOR: ^

現在，ISeaTeL團隊遇到了有點複雜的邏輯電路：


input為in, a0, b0, a1, b1
output為c0, c1, c2


現在我們會拿到兩個2-bit範圍內的數A, B，其以十進位表示
而將A, B轉換為二進位會有以下關係：
A = a1a0(二進位), B = b1b0(二進位)

經過這個邏輯電路後會得到一個3-bit範圍內的數C，其也以十進位表示
而將C轉換為二進位會有以下關係：
C = c2c1c0(二進位)

Ex:
         A = 1(十進位) = 01(二進位) => a1 = 0, a0 = 1
         B = 3(十進位) = 11(二進位) => b1 = 1, b0 = 1

        若in的訊號為0
        則最後output c2 = 1, c1 = 0, c0 = 0
                          => C = 100(二進位) = 4(十進位)

已知input中in的訊號永遠為0，請在給定的A, B下幫我們求出C的值

Input

第一行有一T<100代表測資數
以下每行為一筆測資，第一個數為A(十進制)，第二個數為B(十進制)，0 ≦ A,B ≦ 3，兩數間以單空格分隔開

Output

對於每筆測資，請輸出給定的A跟B經過邏輯電路後的結果C(十進制)，並換行

Sample Input  Download

Sample Output  Download

Tags




Discuss