---
tags: IOICamp
---

# Day1 趣味賽

:::spoiler Description
:::

:::spoiler Scoreboard
:::

:::spoiler pA & pB
:::

:::spoiler pC & pD
:::

:::spoiler pE & pF & pG
:::

:::spoiler pH & pI
:::

:::spoiler pJ
:::

:::spoiler pK & pL & pM
:::

:::spoiler pN
:::

:::spoiler pO*
:::

:::spoiler pP
:::

:::spoiler pQ**
:::

---

[TOC]

#### **pA & pB. Yuuki 數 (除蟲題)**

:::spoiler Solution (Edit Distance = 8)

#include <iostream>
#include <string>
using namespace std;

int n, h ,t;

void go() {
    cin >> n;
    h = n/100-(n/1000)*10;
    t = n/1000-(n/10000)*10;
    if ( h%2==0 && (t==2||t==5||t==8)){
        cout << "890916" <<endl;
    }
    else if (h%3==0 && t%4!=0 && (h+t)%5==0){
        cout << "890916" << endl;
    }
    else
        cout << "0" <<endl;
}

int main(){
    int T; cin >> T;
    while (T--) {
        go();
    }
}

:::

:::spoiler Solution (Edit Distance = 4)

#include <iostream>
#include <string>
using namespace std;

int n, h ,t;

void go() {
    cin >> n;
    h = n/100-(n/1000)*10;
    t = n/1000-(n/10000)*10;
    if ( h%2==0 && t%3==2 //||5||8
    ){
        cout << "890916" <<endl;
    }
    else if (h%3==0 && t%4!=0 && (h+t)%5==0){
        cout << "890916" << endl;
    }
    else
        cout << "0" <<endl;
}

int main(){
    int T; cin >> T;
    while (T--) {
        go();
    }
}

:::

:::spoiler Solution (Edit Distance = 4)

#include <iostream>
#include <string>
using namespace std;

int n, h ,t;

void go() {
    cin >> n;
    h = n/100-(n/1000)*10;
    t = n/1000-(n/10000)*10;
    if ( h%2==0 && t%3==2||0||0){
        cout << "890916" <<endl;
    }
    else if (h%3==0 && t%4!=0 && (h+t)%5==0){
        cout << "890916" << endl;
    }
    else
        cout << "0" <<endl;
}

int main(){
    int T; cin >> T;
    while (T--) {
        go();
    }
}

:::

#### **pC & pD. 次方和 (除蟲題)**

:::spoiler Solution (Edit Distance = 6)

#include <iostream>
#include <cmath>
using namespace std;

struct cal_int {
    string s;
    string t;
};

inline cal_int f() {
    cal_int cal_ret;
    int ret = 880301;
    cal_ret.s = "IOICamp 2020";
    cal_ret.t = "Yuuki <3";
    return cal_ret;
}

int cal_pow(int aa, int bb) {
    int ret = 1;
    for (int i = 0; i < bb; i += 1) {
        ret *= aa;
    }
    return ret;
}

int main () {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << int(cal_pow(a, b) + cal_pow(c, d) + 0.1) << endl;
}

:::

:::spoiler Solution (Edit Distance = 4)

#include <iostream>
#include <cmath>
using namespace std;

struct cal_int {
    string s;
    string t;
};

inline cal_int f() {
    cal_int cal_ret;
    int ret = 880301;
    cal_ret.s = "IOICamp 2020";
    cal_ret.t = "Yuuki <3";
    return cal_ret;
}

int cal_pow(int aa, int bb) {
    int ret = 1;
    for (int i = 0; i < aa; i -= 1) {
        ret *= ret;
    }
    return ret;
}

int main () {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << int(//cal_
    pow(a, b) + //cal_
    pow(c, d) + 0.1) << endl;
}

:::

:::spoiler Solution (Edit Distance = 4) (CE)

#include <iostream>
#include <cmath>
using namespace std;

struct cal_int {
    string s;
    string t;
};

#define cal_
int f() {
    cal_int cal_ret;
    int ret = 880301;
    cal_ret.s = "IOICamp 2020";
    cal_ret.t = "Yuuki <3";
    return cal_ ret;
}

