2020年6月28日 星期日

APCS(2016/03/05) b964: 第 1 題 成績指標

題目來源:https://zerojudge.tw/ShowProblem?problemid=b964
一次考試中,於所有及格學生中獲取最低分數者最為幸運,反之,於所有不及格同學中,獲取最高分數者,可以說是最為不幸,而此二種分數,可以視為成績指標。
請你設計一支程式,讀入全班成績(人數不固定),請對所有分數進行排序,並分別找出不及格中最高分數,以及及格中最低分數。

當找不到最低及格分數,表示對於本次考試而言,這是一個不幸之班級,此時請你印出「worst case」;反之,當找不到最高不及格分數時,請你印出「best case」。

( 註:假設及格分數為 60 )。
輸入說明
第一行輸入學生人數,第二行為各學生分數(0~100 間),分數與分數之間以一個空白間格。
每一筆測資的學生人數為 1~20 的整數。


輸出說明
每筆測資輸出三行。

第一行由小而大印出所有成績,兩數字之間以一個空白間格,最後一個數字後無空白;
第二行印出最高不及格分數,如果全數及格時,於此行印出 best case
第三行印出最低及格分數,如果全數不及格時,於此行印出 worst case

範例輸入 #1                                範例輸出 #1
10                                                0 11 22 33 44 55 66 77 88 99
0 11 22 33 55 66 77 99 88 44     55
                                                    66



範例輸入 #2                                範例輸出 #2
1                                                    13
13                                                  13
                                                      worst case

範例輸入 #3                                範例輸出 #3
2                                                    65 73
73 65                                             best case
                                                      65

解題心得:
跟一般單純求最大值的條件有點不同,這題是求大數字中的最小值與小數字中的最大值,把條件式釐清楚,相信這題是可以把握的分數。

以下附上程式碼,如果有問題請在下方留言或是EMAIL給我囉。
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(false);
    int n , m , i;
    vector<int> v;
    while(cin >> n) {
        v.clear();
        int maxs = 101,mins = -101;
        while(n-- > 0) {
            cin >> m;
            for(i = 0; i < v.size(); i++) {
                if(v[i] > m) {
                    break;
                }
            }
            v.insert(v.begin() + i , m);
            if(m < 60) {
                mins = max(mins , m);
            } else if(m >= 60) {
                maxs = min(maxs , m);
            }
        }
        for(i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << '\n';
        if(mins == -101) {
            cout << "best case\n";
        } else {
            cout << mins << '\n';
        }
        if(maxs == 101) {
            cout << "worst case\n";
        } else {
            cout << maxs <<'\n';
        }
    }

    return 0;
}

2020年6月22日 星期一

d732: 二分搜尋法 解題心得

題目連結:https://zerojudge.tw/ShowProblem?problemid=d732

給你一個嚴格遞增的數列A1,A2,A3.....An(1<=n<=100000), &下面有幾個問題的詢問數k(1<=K<=100000),以及k個詢問的整數x,求數列中是否存在一個Ai(1<=i<=n)的值與X相等?

輸入說明
第一行包含兩個整數n,k分別表示數列長度以及詢問數,第二行包含n個整數第i(1<=i<=n)個整數依序為數列中Ai的值,第三行包含k個詢問的整數x. 

輸出說明
對於每個詢問整數x對應一行輸出:
輸出i的值其中1<=i<=n且Ai=x若沒有這樣的i值請輸出0代替.

範例輸入 #1            範例輸出 #1
5 5                            2
1 3 4 7 9                   1
3 1 9 7 -2                  5
                                 4
                                 0

很標準的2元搜尋法,是很好的練習題。

以下附上程式碼,如果有什麼問題請留言或寄信給我囉。

#include <iostream>
using namespace std;

int main()
{
    cin.tie(0), cin.sync_with_stdio(false);
    int n , m;
    cin >> n >> m;
    int* v = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    int a;
    for(int i = 0; i < m; i++) {
        cin >> a;
        int start = 0;
        int end = n;
        int mid = (start + end) >> 1;
        bool find = false;
        while(true) {
            if(v[mid] > a) {
                end = mid;
            } else if(v[mid] < a) {
                start = mid;
            } else {
                find = true;
                break;
            }
            
            if(mid == (end + start) >> 1) break;
            mid = (end + start) >> 1;
            
        }
        find ? cout << mid+1 <<endl : cout << 0 << endl;
    }

    return 0;
}

