Zerojudge 第三屆簡單的小競賽題解

簽到 (Zerojudge_f026不公開)

題目：輸出 $2021!!!$

解法：輸出。

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    cout << "2021!!!\n";
}

規則說明 (Zerojudge_f027不公開)

題目：輸入帳密，輸出帳密。

解法：輸出帳密。

#include <iostream>
using namespace std;
int main() {
    string str;
    cin >> str;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '+')
            cout << '\n';
        else
            cout << str[i];
    }
    cout << "\nLog in\n";
}

1. 位數 (Zerojudge_f356練習題)

題目：輸出數字長度。

解法：使用字串。

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    string str;
    while (cin >> str)
        cout << str.length() << '\n';
}

2. Say HELLO! (Zerojudge_e412練習題)

題目：輸出 $\text{HELLO,} +$ 字串。

解法：要讀取整行。

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    string str;
    while (getline (cin, str))
        cout << "HELLO," << str << '\n';
}

3. Shady的複製品 (Zerojudge_f360)

題目：輸入 $n$，輸出 $n-1$。

解法：大數。

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    string str;
    while (cin >> str) {
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str[i] == '0')
                str[i] = '9';
            else {
                str[i]--;
                break;
            }
        }
        if (str[0] == '0')
            cout << str.substr (1, str.length() - 1) << '\n';
        else
            cout << str << '\n';
    }
}

4.階乘 (Zerojudge_f357練習題)

題目：輸入 $n$，輸出 $n!$ 的位數。

解法：將 $log(1)+log(2)+log(3)+...+log(n)$ 再加 $1$ 取整數。($log$ 以 $10$ 為底)

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int n;
    while (cin >> n) {
        double ans = 0;
        for (int i = 1; i <= n; i++)
            ans += log10 (i);
        cout << (int) ans + 1 << '\n';
    }
}

5. 貝瑞的鐵線體積 (Zerojudge_f332)

題目：輸入多項式函數 $f(x)$ 的各項係數，輸入邊界 $a,b$，求函數繞 $x$ 軸的體積。

解法：將每一個點對應的面積加起來 $πr^2=πf(x)^2$，然後 $a$ 到 $b：∫πf(x)^2dx$，不用考慮正負，因為平方出來為正。(原本有一題算面積，但是精準度不夠高，沒有人解出來，所以我就刪了)

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const double pi = acos (-1);
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int ar[n + 1];
        for (int i = n; i >= 0; i--)
            cin >> ar[i];
        double arr[2 * n + 1] = {0};
        for (int i = n; i >= 0; i--)
            for (int j = n; j >= 0; j--)
                arr[i + j] += ar[i] * ar[j];
        for (int i = 2 * n; i >= 0; i--)
            arr[i] /= (i + 1);
        double a, b, suma = 0, sumb = 0;
        cin >> a >> b;
        for (int i = 2 * n; i >= 0; i--)
            suma = suma * a + arr[i];
        suma *= a;
        for (int i = 2 * n; i >= 0; i--)
            sumb = sumb * b + arr[i];
        sumb *= b;
        cout << fixed << setprecision (2) << pi* (sumb - suma) << '\n';
    }
}

6. 彼得的誤差率 (Zerojudge_f362)

題目：誤差率定義為 $| ( x -n ) / x |$，$x$ 為正確答案，$n$ 為算出來的答案，給你 $n$，求 $| ( x -n ) / x |=x$的解。

解法：將原式化成兩個一元二次方程式，求根，然後去掉小於等於 $0$ 的。

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
double rou (double n) {
    n *= 100;
    if (n - (int) n < 0.5)
        return double ( (int) n) / 100;
    return double ( (int) n + 1) / 100;
}
int main() {
    double n;
    while (cin >> n) {
        vector<double>ans;
        if (1 + 4 * n >= 0) {
            double num = rou ( (-1 + sqrt (1 + 4 * n)) / 2);
            if (num > 0)
                ans.push_back (num);
            num = rou ( (-1 - sqrt (1 + 4 * n)) / 2);
            if (num > 0) {
                bool is = 0;
                for (int i = 0; i < ans.size(); i++)
                    if (num == ans[i]) {
                        is = 1;
                        break;
                    }
                if (is == 0)
                    ans.push_back (num);
            }
        }
        if (1 - 4 * n >= 0) {
            double num = rou ( (1 + sqrt (1 - 4 * n)) / 2);
            if (num > 0) {
                bool is = 0;
                for (int i = 0; i < ans.size(); i++)
                    if (num == ans[i]) {
                        is = 1;
                        break;
                    }
                if (is == 0)
                    ans.push_back (num);
            }
            num = rou ( (1 - sqrt (1 - 4 * n)) / 2);
            if (num > 0) {
                bool is = 0;
                for (int i = 0; i < ans.size(); i++)
                    if (num == ans[i]) {
                        is = 1;
                        break;
                    }
                if (is == 0)
                    ans.push_back (num);
            }
        }
        sort (ans.begin(), ans.end());
        if (ans.size() == 0)
            cout << "NULL\n";
        else {
            for (int i = 0; i < ans.size(); i++)
                cout << fixed << setprecision (2) << ans[i] << ' ';
            cout << '\n';
        }
    }
}

中場休息 (Zerojudge_f029不公開)

題目：輸入 $n$，輸出 $0\times n$。

解法：輸出。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++)
        cout << i << ' ';
}

