# 師大附中電算社46×47第二次社內賽
## 題本
[完整題目 PDF 檔在這裡](https://www.dropbox.com/scl/fi/fc5qgtp798rq5hri47x6v/46_47.pdf?rlkey=hltmi0x7z94lxwnnorlgruh2i&st=8qykgzst&dl=1)
[第一題 PDF 檔在這裡](https://www.dropbox.com/scl/fi/alg1e5bx4cghip2rx49a1/Distribution.pdf?rlkey=tuaatdkdwkmcld9nhmdgvlyjg&st=la5vgxdf&dl=1)
[第二題 PDF 檔在這裡](https://www.dropbox.com/scl/fi/hvq04k0a43w6hr74rrbq8/Class.pdf?rlkey=s9k8o468upknrqtofuchbjurq&st=6swyd8zj&dl=1)
[第三題 PDF 檔在這裡](https://www.dropbox.com/scl/fi/7ugskfjhanf7wcdh3y5va/Barbecue.pdf?rlkey=2zxul9pg0ntftefgjlwvsqnyi&st=snopwe81&dl=1)
## 題解

### 分配
#### 出題者：hi
#### 子題一
對每一組輸入做 $n_i$ 次整數除法，小數點後再輸出 $p_{i,n_i}$ 個 $0$ 就可以了。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long t, n, a, b, p;
    cin >> t;
    while(t--)
    {
        cin >> n >> a;
        while(n--)
        {
            cin >> b >> p;
            a /= b;
        }
        cout << a;
        if(p > 0) cout << ".";
        while(p--) cout << 0;
        cout << "\n";
    }
}

t = int(input())
for _ in range(t):
    n, a = map(int, input().split())
    b, p = 0, 0
    for _ in range(n):
        b, p = map(int, input().split())
        a //= b
    print(a, end = "")
    if p > 0:
        print(".", end = "")
    for _ in range(p):
        print(0, end = "")
    print()

#### 子題二
整數 $a$ 除以整數 $b$ ，如果要求精度為 $p$ 可以將除法的流程變成：
1. 把 $a$ 乘以 $10^p$
2. 做 $a\div b$ 的整數除法
3. 把 $a$ 除以 $10^p$

如此一來除法的部分就可以全部用整數完成，不會有浮點數誤差的問題，無條件捨去也不需要再處理。最後一步再把 $a$ 除以最後的 $10^p$ 之後輸出。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long m, n, a, b, p, pw, i;
    cin >> m;
    while(m--)
    {
        cin >> n >> a;
        pw = 0;
        while(n--)
        {
            cin >> b >> p;
            while(pw < p)
                a *= 10, pw++;
            while(pw > p)
                a /= 10, pw--;
            a = a / b;
        }
        double res = a / pow(10, pw);
        cout << fixed << setprecision(pw) << res << "\n";
    }
}

t = int(input())
while t > 0:
    t -= 1
    n, a = map(int, input().split())
    pw = 0
    for _ in range(n):
        b, p = map(int, input().split())
        while pw < p:
            a *= 10
            pw += 1
        while pw > p:
            a //= 10
            pw -= 1
        a //= b
    res = a / 10 ** pw
    print(f"{res:.{pw}f}")

### 社課
#### 出題者：cyano
#### 子題一
可以發現在 $n \le 9$ 的情況下，所有座號的下一位社員座號都會是自己，所以座號 $p$ 的社員必定會被抽問 $m$ 次，其他社員必定不會被抽問。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, p, q, ignore, i;
    cin >> n >> m >> p >> q;
    while(q--) cin >> ignore;
    cout << p << " " << m << "\n";
}

n, m, p, q = map(int, input().split())
ignore = input()
print(p, m)

#### 子題二
直接依照規則模擬。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long ans[100];
int main()
{
    long long n, m, p, q, s = 0, t = 0, i;
    cin >> n >> m >> p >> q;
    while(m--)
    {
        ans[p]++;
        if(p + 10 > n) p = p / 10 + p % 10;
        else p += 10;
    }
    for(i = 1; i <= n; i++)
    {
        if(ans[i] != 0)
            cout << i << " " << ans[i] << "\n";
    }
}

ans = [0] * 100
n, m, p, q = map(int, input().split())
while m > 0:
    ans[p] += 1
    if p + 10 > n:
        p = p // 10 + p % 10
    else:
        p += 10
    m -= 1
for i in range(1, n + 1):
    if ans[i] != 0:
        print(i, ans[i])

#### 子題三
因為從子題三之後可能會用到超過一次尋找下一個社員的程式，所以先定義一個函式。

long long nxt(long long p, long long n)
{
    if(p + 10 > n) return p / 10 + p % 10;
    return p + 10;
}

def nxt(p, n):
    if p + 10 > n:
        return p // 10 + p % 10
    return p + 10

接著同樣依照規則模擬，這個子題值得注意的地方是座號 $p$ 的社員並不保證不會缺席，所以以下的程式可能會得到 `WA` 。

while(m--)
{
    ans[p]++;
    do
        p = nxt(p, n);
    while(absent[p]);
}

while m > 0:
    ans[p] += 1
    while True:
        p = nxt(p, n)
        if not absent[p]:
            break
    m -= 1

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long absent[100], ans[100];
long long nxt(long long p, long long n)
{
    if(p + 10 > n) return p / 10 + p % 10;
    return p + 10;
}
int main()
{
    long long n, m, p, q, i;
    cin >> n >> m >> p >> q;
    while(q--)
    {
        cin >> i;
        absent[i] = 1;
    }
    while(m--)
    {
        while(absent[p])
            p = nxt(p, n);
        ans[p]++;
        p = nxt(p, n);
    }
    for(i = 1; i <= n; i++)
    {
        if(ans[i] != 0)
            cout << i << " " << ans[i] << "\n";
    }
}

absent = [0] * 100
ans = [0] * 100
def nxt(p, n):
    if p + 10 > n:
        return p // 10 + p % 10
    return p + 10
n, m, p, q = map(int, input().split())
for _ in range(q):
    i = int(input())
    absent[i] = 1
while m > 0:
    while absent[p]:
        p = nxt(p, n)
    ans[p] += 1
    p = nxt(p, n)
    m -= 1
for i in range(1, n + 1):
    if ans[i] != 0:
        print(i, ans[i])

#### 子題四
因為 $m$ 很大所以無法直接算。假設 $n = 30,\ p = 28$ ，則抽問的順序會像底下這一張圖。
如此一來會形成一條鍊接到一個環上，所以只需要處理鍊上還有環上的數字就可以了。定義三個陣列 `start[]` 、 `loop[]` 、 `final[]` ， `start[]` 記錄形成環之前被抽問到的座號， `loop[]` 記錄環上的座號、 `final[]` 記錄剩下無法形成一個環的座號。而環上每一個座號被抽問的次數即為 $m$ 減去形成環之前被抽問到的人數再除以環上的人數，令這個數字是 $t$ ，而剩下無法形成一個環的人數就是 $m$ 減去形成環之前被抽問到的人數除以環上人數的餘數，最後座號 $i$ 被抽問的次數即為 `start[i] + loop[i] * t + final[i]`

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long absent[100], start[100], loop[100], final[100];
long long nxt(long long p, long long n)
{
    if(p + 10 > n) return p / 10 + p % 10;
    return p + 10;
}
int main()
{
    long long n, m, p, q, s = 0, t, i;
    cin >> n >> m >> p >> q;
    while(m && start[p] == 0)
    {
        m--;
        start[p] = 1;
        p = nxt(p, n);
    }
    while(loop[p] == 0)
    {
        s++;
        loop[p] = 1;
        p = nxt(p, n);
    }
    t = m / s;
    m %= s;
    while(m)
    {
        m--;
        final[p] = 1;
        p = nxt(p, n);
    }
    for(i = 1; i <= n; i++)
    {
        if(start[i] + loop[i] * t + final[i] != 0)
            cout << i << " " << start[i] + loop[i] * t + final[i] << "\n";
    }
}

absent = [0] * 100
start = [0] * 100
loop = [0] * 100
final = [0] * 100
def nxt(p, n):
    if p + 10 > n:
        return p // 10 + p % 10
    return p + 10
n, m, p, q = map(int, input().split())
while m > 0 and start[p] == 0:
    m -= 1
    start[p] = 1
    p = nxt(p, n)
s = 0
while loop[p] == 0:
    s += 1
    loop[p] = 1
    p = nxt(p, n)
t = m // s
m %= s
while m > 0:
    m -= 1
    final[p] = 1
    p = nxt(p, n)
for i in range(1, n + 1):
    if start[i] + loop[i] * t + final[i] != 0:
        print(i, start[i] + loop[i] * t + final[i])

#### 子題五
做法與子題四相同，只是要考慮缺席的社員。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long absent[100], start[100], loop[100], final[100];
long long nxt(long long p, long long n)
{
    if(p + 10 > n) return p / 10 + p % 10;
    return p + 10;
}
int main()
{
    long long n, m, p, q, s = 0, t, i;
    cin >> n >> m >> p >> q;
    while(q--)
    {
        cin >> i;
        absent[i] = 1;
    }
    while(m && start[p] == 0)
    {
        if(!absent[p])
        {
            m--;
            start[p] = 1;
        }
        p = nxt(p, n);
    }
    while(loop[p] == 0)
    {
        if(!absent[p])
        {
            s++;
            loop[p] = 1;
        }
        p = nxt(p, n);
    }
    t = m / s;
    m %= s;
    while(m)
    {
        if(!absent[p])
        {
            m--;
            final[p] = 1;
        }
        p = nxt(p, n);
    }
    for(i = 1; i <= n; i++)
    {
        if(start[i] + loop[i] * t + final[i] != 0)
            cout << i << " " << start[i] + loop[i] * t + final[i] << "\n";
    }
}

absent = [0] * 100
start = [0] * 100
loop = [0] * 100
final = [0] * 100
def nxt(p, n):
    if p + 10 > n:
        return p // 10 + p % 10
    return p + 10
n, m, p, q = map(int, input().split())
u = list(map(int, input().split()))
for i in u:
    absent[i] = 1
while m > 0 and start[p] == 0:
    if not absent[p]:
        m -= 1
        start[p] = 1
    p = nxt(p, n)
s = 0
while loop[p] == 0:
    if not absent[p]:
        s += 1
        loop[p] = 1
    p = nxt(p, n)
t = m // s
m %= s
while m > 0:
    if not absent[p]:
        m -= 1
        final[p] = 1
    p = nxt(p, n)
for i in range(1, n + 1):
    if start[i] + loop[i] * t + final[i] != 0:
        print(i, start[i] + loop[i] * t + final[i])

#### 子題四、五另解
定義 `to[i][j]` 為由 $i$ 往下抽問 $2^j$ 位社員後輪到的社員， `s[i][j][k]` 為由 $i$ 往下抽問 $2^j$ 位社員後座號 $k$ 的社員被抽問的次數。 `to[i][0]` 的處理就和尋找形成環之前被抽問到的座號類似，而根據定義， `to[i][j] = to[to[i][j - 1]][j - 1]` 。除此之外也可以推得 `s[i][0][i] = 1` ，而根據定義， `s[i][j][k] = s[i][j - 1][k] + s[to[i][j - 1]][j - 1][k]` 。最後再把 $m$ 做二進位分解就可以得到答案。以下只題供子題五的程式碼。

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long absent[100], to[100][60], s[100][60][100], ans[100];
long long nxt(long long p, long long n)
{
    if(p + 10 > n) return p / 10 + p % 10;
    return p + 10;
}
signed main()
{
    long long n, m, p, q, i, j, k;
    cin >> n >> m >> p >> q;
    while(q--)
    {
        cin >> i;
        absent[i] = 1;
    }
    while(absent[p])
        p = nxt(p, n);
    long long t = p;
    while(to[t][0] == 0)
    {
        long long tmp = t;
        do
            t = nxt(t, n);
        while(absent[t]);
        to[tmp][0] = t;
    }
    for(j = 1; j < 60; j++)
    {
        for(i = 1; i <= n; i++)
            to[i][j] = to[to[i][j - 1]][j - 1];
    }
    for(i = 1; i <= n; i++)
        s[i][0][i] = 1;
    for(j = 1; j < 60; j++)
    {
        for(i = 1; i <= n; i++)
        {
            for(k = 1; k <= n; k++)
                s[i][j][k] = s[i][j - 1][k] + s[to[i][j - 1]][j - 1][k];
        }
    }
    for(j = 0; j < 60; j++)
    {
        if(m % 2 == 1)
        {
            for(k = 1; k <= n; k++)
                ans[k] += s[p][j][k];
            p = to[p][j];
        }
        m /= 2;
    }
    for(i = 1; i <= n; i++)
    {
        if(ans[i] != 0)
            cout << i << " " << ans[i] << "\n";
    }
}

absent = [0] * 100
to = [[0] * 60 for _ in range(100)]
s = [[[0] * 100 for _ in range(60)] for _ in range(100)]
ans = [0] * 100
def nxt(p, n):
    if p + 10 > n:
        return p // 10 + p % 10
    return p + 10
n, m, p, q = map(int, input().split())
u = list(map(int, input().split()))
for i in u:
    absent[i] = 1
while absent[p]:
    p = nxt(p, n)
t = p
while to[t][0] == 0:
    tmp = t
    while True:
        t = nxt(t, n)
        if not absent[t]:
            break
    to[tmp][0] = t
for j in range(1, 60):
    for i in range(1, n + 1):
        to[i][j] = to[to[i][j - 1]][j - 1]
for i in range(1, n + 1):
    s[i][0][i] = 1
for j in range(1, 60):
    for i in range(1, n + 1):
        for k in range(1, n + 1):
            s[i][j][k] = s[i][j - 1][k] + s[to[i][j - 1]][j - 1][k]
for j in range(60):
    if m % 2 == 1:
        for k in range(1, n + 1):
            ans[k] += s[p][j][k]
        p = to[p][j]
    m //= 2
for i in range(1, n + 1):
    if ans[i] != 0:
        print(i, ans[i])

### 秋烤
#### 出題者：R緯
#### 子題一
因為所有 $a_i$ 都相異，每一個箱子最多放入一個盒子，又因為 $m \le n$ ，所有箱子必定會有一個盒子，因此所有 $ans$ 都會是 $m$ 。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, k, ignore, i;
    cin >> n >> m >> k;
    for(i = 0; i < n; i++) cin >> ignore;
    for(i = 0; i < n; i++) cout << m << " \n"[i == n - 1];
    cout << m << "\n";
    for(i = 0; i < n; i++) cout << i + 1 << " \n"[i == n - 1];
}

