CPE一顆星考題:
17.The Hotel with Infinite Rooms
題意：依據觀察當入住人數>第b天，代表找到答案(梯形面積)
有一間很奇怪的旅館，他有無限多的房間。來到這家旅館的旅行團都遵守以下的規則：
- 同一個時間只能住一個旅行團
- 每一旅行團在一早就住進旅館，然後在另一天的晚上離開。
- 上一個旅行團離開之後，隔天早上另一旅行團即住進。
- 除了第一個旅行團之外，每個剛來的旅行團的人數都比上一個旅行團多一人。
- 有n個人的旅行團會在旅館住n天。例如：有一個4個人的旅行團在8月1日上午住進旅館，他們會在8月4日晚上離開旅館。下一個有5個人的旅行團會在8月5日住進，並且停留5天。
給你第一個旅行團的人數，請你告訴我在某一天住在這家旅館的旅行團的人數有多少人。
#include <iostream>
using namespace std;
int main(){
long long int a,b; //入住的人數a，想查的第b天人數
int p; //計算第b天入住人數
while(cin>>a>>b){
p=a; //將第一天入住的人數賦給p
while(a<b){ //依據觀察當入住人數>第b天，代表找到答案
p++; //每過一天增加一人
a=a+p; //每次入住的人數加上p人
}
cout<<p<<endl;
}
return 0;
}
18. 498'
題意：請記住微分公式
請你求以下多項式的值：
a0xn+a1xn-1+...+an-1x+an
而在本問題中，要請你求此多項式的導函數（ derivative）的值。上述多項式的 導函數定義如下：
a0nxn-1+a1(n-1)xn-2+...+an-1
所有的輸入及輸出都在整數的範圍內，也就是說其絕對值一定小於231。
Input
每組測試資料2列，第一列有一個整數，代表x的值。第二列則含有一連串的整數a0, a1, ..., an-1, an。代表多項式的各項次係數。（第二列的長度可能很長，但是最多不會超過1000000個字元的長度）
Output
對每組測試資料輸出一列，根據輸入x的值輸出多項式的導函數（ derivative）的值。
#include <stdlib.h>
#include <stdio.h>
int a[1000000];
int d(int x,int max){
long long sum=0,exp=1; //要記得初始化sum跟exp
int i;
for(i=max-1;i>=0;i--){ //根據題目提供的公式
sum=sum+a[i]*exp*(max-i); //由尾部n-1項開始累加sum，直到第0項
exp = exp*x;
}
return sum;
}
int main(){
int x,n; //x為要代入的值，n為a陣列的項數
while(scanf("%d",&x)!=EOF){ //輸入要代入的值，賦值給x
for(n=0;;n++){
scanf("%d",&a[n]); //輸入係數，賦值給a陣列的第n項
if(getchar()=='\n'){ //如果換行，就停止(代表已經沒有細數了)
break;
}
}
printf("%d\n",d(x,n)); //輸出 題目的x值跟係數的數量
}
return 0;
}
20.Beat the Spread!
題意：解聯立方程式(a=x+y、g=x-y)
球賽賭局，有總分和兩隊相差的分數
求出兩隊分別得幾分，高分的顯示在前
Input
N筆資料、總分、相差分
Output
高分 低分
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int l,a,g;
int x,y;
cin>>l;
while(l--){
cin>>a>>g;
x=(a+g)/2; //解聯立方程式(a=x+y、g=x-y)
y=(a-g)/2;
if(x<0||y<0||a<0||g<0||(a+g)%2!=0) //分數不可能為零、分數相加為奇數會算不出結果
cout<<"impossible"<<endl;
else
cout<<x<< " "<<y<<endl;
}
return 0;
}
22.Square Numbers
題意：
完全平方數：代表該數可以為另一個數的完全平方。
題目給予a、b兩個數字，其中0<a≤b≤100000
最後要求取得兩數之間有多少個平方數 ("不包含a數，包含b數")
#include <iostream>
using namespace std;
int main(){
int s[100001]={}; //陣列空間為a與b的最大範圍，初始化為0
int i,a,b;
for (i=1;i*i<100001;i++)
s[i*i]=1; //有平方的在陣列設置為1
for (i=1;i<100001;i++)
s[i]=s[i-1]+s[i]; //將前一陣列值累加上去
//各項之值代表包含多少個平方
while(cin>>a>>b && (a!=0&&b!=0)){ //輸入兩個0就會跳出迴圈
cout<<(s[b]-s[a-1])<<endl; //小於最小平方數，小於等於最大平方數
}
return 0;
}
23.B2-Sequence*CPE48-23
題意：
所謂「B2數列」係指一正整數數列 1<= b1 < b2 < b3 ...，其中所有的 bi + bj （i <= j）皆不相等。
您的任務是判別某一數列是否為「B2數列」。
每筆測試資料有兩行，第一行代表該數列有 N 個數值（2 ≤ N ≤ 100），第二行則為該數列的N個數值。每個數值 bi 皆為整數，且 bi ≤ 10000。
每筆測試資料以一行輸出，且每筆輸出資料後均需輸出一空白行。格式請參考輸出範例
#include <iostream>
using namespace std;
int main(){
int b[1005]={0},t=0,i,j; //b陣列存放數列的每個數值，t為case的編號
int n,bl=0; //n為數列有多少個數值，bl預設為0代表是B2，被改為1時代表不是B2
while(cin>>n){ //輸入數列數值的個數
for (i=1;i<=n;i++){
cin>>b[i]; //迴圈將數值填入b陣列
if (b[i]<=b[i-1])bl=1; //若該陣列不是遞增，則不是B2，bl就改為1
}
int note[20005]={}; //note陣列存入相加的b數列值
if (bl==0){ //若bl是零的時候開始檢查
for (i=1;i<=n;i++){
for (j=i;j<=n;j++){
if (note[b[i]+b[j]]!=0)bl=1; //如果note陣列已經有該值，則不是B2，bl就改為1
note[b[i]+b[j]]=1; //將note陣列中的[b數列相加值]，改為1
}
}
}
cout<<"Case #"<<++t;
if (!bl) cout<<": It is a B2-Sequence."<<endl<<endl;
else cout<<": It is not a B2-Sequence."<<endl<<endl;
}
return 0;
}
24. Back to High School Physics
題意：
//C++
#include <iostream>
using namespace std;
int main(){
int v,t; //第t秒後的速度為v，t為秒數
while(cin>>v>>t)
cout<<2*v*t<<endl; //據公式推算，第2t秒位移為 " 2*第t秒速度*t "
return 0;
}
//C語言
#include <stdio.h>
int main(){
int v,t;
while(scanf("%d%d", &v,&t)!=EOF)
printf("%d\n",2*v*t);
return 0;
}
進位制
25.An Easy Problem!
題意：
以N為基底進位的數字R，已知R為(N-1)的倍數，求N最小值。
2<=N<=62，N的字母依序為0-9,A-Z,a-z。
解法：
將輸入的字串轉換為數值(2~62)
比較該字串中數值最大的數，以此為最小起測值
計算n進位中，num的真實數值對(n-1)的餘數rsd
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
string b="0123456789" //宣告 b 紀錄進位字母
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
string num; //宣告 num 為測資輸入的內容
while (cin>>num){
for (int i = 0; i < num.size() ; i++){ //檢測長度，將字元替換為0-61
num[i]=b.find(num[i]);
num[i]=max(0,(int)num[i]);
}
int n = *max_element(num.begin(),num.end())+1; //將num中最大字元+1作為最小起測n值
n = max(2,n);
for (;n<=62;n++){
int rsd = 0;
for (int k=0;k<num.size();k++){ //計算n進位中，num的真實數值對(n-1)的餘數rsd
rsd = rsd*n+num[k];
rsd = rsd%(n-1);
}
if(rsd==0) //若餘數為0則找到答案
break;
}
if (n<=62)
cout<<n<<endl;
else
cout<<"such number is impossible!"<<endl;
}
return 0;
}
26.Fibonaccimal
題意：將數字用費式進位法表示
f(x)=f(x-1)+f(x-2)
ex.
6=5+1 = 1001(fib)
6=3+2+1 = 111(fib)
且題目要求不可以使用連續1來表示
解題步驟:
建立費式數列
讀取測資組數
讀取正整數
用布林preone來檢查是否有1
遞減輸出
#include <iostream>
using namespace std;
int main(){
int f[40]={0,1}; //建立費式數列
for (int x=2;x<40;x++)
f[x] = f[x-1] + f[x-2];
int n,m;cin>>n; //宣告並讀取測資組數
while(n--){
cin>>m;cout<<m<<" = "; //讀取正整數
bool preone = false; //使用布林檢查"1"
for (int k=39;k>=2;k--){
if(m>=f[k]){ //如果m>=費式數列
cout<<"1"; //則輸出 1
m = m-f[k]; //m扣除f[k]再繼續
preone = true; //若m小於該費式數
}else if(preone) //則進去else if 有輸出過 1 才可輸出 0
cout<<"0";
}
cout<<" (fib)"<<endl;
}
return 0;
}
27.Funny Encryption Method
題意：
算該數字的二進位有幾個1
再分別算該數字裡每個位數的二進位有幾個1
ex、
M=63 ，二進位 = 111111 共6個
6的二進位110，3的二進位11 共4個
#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
while(n--){
int b1=0,b2=0;
int m;cin>>m;
for(int v=m;v;v=v/2) //將m的值賦給v，v每迴圈一次除以2
b1=v%2+b1; //除以2若餘1就加在b1上
for(int w=m;w;w=w/10){ //將m的值賦給w，w每迴圈一次除以10
for(int v=w%10;v;v=v/2) //將除以10的餘數賦給v，v每迴圈一次除以2
b2=v%2+b2; //除以2若餘1就加在b1上
}
cout<<b1<<" "<<b2<<endl;
}
return 0;
}
28.Parity
題意：
給定一個十進位整數，並將其轉換為二進位表示法
求二進位表示法中出現1的次數
#include <iostream>
#include <stack> //宣告 推疊 st
using namespace std;
stack <int> st;
int main(){
int a;
while(cin>>a && a!=0){ //輸入一組測試資料
int pp=0; //宣告 計算1數量的變數
while(a!=0){
pp = a%2 + pp;
st.push(a%2); //將a%2放在st的頂部
a = a/2;
}
cout<<"The parity of ";
while(st.size()){ //長度不等於0就執行
cout<<st.top(); //輸出st最上層的內容
st.pop(); //刪除st最上層的內容
}
cout<<" is "<<pp<<" (mod 2)."<<endl;
}
return 0;
}
29.Cheapest Base
題意： 當我們想要把一些字印在紙上時，我們需要墨水。但不是每個字都需要相同的墨水，例如'W'，'M'，'8'要比'i'，'c'，'1'來的貴。這個問題主要是討論在不同進位制下需要的不同花費。
數字可以被表示成不同的進位制，當我們把數字表示成n進位時（2 <= n <= 36），我們需要用到字串'0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'的前 n 項。
每個字元都有他獨特的價錢，以一個1~128的整數表示，對於每一個數字，他被印出的價錢是組成他的數字被印出的價錢和。現在給你一個數字，請計算他用哪些進位輸出最省錢。（註：輸出的數最左方不會有沒有意義的 0）
解題步驟:
分別求出x以三十六進位制表示所需要的價錢，並將其存在陣列中
從陣列中找出最小價格
從陣列中找出最小價格對應的進位制
#include <iostream>
const int MXBASE=36; //使用限定符 設置變數
using namespace std;
int main(){
int m;
cin>>m; //輸入測資組數
for (int k=1;k<=m;k++){
if (k>1) //在每組開頭前先印一個空白列
cout<<endl;
cout<<"Case "<<k<<":"<<endl;
int coc[MXBASE];
for (int i=0;i<MXBASE;i++) //讀入價格對應表至coc陣列
cin>>coc[i];
int n;
cin>>n; //輸入該組測資個數
while(n--){
int x;
cin>>x;
int cob[MXBASE+1]; //cob陣列填寫二至三十六進位制所花費價格
for (int i=2;i<=MXBASE;i++){
int t =x; //將x值賦給t，以防x被改變
cob[i]=0;
do{
cob[i]= cob[i]+coc[t%i]; //每分解出一位數，就查詢此位數的價格
t = t/i; //加總至cob[i]
}while(t!=0);
}
int min=cob[2]; //找最小值
for (int i=3;i<=MXBASE;i++){ //跟其他元素比較，更新最小值
if (cob[i]<min) min=cob[i];
}
cout<<"Cheapest base(s) "
"for number "<<x<<":";
for (int i=2;i<=MXBASE;i++){ //再跑一次陣列找出最小值的進位制
if (cob[i]==min) cout<<" "<<i;
}
cout<<endl;
}
}
return 0;
}
30.Hartals
題意：
考慮有三個政黨的情況，假設 h1 = 3, h2 = 4, h3 = 8，其中 hi 為政黨 i(i=1, 2, 3)的“罷會參數”，接下來我們摸擬這三個政黨在N=14天內的罷會行為，模擬的情況總是設定第一天為星期日，並且每週的例假日(星期五與星期六)不會有罷會的情況。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| Days | ||||||||||||||
| Su | Mo | Tu | We | Th | Fr | Sa | Su | Mo | Tu | We | Th | Fr | Sa | |
| Party 1 | x | x | x | x | ||||||||||
| Party 2 | x | x | x | |||||||||||
| Party 3 | x | |||||||||||||
| Hartals | 1 | 2 | 3 | 4 | 5 |
上述的模擬結果顯示14天內將罷會5天(第3, 4, 8, 9, 12日)，而第6天沒有罷會是因為該天是例假日星期五，因此可看出兩週的議程已去掉了5天。
本問題會給定各個黨政的“罷會參數”與總議程的天數N，你的任務是算出在N天內共有多少個工作天因為各政黨的罷會而導致議程延岩。
input
輸入的第一列為一個用來表示有幾組測試資料的整數T。
每組測試資料的第一列為整數N ，用來表示所模擬議程的天數。下一列為另一個整數P 表示共有P個政黨，接下來的P列分別為各政黨的“罷會參數”(絕不會為7的倍數)。
output
輸出的每一列表示每一組測試資料所模擬出來的罷會天數(損失多少個工作天)。
#include <iostream>
using namespace std;
int main(){
int h[100],a,b,c; //h[i]表示第i個政黨的週期，a為測資組數
cin>>a; //b為總天數，c為政黨數量
while (a--){
int day[3651]={}; //day陣列用來存放該天是否有政黨罷工，初始為0，有罷工就改為1
cin>>b>>c;
for (int i=0;i<c;i++){ //迴圈政黨的數量，放入h陣列中，賦值為罷工週期
cin>>h[i];
for (int j=h[i];j<=b;j=j+h[i]) //迴圈該政黨的罷工日期來累加，每次迴圈都將該日的day值改為1
day[j]=1;
}
int count=0; //count用來計算罷工日數
for (int j=1;j<=b;j++){ //從第一天算到總天數
if (j%7==6 || j%7==0) continue ; //遇到假日，跳回迴圈的開頭執行下一項
if (day[j]==1) //若該day值為1，則count+1
count++;
}
cout<<count<<endl;
}
return 0;
}
31.All You Need Is Love
題意：
輸入的第一列有一個整數N（N<10000），代表以下有幾組測試資料。每組測試資料2列，代表S1和S2字串，其長度都不會超過30個字元。你可以假設所有的字串都是合法的。
output
Pair #p: All you need is love!
Pair #p: Love is not all you need!
在這裡p代表這是第幾組測試資料。如果S1和S2至少可以找到一個合法的L，使得S1和S2都可以用Love做成，則輸出第一種訊息。否則，請輸出第二種訊息。
解題概念：
轉換成10進位
算出最大公因數
輸出最大公因數>1的結果
#include <iostream>
using namespace std;
int strtoint(char s[31]){ //二進位轉十進位
int ans=0;
for (int i=0;i<30;i++){
if (s[i]=='\0')break; //二進位開頭不能為0
ans=ans*2; //每進位一次 *2
if (s[i]=='1')ans=ans+1; //遇到1就加1
}
return ans; //回傳十進位的值
}
int gcd(int x,int y){ //算兩數字(int)最大公因數
while(x=x%y)swap(x,y); //輾轉相除法
return y;
}
int main(){
int a,t=0; //a為測資的組數，t為#編號
char b[31],c[31]; //測資的兩個二進位數字
cin>>a;
while(a--){
cin>>b>>c;
int b2 = strtoint(b); //將二進位數字轉換為十進位，且轉為int
int c2 = strtoint(c);
if (gcd(b2,c2)>1) //將兩個十進位(int)代入輾轉相除法，且不能=1(二進位表示法的的限制條件)
cout<<"Pair #"<<++t<<": All you need is love!\n";
else
cout<<"Pair #"<<++t<<": Love is not all you need!\n";
}
return 0;
}
留言列表
NAS (1)