# APCS 2022年1月實作題題目
## 注意
這些題目是根據我的印象寫出的，如果有敘述不清楚可在下方留言!

## P1 程式交易
給你n天的股票價錢及正整數D，不論如何你第一天一定買入，而如果之後某一天價錢比上次買入的價錢還至少高D就賣掉，如果賣出後下次有一天價錢比上次賣出的價錢還至少低D就再買。
不斷重複，問你最後得多少錢（如果最後動作是買入，則我們可以無視最後一筆交易）
**範例:D=2 價格:1 3 1 2 2 答案為2**
說明:1買入->3賣出->1買入，答案為3-1=2。

## P2 贏家預測
給你n個選手的起始戰力a與反應力b，以及比賽順序，我們會根據比賽順序兩個兩個對決，判斷輸贏關鍵是比較ab的乘積，比較大的贏(如果相同就前者贏)。
而兩人戰力會發生以下改變：
假設兩人分別為(a1,b1),(a2,b2)，且1贏則:
**a1=a1+(a2xb2)/2b1**
**b1=b1+(a2xb2)/2a1**
**a2=a2+a2/2
b2=b2+b2/2**
(注意:上面算式我有點忘了，但大概長這樣)
另外題目給個m代表如果一人輸m次就會被淘汰、上面除法是使用無條件捨去。
注意如果這次序列的人是奇數，最後一人會沒辦法被配對，則這人直接視為贏的狀態，但戰力不改變。
問你最後剩下的一人是誰？

## P3 數位占卜
給你m(小於50000）個字串，每個字串長度不超過100，這些是籤，保證每個籤不同，我們同時抽出兩個籤A、B，如果A+B（這裡指的是字串的運算）的字串可以剛好切成兩個一模一樣的字串即稱為中籤，問你有幾種中籤方式。
範例：給你'三種籤“bab”,“aaa”,“a”有兩種組合方式，分別為baba和aaaa。
另外注意A-B必須要是長籤接短籤，也就是如果A長>B長，只有組合A+B而沒有B+A

## P4 圍牆公告
給你n個從左到右的木棍(n範圍為2e5)，以及他們的高H(x)（注意高介於1到1e9之間），並且叫你在上面貼k個布條(k<=5000)，長度為L(1)、L(2)...L(k)，而布條一定要整個貼在木棍上且兩兩不重疊，另外布條必須照編號從左向右貼(也就是2不能貼在1的左邊)且大家高度一樣，問你最高可以貼多高?（保證一定有解）
範例:高度1 2 3 1 2，布條長為2 1，則最佳解是2。