Finding 67#12267

Finding 67 (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

fact: The answer is less than $100$ .

Proof: Let's look at the number $z = x mod 100$ z = x\mod100. If $z < 67$ z < 67 is true then $x + 67 - z$ x + 67-z is tuff. Otherwise if $z > 67$ z > 67 then $x + 167 - z$ x + 167-z is tuff ( $z$ can't be equal to $67$ because $x$ is guaranteed to not be a tuff number).

We can find the answer for $x mod 1000$ x\mod1000 by querying the last $3$ digits in $x$ individually, and the only case where the answer for $x$ can differ from the answer for $x mod 1000$ x\mod1000 is when $x$ is of the form:

$x_{1} x_{2} ... x_{i - 2} x_{i - 1} 6699...99 x_{n - 1} x_{n}$ x_1x_2...x_{i-2}x_{i-1}6699...99x_{n-1}x_{n}

So we only need to find the smallest $i d x$ where all the digits $x_{i d x}, x_{i d x + 1}, ..., x_{n - 2}$ x_{idx},x_{idx+1},...,x_{n-2} are equal to $9$ and check if $x_{i d x - 2} = x_{i d x - 1} = 6$ x_{idx-2} = x_{idx-1} = 6, because if we add $100 - x mod 100$ 100 - x\mod100 to $x$ all the digits $x_{i d x}, x_{i d x + 1}, ..., x_{n}$ x_{idx},x_{idx+1},...,x_{n} will be equal to $0$ , and the digits $x_{i d x - 2}, x_{i d x - 1}$ x_{idx-2},x_{idx-1} will become $6, 7$ respectively.

We can do the above with binary search using $lo g (n) + 1$ \log(n)+1 queries.


#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mid ((l+r)/2)
 
using namespace std;

const ll N = 2e5+9;

ll n;

bool check(ll id)
{
    vector<ll> v;
    for(int i = id ; n-2>=i ; i++)
        v.pb(i);
    cout << "? " << v.size();
    for(auto it : v)
        cout << " " << it;
    cout << "\n";
    ll sz;
    bool g = 1;
    cin >> sz;
    if(sz!=1)
        g=0;
    while(sz--)
    {
        ll s;
        cin >> s;
        if(s!=9)
            g=0;
    }
    return g;
}

ll dgit(ll id)
{
    cout << "? " << 1 << " " << id << "\n";
    ll dg;
    cin >> dg >> dg;
    return dg;
}

int main()
{
    ll T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        if(n==-1)
            return 0;
        if(n==1)
        {
            ll x = dgit(n);
            cout << "! " << 67-x << "\n";
            continue;
        }
        ll x = dgit(n-1) , y = dgit(n);
        ll e = x*10 + y;
        if(n==2)
        {
            if(e<67)
                cout << "! " << 67-e << "\n";
            else
                cout << "! " << 167-e << "\n";
            continue;
        }
        ll ans = LLONG_MAX;
        if(e<67)
            ans=min(ans,67-e);
        else
            ans=min(ans,167-e);
        ll z = dgit(n-2);
        if(z==6&&e<70)
            ans=min(ans,70-e);
        ll l = 1 , r = n-2;
        ll id=-1;
        while(l<=r)
        {
            if(check(mid))
                id=mid,r=mid-1;
            else
                l=mid+1;
        }
        if(id!=-1&&id>2)
        {
            cout << "? " << 2 << " " << id-1 << " " << id-2 << "\n";
            ll sz;
            cin >> sz;
            bool g = 1;
            if(sz!=1)
                g=0;
            while(sz--)
            {
                ll s;
                cin >> s;
                if(s!=6)
                    g=0;
            }
            if(g)
                ans=min(ans,100-e);
        }
        cout << "! " << ans << "\n";
    }
}