n, m, k = map(int, input().split())
ignore = input()
for i in range(n):
    print(m, end = " ")
print()
print(m)
for i in range(n):
    print(i + 1, end = " ")
print()

#### 子題二
陣列複製一份到尾端，這樣就不需要另外處理盒子移到尾端的部分。然後直接模擬，紀錄每一種盒子出現的次數，更新出現次數時如果次數是 $k$ 的倍數就更新箱子的數量，箱子的數量到 $m$ 之後就不再新增箱子。

#include <bits/stdc++.h>
using namespace std;
long long m, k, cur_box, cur_ans;
long long a[600], cnt[301], ans[300];
void add(long long t)
{
    if(cnt[t] % k == 0)
    {
        if(cur_box == m) return;
        cnt[t]++;
        cur_box++;
        cur_ans++;
    }
    else
    {
        cnt[t]++;
        cur_ans++;
    }
}
int main()
{
    long long n, i, j;
    cin >> n >> m >> k;
    for(i = 0; i < n; i++) cin >> a[i], a[i + n] = a[i];
    for(i = 0; i < n; i++)
    {
        cur_box = cur_ans = 0;
        for(j = 1; j <= n; j++) cnt[j] = 0;
        for(j = 0; j < n; j++) add(a[i + j]);
        ans[i] = cur_ans;
    }
    for(i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    long long mx = 0;
    for(i = 0; i < n; i++) mx = max(mx, ans[i]);
    cout << mx << "\n";
    for(i = 0; i < n; i++) if(ans[i] == mx) cout << i + 1 << " ";
    cout << "\n";
}

n, m, k = map(int, input().split())
cur_box, cur_ans = 0, 0
cnt = [0] * 301
ans = [0] * 300
a = list(map(int, input().split()))
a = a + a
def add(t):
    global cur_box, cur_ans
    if cnt[t] % k == 0:
        if cur_box == m:
            return
        cnt[t] += 1
        cur_box += 1
        cur_ans += 1
    else:
        cnt[t] += 1
        cur_ans += 1
for i in range(n):
    cur_box, cur_ans = 0, 0
    for j in range(1, n + 1):
        cnt[j] = 0
    for j in range(n):
        add(a[i + j])
    ans[i] = cur_ans
for i in range(n):
    print(ans[i], end = " ")
print()
mx = 0
for i in range(n):
    mx = max(mx, ans[i])
print(mx)
for i in range(n):
    if ans[i] == mx:
        print(i + 1, end = " ")
print()

#### 子題三
[R緯寫的題解](https://hackmd.io/@ts-boring/Hk3VngAQ1l)

完整程式碼：

#include <bits/stdc++.h>
using namespace std;
long long k, cur_box, cur_ans;
long long a[400000], total[200001], cnt[200001], ans[200000];
void update(long long t, long long d)
{
    long long box;
    box = (cnt[t] + k - 1) / k;
    cur_ans -= min(box * k, total[t]);
    cur_box -= box;
    cnt[t] += d;
    box = (cnt[t] + k - 1) / k;
    cur_ans += min(box * k, total[t]);
    cur_box += box;
}
int main()
{
    long long n, m, r = 0, i;
    cin >> n >> m >> k;
    for(i = 0; i < n; i++)
    {
        cin >> a[i];
        total[a[i]]++;
        a[i + n] = a[i];
    }
    for(i = 0; i < n; i++)
    {
        while(r < i + n && cur_box < m)
            update(a[r++], 1);
        ans[i] = cur_ans;
        update(a[i], -1);
    }
    long long mx = 0;
    for(i = 0; i < n; i++)
    {
        cout << ans[i] << " \n"[i == n - 1];
        mx = max(mx, ans[i]);
    }
    cout << mx << "\n";
    for(i = 0; i < n; i++)
    {
        if(ans[i] == mx)
            cout << i + 1 << " ";
    }
    cout << "\n";
}

# 讀取輸入的數據
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
a = [t - 1 for t in a]  # 轉為 0-indexed
a_double = a + a  # 複製並連接->模擬輪換
type_cnt = [0 for _ in range(n)]  # 記錄每種盒子的總數

cur_cnt = [0 for _ in range(n)]  # 記錄當前每種盒子在箱子中的數量
R = -1  # 右指針
cur_box = 0  # 當前已經使用的箱子數量
ans = 0  # 當前成功放入箱子中的盒子總數

# 計算每種盒子的總數
for i in range(n):
    type_cnt[a[i]] += 1

def update_box_count(box_type_index, change):
    global ans, cur_box

    # 計算當前類型盒子在箱子中的數量
    box = (cur_cnt[box_type_index] + k - 1) // k
    ans -= min(box * k, type_cnt[box_type_index])
    cur_box -= box

    # 更新當前盒子數量
    cur_cnt[box_type_index] += change
    box = (cur_cnt[box_type_index] + k - 1) // k
    ans += min(box * k, type_cnt[box_type_index])
    cur_box += box

# 主循環
Max_r = []
Max_value = 0
for j in range(n):
    while (R < j + n) and (cur_box < m):
        R += 1
        update_box_count(a_double[R], 1)

    #找最大值
    if ans > Max_value:
        Max_value = ans
        Max_r = [j+1]
    elif ans == Max_value:
        Max_r.append(j+1)

    print(ans, end=" ")  # 輸出當前成功放入箱子的盒子總數
    update_box_count(a_double[j], -1)  # 移除當前盒子
    
print()
print(Max_value)    # 輸出最大值
for l in Max_r:
    print(l, end=" ")    # 輸出有最大值的r
print()