akhauriyash/Code-Regression huggingface dataset:
import math
k=int(input())
total=0
info=[0]
for i in range(1,201):
    for j in range(1,201):
        if j<i:
            info.append(0)
            continue
        info.append(math.gcd(i,j))
        #print(str(i)+" "+str(j)+" "+str(math.gcd(i,j)))
#print(info[202])
#print(info)
for i in range(1,k+1):
    a=[]
    a.append(i)
    for j in range(1,k+1):
        a.append(j)
        for m in range(1,k+1):
            a.append(m)
            a=sorted(a)
            gcd=info[(a[0]-1)*200+a[1]]
            b=min(gcd,a[2])
            c=max(gcd,a[2])
            gcd=info[(b-1)*200+c]
            total+=gcd
            #print(gcd)
            #print(a)
            a=[i,j]
        a=[i]
print(total)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  using P = pair<i64, i64>;
  int n; cin >> n;
  vector<P> xy;
  map<P, int> ma;
  rep(i, n) {
    int x, y; cin >> x >> y;
    xy.push_back({x, y});
  }
  if (n == 1) {
    cout << 1 << '\n';
    return;
  }
  sort(all(xy));
  rep(i, n) {
    i64 x = xy[i].first, y = xy[i].second;
    ma[P(x, y)] = i;
  }
  int ans = 1e9;
  rep(i, n) rep(j, n) {
    if (i == j) continue;
    i64 p = xy[i].first - xy[j].first;
    i64 q = xy[i].second - xy[j].second;
    if (p < 0) p *= -1, q *= -1;
    
    int cnt = 0;
    vector<bool> f(n);
    rep(k, n) {
      if (f[k]) continue;
      f[k] = true;
      cnt++;
      i64 x = xy[k].first, y = xy[k].second;
      while (ma.count(P(x + p, y + q)) > 0) f[ma[P(x += p, y += q)]] = true;
    }
    amin(ans, cnt);
  }
  cout << ans << '\n';
}


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

int main(void){
    int K, A, B;
    cin >> K;
    cin >> A >> B;
    if((A%K==0)||(A/K<B/K)){
        cout << "OK" << endl;
    }else{
        cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3640
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
 
        int n = sc.nextInt();
        long k = sc.nextLong();
        int[] a = new int[n];
 
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt()-1;
        }
 
        int cnt = 0;
        int p = 0;
        int[] visit = new int[n];
        int[] history = new int[n];
        Arrays.fill(visit, -1);
        do {
            visit[p] = cnt;
            history[cnt] = p;
            p = a[p];
            cnt++;
        } while (visit[p] == -1);
 
        int dist = cnt - visit[p];
        int num = (int)((k - cnt) % dist + visit[p]);
        if (cnt > k)
            num = (int)k;
 
        System.out.println(history[num] + 1);
    }
 
    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;
 
        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

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

const long long MOD = 1000000007;
const long long inverse2 = 500000004;
int main(){
    int n; cin >> n;
    vector<int> A(n);
    vector<int> prime(1000001);
    for (int i = 0; i < n; i++){
        cin >> A[i];
        if (A[i] % 2 == 0){
            prime[2]++;
        }
        while (A[i] % 2 == 0){
            A[i] /= 2;
        }
        int j = 3;
        while (j * j <= A[i]){
            if (A[i] % j == 0){
                prime[j]++;
            }
            while (A[i] % j == 0){
                A[i] /= j;
            }
            j += 2;
        }
        if (A[i] > 1){
            prime[A[i]]++;
        }
    }
    bool pair = true; bool set = true;
    for (int i = 2; i <= 1000000; i++){
        if (prime[i] > 1){
            pair = false;
        }
        if (prime[i] == n){
            set = false;
        }
    }
    if (pair){
        cout << "pairwise coprime" << '\n';
    }else{
        if (set){
            cout << "setwise coprime" << '\n';
        }else{
            cout << "not coprime" << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 11148
//all possible//
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(b==c || a==d)
	{
		cout<<0;
		return 0;
		
	}
	if(a!=c && b==d )
	{
		cout<<b-max(a,c);
		return 0;
	}
	if(a==c && b!=d)
	{
		cout<<min(b,d)-a;
		return 0;
		
	}
	if(a==c && b==d)
	{
		cout<<b-a;
		return 0;
	}
	if(c>b || a>d )
	{
		cout<<0;
		return 0;
		
	}
	if((c>a && d<b))
	{
		cout<<d-c;
		return 0;
	}
	if((a>c && b<d))
	{
		cout<<b-a;
		return 0;		
	}
	if(c>a && c<b && d>b)
	{
		cout<<max(a,b)-c;
		
	}
	if(a>c && a<d && b>d)
	{
		cout<<max(c,d)-a;
		
	}

}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#define DEBUG 0
constexpr int kMod = 1000000007;
constexpr int kNmax = 201;
constexpr int kXmax = 1e5 + 1;
typedef long long LL;
LL dp[kNmax][kXmax];

LL dfs(int n, int x, const std::vector<int>& s) {
#if DEBUG
  std::cout << "call dfs(" << n << ", " << x << ") " << std::endl;
#endif
  if (n == 1) return x%s[n-1];
  if (dp[n][x] >= 0) return dp[n][x];

  LL total = 0;
  total += dfs(n-1, x%s[n-1], s);
  total += dfs(n-1, x, s) * static_cast<LL>(n-1);
#if DEBUG
  std::cout << "\t->" << total << std::endl;
#endif
  dp[n][x] = total % kMod;
  return dp[n][x];
}

int main() {
  int N, X; std::cin >> N >> X;
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= X; ++j) {
      dp[i][j] = -1;
    }
  }

  std::vector<int> S(N);
  for (auto& v : S) std::cin >> v;
  std::sort(S.begin(), S.end());

  std::cout << dfs(N, X, S) << std::endl;
}


