::: success
# 79.6/100
:::
# 前言
這次題解真的不好寫，寫的很辛苦，產出時間偏久，沒有上次那麼好寫了QQ
# Q1 [少林寺的代幣](https://judge.tcirc.tw/ShowProblem?problemid=d042)
From:AP325
~~看吧 我考前是不是有說會考~~
## 題目
令狐沖去少林寺觀光，少林寺有六種代幣，面額分別是$[1, 5, 10, 50,100,500,1000]$，令狐沖拿了$n$元去換代幣
請問以這四種代幣湊成$n$元，最少要多少枚代幣？
## 解析
你在等什麼?
~~不是上課教過嗎?~~
## 程式碼
### python

while True:
    try:
        n=int(input())
        a=[1000,500,100,50,10,5,1]
        b=int(input())
        ans=0
        for i in range(len(a)):
        while b>=a[i]:
            ans=ans+1
            b=b-a[i]
        print(ans)
    except:
        break;

### c++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int a[4]={50,10,5,1};
        while(n--)
        {
            int ans=0,mon;
            cin>>mon;
            for(int i=0;i<4;i++)
            {
                while(mon>=a[i])
                {
                    mon=mon-a[i];
                    ans++;
                }
            }
            cout<<ans<<endl;
         }
    }
    return 0;
}

# Q2 [Increasing Array](https://cses.fi/problemset/task/1094)
From:CSES
題目說的不清不楚的
## 題目翻譯
你得到一個陣列含有n個整數。你希望修改陣列以使其遞增，即每個元素至少與前一個元素一樣大。
每次修改，你可以將任何元素的值增加一個。所需的最小增加次數是多少？
## 程式碼
### python

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n):
  if a[i]<a[i-1]:
    ans=ans+a[i-1]-a[i]
    a[i]=a[i-1]
print(ans)

### c++

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    int a[200005]={0};
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    long long sum=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            sum+=a[i-1]-a[i];
            a[i]=a[i-1];
        }
    }
    cout<<sum<<endl;
}

# Q3 [Movie Festival](https://cses.fi/problemset/task/1629)
From:CSES
## 題目翻譯
在電影節上將放映$n$部電影。你知道每部電影的開始和結束時間。最多可以觀看多少部電影？
## 解析
痾......排程問題
## 程式碼
### python

n=int(input())#輸入有幾個要排
a=[]
for i in range(n):
  a.append((0,0))#第一個裝結束時間，第二個裝開始時間
for i in range(n):
  b,e=map(int,input().split())
  a[i]=(e,b)
a.sort()
ans=1
endt=a[0][0]
for i in range(1,n):
  if(a[i][1]>=endt):
    ans=ans+1
    endt=a[i][0]
print(ans)

### C++

#include <bits/stdc++.h>
using namespace std;
signed main()
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int endt,begt;
        cin>>begt>>endt;
        pq.push({endt,begt});
    }
    int ans=1;
    int endti=0;
    endti=pq.top().first;
    pq.pop();
    while(!pq.empty())
    {
        if(pq.top().second>=endti)
        {
            ans++;
            endti=pq.top().first;
        }
        pq.pop();

    }
    cout<<ans<<endl;
    return 0;
}

# Q4 [Two set II](https://cses.fi/problemset/task/1093)
From:CSES
本次最難
但我撈到40% :)
## 解析
這題解析其實很難寫
由題目可知其實是一個0-1背包問題，你可以理解為取的放左邊，不取的放右邊，然後可以推出遞迴式
$其中i欄位放的是數字，j欄位放的是總和$
$$
dp[i][j]=\begin{cases}
1 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ if \ i=0,j=0
\\[2ex]
dp[i-1][j]
\qquad\quad\qquad\qquad\qquad\quad\ else \quad\ if \quad\ j-i<0
\\[2ex]
dp[i-1][j]+dp[i-1][j-i]
\qquad\quad\ else \\[2ex]
\end{cases}
$$
看不懂或不知道怎麼來的其實是正常的，這題的難度已經可以放在APCS最後一題了

但等等，如果無解呢？

我們考慮 $(\displaystyle \sum_{i=1}^{n}i)\%2=1$，也就是總和為奇數下，我們無法拆成兩個只有正整數的等分，所以這個情況下無解

:::spoiler 求和公式

$\displaystyle \sum_{i=1}^{n}i=\frac{n*(n+1)}{2}$

:::

## 程式碼
意外的，程式碼比想像的簡單許多
### python
原題TLE

MOD = 10**9 + 7
def main():
    n = int(input())
    t = n * (n + 1) // 2
    if t % 2 != 0:
        print(0)
        return
    t //= 2
    dp = [[0] * (t + 1) for _ in range(n)]
    dp[0][0] = 1
    for i in range(1, n):
        for j in range(t + 1):
            dp[i][j] += dp[i - 1][j]
            if j - i >= 0:
                dp[i][j] += dp[i - 1][j - i]
            dp[i][j] %= MOD
    print(dp[n - 1][t])
