# 落差與常識的補完

本篇著重在介紹一些寫 OJ 題目時，一些必要的知識或技巧。
這些可能一般在上課或自學時，並不會接觸到，
但缺乏這些可能會在解 OJ 的題目時，遇上一些困難。

## 迴避莫名其妙的 TLE

如果你的做法沒有問題，那可能是來自 C++ 的 IO 因為一些原因導致非常沒有效率。

使用 cin/cout 處理輸出輸入時，
可在 main() 大括號中，最前面加入這兩行：

ios::sync_with_stdio(0);
cin.tie(0);

可以大幅提升 cin / cout 的效能。
主要是 C++ 的 IO 會因 buffered IO 的處理上需要牽就 C 的 IO，如果選擇放棄與 C 的共存就能找回原本該有的速度。

不這麼做的話，很容易**因為 cin / cout 過慢，導致 TLE**。

:::warning
這將會關閉 cin/cout 與 scanf()/printf() 之間的同步，導致無法並用。
:::

#include <iostream>
using namespace std;

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// 你真正的 code
	return 0;
}

:::warning
當你加入這兩行後，可能導致在某些 IDE（例如 Dev-CPP 或 Code::Blocks）手動測試時行為會改變。而 CP Editor 不受此影響。
可以在上傳前才加上去，或者平時將它們註解掉。
:::

### endl

`endl` 用在 cout 輸出換行時，它會比單純的 `\n` 做更多細節處理，平常使用是更安全，但在競程反而會拖慢效率。
拖慢效率的主因是 `endl` 自帶 flush。

在競程，必須用 `cout << '\n';` 或 `cout << "\n";` 來輸出換行。

:::spoiler 閱讀更多細節
### sync_with_stdio

主要是因為硬碟的硬體架構上，擅長讀入連續的資料，但不擅長跳來跳去。
然而，電腦通常會同時執行多個程式，透過不斷的切換使得看起來像同時執行。

因此你程式連續輸入兩個 int，看似資料連續，實際可能輸入完一個後，就先切到別的程式去輸入其它東西，再切回來又得命令硬碟跳回原本位置。除了速度慢以外，也會減少硬碟壽命。

一個處理方式就是 Buffered IO，每次輸入時預先讀個一大塊存起來，例如 $4$ KB（$4096$ 個字元），在這些資料處理完前，就不用再次向硬碟請求輸入資料。

但是若輸入間沒法講好，可能 scanf() 預讀掉個 $8000$ 字，cin 不知道又去硬碟再往下讀，那中間被預讀掉的就被跳過去了，如果有對預讀的地方做出修改時另一方也不會被通知。

cin 因為這些溝通上的關係變得十分緩慢，但可以混用不會出事；關掉同步後混用就會出事，但 cin 解放後會回到原本該有的速度。

輸出同理，會先放在記憶體中，待累積至一定的量才真正寫入，因此 cout 也需要和 printf() 去做同步。

暫存這些預讀或待寫入資料的地方，稱為 buffer。

另，stdio 指的是 C 的輸出輸入函式庫（`<stdio.h>`）。

### flush

flush 用於強制將未寫入 buffer 清空並真正寫入硬碟。

endl 頻繁地（至少每一行為單位）清空 buffer 並寫入硬碟，如上述原因會因硬碟物理上的移動導致非常沒有效率。等於 buffer 幾乎沒有生效。

### cin.tie

這是用於互動式的執行方式中，使用者一邊手動輸入時，程式讀完必要資料就馬上輸出結果，使用者才能馬上看到並做出不同回應。

但資料本該是暫存在 buffer 沒有顯示到畫面上的，除非用 flush 讓它清空 buffer 顯示出來。為了讓它每次輸入都做出反應，因此每次有 cin 發生，就會去做 flush 讓結果先跑出來。

這件事在競程上因為全部執行完才會一次對答案的關係，顯得沒有意義，只會導致頻繁而不必要的 flush 拖慢效能，因此將 cin 和 cout 為實現互動性而綁在一起互相 flush 的特性關閉，就會變快。
:::

## 多重輸入

UVa 通常沒特別講的話，默認是有多組測試資料的。

通常有三種多重輸入：

- 一開始輸入一個整數，告訴你總共有幾組測試資料。
- 告訴你當某一組輸入為多少（比如說 0）時，代表輸入結束
- 什麼也不講，讀到 EOF 為止。

