# APCS202201
#### 以下非*施工中*程式碼皆由ZeroJudge檢測通過
## [1. 程式交易](https://zerojudge.tw/ShowProblem?problemid=h081)
紀錄前一次交易的價格&是否有股票
硬算
:::spoiler C++

#include <iostream>
using namespace std;
int main(){
    int n,d,last,cur,had=0,ans=0;
    cin >> n >> d;
    cin >> cur;
    last = cur;
    had=1;
    n--;
    while(n--){
        cin >> cur;
        if (had){
            if (cur>=last+d){
                had = 0;
                ans+=cur-last;
                last = cur;
            }
        }else{
            if (cur<=last-d){
                had = 1;
                last = cur;
            }
        }
    }
    cout << ans << "\n";
}

:::
:::spoiler Python

n,d = map(int,input().split())
last=10000
had=False
ans=0
for cur in map(int,input().split()):
    if had:
        if cur>=last+d:
            had=False
            ans+=cur-last
            last=cur
    else:
        if cur<=last-d:
            had=True
            last=cur
print(ans)

:::
:::spoiler Python in one line

print((lambda a,l:(lambda n,d,v:max(((bool(v.__setitem__(0,v[0]+c-v[1]))+bool(v.__setitem__(1,c))+bool(v.__setitem__(2,False)) if c>=v[1]+d else 0) if v[2] else (bool(v.__setitem__(1,c))+bool(v.__setitem__(2,True)) if c<=v[1]-d else 0) for c in l))+v[0])(int(a[0]),int(a[1]),[0,10000,False]))(input().split(),map(int,input().split())))

:::
## [2. 贏家預測](https://zerojudge.tw/ShowProblem?problemid=h082)
照題敘算
:::spoiler C++
施工中

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> s(n),t(n),o(n),h(n,m);
    for (int i = 0;i<n;i++){
        cin >> s[i];
    }
    for (int i = 0;i<n;i++){
        cin >> t[i];
    }
    for (int i = 0;i<n;i++){
        cin >> o[i];
        o[i]++;
    }
    while (o.size()>1){
        vector<int> ns(n,0),nt(n,0),win,lose;
        for (int i = 0;i<o.size()/2;i++){
            int a = o[i*2];
            int b = o[i*2+1];
            if (s[b]*t[b]>s[a]*t[a]){
                swap(a,b);
            }
            h[b]--;
            ns[a] = s[b]*t[b]/t[a]/2;
            nt[a] = s[b]*t[b]/s[a]/2;
            ns[b] = s[b]/2;
            nt[b] = t[b]/2;
            win.push_back(a);
            if(h[b]) lose.push_back(b);
        }
        for (int i = 0;i<n;i++){
            s[i]+=ns[i];
            t[i]+=nt[i];
        }
        o.clear();
        for (int p : win){
            o.push_back(p);
        }
        for (int p : lose){
            o.push_back(p);
        }
    }
    cout << (o[0]+1) << "\n";
}

:::
:::spoiler Python