Measured memory_bytes: 157312
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;

int main(void){
    std::string s;
    cin >> s;
    int pos_l = 0, pos_r = (int)s.size()-1;
    int count = 0;
    while (pos_l < pos_r)
    {
        //cout << s[pos_l] << s[pos_r] << endl;
        if(s[pos_l]==s[pos_r]){
            pos_l++;
            pos_r--;
        }else if(s[pos_l]=='x'){
            count++;
            pos_l++;
        }else if(s[pos_r]=='x'){
            count++;
            pos_r--;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    cout << count << endl;


    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>
#define STR 10000

int n, q, i, j, cnt = 0;
int s[STR];
int t[STR];

int Serch() {
    for(j = 0 ; j < n ; j++) {
        if(s[j] == t[i]) {
            return(cnt++);
        }
    }
}

int main(void){
    scanf("%d", &n);
    for(i = 0 ; i < n ; i++) {
        scanf("%d", &s[i]);
    }
    
    scanf("%d", &q);
    for(i = 0 ; i < q ; i++) {
        scanf("%d", &t[i]);
    }
    
    for(i = 0 ; i < q ; i++) {
      Serch();
    }
    printf("%d\n", cnt);
    return 0;
}



Measured memory_bytes: 2116
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), d = sc.nextInt(), i, j;
		int[][] p = new int[n][d];
		for (i = 0; i < n; i++) {
			for (j = 0; j < d; j++) {
				p[i][j] = sc.nextInt();
			}
		}
		int count = 0;
		for (i = 0; i < n - 1; i++) {
			for (j = i + 1; j < n; j++) {
				int sum = 0;
				for (int k = 0; k < d; k++) {
					sum += (p[i][k] - p[j][k]) * (p[i][k] - p[j][k]);
				}
				double sqrt = Math.sqrt(sum);
				if (0 == sqrt % 1) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 21716
#include    <stdio.h>

int main(void)
{
    char a;
    if (fscanf(stdin, "%c", &a) == EOF) {
	return 1;
    }

    if (a >= 'A' && a <= 'Z') {
	printf("A\n");
    } else if (a >= 'a' && a <= 'z') {
	printf("a\n");
    }

    return 0;
}


Measured memory_bytes: 1576
n = int(input())

arr = [-1] * 1000000
arr[0] = n

for i in range(1, 1000000):
	arr[i] = arr[i-1] // 2 if arr[i-1] % 2 == 0 else arr[i-1] *3 + 1

	if i >= 3 and arr[i] == arr[i-3]:
		print(i + 1) #0->1 indexed
		break


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

int main() {
  int n, w;
  cin >> n >> w;
  vector<int> weight(n), value(n);
  rep(i,n) cin >> weight[i] >> value[i];
  vector<vector<ll>> dp(n+1, vector<ll>(w+1));
  for(int i = 0; i < n; i++) {
    for(int j = 0; j <= w; j++) {
      if(j - weight[i] >= 0) {
        dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]] +  value[i]);
      }
      dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
    }
  }
  cout << dp[n][w] << endl;
  return 0;
}

Measured memory_bytes: 83068
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
A = sorted(A)
heapq.heapify(A)
for _ in range(M):
    ma = heapq.heappop(A)
    ma = -((-ma)//2)
    heapq.heappush(A, ma)
    # print(A, ma)
print(-sum(A))

Measured memory_bytes: 14180
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    string S;
    cin >>N>>S;
    vector<ll>cntE(N+1);
    vector<ll>cntW(N+1);

    rep(i,N){
        if(S[i]=='E'){
            cntE[i+1]=cntE[i]+1;
            cntW[i+1]=cntW[i];
        }else{
            cntW[i+1]=cntW[i]+1;
            cntE[i+1]=cntE[i];
        }

    }
    ll ans = INF;
    rep(i,N){
        ll now = cntW[i]+cntE[N]-cntE[i+1];
        chmin(ans,now);
    }
    
    cout << ans << endl;


    return 0;
    

}

Measured memory_bytes: 8252
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scanner= new Scanner(System.in);
        String s = scanner.next(), ans = "Heisei";
        if(s.charAt(5) == '1')ans = "TBD";
        else if(s.charAt(6) > '4')ans = "TBD";

        System.out.println(ans);
    }

}


