ZeroJudge April Fools Contest 2020 解題心得

這次比賽真的蠻有 April Fools 的味道

不過在 ZeroJudge 平台應該是新手居多，可能會有點適應不良，或者不知從何下手

有些題目也要一些 CTF 的基礎才可能通靈解開來

這次就來一次看清楚吧！

不負責聲明：本人不是出題者，我只是寫我的解題心得而已，要官方題解請找出題者

競賽連結 Contest

競賽連結：https://zerojudge.tw/ShowContest?contestid=3282

本人 Rank 2/125
之前在 TIOJ 打 April Fools 也是拿很前面的名次
正常競賽不會打，只會打 April Fools = =

———————————暴雷分隔線，害怕請避難————————————

題目 Problems

pA - Hello, April Fools Day 2020

題目連結：https://zerojudge.tw/ShowProblem?problemid=e959

進來雖然看懂題目了，也寫好了，可是……「送出解答」按鈕呢？

在那裡附近右鍵打開檢查

找到送出「解答按鈕」的元素，你會發現按紐被 display: none; 了

雙擊編輯把 display: none; 去除

送出吧！

print('Hello, April Fools Day 2020')

pB - 顛倒

題目連結：https://zerojudge.tw/ShowProblem?problemid=e960

整個敘述都顛倒好難看……

一秒破解，把敘述複製到無格式記事本

好，你看懂題目，也打出來了，可是送出去之後

我的聚焦會在 TLE，理當來說 $T\times N = 100\times 1000$，是不應該會 TLE 的

於是我就先寫其他題目了

但我後來回去再看一次標題「顛倒」

就在想，會不會輸入也要顛倒…

果然，輸入倒回去看也是正確的，只不過輸出也要顛倒輸出

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/4/1
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)

/********** Good Luck :) **********/
int main()
{
    IOS();
    ll w;
    int i = 0;
    ll enter[1000005];
    while(cin >> w){
        enter[i++] = w;
    }
    ll ans[10000];
    int j = 0;
    ll t;
    t = enter[--i];
    while(t--){
        ll n;
        n = enter[--i];
        ll total = 0;
        while(n--){
            ll tp;
            tp = enter[--i];
            total += tp;
        }
        ans[j++] = total;
    }
    while(j){
        cout << ans[--j] << '\n';
    }
    return 0;
}

pC - 解題技巧

題目連結：https://zerojudge.tw/ShowProblem?problemid=e961

題目說參與「某種活動」有機會秒殺這題

再加上輸入有數字 0-9、/和X

就想到這題是保齡球分數計算，再稍微驗證一下輸入有 $11 \sim 21$ 字元，應該準沒錯

然後找了 UVa 584 的 Code（對，我懶得重寫）

稍微改了一下，但還是 WA，不過分數多了一些

隔一段時間回來後，因為測資有誤，Rejudge 後，也直接 AC 了

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
    int t;
    cin >> t;
    string line;
    cin.ignore();
    while (t-- && getline(cin, line)) {
        if (line == "Game Over")
            break;
        stringstream sin(line);
        vector<pair<int, int> > frame;
        int n = 0, i;
        for (i = 0; i < line.length(); i++) {
            if (line[i] != ' ') {
                line[n++] = line[i];
            }
        }
        int score = 0;
        for (i = 0; i < n; i++) {
            if (line[i] == 'X') {
                frame.push_back(make_pair(10, 0));
            } else {
                if (line[i + 1] == '/')
                    frame.push_back(make_pair(line[i] - '0', 10 - (line[i] - '0')));
                else
                    frame.push_back(make_pair(line[i] - '0', line[i + 1] - '0'));
                i++;
            }
        }
        for (i = 0; i < 10; i++) {
            if (frame[i].first + frame[i].second != 10)
                score += frame[i].first + frame[i].second;
            else if (frame[i].first == 10) {
                if (frame[i + 1].first == 10)
                    score += 10 + 10 + frame[i + 2].first;
                else
                    score += 10 + frame[i + 1].first + frame[i + 1].second;
            } else {
                score += 10 + frame[i + 1].first;
            }
        }
        printf("%d\n", score);
    }
    return 0;
}

pD - 灰階

題目連結：https://zerojudge.tw/ShowProblem?problemid=e962

通靈解題失敗，等作者發題解，我覺得那公式應該是唬爛的

但我發現 Reddit 竟然找得到…

2020.04.04 更新

參考 inversion 大大的通靈的心路歷程: https://zerojudge.tw/ShowThread?postid=21040&reply=0

