ASC 35

C Spending Budget

#include<bits/stdc++.h>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("budget.in", "r", stdin)
#define OUT freopen("budget.out", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))
#define fi first
#define se second
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int maxn=105;
LL n,m,pp;
LL r[maxn],l[maxn];
priority_queue<LL> p;
priority_queue< pair<LL,LL> > q;

bool check(LL x)
{
    int cnt=0;
    while(!q.empty())q.pop();
    while(!p.empty())p.pop();
    for(int i=1;i<=m;i++)q.push(mp(x-l[i]+1,l[i]));
    while(!q.empty() && cnt<n)
    {
        cnt++;
        pair<LL,LL> t=q.top();q.pop();
        p.push(t.fi);
        if(t.fi>t.se)
        {
            t.fi-=t.se;
            q.push(t);
        }
    }
    if(cnt<n)return false;
    for(int i=n;i>=1;i--)
    {
        if(p.top()<r[i])return false;
        p.pop();
    }
    return true;
}

int main()
{
    IN;OUT;
    scanf("%lld%lld%lld",&m,&n,&pp);
    for(int i=1;i<=m;i++)
    {
        LL x;
        scanf("%lld",&x);
        l[i]=(pp+x-1)/x;
    }
    for(int i=1;i<=n;i++)scanf("%lld",&r[i]);
    sort(r+1,r+n+1);
    LL le=0,ri=1e11;
    while(ri-le>1)
    {
        LL mid=(le+ri)>>1;
        if(check(mid))ri=mid;else le=mid;
    }
    if(!check(le))le++;
    printf("%lld\n",le);
    return 0;
}

D Circuit Design

判断电路险象的策略：
可以发现险象经过一个门消失只有2种情况：and0，or1
我们给电路中的任意点定义5种状态（0，1，升，降，险象），然后对这5*5种情况通过与或非门的情况分别讨论。

E Strange Digits

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=min(a+b,100LL);}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
int T;
#define MAXN (511)
char a[MAXN];
ll f[MAXN][110];
//first i,jth num
int b,k;
char buf[MAXN];
int pre[MAXN][110];
char h[1000000];
int an[1000000],cnt=0;
int a2[100000],nn=0;
struct BigInteger {
    typedef unsigned long long LL;

    static const int BASE = 100000000;
    static const int WIDTH = 8;
    vector<int> s;

    BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
    BigInteger(LL num = 0) {*this = num;}
    BigInteger(string s) {*this = s;}
    BigInteger& operator = (long long num) {
        s.clear();
        do {
            s.push_back(num % BASE);
            num /= BASE;
        } while (num > 0);
        return *this;
    }
    BigInteger& operator = (const string& str) {
        s.clear();
        int x, len = (str.length() - 1) / WIDTH + 1;
        for (int i = 0; i < len; i++) {
            int end = str.length() - i*WIDTH;
            int start = max(0, end - WIDTH);
            sscanf(str.substr(start,end-start).c_str(), "%d", &x);
            s.push_back(x);
        }
        return (*this).clean();
    }

    BigInteger operator + (const BigInteger& b) const {
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = g;
            if (i < s.size()) x += s[i];
            if (i < b.s.size()) x += b.s[i];
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c;
    }
    BigInteger operator - (const BigInteger& b) const {
        assert(b <= *this); // 减数不能大于被减数
        BigInteger c; c.s.clear();
        for (int i = 0, g = 0; ; i++) {
            if (g == 0 && i >= s.size() && i >= b.s.size()) break;
            int x = s[i] + g;
            if (i < b.s.size()) x -= b.s[i];
            if (x < 0) {g = -1; x += BASE;} else g = 0;
            c.s.push_back(x);
        }
        return c.clean();
    }
    BigInteger operator * (const BigInteger& b) const {
        int i, j; LL g;
        vector<LL> v(s.size()+b.s.size(), 0);
        BigInteger c; c.s.clear();
        for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
        for (i = 0, g = 0; ; i++) {
            if (g ==0 && i >= v.size()) break;
            LL x = v[i] + g;
            c.s.push_back(x % BASE);
            g = x / BASE;
        }
        return c.clean();
    }
    BigInteger operator / (const BigInteger& b) const {
        assert(b > 0);  // 除数必须大于0
        BigInteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大
        BigInteger m;               // 余数:初始化为0
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return c.clean();
    }
    BigInteger operator / (const ll& b) const {
        assert(b > 0);  // 除数必须大于0
        BigInteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大
        ll m=0;               // 余数:初始化为0
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = m/b ;
            m -= b*c.s[i];
        }