int cal_pow(int aa, int bb) {
    int ret = 1;
    for (int i = 0; i < aa; i -= 1) {
        ret *= ret;
    }
    return ret;
}

int main () {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << int(cal_ pow(a, b) + cal_ pow(c, d) + 0.1) << endl;
}

:::

#### **pE & pF & pG. 堅果好吃 (除蟲題)**

:::spoiler Solution (Edit Distance = 9)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int maxnut, *x;
int pos = 0, n;
int CalcThemaxnut();
int main() {
    if (x == NULL) x = (int*)malloc(1010 * sizeof (int));
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            while (scanf("%d", &x[pos ++]) == 1) {
                maxnut = 0;
                pos -= i % 2;
                CalcThemaxnut();
                break;
            }
        }
        break;
    }
    printf("%d\n", maxnut);
    exit(0);
}

int CalcThemaxnut() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < pos; ++ i) {
        maxnut += x[i];
        assert(cnt1 == i); 
        assert(cnt2 == i); 
        cnt1 += 1;
        cnt2 += 1;
    }
    assert(cnt1 == pos);
    assert(cnt2 == pos);
    return maxnut;
}

:::

:::spoiler Solution (Edit Distance = 5)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int maxnut, *x;
int pos = 0, n;
int CalcThemaxnut();
int main() {
    if (x == NULL) x = (int*)malloc(1010 * sizeof (int));
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            while (scanf("%d", &x[pos ++]) == 1) {
                maxnut = 0;
                CalcThemaxnut();
                break;
            }
        }
        break;
    }
    printf("%d\n", maxnut);
    exit(0);
}

int CalcThemaxnut() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < pos; ++ i) {
        i&1 ? : maxnut += x[i];
        assert(cnt1 == i); 
        assert(cnt2 == i); 
        cnt1 += 1;
        cnt2 += 1;
    }
    assert(cnt1 == pos);
    assert(cnt2 == pos);
    return maxnut;
}

:::

:::spoiler Solution (Edit Distance = 5)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int maxnut, *x;
int pos = 0, n;
int CalcThemaxnut();
int main() {
    if (x == NULL) x = (int*)calloc(9010 , sizeof (int));
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            while (scanf("%d", &x[pos ++]) == 1) {
                maxnut = 0;
                CalcThemaxnut();
                break;
            }
        }
        break;
    }
    printf("%d\n", maxnut);
    exit(0);
}

int CalcThemaxnut() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < pos; ++ i) {
        maxnut += x[i*2];
        assert(cnt1 == i); 
        assert(cnt2 == i); 
        cnt1 += 1;
        cnt2 += 1;
    }
    assert(cnt1 == pos);
    assert(cnt2 == pos);
    return maxnut;
}

:::

:::spoiler Solution (Edit Distance = 3, Only on Easy & Mid)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int maxnut, *x;
int pos = 0, n;
int CalcThemaxnut();
int main() {
    if (x == NULL) x = (int*)malloc(4010 * sizeof (int));
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            while (scanf("%d", &x[pos ++]) == 1) {
                maxnut = 0;
                CalcThemaxnut();
                break;
            }
        }
        break;
    }
    printf("%d\n", maxnut);
    exit(0);
}

int CalcThemaxnut() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < pos; ++ i) {
        maxnut += x[i*2];
        assert(cnt1 == i); 
        assert(cnt2 == i); 
        cnt1 += 1;
        cnt2 += 1;
    }
    assert(cnt1 == pos); 
    assert(cnt2 == pos); 
    return maxnut;
}

:::

:::spoiler Solution (Edit Distance = 3)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

const int xsize = 4010;
int maxnut, *x;
int pos = 0, n;
int CalcThemaxnut();
int main() {
    if (x == NULL) x = (int*)malloc(xsize);
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++ i) {
            while (scanf("%d", &x[pos ++]) == 1) {
                maxnut = 0;
                CalcThemaxnut();
                break;
            }
        }
        break;
    }
    assert(xsize == 4010);
    printf("%d\n", maxnut);
    exit(0);
}