Measured memory_bytes: 23252
N, M = map(int, input().split(' '))
 
data = []
l = 1
r = 10**5
for m in range(M):
    li, ri = map(int, input().split(' '))
    if li > l:
      l = li
    if ri < r:
      r = ri
 
if l<= N <= r:
  cnt = (N - l) + 1
elif l > r:
  cnt = 0
elif r < N:
  cnt = (r - l) + 1
else:
  cnt = 0
 
print(cnt)

Measured memory_bytes: 3064
#include <stdio.h>;

int main() {
	int c=1,r=1,count=0;
	double r0,w0;
	while(r0!=0||w0!=0||c!=0||r!=0){
		count=0;
		scanf("%lf%lf%d%d",&r0,&w0,&c,&r);
		if(r0==0&&w0==0&&r==0&&c==0){
			break;
		}
		if(r0/w0>=c){
			printf("0\n");
		}
		else{
			while(r0/w0<c){
				r0+=r;
				count++;
			}
			printf("%d\n",count);
		}
	}
	return 0;
}

Measured memory_bytes: 2712
#include<bits/stdc++.h>
using namespace std;
int main(){
		int W,a,b;
		int minWidth;
		scanf("%i %i %i",&W,&a,&b);
		if(W>=1 && W<=pow(10,5) && a>=1 && a<=pow(10,5)){
			if(a+W<=b)
				if(b-(a+W)>=0)
					minWidth=b-(a+W);
				else
					minWidth=0;
			else
				if(a-(b+W)>=0)
					minWidth=a-(b+W);
				else
					minWidth=0;
			printf("%i",minWidth);
		}
}

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


void solve(){
    ll n;
    cin>>n;
    int64_t a[n];
    int64_t x,ans=1;
    for (ll i = 0; i < n; i++)
    {
        cin>>a[i];
        if(a[i]==0){
            cout<<"0";
            return;
        }  

    }

    for (ll i = 0; i < n; i++)
    {
        if(a[i] <= 1000000000000000000/ans){
            ans *= a[i];
        }
        else{
            cout<<"-1";
            return;
        }
    }

    cout<<ans;
    
    return;

}

int main(){
   int t;
   t=1;
    while(t--){
        solve();
    }

}

Measured memory_bytes: 4360
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
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 print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
#define fs first
#define sc second

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
 
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;


int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll n,a,b;
    cin >> n >> a >> b;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];
    ll ans = 0;
    rep(i, n - 1){
        if(a * (x[i + 1] - x[i]) > b) ans += b;
        else ans += a * (x[i + 1] - x[i]);
    }
    print(ans);

}

Measured memory_bytes: 1024
// 2020-08-17 06:04:17
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n;
  cin >> n;
  vector<int> mp(n+1, 0);
  {
    vector<int> b(n);
    rep(i, n) {
      int a; cin >> a; a--;
      b[a]++;
    }
    rep(i, n) mp[b[i]]++;
  }
  vector<ll> sum1(n+2, 0), sum2(n+2, 0);
  repc(i, n) {
    sum1[i+1] = sum1[i] + i * mp[i];
    sum2[i+1] = sum2[i] + mp[i];
  }
  vector<ll> ans(n+1, 0);
  REPC(i, 1, n) {
    ll res = 0;
    res = sum1[i+1] + (sum2[n+1] - sum2[i+1]) * i;
    res /= ll(i);
    chmax(ans[res], ll(i));
  }
  REPCM(i, n-1, 1) chmax(ans[i], ans[i+1]);
  REPC(i, 1, n) cout << ans[i] << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 11304
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,sse")
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int w, h, x, y;
    cin >> w >> h >> x >> y;
    double opt = w * h / 2.0;
    if (x * 2 == w && y * 2 == h) {
        cout << opt << ' ' << 1 << '\n';
    } else {
        cout << opt << ' ' << 0 << '\n';
    }

    fflush(stdout);
    return 0;
}


Measured memory_bytes: 3760
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

std::vector<std::string> split(const std::string &str, char sep)
{
    std::vector<std::string> v;
    std::stringstream ss(str);
    std::string buffer;
    while( std::getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}


int main()
{
        char tmp, cup = 'A';
        string input;
        vector< string > inputv;

        while ( cin >> input )
        {
                inputv = split( input, ',' );
                if ( inputv[0][0] == cup )
                {
                        cup = inputv[1][0];
                }
                else if ( inputv[1][0] == cup )
                {
                        cup = inputv[0][0];
                }
        }

        cout << cup << endl;
        return 0;
}



Measured memory_bytes: 3184
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Gosu_Hiroo
 */

#include <iostream>
#include <fstream>

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

typedef long long ll;
#define tr(container, it) \
        for (auto it = container.begin(); it != container.end(); it++)
#define scontains(c, x) ((c).find(x) != (c).end())   //O(log n)
#define contains(c, x) (find((c).begin(),(c).end(),x) != (c).end()) //O(n)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mll map<ll,ll>
#define intv(x, a, b)((x)>=a && (x)<=b)
#define  rep(i, _begin, _end) for (__typeof(_end) end = _end, begin = _begin,  i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define  _for(i, end) for (__typeof(end) i = 0, _len = (end); i < (_len); i += 1)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define F first
#define S second
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define readint ({int t;cin >> t;t;})
const double PI = 2 * acos(.0);
const int INF = 0x3f3f3f3f;
const ll LLINF = 1000000000000000005LL;;
const ll MOD = (ll) (1e9) + 7;
void _mod(ll &x){x = mod(x, MOD);}
//const ll MOD = (ll) 998244353 ;
const double EPS = 1e-10;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *) array, (T *) (array + N), val);
}

