Знаходження 67#12267

Знаходження 67 (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редаговано:	Hasan Saleh (MathModel)

Рішення

факт: Відповідь менша за $100$ .

Доказ: Давайте розглянемо число $z = x mod 100$ z = x\mod100. Якщо $z < 67$ z < 67, то $x + 67 - z$ x + 67-z є "tuff". Інакше, якщо $z > 67$ z > 67, то $x + 167 - z$ x + 167-z є "tuff" ( $z$ не може дорівнювати $67$ , оскільки $x$ гарантовано не є "tuff" числом).

Ми можемо знайти відповідь для $x mod 1000$ x\mod1000, запитуючи останні $3$ цифри в $x$ окремо, і єдиний випадок, коли відповідь для $x$ може відрізнятися від відповіді для $x mod 1000$ x\mod1000, це коли $x$ має форму:

$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}

Отже, нам потрібно лише знайти найменший $i d x$ , де всі цифри $x_{i d x}, x_{i d x + 1}, ..., x_{n - 2}$ x_{idx},x_{idx+1},...,x_{n-2} дорівнюють $9$ , і перевірити, чи $x_{i d x - 2} = x_{i d x - 1} = 6$ x_{idx-2} = x_{idx-1} = 6, тому що якщо ми додамо $100 - x mod 100$ 100 - x\mod100 до $x$ , всі цифри $x_{i d x}, x_{i d x + 1}, ..., x_{n}$ x_{idx},x_{idx+1},...,x_{n} стануть рівними $0$ , а цифри $x_{i d x - 2}, x_{i d x - 1}$ x_{idx-2},x_{idx-1} стануть $6, 7$ відповідно.

Ми можемо зробити вищезазначене за допомогою бінарного пошуку, використовуючи $lo g (n) + 1$ \log(n)+1 запитів.


#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";
    }
}