# PCCA Winter 一般組 Day 1 練習賽 參考解答

## A. Simple Base Conversion
- **看清楚題目和測資的大小寫和範圍！**
- 對於 `<cstdio>`，`%i` 可以自動判斷輸入的整數是 16 進位或 10 進位並存入 `int` 型別中，再自行判斷後用 `%d` 輸出 10 進位和 `%X` 輸出 16 進位（大寫字母）即可。
- `<ios>` 中有 `std::showbase`、`std::hex`、`std::dec`、`std::uppercase` 等物件可以使用，如：

	cout << hex << uppercase;
	cout << "0x" << 44 << endl;

會輸出：

	0x2C

- 如果使用 `cin`, `cout` 的同學，請在 `main` 函數一開始加上以下程式碼，避免超時。

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

- 題目敘述中提到是非負整數，小心輸入為 `0` 或 `0x0` 的狀況。

## B. Kindergarten Counting Game
- 輸入一整行之後再處理。
- 注意開頭和結尾的一些特殊狀況！

## C. The Playboy Chimp
- 二分搜

## D. Rotating Sentences
- 請小心處理換行字元，不要輸出多餘的空白！

## E. Solve It
- 發現單調性。
- 答案只要求到小數點後第四位。
- 比較兩個數字是否相等時，可以接受非常小的誤差。
- 即： $|a-b| \le \varepsilon$ 但因為 $\varepsilon$ 太小所以我們忽略，仍然可以視為 $a=b$ 成立。

## F. Marvelous Mazes
- 字串處理

## G. Where's Waldorf?
- 字串處理
- 同 A，使用 `cin`、`cout` 時請注意速度。

## H. Humidex
- 二分搜
- 單調性
- 同 E，請注意浮點數運算的誤差。

## I. Broken Keyboard (a.k.a. Beiju Text)
- 開一個陣列 $O(n)$ 檢查，每次移動指針時（Home, End, Next）把下一個字元映射到指針位置的陣列格中。
- 另解：linked-list

## J. Monthly Expense
- $N+1$ 個數的數列分成連續的 $M$ 個區間，使最大區間和最小。
- 二分搜答案，並且爬行法 $O(n)$ 是否有合法的分法。

## K. The Monkey and the Oiled Bamboo
- 二分搜答案，按照題意 $O(n)$ 檢查是否合法。

## L. Product
- 數字範圍到 ${10}^{250}$，也就是兩個 $250$ 位數相乘，直式乘法：$O(n^2)$，$n \le 250$。
- 兩個最大到 ${10}^{250}$ 的數字相乘，最大會到 ${10}^{500}$。
- 如果寫不出大數乘法，開其他程式語言也是不錯的選擇。