template <typename T>
ostream& operator << (ostream& os, const vector<T> V) {
    for(auto v : V)os << v << " ";
    return os;
}

template <typename T>
ostream& operator << (ostream& os, const set<T> V) {
    for(auto v : V)os << v << " ";
    return os;
}

//#define int ll

typedef tuple<string, int, int> Shop;
class BGuidebook {
public:
    vector<Shop> Shops;
void solve(std::istream& cin, std::ostream& cout) {
    int N;
    cin >> N;
    _for(i,N){
        string s;
        cin >> s;
        int p;
        cin >> p;
        Shops.emplace_back(s, -p, i);
    }
    sort(all(Shops));
    for(auto shop : Shops)cout << get<2>(shop) + 1 << endl;
}


};


#undef int
int main() {


	BGuidebook solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(0); ios::sync_with_stdio(0); out<<fixed<<setprecision(20);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 5005
using namespace std;
lo int n,k,A[li],dp[li+105];
bool check(lo int mid){
	if(A[mid]>=k) return true;
	for(int i=1;i<=li;i++) dp[i]=0;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(i==mid) continue;
		for(int j=k-1;j>=0;j--){
			if(dp[j]!=0 && j+A[i]<k){
				dp[j+A[i]]=1;
				if(j+A[i]+A[mid]>=k) return true;
			}
		}
	}
	return false;
}
int main(){
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&A[i]);
	}
	sort(A+1,A+n+1);
	lo int bas=0,son=n;
	while(bas<=son){
		lo int mid=(bas+son)/2;
		if(check(mid)) son=mid-1;
		else bas=mid+1;
	}
	printf("%lld\n",son);
	return 0;
}



Measured memory_bytes: 384
#include<stdio.h>
int main ()
{
    int N,M,A,i,a=0,b=0;
    scanf ("%d %d",&N,&M);
    for (i=1;i<=M;i++)
    {
        scanf ("%d",&A);
        a=a+A;
    }
    b=N-a;
    if (b<0)
    {
        printf ("-1\n");
    }
    else
    {
        printf ("%d\n",b);
    }
return 0;
}


Measured memory_bytes: 1728
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <string>

#define rep(x,to) for(int x=0;x<to;x++)
#define rep2(x,from,to) for(int x=from;x<to;x++)

using namespace std;


int main(void){

int cd[5]={0},cnt=0;

char k;
	while(!cin.eof()){
		cin >> cd[0] >> k >>cd[1] >>k >>cd[2] >>k >>cd[3] >>k >>cd[4];
		if(cin.eof()) break;
		
		sort(cd,cd+5);
		int mxp=0,cn1,cn2=0;
		rep(i,5){
			cn1=0;
			rep2(j,i+1,5) if(cd[i]==cd[j]) cn1++;
			cn2 += cn1; 
			mxp = max(mxp,cn1);
		}
//		printf("%d,%d\n",mxp,cn2);
		string yak = "straight";
		rep(i,4) if(cd[i] +1 != cd[i+1]) yak="null";
		if(cd[0]==1 && cd[1]==10 && cd[2]==11 && cd[3]==12 && cd[4]==13)
					yak = "straight";
		if(mxp==1 && cn2==1) yak ="one pair";
		if(mxp==1 && cn2==2) yak ="two pair";
		if(mxp==2 && cn2==3) yak ="three card";
		if(mxp==2 && cn2==4) yak ="full house";
		if(mxp==3) yak ="four card";
		cout << yak << endl;
		cnt++; if(cnt>50) break;
	}	
	
	return 0;
	
	
}

Measured memory_bytes: 1216
package main

import "fmt"

var broken map[int]struct{}

const (
	LARGE_NUM = 1000000007
)

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	num := make([]int, N+1)
	broken = make(map[int]struct{})
	a := 0
	for i := 0; i < M; i++ {
		fmt.Scan(&a)
		broken[a] = struct{}{}
	}
	num[0] = 1
	if isBroken(1) {
		num[1] = 0
	} else {
		num[1] = 1
	}
	for i := 2; i <= N; i++ {
		if isBroken(i) {
			num[i] = 0
		} else {
			num[i] = (num[i-2] + num[i-1]) % LARGE_NUM
		}
	}
	fmt.Println(num[N])
}

