---
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;
}
}
```
Sign in with Wallet
Connect another wallet