2017 google code jam 資格賽

這是我第三次參加GCJ,比起前兩次進步超多的> <,寫出了完整三題,最終排名在三千左右,雖然資格賽排名沒甚麼用,但我還是心裡暗爽了一下XD


以下,就由小弟來分享一下解題心得吧


先附上題目連結: https://code.google.com/codejam/contest/3264486/dashboard


一. 翻餅問題: 這題算是考古題吧! 蠻有名的題目,不過有簡化過,以前的題目翻餅數不固定,不過這次翻餅數固定,可以用貪心法求解,解題思路如下,因為翻的順序不影響餅的狀態,所以可以先從最左邊開始考慮,若最左邊為unhappy,則從最左邊開始翻,並更新從最左邊開始K塊餅的狀態,之後,若遇到happy則跳過,unhappy則連翻K塊餅,最後在確認邊界,即可得知答案,這樣算是比較粗略的作法,複雜度為O(n*k),還有更快的作法,稱為尺取法,不過這題不需要,有需要請自行google

code如下:

#include<cstdio>
#include<iostream>
#include<string>
#pragma warning(disable : 4996)
using namespace std;

int main(void)
{
    freopen("C:\\Users\\user\\Desktop\\input.in", "r", stdin);
    freopen("C:\\Users\\user\\Desktop\\output.txt", "w", stdout);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {

        string s;
        cin >> s;
        int k;
        cin >> k;
        int ans = 0;
        int len = s.length();

        //cout<<s<<" "<<k<<" "<<len<<endl;
        for (int j = 0; j < len; j++)
        {
            //cout << s << endl;
            if (j + k >len)
            {
                for (int g = j; g < len; g++)
                {
                    if (s[g] != '+')
                    {
                        ans = -1;
                        break;
                    }
                }
            }
            else
            {
                if (s[j] == '+')
                    continue;
                else
                {
                    for (int g = j; g < j + k; g++)
                    {
                        if (s[g] == '-')
                            s[g] = '+';
                        else
                            s[g] = '-';
                    }
                    ans++;
                }
            }
            if (ans < 0)
                break;
        }
        if (ans != -1)
            cout << "Case #" << i + 1 << ": " << ans << endl;
        else
            cout << "Case #" << i + 1 << ": " << "IMPOSSIBLE" << endl;
    }

二. 小數問題: 這題其實算是簡單的數學題吧,解題技巧就是找到第一個比下一個數字還小的數,若這個數字和之前相同,則回推到第一個相同的數字,再將其減一,之後都加九,直到底為止,如此即為答案,複雜度為O(n)


ex. 13322, 其答案為12999, 可由上述演算法得知
ps. 若減一後發現為零,需捨去零.要特別注意

code如下:

#include<bits/stdc++.h>

using namespace std;

int main(void)
{
    freopen("C:\\Users\\user\\Desktop\\input.in","r",stdin);
freopen("C:\\Users\\user\\Desktop\\output.txt","w",stdout);
    int t;
    cin>>t;

    for(int i=1;i<=t;i++)
    {
        int ok=1;
        string s;
        cin>>s;
        //cout<<s<<endl;
        string ans="";
        int len=s.length();
        int same=0;;
        for(int i=0;i<len-1;i++)
        {

            if(s[i]>s[i+1])
            {
                for(int j=0;j<same;j++)
                ans=ans+s[j];
                char c=s[same]-1;
                if(same!=0||c!='0')
                ans=ans+c;
                for(int j=same+1;j<len;j++)
                ans=ans+'9';
                ok=0;
                break;
            }
        if(s[i]!=s[i+1])
            same=i+1;

        }
        if(ok)
            ans=s;
        cout<<"case #"<<i<<": "<<ans<<endl;
    }

}

三. 廁所問題:這題算是數論題,有O($log$ $n$) 的解法,公式有些複雜,不過最終答案可由n,k組成的公式決定,讀者慢慢推應可發現和$\lfloor\log _2 n\rfloor$有關,可以用狀態樹來分析,比如說如果n=6,那狀態樹就會6分成3和2,剩下繼續分,一直分到零為止,而由大到小第k個節點的值即為第k次分的點,接下來就可求解答案!

#include<bits/stdc++.h>

using namespace std;

long long logtwo(long long q)
{
    long long a=1;
    long long r=0;
    while(a<=q)
    {
        r++;
        a=a*2;
    }
    return a/2;
}

int main(void)
{
   freopen("C:\\Users\\user\\Desktop\\input.in","r",stdin);
   freopen("C:\\Users\\user\\Desktop\\output.txt","w",stdout);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        long long n,k;
        cin>>n>>k;
        //cout<<n<<" "<<k<<endl;
        long long exp=logtwo(k);
        //cout<<exp<<endl;
        long long temp=(n+1-exp)/exp;
        if((n+1-exp-exp*(temp))>=k+1-exp)
            temp++;
        cout<<"Case #"<<i<<": "<<temp/2<<" "<<(temp-1)/2<<endl;
    }
}

四. 筆者也不會,還在努力研究中