Contest 2020

contest

A

#include<stdio.h>
int main()
{
    int n,num[105],t,flag;
    for(int i=0;i<105;i++)num[i]=0;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&t);
            num[t]++;
        }
        flag=0;
        for(int i=0;i<105;i++)
        {
            while(num[i])
            {
                if(flag==1)printf(" %d",i);
                else
                {
                    printf("%d",i);
                    flag=1;
                }
                num[i]--;
            }
        }
        printf("\n");
    }
}

B

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif
    int a[7]= {0,1,2,11,101,111,1001};
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF) {
        if(m<n){
            int f=m;
            m=n;
            n=f;
        }
        int f=0;
        for(int i=0; i<7; i++) {
            if(a[i]>=n&&a[i]<=m) {
                f=1;
                cout<<a[i]<<" ";
            }
        }
        if(!f)
            cout<<-1;
        cout<<endl;
    }
#ifdef xiaofan
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#endif
    return 0;
}

C

#include<stdio.h>
#define Pai 3.141592653589
double solution1(double k,double m)
{
    double r=k/(2*Pai);
    return Pai*r*r*(m-2*r);
}
double solution2(double k,double m)
{
    double r=m/(2*Pai+2);
    if(r>k/2)r=k/2;
    return Pai*r*r*k;
}
int main()
{
    double a,b,ans1,ans2;
    while(1)
    {
        scanf("%lf%lf",&a,&b);
        if(a==0&&b==0)break;
        ans1=solution1(a,b);
        ans2=solution2(a,b);
        if(ans1>ans2)printf("%.3lf\n",ans1);
        else printf("%.3lf\n",ans2);
    }
}

D

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define int long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=2e5+10;
int s[N],x[N],a[N];
signed main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+a[i];
        x[i]=x[i-1]^a[i];
    }
    int l=1,r=1;
    int ans=0;
    while(r<=n){
        while((s[r]-s[l-1])!=(x[r]^x[l-1]))
            l++;
        //cout<<l<<" "<<r<<endl;
        ans+=r-l+1;
        r++;
    }
    cout<<ans<<endl;
#ifdef xiaofan
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#endif
    return 0;
}

E

#include<stdio.h>
int main()
{
    int cas=0,flag;
    long long mul,k,min,m,n,temp;
    while(scanf("%lld",&k)!=EOF)
    {
        printf("Case %d: ",++cas);
        temp=1;flag=0;
        if(k==1)
        {
            printf("Impossible\n");
            continue;
        }
        for(long long i=2;i<k;i++)
        {
            temp*=i;
            if(temp>=k)
            {
                min=i;
                break;
            }
        }
        if(temp==k)
        {
            printf("%lld 1\n",min);
            continue;
        }
        for(long long i=min;(i-1)*(i-1)<=k;i++)
        {
            mul=i;
            for(long long j=i-1;j>=1;j--)
            {
                mul*=j;
                if(mul>k)break;
                if(mul==k)
                {
                    printf("%lld %lld\n",i,j-1);
                    flag=1;
                    break;
                }
            }
            if(flag)break;
        }
        if(!flag)printf("%lld %lld\n",k,k-1);
    }
}

F

#include <stdio.h>
char down[12][12],up[12][12];
bool check(int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)if(up[i][j]=='*')return false;
    }
    return true;
}
int main()
{
    int x1,y1,x2,y2,n,m,end;
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(!n&&!m)break;
        getchar();
        for(int i=0;i<n;i++)gets(up[i]);
        for(int i=0;i<m;i++)gets(down[i]);
        int flag=0;end=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(down[i][j]=='*')
                {
                    x2=i;
                    y2=j;
                    flag=1;
                    break;
                }
            }
            if(flag)break;
        }
        while(!check(n)&&end)
        {
            int flag=0;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(up[i][j]=='*')
                    {
                        x1=i;
                        y1=j;
                        flag=1;
                        break;
                    }
                }
                if(flag)break;
            }
            for(int i=0;i<m&&end;i++)
            {
                for(int j=0;j<m&&end;j++)
                {
                    if(down[i][j]=='*')
                    {
                        if(up[x1-x2+i][y1-y2+j]=='*')up[x1-x2+i][y1-y2+j]='.';
                        else 
                        {
                            end=0;
                            break;
                        }
                    }
                }
            }
        }
        if(end)printf("1\n");
        else printf("0\n");
    }
}

G

