---
# System prepended metadata

title: NYCU GPE
tags: [Programming Practice]

---

---
tags: Programming Practice
---
 
 NYCU GPE
 # NYCU GPE
 
 ## 22351 : Quirksome Squares
 只要判斷完全平方數即可，少用pow函數
 ```cpp=1
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int table[9] = {0,10,100,1000,10000,10000,1000000,10000000,100000000};
int main (void){
    int n = 0 ;
    while (cin >> n){
        for (int i= 0 ; i<table[n] ; i++){
            int r = (i/table[n/2]) + (i%table[n/2]);
            if ( pow(r,2) == i ){
                if (n==2) printf ("%02d\n" , i);
                if (n==4) printf ("%04d\n" , i);
                if (n==6) printf ("%06d\n" , i);
                if (n==8) printf ("%08d\n" , i);
            }
        }
    }
    return 0;
}

 ```
 
## 11028 : Digit Primes
判斷質數：
1. 除了 2、3 ，質數一定滿足 6N+1 或 6N+5
2. 只需要檢查 3~根號K

```cpp=1
#include<iostream>
#include<cmath>
using namespace std;
int is_prime(int k){
    if (k==0 || k==1) return 0;
    else if (k==2 || k==3) return 1;
    else{
        int upper_bound = pow(k,0.5);
        if ((k-1)%6 == 0 || (k-5)%6 == 0){
            for (int i = 3; i <= upper_bound ; i++){
                if (k % i == 0) return 0;
            }
        }
        else{
            return 0;
        }
        return 1;
    }
     
}
int digital_sum(int k){
    int ans =0;
    while(k>0){
        ans += k % 10;
        k = k /10;
    }
    return ans;
}
int main (void){
    int ca = 0;
    cin >> ca;
    int M = 0 , N = 0;
    for (int idx = 0 ;idx<ca;idx++){
        cin >> M >> N;
        int count = 0;
        for (int i = M ; i <= N ; i++){
            int a = is_prime(i);
            if (a==1){
                int b = is_prime(digital_sum(i));
                if (b==1){
                    count++;
                }
            }
        }
        cout <<  count << endl;
    }
    return 0;
}
```

## 11017 : Longest Common Subsequence
LCS:
建立DP
Hint: arr 長寬都個多一 
```cpp=1
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main (void){
    string M, N;
    while (1){
        getline(cin , M);
        getline(cin , N);
        if (M=="" || N=="") break;
        vector < vector<int> > arr;
        for (int i = 0 ; i <= M.size() ; i ++){
            vector<int> temp;
            for (int j = 0 ; j <= N.size() ; j++){
                temp.push_back(0);
            }
            arr.push_back(temp);
        }
        for (int i =1 ; i <=  M.size() ; i++){
            for (int j=1 ; j <= N.size() ; j++){
                if (M[i-1] == N[j-1]){
                    arr[i][j] = arr[i-1][j-1]+1;
                }
                else{
                    arr[i][j] = max(arr[i-1][j],arr[i][j-1]);
                }
            }
        }
        cout <<arr[M.size()][N.size()] <<endl;
    }
    return 0;
}
```

## 24731:Roads in the North


## 2015-09: Longest Increasing Subsequence

```cpp=1
#include <iostream>
#include <vector>
using namespace std;
int main (void){
    int n = 0;
    while ( cin >> n){
        vector <int> arr;
        vector <int> dp;
        for (int i = 0 ; i < n ; i++){
            int temp;
            cin >> temp;
            arr.push_back(temp);
            dp.push_back(1);
        }
        int ans = 0;
        for (int i = 0 ; i < arr.size() ; i++){
            for (int j = 0 ; j < i ; j++){
                if (arr[i] > arr[j]){
                    dp[i] = max (dp[i] , dp[j]+1);
                }
            }
            ans = max (ans , dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}
```