func isBroken(i int) bool {
	_, ok := broken[i]
	return ok
}


Measured memory_bytes: 7568
#while True:     
#  try:         
#    listC.append(list(map(int,input().split())))
#  except:         
#    break; 
#x,y = map(int,input().split())
n = int(input())
p = list(map(int,input().split()))

count = 0
for i in range(n-2):
  if (p[i+1] > p[i]) and (p[i+2] > p[i+1]):
    count += 1
  elif (p[i+1] < p[i]) and (p[i+2] < p[i+1]):
    count +=1
                        
print(count)
  

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		int[] ans = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		Scanner sc = new Scanner(System.in);
		int i = sc.nextInt();
		sc.close();
		System.out.println(ans[i-1]);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,r;
	cin >> n >> r;

	cout << (n>=10 ? r : r + 100*(10-n)) << '\n';
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main(){

  int N,K;
  int a[200001] = {};
  int type = 0;
  int out = 0;
  
  cin >> N >> K;

  for(int i = 0; i < N; i++){
	int num;
	cin >> num;
	if(a[num] == 0){
	  type++;
	}
	a[num]++;
  }

  sort(a,a+N+1);

  if(K < type){
	int head = 0;
	while(a[head]==0){
	  head++;
	}
	for(int i = 0; i < type - K; i++){
	  out += a[head];
	  head++;
	}

  }

  cout << out << "\n";
  
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pop pop_back
#define N (ll)(2e5+5)

void solve()
{   

    ll n, w; cin>>n>>w; ll value[n], weights[n];
    for(ll i = 0; i<n; i++)
    {
        ll wi, vi; cin>>wi>>vi;
        value[i] = vi; weights[i] = wi;
    }
    ll dp[n+1][w+1]; memset(dp, 0, sizeof(dp));
    for(ll i = 1; i <= n; i++)
    {
        for(ll j = 1; j <= w; j++)
        {
            if( j < weights[i-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-weights[i-1]]);
        }
    }
    ll ans = dp[n][w];
    cout<<ans<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t = 1;
    // ll t; cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 79232
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
class Solve{
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        string[] str = Console.ReadLine().Split(' ');
        int N = int.Parse(str[0]);
        int M = int.Parse(str[1]);
        int[] f = new int[M];
        int[] t = new int[M];
        long[] c = new long[M];
        for(int i=0;i<M;i++){
            str = Console.ReadLine().Split(' ');
            f[i] = int.Parse(str[0]) - 1;
            t[i] = int.Parse(str[1]) - 1;
            c[i] = int.Parse(str[2]);
        }
        BellmanFord B = new BellmanFord(f,t,c,N,0,100000000000000,N-1);
        if(B.NegativeCycle()){
            sb.Append("inf\n");
        }
        else{
            sb.Append(B.GetCost(N-1)+"\n");
        }
    }
}
class BellmanFord{
    bool NEGATIVECYCLE;
    long[] cost;
    public BellmanFord(int[] f,int[] t,long[] c,int n,int s,long INF,int G){
        cost = new long[n];
        int e = f.Length;
        for(int i=0;i<n;i++){
            cost[i] = -INF;
        }
        cost[s] = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<e;j++){
                if(cost[f[j]] != -INF){
                    cost[t[j]] = Math.Max(cost[t[j]],cost[f[j]]+c[j]);
                }
            }
        }
        long GC = cost[G];
        for(int i=0;i<n+1;i++){
            for(int j=0;j<e;j++){
                if(cost[f[j]] != -INF){
                    cost[t[j]] = Math.Max(cost[t[j]],cost[f[j]]+c[j]);
                }
            }
        }
        NEGATIVECYCLE = cost[G] != GC;
    }
    public bool NegativeCycle(){
        return NEGATIVECYCLE;
    }
    public long GetCost(int v){
        return cost[v];
    }
}

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

int main(void) {
    unsigned long long int a, b;
    scanf("%lld %lld", &a, &b);
    a--;
    if (a % 4 == 1) a = 1;
    else if (a % 4 == 2) a = a + 1;
    else if (a % 4 == 3) a = 0;
    if (b % 4 == 1) b = 1;
    else if (b % 4 == 2) b = b + 1;
    else if (b % 4 == 3) b = 0;
    printf("%lld\n", a^b);
    return 0;
}

Measured memory_bytes: 128
import sys
input = sys.stdin.buffer.readline

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

N = int(input())

def divisors(n) -> list:
    res = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    #res = sorted(res)
    return res

div1 = divisors(N)
div2 = divisors(N - 1)

cnt = defaultdict(int)
for d in div1:
    cnt[d] += 1
for d in div2:
    cnt[d] += 1

arr = list(cnt.keys())
arr.sort()
#print(arr)

answer = 0

