# 題目: UVa 1746 - String Theory

# 題目說明

巢狀引文不只適合寫文章,也適合寫程式,以下是說明:

1 層的引文 (1-quotation) 定義為一個字串的頭尾都有一個 '
例如: 'this is a string'

k 層的引文 (k-quotation) 定義為頭尾都有 k 個 ' ,而裡面有 (k - 1) 層的引文
例如: ''All 'work' and no 'play''' 就是一個 2 層的引文


INPUT:
每筆測茲有兩行輸入
第一行為一個整數 N ,代表接下來有 N 個整數
第二行輸入 N 個整數,代表引號的數量


OUTPUT:
輸出測資為幾層的巢狀引文 (k)
若沒有 k ,則輸出 no quotation

# 解題方法

儲存資料之後,從頭尾之間比較小的數字開始爆破
從最左及最右開始每次減 tmp ,隨後 tmp - 1 ,直到 tmp = 0 或不符合 while 條件
tmp = 0 時,若剩餘數字的合可以整除 2,則輸出答案

注意當 k = 1 時,只有兩種輸入會成立 1 22 1 1 ,需要特別處理

# 參考程式碼

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, a;	
	while (cin >> N)
	{
		// store data
		vector<int> data;
		for (int i = 0; i < N; ++i) cin >> a, data.emplace_back(a);
		// i start with the smallest number
		for (int i = min(data[0], data[N - 1]); i > 0; --i)
		{
			// copy the original data
			vector<int> cpy = data;
			int left = 0, right = N - 1;
			int tmp = i;
			while (right >= 0 && left < N && cpy[left] >= tmp && cpy[right] >= tmp)
			{
				if ((cpy[left] -= tmp) == 0) ++left;
				if ((cpy[right] -= tmp--) == 0) --right;
				
				if (tmp == 0)
				{
					int sum = 0;
					for (auto& j : cpy) sum += j;
					// if i = 1, thete are only two cases: 1 2 and 2 1 1
					if (!(sum & 1) && i != 1 || sum == 0 && i == 1) cout << i << "\n";
					else cout << "no quotation\n";
					goto finish;				
				}
			}
		}
		finish:;
	}
	return 0;
}

# 參考資料

https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/1746.php