Contest 16

contest

A hesorchen

//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define MAX 200010
#define mod 1000000007
int main()
{
    ll a, b;
    cin >> a >> b;
    int ans = 0;
    while (a <= b)
    {
        a *= 3;
        b *= 2;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B hesorchen

//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define MAX 200010
#define mod 1000000007
int p[MAX];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> p[i];
    sort(p, p + n);
    cout << p[n / 2] << endl;
    return 0;
}

C hesorchen

//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define MAX 105
#define mod 1000000007
int p[MAX];
int tong[MAX];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        fill(p, p + MAX, 0);
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> p[i];
        sort(p, p + n);
        int f = 0;
        for (int i = 1; i < n; i++)
            if (p[i] - p[i - 1] <= 1)
            {
                f = 1;
                break;
            }
        if (!f)
        {
            printf("1\n");
            continue;
        }
        else
        {
            printf("2\n");
        }
    }
    return 0;
}

D 541907230304

//#include<bits/stdc++.h>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF  0x7fffffffffff//ffff
#define M 612345
double x[M],y[M],l,h,s,x1, z1, x2, y2, x3, y3, x4, y4;
int main(void){
    while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&z1,&x2,&y2,&x3,&y3,&x4,&y4)!=EOF){
        x[0] = x1; x[1] = x2; x[2] = x3; x[3] = x4;
        y[0] = z1; y[1] = y2; y[2] = y3; y[3] = y4;
        sort(x, x + 4);
        sort(y, y + 4);
        l = fabs(x2 - x1) + fabs(x4 - x3) - (x[3] - x[0]);
        h = fabs(y2 - z1) + fabs(y4 - y3) - (y[3] - y[0]);
        s = l * h;
         if (l <= 0 || h <= 0)
            s = 0.00;
        printf("%.2f\n", s);
}
    return 0;
}

E 541907230304

#include<bits/stdc++.h>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF  0x7fffffffffff//ffff
#define M 612345
ll t;
double a,b,c,ans,x1,z1,x2,y2;
int main(void){
    cin>>t;
    while(t--){
        cin>>x1>>z1>>x2>>y2;
        a = sqrt(x1 *x1 +z1*z1);
        b = sqrt(x2*x2+y2*y2);
        c = sqrt((x1-x2)*(x1 - x2) +(z1-y2)*(z1-y2));
        ans = (a*a+b*b-c*c)/(2*a*b);
        ans =acos(ans)*180/3.1415926;
        printf("%.2f\n",ans);
    }
    return 0;
}

F 541907230304

