2013 校慶盃乙組參考解答
******************* 第 1 題 *******************
//113 - Power of Cryptography (by Snail)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
double n, p;
while (cin >> n >> p)
cout << int(pow(p,1/n)+.5) << endl;
}
******************* 第 2 題 *******************
//155 - All Squares (by Snail)
#include <iostream>
#include <iomanip>
#include <cstdlib> //for abs(int)
using namespace std;
int main () {
int k, x, y, x1, y1, ns;
while (cin >> k >> x >> y, k) {
ns = 0; //no of s(quare)--正方形數
x1 = y1 = 1024; //中心點
while (k) {
if (abs(x-x1)<=k && abs(y-y1)<=k) //在正方形內
ns++;
x1 += k * ((x >= x1) - (x < x1)); //(x1,y1) 移到最接近的角
y1 += k * ((y >= y1) - (y < y1));
k /= 2; //縮小正方形
}
cout << setw(3) << ns << endl;
}
}
******************* 第 3 題 *******************
//10026 - Shoemaker's Problem (by Snail)
#include <iostream>
#include <algorithm>
using namespace std;
struct job { //i(ndex)--工作編號
int i, t, s; //t(ime)--工作天數
} j[1001]; //s (fine)--罰金
bool gt (job a, job b) { return a.s * b.t > b.s * a.t; }
//罰得較重 (s/t較大) 的先做，交叉相乘
int main () {
int tc, n, i;
cin >> tc;
while (tc--) {
cin >> n;
for (i=1; i<=n; i++) {
j[i].i = i;
cin >> j[i].t >> j[i].s;
}
stable_sort (j+1, j+1+n, gt); //穩定排序
for (i=1; i<n; i++)
cout << j[i].i << ' ';
cout << j[n].i << endl; //最後一筆後面沒有空白
if (tc) cout << endl; //測試資料間空一行
}
}
******************* 第 4 題 *******************
//10048 - Audiophobia (by Snail)
#include <iostream>
#include <climits>
using namespace std;
int main() {
int d[101][101], c, s, q, i, k, c1, c2, tc=0;
while (cin >> c >> s >> q, c) {
if (tc++) cout << endl;
cout << "Case #" << tc << endl;
for (c1=1; c1<=c; c1++) //歸零
for (c2=1; c2<=c; c2++)
d[c1][c2] = INT_MAX;
for (i=1; i<=s; i++) {
cin >> c1 >> c2; //輸入街道起訖點
cin >> d[c1][c2]; //輸入街道噪音值
d[c2][c1] = d[c1][c2]; //無向圖
}
for (k=1; k<=c; k++) //Floyd-Warshall
for (c1=1; c1<=c; c1++)
for (c2=1; c2<=c; c2++)
d[c1][c2] = min(d[c1][c2], max(d[c1][k], d[k][c2]));
for (i=1; i<=q; i++) {
cin >> c1 >> c2;
if (d[c1][c2] == INT_MAX)
cout << "no path\n";
else
cout << d[c1][c2] << endl;
}
}
}
******************* 第 5 題 *******************
//166 - Making Change (by Snail)
#include <iostream>
#include <iomanip>
using namespace std;
int main () {
int i, j, d, c, a, p[6], nc[201]={};
int f[6]={5, 10, 20, 50, 100, 200}; //f(ace value)--面額
char ch;
for (i=1; i<=200; i++) //no of coins of change
nc[i] = 9999; //nc[i]--店家找 i 分時最少要幾個硬幣
for (i=0; i<6; i++)
for (j=f[i]; j<=200; j++) //硬幣面額最大 $2, 找零不可能大於 $2
nc[j] = min (nc[j], nc[j-f[i]]+1);
while (cin >> p[0] >> p[1] >> p[2] >> p[3] >> p[4] >> p[5], p[0]+p[1]+p[2]+p[3]+p[4]+p[5]) {
int mnc=9999, np[701]={}; //no of coins of payment
cin >> d >> ch >> c; //d(ollar), c(ent)
a = d*100 + c; //a(mount)--金額
for (i=a+200; i; i--) //no of coins of payment
np[i] = 9999; //np[i]--顧客付 i 分時最少要幾個硬幣
for (i=0; i<6; i++) //面額
while (p[i]--) //硬幣數量
for (j=a+200; j>=f[i]; j--) //每個硬幣用一次, 倒著 DP
np[j] = min (np[j], np[j-f[i]]+1);
for (i=0; i<200; i++) //溢付金額不超過 $2
mnc = min (mnc, nc[i]+np[a+i]);
cout << setw(3) << mnc << endl;
}
}
******************* 第 6 題 *******************
//111 - History Grading (by Snail)
#include <iostream>
using namespace std;
int main () {
int n, i, j, x, c[21], r[21], a[21][21]={};
cin >> n;
for (i=1; i<=n; i++)
cin >> x, c[x] = i; //轉成事件順序
while (cin >> x) {
r[x] = 1;
for (i=2; i<=n; i++)
cin >> x, r[x] = i; //轉成事件順序
for (i=1; i<=n; i++) //LCS
for (j=1; j<=n; j++)
if (c[i]==r[j])
a[i][j] = a[i-1][j-1] + 1;
else
a[i][j] = max (a[i][j-1], a[i-1][j]);
cout << a[n][n] << endl;
}
}