n,m = map(int,input().split())
s = [int(text) for text in input().split()]
t = [int(text) for text in input().split()]
health = [m]*n
o = [int(text)-1 for text in input().split()]
while len(o)>1:
    win=[True]*n
    for i in range(len(o)//2):
        p1=o[i*2]
        p2=o[i*2+1]
        p1,p2=(p1,p2) if s[p1]*t[p1]>=s[p2]*t[p2] else (p2,p1)
        d=s[p2]*t[p2]//2
        s[p1],t[p1]=s[p1]+d//(t[p1]),t[p1]+d//(s[p1])
        s[p2]+=s[p2]//2
        t[p2]+=t[p2]//2
        health[p2]-=1
        win[p2]=False
    o = [i for i in o if win[i]]+[i for i in o if not win[i] and health[i]]
print(o[0]+1)

:::
:::spoiler Python in one line

print((lambda d:(lambda f:f(f,[d[1]]*d[0]))(lambda F,h:bool((lambda win:(lambda ns,nt:min((bool(d[2].__setitem__(d[4][i],ns[i])) for i in range(len(ns))))+min((bool(d[3].__setitem__(d[4][i],nt[i])) for i in range(len(nt))))+min((bool(h.__setitem__(d[4][i],h[d[4][i]]-(0 if win[i] else 1))) for i in range(len(d[4]))))+bool(d.__setitem__(4,[d[4][i] for i in range(len(d[4])) if win[i]]+[d[4][i] for i in range(len(d[4])) if not win[i] and h[d[4][i]]>0])))([(d[2][d[4][i]] if win[i]>1 else d[2][d[4][i]]+d[2][d[4][i^1]]*d[3][d[4][i^1]]//d[3][d[4][i]]//2) if win[i]>0 else d[2][d[4][i]]+d[2][d[4][i]]//2 for i in range(len(d[4]))],[(d[3][d[4][i]] if win[i]==2 else d[3][d[4][i]]+d[2][d[4][i^1]]*d[3][d[4][i^1]]//d[2][d[4][i]]//2) if win[i] else d[3][d[4][i]]+d[3][d[4][i]]//2 for i in range(len(d[4]))]))([((i^1<len(d[4])) and (d[2][d[4][i]]*d[3][d[4][i]]>d[2][d[4][i^1]]*d[3][d[4][i^1]] or (d[2][d[4][i]]*d[3][d[4][i]]==d[2][d[4][i^1]]*d[3][d[4][i^1]] and i<(i^1))))+2*(i^1==len(d[4])) for i in range(len(d[4]))]))*0+(F(F,h[:]) if len(d[4])>1 else d[4][0]+1)))([int(t) for t in input().split()]+[[int(t) for t in input().split()],[int(t) for t in input().split()],[int(t)-1 for t in input().split()]]))

:::
## [3. 數位占卜](https://zerojudge.tw/ShowProblem?problemid=h083)
用hashset存籤
對於每一個籤，切出不同長度的前後綴，若前綴=後綴 且 剩下的部分能在set裡找到一樣的 則 答案+1
#### 原理：
對於一組聖筊$a+b$
不失一般性設$a$比較長
所以**a的前半**和**a的後半加b**一樣
設**a的前半**=c、**a的後半**=d
$a+b=(c+d)+b=((d+b)+d)+b=(d+b+d)+b$
可知$d$是$a$的前後綴
所以對每一支籤，切出不同長度的前後綴$d$，只要存在與剩下的部分相同的籤$b$，就可以組成**聖筊**
因為總是用長的籤去找短的籤，所以不用擔心重複算到的問題
:::spoiler C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    unordered_set<string> dat;
    while (n--){
        string s;
        cin >> s;
        dat.insert(s);
    }
    long long ans = 0;
    for (string s: dat){
        int l = s.size();
        for (int i = 1;i<(l+1)/2;i++){
            bool sus = true;
            for (int j = 0;j<i;j++){
                if (s[j]!=s[j+l-i]) sus=false;
            }
            if (sus){
                ans += dat.count(s.substr(i,l-2*i))?1:0;
            }
        }
    }
    cout << ans << "\n";
}

:::
:::spoiler Python

m = int(input())
dat = {input() for a in range(m)}
ans = 0
for s in dat:
    for i in range(1,(len(s)+1)//2):
        if s[:i]==s[-i:] and s[i:-i] in dat:
            ans+=1
print(ans)

:::
:::spoiler Python in one line

print((lambda dat:str(sum((sum((s[:i]==s[-i:] and s[i:-i] in dat for i in range(1,(len(s)+1)//2))) for s in dat))))({input() for z in range(int(input()))}))

:::
## [4. 牆上海報](https://zerojudge.tw/ShowProblem?problemid=h084)
用貪心法可$O(n)$求出某一高度能否貼海報
能否貼海報$\leftrightarrow$此高度$\le$最大高度$=$答案
且已知答案為$[1,h_{max}]$中的一個整數
對$[1,h_{max}]$二分搜
時間複雜度為$O(n\log_2h_{max})$
:::spoiler C++

#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<int> h,w;
bool check(int ans){
    int t = 0,len=0;
    for (int i = 0;i<n;i++){
        if (h[i]>=ans) len++;
        else len = 0;
        if(len>=w[t]){
            len-=w[t];
            t++;
            if(t>=k) return true;
        }
    }
    return false;
}
int search_ans(int l, int r){
    if (l == r) return l;
    int mid = ((r+l)/2)+1;
    if (check(mid)){
        return search_ans(mid,r);
    }
    return search_ans(l,mid-1);
}
int main(){
    ios::sync_with_stdio(false);cin.tie();
    cin >> n >> k;
    h.resize(n);
    w.resize(k);
    int mh = 0;
    for (int i = 0;i<n;i++){
        cin>>h[i];
        if(h[i]>mh) mh=h[i];
    }
    for (int i = 0;i<k;i++){
        cin>>w[i];
    }
    cout << search_ans(1,mh) << "\n";
}

:::
:::spoiler Python

n=k=0
h=[]
w=[]
def check(ans):
    t = l = 0
    for i in range(n):
        if h[i]>=ans:
            l+=1
        else:
            l=0
        if l>=w[t]:
            l-=w[t]
            t+=1
            if t>=k:
                return True
    return False
def search(l,r):
    if l==r:
        return l
    mid = (l+r)//2+1
    if check(mid):
        return search(mid,r)
    return search(l,mid-1)
n,k = map(int,input().split())
h = [int(s) for s in input().split()]
w = [int(s) for s in input().split()]
print(search(1,max(h)))

:::
:::spoiler Python in one line

print((lambda _0,h,w:(lambda c,f:str(f(1,max(h),f,c)))((lambda a:(lambda v:min((bool(v.__setitem__(1,v[1]+1 if i>=a else 0))+(bool(v.__setitem__(1,v[1]-w[v[0]]))+bool(v.__setitem__(0,v[0]+1)) if v[1]>=w[v[0]] else 0) for i in h if v[0]<len(w)))*0+(v[0]>=len(w)))([0,0])),(lambda l,r,F,C:l if l==r else (F((l+r)//2+1,r,F,C) if C((l+r)//2+1) else F(l,(l+r)//2,F,C)))))(input(),[int(s) for s in input().split()],[int(s) for s in input().split()]))

:::