#include<stdio.h>
int a[10005];
int findtop(int x)
{
    return x==a[x]?x:a[x]=findtop(a[x]);
}
int checktop(int x)
{
    return x==a[x]?x:checktop(a[x]);
}
int main()
{
    int n,m,x,y,t,sum,k1,k2,b[10];
    char ch[10];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<=(n+1)*(n+1);i++)a[i]=-1;
        sum=0;k1=0;
        while(m--)
        {
            scanf("%s",ch);
            if(ch[0]=='O')
            {
                scanf("%d%d",&x,&y);
                t=x*n+y;
                if(a[t]!=-1)continue;
                a[t]=t;
                k1=0;
                if(x!=n-1)if(a[t+n]!=-1){b[k1]=checktop(t+n);k1++;}
                if(x!=0)if(a[t-n]!=-1){b[k1]=checktop(t-n);k1++;}
                if(y!=n-1)if(a[t+1]!=-1){b[k1]=checktop(t+1);k1++;}
                if(y!=0)if(a[t-1]!=-1){b[k1]=checktop(t-1);k1++;}
                int temp=k1;
                for(int i=0;i<temp;i++)
                {
                    for(int j=i+1;j<temp;j++)
                    {
                        if(b[i]==b[j]&&b[i]!=-1)
                        {
                            k1--;
                            b[j]=-1;
                        }
                    }
                }
                if(x!=n-1)if(a[t+n]!=-1&&a[findtop(t)]!=a[findtop(t+n)])a[findtop(t)]=a[findtop(t+n)];
                if(x!=0)if(a[t-n]!=-1&&a[findtop(t)]!=a[findtop(t-n)])a[findtop(t)]=a[findtop(t-n)];
                if(y!=n-1)if(a[t+1]!=-1&&a[findtop(t)]!=a[findtop(t+1)])a[findtop(t)]=a[findtop(t+1)];
                if(y!=0)if(a[t-1]!=-1&&a[findtop(t)]!=a[findtop(t-1)])a[findtop(t)]=a[findtop(t-1)];
                sum=sum+1-k1;
            }
            else if(ch[0]=='P')printf("%d\n",sum);
        }
    }
}

H

#include<stdio.h>
int dfs(int a,int b)
{
    if(a>b)
    {
        int temp=a;
        a=b;
        b=temp;
    }
    if(b%a==0)return 1;
    else
    {
        if(dfs(b%a,a)==1&&b-a<a)return 0;
        else return 1;
    }
}
int main()
{
    int a,b;
    while(1)
    {
        scanf("%d%d",&a,&b);
        if(a==0&&b==0)break;
        if(dfs(a,b)==1)printf("Captain\n");
        else printf("Big Pang Pang\n");
    }
}

I

#include <cstdio>
#include <cctype>
#include <algorithm>
#define int long long
using namespace std;
struct Node {
    int x, y;
} a[233];
int n, num, ans = 0x7fffffffffffffff;
int read() {
    int ret, f = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * f;
}
void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
bool cmp(Node a, Node b) {
    return a.x < b.x;
}
signed main() {
    n = read(), num = read();
    for(int i = 1; i <= n; ++i) a[i].x = read(), a[i].y = read();
    std::sort(a + 1, a + n + 1, cmp);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j) {
            int tmx = std::max(a[i].y, a[j].y),
                tmn = std::min(a[i].y, a[j].y);
            for(int k = 1; k <= n; ++k) {
                if(a[k].y > tmx || a[k].y < tmn) continue;
                int cnt = 0;
                for(int l = k; l <= n; ++l) {
                    if(a[l].y > tmx || a[l].y < tmn) continue;
                    if(++cnt >= num) ans = min(ans, (tmx - tmn) * (a[l].x - a[k].x));
                }
            }
        }
    print(ans);
    return 0;
}

J

#include <cstdio>
#include <cctype>
#include <algorithm>
#define int long long
int n, m;
int a[100010], fs[100010];
int l = 0, r = 200010, ans, cnt, res;
int read() {
    int ret, f = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * f;
}
void print(int x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
signed main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    std::sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) fs[i] = fs[i - 1] + a[i];
    while(l <= r) {
        int mid = (l + r) >> 1;
        cnt = res = 0;
        for(int i = 1; i <= n; ++i) {
            int pos = std::lower_bound(a + 1, a + n + 1, mid - a[i]) - a;
            res += fs[n] - fs[pos - 1] + a[i] * (n - pos + 1); 
            cnt += n - pos + 1;
        }
        if(cnt >= m) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    print(res - ans * (cnt - m));
    return 0;
}

K

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod=20130719;
struct node {
    ll m,l;
    ll v[3][3];
};
node qmul(node a,node b) {
    node c;
    c.m=a.m,c.l=b.l;
    for(int i=1; i<=c.m; i++) {
        for(int j=1; j<=c.l; j++) {
            c.v[i][j]=0;
            for(int k=1; k<=a.l; k++) {
                c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%mod;
            }
        }
    }
    return c;
}
int get(ll n) {
    node a,b;
    a.l=2,a.m=1,a.v[1][1]=1,a.v[1][2]=0;
    b.l=2,b.m=2,b.v[1][1]=1,b.v[1][2]=1,b.v[2][1]=1,b.v[2][2]=0;
    while(n) {
        if(n&1)
            a=qmul(a,b);
        b=qmul(b,b);
        n/=2;
    }
    return a.v[1][2];
}
int main() {
    IOS;
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif
    ll n;
    while(cin>>n)
        cout<<get(n)<<endl;
#ifdef xiaofan
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#endif
    return 0;
}

