Chapter II. 新手上路
實作技巧
常見輸入類型
作者baluteshih

簡介


在程式競賽中,從「標準輸入(Standard Input)」讀取資料後再將結果寫到「標準輸出(Standard Output)」是最為常見的一種實現解題的方式,照著格式輸出倒還簡單,但輸入的格式可能就有一些需要注意的地方了,以下我們會簡單介紹幾種常見的輸入類型,並講述大多選手會如何應對。

$T$ 筆測資型


有時候為了減少測試資料檔案數量,出題者會直接在單一測資檔內塞入多組測資,並用一個變數 $T$ 來表示測資數量。知名競程網站 Codeforces 常在比賽的前幾題使用這樣的輸入格式。

該類型的題目通常會要你輸入一個 $T$ 後,再用一個迴圈執行 $T$ 次讀取真正用來解題的輸入,而通常我們會用這樣的方式來處理:

int t;
cin >> t;
while (t--) {
    // do something
}

直接寫成 t-- 讓迴圈變得非常簡潔,原理是利用 -- 會「對變數減一、但回傳減一前的值」,也因此如果 t 輸入進來是 $1$ 的話,迴圈的判斷的第一次會讀到 $1$,第二次才會讀到已經被減一的 $0$ 進而終止,也就恰好執行了一次。

另外,有一個好習慣是直接寫一個函式把解題的部分獨立出來,例如:

while (t--) {
    solve();
}

這樣的好處是如果要在 solve() 的過程中宣告一個名字也是 t 的變數,就不會和外面的 t 撞名了。

輸入到 EOF 型


在比較古老的題目中,有些題目會要求選手輸入到「EOF」,這個 EOF 的全名是「End of File」,意思是檔案結尾。讀者可以想像輸入是從一個檔案讀取裡面的資料,那如果我們把資料讀完了,卻還繼續輸入的話,系統就會發出一個信號告訴程式說「已經讀完了!」,而這個信號就是我們的「EOF」。

一旦收到 EOF,程式就會採取相應的對策,若是以 C++ 的 cin 為例的話,他會在讀到 EOF 時讓判斷式可以判斷其為 false 好讓迴圈停止,讓我們直接看程式碼為例:

int n;
while (cin >> n) {
    // do something
}

在上述的程式碼裡面,我們直接寫上 while (cin >> n) 來不斷輸入值到 n 裡面,例如輸入 n 後再輸入 n 個數字的題目裡,因為 n 已經在判斷式裡面輸入完成,我們就可以接著在迴圈內部直接讀取後面的 n 個數字就好。

而讀到 EOF 後,cin >> n 就會直接在判斷式裡面轉為 false,並終止程式。

不過好像有個問題──自己測試的時候要怎麼輸入 EOF 呢?我們平常在終端機介面做測試輸入時,看上去是沒有所謂的「檔案結尾」的,也因此我們勢必得輸入些什麼來告訴程式「現在正是檔案結尾」。當然,不是直接輸入「EOF」三個字元這種東西(要是輸入正好就是 EOF 怎麼辦?),不過其實也相當容易,根據作業系統的差別,以下提供在常見作業系統下輸入 EOF 的方法:

作業系統輸入 EOF 的方法
WindowsCtrl + Z
macOSCtrl + D
LinuxCtrl + D

只要相對的按鍵按下去,就可以製造出 EOF 的效果囉!讀者可以自己試試看。

輸入到 0 型


這個同樣是一些古老的題目會有的格式,但相對 EOF 單純一點,就是直接在結束時輸入一個 0 以示終止。這樣的形式不一定會以 0 出現,也可能是 -1 等。

遇到這種格式,我們就可以這樣寫:

int n;
while (cin >> n && (n != 0)) {
    // do something
}

這裡主要仰賴的就是後面的 n != 0 這個判斷式,括號可加可不加。

另外,其實還可以更省略的改成

while (cin >> n && n) {
    // do something
}

這是因為 0 轉成布林值就是 false,所以讀到 0 自然就會停下來了。但如果是 -1 就不行啦,所以還千萬要小心不要顧著寫短而搞錯了。

不告訴你一行有幾個變數


有些題目會很過份的要你自己處理一行有幾個數字,例如輸入

3 1 4 1 5 9