def check(n, k):
    #print(n, k)
    if n < k:
        if n == 1:
            return 1
        else:
            return 0
    if n % k == 0:
        return check(n // k, k)
    else:
        return check(n % k, k)

for a in arr:
    if 2 <= a <= N:
        if check(N, a):
            answer += 1
print(answer)

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

signed main() {
	ll x[5];
	rep(i, 5) cin >> x[i];
	rep(i, 5){
		if(x[i] == 0) cout << i + 1 << endl;
        }
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
  
#define lol long long
#define gcd(x,y) __gcd(x,y)
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define fixed(x) fixed<<setprecision(x)
using namespace std;
using pii=pair<int,int>;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class A> inline A abs(A &a) { return (a < 0 ? -a : a); }
bool inLine(int x,int y,int mx,int my){return (x>=0&&y>=0&&x<mx&&y<my);}
const lol inf=(1LL<<62);
const lol MOD=(1e9)+7;
const lol mod=998244353;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  lol sum=0;
  int n;
  cin >>n;
  vector<lol> a(n);
  for(int i=0;i<n;i++){
    cin >>a[i];
    sum+=a[i];
    sum%=MOD;
  }
  lol ans=0;
  for(int i=0;i<n;i++){
    sum-=a[i];
    sum%=MOD;
    sum=(sum+MOD)%MOD;
    ans+=(sum*a[i])%MOD;
    ans%=MOD;
  }
  cout <<ans<<'\n';
  return(0);
}

Measured memory_bytes: 4776
//52
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include<deque>

using namespace std;

int main(){
  for(int m,c,n;cin>>m>>c>>n,m|c|n;){
    queue<deque<int> > que;
    for(int i=0;i<n;i++){
      int k;
      cin>>k;
      deque<int> v(k);
      for(int j=0;j<k;j++){
	cin>>v[j];
      }
      que.push(v);
    }
    int b[100];
    fill(b,b+100,m);
    int cs=0;
    deque<int> d[11];
    while(!que.empty()){
      deque<int> cv=que.front();
      que.pop();
      int id=cv[0];
      cs+=b[id]+1;
      if(b[id]!=m){
	d[b[id]].erase(find(d[b[id]].begin(),d[b[id]].end(),id));
      }
      if(d[0].size()<c){
	d[0].push_back(id);
	b[id]=0;
	cs++;
      }else{
	int i;
	for(i=1;i<m;i++){
	  if(d[i].size()<c){
	    break;
	  }
	}
	d[i].push_back(id);
	cs+=i+1;
	int j;
	for(j=1;j<m;j++){
	  if(d[j].size()<c)break;
	}
	cs+=j+1;
	d[j].push_back(d[0][0]);
	b[d[0][0]]=j;
	d[0].pop_front();
	cs++;
	d[0].push_back(id);
	cs++;
	d[i].pop_back();
	cs+=i+1;
	b[id]=0;
      }
      if(cv.size()>1){
	cv.pop_front();
	que.push(cv);
      }
    }
    cout<<cs<<endl;
  }
  return 0;
}

Measured memory_bytes: 1304
#include<cstdio>
const int N = 2e3+5;
int sum[2000+5];
int cnt[2000+5];
int a[2000+5];

int max(int a,int b){ return a>b?a:b; }
//闭区间
int getCnt(int lower,int upper){
    if(lower>upper) return 0;
    else return sum[upper]-sum[lower-1];
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    sum[0] = 0;
    for(int i = 1; i <= 2003; i++){
        sum[i] = sum[i-1]+cnt[i];
    }
    //本身不能算
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i==j) continue;
            int lower = max(a[i]-a[j],a[j]-a[i])+1, upper = a[i]+a[j]-1;
            long long count = getCnt(lower,upper);
            if(a[i]>=lower && a[i]<=upper) count--;
            if(a[j]>=lower && a[j]<=upper) count--;
            //printf("lower = %d, upper = %d\n",lower,upper);
            //printf("a = %d, b = %d, cnt = %d\n",a[i],a[j],getCnt(lower,upper));
            ans += count;
        }
    }
    printf("%lld\n",ans/6ll);
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

#define ABS(x) ((x) >= 0 ? (x) : -(x))
#define MAX_N (100000)

int main(int argc, char *argv[]) {
  int N, t[MAX_N + 1], x[MAX_N + 1], y[MAX_N + 1];
  // read inputs
  scanf("%d", &N);
  t[0] = 0; x[0] = 0; y[0] = 0;
  for (int i = 1; i <= N; i++)
    scanf("%d %d %d", &t[i], &x[i], &y[i]);
  // check
  for (int i = 1; i <= N; i++) {
    int min_time = ABS(x[i] - x[i - 1]) + ABS(y[i] - y[i - 1]);
    int delta_t = t[i] - t[i - 1];
    if (!(min_time <= delta_t && (delta_t - min_time) % 2 == 0)) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}


Measured memory_bytes: 1280
using System;
using System.Linq;
using System.Collections.Generic;
class c
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var list = new List<Tuple<int, int>>();
        for (int i = 0; i < n; i++)
        {
            var temp = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            var tup = new Tuple<int, int>(temp[0], temp[1]);
            list.Add(tup);
        }
        list = list.OrderBy(f => f.Item2).ToList();
        bool job = true;
        int time = 0;
        for (int i = 0; i < list.Count(); i++)
        {
            time += list[i].Item1;
            if (time > list[i].Item2) job = false;
        }
        Console.WriteLine(job ? "Yes" : "No");
    }
}

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