L

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <limits>
#include <set>
#include <map>
#include <functional>
#include <inttypes.h>
#include <stdint.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
using namespace std;
typedef long long ll;
#ifndef PRId64
#define PRId64 "lld"
#endif
#ifndef SCNd64
#define SCNd64 "lld"
#endif
#define SC sc()
#define PT pr()
#define FORi(i,b,e) for (int i = (b), _ = (e); i < _; ++i)
#define FORe(i,b,e) for (int i = (b), _ = (e); i <= _; ++i)
#define FORre(i,b,e) for (int i = (b), _ = (e); i >= _; --i)
static int sc_ret = 0;
struct sc
{
    sc& operator()(char& v) { v = sc_ret = getchar(); return *this; }
    sc& operator()(int& v) { sc_ret = read(v); return *this; }
    sc& operator()(unsigned& v) { sc_ret = scanf("%u", &v); return *this; }
    sc& operator()(double& v) { sc_ret = scanf("%lf", &v); return *this; }
    sc& operator()(char* v) { sc_ret = scanf("%s", v); return *this; }
    sc& operator()(string& v) { sc_ret = (bool)(cin >> v); return *this; }
    sc& operator()(ll& v) { sc_ret = read(v); return *this; }
    sc& ch(char& v) { sc_ret = scanf(" %c", &v); return *this; }
    sc& gets(char* v) { sc_ret = fgets(v, INT_MAX, stdin) != 0; v[strlen(v) - 1] = 0; return *this; }
    operator bool() const { return sc_ret > 0; }
    template <typename T>
    int read(T& v)
    {
        T x = 0, k = 1;
        int c = getchar();
        while (c < '0' || c > '9')
        {
            if (c == '-') k = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c - 48), c = getchar();
        v = x * k;
        return c;
    }
};
struct pr
{
    pr& ln() { putchar('\n'); return *this; }
    pr& operator()(char v) { putchar(v); return *this; }
    pr& operator()(int v) { write(v); return *this; }
    pr& operator()(double v) { printf("%.2f", v); return *this; }
    pr& operator()(const char* fmt, double v) { printf(fmt, v); return *this; }
    pr& operator()(const char* v) { printf("%s", v);return *this; }
    pr& operator()(string v) { printf("%s", v.c_str());return *this; }
    pr& operator()(ll v) { write(v);return *this; }
    template <typename T>
    void write(T v)
    {
        int cnt = 0; char c[23];
        if (v == 0)
        {
            putchar('0');
            return;
        }
        if (v < 0) putchar('-'), v = -v;
        while (v) c[++cnt] = (v % 10) + 48, v /= 10;
        while (cnt > 0) putchar(c[cnt--]);
    }
    template <typename T>
    void ln(T* arr, int size)
    {
        if (size > 0)
        {
            (*this)(arr[0]);
            for (int i = 1; i < size; ++i)
            {
                putchar(' ');
                (*this)(arr[i]);
            }
            putchar('\n');
        }
    }
    template <typename T>
    void muln(T* arr, int size)
    {
        for (int i = 0; i < size; ++i)
        {
            (*this)(arr[i]);
            putchar('\n');
        }
    }
};
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 10000 + 10;
const int maxm = 2000 + 10;
int ans[maxn];
typedef const char* CSTR;
struct scmp
{
    bool operator()(CSTR a, CSTR b) const
    {
        return strcmp(a, b) < 0;
    }
};
std::map<CSTR, int, scmp> sort_m;
int same_pre(CSTR a, CSTR b)
{
    for (CSTR p = a; ; ++p, ++b)
    {
        if (*p != *b)
        {
            return (int)(p - a);
        }
    }
    return 0;
}
void dfs(vector<int> edge[], char node[], char vis[], char st_node[], int cur, int last, int deep)
{
    if (vis[cur])
    {
        return;
    }
    vis[cur] = 1;
    *st_node = node[cur];
    sort_m[st_node] = 0;
    std::map<CSTR, int, scmp>::iterator it = sort_m.find(st_node),
        it_pre = it, it_next = it;
    it_pre--; it_next++;
    int add = 0;
    if (it_pre != it && it_pre != sort_m.end())
    {
        add = same_pre(it_pre->first, it->first);
    }
    if (it_next != sort_m.end())
    {
        add = std::max(add, same_pre(it_next->first, it->first));
    }
    int sum = last + deep - add;
    ans[cur] = sum;
    for (vector<int>::iterator vit = edge[cur].begin(); vit!= edge[cur].end(); ++vit)
    {
        dfs(edge, node, vis, st_node - 1, *vit, sum, deep + 1);
    }
    sort_m.erase(it);
    vis[cur] = 0;
}
int main()
{
    int t;
    SC(t);
    FORi(c, 0, t)
    {
        vector<int> edge[maxn];
        char node[maxn] = "";
        char vis[maxn] = "";
        char st_node[maxn * 2] = "";
        sort_m.clear();
        int n;
        SC(n);
        FORi(i, 1, n)
        {
            int x, y;
            SC(x)(y);
            edge[x-1].push_back(y-1);
            edge[y-1].push_back(x-1);
        }
        SC(node);
        dfs(edge, node, vis, st_node + maxn, 0, 0, 1);
        FORi(i, 0, n)
        {
            PT(ans[i]).ln();
        }
    }
    return 0;
}