int CalcThemaxnut() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < pos; ++ i) {
        maxnut += x[i];
        assert(cnt1 == i); 
        assert(cnt2 == i); 
        cnt1 += 1;
        cnt2 += 1;
    }
    assert(cnt1 == pos); 
    assert(cnt2 == pos); 
    return main();
}

:::

#### **pH & pI. 季節 (除蟲題)**

:::spoiler Solution (Edit Distance = 6)

#include <iostream>  
using namespace std;  

int main(){  
    int N;
    cin>>N;
    if(N==12||N<=2)
    cout<<"Winter"<<endl;
    else if(3<=N<=4,N<=5)
    cout<<"Spring"<<endl;
    else if(6<=N<=7,N<=8)
    cout<<"Summer"<<endl;
    else
    cout<<"Autumn"<<endl;    
}

:::

:::spoiler Solution (Edit Distance = 4)

#include <iostream>  
using namespace std;  

int main(){  
    int N;
    cin>>N;
    if(1<=1&N==12|N<=2)
    cout<<"Winter"<<endl;
    else if(3<=N<=4,N<=5)
    cout<<"Spring"<<endl;
    else if(6<=N<=7,N<=8)
    cout<<"Summer"<<endl;
    else
    cout<<"Autumn"<<endl;    
}

:::

:::spoiler Solution (Edit Distance = 3)

#include <iostream>  
using namespace std;  

int main(){  
    int N;
    cin>>N;
    if(1<=N<=12,N%12<=2)
    cout<<"Winter"<<endl;
    else if(3<=N<=4,N<=5)
    cout<<"Spring"<<endl;
    else if(6<=N<=7,N<=8)
    cout<<"Summer"<<endl;
    else
    cout<<"Autumn"<<endl;    
}

:::

#### **pJ. 加法大師 - (駭客題)**

:::spoiler Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
	cout << 5 << endl;
	int left = 0;
	for (int t = 0; t < 5; ++t) {
		srand(1579513020 + 50 + t); // 2020/01/20 17:37
		set<ll> st; //randomly generate 5 numbers
		
		for (int i = 0; i < left; ++i) rand();
		while (st.size() != 5) {
			++left;
			st.insert(rand() % 1000 + 3000);
		}
		
		ll ans = 1;
		for (auto x : st) ans *= x;
	
		cout << ans << " " << ans << " " << 3*ans << endl;
	}
	return 0;
}

:::

:::spoiler Solution (CE)

#include <bits/stdc++.h>
using namespace std;

#define _ <<' '<<

int main () {
    int T = 5;
    cout << T << endl;
    long long t = /*time(NULL)*/, dl = 3, a;
    set<int> st;
    for(int i = 0; i < T; i++) {
        srand(t+dl+i);
        for(int j = 0; j < i; j++) {
            st.clear();
            while (st.size() != 5)
                st.insert(rand() % 1000 + 3000);
        }
        st.clear();
        while (st.size() != 5)
            st.insert(rand() % 1000 + 3000);
        a = 1;
        for (const int &x: st) a *= x;
        cout << a _ a _ a << endl;
    }
}

:::

:::spoiler Solution (WA)

#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/syscall.h>
using namespace std;

#define ll long long

int main() {
	srand(syscall(201, 0));
	
	cout << 5 << "\n";
	
	for (int i = 0; i < 5; ++i) {
		set<ll> st; //randomly generate 5 numbers
		while (st.size() != 5) {
			st.insert(rand() % 1000 + 3000);
		}
		
		ll ans = 1;
		for (auto x : st) ans *= x;
		
		ll a = ans, b = ans, c = 3*ans;
		
		for (ll mod: st) {
			if ((a % mod + b % mod) % mod != c % mod) {
				// cout << "Noooo" << endl;
				return 0;
			}
		}
		// cout << "Yuuki" << endl;
		
		cout << a << " " << b << " " << c << "\n";
	}
	
	return 0;
}

:::

#### **pK & pL & pM. 假解構造 (駭客題)**

:::spoiler Solution (Sum ~ 25000, Randomize)