#include<bits/stdc++.h>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF  0x7fffffffffff//ffff
#define M 112300
ll a[M],ans = 0,n,m;
bool check(ll x){
    if(x==2)
    return true;
    for(ll i = 2;i*i <=x;i++){
        if(x %i==0)
        return false;
    }
    return true;
}
int main(void){
    cin>>n>>m;
    if(n < m)
    swap(n,m);
    ll j = 0;
    for(ll i = 1;i *i <= m;i++){
        if(m %i==0){
            a[j] = i;
            j++;
            if(i*i!=m){
            a[j] = m/i;
            j++;
        }
        }
    }
    for(ll i = 0;i < j;i++){
        if(n % a[i]==0&&check(a[i]))
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

G 541907190117

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define zero(a) memset(a, 0, sizeof(a))
#define INF(a) memset(a, 0x3f, sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, ll> P2;
const double pi = acos(-1.0);
const double eps = 1e-7;
const ll MOD =  1000000007LL;
const int INF = 0x3f3f3f3f;
const int _NAN = -0x3f3f3f3f;
const double EULC = 0.5772156649015328;
const int NIL = -1;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int maxn = 1e5+10;
ll arr[maxn];
int main(void) {
    ll n, m;
    scanf("%lld%lld", &n, &m);
    ll t, num;
    for (int i = 0; i<n; ++i) {
        scanf("%lld", &arr[i]);
        if (!i)
            t = arr[i]/2;
        else 
            t = arr[i]/2/(__gcd(arr[i]/2, t))*t;
    }
    for (int i = 0; i<n; ++i)
        if (!(t%arr[i])) {
            printf("0\n");
            return 0;
        }
    t = m/t;
    if (t&1)
        ++t;
    printf("%lld\n", t/2);
    return 0;
}

H 541907230304

#include<bits/stdc++.h>
#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF  0x7fffffffffff//ffff
#define M 112300
ll a[20][M],maxx,n,x,t;
int main(void){ 
    while(cin>>n&&n){
        memset(a,0,sizeof(a));
        maxx = 0;
        for(ll i = 0;i < n;i++){
            cin>>x>>t;
            a[x][t]++;
            maxx = max(maxx,t);
        }
        for(ll j = maxx - 1;j >= 0;j--){
        a[0][j] +=max(a[0][j+1],a[1][j+1]);
        for(ll i = 1;i < 11;i++)
        a[i][j] +=max(max(a[i][j+1],a[i-1][j+1]),a[i+1][j+1]);
    }
    cout<<a[5][0]<<endl;
    }
    return 0;
}

I 541907190117

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define endl '\n'
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define zero(a) memset(a, 0, sizeof(a))
#define INF(a) memset(a, 0x3f, sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define _test printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, ll> P2;
const double pi = acos(-1.0);
const double eps = 1e-7;
const ll MOD =  1000000007LL;
const int INF = 0x3f3f3f3f;
const int _NAN = -0x3f3f3f3f;
const double EULC = 0.5772156649015328;
const int NIL = -1;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int maxn = 1e6+10;
queue<int> pos, clears;
char str[maxn];
int main(void) {
    ll t, n, k;
    scanf("%lld", &t);
    while(t--) {
        scanf("%lld%lld%s", &n, &k, str);
        int cnt = 0, pos = -1;
        for (int i = 0; i<n && k; ++i) {
            if (str[i] == '0') {
                if (i-cnt <= k) {
                    k -= i-cnt;
                    str[i] = '1';
                }
                else {
                    pos = i-k;
                    str[i] = '1';
                    break;
                }
                ++cnt;
            } 
        }
        for (int i = 0; i<n; ++i) {
            if (cnt) {
                --cnt;
                putchar('0');
            }
            else if (i == pos)
                putchar('0');
            else 
                putchar(str[i]);
        }
        putchar(endl);
    }
    return 0;
}

J rubbish_is_me

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<sstream>
#include<string>
#include<string.h>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define E (2.71828182)
#define PI (3.1415926535898)
#define mem(a,b)    memset(a,b,sizeof(a))
#define mod 1000000007
#include<set>
#define gc getchar
#define debug(a) cout << "*" << a << "*" << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<float, int> P;
const int N = 1000000;
const long long  MAX_V = 5005, INF = 2147483647, MOD = 998244353;
int n, m, gt[100005], tot, dis[1000005], a, b;
char op;
set<int> st;
int find(int x)
{
    return x == dis[x] ? x : dis[x] = find(dis[x]);
}
void uni(int x, int y)
{
    int xx = find(x);
    int yy = find(y);
    if (xx != yy)
    {
        dis[xx] = yy;   
    } 
}
int main()
{
    int t = 1;
    while (~scanf("%d%d", &n, &m) && (n || m))
    {
        st.clear();
        tot = n;
        for (int i = 0; i < 100000; i++) gt[i] = i;
        for (int i = 0; i < 1000000; i++)   dis[i] = i;
        for (int i = 0; i < m; i++)
        {
            scanf(" %c", &op);
            if (op == 'M')
            {
                scanf("%d%d", &a, &b);
                uni(gt[a], gt[b]);
            }
            else
            {
                scanf("%d", &a);
                gt[a] = tot++;
            }
        }
        for (int i = 0; i < n; i++)
        {
            st.insert(find(gt[i]));
        }
        printf("Case #%d: %d\n", t, st.size());
        t++;
    }
}

K rubbish_is_me

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<sstream>
#include<string>
#include<string.h>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define ls (k << 1)
#define rs (k << 1 | 1)
#define E (2.71828182)
#define PI (3.1415926535898)
#define mem(a,b)    memset(a,b,sizeof(a))
#define mod 1000000007
#include<set>
#define gc getchar
#define debug(a) cout << "*" << a << "*" << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<float, int> P;
const int N = 1000000;
const long long  MAX_V = 5005, INF = 2147483647, MOD = 998244353;
struct seg_tree{
    int l, r, mark, mx;
}tk[4000005];
struct node{
    int l, r, od;
    friend bool operator < (node a, node b)
    {
        if (a.r != b.r) return a.r < b.r;
        return a.l > b.l;
    }
}seg[1000005];
int n, k, d[1000005], tot;
void push_up(int k)
{
    tk[k].mx = max(tk[ls].mx, tk[rs].mx);
}
void push_down(int k)
{
    if (tk[k].mark)
    {
        tk[ls].mark += tk[k].mark;
        tk[rs].mark += tk[k].mark;
        tk[ls].mx += tk[k].mark;
        tk[rs].mx += tk[k].mark;
        tk[k].mark = 0;
    }
}
void build(int k, int l, int r)
{
    tk[k].l = l, tk[k].r = r;
    tk[k].mark = 0;
    if (l == r) 
    {
        tk[k].mx = 0;
        return;
    }
    int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(k);
}
void update(int k, int l, int r, int d)
{
    if (l <= tk[k].l && tk[k].r <= r)
    {
        tk[k].mark += d;
        tk[k].mx += d;
        return ;
    }
    push_down(k);
    int mid = tk[k].l + tk[k].r >> 1;
    if (l <= mid)   update(ls, l, r, d);
    if (r > mid)    update(rs, l, r, d);
    push_up(k);
}
int query(int k, int l, int r)
{
    if (l <= tk[k].l && tk[k].r <= r)
    {
        return tk[k].mx;
    }
    push_down(k);
    int mid = tk[k].l + tk[k].r >> 1;
    int resl = 0, resr = 0;
    if (l <= mid)   resl = query(ls, l, r);
    if (r > mid)    resr = query(rs, l, r);
    return max(resl, resr);
}
int main()
{
    scanf("%d%d", &n, &k);
    build(1, 1, 1000000);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &seg[i].l, &seg[i].r);
        seg[i].od = i + 1;
    }
    sort(seg, seg + n);
    for (int i = 0; i < n; i++)
    {
        if (query(1, seg[i].l, seg[i].r) < k)
        {
            update(1, seg[i].l, seg[i].r, 1);
        }
        else
        {
            d[tot++] = seg[i].od;
        }
    }
    printf("%d\n", tot);
    for (int i = 0; i < tot; i++)
        printf("%d%c", d[i], i == tot - 1 ? '\n' : ' ');
}