要你把這若干個數字存到陣列裡,這時候可能一行的數字量是不一定的,我們也就沒辦法知道要輸入幾次才能停下來。

一個簡單的做法是使用 C++ 內建的 std::stringstream,來單獨轉換一整行變成一個輸入,具體可以這樣做使用:

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
    int n = 0, arr[100] = {};
    {
        string line;
        getline(cin, line);
        stringstream ss(line);
        int x;
        while (ss >> x)
            arr[++n] = x;
    }
}

要使用 stringstream,首先要先 #include <sstream>stringstream 在做的事情可以想成就是把字串變成一種仿造的輸入輸出系統,而在這裡我們就是直接把他當成一個輸入來用,並直接把原本輸入的 line 當成輸入檔在第 11 行餵給 stringstream

所以既然已經變成一個輸入系統了,就可以正常使用我們讀到 EOF 的方式來讀輸入啦!也就是我們 12 到 14 行在做的事情。注意到我們這裡在輸入時同時也巧妙的維護 n 的數值,所以輸入完畢後,n 自然就是數字個數,也同時讓 arr[1]arr[n] 是這 n 個數字了。

有關於讀取一整行

至於最前面的 getline 又是什麼呢?這是因為一般輸入數字的時候,讀到空格 cin 就會停下來了,所以我們需要調用一個額外能讀取一整行的函式,也就是第 10 行的 getline(cin, line),就是從 cin 不斷輸入、直到遇見一個換行後,再將目前讀到的所有字元存進 line 這個變數的意思,注意到這裡並不會一起把換行字元存進 line 裡。

一般的 cin 讀到空白或換行後會直接停下來,而不會刻意把後面的空白或換行讀取掉,但 getline 會這麼做。這就會出現一種狀況像當輸入是

1
1 2 3 4 5

時,若先執行一行 cin >> x 的話,在第一行的 1 後面的「換行字元」還會留著,這時候如果再直接執行 getline(cin, line)getline 就會直接看到換行字元,並直接停下來存空的東西進去 line 裡,造成問題。

想要正確的讀到第二行的話,可以這麼寫:

int x;
string line;
cin >> x >> ws;
getline(cin, line);

這裡 wscin 等輸入工具專用的特殊變數,寫出 cin >> ws 時,cin 就會不斷「讀掉空白字元」直到遇到一個非空白字元為止,也因此他會把上面 1 後面的換行字元讀掉後,留下第二行的開頭給後面的 getline

有關於多一層大括號

可以注意到上面的程式碼刻意的包了一層大括號形成 8 到 15 行的區域,這麼做是因為在輸入完畢後,stringstream 跟其相關的東西都再也用不到了,為了避免未來混用或撞名等問題,乾脆故意把他們寫成一個區域,這樣在 16 行以後就再也不會看到他們了。

如果中間不是空格

如果輸入長成這個樣子

3,1,4,1,5,9

那就不能直接轉成 stringstream 了,因為轉過去後還是只會讀到一樣的東西。但有一個偷吃步的方法可以解決這件事,那就是直接把這些逗號改成空格:

for (int i = 0; i < int(line.size()); ++i)
    if (line[i] == ',')
        line[i] = ' ';

轉完之後再比照前面的程式碼把 line 餵給 stringstream 就好了,是不是很單純呢?

習題


這裡提供一些需要處理輸入格式的習題給讀者熟悉上面的內容。

習題
格瑞哥里的煩惱 (t 行版)

輸入一個整數,判斷是不是閏年。以 $t$ 筆測資作為輸入格式。

習題
格瑞哥里的煩惱 (EOF 版)

輸入一個整數,判斷是不是閏年。以輸入到 EOF 作為輸入格式。

習題
格瑞哥里的煩惱 (0 尾版)

輸入一個整數,判斷是不是閏年。以輸入到 $0$ 為止作為輸入格式。

習題
升旗典禮抽背課文

首行輸入若干個以空格隔開的字串,代表由左至右的學生姓名,次行再輸入一個數字 $n$,代表要輸出從右邊數過來第 $n$ 個姓名。

習題
基礎排序 #1-1 (偶數排序)

每行輸入一串以逗號分格的數字序列,並單獨將輸入中的「偶數」們排序後以同樣的格式輸出。

輸入多行至 EOF 停止。