---
# System prepended metadata

title: S3 演算法 week 5
tags: [S3 公開資源]

---

# S3 演算法 week 5
###### tags: `S3 公開資源`

:::info
時間：12/11 9:00 ~ 17:00
地點：成大資工系新館 **65203** 教室
主題：基礎數論與資料結構
直播連結：https://youtu.be/OR0Z_fVyKAs
:::

## 課程內容
- 進位制
- 餘數
- 建表
- stack
- queue
- linked list
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS


## 注意事項
1. 接下來的課程都是演算法的內容，請學員務必熟悉基本語法的運用
2. 之後的助教時間將固定舉辦於每週五 20:00 ~ 22:00（段考週可能會暫停），運作模式如下：
	- 採自由練習 / 討論的方式，學員們可在任意語音討論區討論，每個語音頻道限制 10 人，請盡量開啟畫面直播以方便助教查看
	- 每次助教時間都有至少一名值班助教，會不定時關心練習狀況，如果練習途中遇到問題了可以開麥克風跟同頻道的夥伴們討論，或是呼叫助教幫忙
	- 如果該堂課有額外題解或是其他事務，會在 22:00 左右將學員集中至某個語音頻道
3. 所有上課相關連結都會放在資源彙整裡：https://hackmd.io/@SCIST/rykldedMj
4. 上課期間請全程配戴口罩
5. 請假表單：https://forms.gle/2ESVuTezcHCK959H6

# 必作題題解

[TOC]

## 第二章－第三節

### [No_Judge - 擲骰結果](https://hackmd.io/@sa072686/cp/%2F4uO2GyfGTi2a4vP0rUtZXA#%E6%93%B2%E9%AA%B0%E7%B5%90%E6%9E%9C)

撰寫者：fishhh

這一題其實有很多種解法，那因為章節是進位制，故使用這種方法~
這其實有一個名稱 叫做位元枚舉。
詳細的解法可以在講義裡看到~ 那我這邊就提供程式碼。

:::spoiler
```cpp=
#include "iostream"
using namespace std;
int main(){
    int n,t;
    cin>>n>>t;
    int ans=0;
    int all = 1; // 所有可能
    for(int i=0;i<n;i++){
        all*=6;
    }
    for(int i=0;i<=all;i++){
        int temp=i;
        int now_tot=0;
        while(temp){
            now_tot+=(temp%6+1); // 加1 是因為在六進位下 只會有 0~5 所以全部平移 1 就會是骰子的點數~
            temp/=6;
        }
        if(now_tot>=t)ans++;
    }
    cout<<ans;
}
```
:::

---

### [TOJ 292 - Jessica好仁慈](https://toj.tfcis.org/oj/pro/292/)

撰寫者：Eason

主要想法就是先轉成十進位
再轉成題目要求的進位

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int a, b, c;

int to_decimal (int origin, int num){ // 轉十進位
    int sum = 0, pow = 0;
    int tmp = 1;
    while (num != 0){
        sum += num % 10 * tmp;
        num /= 10;
        tmp *= origin;
    }
    return sum;
}

int transform (int dis, int num){// 轉題目要求的進位制
    int sum = 0, cnt = 1;
    while (num != 0){
        sum += num % dis * cnt;
        num /= dis;
        cnt *= 10;
    }
    return sum;
}