        return c.clean();
    }
    BigInteger operator % (const ll& b) const {
        assert(b > 0);  // 除数必须大于0
        BigInteger c = *this;       // 商:主要是让c.s和(*this).s的vector一样大
        ll m=0;               
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            m%=b;
        }

        return BigInteger(m);
    }

    BigInteger operator % (const BigInteger& b) const { //方法与除法相同
        BigInteger c = *this;
        BigInteger m;
        for (int i = s.size()-1; i >= 0; i--) {
            m = m*BASE + s[i];
            c.s[i] = bsearch(b, m);
            m -= b*c.s[i];
        }
        return m;
    }

    // 二分法找出满足bx<=m的最大的x
    int bsearch(const BigInteger& b, const BigInteger& m) const{
        int L = 0, R = BASE-1, x;
        while (1) {
            x = (L+R)>>1;
            if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
            else R = x;
        }
    }
    BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
    BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
    BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
    BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
    BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}

    BigInteger& operator /= (const ll& b) {*this = *this / b; return *this;}
    BigInteger& operator %= (const ll& b) {*this = *this % b; return *this;}


    bool operator < (const BigInteger& b) const {
        if (s.size() != b.s.size()) return s.size() < b.s.size();
        for (int i = s.size()-1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
    bool operator >(const BigInteger& b) const{return b < *this;}
    bool operator<=(const BigInteger& b) const{return !(b < *this);}
    bool operator>=(const BigInteger& b) const{return !(*this < b);}
    bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
    bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};

ostream& operator << (ostream& out, const BigInteger& x) {
    out << x.s.back();
    for (int i = x.s.size()-2; i >= 0; i--) {
        char buf[20];
        sprintf(buf, "%08d", x.s[i]);
        for (int j = 0; j < strlen(buf); j++) out << buf[j];
    }
    return out;
}

istream& operator >> (istream& in, BigInteger& x) {
    string s;
    if (!(in >> s)) return in;
    x = s;
    return in;
}
int main()
{
//  freopen("E.in","r",stdin);
    freopen("digits.in","r",stdin);
    freopen("digits.out","w",stdout);
    b=read();
    scanf("%s",buf);
    int len=strlen(buf);
    Rep(i,len) {
        if (isdigit(buf[i])) buf[i]-='0'; else buf[i]=buf[i]-'A'+10;
    }
    sort(buf,buf+len);
    Rep(i,10) h[i]=i+'0';
    Rep(i,26) h[10+i]=i+'A';

    BigInteger p;
    cin>>p;
    int n=0;
    while(p>0) {
        a[++n] = (p%b).s[0];
        p/=b;
    }
    if(n==0) {
        a[++n]=0;
    }
    reverse(a+1,a+1+n);
    ll ans=0;


    MEM(f)
    f[0][0]=1;
    Rep(i,n) {
        Rep(j,36){
            if (f[i][j]) {
                Rep(k,len) {
                    int t=buf[k];
                    int nj=j*b+a[i+1]-t;
                    if (0<=nj && nj<= 36 )  {
                        upd(f[i+1][nj],f[i][j]);
                        pre[i+1][nj]=j;
                    }
                }
            }
        }
    }

    ans=f[n][0];
    if (ans==0) puts("Impossible");
    else{
        if (ans>1) puts("Ambiguous");
        else puts("Unique");

        int i=n,j=0;
        while(1) {
            if (!i && !j) {
                break;
            }
            int nj=pre[i][j],ni=i-1;
            an[cnt++]=nj*b+a[i]-j;
            i=ni,j=nj;
        }
        bool fl=0;
        RepD(i,cnt-1) {
            if (!fl) {
                if (!an[i]) continue;
            }
            fl=1;cout<<h[an[i]];
        }
        if (!fl) putchar('0');
        puts("");

    }

    return 0;
}