雖然我有看到這段話

小歐:「24bit… 就像全彩RGB那樣… ?」
小草:「你要那樣說也不是不行啦~~~」

也一度懷疑那字串不是 RGB，但那時候也不以為意（實際上就不是 RGB）

不過用 Gray Code（格雷碼）諧音梗來誤導 RGB 也太傳神w

但其實我也有發現範例輸入 #a0a0a0 顏色本身就是灰色，為何要硬轉成 #f0f0f0

只能說我的通靈之路還得加強w

本題就直接把 Hexadecimal 轉成 Binary

然後再依照這部影片的教學轉成 Gray Code（格雷碼）

再從 Binary 轉成 Hexadecimal 輸出即可 AC

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/4/4
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define ALL(_a) _a.begin(),_a.end()
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)

string decToBin(int s){
    string re;
    REP(i, 4){
        if(s % 2){
            re += '1';
        }
        else{
            re += '0';
        }
        s /= 2;
    }
    reverse(ALL(re));
    return re;
}

string hexToBin(char s){
    int ans = 0;
    if (isdigit(s)){
        ans = s - '0';
    }
    else {
        ans = s - 'a' + 10;
    }
    return decToBin(ans);
}

char decToHex(int s) {
    if (s < 10) {
        return s + '0';
    }
    else {
        return s - 10 + 'a';
    }
}

char binToHex(string s){
    int total = 0;
    int now = 8, i = 0;
    while (now) {
        if (s[i] == '1') {
            total += now;
        }
        i++;
        now /= 2;
    }
    return decToHex(total);
}

/********** Good Luck :) **********/
int main()
{
    IOS();
    int n;
    cin >> n;
    while(n--){
        string enter;
        cin >> enter;
        string a;
        REP(i, 6){
            a += hexToBin(enter[i]);
        }
        bitset<24> bita(a), bitb(a);
        bitb >>= 1;
        bita ^= bitb;
        string bins = bita.to_string();
        string ans;
        for (int i = 0; i < 24; i += 4){
            ans += binToHex(bins.substr(i, 4));
        }
        cout << ans << '\n';
    }
    return 0;
}

pE - 餅乾盒遊戲

題目連結：https://zerojudge.tw/ShowProblem?problemid=e963

這題你會發現，你無法從題目敘述、輸入輸出判別 Yes or No

他很強調「餅乾」

還有一句話「畢竟不同的餅乾就能代表不同的人，也就是說，能夠從餅乾來判別一個人喔。」

打過 Web CTF 就會知道，不過稍微通靈想一下

「餅乾」=「Cookies」

於是就打開 ZeroJudge 的 Cookies 欄位

點進去，把 ZeroJudge 的 Cookies 展開，多了個東西叫做 pE_answer

內容蠻長的，要複製完整才有答案哦！

6IulIFNbaV0g54K6IOWtl+S4slMg56ysIGkg5YCL5a2X5YWD55qEIGFzY2lpIOaVuOWAvCAoRVg6IFM9ImJhciIg5YmHIFNbMF09OTgpCuS7pCBIKFMpID0gc3VtKFNbaV0qMTM5XmkpICjpgJnoo6HnmoRe5piv5oyH5pW46YGL566XKSAoRVg6IFM9ImJhciIg5YmHIEgoUyk9OTgrOTcqMTM5KzExNCoxMzleMj0yMjE2MTc1KQrlpoLmnpwgSChTKSUoU1swXSUzKzIpID09IDAgKOmAmeijoeeahCXmmK/lj5bppJjmlbgpIOWJh+ipsumkheS5vuaYr+WxrOaWvCLlsI/mrZAi55qE6aSF5Lm+77yM5Y+N5LmL5YmH5LiN5piv44CCCihFWDogUz0iYmFyIiwgIOWboOeCuiBIKFMpJShTWzBdJTMrMikgPSAyMjE2MTc1JTQgPSAzIOaVhSDoqbLppIXoqbLkuKbkuI3lsazmlrwi5bCP5q2QIueahOmkheS5vik=

結尾有個等於，看起來是 Base64 Encode，找個 Online Base64 Decoder 還原回去

若 S[i] 為 字串S 第 i 個字元的 ascii 數值 (EX: S="bar" 則 S[0]=98)
令 H(S) = sum(S[i]*139^i) (這裡的^是指數運算) (EX: S="bar" 則 H(S)=98+97*139+114*139^2=2216175)
如果 H(S)%(S[0]%3+2) == 0 (這裡的%是取餘數) 則該餅乾是屬於"小歐"的餅乾，反之則不是。
(EX: S="bar",  因為 H(S)%(S[0]%3+2) = 2216175%4 = 3 故 該餅該並不屬於"小歐"的餅乾)