void solve(){
    cin >> a >> b >> c;
    int ans = c;
    if (a != 10) ans = to_decimal (a, c); // 原本是十進位就不用轉換
    if (b != 10) ans = transform (b, ans); // 要求如果是十進位就不用再轉換
    cout << ans << '\n';
    return;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
```
:::

---

### [費氏數列．改](https://hackmd.io/@sa072686/cp/%2FUDa8rLAPTOqv-FZ_KwlVgQ#%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97%EF%BC%8E%E6%94%B9)

撰寫者：fishhh

在做費氏(~~事~~)數列的時候如果只有要求單純一項，就不用儲存不需要的東西 
例如：你要求第 4 項，那麼你就只需要第 2、3 項
第0、1項就完全沒有用(明確來說 是用過後就沒用ㄌ)
那就可以稍微用個滾動陣列來處理它~程式碼就會變得十分簡潔。

:::spoiler 正常版
```cpp
#include "iostream"
using namespace std;
long long int fib[10010]={0,1,1};
int main(){
    long long int n,m;
    cin>>n>>m;
    for(int i=3;i<=n;i++)fib[i]=(fib[i-1]+fib[i-2])%m;
    cout<<fib[n];
}
```
:::


:::spoiler 滾動陣列版
```cpp
#include "iostream"
using namespace std;
int main(){
    long long int n,m;
    cin>>n>>m;
    long long int fib[2]={1,1};
    for(int i=3;i<=n;i++){
        fib[i%2]=(fib[i%2]+fib[1-(i%2)])%m;
    }
    cout<<fib[n%2];
}
```
:::

---

### [AtCoder typical90_bf - Original Calculator（★4）](https://hackmd.io/@sa072686/AtCoder_typical90_bf)

撰寫者：fishhh

可以發現一件事情，就是所有數字會在 10^5 裡面。
然後，一個數一直按按鈕A 一定會有循環。

可以這樣想，就是一個數 $x$ 按了按鈕後，就會變成 $z$
那這個 $z$ 一定會符合 ($0 \leq z \leq 10^5-1$) 
(因為$z$會被模$1e5$)

那麼，假設今天按了按鈕 $1e5$ 次後，接下來出現的數一定會在之前出現過。

了解了為什麼會有循環後，就可以來分析一下循環的種類。

第一種：
![](https://hackmd.io/_uploads/SJndVTfuj.png)
一開始是 n 最後一樣會回到 n
第二種：
![](https://hackmd.io/_uploads/SkRRNpzOj.png)
最後的 loop 並不會回到 n 而是在某個點開始循環。

知道循環會有以下兩種可能後，或許下面的程式就會比較好懂ㄌ!
:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
long long int circle[100100]={};
int vis[100100]={}; //第一次出現在 cycle ary 裡面的 index
int main(){
    long long int n,k,tp=0; //tp => circle 陣列的最上面那一項(待填進去的地方)
    cin>>n>>k;
    long long int now=n,loop;
    while(!vis[now]){
        vis[now]=tp;
        circle[tp++]=now;
        long long temp=now,nxt=0;
        while(temp){
            nxt+=temp%10;
            temp/=10;
        }
        now=(nxt+now)%100000;
    }
    loop=vis[now]; // loop => 從circle 陣列的第幾個點開始循環。
    //假設是第一種情況 那麼 loop 就會是0
    cout<<circle[(k-loop)%(tp-loop)+loop]<<"\n";
}
```
:::


---

### [Kattis Drunk Vigenère](https://open.kattis.com/problems/drunkvigenere)

撰寫者：小麥

奇數用減的，偶數用加的。
奇數減的時候要注意，因為C++的負數MOD並不會變成正的，所以要自己加26

:::spoiler Code
```cpp=
#include <bits/stdc++.h>

using namespace std;

int main() {

    string str;
    string str2;

    cin >> str >> str2;

    string ans = "";
    int len = str.length();
    for (int i = 0; i < len; i++) {
        str[i] -= 'A';
        str2[i] -= 'A';
        
        if (i % 2 == 0) {
            int k = str[i] - str2[i];
            if (k < 0) {
                k += 26;
            } 
            ans += k % 26;
        }
        else {
            ans += (str[i] + str2[i]) % 26;
        }
    }

    for (int i = 0; i < len; i++) {
        cout << (char) (ans[i] + 'A');
    }

    cout << '\n';

    return 0;

}
```
:::

---

### [Kattis trollhunt - Troll Hunt](https://open.kattis.com/problems/trollhunt)

撰寫者：fishhh

其實只要按照題意去寫即可。

:::spoiler
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	unsigned long long t,a,b,c;
	double per;
	cin>>a>>b>>c;
	a--;
	per=b/c;
	cout<<ceil(a/per)<<"\n";
	return 0;
}
```
:::

---
### [UVa 12468 - Zapping](http://domen111.github.io/UVa-Easy-Viewer/?12468)

撰寫者：fishhh

分別去找哪一種方案所需要的次數最少就好~

:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int a,b;
    while (cin>>a>>b){
        if(a==-1)return 0;
        int ans=b-a;
        if(ans<0){
            ans+=100;
        }
        int nans=a-b;
        if(nans<0)nans+=100;
        ans=min(ans,nans);
        cout<<ans<<"\n";
    }
}
```
:::

