# [zerojudge](https://zerojudge.tw/)
## a
### a001
```cpp=
/*
* a001. 哈囉
* C++
* AC (3ms, 320KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
cout << "hello, " << s << endl;
return 0;
}
```
### a002
```cpp=
/*
* a002. 簡易加法
* C++
* AC (2ms, 332KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
cout << a+b << endl;
return 0;
}
```
### a003
```cpp=
/*
* a003. 兩光法師占卜術
* C++
* AC (3ms, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int m,d;
cin >> m >> d;
//
int s=(m*2+d)%3;
//
if(s==0){
cout << "普通" << endl;
}else if(s==1){
cout << "吉" << endl;
}else if(s==2){
cout << "大吉" << endl;
}
//
return 0;
}
```
### a004
```cpp=
/*
* a004. 文文的求婚
* C++
* AC (8ms, 312KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
if( (n%4==0 && n%100!=0) || n%400==0){
cout << "閏年" << endl;
}else{
cout << "平年" << endl;
}
}
return 0;
}
```
### a005
```cpp=
/*
* a005. Eva 的回家作業
* C++
* AC (2ms, 292KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int a,b,c,d;
int e=0;
cin >> a >> b >> c >> d;
if( (b/a)==(c/b) && (c/b)==(d/c) ){
e=d*(b/a);
}else if( (b-a)==(c-b) && (c-b)==(d-c) ){
e=d+(b-a);
}
cout << a << " " << b << " " << c << " " << d << " " << e << endl;
}
return 0;
}
```
### a006
```cpp=
/*
* a006. 一元二次方程式
* C++
* AC (2ms, 332KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b,c;
cin >> a >> b >> c;
if(b*b-4*a*c <0){
cout << "No real root" << endl;
}else{
int x1= (-1*b+sqrt(b*b-4*a*c) ) / (2*a);
int x2= (-1*b-sqrt(b*b-4*a*c) ) / (2*a);
//
if(x1!=x2){
cout << "Two different roots x1=" << x1 << " , x2=" << x2 << endl;
}else{
cout << "Two same roots x=" << x1 << endl;
}
}
return 0;
}
```
### a009
```cpp=
/*
* a009. 解碼器
* C++
* AC (7ms, 324KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int k=-7; //從輸入輸出 J->C 知道差-7
string s;
cin >> s;
for(int i=0;i<s.size();i++){
char c = s[i]+k;
cout << c;
}
cout << endl;
}
```
### a011
#### C++
```cpp=
/*
* a011. 00494 - Kindergarten Counting Game
* C++
* AC (2ms, 312KB)
*/
#include<bits/stdc++.h>
using namespace std;
bool f(char c){
if( c<='z' && c>='a' || c<='Z' && c>='A' ){
return 1;
}else{
return 0;
}
}
int main(){
string s;
while(getline(cin,s)){
int sum=0;
int i=0;
bool isEn = false;
for(;i<s.size();i++){
if(isEn){
if(f(s[i])==0){
isEn=0;
}
}else{
if(f(s[i])==1){
sum+=1;
isEn=1;
}
}
}
cout << sum << endl;
}
}
```
### a054
```cpp=
/*
* a054. 電話客服中心
* C++
* AC (2ms, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
int f(int a){
if (a == 0) {
return 10; // 台北市 A
} else if (a == 1) {
return 11; // 台中市 B
} else if (a == 2) {
return 12; // 基隆市 C
} else if (a == 3) {
return 13; // 台南市 D
} else if (a == 4) {
return 14; // 高雄市 E
} else if (a == 5) {
return 15; // 台北縣 F
} else if (a == 6) {
return 16; // 宜蘭縣 G
} else if (a == 7) {
return 17; // 桃園縣 H
} else if (a == 8) {
return 34; // 嘉義市 I
} else if (a == 9) {
return 18; // 新竹縣 J
} else if (a == 10) {
return 19; // 苗栗縣 K
} else if (a == 11) {
return 20; // 台中縣 L
} else if (a == 12) {
return 21; // 南投縣 M
} else if (a == 13) {
return 22; // 彰化縣 N
} else if (a == 14) {
return 35; // 新竹市 O
} else if (a == 15) {
return 23; // 雲林縣 P
} else if (a == 16) {
return 24; // 嘉義縣 Q
} else if (a == 17) {
return 25; // 台南縣 R
} else if (a == 18) {
return 26; // 高雄縣 S
} else if (a == 19) {
return 27; // 屏東縣 T
} else if (a == 20) {
return 28; // 花蓮縣 U
} else if (a == 21) {
return 29; // 台東縣 V
} else if (a == 22) {
return 32; // 金門縣 W
} else if (a == 23) {
return 30; // 澎湖縣 X
} else if (a == 24) {
return 31; // 陽明山 Y
} else if (a == 25) {
return 33; // 連江縣 Z
}
}
char g(char a){
return a+'A';
}
int main(){
int n;
cin >> n;
int m=0;
int c=n%10;
n/=10;
//
for(int i=1;i<=8;i++){
m += (n%10)*i;
n /= 10;
}
//
for(int i=0;i<=25;i++){
int x = (f(i)/10) + ((f(i)%10)*9);
int key = (10-((m+x)%10));
if(key>9){ // 10 算 0 有幾題陷阱
key=0;
}
if( key == c){
cout << g(i);
}
}
cout << endl;
}
```
### a225
```cpp=
/*
* a225. 明明愛排列
* C++
* AC (26ms, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
//
for(int i=0;i<n;i++){
for(int j=0;j<n-1;j++){
if(a[j]%10 > a[j+1]%10){
int temp = a[j];
a[j]=a[j+1];
a[j+1]=temp;
}else if(a[j]%10 == a[j+1]%10){
if(a[j]<a[j+1]){
int temp = a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
//
for(int i=0;i<n;i++){
cout << a[i] << " ";
}
cout << endl;
}
}
```
### a410
```cpp=
/*
* a410. 解方程
* C++
* AC (2ms, 328KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
float a,b,c,d,e,f;
cin >> a >> b >> c >> d >> e >> f;
//
if(a*e==d*b){
if(a*f==c*d){
cout << "Too many\n";
}
else{
cout << "No answer\n";
}
}
else{
float x=(c*e-b*f)/(a*e-b*d);
float y=(c*d-a*f)/(b*d-a*e);
//
cout << "x=" << fixed << setprecision(2) << x << endl;
cout << "y=" << fixed << setprecision(2) << y << endl;
}
}
```
### a414
```cpp=
/*
* a414. 位元運算之進位篇
* C++
* AC (0.9s, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
fastio;
int n;
while(cin >> n){
if(n==0){
break;
}
//
int cnt=0;
while(n){
if(n%2==1){
cnt++;
}else{
break;
}
n/=2;
}
cout << cnt << endl;
}
}
```
## b
### b294
```cpp=
/*
* b294. 經濟大恐荒
* C++
* AC (2ms, 316KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int sum=0;
for(int i=1;i<=n;i++){
int x;
cin >> x;
sum += x*i;
}
cout << sum << endl;
return 0;
}
```
### b428
```cpp=
/*
* b428. 凱薩加密
* C++
* AC (15ms, 328KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
bool isP1 = true;
string s;
char p1,p2;
while(cin >> s){
if(isP1){
p1 = s[0];
}else{
p2 = s[0];
int password = p2-p1;
if(password<0){
password+=26;
}
cout << password << endl;
}
isP1 = !isP1;
}
return 0;
}
```
### b964
```cpp=
/*
* b964. 1. 成績指標
* C++
* AC (2ms, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int min=-111;
int max=999;
int x[n];
//
for(int i=0;i<n;i++){
int a;
cin >> a;
x[i]=a;
if(a<60 && min<a){
min=a;
}
if(a>=60 && a<max){
max=a;
}
}
////
sort(x,x+n);
for(int i=0;i<n;i++){
cout << x[i] << " ";
}
cout << endl;
//
if(min==-111){
cout << "best case" << endl;
}else{
cout << min << endl;
}
//
if(max==999){
cout << "worst case" << endl;
}else{
cout << max << endl;
}
//
return 0;
}
```
### b965
```cpp=
/*
* b965. 2. 矩陣轉換
* C++
* AC (2ms, 336KB)
*/
#include <bits/stdc++.h>
using namespace std;
int R,C,M;
int main(){
cin >> R >> C >> M;
int a[max(R,C)][max(R,C)];
int b[max(R,C)][max(R,C)];
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cin >> a[i][j];
}
}
//
int x[M];
for(int i=0;i<M;i++){ //動作
cin >> x[i];
}
for(int i=0;i<M;i++){ // M-i-1 反著讀
if(x[M-i-1]==0){ //旋轉
int temp=R;
R=C;
C=temp;
//
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
b[i][j]=a[j][R-i-1];
}
}
}
if(x[M-i-1]==1){ //翻轉
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
b[i][j]=a[R-i-1][j];
}
}
}
//
for(int i=0;i<R;i++){ //複製
for(int j=0;j<C;j++){
a[i][j]=b[i][j];
}
}
}
//輸出
cout << R << " " << C << endl;
for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cout << a[i][j];
if(j!=C-1){
cout << " ";
}
}
cout << endl;
}
}
```
### b966
```cpp=
/*
* b966. 3. 線段覆蓋長度
* C++
* AC (27ms, 1.3MB)
*/
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define M 9999999
#define m -9999999
struct LINE{
int L;
int R;
};
int main(){
int n;
cin >> n;
int mL=M;
int mR=m;
LINE line[n];
//
for(int i=0;i<n;i++){
cin >> line[i].L >> line[i].R;
if(line[i].L<mL){
mL=line[i].L;
}
if(line[i].R>mR){
mR=line[i].R;
}
}
//
bool line2[mR-mL] = { 0 };
for(int i=0;i<n;i++){
for(int j=line[i].L-mL;j<=line[i].R-mL-1;j++){
line2[j]+=1;
}
}
//
int sum=0;
for(int i=0;i<mR-mL;i++){
if(line2[i]){
sum+=1;
}
}
cout << sum << endl;
}
```
### b967
```cpp=
/*
* b967. 4. 血緣關係
* C++
* AC (0.2s, 10.9MB)
*/
#include <bits/stdc++.h>
using namespace std;
pair<int, int> bfs(const vector<vector<int>>& g, int s) {
queue<int> q;
unordered_map<int, int> levels;
q.push(s);
levels[s] = 0;
//
while (!q.empty()) {
int n = q.front();
q.pop();
int l = levels[n];
for(int i=0;i<g[n].size();i++) {
int x = g[n][i];
if (levels.find(x)==levels.end()) {
levels[x] = l+1;
q.push(x);
}
}
}
//
int ml = -1;
int mn = -1;
for (const auto& pair : levels) {
if (pair.second > ml) {
ml = pair.second;
mn = pair.first;
}
}
return {mn,ml};
}
int main() {
int n;
cin >> n;
vector<vector<int>> g(n);
//無向圖
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cout << bfs(g, bfs(g, 0).first).second << endl; //用最遠的點 bfs 來求最遠的距離
return 0;
}
```
## c
### c290
```cpp=
/*
* c290. APCS 2017-0304-1秘密差
* C++
* AC (2ms, 336KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
bool isOdd = true;
int ans=0;
cin >> s;
for(int i=s.length()-1;i>=0;i--){
if(isOdd){
ans += s[i] - '0';
}else{
ans -= s[i] - '0';
}
isOdd = !isOdd;
}
cout << abs(ans) << endl;
return 0;
}
```
### c291
```cpp=
/*
* c291. APCS 2017-0304-2小群體
* C++
* AC (37ms, 552KB)
*/
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio; icn.tie(0);
using namespace std;
int main(){
int n;
cin >> n;
int x[n];
bool isRun[n] = {0};
for(int i=0;i<n;i++){
cin >> x[i];
}
//
int cnt=0;
for(int i=0;i<n;i++){
int start=i;
int a=x[i];
if(isRun[i]==true){
continue;
}
while(a!=start){
isRun[a]=true;
a=x[a];
}
cnt++;
}
//
cout << cnt << endl;
}
```
### c292
```cpp=
/*
* c292. APCS2017-0304-3數字龍捲風
* C++
* AC (4ms, 336KB)
*/
#include <bits/stdc++.h>
using namespace std;
int N=0;
int a=0;
int x=0,y=0;
int step=0;
int sum=0;
void move(){
if(a>=4){
a=0;
}
//
if(a==0){
x-=1;
}
if(a==1){
y-=1;
}
if(a==2){
x+=1;
}
if(a==3){
y+=1;
}
sum++;
}
int main(){
cin >> N;
cin >> a;
int map[N+1][N+1];
//
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin >> map[j][i]; // [x]右[y]下
}
}
//
x=N/2+1;
y=N/2+1;
step=1;
//
sum=1;
cout << map[x][y];
while(1){
for(int j=0;j<2;j++){
for(int i=0;i<step;i++){
move();
cout << map[x][y];
if(sum==N*N){
break;
}
}
a++;
if(sum==N*N){
break;
}
}
step+=1;
if(sum==N*N){
break;
}
}
cout << endl;
return 0;
/*假設:
* 左一格上一格 接著
* 右兩格下兩格 ...
* /
}
```
### c294
```cpp=
/*
* c294. APCS-2016-1029-1三角形辨別
* C++
* AC (2ms, 336KB)
*/
#include<bits/stdc++.h>
using namespace std;
string triangle(int a,int b,int c){
if(a+b<=c){
return "No";
}else if(a*a+b*b<c*c){
return "Obtuse";
}else if(a*a+b*b==c*c){
return "Right";
}else if(a*a+b*b>c*c){
return "Acute";
}
return "";
}
int main(){
int t[3];
for(int i=0;i<3;i++){
cin >> t[i];
}
sort(t,t+3);
for(int i=0;i<3;i++){
cout << t[i] << " ";
}
cout << endl;
cout << triangle(t[0],t[1],t[2]) << endl;
return 0;
}
```
### c295
```cpp=
/*
* c295. APCS-2016-1029-2最大和
* C++
* AC (2ms, 324KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
int a[m];
vector<int>x;
int sum=0;
while(n--){
for(int i=0;i<m;i++){
cin >> a[i];
}
sort(a,a+m);
sum+=a[m-1];
x.push_back(a[m-1]);
}
cout << sum << endl;
bool key=true;
for(int i=0;i<x.size();i++){
if(sum%x[i]==0){
if(key){
cout << x[i];
}else{
cout << " " << x[i];
}
key=false;
}
}
if(key){
cout << -1 << endl;
}else{
cout << endl;
}
return 0;
}
```
### c461
```cpp=
/*
* c461. apcs 邏輯運算子 (Logic Operators)
* C++
* AC (2ms, 336KB)
*/
#include <bits/stdc++.h>
using namespace std;
int f_and(int a,int b){
if(a!=0 && b!=0)return 1;
return 0;
}
int f_or(int a,int b){
if(a==0 && b==0)return 0;
return 1;
}
int f_xor(int a,int b){
int sum = 0;
if(a==0 && b!=0)return 1;
if(a!=0 && b==0)return 1;
return 0;
}
int main(){
int a,b,y;
int sum=0;
if(a>=1){
a=1;
}
if(b>=1){
b=1;
}
cin >> a >> b >> y;
if(f_and(a,b)==y){
sum++;
cout << "AND" << endl;
}
if(f_or(a,b)==y){
sum++;
cout << "OR" << endl;
}
if(f_xor(a,b)==y){
sum++;
cout << "XOR" << endl;
}
if(sum==0){
cout << "IMPOSSIBLE" << endl;
}
return 0;
}
```
```cpp=
/*
* c462. apcs 交錯字串 (Alternating Strings)
* C++
* AC (4ms, 368KB)
*/
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
bool isSmall(char c) {
return (c >= 'a' && c <= 'z');
}
int main() {
int k;
cin >> k;
string s;
cin >> s;
int maxLen = 0;
int i = 0;
//
for (int start = 0; start < s.size(); ++start) {
if(start>s.size()-maxLen){ //不可能超過了
break;
}
//
int count = 0;
bool isExpected = isSmall(s[start]); //目前大小寫
//
for (i = start; i < s.size(); ++i) {
if (isSmall(s[i]) != isExpected) {
break;
}
count++;
//
if (count % k == 0) { //第k個 轉換大小寫
//cout << start << ":" << i << endl;
if(count>maxLen){ //刷新最大值
maxLen=count;
}
isExpected = !isExpected;
}
}
//
if(count%k==0){
//cout << start << ":" << i-1 << endl;
if(count>maxLen){ //刷新最大值
maxLen=count;
}
}
//
}
//
cout << maxLen << endl;
return 0;
}
```
### c760
```cpp=
/*
* c760. 蝸牛老師的點名單 (懶憜篇)
* C++
* AC (2ms, 320KB)
*/
#include <bits/stdc++.h>
using namespace std;
char big(char c){
if(c=='a')return 'A';
if(c=='b')return 'B';
if(c=='c')return 'C';
if(c=='d')return 'D';
if(c=='e')return 'E';
if(c=='f')return 'F';
if(c=='g')return 'G';
if(c=='h')return 'H';
if(c=='i')return 'I';
if(c=='j')return 'J';
if(c=='k')return 'K';
if(c=='l')return 'L';
if(c=='m')return 'M';
if(c=='n')return 'N';
if(c=='o')return 'O';
if(c=='p')return 'P';
if(c=='q')return 'Q';
if(c=='r')return 'R';
if(c=='s')return 'S';
if(c=='t')return 'T';
if(c=='u')return 'U';
if(c=='v')return 'V';
if(c=='w')return 'W';
if(c=='x')return 'X';
if(c=='y')return 'Y';
if(c=='z')return 'Z';
return 0;
}
int main(){
string s="";
while(cin >> s){
s[0] = big(s[0]);
cout << s << endl;
}
return 0;
}
```
## d
### d010
```cpp=
/*
* d010. 盈數、虧數和完全數
* C++
* AC (4ms, 324KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
while(cin >> N){
int l=2;
int r=N;
int S=1;
while(1){
if(l+1>=r)break;
if(N%l==0){
r = N/l;
S+=l+r;
if(l==r){
S-=l;
}
}
l+=1;
}
if(S>N){
cout << "盈數" << endl;
}else if(S==N){
cout << "完全數" << endl;
}else if(S<N){
cout << "虧數" << endl;
}
}
return 0;
}
```
### d235
```cpp=
/*
* d235. 10929 - You can say 11
* C++
* AC (6ms, 324KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
string s;
while(cin >> s){
if(s=="0"){
break;
}
//
bool isOdd=true;
int sum=0;
int i=0;
while(s[i]!='\0'){
if(isOdd){
sum+=s[i]-'0';
}else{
sum-=s[i]-'0';
}
i++;
isOdd=!isOdd;
}
if(sum<0){
sum*=-1;
}
if(sum%11==0){
cout << s << " is a multiple of 11." << endl;
}else{
cout << s << " is not a multiple of 11." << endl;
}
}
return 0;
}
```
### d275
```cpp=
/*
* d275. 11586 - Train Tracks
* C++
* AC (2ms, 324KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
getline(cin, s); // 輸入整行
while(n--){
getline(cin, s);
stringstream ss(s);
//
vector<string>word;
while(ss>>s){
word.push_back(s);
}
bool isLoop = true;
if(word.size()<=1){ //軌道至少兩個
isLoop=false;
}
else if(word[0][0]==word[word.size()-1][1]){ //頭尾相鄰部分相同
isLoop=false;
}
else{
//軌道相鄰部分相同
for(int i=1; i < word.size();i+=1) {
if (word[i - 1][1] == word[i][0]){
isLoop = false;
break;
}
}
}
//
if(isLoop){
cout << "LOOP" << endl;
}else{
cout << "NO LOOP" << endl;
}
}
}
```
### d478
```cpp=
/*
* d478. 共同的數 - 簡易版
* C++
* AC(0.2s, 408KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//
int n,m;
cin >> n >> m;
while (n--){
int a[m],b[m];
for(int i=0;i<m;i++){
cin >> a[i];
}
for(int i=0;i<m;i++){
cin >> b[i];
}
//
int ai=0,bi=0,cnt=0;
while (ai<m && bi<m){
if(a[ai]==b[bi]){
cnt++;
ai++;
bi++;
}else if(a[ai]<b[bi]){
ai++;
}else{
bi++;
}
}
//
cout << cnt << endl;
}
return 0;
}
```
## e
### e313
```cpp=
/*
* e313. 最少相異字母
* C++
* AC (46ms, 352KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> v;
string ans = "";
int m = 26;
for(int i=0;i<n;i++){
string s;
cin >> s;
set<char>c;
for(int j=0;j<s.size();j++){
c.insert(s[j]);
}
//
if(c.size()<m){
v.clear();
m=c.size();
v.push_back(s);
ans=s;
}else if(c.size()==m){
v.push_back(s);
}
}
//
for (const auto& i : v) {
if (i < ans) {
ans = i;
}
}
cout << ans << endl;
}
```
### e339
```cpp=
/*
* e339. 前綴和練習
* C++
* AC (0.3s, 1.8MB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
cin >> N;
long long a;
long long b[N];
long long sum=0;
for(int i=0;i<N;i++){
cin >> a;
sum += a;
b[i] = sum;
}
//
for(int i=0;i<N;i++){
cout << b[i] << " ";
}
cout << endl;
return 0;
}
```
### e529
```cpp=
/*
* e529. 00482 - Permutation Arrays --
* C++
* AC (2ms, 328KB)
*/
#include<bits/stdc++.h>
using namespace std;
string line;
int main(){
int t;
cin >> t;
getline(cin ,line);
while(t--){
vector<int>a;
vector<float>b;
map<int,string>m;
//
getline(cin ,line);
//
int i=0;
getline(cin ,line);
stringstream line2(line);
string j="";
getline(cin ,line);
stringstream line3(line);
while(line2 >> i){
line3 >> j;
m[i]=j;
}
//
for(auto it = m.begin(); it != m.end(); ++it){
cout << it->second << '\n';
}
}
return 0;
}
```
## f
### f027
```cpp=
/*
* f027. 大木折木棍
* C++
* AC (4ms, 308KB)
*/
#include <bits/stdc++.h>
using namespace std;
bool asc(int a,int b){
return a<b;
}
int main(){
int t;
int x[3];
int a,b,c;
cin >> t;
for(int i=0;i<t;i++){
cin >> x[0] >> x[1] >> x[2];
sort(x,x+3,asc);
a = x[0],b = x[1],c = x[2];
if(a+b>c){
cout << "3" << endl;
}else if(c-b>=a){
cout << "4" << endl;
}else{
cout << "0" << endl;
}
}
return 0;
}
```
### f312
```cpp=
/*
* f312. 1. 人力分配
* C++
* AC (2ms, 324KB)
*/
#include <bits/stdc++.h>
using namespace std;
int a1,b1,c1;
int a2,b2,c2;
int n;
bool cmp(int a,int b){
return a>b;
}
int sum(int x1,int x2){
int y1 = a1*x1*x1+b1*x1+c1;
int y2 = a2*x2*x2+b2*x2+c2;
return y1+y2;
}
int main(){
cin >> a1 >> b1 >> c1;
cin >> a2 >> b2 >> c2;
cin >> n;
vector<int> x;
//
for(int i=0;i<=n;i++){
x.push_back(sum(i,n-i));
}
sort(x.begin(),x.end(),cmp);
cout << x[0] << endl;
return 0;
}
```
### f313
```cpp=
/*
* f313. 2. 人口遷移
* C++
* AC (5ms, 328KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int r,c,k,m;
cin >> r >> c >> k >> m;
int a[r][c];
int b[r][c];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
//
while(m){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(a[i][j]!=-1){
if(i!=0 && a[i-1][j]!=-1){
b[i][j]-=a[i][j]/k;
b[i-1][j]+=a[i][j]/k;
}
if(j!=0 && a[i][j-1]!=-1){
b[i][j]-=a[i][j]/k;
b[i][j-1]+=a[i][j]/k;
}
if(j!=c-1 && a[i][j+1]!=-1){
b[i][j]-=a[i][j]/k;
b[i][j+1]+=a[i][j]/k;
}
if(i!=r-1 && a[i+1][j]!=-1){
b[i][j]-=a[i][j]/k;
b[i+1][j]+=a[i][j]/k;
}
}
}
}
//
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
a[i][j] =b[i][j];
}
}
m--;
}
//
int min = 999999;
int max = 0;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(b[i][j]!=-1){
if(b[i][j]<min){
min=b[i][j];
}
if(b[i][j]>max){
max=b[i][j];
}
}
}
}
//
cout << min << endl;
cout << max << endl;
return 0;
}
```
### f579
```cpp=
/*
* f579. 1. 購物車
* C++
* AC (4ms, 344KB)
*/
#include <bits/stdc++.h>
using namespace std;
int a,b;
int s=0;
int sa=0,sb=0;
void buy(int n){
if(n>0){
if(n-a==0){
sa+=1;
}
if(n-b==0){
sb+=1;
}
}else{
n*=-1;
if(n-a==0){
sa-=1;
}
if(n-b==0){
sb-=1;
}
}
}
int main() {
int n;
cin >> a >> b;
cin >> n;
for(int i=0;i<n;i++){
int x=0;
sa=0,sb=0;
while(cin >> x){
if(x==0)break;
buy(x);
}
if(sa>=1 && sb>=1){
s+=1;
}
}
cout << s << endl;
return 0;
}
```
### f580
```cpp=
/*
* f580. 2. 骰子
* C++
* AC (2ms, 328KB)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,M;
cin >> N >> M;
//
int s[N+1][7];
for(int i=1;i<=N;i++){
s[i][1]=1; //上
s[i][2]=2; //右
s[i][3]=3; //後
s[i][4]=4; //前
s[i][5]=5; //左
s[i][6]=6; //下
}
//
for(int i=1;i<=M;i++){
int n,x;
cin >> n >> x;
if(x==-1){
int t[4] = { s[n][1],s[n][3],s[n][4],s[n][6] };
s[n][1]=t[1];
s[n][4]=t[0];
s[n][6]=t[2];
s[n][3]=t[3];
}else if(x==-2){
int t[4] = { s[n][1],s[n][2],s[n][5],s[n][6] };
s[n][1]=t[2];
s[n][2]=t[0];
s[n][5]=t[3];
s[n][6]=t[1];
}else{
int t[6] = { s[n][1],s[n][2],s[n][3],s[n][4],s[n][5],s[n][6] };
s[n][1]=s[x][1];
s[n][2]=s[x][2];
s[n][3]=s[x][3];
s[n][4]=s[x][4];
s[n][5]=s[x][5];
s[n][6]=s[x][6];
//
s[x][1]=t[0];
s[x][2]=t[1];
s[x][3]=t[2];
s[x][4]=t[3];
s[x][5]=t[4];
s[x][6]=t[5];
}
}
//
for(int i=1;i<=N;i++){
cout << s[i][1] << " ";
}
cout << endl;
return 0;
}
```
## g
### g275
```cpp=
/*
* g275. 1. 七言對聯
* C++
* AC (3ms, 340KB)
*/
#include <bits/stdc++.h>
using namespace std;
int a[7],b[7];
int fA(){
if(a[2-1]!=a[4-1] && a[2-1]==a[6-1] && b[2-1]!=b[4-1] && b[2-1]==b[6-1])return 1;
return 0;
}
int fB(){
if(a[7-1]==1 && b[7-1]==0)return 1;
return 0;
}
int fC(){
if(a[2-1]!=b[2-1] && a[4-1]!=b[4-1] && a[6-1]!=b[6-1])return 1;
return 0;
}
int main(){
int n;
cin >> n;
//
for(int i=0;i<n;i++){
for(int j=0;j<7;j++){
cin >> a[j];
}
for(int j=0;j<7;j++){
cin >> b[j];
}
//
int sum = fA()+fB()+fC();
if(fA()==0){
cout << "A";
}
if(fB()==0){
cout << "B";
}
if(fC()==0){
cout << "C";
}
if(sum==3){
cout << "None";
}
cout << "\n";
}
return 0;
}
```
### g488
```cpp=
/*
* g488. COVID-101
* C++
* AC (2ms, 336KB)
*/
#include <bits/stdc++.h>
using namespace std;
int n(int x){
if(x==1)return 1;
return n(x-1)+x*x-x+1;
}
int main(){
int x;
cin >> x;
int sum = n(x);
cout << sum << endl;
return 0;
}
```
### g595
```cpp=
/*
* g595. 1. 修補圍籬
* C++
* AC (3ms, 340KB)
*/
#include <bits/stdc++.h>
using namespace std;
int sum = 0;
void f(int a,int b,int c){
if(a==-1){
sum+=c;
}else if(c==-1){
sum+=a;
}else{
if(a>c){
sum+=c;
}else{
sum+=a;
}
}
}
int main(){
int n;
cin >> n;
int a[n];
for(int i=0;i<n;i++){
cin >> a[i];
}
//
for(int i=0;i<n;i++){
if(a[i]==0){
if(i-1<0){
f(-1,a[i],a[i+1]);
}else if(i+1>=n){
f(a[i-1],a[i],-1);
}else{
f(a[i-1],a[i],a[i+1]);
}
}
}
cout << sum << endl;
return 0;
}
```
## h
## i
### i213
```cpp=
/*
* i213. stack 練習
* C++
* AC (0.1s, 412KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
stack<int>s;
int n;
cin >> n;
while(n--){
int k;
cin >> k;
if(k==1){
int a;
cin >> a;
s.push(a);
}else if(k==2){
if(!s.empty()){
cout << s.top() << endl;
}else{
cout << -1 << endl;
}
}else if(k==3){
if(!s.empty()){
s.pop();
}
}
}
}
```
### i840
```cpp=
#include <bits/stdc++.h>
using namespace std;
/*
* i840. 字元矩陣轉置
* C++
* AC (2ms, 336KB)
*/
int main(){
char a[5][5];
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
cin >> a[i][j];
}
}
//
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
cout << a[j][i];
}
cout << "\n";
}
return 0;
}
```
## j
### j329
```cpp=
/*
* j329. 絕交
* C++
* AC (2ms, 324KB)
*/
#include <bits/stdc++.h>
using namespace std;
string f(string s){
if(s=="yes")return "想和";
if(s=="no")return "不想和";
return "";
}
int main(){
string A;
string B;
string C;
cin >> A;
cin >> B;
cin >> C;
cout << A << f(C) << B << "絕交\n";
return 0;
}
```
## k
### k605
```cpp=
/*
* k605. 班級成績單
* C++
* AC (3ms, 324KB)
*/
#include <bits/stdc++.h>
using namespace std;
struct define_test{
int num;
string name;
int s[5];
int score;
int rank;
};
bool cmp(define_test t1,define_test t2){
return t1.score>t2.score || (t1.score==t2.score && t1.num<t2.num);
}
int main(){
int N;
cin >> N;
define_test test[N];
for(int i=0;i<N;i++){
cin >> test[i].num >> test[i].name;
int a,b,c,d,e;
cin >> a >> b >> c >> d >> e;
test[i].s[0] = a;
test[i].s[1] = b;
test[i].s[2] = c;
test[i].s[3] = d;
test[i].s[4] = e;
test[i].score = a+b+c+d+e;
}
//
sort(test,test+N,cmp);
//
int rank = 1;
int x=0;
test[0].rank = rank;
for(int i=0;i<N;i++){
if(i!=0 && test[i].score != test[i-1].score){
rank=test[i-1].rank+x;
x=0;
}
x++;
test[i].rank = rank;
}
//
for(int i=0;i<N;i++){
cout << test[i].num << " " << test[i].name << " ";
cout << test[i].s[0] << " ";
cout << test[i].s[1] << " ";
cout << test[i].s[2] << " ";
cout << test[i].s[3] << " ";
cout << test[i].s[4] << " ";
cout << test[i].score << " ";
cout << test[i].rank << "\n";
}
return 0;
}
```
## l
### l960
```cpp=
/*
* l960. 星期幾？
* C++
* AC (2ms, 312KB)
*/
#include <bits/stdc++.h>
using namespace std;
int f(string s){
if(s=="Sunday")return 0;
if(s=="Monday")return 1;
if(s=="Tuesday")return 2;
if(s=="Wednesday")return 3;
if(s=="Thursday")return 4;
if(s=="Friday")return 5;
if(s=="Saturday")return 6;
return -1;
}
int main(){
string s;
cin >> s;
if(f(s)==-1){
cout << "error" << endl;
}else{
cout << f(s) << endl;
}
return 0;
}
```
## m
### m931
```cpp=
/*
* m931. 1. 遊戲選角
* C++
* AC (2ms, 324KB)
*/
#include<bits/stdc++.h>
using namespace std;
struct N{
int sum;
int a;
int b;
};
bool asc(N n1,N n2){
return n1.sum>n2.sum;
}
int main() {
int n;
cin >> n;
N x[n];
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
x[i].sum=a*a+b*b;
x[i].a=a;
x[i].b=b;
}
sort(x,x+n,asc);
cout << x[1].a << " " << x[1].b << endl;
}
```
### m932
```cpp=
/*
* m932. 2. 蜜蜂觀察
* C++
* AC (3ms, 332KB)
*/
#include<bits/stdc++.h>
using namespace std;
bool isRun[2][26];
int step=0;
int m,n,k;
void f(char c){
if(c>=65 && c<=90){
if(isRun[1][c-65]!=true){
isRun[1][c-65]=true;
step++;
}
}else if(c>=97 && c<=122){
if(isRun[0][c-97]!=true){
isRun[0][c-97]=true;
step++;
}
}
}
bool g(int x,int y){
if(x<0 || y<0 || x>=n || y>=m){
return false;
}else{
return true;
}
}
int main() {
cin >> m >> n >> k;
char a[n][m];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin >> a[j][i];
}
}
//
int sx = 0;
int sy = m-1;
//
for(int i=0;i<k;i++){
int x;
cin >> x;
int nx=sx;
int ny=sy;
if(x==0){
ny-=1;
}
if(x==1){
nx+=1;
}
if(x==3){
ny+=1;
}
if(x==4){
nx-=1;
}
//
if(x==5){
nx-=1;
ny-=1;
}
if(x==2){
nx+=1;
ny+=1;
}
//
if(g(nx,ny)){
sx=nx;
sy=ny;
}
//
f(a[sx][sy]);
//
cout << a[sx][sy];
}
cout << endl;
cout << step << endl;
return 0;
}
```
## n
### n621
```cpp=
/*
* n621. DD說這題是簡單題
* C++
* AC (8ms, 332KB)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,x;
cin >> n >> x;
cout << n/x+(n%x!=0)<< endl;
return 0;
}
```
# [leetcode](https://leetcode.com/problems/)
### 1
```cpp=
/*
* 1. Two Sum
* C++
* AC
* 8ms Beats 79.28%
* 14.06MB Beats 29.85%
*/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> ht; //哈希表
for(int i=0;i<nums.size();i++){
int diff = target-nums[i];
if(ht.count(diff)){
return {ht[diff],i};
}
ht[nums[i]]=i;
}
return{};
}
/* [2,7]
target = 9
9-2=7
key:2 value:0
9-7=2
找key:2得出value:0
return {0,1}
*/
};
```
### 3
```cpp=
/*
* 3. Longest Substring Without Repeating Characters
* C++
* AC
* 23ms Beats 29.35%
* 13.85MB Beats 23.01%
*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max_length=0;
int l=0,r=0;
unordered_set<char>ht;
//
for(r=0;r<s.length();r++){
while(ht.count(s[r])>0){ //查找右邊的字 只要有重複的
ht.erase(s[l]); //移除左邊重複的字
l++; //左邊往右一格
}
ht.insert(s[r]); //每次加右邊的字
max_length = max(max_length, r-l+1); //右邊到左邊=字串長度
}
return max_length;
}
};
```
### 9
```cpp=
/*
* 9. Palindrome Number
* C++
* AC
* 4ms Beats 84.59%
* 8.22MB Beats 48.69%
*/
class Solution {
public:
bool isPalindrome(int x) {
if( (x<0) || (x!=0 && x%10==0) ) return false;
int check=0;
while(x>check){
check = check*10 + x%10;
x/=10;
}
return (x==check || x==check/10);
}
};
```
### 12
```cpp=
/*
* 12. Integer to Roman
* C++
* AC
* 4ms Beats 73.65%
* 7.84MB Beats 95.43%
*/
class Solution {
public:
string intToRoman(int num) {
string s="";
while(num>=1000){
num-=1000;
s+="M";
}
while(num>=900){
num-=900;
s+="CM";
}
while(num>=500){
num-=500;
s+="D";
}
while(num>=400){
num-=400;
s+="CD";
}
while(num>=100){
num-=100;
s+="C";
}
while(num>=90){
num-=90;
s+="XC";
}
while(num>=50){
num-=50;
s+="L";
}
while(num>=40){
num-=40;
s+="XL";
}
while(num>=10){
num-=10;
s+="X";
}
while(num>=9){
num-=9;
s+="IX";
}
while(num>=5){
num-=5;
s+="V";
}
while(num>=4){
num-=4;
s+="IV";
}
while(num>=1){
num-=1;
s+="I";
}
return s;
}
};
```
### 13
```cpp=
/*
* 35. Search Insert Position
* C++
* AC
* 20ms Beats 9.65%
* 12.82MB Beats 23.76%
*/
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> roman_list;
//
roman_list['I'] = 1;
roman_list['V'] = 5;
roman_list['X'] = 10;
roman_list['L'] = 50;
roman_list['C'] = 100;
roman_list['D'] = 500;
roman_list['M'] = 1000;
//
int sum = 0;
for(int i = 0; i < s.length(); i++){
if(roman_list[s[i]] < roman_list[s[i+1]]){
sum -= roman_list[s[i]];
}
else{
sum += roman_list[s[i]];
}
}
return sum;
}
};
```
### 15
```cpp=
/*
* 15. 3Sum
*/
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]){
continue;
}
for (int j = i + 1; j < nums.size() - 1; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int target = -(nums[i] + nums[j]); // -(a+b) 求 c
auto lb = lower_bound(nums.begin() + j + 1, nums.end(), target); //從j+1 ~ end()
if (lb != nums.end()){ //沒找到
if(*lb == target) {
res.push_back({nums[i], nums[j], target}); // 添加三個數
}
}
}
}
return res;
}
};
```
### 17
```cpp=
/*
* 17. Letter Combinations of a Phone Number
* C++
* AC
* 4ms Beats 15.66%
* 8.50MB Beats 18.00%
*/
void permute(string digits, int index, unordered_map<char, vector<char>>& ht, string letter, vector<string>& sentence) {
if (index >= digits.size()) { //超過長度 : 添加到字母組合,不再遞迴
sentence.push_back(letter);
return;
}
//
char digit = digits[index];
vector<char> letters = ht[digit]; //那個按鍵的所有字母
for (int i = 0; i < letters.size(); ++i) { //原字母+新字母 遞迴
permute(digits, index + 1, ht, letter + letters[i], sentence);
}
}
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> sentence;
if(digits.empty()){
return sentence;
}
//
unordered_map<char, vector<char>>ht;
ht['2'] = {'a', 'b', 'c'};
ht['3'] = {'d', 'e', 'f'};
ht['4'] = {'g', 'h', 'i'};
ht['5'] = {'j', 'k', 'l'};
ht['6'] = {'m', 'n', 'o'};
ht['7'] = {'p', 'q', 'r', 's'};
ht['8'] = {'t', 'u', 'v'};
ht['9'] = {'w', 'x', 'y', 'z'};
//
permute(digits,0, ht,"", sentence);
/*
* 題目資料
* 旗標
* 按鍵對應表
* 字母
* 字母組合
*/
return sentence;
}
};
```
### 21
```cpp=
/*
* 21. Merge Two Sorted Lists
* C++
* AC
* 3ms Beats 83.23%
* 20.05MB Beats 5.39%
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* list3 = new ListNode(-1);
//
ListNode* h = list3;
ListNode* i = list1;
ListNode* j = list2;
while (i != nullptr || j != nullptr) {
if(i==nullptr){
h->next = new ListNode(j->val);
j = j->next;
h = h->next;
}else if(j==nullptr){
h->next = new ListNode(i->val);
i = i->next;
h = h->next;
}else if (i->val < j->val) {
h->next = new ListNode(i->val);
i = i->next;
h = h->next;
}else if(i->val > j->val) {
h->next = new ListNode(j->val);
j = j->next;
h = h->next;
}else if(i->val == j->val){
h->next = new ListNode(j->val);
j = j->next;
h = h->next;
//
h->next = new ListNode(i->val);
i = i->next;
h = h->next;
}
}
return list3->next;
}
};
```
### 35
```cpp=
/*
* 35. Search Insert Position
* C++
* AC
* 5ms Beats 24.10%
* 11.98MB Beats 84.91%
*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left=0;
int right=nums.size();
int mid=(left+right)/2;
while(left<right){
if(nums[mid]==target){
break;
}
else if(nums[mid]>target){
right--;
}
else{
left++;
}
mid=(left+right)/2;
}
return mid;
}
};
----
/*
* 35. Search Insert Position
* C++
* AC
* 0ms Beats 100.00%
* 12.25MB Beats 34.99%
*/
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0;
int r=nums.size()-1;
if(target>nums[r]){
return r+1;
}
if(target<nums[l]){
return l;
}
while(l<=r){
int m = l+(r-l)/2;
if(nums[m]==target){
return m;
}else if(nums[m]<target){
l=m+1;
}else if(nums[m]>target){
r=m-1;
}
}
return l;
}
};
```
### 66
```cpp=
/*
* 66. Plus One
* C++
* AC
* 0ms Beats 100.00%
* 10.23MB Beats 54.42%
*/
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for (auto it = digits.rbegin(); it != digits.rend(); ++it) { //從最後一位到第一位
if(*it < 9){ //<9就+1
(*it)++;
return digits;
}else { //是9就變0
*it = 0;
}
}
digits.insert(digits.begin(), 1); ////都是9就在最前面+1
return digits;
}
};
```
### 69
```cpp=
/*
* 69. Sqrt(x)
* C++
* AC
* 0ms Beats 100.00%
* 8.15MB Beats 87.68%
*/
class Solution {
public:
int mySqrt(int x) {
if (x == 0){
return 0;
}
int l = 1;
int r = x;
int y;
while (l <= r) {
y = l + (r - l) / 2;
if (y == x / y) {
return y;
} else if (y > x / y) {
r=y-1;
} else {
l=y+1;
}
}
return r;
}
};
```
```cpp=
/*
* 70. Climbing Stairs
* C++
* AC
* 2ms Beats 49.47%
* 7.26MB Beats 52.09%
*/
class Solution {
public:
int climbStairs(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
vector<int> dp;
dp.push_back(1);
dp.push_back(1);
while(dp.size()!=n+1){
dp.push_back(dp[dp.size() - 1] + dp[dp.size() - 2]);
}
return dp[n];
}
};
----
class Solution {
public:
int climbStairs(int n) {
if(n<=1){
return 1;
}
int O=1;
int N=1;
int t;
n--;
while(n--){
t=N;
N+=O;
O=t;
}
if(N>O){
return N;
}else{
return O;
}
}
};
```
### 88
```cpp=
/*
* 69. Sqrt(x)
* C++
* AC
* 2ms Beats 49.60%
* 11.11MB Beats 7.11%
*/
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int j=0,i=m ; j<n ; i++,j++){
nums1[i] = nums2[j];
}
sort(nums1.begin(),nums1.end());
}
};
```
### 141
```cpp=
/*
* 141. Linked List Cycle
* C++
* AC
* 20ms Beats 6.75%
* 14.21MB Beats 8.08%
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set <ListNode*>ht;
if (head == nullptr || head->next == nullptr) {
return false;
}
//
ListNode *now = head;
while (now != nullptr) {
if (ht.count(now) > 0) {
return true;
}
ht.insert(now);
now = now->next;
}
//
return false;
}
};
```
### 160
```cpp=
/*
* 160. Intersection of Two Linked Lists
* C++
* AC
* 56ms Beats 14.39%
* 23.72MB Beats 6.00%
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
map<ListNode* ,int>m;
while(headA!=NULL){
m[headA]++;
headA=headA->next;
}
while(headB!=NULL){
if(m[headB]){
return headB;
}
headB=headB->next;
}
return NULL;
}
};
```
### 222
```cpp=
/*
* 222. Count Complete Tree Nodes
* C++
* AC
* 21ms Beats 74.16%
* 29.15MB Beats 44.06%
*/
class Solution {
public:
int solve(TreeNode* root){
if(root==NULL) return 0;
return 1+solve(root->left)+solve(root->right);
}
int countNodes(TreeNode* root) {
return solve(root);
}
/*
1 樹根
往左走
往右走
*/
};
```
### 278
```cpp=
/*
* 278. First Bad Version
* C++
* AC
* 0ms Beats 100.00%
* 7.62MB Beats 6.06%
*/
class Solution {
public:
int firstBadVersion(int n) {
int l=0;
int r=n;
while(l<=r){
int m = l+(r-l)/2;
if(isBadVersion(m)){
r=m-1;
}else{
l=m+1;
}
}
return l;
}
};
```
### 1700
```cpp=
/*
* 1700. Number of Students Unable to Eat Lunch
* C++
* AC
* 0ms Beats 100.00%
* 11.10MB Beats 40.68%
*/
class Solution {
public:
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int t1 = 0;
int t2 = 0;
int len = students.size();
int no = 0;
while(no<len){
if(students[t1]==sandwiches[t2]){
students[t1]=-1;
sandwiches[t2]=-1;
t1+=1;
t2+=1;
no = 0;
if (t2 == sandwiches.size()) {
break;
}
}else{
students.push_back(students[t1]);
students[t1]=-1;
t1+=1;
no+=1;
}
}
return len-t2;
}
};
```
# [LIOJ](https://oj.lidemy.com/)
## Low
### 1008
```cpp=
/*
* 1008 幾個水桶
* C++
* AC
* Time: 0ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
int cnt=0;
while(n){
if(n%2==1){
cnt+=1;
}
n/=2;
}
cout << cnt << endl;
}
```
### 1011
```cpp=
/*
* 1011 183 Club
* C++
* AC
* Time: 0ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
float sum;
for(int i=0;i<n;i++){
float a;
cin >> a;
sum+=(a/n);
}
if(sum>=183){
cout << "real" << endl;
}else{
cout << "fake" << endl;
}
}
```
### 1017
```cpp=
/*
* 1011 貪婪的小偷
* C++
* AC
* Time: 0ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
bool desc(int a,int b){
return a>b;
}
int main(){
int c,n;
cin >> c >> n;
vector<int>x(n);
if(c>n){
c=n;
}
for(int i=0;i<n;i++){
cin >> x[i];
}
//
sort(x.begin(),x.end(),desc);
//
long long int sum;
sum=0;
for(int i=0;i<c;i++){
sum+=x[i];
}
cout << sum << endl;
}
```
### 1020
```cpp=
/*
* 1020 判斷質數
* C++
* AC
* Time: 4ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
bool desc(int a,int b){
return a>b;
}
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int x;
cin >> x;
if(x==1){
cout << "Composite" << endl;
continue;
}
if(x==2){
cout << "Prime" << endl;
continue;
}
//
if(x%2==0){
cout << "Composite" << endl;
continue;
}
//
int cnt=1;
for(int j=3;j<=x;j+=2){
if(x%j==0){
cnt+=1;
}
}
if(cnt==2){
cout << "Prime" << endl;
}else{
cout << "Composite" << endl;
}
}
}
```
## Mid
### 1052
```cpp=
/*
* 1052 貪婪的小偷 Part2
* C++
* AC
* Time: 0ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
int limit[n+1]; //限制
int value[n+1]; //價值
for(int i=1;i<=n;i++){
cin >> limit[i] >> value[i];
}
//物品:n 限制:m 全部填0
vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
//
for(int i=1;i<=n;i++){ //物品
for(int j=1;j<=m;j++){ //限制
dp[i][j] = dp[i-1][j]; //上個物品的最佳解
if(limit[i]<=j){ //這個物品符合限制的話
int _now = dp[i][j];
int _new = dp[i-1][j-limit[i]]+value[i]; //多餘的重量買上一個物品 + 現在的物品
dp[i][j] = max(_now,_new);
}
}
}
//
cout << dp[n][m] << endl;
}
```
# [ASOJ](https://apcs-simulation.com/problem/)
## Low
### apcs0101
```cpp=
/*
* apcs0101 電車難題(Metro)
* C++
* AC
* Time: 4ms
* Memory: 3MB
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,p,m,k,d;
cin >> n >> p >> m >> k >> d;
int sit = p>n ? n : p;
int stand = p>n ? p-n : 0;
int stand2 = stand-k;
int sit2 = n-(sit-m+stand2);
if(sit2>=d){
cout << "Happy :>" << endl;
cout << sit2-d << endl;
}else{
cout << "Sad :((" << endl;
cout << (d-1)-sit2 << endl;
}
}
```
### apcs0201
```cpp=
/*
* apcs0201 氧化還原滴定 (Redox titration)
* C++
* AC
* Time: 4ms
* Memory: 3MB
*/
#includ
#include<bits/stdc++.h>
using namespace std;
/* 概念
2*(C1*V1) = 5*(C2*V2)
*/
int main(){
int C1,C2,V1,V2;
cin >> C1 >> C2 >> V1 >> V2;
if(2*C1*V1 == 5*C2*V2){
cout << "Yes" << endl;
cout << 2*C1*V1 << endl;
}else{
cout << "No" << endl;
}
}
```
# [UVa](https://onlinejudge.org/external/)
## 1
### 122
```cpp=
/*
* 122 Trees on the level
* C++
*/
#include <bits/stdc++.h>
using namespace std;
struct Tree{
Tree *left;
int val;
Tree *right;
};
void I(Tree *temp, int val = 0) { // init
temp->left = nullptr;
temp->right = nullptr;
temp->val = val;
}
Tree* L(Tree *temp, int val = 0) { // left
if (temp->left == nullptr) {
temp->left = new Tree();
I(temp->left, val);
}
return temp->left;
}
Tree* R(Tree *temp, int val = 0) { // right
if (temp->right == nullptr) {
temp->right = new Tree();
I(temp->right, val);
}
return temp->right;
}
//
void bfs(Tree* root) {
if (root == nullptr) return;
queue<Tree*> q;
q.push(root);
while (!q.empty()) {
Tree* current = q.front();
q.pop();
cout << current->val << " ";
if (current->left){
q.push(current->left);
}
if (current->right){
q.push(current->right);
}
}
cout << endl;
}
void dfs(Tree* node) {
if (node == nullptr) return;
stack<Tree*> s;
s.push(node);
while (!s.empty()) {
Tree* current = s.top();
s.pop();
cout << current->val << " ";
if (current->right) s.push(current->right);
if (current->left) s.push(current->left);
}
cout << endl;
}
//
int main(){
string s;
Tree *root = new Tree();
I(root);
bool key=false;
while (cin >> s) {
if (s == "()"){
break;
}
char ch;
int value;
string path;
stringstream parser(s);
parser >> ch >> value >> ch >> path;
Tree* current = root;
if(path==")"){
key=true;
}else{
for (char direction : path) {
if (direction == 'L') {
current = L(current);
}else if (direction == 'R') {
current = R(current);
}
else{
break;
}
}
}
current->val = value;
}
if(key){
bfs(root);
}else{
cout << "not complete" << endl;
}
}
```
## 103
### 10370
```cpp=
/*
* 10370 Above Average
* C++
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int m;
cin >> m;
float sum=0;
for(int j=0;j<m;j++){
int score;
cin >> score;
sum += score;
}
sum/=m;
cout << fixed << setprecision(3) << sum << "%\n";
}
}
```
## 109
### 10935
```cpp=
/*
* 10935 Throwing cards away I
* C++
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
while(cin >> n){
if(n==0){
break;
}
deque<int>dq;
for(int i=1;i<=n;i++){
dq.push_back(i);
}
int x;
cout << "Discarded cards: ";
for(int i=1;i<=n;i++){
x=dq[0];
if(i==n){
cout << "\nRemaining card: " << x << endl;
}else{
cout << x;
if(i!=n-1){
cout << ", ";
}
}
dq.pop_front();
x=dq[0];
dq.pop_front();
dq.push_back(x);
}
}
}
```
## 119
### 11988
```cpp=
/*
* 11988 Broken Keyboard (a.k.a. Beiju Text)
* C++
*/
#include<bits/stdc++.h>
using namespace std;
struct ListNode{
char val;
ListNode* next;
ListNode(char x) : val(x), next(nullptr) {}; // 創建點的方法
};
int main(){
string s;
cin >> s;
ListNode* a = new ListNode('0'); // 剛開始一定要有值
ListNode* ah=a;
ListNode* b = new ListNode('0');
ListNode* bh=b;
bool key=false;
for(int i=0;i<s.size();i++){
if(s[i]=='['){
key=true;
continue;
}else if(s[i]==']'){
key=false;
continue;
}
if(!key){
a->next = new ListNode(s[i]);
a=a->next;
}else{
b->next = new ListNode(s[i]);
b=b->next;
}
}
b->next=ah->next; //為了跳過a開頭
ListNode* current = bh->next; //為了跳過b開頭
while (current != nullptr) {
cout << current->val;
current = current->next;
}
cout << endl;
return 0;
}
```
# [TIOJ](https://tioj.ck.tp.edu.tw/problems/)
### 1001
```cpp=
/*
* 1001. Hello World!
* C++
* AC
* Time (2.6 ms)
* VSS (6056 KiB)
* Code Length (116 Bytes)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
cout << "Hello Tmt World XD!" << endl;
return 0;
}
```
### 1003
```cpp=
/*
* 1003. 切義大利餅問題
* C++
* AC
* Time (2.6 ms)
* VSS (6056 KiB)
* Code Length (238 Bytes)
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
int n=1;
int m=0;
for(int i=1;i<=x;i++){
if(i%2==1){
m=n+i;
}else{
n=m+i;
}
}
cout << ((m>n) ? m : n) << endl;
}
```
### 1025
```cpp=
/*
* 1025. 數獨問題
* C++
* AC
* Time (9.7 ms)
* VSS (6056 KiB)
* Code Length (1.52 KB)
*/
#include<bits/stdc++.h>
using namespace std;
array<array<int, 9>, 9> board;
array<bitset<9>, 9> row = {0,0,0,0,0,0,0,0,0};
array<bitset<9>, 9> col = {0,0,0,0,0,0,0,0,0};
array<bitset<9>, 9> cell = {0,0,0,0,0,0,0,0,0};
int cnt = 0;
void input() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> board[i][j];
if (board[i][j] != 0) {
row[i][board[i][j]-1] = 1; //橫
col[j][board[i][j]-1] = 1; //直
cell[(i/3)*3 + (j/3)][board[i][j]-1] = 1; //區塊
}
}
}
}
void print() { //打印
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << board[i][j] << " ";
}
cout << endl;
}
cout << endl;
cnt++;
}
void solve(int i, int j) {
if (i == 9) { // 結束一種解法
print();
return;
}
if (j == 9) { // 換行
solve(i + 1, 0);
return;
}
if (board[i][j] != 0) { // 直接往右
solve(i, j + 1);
return;
}
//
for (int num = 1; num <= 9; num++) { // 填1~9
int cellIndex = (i / 3) * 3 + (j / 3);
if (!row[i][num-1] && !col[j][num-1] && !cell[cellIndex][num-1]) {//三個都確定沒填過
board[i][j] = num; //填數字
row[i][num-1] = col[j][num-1] = cell[cellIndex][num-1] = 1; //改成1
solve(i, j + 1); //往右
board[i][j] = 0; //回朔 看能不能填其他
row[i][num-1] = col[j][num-1] = cell[cellIndex][num-1] = 0; //回朔 看能不能填其他
}
}
}
int main() {
input(); //輸入
solve(0, 0); //左上角開始
cout << "there are a total of " << cnt << " solution(s)." << endl;
return 0;
}
```
### 1053
```cpp=
/*
* 1053. [入門]難度1.除法練習
* C++
* AC
* Time (2.8 ms)
* VSS (6056 KiB)
* Code Length (256 Bytes)
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin >> a >> b;
if(a>b){
if(a%b==0){
cout << "Y" << endl;
}else{
cout << "N" << endl;
}
}else{
if(b%a==0){
cout << "Y" << endl;
}else{
cout << "N" << endl;
}
}
}
```
Sign in with Wallet
Connect another wallet