## 23681: Bachet's Game
因為stan 先開始，所以只針對stan的狀態
確保 j - k[i] >= 0 && status[j - k[i]] 狀態為輸
j 為石頭數量 k[i] 為拿法
```cpp=1
#include<iostream>
#include<vector>
using namespace std;
int main (void){
    int n , m ;
    while(1){
        cin >> n >> m ;
        vector <int> k;
        vector <int> status;
        for (int i = 0 ; i <= n ; i++){
            status.push_back(0);
        }
        for (int i = 0; i < m ; i++){
            int temp ;
            cin >> temp;
            k.push_back(temp);
        }
        for (int j = 1 ; j <= n ;j++){
            for (int i = 0 ; i < m; i++){
                if (j-k[i] >= 0 && status[j-k[i]]==0)
                    status[j]=1;
            }
        }
        if (status[n]==1)
            cout << "Stan Wins" << endl;
        else{
            cout << "Ollie Wins" << endl;
        }
    }
}
```
## 10675: Urn-ball Probabilities
题目要求所有抽取中，至少有一次抽到两个红球的概率
我们算出所有抽取中，每次都没有抽到两个红球的概率Q=(q1*q2*q3……qn)，则1-Q为所求答案
另外要求出，每一次都抽到两个红球的概率，即P=(p1*p2*p3……pn)
但P这个数值必定非常小，所以题目只需要输出P小数点后有多少个连续的0
所以取log
```cpp=1
#include<iostream>
#include<vector>
#include<stdio.h>
#include<cmath>
using namespace std;
int main (void){
    double p=1 , q=1 , a=0;
    vector<double> ans;
    vector<int>c;
    for (long long i = 1 ; i <= 1000000 ; i++){
        p = (1.0 / i) * ( 1.0 / (i+1) );
        q *= 1.0-p;
        ans.push_back(1-q);
        a += log10(p);
        c.push_back(abs(a));
    }
    int n;
    while(cin >> n){
        if (n==0){
            break;
        }
        printf("%.6f %d\n",ans[n-1],c[n-1]);
    }
}
```

## 10422:Is This Integration
畫輔助線，正三角形單一內角=60度
```cpp=1
#include<iostream>
#include<cmath>
using namespace std;
int main (void){
    double n;
    double pi = M_PI;
    while (cin >> n){
        if (n==0) break;
        double ans1 , ans2 , ans3;
        ans3 = ((n * n / 2.0) - ( n * n * pow(3,0.5) / 8.0) - (n * n * pi / 12.0) )*8 ;
        ans2 = ((n * n) - (n * n * pi / 4.0) - (ans3 / 2.0 ) )* 4; 
        ans1 = n*n - ans2 - ans3; 
        printf("%.3f %.3f %.3f\n",ans1,ans2,ans3 );
    }
}
```

## 24461: Sum of Consecutive Prime Numbers

先建立質數表
從小的質數往上加，超過數值後從頭往下減

