2014 資訊能力競賽參考解答

***********************   第 1 題   ***********************

//10287 - Gifts in a Hexagonal Box (by Snail)

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

    double s, r1, r2, r3, r4;

    cout << fixed << setprecision(10);

    r1 = sqrt(3.) / 2;

    r2 = 2*sqrt(3.) - 3;

    r3 = sqrt(3.) / 4;

    r4 = .6*sqrt(7.) - .7*sqrt(3.);

    while (cin >> s) {

        cout << r1*s << ' ' << r2*s << ' '

             << r3*s << ' ' << r4*s << endl;

    }

}

***********************   第 2 題   ***********************

//10878 - Decode the tape (by snail)

#include <iostream>

#include <string>

using namespace std;

int main () {

    string s;

    while (getline(cin, s)) {

        while (getline(cin, s), s !="___________") {

            cout << char((s[2]=='o')*64 +

                (s[3]=='o')*32 + (s[4]=='o')*16 +

                (s[5]=='o')*8 + (s[7]=='o')*4 +

                (s[8]=='o')*2 + (s[9]=='o'));

        }

        cout << endl;

    }

}

***********************   第 3 題   ***********************

//424 - Integer Inquiry (by Snail)

#include <iostream>

#include <string>

using namespace std;

int main () {

    string n1, n2;

    cin >> n1;

    while (cin >> n2, n2 != "0") {

        if (n1.size() < n2.size())              //確定 n1 比 n2 長

            swap (n1, n2);

        n2.insert (0, n1.size()-n2.size(), '0');//把數字補成一樣長

        int c = 0;                              //c(arry)--進位

        for (int i=n1.size()-1; i>=0; i--) {    //從個位數開始算

            c += n1[i] + n2[i] - 96;

            n1[i] = c % 10 + '0';

            c /= 10;

        }

        if (c)                                  //若還有進位

            n1.insert (0, 1, '1');              //再加一位數

    }

    cout << n1 << endl;

}

***********************   第 4 題   ***********************

//10127 - Ones (by Snail)

#include <iostream>

using namespace std;

int main () {

    int n, m, c;

    while (cin >> n) {

        m = 1;

        for (c=1; m%n; c++)                     //c(ount)--計算幾位數

            m = (m * 10 + 1) % n;               //m(ultiple)--倍數

        cout << c << endl;

    }

}

***********************   第 5 題   ***********************

//10193 - All You Need Is Love (by Snail)

#include <iostream>

#include <string>

using namespace std;

int main () {

    int n, a, b, t, p=1;

    string s1, s2;

    cin >> n;

    while (n--) {

        cin >> s1 >> s2;

        a = strtol (s1.c_str(), NULL, 2);

        b = strtol (s2.c_str(), NULL, 2);

        while (b)                               //輾轉相除法

            t = a%b, a = b, b = t;

        if (a == 1)                             //互質

            cout << "Pair #" << p++ << ": Love is not all you need!\n";

        else

            cout << "Pair #" << p++ << ": All you need is love!\n";

    }

}

***********************   第 6 題   ***********************

//10325 - The Lottery (by Snail)

#include <iostream>

using namespace std;

int N, M, r[16];                                //r(andom)[i]--M 個隨機數

int cnt(long long lcm, int sgn, int i) {

    if (lcm > N) return 0;                      //避免 lcm 溢位

    if (i > M) return N / (int) lcm * sgn;      //sgn (sign)--正負號, +1 與 -1 變換

    int a = (int)lcm, b = r[i], t;

    while (b)                                   //當 b==0 時

        t = a%b, a = b, b = t;                  //a 為 lcm 與 r[i] 的最大公因數

    return cnt(lcm,         sgn, i+1) +         //偶數個 r 的 lcm 的倍數要加回來

           cnt(lcm*r[i]/a, -sgn, i+1);          //奇數個 r 的 lcm 的倍數要扣掉

}

int main() {

    while (cin >> N >> M) {

        for (int i=1; i<=M; i++)

            cin >> r[i];

        cout << cnt(1, 1, 1) << endl;

    }

}

***********************   第 7 題   ***********************

//10041 - Vito's large family (by Snail)

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

int main () {

    int t, r, i, s, ac;

    long long d;

    cin >> t;

    while (t--) {

        int c[30001] = {};                      //c(ount)[s]--s出現次數

        cin >> r;

        for (i=0; i<r; i++)

            scanf("%d",&s), c[s]++;

        ac = 0;                                 //ac(cumulation)--累積人數

        for (i=0; ac+c[i] < (r+1)/2; i++)

            ac += c[i];

        d = 0;                                  //d(istance)--總距離

        for (s=0; s<=30000; s++)

            d += abs(s - i) * c[s];

        cout << d << ' ' << i << endl;

    }

}