---

### [Kattis friday - Friday the 13th](https://open.kattis.com/problems/friday)

撰寫者：fishhh

就 直接寫即可 主要是判斷範例程式中的 $w$ 可以會有循環 直接 %7 即可。

:::spoiler 參考程式碼
```cpp
#include<iostream>
using namespace std;
int main(){
    int w,n,d,m,day,tot;
    cin>>n;
    while(n--){
        cin>>d>>m;
        w=7,tot=0;
        for(int i=0;i<m;i++){
            cin>>day;
            if(day<13){
                w+=day;
                continue;
            }
            w+=12;
            if(w%7==5){
                tot++;
            }
            w+=day-12;
        }
        cout<<tot<<"\n";
        
    }
}
```
:::

---

### [Kattis Ptice](https://open.kattis.com/problems/ptice)

撰寫者：fishhh

利用餘數循環的性質算出個別每一題選什麼即可~

:::spoiler
```cpp
#include<iostream>
using namespace std;
int main(){
    int max=-999,n,t1,t2,t3;
//  cout<<0%1;
    string k;
    t1=t2=t3=0;
    cin>>n>>k;
    char adr[]={'A','B','C'},br[]={'B','A','B','C'},gor[]={'C','C','A','A','B','B'};// 3 4 6
    for(int i=0;i<n;i++){
        if(k[i]==adr[i%3]){
            t1++;
        }
        if(k[i]==br[i%4]){
            t2++;
        }
        if(k[i]==gor[i%6]){
            t3++;
        }
    }
    if(t1>t2)max=t1;
    if(t3>max)max=t3;
    if(t1>max)max=t1;
    if(t2>max)max=t2;
    cout<<max<<"\n";
    if(t1==max)cout<<"Adrian\n";
    if(t2==max)cout<<"Bruno\n";
    if(t3==max)cout<<"Goran\n";
}
```
:::

---

### [Kattis Spavanac](https://open.kattis.com/problems/spavanac)

撰寫者：fishhh

先把全部轉成分的單位 然後減45 如果變成負的再加上一天即可~

:::spoiler
```cpp
#include<iostream>
using namespace std;
int main(){
    int h,m;
    cin>>h>>m;
    m+=60*h;
    m-=45;
    if(m<0){
        m+=60*24;
    }
    cout<<m/60<<" "<<m%60;
}
```
:::

---

### [toj405](https://toj.tfcis.org/oj/pro/405/)

撰寫者：fishhh

主要觀念就是進位制轉換，可以參考前面的 TOJ292。

:::spoiler 參考程式碼
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,b,k=1,oct=0,te=0,g,d=0,h;
    cin>>a>>b;
    h=b;
    while(h){ //算長度
        d++;
        h/=10;
    }
    while(b){
        g=1;
        for(int i=0;i<d;i++){ //做次方
            g*=(b%10);
        }
        te=g; 
        oct+=(b%10)*k; //算十進位
        k*=a;
        b/=10;
    }
    if(te==oct){
        cout<<"YES\n";
        return 0;
    }
    cout<<"NO\n";
}
```
:::

---

### [UVa445](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=386)

撰寫者：fishhh

直接做就好。

:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
int main(){
    string s;
    while(getline(cin,s)){
        int cnt=0;
        for(int i=0;i<s.size();i++){
            if(s[i]<='9'&&s[i]>='0'){
                cnt+=(s[i]-'0');
            }
            else if(s[i]=='!'){
                cout<<"\n";
            }
            else{
                if(s[i]=='b')s[i]=' ';
                for(int j=0;j<cnt;j++)cout<<s[i];
                cnt=0;
            }
        }
        cout<<"\n";
    }
}
```

:::


---

### [UVa10929](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1870)

撰寫者：Eason

1. 因為這題題目有說可能會到1000位數(非常的大)
   所以絕對不是讀入數字直接取餘數