```cpp=1
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int judge_prime(int a){
    if ( a==0 || a==1 ){
        return 0;
    }
    else if ( a==2 || a==3){
        return 1;
    }
    else {
        int upper_bound = pow(a,0.5);
        if ((a-1)%6 ==0 || (a-5)%6 ==0 ){
            for (int i=2; i <= upper_bound ; i++){
                if (a%i == 0 ) return 0;
            }
        }
        else{
            return 0;
        }
        return 1;
    }

}
int main(){
    vector <int> ptable;
    for (int i=2; i < 10000 ; i++){
        if (judge_prime(i) == 1) ptable.push_back(i);
    }
    int test;
    while(cin >> test){
        int sum=0,c=0,j=0;
        if (test == 0 ) break;
        for (int i = 0 ; test >= ptable[i] ; i++){
            sum += ptable[i];
            while(sum > test){
                sum -= ptable[j];
                j++;
            }
            if (sum == test) c++;
        }
        cout << c << endl;
    }
}
```
## 10500:Brick Wall Patterns
費氏數列
```cpp=1
#include<iostream>
using namespace std;
int main (void){
    long long DP[60]={0,1,2};
    for (int i=3; i<59; i++){
        DP[i] = DP[i-1] + DP[i-2];
    }
    int n;
    while(cin >> n){
        if (n==0) break;
        cout << DP[n] <<  endl;
    }
    return 0;
}
```
## 10471:COUNTING CHAOS
先檢查有沒有超過一天, 之後用窮局法依次檢查
```cpp=1
#include<iostream>
#include<stdio.h>
#include<cstdlib>
#include<cstring>
using namespace std;
int main (void){
    int n;
    while(cin >> n){
        if (n==0) break;
        int x ,y,n;
        scanf("%2d:%2d",&x,&y);
        int time;
        time = 60*x + y;
        char str[10];
        while(1){
            time++;
            if (time >= 1440) time=0;
            x = time / 60 ; y = time % 60;
            sprintf(str , "%02d%02d" , x ,y);
            sscanf(str, "%d", &n);
            sprintf(str, "%d", n);
            int flag =0;
            for (int i=0 , j=strlen(str)-1 ; i < j ; i++ , j--){
                if (str[i] != str[j] ){
                    flag = 1;
                }
            } 
            if (!flag){
                printf("%02d:%02d\n",x,y);
                break;
            }
        }
    }
}
```

## 21944:Power Crisis
+i mod j
```cpp=1
#include<iostream>
#include<string>
using namespace std;
int main (void){
    int n;
    int i;
    while (cin >> n){
        n--;
        for (i = 1 ; i < n ;i++){
            int turnoff = 0;
            for (int j = 1 ; j <= n ;j++){
                turnoff = (turnoff+i) % j;
            }
            if (turnoff == 11) break;
        }
        cout << i << endl;
    }
}
```

## 10605:Count the Trees
從n+2 乘到 2n  + 大數乘法
```cpp=1
#include<iostream>
using namespace std;
const int MAX (1e8);
long long ans[MAX];
int main (void){
    int n;
    while(cin >> n && n!=0){
        ans[0]=1;
        int len = 0;
        for (int i =n+2; i<=2*n; i++){
            int temp =0;
            for (int j=0; j<=len;j++){
                ans[j] = ans[j] *i + temp;
                temp = ans[j] / 100;
                ans[j] = ans[j] % 100;
            }
            if (temp>0){
                len++;
                ans[len] = temp;
            }
        }
        for (int i = len ; i >=0 ; i --){
            if (ans[i]==0){
                cout << "00";
            }
            else{
                cout << ans[i];
            }
        }
        cout << endl;
    }
    return 0;
}
```

## 10528:Light, more light
判斷是否為完全平方數
```cpp=1
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int n;
    while(cin >> n && n!=0){
        int temp;
        temp = sqrt(n);
        if (temp * temp == n ){
            cout << "yes" << endl;
        }
        else{
            cout << "no" << endl;
        }
    }
    return 0;
}
```
## 11192:Simple Minded Hashing

題目的範圍過於浮誇
由於限制小寫英文字母，所以 a ~ z 有 26 個，而函數值為 1 + 2 + ... + 25 + 26 = 351

設一個 dp[i][j][k]
i 代表選到哪一個字母
j 為 L ，代表字串長度
k 為 S ，代表函數值

字母 i 可選也可不選，所以 dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - i]
(前者不選 i ，後者選 i )

同樣是事先全部建完表後再輸入資料
最後輸出答案 dp[26][L][S]

```cpp=1
#include <iostream>
#include <cstring>
using namespace std;
int dp[27][27][352];
int main (void){
    int L,S,ca;
    ca =1;
    memset (dp , 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1 ; i <= 26 ; i++){
        for (int j = 0 ; j <= i ; j++){
            for (int k = 0 ; k <=351 ; k++){
                dp[i][j][k] = dp[i - 1][j][k];
                if (j && k >= i){
                    dp[i][j][k] += dp[i-1][j-1][k-i];
                }
            }
        }
    }
    while (cin >> L >> S && L!=0 && S!=0){
        cout << "Case " << ca << ": " << dp[26][L][S] << endl;
        ca++;
    }
}
```

