Submission #1140099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140099		12345678	Binary Subsequences (info1cup17_binary)	C++20	12.90 / 100	246 ms	440 KiB

binary

#include <bits/stdc++.h>

using namespace std;

int Q, k;

int solve(int a, int b)
{
    if (a==1) return b-1;
    if (b==1) return a-1;
    if (a>=b)
    {
        int mod=a%b, div=a/b;
        if (mod==0) return -1e9;
        return div+solve(mod, b);
    }
    else
    {
        int mod=b%a, div=b/a;
        if (mod==0) return -1e9;
        return div+solve(a, mod);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>Q;
    while (Q--)
    {
        cin>>k;
        k+=2;
        int cnt=0;
        pair<int, int> ans={1e9, 0}; 
        for (int a=1; a<k-a; a++)
        {
            //cout<<"debug "<<a<<' '<<k-a<<' '<<solve(a, k-a)<<'\n';
            int tmp=solve(a, k-a);
            if (tmp>=0) cnt++, ans=min(ans, {tmp, a});
        }
        cout<<2*cnt<<'\n'<<-1<<'\n';
    }
}

• Subtask 1: 12.9 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18