2. 判斷11的倍數可以利用一個特質
   **偶數位數的總和減掉奇數位數的總和 必須是11的倍數**

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    string s;
    while (cin >> s){
        if (s == "0") break;
        int len = s.size();
        int odd = 0, even = 0;
        for (int i = 0; i < len; i++){
            if (i % 2 == 0){
                even += (int)(s[i] - '0');
            }
            else{
                odd += (int)(s[i] - '0');
            }
        }
        if ((odd - even) % 11 == 0){
            cout << s << " is a multiple of 11.\n";
        }
        else{
            cout << s << " is not a multiple of 11.\n";
        }
    }
    return 0;
}
```
:::

---

### [UVa 11879](http://domen111.github.io/UVa-Easy-Viewer/?11879)

撰寫者：小麥

102 = (1 * 100) + (0 * 10) + (2 * 1)
的原理，所以可以使用MOD一位一位的取模。

:::spoiler Code
```cpp=
#include <bits/stdc++.h>

using namespace std;

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string str;
    while (cin >> str && str != "0") {
        int sum = 0;

        int len = str.length();
        for (int i = 0; i < len; i++) {
            sum *= 10;
            sum += str[i] - '0';
            sum %= 17;
        }

        cout << (sum == 0)  << '\n';
    }

    return 0;

}
```
:::

---

## 二章－第四節

### [No_Judge 總價格](https://hackmd.io/18aJIgTtSxiZ4K7vLmlyHw#%E7%B8%BD%E5%83%B9%E6%A0%BC)

撰寫者：fishhh

全部相加後輸出。
請觀察題目下面附的[連結](https://docs.google.com/spreadsheets/d/1Ze1A6ir3bia4PMpFgP_VHM92gMyNwUlSN-hMiMc0wSw/edit?usp=sharing)

---

### [No Judge - 次高級硬體](https://hackmd.io/18aJIgTtSxiZ4K7vLmlyHw#%E6%AC%A1%E9%AB%98%E7%B4%9A%E7%A1%AC%E9%AB%94)

撰寫者：fishhh

基礎的請去看講義下面附的code

這裡提供一個較為簡潔的程式。

:::spoiler
```cpp
#include "iostream"
using namespace std;
int main(){
    int n;
    cin>>n;
    int ary[200]={};
    for(int i=0;i<n;i++)cin>>ary[i];
    int tmax=0,secmax=0;
    for(int i=0;i<n;i++){
        if(ary[i]>tmax){
            secmax=tmax;
            tmax=ary[i];
        }
        else if(ary[i]>secmax&&ary[i]!=tmax)secmax=ary[i];
    }
    cout<<secmax<<"\n";
}
```
:::

---

### [No Judge - 位數判斷](https://hackmd.io/fmJHEIwIR0q9ms7kM-DjOQ#%E4%BD%8D%E6%95%B8%E5%88%A4%E6%96%B7)

撰寫者：fishhh

寫完再來看><
:::spoiler 答案程式碼
wrang case n=11
```cpp
#include <iostream>
using namespace std;

int main()
{
	int n, t, r; // r 要初始化
	cin >> n;
	for (t=n; t>0; t--) //把 t--弄掉
	{
		r++;
		t /= 10;
	}
	cout << r << '\n';
	return 0;
}
```
:::

---

### [No Judge - 質數判別](https://hackmd.io/fmJHEIwIR0q9ms7kM-DjOQ#%E8%B3%AA%E6%95%B8%E5%88%A4%E5%88%A5)

撰寫者：fishhh

寫完再來看><
:::spoiler 答案程式碼
```cpp
#include <iostream>
using namespace std;

int main()
{
	int n, i, p;
	cin >> n;
	for (i=1, p=1; i*i<n; i++) // i start form 2(wrang case :all) , i*i<=n(wrang ase : 49)
	{
		if (n % i == 0)
		{
			p = 0;
			break;
		}
	}
	if (p)
	{
		cout << "prime\n";
	}
	else
	{
		cout << "not prime\n";
	}
	return 0;
}
```
:::

---

### [TOJ 120](https://toj.tfcis.org/oj/pro/120/)

撰寫者：小麥

前綴合裸題，唯一要注意的是頭尾有可能反過來。

:::spoiler
```cpp=
#include <bits/stdc++.h>

using namespace std;

int arr[(int) 2e6 + 5];
long long pf[(int) 2e6 + 5];

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        pf[i] = pf[i-1] + arr[i-1];
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        
        if (a > b) {
            int c = a;
            a = b;
            b = c;
        }

        cout << (pf[b] - pf[a - 1]) << '\n';
    }

    return 0;

}
```
:::

---