e788: b3.畢業典禮(Ceremony) TOI練習賽 解題心得

第一行輸入一個正整數N(1≤ N ≤ 100),表示共有幾位學生;接著輸入N行,每行皆有一個學號IDID為9個字元,由8個數字與一個英文大寫字母所組成)及英文姓名s(1≤ |s|≤ 10,即姓名不超過10個字元),ID與s中間以空白區隔。

學務處已收到所有報名參加畢業典禮的學生學號,需要你協助撰寫一個程式來列出學生上台的順序表。

※上台規則如下:

1、依照學院代碼A~Z的順序。

2、若學院代碼相同,依學號開頭由小到大,4(學士)à6(碩士) à8 (博士)。

3、若學院代碼、學號開頭皆相同,則依報名順序排列。

這題就是標準準的大數據排序,看題目大概就猜得出不是我最愛的氣泡排序可以搞定,所以這題就是改用二元搜尋法來解決。這題要注意的是排序有兩個條件,所以在二元搜尋法的使用上需要有一些改變。

如果還是有什麼不清楚的地方,歡迎留言或來信,我會做更進一步的解釋。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    cin.tie(0), cin.sync_with_stdio(false);
    cout.tie(0), cout.sync_with_stdio(false);
    vector<string> v;
    string s;
    int n;
    cin >> n;
    getline(cin, s);
    for (int x = 0; x < n; x++) {
        getline(cin, s);
        bool find = false;
        int start = 0, end = x, mid = (start + end) >> 1;
        while (mid != start) {
            if (s[8] < v[mid][8]) {
                end = mid;
            }
            else if (s[8] > v[mid][8]) {
                start = mid;
            }
            else {
                int j = mid;
                while (true) {
                    if (j == -1) {
                        break;
                    }
                    if (s[8] == v[j][8]) {
                        j--;
                    }
                    else {
                        break;
                    }
                }
                j++;
                while (true) {
                    if (j == x || s[8] != v[j][8] || s[0] < v[j][0]) {
                        mid = j;
                        find = true;
                        break;
                    }
                    j++;
                }
            }
            if (find)  break;
            mid = (start + end) >> 1;
        }
        if (find) {
            v.insert(v.begin() + mid, s);
        }
        else if (v.size() > mid) {
            if ((v[mid][8] == s[8] && v[mid][0] <= s[0] ) || v[mid][8] < s[8]) {
                v.insert(v.begin() + mid +1, s);
            } else
                v.insert(v.begin() + mid, s);
        }
        else {
            v.push_back(s);
        }
    }
    for (int i = 0; i < v.size(); i++) {
        cout << v[i][8] << ":" << v[i].substr(9, 100) << endl;
    }


    return 0;
}

2020年6月14日 星期日

a225: 明明愛排列 解題心得

題目來源:https://zerojudge.tw/ShowProblem?problemid=a225
明明有自己獨特的排列數組的方式,EX:如果數字有 38 106 98 26 13 46 51 的話,那麼 51 會排最前面,因為個位數字 1 是其中最小的一個。
而 106 26 46 這三個數字,個位數同樣都是 6,所以明明會直接將他們由大至小排,也就是 106 46 26。
所以,排好之後是:51 13 106 46 26 98 38。

輸入有多組,每組的第一行有一個正整數,代表接下來會有幾個數字要被排序。


這題只是在基本的排序規則上,再多加了一些條件,其實本身的問題不大。


以下附上程式碼:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while(cin >> n) {
        vector<pair<int , int>> v;
        for(int i = 0; i < n; i++) {
            int x;
            cin >> x;
            pair<int , int> p;
            p.first = x % 10;
            p.second = x;
            bool find = false;
            for(int j = 0; j < i; j++) {
                if(v[j].first > p.first || (v[j].first == p.first && v[j].second < p.second)) {
                    v.insert(v.begin() + j , p);
                    find = true;
                    break;
                } 
            }
            if(!find) v.push_back(p);
        }
        for(int i = 0; i < n; i++) {
            cout << v[i].second << " ";
        }
        cout << endl;
    }

    return 0;
}

a216. 數數愛明明 解題心得

題目來源:https://zerojudge.tw/ShowProblem?problemid=a216

