# uVA
[TOC]
## 考前必讀
1\. I/O 處理
2\. STL Container
3\. STL Algorithm
1. sort
2. lower_bound
3. upper_bound
4\. String 處理
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s = "xxxabccd";
string cmpS = "xxxb";
cout << s.compare(cmpS); // return 0 if equal
cout << s.substr(0, 5); // substr(pos, length)
s.push_back(65); // s = s + 'A'
s.push_back(*(char*)"a"); // s = s + 'a'
cout << s.length();
string s1 = "abc";
transform(s1.begin(), s1.end(), s1.begin(), ::toupper);
cout << s1;
return 0;
}
```
5\. 萬能標頭檔案 `#include<bits/stdc++.h>`
6\. 基本數學
- 建立質數表
- 找最大公因數
- 定義 PI
## 演算法模板
### 廣度優先搜尋 & 深度優先搜尋
```c++
// 深度優先框架
bool DeepSearch(node_t node, int target) {
stack <node_t> stk;
stk.push(node);
while (stk.length() > 0) {
node_t currNode = stk.top();
stk.pop();
if (currNode.value == target) {
return True;
}
if (currNode.left != null) {
stk.push(currNode.left);
}
if (currNode.right != null) {
stk.push(currNode.right);
}
}
}
```
- 廣度優先：
- 把 stack 換成 queue
- 把 top() 換成 front()
### 二分搜尋
```c++
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return target;
if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
```
### DP
個人覺得的重點：
- 定義結束條件
- 定義邊界
- 問題與子問題的關係？
- bottom to top？
### Floyd warshall
找一個中點 K ，看看以下兩個走法哪個比較短：
- 從 i 到 j 的路徑
- 從 i 到 k ，再從 k 走到 j 的路徑
- 窮舉法
- 不能處理 Negative cycle
```c++
#include <iostream>
#define min(a, b) ((a < b) ? (a) : (b))
int main()
{
int n;
std::cin >> n >> endl;
int dis[n + 1][n + 1];
for (int k = 1; k <= n; k++)
{
for (int i = 0; i <= n; i++)
{
for (size_t j = 0; j <= n; j++)
{
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
return 0;
}
```
### GCD
找最大公因數：
- 使用輾轉相除法
```cpp=
#include<iostream>
using namespace std;
int main()
{
int a, b, t;
while( cin >> a >> b )
{
while( b!=0 )
{
t = b;
b = a%b;
a = t;
}
cout << a << endl;
}
return 0;
}
```
## GPE
### 2008-37:Prefix expression evaluation
:::info
Hint
```
- * + 23 % 45 10 6 / 77 12
```
is the prefix expression of the following statement
```
{[23+(45%10)]*6}-(77/12)
```
:::
:::success
將輸入依序從尾部到頭部進行掃描，以 `- * + 23 % 45 10 6 / 77 12` 為例子：
- 第一圈：
- 12 -> stack (stack: 12)
- 第二圈：
- 77 -> stack (stack: 77 12)
- 第三圈：
- 遇到運算符號，將 stack 上的兩個元素取出來，運算後丟回 Stack
- 6 -> stack (stack: 6)
- 第四圈：
- 6 -> stack (stack: 6 6)
- 第五圈：
- 10 -> stack (stack: 10 6 6)
- 第六圈：
- 45 -> stack (stack: 45 10 6 6)
- 第七圈：
- `%`
- 5 -> stack (stack: 5 6 6)
- 第八圈：
- 23 -> stack (stack: 23 5 6 6)
- 第九圈：
- `+`
- 28 -> stack (stack: 28 6 6)
- 第十圈：
- `*`
- 144 -> stack (stack: 144 6)
- 第十一圈：
- `+`
- 150
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
double evaluatePrefix(string prefixExp) {
stack<double> operendStack;
int size = prefixExp.size() - 1;
for (int i = size; i >= 0; i--) {
if (isdigit(prefixExp[i]))
operendStack.push(prefixExp[i] - '0');
else {
double o1 = operendStack.top();
operendStack.pop();
double o2 = operendStack.top();
operendStack.pop();
if( prefixExp[i] == '+')
operendStack.push(o1 + o2);
else if( prefixExp[i] == '-')
operendStack.push(o1 - o2);
else if( prefixExp[i] == '*')
operendStack.push(o1 * o2);
else if( prefixExp[i] == '/')
operendStack.push(o1 / o2);
else{
cout<<"Invalid Expression";
return -1;
}
}
}
return operendStack.top();
}
int main()
{
string prefixExp = "*+69-31";
cout<<"The result of evaluation of expression "<<prefixExp<<" is "<<evaluatePrefix(prefixExp);
return 0;
}
```
## 2013-12-17 CPE
### 12602 - [Nice Licence Plates](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/12602.pdf)
:::info
Alberta的車牌當前格式為ABC-0123(三個字母後跟著四個數字)。
如果第一部分的值和第二部分的值之間的絕對差最大為100，則此車牌是"nice"。
第一部分的值計算為以26為底的數字(其中[A-Z]中的數字)的值。
例如，如果第一部分是"ABC"，則其值為28 (0*26^2 + 1*26^1 + 2*26^0)。
因此，"ABC-0123"車牌很好，因為|28-123| ≤ 100。
我們將會給定車牌號碼列表，您的程式要確認車牌是否"nice"或者"not nice"。
:::
:::success
把車牌的英文轉換成對應的數字，再取兩者絕對差判斷是否小 100。
:::
```cpp=
#include <iostream>
#include <cstdlib>
// cstdlib: atoi
using namespace std;
inline int deA(char c) {return c - 'A';}
int main(){
int case_n;
cin >> case_n;
while(case_n--) {
char input[9];
cin >> input;
int scoreA = deA(input[0]) * 26 * 26 + deA(input[1]) * 26 + deA(input[2]);
int scoreB = atoi(input + 4);
if(abs(scoreA - scoreB) <= 100)
cout << "nice\n";
else
cout << "not nice\n";
}
return 0;
}
```
### 10235 - [Simply Emirp](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10235.pdf)
:::info
一個比 1 大的整數如果只有 1 和他本身自己共 2 個因數，我們稱這個數為質數（prime number）。多年來質數一直被數學家們研究著。質數也常被應用在密碼學和編碼理論中。
那麼你曾經把質數倒轉過來嗎？對大部分的質數來說，你將會得到一個組合數（例如：43 變成 34）現在，我們要定義 Emirp（就是把 Prime 反過來拼）：如果你把一個質數反過來之後，他仍然是一個質數，並且和原來那個質數不同，那我們就稱這個數為 emirp number。例如：17 是一個emirp，因為 17 和 71 都是質數。在這個問題中，你必須要決定某一個整數 N 是非質數，質數，或 emirp。你可以假設 1<N<1000000。
:::
:::success
這題會有幾個步驟：
1. 製作質數表
```cpp=
#include <iostream>
using namespace std;
int main()
{
int queryMap[1005] = {0};
for (int i = 2; i < 1000; i++) {
if (queryMap[i]) {
continue;
}
for (int j = 2*i; j < 1000; j+=i) {
queryMap[j] = 1;
}
}
for (int i = 2; i < 1000; i++) {
cout << i << ": " << (queryMap[i]>0?"NotPrime":"isPrime") << endl;
}
return 0;
}
```
2. 將待判斷數字反轉：
```cpp=
for(rn = 0; n; n /= 10) rn = rn * 10 + (n % 10);
```
:::
```cpp=
#include<iostream>
using namespace std;
int com[1000000];
int main() {
for(int i = 2; i < 1000; i++) {
if(com[i])
continue;
for(int j = i + i; j < 1000000; j += i)
com[j] = 1;
}
int n, rn;
while(cin >> n) {
int sn = n;
for(rn = 0; n; n /= 10) rn = rn * 10 + (n % 10);
if(com[sn]) cout << sn << " is not prime.";
else if(com[rn]) cout << sn << " is prime.";
else if(sn == rn) cout << sn << " is prime.";
else cout << sn << " is emirp.";
cout << endl;
}
return 0;
}
```
### 11917 - [Do Your Own Homework!](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11917.pdf)
:::info
這幾天Soha非常忙，以至於他沒有時間寫作業。
但這不是一個大問題，因為他有很多願意幫助他的朋友，其中一個就是Sparrow。
每當Soha被分配任何作業時，他都會向Sparrow尋求她的幫助。
Sparrow給出了她喜歡的科目列表，以及完成每個科目的作業所需的天數。
Soha只有 D 天的時間來完成他的作業。不過還好教授允許可以遲交最多 5 天。
這意味著教授將不接受從現在起 D+5 天之後的任何提交。
Sparrow這次能為Soha做到嗎？
:::
```cpp=
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main() {
int caseNum, listNum, useDay, limitDay;
string useCourse, limitCourse;
map<string, int> myList;
// get case number
cin >> caseNum;
for(int i = 0; i < caseNum; i++) {
// initialize
myList.clear();
// get number of schedule
cin >> listNum;
for(int j = 0; j < listNum; j++) {
// get schedule
cin >> useCourse >> useDay;
// put into map
myList[useCourse] = useDay;
}
// get limit day and course
cin >> limitDay >> limitCourse;
// output
cout << "Case " << i + 1 << ": ";
if(myList.find(limitCourse) == myList.end()) {
// the course is not in the schedule
cout << "Do your own homework!" << endl;
}
else if(myList[limitCourse] <= limitDay) {
// finished on the limit day
cout << "Yesss" << endl;
}
else if(myList[limitCourse] <= (limitDay + 5)) {
// finished over than limit day but not over than 5 days
cout << "Late" << endl;
}
else {
// finished over than limit day + 5
cout << "Do your own homework!" << endl;
}
}
return 0;
}
```
## 2014-03-25 CPE
### 10931 - [Parity](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10931.pdf)
:::info
整數 n 的「同位元」定義為：其二進位表示法中每位元的和再除以 2 的餘數。例如：21 = 101012 的二進位有三個 1，因此它的同位元為 3 (mod 2)，或 1。
在此，你要計算一個整數 1 ≤ I ≤ 2147483647 的同位元。
:::
- 利用 bitwise 做 Mask
```cpp=
#include <iostream>
const unsigned int MASK = 1<<31;
int main(){
using namespace std;
int input;
while(cin >> input,input){
cout << "The parity of ";
unsigned int mask = 1<<31;
int count = 0;
for(;mask&& !(mask&input);mask >>= 1);
for(;mask;mask >>= 1){
cout << 0 + !!(mask & input);
count += !!(mask & input);
}
cout << " is " << count << " (mod 2)."<< endl;
}
return 0;
}
```
### 00401 - [Palindromes](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/401.pdf)
:::info
迴文字串是一串數字或字母，從左到右讀取和從右到左讀取相同。
例如，"ABCDEDCBA"是迴文字串。
鏡像字串是一種字串，當該字串的每個元素更改為鏡像(如果它具有鏡像)並且從右到左讀取該字串時，其結果與從左到右讀取原始字串相同。
例如，"3AIAE"是鏡像字符串，因為"A"的鏡像和"I"的鏡像是他們自己，而"3"和"E"為彼此的鏡像。
鏡像迴文是指符合迴文字串標準和鏡像字串標準的字串。
例如，"ATOYOTA"是一個鏡像迴文，"A"、"T"、"O"、"Y"為彼此的鏡像。
該字串從左到右讀取和從右到左讀取相同。
並且每個字元都鏡像替換後從右到左讀取結果，與從左到右讀取原始字串相同。
以下為有效字元鏡像對應表：
:::
```cpp=
#include<stdio.h>
#include<iostream>
#include<map>
using namespace std;
string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ123456789";
string r = "A 3 HIL JM O 2TUVWXY51SE Z 8 ";
int main() {
string line;
bool m = true;
bool p = true;
map<char, char> map;
for(int i = 0; i < s.length(); i++)
map[s[i]] = r[i];
while(cin >> line) {
m = true;
for(int i = 0; i < line.length() / 2 + line.length() % 2; i++)
if(line[line.length() - i - 1] != map[line[i]])
m = false;
p = true;
for(int i = 0; i < line.length() / 2; i++)
if(line[line.length() - i - 1] != line[i])
p = false;
if(!m && !p)
cout << line << " -- is not a palindrome.\n";
else if(!m && p)
cout << line << " -- is a regular palindrome.\n";
else if(m && !p)
cout << line << " -- is a mirrored string.\n";
else
cout << line << " -- is a mirrored palindrome.\n";
cout << endl;
}
return 0;
}
```
### 00406 – [Prime Cuts](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/406.pdf)
:::info
質數的定義為：除了1和它本身之外，沒有別的數可以整除它的。（請注意：在本問題中，1被定義為質數）
你的任務是，給你N及C，請你找出1到N中所有的質數，並把他們排成一列（假設共有K個）。如果K是偶數，請輸出中間那C*2個質數。如果K是奇數，則輸出中間那(C*2)-1個質數。
:::
- 本問題中將 1 認定為質數
```cpp=
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1005;
int prime[maxn]; // 0:prime
vector <int> v;
int main() {
int N, C, K, p;
// 建立質數表
prime[0] = 1;
p = 2;
v.push_back(1);
while (p <= maxn){
if (!prime[p]) {
v.push_back(p);
for (int i=2*p; i<maxn; i+=p)
prime[i] = 1;
}
p++;
}
while (cin >> N >> C){
// 找出大於等於 N 的第一個質數
// http://c.biancheng.net/view/7521.html
auto it = lower_bound(v.begin(), v.end(), N);
K = (int)(it - v.begin());
// 如果第一個質數恰好為 N，K + 1 (因為題目的範圍包含 N)
if (*it == N) {
K++;
}
cout << N << ' ' << C << ":";
for (int i=max(0, K/2 - C + (K % 2)); i<min(K, K/2+C); i++){
cout << ' ' << v[i];
}
cout << '\n';
}
return 0;
}
```
## 2014-05-27 CPE
### 10783: [Odd Sum](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10783.pdf)
:::info
給你一個範圍 a 到 b ，請你找出 a 與 b 之間所有奇數的和。
例如：範圍 [3, 9] 中所有奇數的和就是 3 + 5 + 7 + 9 = 24 。
:::
```cpp=
#include <iostream>
using namespace std;
int main() {
int t, ti = 0;
cin >> t;
int arr[101] = {};
for(int i = 1; i < 101; ++i) {
if(i % 2 == 1)
arr[i] = i;
arr[i] += arr[i-1];
}
while(ti++ < t) {
int a, b;
cin >> a >> b;
if(a == 0)
a = 1;
cout << "Case " << ti << ": " << arr[b] - arr[a-1] << endl;
}
return 0;
}
```
### 00141: [The Spot Game](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/141.pdf)
:::info
放 石頭遊戲(The game of Spot)在一塊 NxN 的板子上進行，如下圖為N=4的板子。遊戲的玩法是兩個玩家輪流放一塊石頭在空的格子上，或是可以從板子上拿一塊石頭起來，遊戲的進行中可以發現，板子上 石頭的佈局會不斷變化，當一玩家排出已重複出現過的佈局時，他就算輸了這一局(一種佈局如果將之旋轉90度、180度、270度亦視為相同的佈局)。若在 2N步內未出現過相同的佈局就算和局。
請 參考下列幾種佈局：
若 出現過第一種佈局，則再出現2、3、4種佈局即結束比賽(還有另一種能結束比賽的佈局未畫出)，注意，第5種佈局並不能算是相同的佈局。
:::
```cpp=
#include <stdio.h>
#include <iostream>
#include <map>
using namespace std;
void rotate(int x[][50], int n) {
int y[50][50], i, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
y[j][n - i - 1] = x[i][j];
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
x[i][j] = y[i][j];
}
int main() {
int n;
while(scanf("%d", &n), n) {
map<string, int> r;
int m = 2 * n, board[50][50] = {}, x, y;
int flag = -1, move;
char cmd[3];
for(int i = 0; i < m; i++) {
scanf("%d %d %s", &x, &y, cmd);
if(flag != -1) continue;
x--, y--;
if(cmd[0] == '+')
board[x][y] = 1;
else
board[x][y] = 0;
string s = "";
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
s += (board[j][k] + '0');
if(r[s] == 1) {
flag = i & 1;
move = i;
continue;
}
for(int rr = 0; rr < 4; rr++) {
string s = "";
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
s += (board[j][k] + '0');
r[s] = 1;
rotate(board, n);
}
}
if(flag == -1)
puts("Draw");
else
printf("Player %d wins on move %d\n", !flag + 1, move + 1);
}
return 0;
}
```
### 105 - [The Skyline Problem](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/105.pdf)
:::info
由於高速繪圖電腦工作站的出現，CAD（computer-aided design）和其他領域（CAM,VLSI設計）都充分使用這些電腦的長處。而在本問題中，你必須幫助建築師，根據他所提供給你都市中建築物的位置，你得幫他找出這些建築物的空中輪廓（skyline）。為了使問題容易處理一些，所有的建築物都是矩形的，並且都建築在同一個平面上。你可以把這城市看成一個二度平面空間。每一棟建築物都以(Li Hi Ri)這樣的序列來表示。其中Li 和 Ri分別是該建築物左邊和右邊的位置，Hi則是建築物的高度。下方左圖就是(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)這八棟建築物的位置圖。而你的任務就是畫出這些建築物所構成的輪廓，並且以(1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)這樣的序列來表示如下方右圖的輪廓。
:::
```cpp=
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int skyline[10005] = {0};
int L, H, R;
int rightest = 0;
bool space = false;
while( scanf( "%d%d%d", &L, &H, &R ) != EOF ){
for( int i = L ; i < R ; i++ )
if( H > skyline[i] ) skyline[i] = H;
if( R > rightest ) rightest = R;
}
for( int i = 1 ; i <= rightest ; i++ )
if( skyline[i-1] != skyline[i] ){
if( space ) printf( " " );
space = true;
printf( "%d %d", i, skyline[i] );
}
printf( "\n" );
return 0;
}
```
## 2014-09-23 CPE
### 579 - [ClockHands](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/579.pdf)
:::info
在一般的時鐘上通常有兩根指針：時針、分針。這個題目是告訴你幾點幾分，請你的程式回應時針和分針之間的角度。請注意：所有的角度請回應最小的正角度。例如：9:00是90度，不是 -90度，也不是270度。
:::
```cpp=
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int h, m;
double ah, am, ans; // angle of hour and min
while (scanf("%d:%d", &h, &m) && (h | m)) {
if (h == 12) h = 0;
// h * 5 * 6 -> 時針本身角度
// 30 * m * 1.0 / 60 分針對時針造成的影響
ah = h * 5 * 6 + 30 * m * 1.0 / 60;
// 一個刻度為 6 度
am = m * 6;
ans = ah - am;
while (ans < 0) ans += 360;
if (ans > 180) ans = 360 - ans;
printf("%.3lf\n", ans);
}
return 0;
}
```
### 10409 - [Die Game](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10409.pdf)
:::info
"Life is not easy."，人生往往超出我們的掌握
現在，作為ACM ICPC的參賽者，您可能只是在品嚐生活的痛苦。
但是不用擔心！不要只看人生的黑暗面，也要看光明面。
人生可能是一種令人愉快的機會遊戲，例如擲骰子"Do or die!"。
說不定可以找到通往勝利的途徑！
此問題來自骰子遊戲。"Do you know a die?"
此處的"die"與死亡無關，而是指一般的立方體骰子，每個面代表一到六個不同的數字。
順帶一提，"a die"是一個很少使用的詞。不過，您可能會聽過一個名言："the die is cast"
遊戲開始時，骰子會在平台上靜止不動。
在遊戲中，主持人將骰子向各個方向滾動。
如果您可以預測骰子停止滾動時在頂面上看到的數字，則您將贏得比賽。
現在，要求您編寫一個模擬骰子滾動的程式。
為簡單起見，我們假設骰子既不滑動也不跳躍，而只是在四個方向(東，南，西，北)上滾動。
在每局遊戲開始時，主持人將骰子放在桌子的中央並調整其方向，以便分別在頂面、北面、西面上看到數字1、2、3。
對於其他三個面，我們沒有明確指定任何內容，但會告訴您一條黃金法則：任何一對相對的面的數字總和始終為7。
您的程式應接受一系列指令，指令為東"east"，南"south"，西"west"，北"north"。
例如"north"指令將骰子向下滾動到北，即頂面變為新的北，北變為新的底，依此類推。
其他指令也會根據自己的方向滾動骰子。
執行順序中的指令後，您的程式應計算最終顯示在頂部的數字。
請注意，桌子足夠大，骰子在遊戲中不會掉落或損壞。
:::
:::success
設定六個變數代表骰子的六個面
並且給予每一個面對應的數字
接著 parse test data，收到不同方位指示時就調換這六個變數。
:::
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
int m;
while (cin >> m){
if (m <= 0)
break;
int u = 1, n = 2, w = 3, e = 4, s = 5, o = 6;
for (int i = 0; i < m; i++){
string stg;
int t;
cin >> stg;
switch (stg[0]){
case 'n':
t = u;
u = s;
s = o;
o = n;
n = t;
break;
case 's':
t = u;
u = n;
n = o;
o = s;
s = t;
break;
case 'e':
t = u;
u = w;
w = o;
o = e;
e = t;
break;
case 'w':
t = u;
u = e;
e = o;
o = w;
w = t;
break;
}
}
cout << u << endl;
}
return 0;
}
```
### 00630 - [Anagrams (II)](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/630.pdf)
:::info
二十世紀末期人們最喜歡的遊戲之一是變位字謎。幾乎每家報紙和雜誌都有專門介紹變位字謎的專欄。
對於變位字謎還有專用的雜誌。舉辦了很多比賽，甚至還有了世界錦標賽。
現在有一個富豪也想跟上流行，他僱用你來幫助他，他希望你使用電腦來玩變位字謎，這樣他就能很快填完。
因此您需要寫一個程式，該程式使用給定的詞彙表來搜索給定單詞的變位字謎。
:::
:::success
把字串讀進來以後 sort 再儲存起來
:::
```cpp=
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void) {
int i, t, n, num;
char word[1005][25], temp1[1005][25], test[25], temp2[25];
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; ++i) {
scanf("%s", word[i]);
strcpy(temp1[i], word[i]);
sort(&temp1[i][0], &temp1[i][0] + strlen(temp1[i]));
}
while(scanf("%s", test) && test[0] != 'E') {
printf("Anagrams for: %s\n", test);
strcpy(temp2, test);
sort(&temp2[0], &temp2[0] + strlen(temp2));
for(i = 0, num = 0; i < n; ++i)
if(strcmp(temp2, temp1[i]) == 0)
printf("%3d) %s\n", ++num, word[i]);
if(num == 0) printf("No anagrams for: %s\n", test);
}
if(t) printf("\n");
}
return 0;
}
```
## 2014-12-23 CPE
### 494 - [Kindergarten Counting Game](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/494.pdf)
:::info
算一算每行有幾個字（word）。
Word的定義是連續的字元（letter: A~Z a~z）所組成的字。
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
string input;
while(getline(cin, input)) {
int result = 0;
bool isStarted = false;
for (int i = 0; i < input.length(); i++) {
if ((97<= input[i] && input[i] <= 122) ||
(65<= input[i] && input[i] <= 90)
){
if (isStarted) {
continue;
} else {
isStarted = true;
result++;
continue;
}
}
isStarted = false;
}
cout << result << endl;
}
return 0;
}
```
### 11054 - [Wine trading in Gergovia](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11054.pdf)
:::info
您可能會從漫畫"Asterix and the Chieftain's Shield"中了解到，Gergovia由一條街道組成，每個城市的居民都是葡萄酒推銷員。
您想知道這種經濟如何運作嗎？
每個人都從城市的其他居民那裡購買葡萄酒。每位居民每天都要決定要購買或出售多少酒。
有趣的是，供需始終是相同的，因此每個居民都能得到自己想要的東西。
但是有一個問題，將葡萄酒從一所房子運到另一所房子會導致工作量上升。
由於所有葡萄酒的品質都一樣，因此，Gergovia的居民不在乎與之交易的人，他們只對出售或購買特定數量的葡萄酒感興趣。
他們足夠聰明，可以找到一種交易方式，從而使運輸所需的總工作量最小化。
在這個問題上，您需要重建Gergovia的一天中的交易路線。為簡單起見，我們假設房屋是沿著一條直線建造的，相鄰房屋之間的距離相等
將一瓶葡萄酒從一棟房子運送到相鄰的房子需要一個單位的工作量。
:::
:::success
- Greedy
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main () {
int houseNum;
while (cin >> houseNum) {
int res = 0;
vec.clear();
if (houseNum == 0) break;
for (int i = 0; i < houseNum; i++) {
int input;
cin >> input;
vec.push_back(input);
}
for (int j = 0; j < vec.size(); j++) {
res += abs(vec[j]);
vec[j + 1] = vec[j] + vec[j + 1];
}
cout << res << endl;
}
}
```
### 11005 - [Cheapest Base](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11005.pdf)
:::info
給定0~9+A~Z每個字的價格，並且計算出不同進位下的數字需要多少錢(Ex 假設1=$3，2=$4，3=$5。123=$3+$4+$5=$12)，並找出最少錢的進位。
:::
```cpp=
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int f(int a, int b, int arr[], int &cnt) {
int tmp[40] = {}, i;
cnt = 0;
while(a >= b) {
tmp[cnt++] = a % b;
a /= b;
}
if(a)
tmp[cnt++] = a;
for(i = 0; i < cnt; ++i)
arr[cnt-i-1] = tmp[i];
return 0;
}
int CalCost(int arr[], int cnt, int cost[]) {
int sum = 0;
for(int i = 0; i < cnt; ++i) {
sum += cost[arr[i]];
}
return sum;
}
int main()
{
int a, b, n, num, Min;
int cost[40];
int t, ti = 0;
cin >> t;
while(ti++ < t) {
printf("Case %d:\n", ti);
for(int i = 0; i < 36; ++i)
cin >> cost[i];
cin >> n;
while(n--) {
int arr[40] = {}, cnt = 0;
int price[40] = {};
cin >> num;
Min = 999999999;
for(b = 2; b <= 36; ++b) {
f(num, b, arr, cnt);
price[b] = CalCost(arr, cnt, cost);
if(price[b] < Min)
Min = price[b];
}
printf("Cheapest base(s) for number %d:", num);
for(b = 2; b <= 36; ++b) {
if(price[b] == Min)
printf(" %d", b);
}
printf("\n");
}
if(ti != t)
printf("\n");
}
return 0;
}
```
## 2015-03-24 CPE
### 591 - [Box of Bricks](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/591.pdf)
:::info
搬磚頭，讓每一堆磚頭等高（求這樣最少要移動幾次）
:::
:::success
首先先算出平均高度，接著尋訪每一堆，看長度高於平均高度多少（如果磚頭堆的高度高於平均，代表他要移到別的地方），這樣即可求出最小移動數。
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main () {
int brickNum;
int arr[100] = {0};
int cases = 1;
while (cin >> brickNum) {
memset(arr,0 ,100);
if (brickNum == 0) return 0;
int avg = 0;
for (int i = 0; i < brickNum; i++) {
cin >> arr[i];
avg += arr[i];
}
avg /= brickNum;
int res = 0;
for (int i = 0; i < brickNum; i++) {
if (arr[i] > avg ) {
res = res + (arr[i] - avg);
}
}
cout << "Set #" << cases << endl;
cout << "The minimum number of moves is " << res << "." << endl;
cases++;
}
}
```
### 10922 - [2 the 9s](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10922.pdf)
:::info
計算是不是 9 的倍數，如果是，要算該數的總和是否也為 9 的倍數。
:::
:::success
就...遞迴...對。
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int isNineS(string s) {
long long sum = 0;
for (int n = s.length(); n > 0; n--) {
sum += (s[n - 1] - '0');
}
if (sum == 9) {
return 1;
} else if (sum % 9 == 0) {
return 1 + isNineS(to_string(sum));
} else {
return 0;
}
}
int main() {
string input;
while (cin >> input) {
if (input == to_string(0)) return 0;
int res = isNineS(input);
if (res > 0) {
cout << input << " is a multiple of 9 and has 9-degree " << res << "." << endl;
} else {
cout << input << " is not a multiple of 9." << endl;
}
}
return 0;
}
```
### 409 - [Excuses, Excuses!](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/409.pdf)
:::info
看看哪一個句子裡面涵蓋最多關鍵字，輸出符合條件的句子（們）。
:::
:::success
先把單字做 uppercase 後放到 vector
把句子拆開逐行放到另一個 vector
計算這個句子裡包含幾個關鍵字（同時計算`符合最多關鍵字的數量`），並且把句子與符合數存到 map
迭代 map，找出`符合數`等於`符合最多關鍵字數`的句子
需要注意的是：cin 跟 getline 之間記得用 `cin.ignore()` ＝＝
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <string> dict;
vector <string> proof;
map <string, int> resMap;
int validate() {
int count = 0;
for (string x: proof) {
for (string y: dict) {
if (x.compare(y) == 0) {
count++;
}
}
}
return count;
}
int main() {
int n, m;
int cases = 1;
while (cin >> n >> m) {
dict.clear();
for (int i = 0; i < n; i++) {
string input;
cin >> input;
// to upper case
transform(input.begin(), input.end(), input.begin(), ::toupper);
dict.push_back(input);
}
cin.ignore();
cout << "Excuse Set #" << cases++ << endl;
int maxn = 0;
for (int j = 0; j < m; j++) {
proof.clear();
string pf;
getline(cin, pf);
string originPf = pf.substr(0);
transform(pf.begin(), pf.end(), pf.begin(), ::toupper);
int pos = 0;
for (int x = 0; x < pf.size(); x++) {
if (!isalpha(pf[x])) {
proof.push_back(pf.substr(pos, x - pos));
pos = x + 1;
}
}
proof.push_back(pf.substr(pos));
int temp = validate();
maxn = max(maxn, temp);
resMap.insert(pair<string, int>(originPf, temp));
}
for (auto it: resMap) {
if (it.second == maxn) {
cout << it.first << endl;
}
}
resMap.clear();
}
return 0;
}
```
## 2015-05-26 CPE
### 1585 - [Score](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/1585.pdf)
:::info
有一個問卷的測試結果，例如"OOXXOXXOOO"。
"O"表示問題的正確答案，"X"表示錯誤的答案。
在答案正確時，每個問題的分數均由自己及其前一個連續的"O"來計算。
例如，第10個問題的分數是3，該分數是由其自己及其前兩個連續的"O"獲得的。
因此，"OOXXOXXOOO"的分數是10，是由"1 + 2 + 0 + 0 + 1 + 0 + 0 + 1 + 2 + 3"計算得出。
您需要寫一個計算測試結果分數的程式。
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int getScore(string input) {
int cur = 1;
int res = 0;
for (int i = 0; i < input.size(); i++) {
if (input[i] == *(char*)"O") {
res += cur;
cur += 1;
} else {
cur = 1;
}
}
return res;
}
int main(){
int n;
while (cin >> n) {
for (int i = 0; i < n; i++) {
string answer;
cin >> answer;
cout << getScore(answer) << endl;
}
}
return 0;
}
```
### 10474 - [Where is the Marble?](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10474.pdf)
:::info
Raju和Meena喜歡玩大理石(marble)。他們有很多上寫有數字的大理石。
剛開始，Raju會按照書寫在上面的數字以升序依次放置大理石。
然後，Meena會要求Raju找到指定號碼的第一塊大理石。
如果Raju成功，Raju將獲得一分，如果Raju失敗，Meena將獲得一分。
經過多次的詢問，遊戲結束，獲得最高分的玩家獲勝。
今天，你有機會幫助Raju。但是請不要小看Meena，她寫了一個程式來追蹤你花多少時間才能給出所有答案。
因此，你也必須寫了一個有效率的程式，來確保勝利。
```
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0
```
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main(){
int n = 0;
int q = 0;
int cases = 1;
while (cin >> n >> q){
if (n == 0 && q == 0) {
return 0;
}
vec.clear();
for (int i = 0; i < n; i++) {
int marble = 0;
cin >> marble;
vec.push_back(marble);
}
sort(vec.begin(), vec.end());
cout << "CASE# " << cases++ << ":" << endl;
for (int i = 0; i < q; i++) {
int ask = 0;
cin >> ask;
int j = 1;
bool isFound = false;
for (int x: vec) {
if (x == ask) {
cout << ask << " found at " << j << endl;
isFound = true;
break;
}
j++;
}
if (!isFound) {
cout << ask << " not found" << endl;
}
}
}
return 0;
}
```
### 10908 - [Largest Square](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10908.pdf)
:::info
給定一個字元矩形，您必須找出最大正方形的邊的長度。
在其中正方形內的所有字元皆相同，並且正方形的中心(兩個對角線的交點)位於位置(r, c)。
矩形的高度和寬度分別為M和N。矩形的左上角座標為(0, 0)，右下角座標為(M-1, N-1)。
比方說下面給出的字元矩形。給定中心位置(1, 2)，此最大正方形邊長為3。
abbbaaaaaa
abbbaaaaaa
abbbaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaccaaaaaa
aaccaaaaaa
:::
:::success
一開始給的點會是正方形的中心點，所以邊長一定會是奇數。
也因為這樣，可以從正方形的任一角開始繞，不用害怕正方形邊長是偶數的 corner case。
:::
```cpp=
// https://theriseofdavid.github.io/2021/05/08/UVa/UVa10908/
#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 120;
int t, q, n, m;
int direct[4][2] = {{0,1},{+1,0},{0,-1},{-1,0}}; //依序是左、下、右、上，圍繞一圈的方向
string graph[MAXN]; //儲存地圖
int isValid(int x, int y){ //判斷這個位置是否非法
if(x >= 0 && x < m && y >= 0 && y < n) return 1; //判斷此位置是否超出邊界
return 0;
}
int find_square(int x, int y){//position distance
int d = 1; //繞圓心一圈的邊長
int root_char = graph[x][y]; //圓心的字元
int flag = 1; //判斷這圈是否可以成功繞圓心一圈，1 表示可以、0 表示不行
while(flag){
d += 2; //邊長增加兩個單位
int nowX = x-(d/2), nowY = y-(d/2); //找出此圈的左上角點
for(int i = 0; i < 4; i++){ //四個方向，共繞行一圈
for(int j = 0; j < d-1; j++){ //每一個方向走 d 步
nowX += direct[i][0]; //計算當前位置
nowY += direct[i][1];
//cout << "nowX nowY " << nowX << ' ' << nowY << ' ' << isValid(nowX,nowY) << '\n';
if(!isValid(nowX,nowY) || graph[nowX][nowY] != root_char){ //如果是非法位置 || 現在的 now 字元與 root_char 不同
flag = 0; //表示無法通行
break;
}
//cout << "graph char " << graph[nowX][nowY] << '\n';
}
if(flag == 0) break; //如果無法通行則離開
}
}
return d-2; //由於是 d 圈沒辦法繞完，因此 d-2 的距離那圈一定可以繞完。
}
int main()
{
#ifdef LOCAL
freopen("in1.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif // LOCAL
cin >> t;
while(t--){
cin >> m >> n >> q;
for(int i = 0; i < m; i++) cin >> graph[i]; //輸入地圖
cout << m << ' ' << n << ' ' << q << '\n'; //輸出地圖資訊
int x, y;
while(q--){ //讀入資訊
cin >> x >> y; //給予圓心點 x,y
cout << find_square(x, y) << '\n'; //尋找圓心最大邊長
}
}
return 0;
}
```
## 2015-10-06 CPE
### 455 - [Periodic Strings](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/455.pdf)
:::info
A character string is said to have period k if it can be formed by concatenating one or more repetitions
of another string of length k. For example, the string ”abcabcabcabc” has period 3, since it is formed
by 4 repetitions of the string ”abc”. It also has periods 6 (two repetitions of ”abcabc”) and 12 (one
repetition of ”abcabcabcabc”).
Write a program to read a character string and determine its smallest period.
:::
```cpp=
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char str[85];
int solve() {
int i, j, len = strlen(str);
for(i = 1; i <= len; i++) { // length
if(len % i != 0) continue;
for(j = 0; j < len; j++)
if(str[j] != str[j % i])
break;
if(j == len)
return i;
}
return -1;
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%s", str);
printf("%d\n", solve());
if(t != 0)
putchar('\n');
}
return 0;
}
```
### 490 - [Rotating Sentences](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/490.pdf)
:::info
在這個問題中你必須將數列文字往順時針方向旋轉90度。也就是說將原本由左到右，由上到下的句子輸出成由上到下，由右到左。
:::
```cpp=
#include <iostream>
using namespace std;
string s[105];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int col = 0, row = 0;
while (getline(cin, s[col])){
row = max(row, (int)s[col].size());
col++;
}
for (int i = 0; i < row; i++){
for (int j = col-1; j >= 0; j--){
if (i >= s[j].size()) cout << " ";
else cout << s[j][i];
}
cout << "\n";
}
return 0;
}
```
### 11389 - [The Bus Driver Problem](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11389.pdf)
:::info
在一個城市裡，有n個巴士司機。也有n條早晨巴士路線和n條傍晚巴士路線，它們的長度各不相同。
每個駕駛員將會被分配一條早晨路線和一條傍晚路線。
對於任何駕駛員，如果一天的總路線長度超過d，則必須在d小時後以每小時r元支付加班費。
您的任務是為每個巴士司機分配一條早上路線和一條傍晚路線，以使支付的總加班費最小。
```
每組測資的第一行有三個整數n、d、r。
n、d、r如題目所述。
1 ≤ n ≤ 100，1 ≤ d ≤ 10000，1 ≤ r ≤ 5。
如果n = d = r = 0代表輸入結束。
第二行有n個以空格分隔的整數，它們是以公尺為單位給出的早晨路徑的長度。
第三行有n個以空格分隔的整數，它們是以公尺為單位給出的傍晚路徑的長度。
長度皆是小於或等於10000的正整數。
```
:::
:::success
把上午跟下午的輸入放到個別的 vector
然後對兩個 vector 進行排序（一個由小到大，一個由大到小）
然後尋訪這兩個 vector 算出超出多少長度
:::
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> vec_m;
vector<int> vec_a;
int main () {
int n, d, r = 0;
while (cin >> n >> d >> r) {
if (n + d + r == 0) {
return 0;
}
vec_m.clear();
vec_a.clear();
for (int i = 0; i < n; i++) {
int length = 0;
cin >> length;
vec_m.push_back(length);
}
for (int i = 0; i < n; i++) {
int length = 0;
cin >> length;
vec_a.push_back(length);
}
sort(vec_m.begin(), vec_m.end());
sort(vec_a.begin(), vec_a.end());
ll res = 0;
for (int i = 0; i < n; i++) {
int exceedL = 0;
if (vec_m[i] + vec_a[n-i-1] > d) {
exceedL = (vec_m[i] + vec_a[n-i-1] - d);
}
res += (ll)exceedL;
}
cout << (ll)(res * (ll)r) << endl;
}
return 0;
}
```
## 2015-12-22 CPE
> 用了 75 分鐘
### 11332 - [Summing Digits](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11332.pdf)
:::info
:::
:::success
寫一個函式將輸入（字串）的每一位相加，並且遞迴的呼叫，直到輸入（字串）的長度為一。
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int f(string str) {
if (str.size() == 1) {
return stoi(str);
}
int s = 0;
for (int i = 0; i < str.size(); i++) {
s += (str[i] - '0');
}
return f(to_string(s));
}
int main() {
int input;
while (cin >> input) {
if (input == 0) {
return 0;
}
int res = f(to_string(input));
cout << res << endl;
}
return 0;
}
```
### 10487 - [Closest Sums](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10487.pdf)
:::info
:::
:::success
先把輸入丟到 vector1
兩兩相加丟到 vector2
sort vector2
看看 target 最接近哪個數（可用尋訪、二分搜）
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector <int> vec1;
vector <int> vec2;
int main () {
int n, m;
int cases = 1;
while (cin >> n) {
if (n == 0) return 0;
vec1.clear();
vec2.clear();
for (int i = 0; i < n; i++) {
int in;
cin >> in;
vec1.push_back(in);
}
for (int i = 0; i < vec1.size(); i++) {
for (int j = i + 1; j < vec1.size(); j++) {
vec2.push_back(vec1[i]+vec1[j]);
}
}
sort(vec2.begin(), vec2.end());
cin >> m;
cout << "Case " << cases++ << ":" << endl;
for (int i = 0; i < m; i++) {
int diff = INT_MAX;
int res = 0;
int in;
cin >> in;
for (int j = 0; j < vec2.size(); j++) {
int cmp = abs(vec2[j] - in);
if (diff > cmp) {
diff = cmp;
res = vec2[j];
}
}
cout << "Closest sum to " << in << " is " << res << "." << endl;
}
}
}
```
### 706 - [LC-Display](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/706.pdf)
:::info
:::
:::success
預先訂一一個 2 dimenstion array：
```cpp=
int lcd[10][7] = {
{1, 1, 1, 1, 1, 1, 0}, // 0
{0, 1, 1, 0, 0, 0, 0}, // 1
{1, 1, 0, 1, 1, 0, 1}, // 2
{1, 1, 1, 1, 0, 0, 1}, // 3
{0, 1, 1, 0, 0, 1, 1}, // 4
{1, 0, 1, 1, 0, 1, 1}, // 5
{1, 0, 1, 1, 1, 1, 1}, // 6
{1, 1, 1, 0, 0, 0, 0}, // 7
{1, 1, 1, 1, 1, 1, 1}, // 8
{1, 1, 1, 1, 0, 1, 1} // 9
}
```
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int lcd[10][7] = {
{1, 1, 1, 1, 1, 1, 0}, // 0
{0, 1, 1, 0, 0, 0, 0}, // 1
{1, 1, 0, 1, 1, 0, 1}, // 2
{1, 1, 1, 1, 0, 0, 1}, // 3
{0, 1, 1, 0, 0, 1, 1}, // 4
{1, 0, 1, 1, 0, 1, 1}, // 5
{1, 0, 1, 1, 1, 1, 1}, // 6
{1, 1, 1, 0, 0, 0, 0}, // 7
{1, 1, 1, 1, 1, 1, 1}, // 8
{1, 1, 1, 1, 0, 1, 1} // 9
};
int main() {
int s;
string input;
while (cin >> s >> input) {
if (s + stoi(input) == 0) return 0;
// first line
for (int i = 0; i < input.size(); i++) {
if (i) cout << " ";
cout << " ";
for (int j = 0; j < s; j++) {
if (lcd[(int)(input[i] - '0')][0]) {
cout << "-";
} else {
cout << " ";
}
}
cout << " ";
}
cout << endl;
// second line
for (int i = 0; i < s; i++) {
for (int j = 0; j < input.size(); j++) {
if (j) cout << " ";
if (lcd[(int)(input[j] - '0')][5]) {
cout << "|";
} else {
cout << " ";
}
for (int k = 0; k < s; k++) {
cout << " ";
}
if (lcd[(int)(input[j] - '0')][1]) {
cout << "|";
} else {
cout << " ";
}
}
cout << endl;
}
// 3rd line
for (int i = 0; i < input.size(); i++) {
if (i) cout << " ";
cout << " ";
for (int j = 0; j < s; j++) {
if (lcd[(int)(input[i] - '0')][6]) {
cout << "-";
} else {
cout << " ";
}
}
cout << " ";
}
cout << endl;
// 4th line
for (int i = 0; i < s; i++) {
for (int j = 0; j < input.size(); j++) {
if (j) cout << " ";
if (lcd[(int)(input[j] - '0')][4]) {
cout << "|";
} else {
cout << " ";
}
for (int k = 0; k < s; k++) {
cout << " ";
}
if (lcd[(int)(input[j] - '0')][2]) {
cout << "|";
} else {
cout << " ";
}
}
cout << endl;
}
// 5th line
for (int i = 0; i < input.size(); i++) {
if (i) cout << " ";
cout << " ";
for (int j = 0; j < s; j++) {
if (lcd[(int)(input[i] - '0')][3]) {
cout << "-";
} else {
cout << " ";
}
}
cout << " ";
}
cout << endl;
}
return 0;
}
```
## 2016-03-22 CPE
### 11764 - [Jumping Mario](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11764.pdf)
:::info
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main() {
int cases = 0;
while (cin >> cases) {
for (int i = 0; i < cases; i++) {
vec.clear();
int walls = 0;
cin >> walls;
for (int j = 0; j < walls; j++) {
int input;
cin >> input;
vec.push_back(input);
}
cout << "Case " << i+1 << ": ";
if (walls > 0) {
int h = 0;
int s = 0;
int prev = vec[0];
for (int k = 1; k < walls; k++) {
if (vec[k] > prev) {
h++;
}
if (vec[k] < prev) {
s++;
}
prev = vec[k];
}
cout << h << " " << s << endl;
} else {
cout << "0 0" << endl;
}
}
}
return 0;
}
```
### 10082 - [WERTYU](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10082.pdf)
:::info
:::
```cpp=
//uva10082
#include <cstdio>
int main() {
const char str[]={"`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"};
char c;
int i;
while (( c = getchar()) != EOF) {
if (c == ' ' || c == '\n')
putchar(c);
else {
for (i = 0; str[i] != c; i++);
putchar(str[i - 1]);
}
}
return 0;
}
```
### 10062 - Tell me the frequencies!
:::info
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int res[256] = {0};
int main(){
char str[256];
bool isFirst = true;
while(fgets(str, 100, stdin) != NULL) {
for (int i = 0; i < 256; i++) {
res[i] = 0;
}
if (isFirst) {
isFirst = false;
} else {
cout << endl;
}
for (int i = 0; i < strlen(str); i++) {
res[(int)str[i]]++;
}
for (int k = 1; k < strlen(str); k++) {
for (int i = 47; i < 256; i++) {
if (res[i] == k) {
cout << i << " " << res[i] << endl;
}
}
}
}
return 0;
}
```
## 2016-05-24 CPE
### 11942 - [Lumberjack Sequencing](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11942.pdf)
:::info
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int cases;
int arr[10] = {0};
while (cin >> cases) {
cout << "Lumberjacks:" << endl;
for (int n = 0; n < cases; n++) {
for (int i = 0; i < 10; i++) {
cin >> arr[i];
}
bool isUp = true;
bool isOrdered = true;
if (arr[1] - arr[0] < 0) {
isUp = false;
}
for (int i = 1; i < 10; i++) {
if (isUp) {
if (arr[i] - arr[i-1] < 0) {
isOrdered = false;
break;
}
} else {
if (arr[i] - arr[i-1] > 0) {
isOrdered = false;
break;
}
}
}
if (isOrdered) {
cout << "Ordered" << endl;
} else {
cout << "Unordered" << endl;
}
}
}
return 0;
}
```
### 00499 - [What's The Frequency, Kenneth?](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/499.pdf)
:::info
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
string str;
char count[256] = {0};
while (getline(cin, str)) {
memset(count, 0, 256);
for (int i = 0; i < str.size(); i++) {
if(isalpha((char)str[i])) {
count[str[i]]++;
}
}
bool isHit = false;
int hitNumber = 0;
for (int i = str.size(); i > 0; i--) {
for (int j = 65; j < 123; j++) {
if (count[j] == i) {
cout << (char)j;
isHit = true;
hitNumber = i;
}
}
if (isHit) {
break;
}
}
cout << " " << hitNumber << endl;
}
return 0;
}
```
### 948 - [Fibonaccimal Base](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/948.pdf)
:::info
:::
```cpp=
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
int dp[50];
int main()
{
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < 40; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int n = 0;
while (cin >> n) {
for (int i = 0; i < n; i++) {
int data = 0;
cin >> data;
bool isFirst = true;
cout << data << " = ";
for (int i = 39; i >= 2; i--) {
if (data >= dp[i]) {
cout << "1";
isFirst = false;
data -= dp[i];
} else {
if (!isFirst) {
cout << "0";
}
}
}
cout << " (fib)" << endl;
}
}
return 0;
}
```
## 2016-10-04 CPE
### 11192 - [Group Reverse](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11192.pdf)
:::info
:::
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
string str;
int groupN;
while (cin >> groupN >> str) {
int groupLength = str.size() / groupN;
for (int i = 0; i < groupN; i++) {
string copyStr = str.substr(i*groupLength, groupLength);
for (int j = 0; j < groupLength; j++) {
str[i*groupLength + j] = copyStr[groupLength - (j + 1)];
}
}
cout << str << endl;
}
return 0;
}
```
### 1587 - [BOX](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/1587.pdf)
:::info
```
Sample Output
POSSIBLE
IMPOSSIBLE
```
:::
```cpp=
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
map<int, int> sidemap;
map<pair<int, int>, int> surfmap;
int main()
{
int n, m = 0;
int i = 0;
while (cin >> n >> m) {
sidemap[n]++;
sidemap[m]++;
surfmap[pair<int, int>(max(m,n), min(m,n))]++;
i++;
bool isPossible = true;
if (i == 6) {
for (auto &it: sidemap) {
if (it.second % 4 != 0) {
isPossible = false;
break;
}
}
for (auto &it: surfmap) {
if (it.second % 2 != 0) {
isPossible = false;
break;
}
}
i = 0;
surfmap.clear();
sidemap.clear();
if (isPossible) {
cout << "POSSIBLE" << endl;
} else {
cout << "IMPOSSIBLE" << endl;
}
}
}
return 0;
}
```
### [10415 - Eb Alto Saxophone Player](https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10415.pdf)
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(){
int n ;
scanf("%d", &n) ;
char note[300] = {0} ;
getchar();
while(n--){
int i, j, finger[11] = {0}, ans[11] = {0} ;
char note[300] = {0} ;
gets(note) ;
for(i = 0 ; i < strlen(note) ; i++){
int temp[11] = {0} ;
if(note[i] == 'c')
temp[2] = temp[3] = temp[4] = temp[7] = temp[8] = temp[9] = temp[10] = 1 ;
if(note[i] == 'd')
temp[2] = temp[3] = temp[4] = temp[7] = temp[8] = temp[9] = 1 ;
if(note[i] == 'e')
temp[2] = temp[3] = temp[4] = temp[7] = temp[8] = 1 ;
if(note[i] == 'f')
temp[2] = temp[3] = temp[4] = temp[7] = 1 ;
if(note[i] == 'g')
temp[2] = temp[3] = temp[4] = 1 ;
if(note[i] == 'a')
temp[2] = temp[3] = 1 ;
if(note[i] == 'b')
temp[2] = 1 ;
if(note[i] == 'C')
temp[3] = 1 ;
if(note[i] == 'D')
temp[1] = temp[2] = temp[3] = temp[4] = temp[7] = temp[8] = temp[9] = 1 ;
if(note[i] == 'E')
temp[1] = temp[2] = temp[3] = temp[4] = temp[7] = temp[8] = 1 ;
if(note[i] == 'F')
temp[1] = temp[2] = temp[3] = temp[4] = temp[7] = 1 ;
if(note[i] == 'G')
temp[1] = temp[2] = temp[3] = temp[4] = 1 ;
if(note[i] == 'A')
temp[1] = temp[2] = temp[3] = 1 ;
if(note[i] == 'B')
temp[1] = temp[2] = 1 ;
for(j = 1 ; j <= 10 ; j++){
if((temp[j] == 1) && (finger[j] != 1))
ans[j] ++ ;
finger[j] = temp[j] ;
}
}
for(i = 1 ; i <= 9 ; i++)
printf("%d ", ans[i]) ;
printf("%d\n", ans[10]) ;
}
return 0 ;
}
```
Sign in with Wallet
Connect another wallet