int no(int n){
    int i = 0;
    if(n%2 != 0)return 0;
    while(n%2 == 0){
        n/= 2;
        i++;
    }
    return i;
}


int main() {
    int n;
    int minn = 10000000;
    cin >> n;
    while(n--){
        int a;
        cin >> a;
        //if(a%2 == 0)minn = 0;
        minn = min(minn,no(a));
    }
    cout << minn;
	return 0;
}

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

typedef long long ll;

#define PB push_back
#define MP make_pair

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    string s, t; cin >> s >> t;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != t[i]) ans++;
    }
    cout << ans << "\n";
}



Measured memory_bytes: 3776
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <iostream>
#include <cmath>

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
typedef long long ll;
using namespace std;


void solve(long long N, std::string S){
    int ans = 0;
    REP(i, N-2) {
        if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C') {
            ans++;
        }
    }
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;
    solve(N, S);
    return 0;
}


Measured memory_bytes: 256
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


int main() {
	string s;
	cin >> s;

	int n = s.size();
	int cnt = 0;
	rep(i, n - 1) {
		if (s[i] != s[i + 1]) cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

type bufReader struct {
	r   *bufio.Reader
	buf []byte
	i   int
}

var reader = &bufReader{
	bufio.NewReader(os.Stdin),
	make([]byte, 0),
	0,
}

func (r *bufReader) readLine() {
	if r.i < len(r.buf) {
		return
	}
	r.buf = make([]byte, 0)
	r.i = 0
	for {
		line, isPrefix, err := r.r.ReadLine()
		if err != nil {
			panic(err)
		}
		r.buf = append(r.buf, line...)
		if !isPrefix {
			break
		}
	}
}

func (r *bufReader) next() string {
	r.readLine()
	from := r.i
	for ; r.i < len(r.buf); r.i++ {
		if r.buf[r.i] == ' ' {
			break
		}
	}
	s := string(r.buf[from:r.i])
	r.i++
	return s
}

func (r *bufReader) nextLine() string {
	r.readLine()
	s := string(r.buf[r.i:])
	r.i = len(r.buf)
	return s
}

var writer = bufio.NewWriter(os.Stdout)

func next() string {
	return reader.next()
}

func nextInt64() int64 {
	i, err := strconv.ParseInt(reader.next(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func nextInt() int {
	return int(nextInt64())
}

func nextLine() string {
	return reader.nextLine()
}

func out(a ...interface{}) {
	fmt.Fprintln(writer, a...)
}

func max64(x, y int64) int64 {
	if x > y {
		return x
	}
	return y
}

func max(x, y int) int {
	return int(max64(int64(x), int64(y)))
}

func min64(x, y int64) int64 {
	if x < y {
		return x
	}
	return y
}

func min(x, y int) int {
	return int(min64(int64(x), int64(y)))
}

func abs64(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

func abs(x int) int {
	return int(abs64(int64(x)))
}

func joinInt64s(a []int64, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.FormatInt(v, 10)
	}
	return strings.Join(b, sep)
}

func joinInts(a []int, sep string) string {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = strconv.Itoa(v)
	}
	return strings.Join(b, sep)
}

func divUp64(x, y int64) int64 {
	return (x + y - 1) / y
}

func divUp(x, y int) int {
	return int(divUp64(int64(x), int64(y)))
}

func gcd64(x, y int64) int64 {
	if x < y {
		x, y = y, x
	}
	for y != 0 {
		x, y = y, x%y
	}
	return x
}

func gcd(x, y int) int {
	return int(gcd64(int64(x), int64(y)))
}

func lcm64(x, y int64) int64 {
	return x * y / gcd64(x, y)
}

func lcm(x, y int) int {
	return int(lcm64(int64(x), int64(y)))
}

func pow64(x, y int64) int64 {
	return int64(math.Pow(float64(x), float64(y)))
}

func pow(x, y int) int {
	return int(pow64(int64(x), int64(y)))
}

func main() {
	solve()
	writer.Flush()
}

type pair struct {
	i, j int
}

func solve() {
	N := nextInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = nextInt()
	}
	sort.Ints(A)
	for i := 0; i < N; i++ {
		if N&1 == 0 {
			if (i&1 == 0 && A[i] != i+1) || (i&1 == 1 && A[i] != i) {
				out(0)
				return
			}
		} else {
			if (i&1 == 0 && A[i] != i) || (i&1 == 1 && A[i] != i+1) {
				out(0)
				return
			}
		}
	}
	if N&1 == 1 {
		N--
	}
	ans := 1
	for i := 0; i < N/2; i++ {
		ans = ans * 2 % 1000000007
	}
	out(ans)
}


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

bool flag[1000000001]={0};

string tostring(int x){
	if(x==0) return "0";
	string s="";
	while(x>0){
		char c=x%10+'0';
		x/=10;
		s=s+c;
	}
	return s;
}

int main(){
	map<string,int > mp;
	int n;cin >>n;
	int res=0;
	for(int i=0;i<n;i++){
		int x;cin >> x;
		string s=tostring(x);
		if(mp[s]==0){
			mp[s]=1;
			res++;
		}
		else if(mp[s]==1){
			mp[s]=0;
			res--;
		}
	}
	
	cout << res;
	return 0;
}

Measured memory_bytes: 12544
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

/*
<url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0358>
?????????============================================================
 ????????????????????\????£????????????°??????????????°???????????°???????????????????????????????????????????????????????????¨??¬?±??????\???????????????
 ???????????????????????????????????¬????????????????????§???????????????????????§?¶????????????¨????????????????????????????????????????????¨?????£???????????????
 ????????§????¶???????????????°???????????????????????????????????????????????????
 
 ?????????????????????????????????????????????????????????????????¬?????????????????????????????¨??????
 ??¬???????????????????????????????????????????????°????????????????°?????????????????????????????????°????????????????????????

=================================================================

?§£??¬=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll m,f,b; cin >> m >> f >> b;
    if(m + f < b){
        cout << "NA" << endl;
    }else{
        cout << ((m < b)?b-m:0) << endl;
    }
	return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
  int N; cin >> N;
  vector<vector<int>> seat(N, vector<int>(N));
  vector<vector<bool>> on(N, vector<bool>(N, true));
  vector<pair<int, int>> P(N * N);
  rep(a, N * N) {
    int x; cin >> x; x--;
    P[a] = make_pair(x / N, x % N);
  }

  rep(a, N) rep(b, N) {
    seat[a][b] = min({a, N - 1 - a, b, N - 1 - b});
  }

  long long ans = 0;
  rep(i, N * N) {
    int a, b;
    tie(a, b) = P[i];
    ans += seat[a][b];
    on[a][b] = false;
    queue<pair<int, int>> q;
    q.emplace(a, b);
    seat[a][b]--;
    while(!q.empty()) {
      int x, y;
      tie(x, y) = q.front(); q.pop();
      int now = seat[x][y];
      rep(d, 4) {
        if (min(x + dx[d], y + dy[d]) < 0) continue;
        if (max(x + dx[d], y + dy[d]) >= N) continue;
        int t = now + 2;
        if (!on[x + dx[d]][y + dy[d]]) t--;
        if (seat[x + dx[d]][y + dy[d]] == t) {
          seat[x + dx[d]][y + dy[d]]--;
          q.emplace(x + dx[d], y + dy[d]);
        }
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 6168
#include <bits/stdc++.h>
using namespace std;
int main() {
    double N,M,c;
    double sum = 0;
    vector<double> a;
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        cin >> c;
        a.push_back(c);
        sum += c;
    }
    sort(a.begin(),a.end(),greater<double>());
    if (a[M-1]<sum/(M*4)) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 256
N,M=map(int, input().split())

A=[list(input()) for i in range(N)]
B=[list(input()) for i in range(M)]




flag=0
for i in range(N-M+1):
    for j in range(N-M+1):
        for t in range(M):
            for s in range(M):
                if A[i+t][j+s]==B[t][s]:
                    flag+=1
        if flag==M*M: break
        else: flag=0
    if flag==M*M: break

if flag==0: print("No")
else: print("Yes")


Measured memory_bytes: 3064
s=input()

cnt=0
while len(s)>1:
    if s[0]==s[-1]:
        s= s[1:-1]
    elif s[0]=="x" and s[-1]!="x":
        s = s[1:]
        cnt +=1
    elif s[-1]=="x" and s[0]!="x":
        s = s[:-1]
        cnt +=1
    else:
        cnt=-1
        break
print(cnt)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,M,X;
  cin >> N >> M >> X;
  vector<int> A(M);
  rep(i,M)
  {
    cin >> A[i];
  }
  int m,n = 0;
  for(int i=0;i<N+1;i++)
  {
    for(int j=0;j<M;j++)
    {
      if(i==A[j]&&i<X)
      {
        m ++;
      }
      else if(i==A[j]&&i>X)
      {
        n ++;
      }
    }
  }
  cout << min(m,n) << endl;
  return 0;
}


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

#define fi first
#define se second

const int K = 100100;

using namespace std;


int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(0);

        string s;
        int k;
        cin >> s >> k;
        vector < int > v;
        for(int i = 0; i < s.size(); i++){
                if(i == 0 || s[i] != s[i - 1]){
                        v.push_back(1);
                } else{
                        v.back() += 1;
                }
        }
        if(v.size() == 1){
                cout << 1ll * s.size() * k / 2 << "\n";
        } else{
                long long res = 0;
                for(int x: v){
                        res += x / 2;
                }
                res *= k;
                if(s[0] == s.back()){
                        res += ((v[0] + v.back()) / 2 - v[0] / 2 - v.back() / 2) * 1ll * (k - 1);
                }
                cout << res << "\n";
        }
}


Measured memory_bytes: 256