L lnkkerst

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int read() {
    int ret, fl = 1;
    char ch;
    while(!isdigit(ch = getchar())) (ch == '-') && (fl = -1);
    for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
    return ret * fl;
}
void print(int x) {
    if(x < 0) { putchar('-'); x *= -1; }
    if(x > 9) { print(x / 10); }
    putchar(x % 10 + '0');
}
struct Trie {
    int go[26], end, fail;
} trie[500010];
char s[1000010];
int cnt = 0;
void insert(char *str) {
    int l = strlen(s);
    int x = 0;
    for(int i = 0; i < l; i++) {
        int k = str[i] - 'a';
        if(!trie[x].go[k])
            trie[x].go[k] = ++cnt;
        x = trie[x].go[k];
    }
    ++trie[x].end;
}
void init_fail() {
    trie[0].fail = 0;
    queue<int > q;
    for(int i = 0; i < 26; ++i)
        if(trie[0].go[i]) {
            trie[trie[0].go[i]].fail = 0;
            q.push(trie[0].go[i]);
        }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = 0; i < 26; ++i) {
            if(trie[u].go[i]) {
                trie[trie[u].go[i]].fail = trie[trie[u].fail].go[i];
                q.push(trie[u].go[i]);
            }
            else trie[u].go[i] = trie[trie[u].fail].go[i];
        }
    }
}
int query(char *s) {
    int l = strlen(s);
    int now = 0, ret = 0;
    for(int i = 0; i < l; ++i) {
        now = trie[now].go[s[i] - 'a'];
        for(int t = now; t && trie[t].end != -1; t = trie[t].fail) {
            ret += trie[t].end;
            trie[t].end = -1;
        }
    }
    return ret;
}
int solve() {
    memset(trie, 0, sizeof(trie));
    for(int n = read(); n--; scanf("%s", s), insert(s));
    scanf("%s", s);   
    init_fail();
    cout << query(s) << endl;
    return 0;
}
int main() {
    int t = read();
    while(t--) solve();
    return 0;
}