7. 家豪的回家作業 (Zerojudge_f368)

題目：輸入字串，輸出 $1/2^{\text{RED} 跟 \text{GREEN} 的個數}$。

解法：大數。

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
const int mod = 1000000000;
vector<int>vec;
void mult() {
    int num = 0;
    for (int i = 0; i < vec.size(); i++)
        vec[i] = vec[i] * 2 + num, num = vec[i] / mod, vec[i] %= mod;
    if (num)
        vec.push_back (num);
}
void out() {
    cout << vec[vec.size() - 1];
    for (int i = vec.size() - 2; i >= 0; i--)
        cout << setfill ('0') << setw (9) << vec[i];
    cout << '\n';
}
int main() {
    string str;
    while (cin >> str) {
        vec.clear();
        int sum = 0;
        string s3 = "   ", s5 = "     ";
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < 2; j++)
                s3[j] = s3[j + 1];
            for (int j = 0; j < 4; j++)
                s5[j] = s5[j + 1];
            s3[2] = s5[4] = str[i];
            if (s3 == "RED")
                sum++;
            if (s5 == "GREEN")
                sum++;
        }
        cout << "1/";
        vec.push_back (1);
        for (int i = 0; i < sum; i++)
            mult();
        out();
    }
}

8. 階乘位數 (Zerojudge_f358練習題)

題目：輸入 $n$，求 $n!\times (n-1)!\times ...\times 1!$ 的位數。

解法：將 $(n-i+1)\times log(i)$ 加起來，最後加一。

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        double sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += (n - i + 1) * log10 (i);
        }
        cout << (long long) sum + 1 << '\n';
    }
}

9. Morty的函數 (Zerojudge_f369)

題目：輸入 $n$ 次函數 $f(x)$ 的 $n+1$ 個值，輸出 $f(k)/100$。

解法：拉格朗日插值法。

#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        long long x[n + 1], y[n + 1], k;
        double ans = 0;
        for (int i = 0; i <= n; i++)
            cin >> x[i];
        for (int i = 0; i <= n; i++)
            cin >> y[i];
        cin >> k;
        for (int i = 0; i <= n; i++) {
            long long up = y[i], down = 1;
            for (int j = 0; j <= n; j++)
                if (i != j)
                    up *= k - x[j], down *= x[i] - x[j];
            ans += (double) up / down;
        }
        cout << (long long) ans / 100 << '\n';
    }
}

10. Caido的彈性碰撞 (Zerojudge_f361)

題目：兩顆球的質量、碰撞前的角度、速度，求碰撞後的角度、速度。

解法：彈性碰撞，動量守恆、力學能守恆，在二維可以拆成水平跟垂直分量，最後再加起來。

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
#include <iomanip>
#define LD long double
using namespace std;

const LD pi = acos (-1);

void solve() {
    LD m1, v1, o1, m2, v2, o2;
    cin >> m1 >> v1 >> o1 >> m2 >> v2 >> o2;
    o1 = o1 * pi / 180, o2 = o2 * pi / 180;
    LD v1s, v1l, v2s, v2l, V1s, V1l, V2s, V2l;
    v1s = v1 * sin (o1), v1l = v1 * cos (o1);
    v2s = v2 * sin (o2), v2l = v2 * cos (o2);
    V1s = (v1s * (m1 - m2) + 2 * m2 * v2s) / (m1 + m2);
    V1l = (v1l * (m1 - m2) + 2 * m2 * v2l) / (m1 + m2);
    V2s = (v2s * (m2 - m1) + 2 * m1 * v1s) / (m1 + m2);
    V2l = (v2l * (m2 - m1) + 2 * m1 * v1l) / (m1 + m2);
    v1 = sqrt (V1s * V1s + V1l * V1l), o1 = atan2 (V1s, V1l) * 180 / pi;
    v2 = sqrt (V2s * V2s + V2l * V2l), o2 = atan2 (V2s, V2l) * 180 / pi;
    if (o1 < -1e-5)
        o1 += 360;
    else if (-1e-5 < o1 && o1 < 1e-5)
        o1 = 0;
    if (o2 < -1e-5)
        o2 += 360;
    else if (-1e-5 < o1 && o1 < 1e-5)
        o2 = 0;
    cout << fixed << setprecision (2) << v1 << ' ' << o1 << ' ' << v2 << ' ' << o2 << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int t;
    cin >> t;
    while (t--)
        solve();
}

11. 肯尼的階乘位數 (Zerojudge_f145)

題目：輸入 $n$，$f(n)=n!\times (n-1)!\times ...\times 1!$，求 $f(n)\times f(n-1)\times ...\times f(1)$ 的位數。

解法：將 $(n-i+1)\times (n-i+2)/2\times log(i)$ 加起來，最後加一。

#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        double sum = 0;
        for (long long i = 1; i <= n; i++)
            sum += (n - i + 1) * (n - i + 2) / 2 * log10 (i);
        cout << (long long) sum + 1 << '\n';
    }
}

離場 (Zerojudge_f033不公開)

題目：現在參加第 $n$ 年的跨年晚會，輸出今年是平年還是閏年。

解法：很多人都被騙到了，現在是 $n-1$ 年才要去參加 $n$ 年的跨年晚會。

#include <iostream>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        n--;
        if (n % 400 == 0 || (n % 100 != 0 && n % 4 == 0))
            cout << "leap\n";
        else
            cout << "pin\n";
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！