The 2018 ACM-ICPC Asia Qingdao Regional Contest

C - Flippy Sequence

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int maxn = 2e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
ll T,N;
char a[maxn],b[maxn];
ll solve(){
    vector<pii> LR;
    LR.clear();
    ll l = -1,r = -1;
    for(int i = 1;i<=N;i++){
        if(a[i] != b[i]){
            if(l == -1) l = i,r = i;
            else r = i;
        }else{
            if(l != -1 && r != -1){
                LR.pb({l,r});
                l = -1,r = -1;
                if(LR.size()>=3) return 0;
            }
        }
    }
    if(l != -1 && r != -1) LR.pb({l,r});
    if(LR.size()>=3) return 0;
    else if(LR.size()==0) return N*(N+1)/2;
    else if(LR.size()==1){
        ll l = LR[0].fs,r = LR[0].sc;
        ll ans = (r-l)*2;
        ans += (l-1)*2 + (N-r)*2;
        return ans;
    }else{
        return 6LL;
    }
}   
int main(){
    // debug;

    read(T);
    while(T--){
        read(N);
        scanf("%s",a+1);
        scanf("%s",b+1);
        ll ans = solve();
        printf("%lld\n",ans);
    }

    return 0;
}

D - Magic Multiplication

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,N,M;
char c[2*maxn];int len;
int a[maxn],b[maxn];
bool judge(int s){
    for(int i = 1;i<=N;i++) a[i] = 0;
    for(int i = 1;i<=M;i++) b[i] = 0;
    a[1] = s;
    int idxa = 1,idxb = 1,pos = 1;
    for(int j = 1;j<=M;j++){
        if(a[1] <= c[pos]-'0' || c[pos] == '0'){
            if(pos>len) return false;
            int cur = c[pos] - '0';
            if(cur%a[1]) return false;
            b[j] = cur/a[1];
            pos++;
        }else{
            if(pos>len-1) return false;
            int cur = 10*(c[pos] - '0') + c[pos+1]-'0';
            if(cur%a[1]) return false;
            b[j] = cur/a[1];
            pos+=2;
        }
    }
    // for(int j= 1;j<=M;j++) printf("%d",b[j]);printf("\n");
    while(1){
        if(pos>len) break;
        int cur_ans = -1;
        for(int j = 1;j<=M;j++){
            if(pos>len || idxa >=N) return false;
            int cur = c[pos]-'0';
            if(cur>=b[j] || cur == 0){
                if(cur>0 && b[j] == 0) return false;
                else if(cur == 0 && b[j] == 0){
                    ;
                }else{
                    if(cur%b[j]) return false;
                    if(cur_ans == -1) cur_ans = cur/b[j];
                    else if(cur_ans == cur/b[j]) ;
                    else return false;
                }
                pos += 1;
            }else{
                if(pos>len-1) return false;
                cur = cur*10 + c[pos+1]-'0';
                if(cur%b[j]) return false;
                if(cur_ans == -1) cur_ans = cur/b[j];
                else if(cur_ans == cur/b[j]) ;
                else return  false;
                pos += 2;
            }
        }
        a[++idxa] = cur_ans;
        if(idxa > N) return false;
    }
    if(idxa != N) return false;
    return true;
}
void solve(){
    int ok = 0;
    for(int i = 1;i<=9;i++){
        if(judge(i)){
            ok = 1;
            break;
        }
    }
    if(!ok) puts("Impossible");
    else{
        for(int i = 1;i<=N;i++){
            if(a[i] == -1) printf("0");
            else printf("%d",a[i]);
        }
        printf(" ");
        for(int i = 1;i<=M;i++) printf("%d",b[i]);printf("\n");
    }
}   
int main(){
    // debug;
    read(T);
    while(T--){
        read(N,M);
        scanf("%s",c+1);len = strlen(c+1);
        solve();
    }

    return 0;
}

E - Plants vs. Zombies

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
ll T,N,M;
ll a[maxn];
ll d[maxn];
bool judge(ll mid){
    for(int i = 1;i<=N;i++) d[i] = 0;
    ll t = M,pos = 0;
    while(1){
        if(pos >N) break;
        if(t<=0) break;
        if(pos == 0 && t>0) {
            pos++;
            d[pos] += a[pos];
            t--;
        }else{
            if(d[pos] < mid){
                ll tim = (mid - d[pos] + a[pos] - 1)/a[pos];
                if(2*tim > t) return false;
                d[pos] += a[pos] * tim;
                d[pos+1] += a[pos+1] * tim;
                t -= 2*tim;
            }
            if(t>0 && pos<=N){
                pos++;
                d[pos] += a[pos];
                t--;
            }
        }

    }
    for(int i = 1;i<=N;i++) if(d[i] < mid) return false;
    return true;
}
void solve(){
    ll l = 0,r = 1e18+100,ans;
    while(l<=r){
        ll mid = (l+r)>>1;
        if(judge(mid)) l = mid+1,ans = mid;
        else r = mid-1; 
    }
    printf("%lld\n",ans);
}   
int main(){
    // debug;
    read(T);
    while(T--){
        read(N,M);
        for(int i = 1;i<=N;i++) read(a[i]);
        solve();
    }

    return 0;
}

J - Books

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,N,M;
int a[maxn];
void solve(){
    int t1 = M,t2 = 0;
    for(int i = 1;i<=N;i++) if(a[i] <= 0) t2++;
    if(t2>t1) puts("Impossible");
    else if(t1 == 0){
        int mi = 1e9+10;
        for(int i = 1;i<=N;i++) mi = min(mi,a[i]);
        printf("%d\n",mi-1);
    }else{
        if(t1 == N) puts("Richman");
        else{
            t1 -= t2;
            ll ans = 0,ok = 1;
            for(int i =1;i<=N;i++){
                if(t1>0){
                    if(a[i] != 0) {
                        ans += a[i];
                        t1--;
                    }
                }else{
                    int mi = 1e9+10;
                    for(int j = i;j<=N;j++){
                        if(a[j] != 0) mi = min(mi,a[j]);
                    }
                    ans += mi-1;
                    break;
                }
            }
            printf("%lld\n",ans);
        }
    }
}   
int main(){
    // debug;

    read(T);
    while(T--){
        read(N,M);
        for(int i = 1;i<=N;i++) read(a[i]);
        solve();
    }

    return 0;
}

M - Function and Function

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class T>void print(T x){
    cout<<x<<" ";
}
template<class H, class... T> void print(H h, T... t) {
    print(h);
    print(t...);
}
int T,x,k;
int a[100];
void init(){
    a[1] = a[2] = a[3] = a[5] = a[7] = 0;
    a[0] = a[4] = a[6] = a[9] = 1;
    a[8] = 2;
}
int solve(){
    int ans = x;
    for(int i = 1;i<=k;i++){
        int tmp = ans;
        int tmp2 = 0;
        if(tmp == 0){
            int left = k-i+1;
            if(left%2) return 1;
            else return 0;
        }else{
            while(tmp){
                tmp2 += a[tmp%10];
                tmp/=10;
            }
        }
        if(tmp2 == ans) break;
        ans = tmp2;
    }
    return ans;
}   
int main(){
    // debug;

    init();
    read(T);
    while(T--){
        read(x,k);
        int ans = solve();
        printf("%d\n",ans);
    }

    return 0;
}