Ideone.com

fork download

copy

#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define db double
#define bo bool
#define vo void
#define ch char
#define fl float
#define ll long long
#define ull unsigned long long
#define str string
#define re return
#define all(x) (x).begin(),(x).end()
using namespace std;
//Đề Đại Học Sư Phạm Hà Nội
vo bai1()
{
	ll n,i,d=0;
	cin>>n;
    for(i=2;i*i<=n;i++)
	{
        if(n%i==0)
		{
            d=i;
            break;
        }
    }
    if(!d) cout<<n-1;
    else cout<<n-d;
}
vo bai2_bruteforce()
{
	ll n,res=0,x,i;
	bo ok;
    str b;
    cin>>n>>b;
    bo check[10]={};
    for(ch c:b) check[c-'0']=1;
    for(i=1;i<=n;i++)
	{
        x=i;
        ok=1;
        while(x)
		{
            if(check[x%10])
			{
                ok=0;
                break;
            }
            x/=10;
        }
        if(ok) res++;
    }
    cout<<res;
}
str s;
ll d[10],dp[20][2][2];
ll TRY(ll i,ll t,ll l)
{
    if(i==(ll)s.size()) re l?0:1;
    ll &r=dp[i][t][l],t1,l1,u=t?(s[i]-'0'):9;
    if(r!=-1) return r;
    r=0;
    for(ll j=0;j<=u;j++)
	{
        t1=t&&(j==u);
        l1=l&&(j==0);
        if(l1) r+=TRY(i+1,t1,1);
        else if(!d[j]) r+=TRY(i+1,t1,0);
    }
    re r;
}
vo bai2_deque()
{
    ll n;
	str b;
    cin>>n>>b;
    for(ch c:b) d[c-'0']=1;
    s=to_string(n);
    memset(dp,-1,sizeof(dp));
    cout<<TRY(0,1,1);
}
vo bai2_dp()
{
    ll n,m,i,j,k,v,l,q,z,p;
	str b;
	static ll f[20][2][2];
	str s;
    cin>>n>>b;
    s=to_string(n);
    m=s.size();
    bo check[10]={};
    for(ch c:b) check[c-'0']=1;
    f[0][1][1]=1;
    for(i=0;i<m;i++)
	{
        for(j=0;j<2;j++)
		for(k=0;k<2;k++)
		{
        	v=f[i][j][k];
            if(!v) continue;
            p=j?(s[i]-'0'):9;
            for(l=0;l<=p;l++)
			{
                q=j&&(l==p);
                z=k&&(l==0);
                if(z) f[i+1][q][1] += v;
                else
				{
                    if(check[l]) continue;
                    f[i+1][q][0]+=v;
                }
            }
        }
    }
    cout<<f[m][0][0]+f[m][1][0];
}
vo bai3()
{
	ll n,m,l=1,r,res,mid,i;
	bo ok;
    cin>>n>>m;
    r=n;
    res=n;
    vector<ll> a(n+1),b(n+1,0);
    for(i=1;i<=n;i++)
	{
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    while(l<=r)
	{
		ok=true;
        mid=(l+r)/2;
        for(i=mid;i<=n;i++)
        if(b[i]-b[i-mid]<m)
        {
        	ok=false;
        	break;
		}
        if(ok)
		{
            res=mid;
            r=mid-1;
        }
		else l=mid+1;
    }
    cout<<res;
}
vo bai4()
{
	ll x,t,i,j,p=pow(2,9);
	vector<ll> v;
    v.push_back(0);
    for(i=1;i<p;i++)
	{
        x=0;
        for(j=0;j<9;j++)
        if(i&(1<<j)) x=x*10+(j+1);
        v.push_back(x);
    }
    sort(all(v));
    cin>>t;
    while(t--)
	{
        cin>>x;
        auto it=upper_bound(all(v),x);
        if(it==v.begin()) cout<<0<<"\n";
        else
		{
			it--;
			cout<<*it<<"\n";
		}
    }
}
int main()
{
	faster
//	bai1();
//	bai2_bruteforce();
//	bai2_deque();
//	bai2_dp();
//	bai3();
	bai4();
	re 0;
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBmYXN0ZXIgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKDApO2NvdXQudGllKDApOwojZGVmaW5lIGRiIGRvdWJsZQojZGVmaW5lIGJvIGJvb2wKI2RlZmluZSB2byB2b2lkCiNkZWZpbmUgY2ggY2hhcgojZGVmaW5lIGZsIGZsb2F0CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIHN0ciBzdHJpbmcKI2RlZmluZSByZSByZXR1cm4KI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksKHgpLmVuZCgpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8vxJDhu4EgxJDhuqFpIEjhu41jIFPGsCBQaOG6oW0gSMOgIE7hu5lpCnZvIGJhaTEoKQp7CglsbCBuLGksZD0wOwoJY2luPj5uOwogICAgZm9yKGk9MjtpKmk8PW47aSsrKQoJewogICAgICAgIGlmKG4laT09MCkKCQl7CiAgICAgICAgICAgIGQ9aTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgfQogICAgaWYoIWQpIGNvdXQ8PG4tMTsKICAgIGVsc2UgY291dDw8bi1kOwp9CnZvIGJhaTJfYnJ1dGVmb3JjZSgpCnsKCWxsIG4scmVzPTAseCxpOwoJYm8gb2s7CiAgICBzdHIgYjsKICAgIGNpbj4+bj4+YjsKICAgIGJvIGNoZWNrWzEwXT17fTsKICAgIGZvcihjaCBjOmIpIGNoZWNrW2MtJzAnXT0xOwogICAgZm9yKGk9MTtpPD1uO2krKykKCXsKICAgICAgICB4PWk7CiAgICAgICAgb2s9MTsKICAgICAgICB3aGlsZSh4KQoJCXsKICAgICAgICAgICAgaWYoY2hlY2tbeCUxMF0pCgkJCXsKICAgICAgICAgICAgICAgIG9rPTA7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICB4Lz0xMDsKICAgICAgICB9CiAgICAgICAgaWYob2spIHJlcysrOwogICAgfQogICAgY291dDw8cmVzOwp9CnN0ciBzOwpsbCBkWzEwXSxkcFsyMF1bMl1bMl07CmxsIFRSWShsbCBpLGxsIHQsbGwgbCkKewogICAgaWYoaT09KGxsKXMuc2l6ZSgpKSByZSBsPzA6MTsKICAgIGxsICZyPWRwW2ldW3RdW2xdLHQxLGwxLHU9dD8oc1tpXS0nMCcpOjk7CiAgICBpZihyIT0tMSkgcmV0dXJuIHI7CiAgICByPTA7CiAgICBmb3IobGwgaj0wO2o8PXU7aisrKQoJewogICAgICAgIHQxPXQmJihqPT11KTsKICAgICAgICBsMT1sJiYoaj09MCk7CiAgICAgICAgaWYobDEpIHIrPVRSWShpKzEsdDEsMSk7CiAgICAgICAgZWxzZSBpZighZFtqXSkgcis9VFJZKGkrMSx0MSwwKTsKICAgIH0KICAgIHJlIHI7Cn0Kdm8gYmFpMl9kZXF1ZSgpCnsKICAgIGxsIG47CglzdHIgYjsKICAgIGNpbj4+bj4+YjsKICAgIGZvcihjaCBjOmIpIGRbYy0nMCddPTE7CiAgICBzPXRvX3N0cmluZyhuKTsKICAgIG1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICAgIGNvdXQ8PFRSWSgwLDEsMSk7Cn0Kdm8gYmFpMl9kcCgpCnsKICAgIGxsIG4sbSxpLGosayx2LGwscSx6LHA7CglzdHIgYjsKCXN0YXRpYyBsbCBmWzIwXVsyXVsyXTsKCXN0ciBzOwogICAgY2luPj5uPj5iOwogICAgcz10b19zdHJpbmcobik7CiAgICBtPXMuc2l6ZSgpOwogICAgYm8gY2hlY2tbMTBdPXt9OwogICAgZm9yKGNoIGM6YikgY2hlY2tbYy0nMCddPTE7CiAgICBmWzBdWzFdWzFdPTE7CiAgICBmb3IoaT0wO2k8bTtpKyspCgl7CiAgICAgICAgZm9yKGo9MDtqPDI7aisrKQoJCWZvcihrPTA7azwyO2srKykKCQl7CiAgICAgICAgCXY9ZltpXVtqXVtrXTsKICAgICAgICAgICAgaWYoIXYpIGNvbnRpbnVlOwogICAgICAgICAgICBwPWo/KHNbaV0tJzAnKTo5OwogICAgICAgICAgICBmb3IobD0wO2w8PXA7bCsrKQoJCQl7CiAgICAgICAgICAgICAgICBxPWomJihsPT1wKTsKICAgICAgICAgICAgICAgIHo9ayYmKGw9PTApOwogICAgICAgICAgICAgICAgaWYoeikgZltpKzFdW3FdWzFdICs9IHY7CiAgICAgICAgICAgICAgICBlbHNlCgkJCQl7CiAgICAgICAgICAgICAgICAgICAgaWYoY2hlY2tbbF0pIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIGZbaSsxXVtxXVswXSs9djsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGNvdXQ8PGZbbV1bMF1bMF0rZlttXVsxXVswXTsKfQp2byBiYWkzKCkKewoJbGwgbixtLGw9MSxyLHJlcyxtaWQsaTsKCWJvIG9rOwogICAgY2luPj5uPj5tOwogICAgcj1uOwogICAgcmVzPW47CiAgICB2ZWN0b3I8bGw+IGEobisxKSxiKG4rMSwwKTsKICAgIGZvcihpPTE7aTw9bjtpKyspCgl7CiAgICAgICAgY2luPj5hW2ldOwogICAgICAgIGJbaV09YltpLTFdK2FbaV07CiAgICB9CiAgICB3aGlsZShsPD1yKQoJewoJCW9rPXRydWU7CiAgICAgICAgbWlkPShsK3IpLzI7CiAgICAgICAgZm9yKGk9bWlkO2k8PW47aSsrKQogICAgICAgIGlmKGJbaV0tYltpLW1pZF08bSkKICAgICAgICB7CiAgICAgICAgCW9rPWZhbHNlOwogICAgICAgIAlicmVhazsKCQl9CiAgICAgICAgaWYob2spCgkJewogICAgICAgICAgICByZXM9bWlkOwogICAgICAgICAgICByPW1pZC0xOwogICAgICAgIH0KCQllbHNlIGw9bWlkKzE7CiAgICB9CiAgICBjb3V0PDxyZXM7Cn0Kdm8gYmFpNCgpCnsKCWxsIHgsdCxpLGoscD1wb3coMiw5KTsKCXZlY3RvcjxsbD4gdjsKICAgIHYucHVzaF9iYWNrKDApOwogICAgZm9yKGk9MTtpPHA7aSsrKQoJewogICAgICAgIHg9MDsKICAgICAgICBmb3Ioaj0wO2o8OTtqKyspCiAgICAgICAgaWYoaSYoMTw8aikpIHg9eCoxMCsoaisxKTsKICAgICAgICB2LnB1c2hfYmFjayh4KTsKICAgIH0KICAgIHNvcnQoYWxsKHYpKTsKICAgIGNpbj4+dDsKICAgIHdoaWxlKHQtLSkKCXsKICAgICAgICBjaW4+Png7CiAgICAgICAgYXV0byBpdD11cHBlcl9ib3VuZChhbGwodikseCk7CiAgICAgICAgaWYoaXQ9PXYuYmVnaW4oKSkgY291dDw8MDw8IlxuIjsKICAgICAgICBlbHNlCgkJewoJCQlpdC0tOwoJCQljb3V0PDwqaXQ8PCJcbiI7CgkJfQogICAgfQp9CmludCBtYWluKCkKewoJZmFzdGVyCi8vCWJhaTEoKTsKLy8JYmFpMl9icnV0ZWZvcmNlKCk7Ci8vCWJhaTJfZGVxdWUoKTsKLy8JYmFpMl9kcCgpOwovLwliYWkzKCk7CgliYWk0KCk7CglyZSAwOwp9Cgo=

Success #stdin #stdout 0.01s 5288KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/PrPIvD

language:

C++14 (clang 8.0)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language