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;

    }

}