f(n) = n + f(n-1)
g(n) = f(n) + g(n-1)
已知N,求f(n)跟g(n)
f(1) = g(1) = 1,
有空可以好好看一下這題的題目,這是一個很典型的出題方式,題目內百分之90都是沒有用的文字,在時間有限的競賽或檢定內,統整跟篩選出有效益的資訊也是很重要的能力。
在這題的解題過程裡,比較要注意的是資料的大小,會超過INT所能儲存的極限。

以下附上程式碼:
#include <iostream>
#include <array>

using namespace std;

int main()
{
    array<long long , 30001> f;
    array<long long , 30001> g;
    f[1] = g[1] = 1;
    for(int i = 2; i <= 30000; i++) {
        f[i] = i + f[i-1];
        g[i] = f[i] + g[i-1];
    }
    int n;
    while(cin >> n) {
        cout << f[n] << " " << g[n] << endl;
    }

    return 0;
}

2020年6月11日 星期四

a215: 明明愛數數 解題心得

題目來源:https://zerojudge.tw/ShowProblem?problemid=a215
明明從n開始數,依序為n+1 , n+2 , n+3....,如果將這些數過的數加總,需要幾次才能超過m

例如:
1 5(n = 1, m = 5),
1 + 2 + 3 > 5。
所以基本上這題跑個遞迴就可以解決了,只是要小心的是n,m的範圍並沒有限制,所以需要將赴數也考慮進來。

以下附上程式碼。如果還有任何問題請在下面留言,或是直接寄信給我囉。


#include <iostream>
#include <limits.h>

using namespace std;

int main()
{
    cin.tie(0), cin.sync_with_stdio(false);
    int t , n;
    while(cin >> t >> n) {
        int sum = t;
        int count = 1;
        while(sum <= n) {
            sum += t + count++;
        }
        cout << count << endl;
    }

    return 0;
}

a149: 乘乘樂 解題心得

給定一組數字N,找出N的每個位數相乘的加總。如365 = 3 * 6 * 5,這題只要善用遞迴與取餘數就可以解決。

以下附上程式碼。如果還有任何問題請在下面留言,或是直接寄信給我囉。

#include <iostream>

using namespace std;

int main()
{
    int t , n;
    cin >> t;
    while(t-- > 0) {
        cin >> n;
        if(n == 0) {
            cout << 0;
            continue;
        }
        int sum = 1;
        while(n > 0) {
            sum *= n % 10;
            n /= 10;
        }
        cout << sum << endl;
    }

    return 0;
}

a044: 空間切割 解題心得

題目:
    對任意正整數n,空間中的n 個平面最多可將空間切成幾個區域?

這題算是程式題目中的數學題目了。

以下附上程式碼。如果還有任何問題請在下面留言,或是直接寄信給我囉。

#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin >> n) {
        int sum = 1;
        for (int k = 1; k <= n; k++) {
            sum += 1 + k * (k - 1) / 2;
        }
        cout <<sum <<endl;
    }

    return 0;
}

2020年6月10日 星期三

b944: 好想上廁所(男廁篇) 解題心得

題目連結:

一開始給予一個整數n (0<n<21),作為小便斗的數量上限。

然後給予兩個整數a,b (0<=a,b<2147483647),作為下一個男生的編號和使用時間。

測資讀入直到EOF。所有的男生搜尋空閒小便斗時都會從編號最小的開始找。

如果使用時間為0,依然會占用小便斗直到下一個人進來。

由於男生找廁所的條件是,盡量挑選旁邊沒人的小便斗,如果真的沒得挑,才會將就於旁邊友人的小便斗,最簡單的方式就是跑兩次FOR-LOOP,第一次一個條件判斷觀察左右兩邊有沒有人,要小心的是觀察的對象不要超過邊界了,如果第一次沒找滿意的位置,第二次再判斷只要有空位就得上,這樣就可以順利完成了。