## 22161:Euclid Problem
輾轉相除法
```cpp=1
#include<iostream>
using namespace std;
int gcd(int a, int b , int &x, int &y){
    if (a % b == 0){
        x = 0;
        y = 1;
        return b;
    }
    else{
        int r, tx,ty;
        r = gcd(b , a%b , tx , ty);
        x = ty;
        y = tx - a/b*ty;
        return r;
    }
}
int main (void){
    int a,b,r,x,y;
    while(cin >> a >> b){
        r = gcd(a,b,x,y);
        cout << x << " "<<y <<" "<< r << endl;
    }
    return 0;
}
```

##  10655:Sumsets
```cpp=1
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main(void){
    int n , tmp;
    int nums[1002];
    map<int,bool>subset;
    while(cin >> n){
        if (n==0) break;
        for (int i = 0 ;i < n ;i++){
            cin >> nums[i];
            subset[nums[i]]=true;
        }
        sort(nums,nums+n,greater<int>());
        bool found = false;
        int result;
        for (int i = 0; i<n ;i++){
            for (int j = 0;j <n ;j++){
                if (i==j) continue;
                for (int k = 0; k<n;k++){
                    if (k==i || k==j) continue;
                    tmp = nums[i] - nums[j] - nums[k];
                    if (subset.find(tmp) != subset.end() && tmp != nums[i] && tmp != nums[j] && tmp != nums[k]) {
                        found = true;
                        result = nums[i];
                        i = j = k = n;
                    }
                }
            }
        }
        if (found) cout << result << endl;
        else cout << "no solution" << endl;
    }
    return 0;
}
```

## 22181:Dollars
 dp[j] += dp[j-possible[i]];
```cpp=1
#include<iostream>
#include<stdio.h>
using namespace std;
int main (void){
    long long dp[30005]={1};
    long long possible[15] = {5,10,20,50,100,200,500,1000,2000,5000,10000};
    for (int i = 0; i < 11 ; i++){
        for (int j = possible[i] ; j <= 30000 ; j++){
            dp[j] += dp[j-possible[i]];
        }
    }
    int x,y;
    while (scanf("%d.%d",&x,&y)){
        if(x==0 && y==0 ) break;
        printf ("%3d.%02d%17lld\n",x , y, dp[100*x+y]);
    }
    
    return 0;
}
```

## 22151:Big Mod
首先，要先知道數學式子：(A*B)%C = (A%C) * (B%C)。因此我就可以不用把B^P算完再去對M取餘數(避免超過變數範圍)，但是如果是((((B%M)*B)%M)*B)%M…..這樣乘的話會TLE的，所以算次方請用次方除二相乘的遞迴來算次方，也就是 (B^P)%M = (B^(P/2)%M) * (B^(P/2)%M) 這樣遞迴。
```cpp=1
#include<iostream>
using namespace std;
long long big_mod(long long B , long long P , long long m){
    if (P==0) return 1;
    else if (P==1) return B%m;
    else {
        long long result = big_mod(B,P/2,m);
        if(P%2==1){
            return result*result*B %m;
        }
        else{
            return result*result%m;
        }
    }
}
int main (void){
    long long B,P,m;
    while(cin >> B >> P >> m){
        cout << big_mod(B,P,m) << endl;
    }
    return 0;
}
```

## 10582:Power Strings
```cpp=1
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int main (void){
    string s;
    while(cin >> s && s!="."){
        vector<int>failure;
        for (int i=0; i<s.length();i++){
            failure.push_back(0);
        }
        for (int i=1, j=failure[0]=-1 ; i<s.length(); i++){
            while(j>=0 && s[j+1] != s[i]){
                j = failure[j];
            }
            if(s[j+1] == s[i]){
                j++;
            }
            failure[i] = j;
        }
        int repeat = s.length() - failure[s.length()-1]-1 ;
        if (s.length() % repeat == 0){
            cout << s.length() / repeat << endl;
        }
        else{
            cout << "1" << endl;
        }
    }
}
```