#include <bits/stdc++.h>
using namespace std;

int main() {
	srand(time(NULL));
//	freopen("test.in", "w", stdout);
	int n = 1000, m = 8000;
	set<pair<int, int>> ans;
	while (m--) {
		int a = rand() % n, b = rand() % n;
		if (a == b) continue;
		if (a > b) swap(a, b);
		ans.insert({a+1, b+1});
		// cout << a + 1 << " " << b + 1 << "\n";
	}
	
	cout << n << " " << ans.size() << "\n";
	for (auto x : ans) cout << x.first << " " << x.second << "\n";
	return 0;
}

:::

:::spoiler Solution (Sum = 125750)

#include <cstdio>
main() {
	puts("1000 125250");
	for (int i = 1; i < 1000; i += 2)
		for (int j = i/2; j < 500; ++j)
			printf("%d %d\n", i, 2*j+2);
}

:::

:::spoiler Solution (Sum = 125750, one line [c11])

main(){puts("1000 125250");for(int i=1;i<1e3;i+=2)for(int j=i/2;j<500;++j)printf("%d %d\n", i, 2*j+2);}

:::

#### **pN. 殿壬愛獨立 (駭客題)**

:::spoiler Solution

#include <stdio.h>

int main() {
	puts("99 98");
	for (int i = 1; i < 99; ++i)
		printf("%d %d\n", i, i+1);
}

:::

#### **pO. 簡單圖構造(構造題)**

:::spoiler Solution

#include <cstdio>

int main() {
	int n; scanf("%d", &n);
	printf("%d\n", (n == 2 ? -1 : n*(n-1)/2-n/2));
	
	for (int i = 1; i <= n; ++i) {
		for (int j = i+1; j <= n; ++j) {
			if (i + j == n + (~n & 1)) continue;
			printf("%d %d\n", i, j);
		}
	}
}

:::

#### **pP. 連續整數(構造題)**

:::spoiler Solution

// 27828, 19
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//bool is[100000005]={0};
int GCD(int a,int b)
{
    if(b==0) return a;
    return GCD(b,a%b);
}
int main()
{
    int i,j,k,last,ok,ok2;
    /*for(i=2;i<=100000000;i++)
    {
        if(is[i]==0)
        {
            //printf("%d\n",i);
            if(i>3)
            {
                ok=1;
                for(j=last+1;j<i;j++)
                {
                    ok2=0;
                    for(k=last+1;k<i;k++)
                    {
                        if(j==k) continue;
                        if(GCD(j,k)!=1) ok2=1;

                    }
                    ok=ok&&ok2;
                }
                if(ok) printf("%d %d\n",last+1,k);
            }
            for(j=i+i;j<=100000000;j+=i)
            {
                is[j]=1;
            }
            last=i;
        }
    }*/
    printf("%d %d\n",27828,27847-27828);
    
    return 0;
}

:::

#### **pQ. 三角旅行 (構造題)**

:::spoiler Solution

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

long long MOD=1e9+7;
long long F[1000005];
long long Pow(long long a,long long b)
{
    if(b==0) return 1;
    long long t=Pow(a,b/2);
    t*=t;
    t%=MOD;
    if(b%2) t*=a;
    return t%MOD;
}
int main ()
{
    srand(time(NULL));
    long long N,x,y,z,i,a,b,c;
    scanf("%lld",&N);
    if(N==1) printf("1 1 1 \n");
    else
    {
        F[0]=1;
        F[1]=1;
        for(i=2;i<=N;i++) F[i]=(F[i-1]+F[i-2])%MOD;
        z=rand()%1000+5;
        y=rand()%1000+5;
        x=Pow(F[N-1],MOD-2)*(y*F[N]%MOD+MOD-z*F[N-2]%MOD)%MOD;
        printf("%lld %lld %lld\n",x,y,z);
        for(i=1;i<=N;i++)
        {
            a=x-y;
            b=y-z;
            c=x-z;
            //printf("%lld %lld %lld\n",a%MOD,b%MOD,c%MOD);
            x=a;
            y=b;
            z=c;
        }
    }

    return 0;
}

:::