# 題目: 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，則輸出答案

# 參考程式碼

#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