使用 while 可以反覆輸入，直到碰到 End Of File (EOF) 為止。
以下示範如何反覆輸入 2 個 int 直至 EOF 為止。

int a, b;
while (cin >> a >> b)
{
	// ...
}

面對較複雜的題目，例如輸入一個整數 n 之後輸入 n 個整數，
由於測試資料是以一組為單位，因此只要讀得到下一組的一部份，
就表示是存在下一組的。

:::info
一個簡單的處理方式是：將處理輸入時的第一個 cin 提出來放到 while 中。
:::

int n;
int ary[128];
while (cin >> n)
{
	for (int i=0; i<n; i++)
	{
		cin >> ary[i];
	}
	// ...
}

如果你使用 scanf() 則可看回傳值得知正確輸入的東西個數：

int a, b;
while (scanf("%d%d", &a, &b) == 2)
{
	// ...
}

### 輸入 EOF 測試

檔案不管多大，大小必是有限的，總會撞到 EOF。
但是，執行時的手動輸入，無法判斷何時結束。

在 windows 底下，手動輸入 `CTRL+Z` 相當於是 EOF 的意思，
明確表明不會再有任何輸入，可用以判斷多重輸入的處理是否正確。

輸入正確的話，會顯示為 `^Z`。記得必須按 Enter 讓它讀進去。
如果程式正常結束，表示處理正確。

:::info
在 linux 底下，似乎得用 CTRL+D。
CTRL+Z 只會把程式丟到背景執行。
:::

:::warning
CP Editor 非採用互動式 IO 的執行方式，沒有此困擾。
:::

## 不要有多餘的 IO

比如說輸出 "please enter a number: " 之類的輸入提示。
所有輸入均會被列入和答案的比對，這會導致比對結果不一致，而得到答案錯誤的結果。

## 不要有多餘空白

比如說題目要求輸出 n 個數字，彼此**間**用空白分隔。
那麼直接輸出數字+空白看起來一樣：

for (int i=0; i<n; i++)
{
	cout << ary[i] << ' ';
}
cout << '\n';

實際上如果把空白換成底線，就可以清楚看出分別：

題目要的：`1_2_3_4`
你的輸出：`1_2_3_4_`

而它們是不相等的。
運氣好你會得到 PE，通常你會得到 WA，即使你數字都是對的。

儘管你不見得知道最後一個是誰（例如 EOF 你不知道有沒有下一組測資），
但你永遠可以知道第一個是誰。

你有個更好的做法：除了第一個以外，都在前面追加空白分隔。

cout << ary[0];
for (int i=1; i<n; i++)
{
	cout << ' ' << ary[i];
}
cout << '\n';

或者你可以追加一個變數作為標記使用：

int first = 1;
for (int i=0; i<n; i++)
{
    if (!first)
    {
        cout << ' ';
    }
    first = 0;
    cout << ary[i];
}
cout << '\n';

## 注意測資『間』還是測資『後』輸出空白行

這個和空白很像。空白行就是只有 '\n' 的一行，其餘什麼也沒有。

n 組測資會有 n-1 個測資『間』，這意味著有一組是不需要輸出空白行的。

觀察可知，要嘛是第一組之前沒有空白行，要嘛是最後一組之後沒有空白行。
多重輸入可能不會知道你這組是不是最後一組，要輸入到下一組了才會知道。
但是不是第一組，你一定知道的。

// 記得放在『每組測資之前』以免每次輸入被重置
bool first_blood = true;
// ...
// 如果已經不是第一次了，就輸出換行隔開；記得放在其他輸出前面
if (!first_blood)
{
	cout << '\n';
}
first_blood = false;
// 你的其他輸出

:::warning
CP Editor 可設定在差異比對中，以特殊記號來顯示原本看不見的換行。
- `Options` → `Preferences`
- `Appearance` → `General`
- 勾選 `Display EOLN In Diff`

右邊 `Checker` 切換至 `Strictly the same` 就可以嚴格比對是否完全相同。預設的比較方式會忽略最末尾以後的多餘換行、最後一行沒有換行、行末的多餘空白等狀況。
:::

## 用檔案輸出看 OJ 看到了什麼