以下附上程式碼。如果還有任何問題請在下面留言,或是直接寄信給我囉。
#include <iostream>
#include <vector>
#include <string>
#pragma GCC optimize("Ofast,no-stack-protector")
using namespace std;
int main()
{
	cin.tie(0), cin.sync_with_stdio(false);
	int n;
	cin >> n;
	vector<long long> v;
	vector<long long> time;

	for (int i = 0; i < n; i++) {
		v.push_back(0);
		time.push_back(0);
	}
	long long a, b;
	while (cin >> a >> b) {
		bool find = false;
		for (int i = 0; i < n; i++) {
			if (v[i] == 0) {
				if (i - 1 >= 0) {
					if (v[i - 1] != 0) continue;
				}
				if (i + 1 < n) {
					if (v[i + 1] != 0) continue;
				}
				v[i] = a;
				time[i] = b;
				find = true;
				break;
			}
		}
		if (find == false) {
			for (int i = 0; i < n; i++) {
				if (v[i] == 0) {
					v[i] = a;
					time[i] = b;
					find = true;
					break;
				}
			}
		}
		if (find == false) {
			cout << "Not enough" << endl;
		}
		string num = "Number: ";
		string tim = "Time: ";

		for (int i = 0; i < n; i++) {
			num += to_string(v[i]) + " ";
			tim += to_string(time[i]) + " ";
			if (time[i] != 0) {
				time[i]--;
			}
			if (time[i] == 0) {
				v[i] = 0;
			}
		}
		cout << num << endl;
		cout << tim << endl;
	}
}

2020年6月9日 星期二

a003: 兩光法師占卜術 解題心得

陰陽
這題很適合初心者拿來做練習,練習將腦中的條件式轉化為IF、ELSE的條件式。


以下附上程式碼,如果還有任何問題請在下面留言,或是直接寄信給我囉。
#include <iostream>
using namespace std;

int main()
{
    int m, d , s;
    while (cin >> m >> d) {
        s = (m * 2 + d) % 3;
        switch (s) {
        case 0:
            cout << "普通";
            break;
        case 1:
            cout << "吉";
            break;
        case 2:
            cout << "大吉";
            break;
        }
    }
}

2020年6月8日 星期一

d097: 10038 - Jolly Jumpers 解題心得

people man travel

大學程式檢定CPE 2012/12/18 Jolly Jumpers
題目來源:https://zerojudge.tw/ShowProblem?problemid=d097


解題的方法很多,SET、MAP,或是建立ARRAY都可以,每次相減求出的差值得絕對值,重複驗證有沒有在範圍限制內及有沒有重複出現,直到結束。

以下附上本題程式碼,如果還有任何問題請在下面留言,或是直接寄信給我囉。
def check():
    try:
        while True:
            a = list(map(int , input().split()))
            arr = [i for i in range(0,a[0])]
            t = False
            for i in range(2 , len(a)):
                if abs(a[i] - a[i - 1]) >= len(arr) or abs(a[i] - a[i - 1]) == 0 or arr[abs(a[i] - a[i - 1])] != abs(a[i] - a[i - 1]):
                    print("Not jolly")
                    t = True
                    break
                arr[abs(a[i] - a[i - 1])] = 0;

            if t == False:
                print("Jolly")

    except EOFError:
        pass

check()

c521: 6. 顯微探測 解題心得

Virus, Microscope, Infection, Disease, Death, Medical

2017高雄市資訊學科能力複賽


數學不好,不知道有什麼數學公式能解決這個問題,如果你是跟我依樣數學不怎麼樣的工程師,請學會觀察,觀察測資與結果的關係。以範例四為例:
s0 + s1 + s2 = 2             0
s0 + s1 + s2 + s3 = 2     1
s0 + s1 + s2 + s3 + s4 = 3     2
        s1 + s2 + s3 + s4 + s5 = 2     3
                s2 + s3 + s4 + s5 + s6 = 3    4
                        s3 + s4 + s5 + s6 = 2    5
                                s4 + s5 + s6 = 2    6
S0代表第一隻細菌發出的光強度,如果想算出所有的細菌的加總,就是2 + 2 = 4如下圖。
故程式碼如下:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> v;
v.assign(n, 0);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
long long sum = 0;
for (int i = 0; i <= k; i++) {//可接受的起點,超過K就取不到第一隻細菌
int j = i;
sum = 0;
for (j = j; j < n - k - 1;) {
sum += v[j];
j += 2 * k + 1;//
}
if (j == n - 1 || (j+k > n and j < n)) {
sum += v[j];
cout << sum << endl;
break;
}
}
}


如果還是不清楚請在下面留言,或是EMAIL我,我會一一回覆。

h206. 強者就是要戰,但......什麼才是強者呢?

         這題是很好的遞迴問題,每次遞迴的時候都要帶入此次遞迴的左右邊界、及這次是要取區間最大還是取區間最小的flag。         完整程式如下: def t (l , r , isBig) : if l == r -1 : retur...