## 10416:Last Digit
0147656369

```cpp=1
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int map[20]={0,1,5,2,8,3,9,2,8,7,7,8,4,7,3,8,4,1,5,4};
int main(void){
    string n;
    while (cin >> n){
        int len = n.length();
        if (len=='0') break;
        int value = n[len-1]-'0';
        if (len > 1){
            value += (n[len-2]-'0')*10;
        }
        cout << (map[value%20] + value/20*4) % 10 << endl;
    }

}
```

## 10465:Necklace
```cpp=1
#include <bits/stdc++.h>
using namespace std;
int main(void){
    double vt ,v0;
    while (cin >> vt >> v0){
        int p = 0;
        double max = 0;
        for (int i = 1 ; i < vt ; i++){
            if ((double)vt/i - v0 < 0 ) break;
            double sum = 0.3*i*sqrt((double)vt/i - v0);
            if (fabs(max - sum) <= 1e-10){
                p=0; break;
            }
            else if (sum > max){
                max = sum;
                p=i;
            }
        }
        
        cout << p << endl;
    }
    return 0;
}
```

## 23661:Bit Mask
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int main (void){
    unsigned int N , L ,U;
    while (cin >> N >> L >> U ){
        int ans =0;
        for (int i =31 ; i >=0 ; i--){
            if ((ans | (1<<i)) > U ) continue;
            if ((ans | (1<<i)) <= L || !(N & (1 << i))){
                ans |= (1 << i);
            }
        }
        cout << ans << endl;
    }
    return 0;
}
```

## 10615:Divisibility
dp[x+1][y] = y + k +- arr[i] =1
查看dp[n][0]
```cpp=0
#include<bits/stdc++.h>
using namespace std;
int dp[10001][101];
int arr[10001];
int main (void){
    int t , n ,k;
    cin >> t ;
    for (int i =0 ;i < t ; i++){
        cin >> n >> k;
        for (int j = 0 ; j <n ; j++){
            cin >> arr[j];
        }
        for (int j = 0 ; j <n ; j++){
            arr[j] = abs(arr[j])%k;
        }

        memset(dp,0,sizeof(dp));
        dp[0][0] = 1 ;
        for (int x = 0 ; x < n ; x ++){
            for (int y = 0; y < k; y++){
                if (dp[x][y]){
                    dp[x+1][(y+k+arr[x]) % k] =1;
                    dp[x+1][(y+k-arr[x]) % k] =1;
                }
            }
        }
        if(dp[n][0]) cout << "YES"<< endl;
        else cout << "NO" << endl; 

        // for (int x = 0 ; x < n+1 ; x ++){
        //     for (int y = 0; y < k; y++){
        //        cout << dp[x][y] <<" ";
        //     }
        //     cout << endl; 
        // }
    }
}
```

## 10603:Cutting Sticks

```cpp=1
#include<bits/stdc++.h>
using namespace std;
int dp[55][55];
int a[55];
int solve(int x, int y){
    if (~dp[x][y]) return dp[x][y];
    if (x+1==y) return dp[x][y]=0;
    int cost = 999999;
    for (int i=x+1 ; i<y ;i++){
        cost = min(cost,solve(x,i)+solve(i,y));
    }
    return cost+a[y]-a[x];
}
int main (void){
    int L ,N ;
    while (cin >> L){
        memset(dp,-1,sizeof(dp));
        memset(a,0,sizeof(a));
        cin >> N;
        for (int i=1 ; i<=N ; i++){
            cin >> a[i];
        }
        a[N+1] = L;
        cout << solve(0,N+1) << endl;
    }
}
```