:::warning
CP Editor 天生 Input 和 Output 分開，沒有此困擾。
這裡主要是講其它 IDE 如何做到 Input 和 Output 分開。
:::

當我們在執行時，因為輸出輸入都在同個視窗，可能會有交雜出現的狀況。
其實那都沒關係，輸入和輸出間的順序並不重要。

重要的是，你的所有輸出的順序。

多組輸出並不需要把答案全存下來再一次輸出，只要是依序輸出就行，
每組輸入完就直接輸出，讓它看起來交錯出現也無所謂。

透過寫入檔案，我們可以得知 OJ 所看到的我們的回答，到底長什麼樣。

在 main() 的最開始加上一行：

`freopen("d:/output.txt", "w", stdout);`

這會讓你所有透過 cout 輸出的結果，全部寫到 `d:/output.txt` 這個檔案。
不過，這也意味著輸出將不會顯示到螢幕上。

讓你的程式正常結束，就可以在 `d:/output.txt` 看到你的所有輸出。
同時，這就是 OJ 所看到的，你的答案。

:::info
如果使用 Windows 路徑分隔字元（反斜線 `\`），
必須注意其在字串中意味著跳脫字元，必須用兩個反斜線才能代表一個反斜線。
例如 `d:\output.txt` 須寫作 `"d:\\output.txt"`
:::

### 從檔案讀取

同樣地，你也可以從檔案讀取測試資料。

只要加上這行：

`freopen("d:/input.txt", "r", stdin);`

就可以將 `d:/input.txt` 檔案內容作為輸入，使用 cin 讀進來。
不過注意這也意味著你無法手動輸入。

## 不要加 while(1) 或者 system("pause") 讓程式停下來

在某些舊版本的 IDE 程式執行結束會馬上關閉，不會停下來讓我們看結果。

新版本的 Dev-C++ 和 Code::Blocks 已經不需要這個行為，
但如果你直接打開執行檔，結束時還是會直接關閉的。

加了 `while(1);` 上傳，一定會 TLE，因為你的程式不會結束。
而且 while(1) 會非常暴力地吃掉你一顆 CPU 讓它全速運轉。
現在電腦大多是多核心比較沒影響，但如果是較舊的單核心......

`system("pause");` 似乎是會得到 compilation error。~~以前是 Restricted Function~~

:::info
system() 可用來在電腦上執行命令列指令，允許這個函數等於給予相當的權限，
用來執行刪除檔案或關機等指令。
:::

所以應該是被 oj 給直接拔了，不給使用。

## int 的範圍

:::info
int 的範圍: -2147483648 ~ [phone]
:::

記好 2147483647，同時要知道它是 10 位數、$2^{31}-1$。
這樣你們才知道什麼時候可以用 int，什麼時候不行。

int 不夠大的時候，你可以用 `long long`。
這可以到 $2^{63}-1$，9223372036854775807。
記得它只能處理到 18 位數就可以了。

再更大時，只能用陣列來儲存每個位數。這是名為『大數』的處理方式。

## scanf/printf 與 long long

在 OJ 需要使用 %lld，而非 %I64d。

## 輸出的格式化

你可能偶而，或者經常遇到以下幾種情況：

- 輸出整數，靠右對齊，不足 n 位數時以空白補齊。
- 輸出整數，靠右對齊，不足 n 位數時以 0 補齊。例如時鐘的 08:07
- 輸出浮點數，四捨五入至小數點下 n 位。
- 將整數輸出為 8 進位、16 進位。

一律找 [iomanip](http://www.cplusplus.com/reference/iomanip/) 就對了。
最好把常見的記下來，否則到時可不能當場 google。
也許它會附 references 給你查，你至少得記得該往哪查。

如果你是用 printf() 那就看 [printf()](http://www.cplusplus.com/reference/cstdio/printf/) 的頁面。

外傳亦會補完 IO 相關文章。

:::warning
近年的競程題目有迴避複雜 IO 的傾向，認為核心應放在解題而非 IO，
為了更專注在核心上，IO 通常被設計得簡單而不需太多心力與技巧。

儘管因此 IO 的學習優先度相對較低，
但部份想法老舊的競賽仍會出相當刁鑽的 IO，較古老的題目通常要求也較高。
:::

{%hackmd @sa072686/__style %}

###### tags: `競程：初章`, `競程`