67-ni tapmaq#12267

67-ni tapmaq (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

fakt: Cavab $100$ -dən azdır.

Sübut: Gəlin $z = x mod 100$ z = x\mod100 ədədinə baxaq. Əgər $z < 67$ z < 67 doğrudursa, onda $x + 67 - z$ x + 67-z tuff-dur. Əks halda, əgər $z > 67$ z > 67-dirsə, onda $x + 167 - z$ x + 167-z tuff-dur ( $z$ $67$ -yə bərabər ola bilməz, çünki $x$ -nin tuff ədəd olmadığı təmin edilir).

$x mod 1000$ x\mod1000 üçün cavabı tapmaq üçün $x$ -in son $3$ rəqəmini ayrı-ayrılıqda soruşa bilərik və $x$ -in cavabı $x mod 1000$ x\mod1000-dən fərqli ola biləcəyi yeganə hal, $x$ -in aşağıdakı formada olduğu zamandır:

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

Beləliklə, yalnız $i d x$ -in ən kiçikini tapmalıyıq ki, bütün rəqəmlər $x_{i d x}, x_{i d x + 1}, ..., x_{n - 2}$ x_{idx},x_{idx+1},...,x_{n-2} $9$ -a bərabər olsun və $x_{i d x - 2} = x_{i d x - 1} = 6$ x_{idx-2} = x_{idx-1} = 6-ya baxmalıyıq, çünki $100 - x mod 100$ 100 - x\mod100-ni $x$ -ə əlavə etsək, bütün rəqəmlər $x_{i d x}, x_{i d x + 1}, ..., x_{n}$ x_{idx},x_{idx+1},...,x_{n} $0$ -a bərabər olacaq və $x_{i d x - 2}, x_{i d x - 1}$ x_{idx-2},x_{idx-1} rəqəmləri müvafiq olaraq $6, 7$ -yə çevriləcək.

Yuxarıdakıları ikili axtarışla $lo g (n) + 1$ \log(n)+1 sorğu istifadə edərək edə bilərik.


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