M _Wallace_

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace fastIO_int{
    int get_int()
    {
        int x=0,f=1;char c=getchar();
        while(c<'0'||c>'9')
        {
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
            x=x*10+c-'0',c=getchar();
        return f*x;
    }
    void read(){}
    template<class T1,class ...T2>
    void read(T1 &i,T2&... rest)
    {
        i=get_int();
        read(rest...);
    }
    void put_int(int x)
    {
        if(x<0)putchar('-'),x=-x;
        if(x>9)put_int(x/10);
        putchar(x%10+'0');
    }
    void write(){}
    template<class T1,class ...T2>
    void write(T1 i,T2... rest)
    {
        put_int(i),putchar(' ');
        write(rest...);
    }
};
const int N=2e4+5;
int T[N<<5],L[N<<5],R[N<<5];
int father[N<<5],depth[N<<5];
int total=0;
#define mid ((l+r)>>1)
int n,m;
int build(int l,int r)
{
    int rt=++total;
    if(l==r)
        return father[rt]=l,rt;
    L[rt]=build(l,mid);
    R[rt]=build(mid+1,r);
    return rt;
}
int mrg(int pre,int l,int r,int x,int f)
{
    int rt=++total;
    L[rt]=L[pre],R[rt]=R[pre];
    if(l==r)
    {
        father[rt]=f,depth[rt]=depth[pre];
        return rt;
    }
    if(x<=mid) L[rt]=mrg(L[pre],l,mid,x,f);
    else R[rt]=mrg(R[pre],mid+1,r,x,f);
    return rt;
}
void inc(int rt,int l,int r,int p)
{
    if(l==r) {depth[rt]++;return;}
    if(p<=mid) inc(L[rt],l,mid,p);
    else inc(R[rt],mid+1,r,p);
}
int qry(int rt,int l,int r,int p)
{
    if(l==r) return rt;
    if(p<=mid) return qry(L[rt],l,mid,p);
    else return qry(R[rt],mid+1,r,p);
}
int find(int ver,int x)
{
    int fa=qry(ver,1,n,x);
    if(x==father[fa]) return fa;
    return find(ver,father[fa]);
}
signed main()
{
    using namespace fastIO_int;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(T,0,sizeof(T));
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        T[0]=build(1,n);
        for(register int i=1;i<=m;i++)
        {
            int op,x,y;
            int px,py;
            read(op);
            if(op==1)
            {
                read(x,y),T[i]=T[i-1];
                px=find(T[i],x),py=find(T[i],y);
                if(father[px]!=father[py])
                {
                    if(depth[px]>depth[py]) swap(px,py);
                    T[i]=mrg(T[i-1],1,n,father[px],father[py]);
                    if(depth[px]==depth[py])
                        inc(T[i],1,n,father[py]);
                }
            }
            if(op==2)
            {
                read(x);
                T[i]=T[x];
            }
            if(op==3)
            {
                read(x,y),T[i]=T[i-1];
                px=find(T[i],x),py=find(T[i],y);
                if(father[px]==father[py])
                    puts("1");
                else puts("0");
            }
        }
    }
    return 0;
}