main()

### C++
原題AC

#include <iostream>
using namespace std;

int n, dp[505][63000], mod = 1e9+7;

int main() {
    cin >> n;
    int tar = n * (n+1) / 2;
    if (tar % 2) {
        cout << 0;
        return 0;
    }
    tar /= 2;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= tar; j++){
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= mod;
            if (j >= i){
                dp[i][j] += dp[i-1][j-i];
                dp[i][j] %= mod;
            }
        }
    }
    long long ans = dp[n][tar];
    ans *= 500000004;
    ans %= mod;
    cout << ans << "\n";
}

# Q5 [Book Shop](https://cses.fi/problemset/task/1158/)
From:CSES
## 解析
0-1背包問題，簡單來說就是取或不取
## 程式碼
### python
一樣原題TLE

n,h=map(int,input().split())
w=list(map(int,input().split()))
p=list(map(int,input().split()))
dp=[0]*100005
for i in range(n):
  for j in range(h,w[i]-1,-1):
    dp[j]=max((dp[j],dp[j-w[i]]+p[i]))
print(dp[h])

### C++
原題AC

#include <bits/stdc++.h>
using namespace std;
int w[1005],p[1005],dp[100005],n,h;
int main() {
    cin>>n>>h;
    for(int i=0;i<n;i++)
        cin>>w[i];
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
        for (int j=h;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
        }
    }
    cout<<dp[h];
}

# Q6 [Dice Combinations](https://cses.fi/problemset/task/1633)
From:CSES
DP最後一題
頗為有趣的一題
## 解析
可以發現
* 右邊那個分支恰好是n=0的情況
* 中間那個分支恰好是n=1的情況
* 中間那個分支恰好是n=2的情況
所以推出遞迴式
$$
dp[n]=\begin{cases}
1 \qquad\qquad\qquad\qquad\qquad\ \ \ if \ n=0
\\[2ex]
\displaystyle\sum_{dp[0]}^{dp[n]}dp[i]
\qquad\qquad\qquad\quad\ if \quad\ n<=6
\\[2ex]
\displaystyle\sum_{dp[n-6]}^{dp[n]}dp[i]\qquad\qquad\qquad\ else
\end{cases}
$$
## 程式碼
### python

dp=[0]*1000005
n=int(input())
mod=1e9+7
dp[0]=1
for i in range(1,n+1):
  for j in range(1,7):
    if(j>i):
      break
    dp[i]=(dp[i]+dp[i-j])%mod
print(int(dp[n]))

### C++

#include <iostream>
using namespace std;
int dp[1000001];
int main(){
    int n, mod=1e9+7;
    cin >> n;
    dp[0] = 1; //only 1 step
    for(int i=1; i<=n; i++){ //dp[1~n]
        for(int j=1; j<=6; j++){ //dp[3]=dp[3-1]+dp[3-2]+dp[3-3]
            if(j>i) break; //j<=i
            dp[i] = (dp[i] + dp[i-j]) % mod;
        }
    }
    cout << dp[n] << '\n';
}

# Q7 [Weird Algorithm](https://cses.fi/problemset/task/1068)
From:CSES
經典的3n+1問題，zj有同款
[The 3n + 1 problem](https://zerojudge.tw/ShowProblem?problemid=d712)
## 解析
可以選擇遞迴解或是while迴圈解
$$
a[i]=\begin{cases}
\frac{a[i-1]}{2}\qquad\qquad\qquad\qquad\qquad\ \ \ if \quad\ a[i-1]\%2=0
\\[2ex]
a[i-1]*3+1
\qquad\qquad\qquad\quad\ if \quad\ a[i-1]\%2=1
\end{cases}
$$
這裡選擇迴圈解
## 程式碼
### python

n=int(input())
while(n!=1):
  print(n,end=' ')
  if n%2==0:
    n=n//2
  else:
    n=3*n+1
print("1")

### C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    cout<<n<<' ';
    while(n!=1)
    {
        if(n%2==0)
            n=n/2;
        else
            n=3*n+1;
        if(n<=0) break;
        cout<<n<<' ';
    }
}

# Q8 Repetitions
From:CSES
## 解析
用一個迴圈，再用一個變數紀錄最最長長度
## 程式碼
### Python

s=input()
ans,l=0,0
for i in range(1,len(s)):
  if s[i]==s[i-1]:
    l=l+1
  else:
    ans=max(l,ans)
    l=0
ans=max(l,ans)
print(ans+1)

### C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int maxs=0,sum=0;
    for(int i=0;i<s.size()-1;i++)
    {
        if(s[i]==s[i+1]) sum++;
        else if(s[i]!=s[i+1])
        {
            maxs=max(maxs,sum);
            sum=0;
        }
    }
    maxs=max(maxs,sum);
    cout<<maxs+1<<endl;
}