akhauriyash/Code-Regression huggingface dataset:
/*input
6
3 3 3 2 2 2
*/
#include <bits/stdc++.h>
using namespace std;
#define TEMPLATE

#ifdef TEMPLATE
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

#endif

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	vi sk(N);
	for (int i = 0; i < N; ++i)
		cin >> sk[i];
	set<int> setas;
	map<int, int> kiek;

	for (int i = 0; i < N; ++i)
	{
		auto it = setas.upper_bound(sk[i]);
		if (it == setas.begin()) {
			setas.insert(sk[i]);
			kiek[sk[i]]++;
		}
		else if (it == setas.end()) {
			if (setas.empty()) {
				setas.insert(sk[i]);
				kiek[sk[i]]++;
			}
			else if (*(--setas.end()) == sk[i]) {
				if (setas.size() == 1) {
					kiek[sk[i]]++;
				} else {
					auto itas = --setas.end();
					itas--;
					kiek[*itas]--;
					if (!kiek[*itas])
						setas.erase(itas);

					setas.insert(sk[i]);
					kiek[sk[i]]++;
				}
			}
			else {
				kiek[*(--setas.end())]--;

				if (!kiek[*(--setas.end())])
					setas.erase(--setas.end());

				setas.insert(sk[i]);
				kiek[sk[i]]++;
			}
		}
		else {
			it--;
			if(*it == sk[i]){
				if(it == setas.begin()){
					kiek[sk[i]]++;
					continue;
				} else {
					it--;
				}
			}
			kiek[*it]--;
			if (!kiek[*it])
				setas.erase(it);

			setas.insert(sk[i]);
			kiek[sk[i]]++;
		}
	}
	int ats = 0;
	for (auto u : kiek) {
		ats += u.y;
	}
	printf("%d\n", ats);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/