知道題目了，來實作吧！

這題需要用到同餘定理，照題目先把要 MOD 的數字算出，再把 $H(S)$ 算出

算 $139$ 的次方，記得都要取 MOD，再去照題目要求判斷，即可 AC

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/4/1
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)

/********** Good Luck :) **********/
int main()
{
    IOS();
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        ll mod = s[0] % 3 + 2;
        ll total = 0;
        ll timee = 1;
        REP(i, SZ(s)){
            total += ((s[i] % mod) * (timee % mod)) % mod;
            timee *= 139;
            timee %= mod;
        }
        if(total % mod == 0){
            cout << "yes" << '\n';
        }
        else{
            cout << "no" << '\n';
        }
    }
    return 0;
}

pF - 前往疫區

題目連結：https://zerojudge.tw/ShowProblem?problemid=e964

這題賽中題目敘述爛掉，還原一下那時候的大意

「現在最嚴重的國家是…？美國」
「對，如果你是從美國來的，就可以拿到提示哦！」

如果你是正常連線的話，你應該只能看到這裡

於是我就用了一下 VPN 連線到美國

小歐:「咦?? 現在這個人好像就是來自 美國 的耶」
小草:「啊… 的確呢 還真是意外耶(棒讀)」
小歐:「怎麼覺得你早就知道會有人一樣… ?」
小草:「沒那回事 那是你的錯覺♪」
小歐:「所以說那個提示.. ?」
小草:「啊，差點就忘了… 提示是『${Ans=(9487945\times\displaystyle\sum_{i=0}^{b}a^i)\bmod 10^9+7}$』。」
小歐:「我是覺得這已經不是提示的程度了啦，直接講解答還能夠算是提示嗎?? 不過確實，不看提示真的猜不到呢… …」
小草:「嘛 惡趣味可不是叫假的」
小歐:「算了… 我已經放棄思考了… …」
小草:「終於看開了呀(笑)」
小歐:「所以在最後還是來做點正事吧 在此恭喜你通過所有關卡!! 🎉🎉🎉」
小草:「不過也有可能是直接跳關到這裡就是了… ?」
小歐:「雖然相見的時間不長，但也到了該謝幕的時間了。」
小草:「我倒是覺得已經很長了… …」
小歐:「就這樣，我是主持人小歐」
小草:「我其實只是路過的♪」
小歐:「欸!? 真的假的!? 總之，有緣的話明年再見吧」
小草:「說真的，究竟有多少人能看到這裡呢… …」

然後你的背景也一起 美國 了，強烈建議連線進去捧場一下

但我是覺得不一定要連 VPN 到美國，想辦法騙過 JavaScript 是從美國來的應該也可以

回到題目重點，本題重點在這裡

$$
{Ans=(9487945\times\displaystyle\sum_{i=0}^{b}a^i)\bmod 10^9+7}
$$

$\displaystyle\sum_{i=0}^{b}a^i$ 這東西 Google 了半天，才知道那是等比級數啊！高中數學都忘光了@@

用 等比級數 搭配 快速冪，改一下條件判斷就 AC 了

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/4/2
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)

const ll MOD = 1000000007LL;

ll a;

ll q_pow(ll a, ll n, ll MOD) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res % MOD;
}

ll sum(ll n) {
    if (n <= 1) return a % MOD;

    ll s = sum(n / 2) % MOD;

    if (n % 2 == 0)
        return s + s * q_pow(a, n / 2, MOD) % MOD;
    else
        return s + s * q_pow(a, n / 2, MOD) + q_pow(a, n, MOD) % MOD;
}

/********** Good Luck :) **********/
int main() {
    IOS();
    int t;
    cin >> t;
    while (t--) {
        ll b;
        cin >> a >> b;
        if (a == 0) {
            cout << "0" << '\n';
        } else if (b == 0){
            cout << "9487945" << '\n';
        } else {
            ll ans = sum(b);
            cout << (((sum(b) + 1) % MOD) * 9487945 % MOD) % MOD << '\n';
        }
    }
    return 0;
}

後記 Afterword

這場比賽性質不能直接跟正常比賽比較

畢竟是 April Fools 嘛 w

TCSH Online Judge 明年也可以來這樣搞好了

話說隔幾天就是 Google Code Jam 了，加上專題還有作業，估計繼續潛水了…

就醬子！ㄅㄅ！