Measured memory_bytes: 9856
#include <iostream>
using namespace std;
int main()
{
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  int mx = max(max(A, B), C);
  int sum = A + B + C - mx;
  for (int i = 0; i < K; i++)
    mx *= 2;
  cout << sum + mx << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
typedef long long ll;



int main()
{
    ll N, K;
    cin >> N >> K;
    vector<ll> V;
    for (int i=0;i<N;++i)
    {
        ll temp;
        cin >> temp;
        V.push_back(temp);
    }
    for (int i=K;i<N;++i)
    {
        if (V[i-K]<V[i]) {
            cout << "Yes" << endl;

        }
        else {
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 5268
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
use proconio::{fastout, input};
#[fastout]
fn main() {
    input! {
        w: f64,
        h: f64,
        x: f64,
        y: f64
    }
    let rec: f64 = w * h / 2.0;

    if x == w / 2.0 && y == h / 2.0 {
        println!("{} {}", rec, 1);
    } else {
        println!("{} {}", rec, 0);
    }
}


Measured memory_bytes: 2200
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b, c; cin >> a >> b >> c;
    int d = a ^ b ^ c;
    if ((d == a || d == b || d == c) ^ (a == b && b == c)) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    string t;
    string s = "CODEFESTIVAL2016";
    int ans = 0;
    cin >> t;
    rep(i, t.size()) ans += t[i] != s[i];

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;

int main() {
  string str;
  while(getline(cin,str)) {
    for(int j=0;j<26;j++) {
      if(str.find("the")!=string::npos||str.find("this")!=string::npos||str.find("that")!=string::npos) {
        cout << str << endl;
        break;
      }
      for(unsigned int i=0;i<str.size();i++) {
        if(str[i] <= 'z' && 'a' <= str[i]) {
          str[i] -= 97;
          str[i]++;
          str[i] %= 26;
          str[i] += 97;
        }
      }
    }
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int s[501][501];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, Q;
    cin >> n >> m >> Q;

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        //l--; r--;

        s[l][r]++;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            s[i][j] += s[i][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            s[i][j] += s[i - 1][j];
        }
    }

    for (int h = 0; h < Q; h++) {
        int p, q;
        cin >> p >> q;
        p--;// q--;

        int r = s[n][q] - s[p][q];

        cout << r << '\n';
    }

    cout << flush;

    return 0;
}

Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;

int x, y;

int group(int n){
	if(n == 1 || n == 3 || n == 5 || n == 7 || n == 8 || n == 10 || n == 12) return 1;
	else if(n == 4 || n == 6 || n == 9 || n == 11) return 2;
	else if(n == 2) return 3;
}

int main(){
	cin >> x >> y;
	if(group(x) == group(y)) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
l = sum(A)
if l % N == 0:
  x = l // N
  s = 0
  for a in A:
    s += (a - x) ** 2
  print(s)
else:
  x = l // N
  y = x + 1
  s = 0
  t = 0
  for a in A:
    s += (a - x) ** 2
    t += (a - y) ** 2
  print(min(s, t))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <stdio.h>

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {

    ll N;
    cin >> N;

    if (N % 2 != 0) {
        print(0);
    } else {
        ll ans = 0;
        ll div = 10;
        while (N >= div) {
            ans += N / div;
            div *= 5;
        }
        print(ans);
    }

}

signed main() {
    solve();
}


Measured memory_bytes: 764
#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> p(n, k-q);
  for (int i = 0; i < q; i++) {
    int a;
    cin >> a;
    a--;
    p[a]++;
  }
  
  for (int i = 0; i < n; i++) {
    if (p[i] <= 0) {
      puts("No");
    } else {
      puts("Yes");
    }
  }
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int n,tot=0,maxh=1;
  int h[110];
  cin >> n;
  for (int i=0; i< n;i++) cin >> h[i];

  
  for (int i=0; i< n;i++){
    if (i == 0){
      maxh = h[i];
      tot++;
    }else{
      if (h[i] >= maxh){
	tot++;
      }
      maxh = max(h[i],maxh);
    }
  }

  cout << tot;
  
}



Measured memory_bytes: 256
import math
def GCD(a):
    gcd = a[0]
    N = len(a)
    for i in range(1, N):
        gcd = math.gcd(gcd, a[i])
    return gcd

# 素因数分解
def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = int(input())
A = list(map(int, input().split()))
hst = [0] * (max(A) + 1)

for a in A:
    F = fact(a)
    for f in F:
        hst[f[0]] += 1
        if hst[f[0]] > 1 and f[0] != 1:
            # ここでpairwise じゃないことが確定する
            if GCD(A) == 1:
                print("setwise coprime")
            else:
                print("not coprime")
            exit()

print("pairwise coprime")

Measured memory_bytes: 189612
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	int i,n,K,ans=mod;cin>>n>>K;
	vector<int>ca(n);
	for(i=0;i<n;i++){cin>>ca[i];}
	for(i=0;i<=n-K;i++){
		int L=ca[i];
		int R=ca[i+K-1];
		int gen;
		if(R<0){gen=-L;}
		else if(0<L){gen=R;}
		else {gen=min(abs(L),abs(R))+abs(L)+abs(R);}
		mineq(ans,gen);
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 888
#include <stdio.h>

int main()
{
        int  a=1,b=0,c=0;
        int tmp;
        char x,y;

        while(~scanf("%c,%c\n",&x,&y)){
                if((x=='A'&&  y=='B')||(x=='B'&&y=='A')){
                        tmp=a;a=b;b=tmp;
                }
                if((x=='B' && y=='C')||(x=='C'&&y=='B')){
                        tmp=b;b=c;c=tmp;
                }
                if((x=='C' && y=='A')||(x=='A'&&y=='C')){
                        tmp=c;c=a;a=tmp;
                }
        }
                if(a==1)puts("A");
                else if(b==1)puts("B");
                else puts("C");
        return 0;
}

Measured memory_bytes: 528
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;cin >> S;
  int N = S.size();
  bitset<4>bs;
  for(int i = 0; i < N; ++i){
    switch(S[i]){
    case 'S':bs[0]=1;break;
    case 'N':bs[1]=1;break;
    case 'W':bs[2]=1;break;
    case 'E':bs[3]=1;break;
    }
  }
  bool f = bs[0] == bs[1];
  f &= bs[2] == bs[3];
  cout << (f?"Yes\n":"No\n");
  return 0;
}


Measured memory_bytes: 256
N,L=gets.split.map(&:to_i)
as=gets.split.map(&:to_i)
knot=false
(N-1).times do |i|
    if as[i]+as[i+1]>=L
        knot=i
        break
    end
end
if !knot
    puts "Impossible"
else
    puts "Possible"
    if knot==0
        puts (1..N-1).to_a.reverse
    elsif knot==N-1-1
        puts (1..N-1).to_a
    else
        puts (1..knot).to_a+((knot+2..N-1).to_a.reverse)+[knot+1]
    end
end

Measured memory_bytes: 14220
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

int main() {
  int n,ans = 0;
  cin >> n;
  unordered_map<long long,int>mp;
  for(int i = 0;i < n;i++){
    long long a;
    cin >> a;
    if(mp.find(a) == mp.end()){
      mp[a] = 1;
    }
    else{
      if(mp[a] == 0){
        mp[a] = 1;
      }
      else{
        mp[a] = 0;
      }
    }
  }
  for(auto itr = mp.begin();itr != mp.end();itr++){
    if(itr->second == 1){
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 4388
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,A,B;
  int a;
  int sum;
  cin >> N >> A >> B;
  int M=N;
  while(M>0){
    N=M;
    for(int i = 10000; i>=1;i/=10){
      a += N/i;
      N -= N/i*i;
    }
    if(A<=a && a <=B){
      sum+=M;
    }
    a=0;
    M--;
  }
  cout << sum << endl;  
}

Measured memory_bytes: 256
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

n,k=map(int,input().split())
w=[int(input().rstrip()) for _ in range(n)]
l,r=0,10**9
while l<r:
    m=(l+r)//2
    loop=0
    ch=False
    for i in range(k):
        noww=0
        while loop<n:
            if noww+w[loop]<=m:
                noww+=w[loop]
                loop+=1
            else: break
        else:
            ch=True
    if ch: r=m
    else: l=m+1
    #print(m,l,r)
print(l)


Measured memory_bytes: 9904
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

const int maxn=1e5+10;
int n,a[maxn],b[maxn],c[maxn];
long long ans;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)scanf("%d",&b[i]);
	for(int i=1;i<=n;++i)scanf("%d",&c[i]);
	sort(a+1,a+n+1);
	sort(c+1,c+n+1);
	for(int i=1;i<=n;++i){
		ans+=(long long)(lower_bound(a+1,a+n+1,b[i])-a-1)*(n-(upper_bound(c+1,c+n+1,b[i])-c-1));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k, s;
  cin >> k >> s;
  int ans = 0;
  int remain;
  for(int i = 0; i <= k; ++i){
    for(int j = 0; j <= k; ++j){
      remain = s - i - j; 
      if(remain <= k && remain >= 0) ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n,i,j,k,s,count = 0;
	scanf("%d",&n);
	int array1[n],array2[n];
	for (i = 0;i < n;i++) {
		scanf("%d",&array1[i]);
		array2[i] = array1[i];
	}

	for (j = 0;j < n - 1 ;j++) {

		for (i = j + 1;i < n -1;i++)
			if(array1[i+1] > array1[i])
				array1[i+1] = array1[i];

		if (array2[j] > array1[n-1]) {
			for (i = j + 1;i < n;i++)
				if (array2[i] == array1[n-1])
					break;
			s = array2[j];
			array2[j] = array1[n-1];
			array2[i] = s;
			count++;
			for (i = j;i < n ;i++) 
				array1[i] = array2[i];
		} else {
			for (i = j + 1;i < n ;i++) 
				array1[i] = array2[i];
		}

	}
	
	for (i = 0;i < n;i++) {
		if (i == n -1)
			printf("%d\n",array2[i]);
		else printf("%d ",array2[i]);
	}
	printf("%d\n",count);
	return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N , M , sum,count;
  cin >> N >> M;
  vector<int>vec(N);
  count = 0;
  sum = 0;
  for(int i = 0;i < N;i++){
    cin >> vec.at(i);
    sum += vec.at(i);
  }
  for(int i = 0;i < N;i++){
    if(sum <= vec.at(i) * 4 * M){
      count ++;
    }
  }
  if(count >= M){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n,s) for (int i=a;s>0?i<n:i>n;i+=s)
#define rep(...) _overload3(__VA_ARGS__,per,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>inline bool chmax(T &a, const T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T b) { if (b<a) { a=b; return 1; } return 0; }
const int inf = 1e9+10, mod = 1e9+7; const long long llinf = 1e18;
// head
int black[100001];
int white[100001];
int visited[100001];
vector<int> G[100001];

void dfs(int node){
  visited[node] = 1;
  long long b=1,w=1;
  for (auto v:G[node]){
    if (!visited[v]) {
      dfs(v);
      b = (b * white[v]) % mod;
      w = (w * (white[v] + black[v]) % mod) % mod;
    }
  }
  black[node] = b;
  white[node] = w;
}

int main(){
  int n;
  cin >> n;
  rep(i,n-1){
    int x,y ;
    cin >> x >> y;
    x--;y--;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(0);
  cout << (black[0] + white[0]) % mod << endl ;
}


Measured memory_bytes: 12416
import java.io.*;

class Main
{
    public static void main (String[ ] args) throws Exception
    {
        BufferedReader br = new BufferedReader (new InputStreamReader (System.in));
        
        double r = Double.parseDouble(br.readLine());
        
        double b = Math.PI * r * r;
        double c = 2 * Math.PI * r;

        System.out.printf("%.5f %.5f\n", b, c);
    }
}

Measured memory_bytes: 24592
#include <iostream>
using namespace std;

int main()
{
	int c1, c5, c10, c50, c100, c500, n;

	cin >> c1 >> c5 >> c10 >> c50 >> c100 >> c500;

	n = c1 + 5 * c5 + 10 * c10 + 50 * c50 + 100 * c100 + 500 * c500;

	if (n >= 1000)
		cout << 1 << endl;
	else
		cout << 0 << endl;

	return 0;
}



Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef std::vector<vector<int> > vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
#define debugone(x) cerr << #x << " " << x << "\n"; cerr.flush();
#define debugtwo(x) cerr << #x << "-------------" << "\n";for(auto &it: x) cerr << it << " ";cerr << "\n"; cerr.flush();
#define debugthree(x_, i_, j_) cerr << #x_ << "------------" << "\n";cerr << "from " << i_ << " to " << j_ << "\n";for(ll k_=i_; k_<=j_; k_++) cerr << x_[k_] << " ";cerr << "\n"; cerr.flush();
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;

const ll MOD = 1e9 + 7;
const int INF = 2e9;
const int MAX_LOG = 21;
const int MAX_N = 12800;

#define forn(i, n) for(int i = 0; i < n; i++)
#define forsn(i, s, n) for(int i = s; i < n; i++)
#define all(x) x.begin(), x.end()

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	string s, t;
	cin >> s >> t;
	cout << t << s;
}

Measured memory_bytes: 256
#include <iostream>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
using ll = long long;

using namespace std;



int main() {
    int x;
    cin >> x;
    if(x) puts("0");
    else puts("1");

    return 0;
}


Measured memory_bytes: 3616
// Code by Nguyen Huu Lam
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long LL;

#define y0 Sword_Art_Online
#define y1 Your_lie_in_April
#define yn Darling_in_the_Franxx
#define tm Plastic_Memories
#define lr Charlotte
#define norm Weathering_with_you
#define left Violet_Evergarden
#define have Date_a_live
#define ends Your_name
#define prev Five_centimeters_per_second
#define hash Silent_voice
#define endl "\n"

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

LL Rand(LL l, LL h){
    return uniform_int_distribution<LL>(l, h)(rng);
}

template <typename T> void read(T &t){
    t = 0; char ch = getchar(); int f = 1;
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    do { (t *= 10) += ch - '0'; ch = getchar(); } while (isdigit(ch)); t *= f;
}

const LL MaxN = 1 + 1e5;

LL n, a[MaxN], cnt;
char ch;
string s;

void InOut(){
    #define TASK "ABC"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
}

int main(){
    // InOut();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> s;
    for(int i = 0 ; i < n ; ++i) if(s[i] == 'R') cnt++;
    LL ans = 0;
    for(int i = 0 ; i < cnt ; ++i)
    if(s[i] != 'R') ans++;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3784
n = int(input())
s = [ str(input()) for _ in range(n) ]

m = [[] for _ in range(5)]
for i in range(n):
    if s[i][:1] == "M":
        m[0].append(s[i])
    elif s[i][:1] == "A":
        m[1].append(s[i])
    elif s[i][:1] == "R":
        m[2].append(s[i])
    elif s[i][:1] == "C":
        m[3].append(s[i])
    elif s[i][:1] == "H":
        m[4].append(s[i])
    else:
        pass
    
for i in range(5):
    m[i] = len(list(set(m[i])))

print(m[0] * m[1] * m[2] + m[0] * m[1] * m[3] + m[0] * m[1] * m[4] + m[0] * m[2] * m[3] + m[0] * m[2] * m[4] + m[0] * m[3] * m[4] + m[1] * m[2] * m[3] + m[1] * m[2] * m[4] + m[1] * m[3] * m[4] + m[2] * m[3] * m[4])


Measured memory_bytes: 16684
#include <stdio.h>
#include <math.h>

int main(void) {
    long long int a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);

    long long int sab = a + b, tab = a * b;    
    if (((c - sab) > 0) || (((c - sab) < 0) && ((c - sab) * (c - sab) < 4 * tab))) {
        if ((4 * tab - sab * sab) < (c * c - 2 * c * sab)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    } else {
        if ((4 * tab - sab * sab) > (c * c - 2 * c * sab)) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b; cin>>a>>b;
  vector<int> vec;
  vec.push_back(a+b);
  vec.push_back(a-b);
  vec.push_back(a*b);
  printf("%d\n",*max_element(vec.begin(),vec.end()));
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define IN_MAX 1299709

char table[IN_MAX+1];

void createtable1(){ //0->prime 1->not prime
  int i=2,j;
  for(;i<=IN_MAX;i++)
    if(!table[i])
      for(j=i*2;j<=IN_MAX;j+=i)
        table[j]=1;
}

void createtable2(){
  int i=2,j=2,x;
  for(;i<=IN_MAX;i++)
    if(!table[i]){
      for(x=j+1;x<i;x++)
        table[x]=i-j;
      j=i;
    }
}

int main(){
  int i;
  createtable1();
  createtable2();
  while(scanf("%d",&i)&&i)printf("%d\n",table[i]);
  return 0;
}

Measured memory_bytes: 1868
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}

long long int combination(long long int a,long long int b){
    queue<long long int> bunsi,bunbo;
    long long int ans=1;
    b=min(b,a-b);
    for(int i=0;i<b;i++){
        bunsi.push(a-i);
        if(b-i>=2)bunbo.push(b-i);
    }
    while(bunsi.size()!=0||bunbo.size()!=0){
        ans*=bunsi.front();
        bunsi.pop();
        if(ans%bunbo.front()==0){
            ans/=bunbo.front();
            bunbo.pop();
        }
    }
    return ans;
}

bool one (int i) {
    if(i>=1)return true;
    else return false;
}

int main(){
    int n;
    in(n);
    vector<char> hikaku={'M','A','R','C','H'};
    vector<ll> counter(5,0);
    string s;
    rep(i,n){
        in(s);
        rep(j,5){
            if(s[0]==hikaku[j]){
                counter[j]++;
            }
        }
    }
    ll ans=0,d;
    sort(all(counter));
    for(int i=7;i<(1<<5);i++){
        bitset<5> bit(i);
        if(bit.count()==3){
            d=1;
            rep(j,5){
                if(bit.test(j)){
                    d*=counter[j];
                }
            }
            ans+=d;
        }
    }
    out(ans);
}


Measured memory_bytes: 3792
#include <iostream>
using namespace std;
int main(void){
    int a,b,c;
    cin >>a;
    cin >>b;
    cin >>c;
    if (a<b&&b<c){
        cout <<"Yes";
       }
    else if (a>=b||b>=c){
        cout <<"No";
       }
    cout <<endl;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;
using i64 = long long;
using vi64 = vector<i64>;

i64 n;
vi64 a;

i64 cnt;
vi64 merge(vi64 &v, int l, int r) {
  vi64 ret;
  if (l + 1 == r) {
    ret.push_back(v[l]);
    return ret;
  }
  vi64 a = merge(v, l, (l + r) / 2);
  vi64 b = merge(v, (l + r) / 2, r);
  int ai = 0, bi = 0;
  rep(i, r - l) {
    if (bi == b.size()) {
      ret.push_back(a[ai++]);
      cnt += bi;
    } else if (ai == a.size()) {
      ret.push_back(b[bi++]);
    } else {
      if (a[ai] <= b[bi]) {
        ret.push_back(a[ai++]);
        cnt += bi;
      } else {
        ret.push_back(b[bi++]);
      }
    }
  }
  return ret;
}

bool check(i64 md) {
  vi64 v(n), s(n + 1);
  cnt = 0;
  rep(i, n) {
    if (a[i] >= md) v[i] = 1;
    else v[i] = -1;
  }
  rep(i, n) {
    s[i + 1] += s[i] + v[i];
  }
  merge(s, 0, n + 1);
  return n * (n + 1) / 4 >= cnt;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cerr << fixed << setprecision(16);
  cin >> n;
  a = vi64(n);
  rep(i, n) cin >> a[i];
  i64 ok = *min_element(all(a)), ng = *max_element(all(a)) + 1;
  while (ng - ok > 1) {
    i64 md = (ok + ng) / 2;
    if (check(md)) {
      ok = md;
    } else {
      ng = md;
    }
  }
  cout << ok << endl;
  return 0;
}


Measured memory_bytes: 5264
#include<bits/stdc++.h>
using namespace std;
long long N,M;
bool check(long long x){
	if(x==1)return 0; 
	long long tmp=M;
	while(tmp%x==0)tmp/=x;
	if(tmp%x==1)return 1;
	return 0;
}
bool check2(){
	long long tmp=sqrt(N);
	tmp=tmp*tmp;
	return tmp==N;
}
int main(){
	cin>>N;M=N;
	int cnt=0;
	for(long long i=1;i<sqrt(N);i++)
		if(N%i==0)
			cnt+=check(i),cnt+=check(N/i);
	if(check2())cnt+=check(sqrt(N));
	N--;
	for(long long i=1;i<sqrt(N);i++)
		if(N%i==0)
			cnt+=check(i),cnt+=check(N/i);
	if(check2())cnt+=check(sqrt(N));
	cout<<cnt; 
}

Measured memory_bytes: 384
#include<cmath>
#include<ctime>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define next nex
using namespace std;
const int MAXN = 200005;
int first[MAXN], next[MAXN << 1], go[MAXN << 1], t;
int n, m, i, j, k, x, y, z, l[MAXN], r[MAXN], a[MAXN];
int w[MAXN];
bool ok;
inline int get()
{
	char c;
	while ((c = getchar()) < 48 || c > 57);
	int res = c - 48;
	while ((c = getchar()) >= 48 && c <= 57)
		res = res * 10 + c - 48;
	return res;
}
inline void add(int x, int y)
{
	next[++t] = first[x]; first[x] = t; go[t] = y;
}
inline void dfs(int now, int las)
{
	if (ok) return;
	int L = l[now], R = r[now];
	for(int i = first[now]; i; i = next[i])
		if (go[i] != las)
		{
			dfs(go[i], now);
			int ll = l[go[i]] - 1, rr = r[go[i]] + 1;
			if (R < ll || L > rr) ok = 1;
			L = max(L, ll);
			R = min(R, rr);
			if (R < L) ok = 1;
		}
	l[now] = L; r[now] = R;
}
inline void getans(int now, int las, int w)
{
	a[now] = w;
	if (ok) return;
	for(int i = first[now]; i; i = next[i])
		if (go[i] != las)
		{
			if (w - 1 >= l[go[i]] && w - 1 <= r[go[i]]) getans(go[i], now, w - 1);
			else if (w + 1 >= l[go[i]] && w + 1 <= r[go[i]]) getans(go[i], now, w + 1);
			else {ok = 1; break;}
		}
}
int main()
{
	cin >> n;
	for(i = 1; i < n; i ++)
		x = get(), y = get(), add(x, y), add(y, x);
	for(i = 1; i <= n; i ++)
		l[i] = -10000000, r[i] = 10000000;
	cin >> m;
	for(i = 1; i <= m; i ++)
	{
		x = get(); y = get();
		l[x] = y;
		r[x] = y;
	}
	dfs(1, 0);
	if (ok)
	{
		cout << "No";
		return 0;
	}
	for(i = l[1]; i <= r[1] && i <= l[1] + 1000; i ++)
	{
		ok = 0;
		getans(1, 0, i);
		if (!ok)
		{
			cout << "Yes\n";
			for(j = 1; j <= n; j ++)
				printf("%d\n", a[j]);
			return 0;
		}
	}
	cout << "No";
}

Measured memory_bytes: 19072
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

long long N, A[200009], cnt;
multiset<long long> S;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A, A + N);

	for (int i = N - 1; i >= 0; i--) {
		bool flag = false;
		for (int j = 0; j < 32; j++) {
			long long ret = (1LL << j) - A[i];
			if (A[i] > ret) continue;
			
			auto itr = S.lower_bound(ret);
			if (itr != S.end() && *itr == ret) {
				S.erase(itr); flag = true; cnt++;
				break;
			}
		}
		if (flag == false) S.insert(A[i]);
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 11136
while True:
  H,W = map(int,input().split())
  if H == 0 and W == 0 :
    break
  line = ['#.'*(W // 2)+'#'*(W % 2),'.#'*(W // 2)+'.'*(W % 2)]
  for i in range(H) :
    print(line[i % 2])
  print()


Measured memory_bytes: 5612
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int numberOfStickUsed = sc.nextInt();
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			list.add(sc.nextInt());
		}
		Collections.sort(list,Comparator.reverseOrder());
		int sum = 0;
		for(int i = 0; i < numberOfStickUsed; i++) {
			sum += list.get(i);
		}
		System.out.println(sum);
		
	}
}


Measured memory_bytes: 22740
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdlib>

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i=0;i<N;i++){
    cin >> d.at(i);
  }
  sort(d.begin(),d.end());
  int ans=1;
  for(int i=1;i<N;i++){
    if(d.at(i) != d.at(i-1))  ans++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>

using namespace std;
//typedef long long ll;
typedef unsigned long long ll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX;
const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<ll, vector<ll>, greater<ll>> PQ_ASK;
const int mod = 1000000007;


int main() {

    int n, m;
    cin >> n >> m;

    vector<bool> ok_list(n, false);
    vector<int> wa_counts(n, 0);

    int ok_count = 0;
    int wa_count = 0;

    rep(i, m) {
        int p;
        string judge;
        cin >> p >> judge;
        p--;

        if (ok_list[p] == false && judge == "AC") {
            ok_list[p] = true;
            ok_count++;
            wa_count += wa_counts[p];
        } else if (ok_list[p] == false && judge == "WA") {
            wa_counts[p]++;
        }
    }


    printf("%d %d\n", ok_count, wa_count);

}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int i=1;
  do{
    int x=i;
    if(x%3==0){
      cout << " " << i;
      continue;
    }
    while(x){
      if(x%10==3){
	cout << " " << i;
	break;
      }
      x/=10;
    }
  }while(++i<=n);
  cout << endl;
  return 0;
}


Measured memory_bytes: 3124
import math
a, b, h, m = map(int, input().split(' '))

rec_h = 30 * h + 0.5 * m
rec_m = 6 * m
rec = abs(rec_h-rec_m)
if rec > 180:
    rec = 360 - rec

x = b * math.sin(math.radians(rec))
y = a - b * math.cos(math.radians(rec))

r = math.sqrt(x**2 + y**2)
print(r)

Measured memory_bytes: 9440
#include <iostream>
using namespace std;

int main() {
    int N ;
    cin >> N;
    int a[N];
    for (int i = 0; i < N; ++i){
        cin >> a[i];
    }
    int light = 1;
    int count = 0;
    int flag = 0;
    for (int i = 0; i < N; ++i){
        light = a[light - 1];
        count += 1;
        if (light == 2){
            flag = 1;
            break;
        }
    }
    if (flag == 1){
        cout << count << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 640
// AOJ 2456: Usoperanto
// 2018.4.17 bal4u

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

// マイナス値の入力に対応
//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0, c = getchar_unlocked();
	if (c == '-') { c = getchar_unlocked();
		do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
		return -n;
	}
	do n = 10*n + (c & 0xf), c = getchar_unlocked(); while (c >= '0');
	return n;
}

#define MAX 1000002
int  N;
int  m[MAX];
int  *base, bsz;
int  hi[MAX], *to[MAX];
int  que[MAX], top;
int  a[MAX];
long long s[MAX], b[MAX], dp[MAX];

int cmp(long long *a, long long *b)
{
	if (*a == *b) return 0;
	if (*a < *b) return 1;
	return -1;
}

void calc(int u)
{
	int i, v, sz;

	sz = 0, s[u] = m[u], dp[u] = 0;
	for (i = 0; i < hi[u]; i++) {
		v = to[u][i];
		b[sz++] = s[v], s[u] += s[v], dp[u] += dp[v];
	}
	qsort(b, sz, sizeof(long long), cmp);
	for (i = 0; i < sz; i++) dp[u] += b[i]*i;
}

int main()
{
	int i, l, t;
	long long ans;
	int *memo;

	N = in();
	memo = malloc(N<<2);
	for (i = 0; i < N; i++) {
		m[i] = in(), memo[i] = l = in();
		if (l == -1) bsz++;
		else hi[l]++;
	}
	base = malloc(bsz<<2);
	for (i = 0; i < N; i++) if (hi[i]) to[i] = malloc(hi[i]<<2);
	bsz = 0, memset(hi, 0, N<<2);

	for (i = 0; i < N; i++) {
		l = memo[i];
		if (l == -1) base[bsz++] = i;
		else to[l][hi[l]++] = i;
	}

	ans = 0;
	for (i = 0; i < bsz; i++) {
		if (hi[base[i]] < 1) continue;
		que[1] = base[i], top = 1;
		while (top) {
			t = que[top];
			if (a[t] < hi[t]) que[++top] = to[t][a[t]++];
			else calc(t), top--;
		}
		ans += dp[base[i]];
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 75968
#include <iostream>
#include <vector>

using namespace std;

char s[20][1010];

int main() {
  int h, w, k; cin >> h >> w >> k;
  for (int i = 0; i < h; i++) { cin >> s[i]; }
  int ans = h + w;
  for (int mask = 0; mask < (1 << (h-1)); mask++) {
    int block = __builtin_popcount(mask) + 1; // ブロックの数
    int cur = block - 1;  // cur: 切断する回数
    int last = 0;
    vector<int> cnt(block, 0); // 各ブロックごとの1の数
    for (int i = 0; i < w; i++) {
      int pos = 0;
      vector<int> add(block, 0);
      for (int j = 0; j < h; j++) {
        add[pos] += s[j][i] - '0';
        pos += (mask >> j) & 1;
      }
      bool ok = true;
      for (int j = 0; j < block; j++) {
        if (cnt[j] + add[j] > k) {
          ok = false;
          break;
        }
      }
      if (ok) {
        for (int j = 0; j < block; j++) {
          cnt[j] += add[j];
        }
      } else {
        if (i == last) {
          cur = h + w;
          break;
        }
        for (int j = 0; j < block; j++) {
          cnt[j] = add[j];
        }
        cur++;
        last = i;
      }
    }
    ans = min(ans, cur);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let mut done: bool = false;
    while !done {
        let x: String = read();
        if x == "0" {
            done = true;
        } else {
            println!("{}", x.chars().map(|c| c.to_digit(10).unwrap()).sum::<u32>());
        }
    }
}



Measured memory_bytes: 5020
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n;
  cin >> n;
  vector<int> x(n), l(n);
  rep(i, n) cin >> x[i] >> l[i];

  vector<P> rl(n);
  rep(i, n) rl[i] = make_pair(x[i] + l[i], x[i] - l[i]);
  sort(rl.begin(), rl.end());

  int num_bot = 0;
  int r = -1e9;
  rep(i, n) {
    if (rl[i].second < r) continue;
    r = rl[i].first;
    ++num_bot;
  }
  cout << num_bot << endl;
  return 0;
}

Measured memory_bytes: 4780
#include "bits/stdc++.h"

using namespace std;

const int maxn = 100005;

int a[maxn];

int main() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  sort(a, a + n);
  printf("%d\n", a[n / 2] - a[(n / 2) - 1]);
}


Measured memory_bytes: 640
N = int(input())

DP = [False]*(N+1000)
prices = [100,101,102,103,104,105]
DP[0] = True
for i in range(N):
    if DP[i]:
        for p in prices:
            DP[i+p] = True

if DP[N]:
    print(1)
else:
    print(0)

Measured memory_bytes: 41324
#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;

int main()
{
    ll n,m;
    ll i,j;
    
    cin >> n;
    ll a,b;
    for(i = 1;i <= sqrt(n);++i){
        if(n%i == 0){
            a = i;
            b = n/i;
        }
    }

    cout << a+b-2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main(){
    #ifdef LOCAL
    freopen("a", "r", stdin);
    #endif // LOCAL
    int x1, y1, x2, y2;
    while(~scanf("%d%d%d%d", &x1, &y1, &x2, &y2)){
        int delx = y1 - y2;
        int dely = x2 - x1;
        printf("%d %d %d %d\n", x2 + delx, y2 + dely, x1 + delx, y1 + dely);
    }
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAX 11111
struct edge2{
  int to,dist,cost;
  edge2(){}
  edge2(int to,int dist,int cost):to(to),dist(dist),cost(cost){}
};
vector<edge2> G[MAX];
typedef pair<int,int> P;
int d[MAX],c[MAX];
int main(){
  int n,m;
  while(cin>>n>>m,n||m){
    int inf=1<<25;
    for(int i=0;i<MAX;i++) d[i]=c[i]=inf;
    for(int i=0;i<MAX;i++) G[i].clear();
    
    for(int i=0;i<m;i++){
      int u,v,d,c;
      cin>>u>>v>>d>>c;
      u--;v--;
      G[u].push_back(edge2(v,d,c));
      G[v].push_back(edge2(u,d,c));
    }
    
    priority_queue<P> q;
    q.push(P(0,0));
    d[0]=0;
    while(!q.empty()){
      P p=q.top();q.pop();
      int v=p.second;
      if(d[v]<-p.second) continue;
      for(edge2 e:G[v]){
	if(d[v]+e.dist<d[e.to]){
	  d[e.to]=d[v]+e.dist;
	  q.push(P(-d[e.to],e.to));
	}
      }
    }

    
    while(!q.empty()) q.pop();
    q.push(P(0,0));
    c[0]=0;
    while(!q.empty()){
      P p=q.top();q.pop();
      int v=p.second;
      if(c[v]<-p.second) continue;
      for(edge2 e:G[v]){
	if(d[v]+e.dist==d[e.to]){
	  if(e.cost<c[e.to]){
	    c[e.to]=e.cost;
	    q.push(P(-c[e.to],e.to));
	  }
	}
      }
    }
    int ans=0;
    for(int i=0;i<n;i++) ans+=c[i];
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 5012
#include <iostream>
using namespace std;

#ifdef DEBUG
    #define IFD if(true)
#else
    #define IFD if(false)
#endif

int main()
{
    int N, H, W;

    cin >> N >> H >> W;
    cout << (N - H + 1) * (N - W + 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n,a;
  string s;
  cin >> n;
  a = 0;
  
  for(int i = 0;i < n;i++){
    cin >> s;
    if(s == "Y"){
    a = 1;
    break;}
  }
  if(a == 0)
    cout << "Three" << endl;
  else
    cout << "Four" << endl;  
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
 #pragma GCC optimize("unroll-loops")
 #pragma GCC optimize("fast-math")
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define int long long
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

void accell() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
}
const int N = 1e5 + 5;

int dp[N][4];

signed main() {
    accell();
    int n;
    cin >> n;
    vector<int>a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= 3; ++j)
            dp[i][j] = -1;
    dp[0][a[0] % 2] = a[0] / 2;
    if (a[0] >= 2)
        dp[0][a[0] % 2 + 2] = a[0] / 2 - 1;
    for (int i = 0; i + 1 < n; ++i) {
        for (int j = 0; j <= 3; ++j) {
            if (dp[i][j] == -1)
                continue;
            int c1 = a[i + 1] % 2;
            int v1 = a[i + 1] / 2;
            int cur1 = min(c1, j);
            c1 -= cur1;
            dp[i + 1][c1] = max(dp[i + 1][c1], dp[i][j] + cur1 + v1);
            if (a[i + 1] >= 2) {
                int c2 = a[i + 1] % 2 + 2;
                int v2 = v1 - 1;
                int cur2 = min(c2, j);
                c2 -= cur2;
                dp[i + 1][c2] = max(dp[i + 1][c2], dp[i][j] + cur2 + v2);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= 3; ++i)
        ans = max(ans, dp[n - 1][i]);
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in, n) for(int i=0; i<n; i++) cin>>in[i]
#define forout(out, n) for(int i=0; i<n; i++) cout<<out[i]<<endl
#define rep(i, n) for(int i=0; i<(n); i++)

int main(){
    double l; cin>>l;
    l /= 3;
    printf("%.8lf\n", pow(l, 3));
}

Measured memory_bytes: 4148
#include <bits/stdc++.h>
using namespace std;

   typedef long long ll;
   typedef pair<ll, ll> Pii;
   typedef vector<ll> Vi;
   typedef vector<Vi> VVi;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define RSORT(x) sort((x).rbegin(), (x).rend())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
   template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}
   ll pow(ll a, ll b, ll m){if (b == 0) return 1; else if (a == 0) return 0; else if (b % 2 == 0) return (pow((a * a) % m, b / 2, m) % m); else return (pow((a * a) % m, b / 2, m) * a) % m;}
   ll residue(ll a, ll m){return ((a % m) + m) % m;};

   ll dx[4]={1,0,-1,0};
   ll dy[4]={0,1,0,-1};

int main(){
  ll n, m; cin >> n >> m;
  VVi x(m, Vi(n, 0)); Vi p(m);
  REP(i, m){
    ll k; cin >> k;
    REP(j, k){
      ll s; cin >> s; x[i][s - 1] = 1;
    }
  }
  REP(i, m) cin >> p[i];
  ll ans = 0;
  REP(i, 1 << n){
    REP(j, m){
      ll q = 0;
      REP(k, n){
        if(x[j][k] == 1 && ((i >> k) & 1)) q++;
      }
      if(q % 2 != p[j]) break;
      if(j == m - 1) ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
	int n, i;
	char s[50][101], x[101];
	int t[50];
	scanf("%d\n", &n);
	for(i=0; i<n; i++){
		scanf("%s %d\n", s[i], t+i);
	}
	scanf("%s", x);
	for(i=0; i<n; i++){
		if(strcmp(s[i], x)==0) break;
	}
	int ans=0;
	for(i++; i<n; i++){
		ans+=t[i];
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  map<ll,ll>MP;
  for(int i=0;i<n;i++){
    ll a;cin>>a;
    MP[a]++;
  }
  ll cnt=0,cnt2=0;
  for(auto a:MP){
    ll num=a.S;
    if(num%2){
      cnt++;
    }else{
      cnt2++;
    }
  }
  cout<<cnt+cnt2-cnt2%2<<endl;
  return 0;
}
  


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#include <math.h>
#define rep(i,n) for (int i=0;i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
 

int main() {
    ll n; int ans=0;
    cin >> n;
    map<ll,int> mp;
    ll j = 2;
    int k = int(sqrt(n)+1.0);
    while(j <= k){
        while(n%j==0){
            n /= j;
            mp[j]++;
        }
        j++;
    }
    mp[n]++;
    mp[1]=0;
    for(auto i = mp.begin();i != mp.end();++i){
        int l=1;
        while(i->second - l>=0){
            i->second -= l;
            l++;
            ans++;
        }
    }
    if(ans==0&&n!=1) ans=1;
    cout << ans << endl;
}

Measured memory_bytes: 3612