akhauriyash/Code-Regression huggingface dataset:
// AtCoder Grand Contest 019
// D - Shift and Flip

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAX_N = 2000;

int N;
bitset<MAX_N + 1> A, B;

int solve() {
    if (B.none()) {
        if (A.none()) {
            return 0;
        }
        return -1;
    }

    // cout << A.to_string().substr(MAX_N + 1 - N) << endl;
    // cout << B.to_string().substr(MAX_N + 1 - N) << endl;
    // cout << endl;

    int ret = 2 * N;
    bitset<MAX_N + 1> b = B, mask = B, remain;
    for (int d = 0; d <= N; d++) {
        // cout << A.to_string().substr(MAX_N + 1 - N) << endl;
        // cout << b.to_string().substr(MAX_N + 1 - N) << endl;
        // cout << mask.to_string().substr(MAX_N + 1 - N) << endl;
        vector<int> li(N), ri(N);

        li[N - 1] = N - 1;
        while (!mask[li[N - 1] % N]) {
            li[N - 1]++;
        }
        for (int i = N - 2; i >= 0; i--) {
            li[i] = mask[i] ? i : li[i + 1];
        }

        ri[0] = 0;
        while (!mask[(ri[0] + N) % N]) {
            ri[0]--;
        }
        for (int i = 1; i < N; i++) {
            ri[i] = mask[i] ? i : ri[i - 1];
        }

        vector<pii> xys;
        xys.push_back(pii(0, 0));
        remain = (A ^ b) & (~mask);
        // cout << remain.to_string().substr(MAX_N + 1 - N) << endl;
        for (int i = 0; i < N; i++) {
            if (remain[i]) {
                xys.push_back(pii(li[i] - i, i - ri[i]));
            }
        }
        sort(xys.begin(), xys.end());

        vector<int> y_max(xys.size() + 1);
        y_max[xys.size()] = 0;
        for (int i = xys.size() - 1; i >= 0; i--) {
            y_max[i] = max(y_max[i + 1], xys[i].second);
        }
        int k = N;
        for (int i = 0; i < (int)xys.size(); i++) {
            // cout << xys[i].first << ", " << y_max[i] << endl;
            k = min(k, xys[i].first + y_max[i + 1]);
        }
        ret = min(ret, d + 2 * k + (int)(A ^ b).count());
        // cout << d << ", " << k << ", " << (A ^ b).count() << ", " << ret
        //      << endl;

        b <<= 1;
        b[0] = b[N];
        b[N] = 0;
        mask |= b;
    }

    // cout << endl;
    return ret;
}

void rev(bitset<MAX_N + 1> &a) {
    string tmp = a.to_string().substr(MAX_N + 1 - N);
    reverse(tmp.begin(), tmp.end());
    a = bitset<MAX_N + 1>(tmp);
}

int main() {
    string tmp;
    cin >> tmp;
    A = bitset<MAX_N + 1>(tmp);
    cin >> tmp;
    B = bitset<MAX_N + 1>(tmp);
    N = tmp.size();

    int ans = solve();
    rev(A);
    rev(B);
    ans = min(ans, solve());

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <utility>
#include <cctype>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;

#define at(v,p) v[p/100][p%100]

int w, h;
int len[11][10];
string field[22];

int dif[] = { -100, -1, 1, 100 };


int fromto(int from, int index){
	queue<pii> q;
	q.push( pii( 0, from ) );

	vector<bitset<22> > visit( 22 );
	visit[from / 100].set( from % 100 );
	
	int count = 0;
	while( !q.empty() ){
		pii p = q.front();
		q.pop();
		int pos = p.second;

		if( isdigit( at( field, pos ) ) ){
			len[index][ at( field, pos ) - '0' ] = p.first;
			++count;
		}

		for( int i = 0; i < 4; ++i ){
			int newpos = pos + dif[i];
			if(
				at( field, newpos ) != 'x' && 
				!at( visit, newpos )
			){
				visit[newpos / 100].set( newpos % 100 );
				q.push( pii( p.first + 1, newpos ) );
			}
		}
	}
	
	return count;
}


int solve(){
	int cnt_dirty = 0;
	int start;
	vector<int> d_pos(10);

	for( int i = 1; i <= h; ++i ){
		for( int j = 1; j <= w; ++j ){
			switch( field[i][j] ){
				case '*':
					field[i][j] = cnt_dirty + '0';
					d_pos[cnt_dirty] = i * 100 + j;
					++cnt_dirty;
					break;
				case 'o':
					start = i * 100 + j;
					break;
			}
		}
	}

	if( fromto( start, 10 ) != cnt_dirty ){
		return -1;
	}

	for( int i = 0; i < cnt_dirty; ++i ){
		fromto( d_pos[i], i );
	}



	vector<vector<int> > dp( 10, vector<int>( 1 << 10, 10000 ) );
	for( int i = 0; i < cnt_dirty; ++i ){
		dp[i][1 << i] = len[10][i];
	}
	int last = (1 << cnt_dirty) - 1;
	for( int S = 1; S < last; ++S ){
		for( int i = 0; i < cnt_dirty; ++i ){
			if( S >> i & 1 ){
				for( int j = 0; j < cnt_dirty; ++j ){
					if( !(S >> j & 1) ){
						dp[j][S | 1 << j] =
							min( dp[j][S | 1 << j], dp[i][S] + len[i][j] );
					}
				}
			}
		}
	}

	int ret = 20000;
	for( int i = 0; i < cnt_dirty; ++i ){
		ret = min( ret, dp[i][last] );
	}
	return ret;
}


int main(){
	field[0] = string( 22, 'x' );
	string s;

	while( cin >> w >> h, w != 0 ){
		for( int i = 1; i <= h; ++i ){
			cin >> s;
			field[i] = 'x' + s + 'x';
		}
		field[h + 1] = field[0];

		cout << solve() << endl;
	}
}

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



int main() {
	int n;
  	cin>>n;
  	
  	vector<int> a(n);
  	rep(i,n){cin>>a[i];
  	}
     
  sort(a.begin(),a.end());
  bool ans=true;
  
  for(int i=0;i<n;i++){
  	if(a[i]==a[i+1]){
    	ans=false;
    }
    
  }
	
  
  if(ans)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  
  
  
  
}

Measured memory_bytes: 4008
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	long double a,b,h,m,H,M;
	cin>>a>>b>>h>>m;
	M=m*6.0;
	H=h*30.0+m*30.0/60.0;
	long double now=abs(H-M);
	double co=now*M_PI/180.0;
	long double ans=a*a+b*b-2.0*a*b*cos(co);
	ans=sqrt(ans);
	printf("%.11Lf",ans);
	// your code goes here
	return 0;
}

Measured memory_bytes: 4160
#ifndef DEBUG
#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 61;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

    int n;
    cin >> n;
    vector<int> l(n);
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }

    Int ans = 0;
    for (int i = 0; i < n; i++) {
        int a = l[i];
        for (int j = i + 1; j < n; j++) {
            int b = l[j];
            for (int k = j + 1; k < n; k++) {
                int c = l[k];
                if (a != b && c != b && a != c) {
                    if (c < a + b && b < a + c && a < b + c) {
                        ans++;
                    }
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
n,l=map(int,input().split())
a=[]
b=[]
for i in range(1,n+1):
  a.append(l+i-1)
  b.append(abs(l+i-1))
for i in range(n):
  if b[i]==min(b):
   d=a[i]
print(sum(a)-d)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX = 100005;
struct Node {
	int key;
	Node *parent, *left, *right;
};
Node *root, *NIL;

//????????????
void PreorderTreeWalk(Node *u) {
	if (u == NIL)
		return;
	printf(" %d", u->key);
	PreorderTreeWalk(u->left);
	PreorderTreeWalk(u->right);
}
//????????????
void InorderTreeWalk(Node *u) {
	if (u == NIL)
		return;
	InorderTreeWalk(u->left);
	printf(" %d", u->key);
	InorderTreeWalk(u->right);
}


void insert(int value) {
	Node *y = NIL, *x = root;
	Node *z = new Node();
	z->key = value;
	z->left = z->right = NIL;

	// ????????????????????????
	while (x != NIL) {
		y = x;
		// z ??? x ?°???? ??????x????????§??????
		// z ??? x ??§??? ??????x????????§??????
		if (z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}

	z->parent = y;

	// ????????¶????????????root
	if (y == NIL) {
		root = z;
	}else {
		// z ??? y ?°???? ?????¨y????????§
		// z ??? y ??§??? ?????¨y????????§
		if (z->key < y->key)
			y->left = z;
		else
			y->right = z;
	}
}

Node * find(Node *u, int value) {
	
	// ????????????????§?????????????
	while (u != NIL && u->key != value) {
		if (value < u->key)
			u = u->left;
		else
			u = u->right;
	}
	return u;
}

int main() {
	int n, value;
	Node * f;
	char s[200];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		if (s[0] == 'i') {
			scanf("%d", &value);
			insert(value);
		}
		else if (s[0] == 'f') {
			scanf("%d", &value);
			f = find(root,value);
			if (f != NIL)
				printf("yes\n");
			else
				printf("no\n");
		}else {
			InorderTreeWalk(root);
			printf("\n");
			PreorderTreeWalk(root);
			printf("\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 21880
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;
int main()
{

  ll n,a[110],ans=1LL<<60;
  cin>>n;
  rep(i,n){
    cin>>a[i];
  }

  for(ll m=-100;m<=100;m++){
    ll tmp=0;
    rep(i,n){
      tmp+=(a[i]-m)*(a[i]-m);
    }
    ans=min(ans,tmp);
  }


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


Measured memory_bytes: 3576
#!/usr/bin/env python3

import sys
input = sys.stdin.readline
N, M, K=map(int, input().split())

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

    def same(self, x, y): return self.root(x) == self.root(y)

    def count(self, x): return -self.parent[self.root(x)]

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

friend_or_block = [set() for _ in range(N)]
friends_chain = UnionFindTree(N)

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    friends_chain.unite(a, b)
    friend_or_block[a].add(b)
    friend_or_block[b].add(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if friends_chain.same(c, d):
        friend_or_block[c].add(d)
        friend_or_block[d].add(c)

print(' '.join(map(str, [friends_chain.count(i) - len(friend_or_block[i]) - 1 for i in range(N)])))


Measured memory_bytes: 68528
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>  
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;
using namespace mp;
using namespace std;
#define eps 0.00000001
#define LONG_INF 10000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
cpp_int gcd(cpp_int a,cpp_int b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
cpp_int lcm(cpp_int a, cpp_int b) {
	return a*b / gcd(a, b);
}
int main() {
	int n;
	cin >> n;
	cpp_int lcmer = 1;
	REP(i, n) {
		long long t;
		cin >> t;
		lcmer = lcm(lcmer, t);
	}
	cout << lcmer << endl;
	return 0;
}

Measured memory_bytes: 384
v = lambda: list(map(int,input().split()))
n,m,l = v()
a = [v() for i in range(n)]
b = [v() for i in range(m)]
t = [[b[i][j] for i in range(m)] for j in range(l)]
for i in range(n):
	print(*(sum(x*y for x,y in zip(a[i], t[j])) for j in range(l)))



Measured memory_bytes: 6676
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <queue>

#define MAX_N 200000

using namespace std;

int A[MAX_N];
priority_queue<pair<int, int> > pq;

int main()
{
    int N, i;
    long long comfort;

    scanf("%d", &N);
    for(i = 0; i < N; ++i)
        scanf("%d", &A[i]);
    sort(A, A + N, greater<int>());

    comfort = 0;
    pq.push(make_pair(A[0], A[0]));
    for(i = 1; i < N; ++i){
        pair<int, int> current = pq.top();
        comfort += current.first;
        pq.pop();
        pq.push(make_pair(A[i], current.first));
        pq.push(make_pair(A[i], current.second));
    }

    printf("%lld", comfort);

    return 0;
}


Measured memory_bytes: 5636
#include <bits/stdc++.h>
using namespace std;
using ll= long long ;
using P = pair<ll,ll>;
#define rep(i,n) for (ll i = 0; i<(ll)(n); i++)
#define mod 1000000007
#define pi 3.141592653589793
typedef vector<ll> vcl;

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t =rep_jijo(n,x/2);
        return t*t%mod;
  }
  return n*rep_jijo(n,x-1)%mod;
}
ll c2(ll n){
    return n*(n-1)/2;
}

int main(){
    ll n;
    cin>>n;
    vcl a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(), a.end()); 
    reverse(a.begin(), a.end());
    ll ans=0;
    if(n%2==0){
        rep(i,n/2){
            ans+=a[i];
        }
        ans=2*ans;
        ans-=a[0];
    }
    if(n%2==1 && n!=1){
        rep(i,(n+1)/2){
            ans+=a[i];
        }
        ans=2*ans;
        ans-=a[0]+a[(n-1)/2];

    }
    cout<<ans<<endl;
}



Measured memory_bytes: 4780
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
#include <wchar.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
日にち、前やったやつ
*/

ll n,a[100010][3],dp[100010][3];

int main(void){
	cin>>n;
	rep(i,n+2)rep(j,3)dp[i][j]=0;
	reg(i,1,n)cin>>a[i][0]>>a[i][1]>>a[i][2];
	reg(i,1,n){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i][0];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i][1];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+a[i][2];
	}
	cout<<max({dp[n][0],dp[n][1],dp[n][2]})<<endl;
	return 0;
}

Measured memory_bytes: 4992
(defun sum (x)  
  (let ((ret 0))
    (loop
       (if (zerop x) (return))
       (setf ret (+ ret (rem x 10)))
       (setf x (floor x 10)))
    ret))

(defun fun (n a b)
  (let ((ans 0)
	(x 0))
    (dotimes (i (1+ n))
      (setf x (sum i))
      (if (and
	   (<= a x)
	   (>= b x))
	  (setf ans (+ ans i))))
    ans))

(format t "~A~%" (fun (read) (read) (read)))


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

int main() {
    long long N; cin >> N;
    string S, T; cin >> S >> T;
    vector<long long>DP(N, 0);
    DP.at(0) = (S.at(0) == T.at(0) ? 3 : 6);
    for (long long i = 1; i < N; i++) {
        if (S.at(i - 1) == T.at(i - 1)) {
            if (S.at(i) == T.at(i)) {
                DP.at(i) = DP.at(i - 1) * 2;
            }
            else {
                DP.at(i) = DP.at(i - 1) * 2;
            }
        }
        else {
            if (S.at(i) == T.at(i)) {
                DP.at(i) = DP.at(i - 1);
            }
            else {
                if(S.at(i) == S.at(i - 1)) {
                    DP.at(i) = DP.at(i - 1);
                }
                else {
                    DP.at(i) = DP.at(i - 1) * 3;
                }
            }
        }
        DP.at(i) %= 1000000007;
    }
    cout << DP.at(N - 1) << endl;
}

Measured memory_bytes: 3632
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class Main{
	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-12;

	int n;
	int[] pow;
	String[] names;
	HashSet<String>[] sets;

	@SuppressWarnings("unchecked")
	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			names=new String[n];
			pow=new int[n];
			sets=new HashSet[n];
			for(int j=0; j<n; j++){
				names[j]=sc.next();
				pow[j]=sc.nextInt();
				sets[j]=new HashSet<String>();
				int m=sc.nextInt();
				for(int i=0; i<m; i++){
					sets[j].add(sc.next());
				}
			}
			solve();
		}
	}

	long[] g;
	int[] _;
	int ans;

	void solve(){
		HashMap<String, Integer> map=new HashMap<String, Integer>();
		for(int i=0; i<n; i++){
			map.put(names[i], i);
		}
		g=new long[n];
		for(int i=0; i<n; i++){
			for(String s : sets[i]){
				int j=map.get(s);
				g[i]|=1L<<j;
			}
		}
		// _:順番->ID
		_=new int[n];
		for(int i=0; i<n; i++){
			_[i]=i;
		}
		for(int i=n-1; i>=1; i--){
			int j=(int)(random()*(i+1));
			int t=_[i];
			_[i]=_[j];
			_[j]=t;
		}
		if(false)
			for(int j=0; j<n; j++){
				for(int i=j+1; i<n; i++){
					if(Long.bitCount(g[_[i]])>Long.bitCount(g[_[j]])){
						int t=_[i];
						_[i]=_[j];
						_[j]=t;
					}
				}
			}

		ans=0;
		// mis(1, 1, pow[0]);
		mis_(0, 1, pow[0]);
		println(ans+"");
	}

	void mis_(int k, long choosed, int sum){
		if(k==n){
			ans=max(ans, sum);
			return;
		}
		if((choosed&(g[_[k]]|(1L<<_[k])))==0){
			mis_(k+1, choosed|(1L<<_[k]), sum+pow[_[k]]);
			long rem=0;
			for(int i=k+1; i<n; i++){
				if((choosed&g[_[i]])==0)
					rem|=g[_[i]];
			}
			if((rem>>>_[k]&1)==0){
				return;
			}
		}
		mis_(k+1, choosed, sum);
	}

	void mis(int k, long choosed, int sum){
		if(k==n){
			// String c=Long.toBinaryString(choosed);
			// for(; c.length()<n; c="0"+c);
			// debug(c, sum);
			ans=max(ans, sum);
			return;
		}
		if((choosed&(g[k]|(1L<<k)))==0){
			mis(k+1, choosed|(1L<<k), sum+pow[k]);
			long rem=0;
			for(int i=k+1; i<n; i++){
				if((choosed&g[i])==0)
					rem|=g[i];
			}
			if((rem>>>k&1)==0){
				return;
			}
		}
		mis(k+1, choosed, sum);
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		new Main().run();
	}
}

Measured memory_bytes: 13000
#define _USE_MATH_DEFINES
#include <math.h>
#include <time.h>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iomanip>
#include <iterator>
#include <algorithm>
#include <functional>
#include <typeinfo>
#include <utility>
#include <tuple>

using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define reprrev(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--)
#define reprev(i, n) reprrev(i, 0, n)

#define answer(formula) formula ? cout << "Yes" << endl : cout << "No" << endl
#define ANSWER(formula) formula ? cout << "YES" << endl : cout << "NO" << endl

#define PI M_PI
#define INF 1050000000
#define MOD 1000000007
#define EPS (1e-10)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<bool>> vvb;
typedef vector<vector<string>> vvs;

constexpr int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

ll Pow(ll a, ll b, ll mod) {
	ll x = 1;
	while (b > 0) {
		if (b & 1) x = x * a;
		a = a * a;
		b = b >> 1;
	}
	return x;
}


/*<ここから>***********************************************************/


int main()
{
	int N;
	cin >> N;
	vi a(N, 0);
	rep(i, N) cin >> a[i];

	sort(a.begin(), a.end());

	int A = 0, B = 0;
	reprev(i, N)
	{
		if ((N - i) % 2 == 1)A += a[i];
		else B += a[i];
	}

	cout << A - B << endl;

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
typedef struct{
  char name[10];
  int time;
}P;

void enqueue(P);
P dequeue(void);
int min(int,int);

int head,tail,n;
P Q[100000];

int main(){
  int q,i,total=0,c;
  P u;

  scanf("%d%d",&n,&q);
  for(i=0;i<n;i++)
    scanf("%s%d",Q[i].name,&Q[i].time);

  head=0;
  tail=n;

  while(head!=tail){
    u=dequeue();
    c=min(q,u.time);
    u.time-=c;
    total+=c;
    if(u.time>0)
      enqueue(u);
    else
      printf("%s %d\n",u.name,total);
  }
  return 0;
}

void enqueue(P x){
  Q[tail]=x;
  if(tail==n)
    tail=0;
  else
    tail++;
}

P dequeue(void){
  P x;
  x=Q[head];

  if(head==n)
    head=0;
  else
    head++;
  return x;
}

int min(int a,int b){
  if(a>=b)
    return b;
  else return a;
}

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

int main() {
  int total_dist = 0;

  int N, K, xi;
  cin >> N >> K;

  for (int i = 0; i < N; i++) {
    cin >> xi;

    if (K - xi < xi) {
      total_dist += (K - xi) * 2 ;
    } else {
      total_dist += xi * 2;
    }
//    cout << "i:" << i << "xi:" << xi << " total:" << total_dist << endl;
  }

  cout << total_dist << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
int n;
int main(){
	cin >> n;
	cout << (n+1)/2;
	return 0;
}

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

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

  ll n, k;
  cin >> n >> k;

  vector<ll> v(n);
  // 重複を判定
  vector<ll> v2(n, 0);
  // 初めてその値に到達したときのcnt
  vector<ll> v3(n, 0);
  for (ll i = 0; i < n; i++)
  {
    ll a;
    cin >> a;
    v.at(i) = a;
  }
  bool dup = false;
  ll index = 0;
  ll count = 0;
  ll count_k = k;
  while (!dup && count_k > 0)
  {
    count++;
    if (v2.at(index) == 1)
    {
      dup = true;
      continue;
    }
    v2.at(index) = 1;
    v3.at(index) = count;
    index = v.at(index) - 1;
    count_k--;
  }
  if (count_k != 0)
  {
    ll q = (k - v3.at(index)) % (count - v3.at(index));
    while (q >= 0)
    {
      index = v.at(index) - 1;
      q--;
    }
  }

  cout << index + 1 << endl;

  return 0;
}

Measured memory_bytes: 7948
#include<stdio.h>
int main()
{
    int k,a,b,i,j=0;
    scanf("%d%d%d",&k,&a,&b);
    i=a;
    while(i>=a&&i<=b)
    {
        if(i%k==0)
        {
            j=1;
            break;
        }
        i++;
    }
    if(j==1)
    {
        printf("OK\n");
    }
    else
    {
        printf("NG\n");
    }
    return 0;
}


Measured memory_bytes: 1648
#include <iostream>
#include <math.h>
using namespace std;

int main( void )
{
	int n;
	int k;
	while ( cin >> n && n > 0 )
	{
		int kotae = 0;
		k = 5;
		while ( n/k >= 1.0 )
		{
			kotae += (int)floor((double)(n/k));
			k *= 5;
		}
		cout << kotae << endl;
	}


	return 0;
}

Measured memory_bytes: 0
program b
    implicit none

    integer n,m,x
    integer i
    real(8),allocatable::a(:)
   
    read(*,*) n,m
    allocate(a(m))
    read(*,*) a(:)
    x=0.d0
    do i=1,m
      x=x+a(i)
    end do
    
    if(n >= x)then 
    write(*,*) n-x
    else 
    write(*,*) -1
    endif

end program b

Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
const int MAX_L = 100000000;
const int MAX_SQRT_B = 10000;
const int INF = 1000000000;
typedef int64_t ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll Q, H, S, D, N;

int main() {
	cin >> Q >> H >> S >> D >> N;
	
	H = min(H, 2 * Q);
	S = min(S, 2 * H);
	if (D > 2 * S) {
		cout << S * N << endl;
	}
	else {
		cout << N / 2 * D + N % 2 * S << endl;
	}
}

Measured memory_bytes: 3588
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

void chmin(int &a,int b) {
	if (a == -1)a = b;
	else if (a > b)a = b;
}



//i個目までの商品まで見たときにA,Bをそれぞれj,kにする最小価格
int dp[45][500][500];
int n, m_a, m_b;

int main() {
	cin >> n >> m_a >> m_b;
	vector<vector<int>>v(n, vector<int>(3, 0));
	rep(i, 0, n) {
		cin >> v[i][0] >> v[i][1] >> v[i][2];
	}

	rep(i, 0, 45)rep(j, 0, 500)rep(k,0,500) { dp[i][j][k] = -1; }
	dp[0][0][0] = 0;

	rep(i, 0, n)rep(j,0,405)rep(k,0,405) {
		if (dp[i][j][k] == -1)continue;
		chmin(dp[i+1][j+v[i][0]][k+v[i][1]],dp[i][j][k]+v[i][2]);
		chmin(dp[i+1][j][k],dp[i][j][k]);
	}

	int ans = 101010;
	for (int i = 1; max(i*m_a, i*m_b) <= 10 * n; i++) {
		if (dp[n][i*m_a][i*m_b] != -1)ans = min(ans,dp[n][i*m_a][i*m_b]);
	}

	if (ans == 101010)cout << "-1" << endl;
	else cout << ans << endl;

	return 0;
}

Measured memory_bytes: 44160
package main

import (
	"fmt"
	"math"
)

func main() {
	a, b, k := SingleInt(), SingleInt(), SingleInt()

	re := []int{}
	ra := Min(a, b)

	for i := ra; 1 <= i; i-- {
		if b%i == 0 && a%i == 0 {
			re = append(re, i)
		}
	}
	fmt.Println(re[k-1])
}

func SingleInt() int {
	var n int
	fmt.Scan(&n)
	return n
}

func Min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}


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


int main() {
    int N;
    cin >> N;
    vector<int> X(N);
    for (int i = 0; i < N; i++) cin >> X[i];

    int res = INT32_MAX;
    for (int i = 1; i <= 100; i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) {
            sum += (X[j] - i) * (X[j] - i);
        }
        res = min(res, sum);
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const int maxn=15;
int a[maxn+1][maxn+1];
int edge[maxn+1][1<<maxn];
int f[maxn+1][1<<maxn],n,m,sum;
const int inf=1e9;
int main(){
	read(n);read(m);
	rep(i,1,m){
		int x,y,z;read(x);read(y);read(z);
		a[x][y]=z;a[y][x]=z;sum+=z;
	}
	rep(i,1,n){
		rep(s,0,(1<<n)-1){
			if((1<<(i-1))&s)continue;
			rep(j,1,n)if((1<<(j-1))&s)edge[i][s]+=a[i][j];
			rep(x,1,n)if((1<<(x-1))&s)rep(y,x+1,n)if((1<<(y-1))&s)
				edge[i][s]+=a[x][y];
			// edge[i][s]+=res;
		}
	}
	rep(i,1,n)rep(s,0,(1<<n)-1)f[i][s]=-inf;
	f[1][1]=0;int ans=0;
	rep(s,0,(1<<n)-1)rep(lst,1,n){
		if(s==((1<<n)-1)&&lst==n)
			lst=n;
		if(!((1<<(lst-1))&s))continue;
		int &res=f[lst][s];
		rep(j,1,n)if(a[lst][j]){
			res=max(res,f[j][s^(1<<(lst-1))]+a[lst][j]);
		}
		for(int news=(s-1)&s;news;news=(news-1)&s){
			assert((news&s)==news);
			res=max(res,f[lst][news]+edge[lst][news^s]);
		}
	}
	rep(s,0,(1<<n)-1)ans=max(ans,f[n][s]);
	printf("%d\n",sum-ans);
	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n;
string s[200010];
vector<string>v;
map<string,int>mp;
signed main(){
    cin>>n;
    rep(i,n){
        cin>>s[i];
        mp[s[i]]++;
    }
    int ma=0;
    for(pair<string,int>p:mp){
        chmax(ma,p.se);
    }
    for(pair<string,int>p:mp){
        if(p.se==ma)v.pb(p.fi);
    }
    sort(all(v));
    for(string t:v)cout<<t<<endl;
    return 0;
}

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

int main(){
  int N,M,a,b;
  cin>>N>>M;
  int city[N];

  for(int i=0;i<N;i++)
    city[i]=0;
  
  for(int i=0;i<M;i++){
    cin>>a>>b;
    city[a-1]++;
    city[b-1]++;   
  }

  for(int i=0;i<N;i++)
    cout<<city[i]<<endl;
  
  return 0;
}


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

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll n;
  cin >> n;
  ll res = 1;
  while (res <= n) {
    res *= 2;
  }
  cout << res/2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define OJ \
        freopen("input.txt","r",stdin); \
        freopen("output.txt","w",stdout);
using namespace std;
  
int main()
{
//  OJ;
ll int n;
cin>>n;
ll int a[n],flag=0,ans=1;
for(int i=0;i<n;i++)
{
  cin>>a[i];
 if(a[i]==0)
 {
   flag=1;
 }
}
if(flag==1)
{
  cout<<0;
  return 0;
}
else{
  for(int i=0;i<n;i++)
  {
    if(a[i]<=1000000000000000000/ans){
      ans*=a[i];
    }
    else{
      cout<<-1;
      return 0;
    }
  }
}
cout<<ans;
}


Measured memory_bytes: 4392
#include <stdio.h>
typedef long long ll;
ll max(ll a, ll b) { return a > b ? a : b; }
int main()
{
	ll a, b, c, d;
	scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
	ll ans = -1000000000000000001;
	ans = max(ans, a * c);
	ans = max(ans, a * d);
	ans = max(ans, b * c);
	ans = max(ans, b * d);
	printf("%lld", ans);
}

Measured memory_bytes: 3164
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define fio                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ull unsigned long long
#define ld long double
#define endl "\n"
#define ff first
#define ss second
#define pi pair<ll, ll>
#define PI 3.141592653589793238462643383279502884L
#define mp make_pair
#define pb push_back
#define fall(i, a, b) for (int i = a; i < b; i++)
#define sz(x) (ll) x.size()
#define all(x) x.begin(), x.end()
#define ed cout << "ed";
#define time_passed 1.0 * clock() / CLOCKS_PER_SEC
ll MOD = 1e9 + 7;
ll MOD1 = 1e9 + 123;
ll MOD2 = 1e9 + 321;
ll T[3001][3001][4];
ll A[3001][3001];
ll R, C;
ll fun(int r, int c, int v)
{
    if (r > R || c > C || v < 0)
        return 0;
    if (T[r][c][v] != -1)
        return T[r][c][v];
ll a=0;
    if (v == 0)
       {   
          
          a= max(a,max(fun(r, c + 1, 0), fun(r + 1, c, 3)));
       
       }
    else
    {
        a = max(a, max(A[r][c] + fun(r + 1, c, 3), fun(r + 1, c, 3)));
        a= max(a, max(A[r][c] + fun(r, c + 1, v - 1), fun(r, c + 1, v)));
    }
    return T[r][c][v] = a;
}
int main()
{
    fio;
    ll t, a, n, q, k, i, l, m, c, u, f, j, p, x, y, b, d;
    ll r;
    cin >> r >> c >> p;
    R = r, C = c;
    memset(T, -1, sizeof(T));

    for (k = 0; k < p; k++)
        cin >> i >> j >> A[i][j];
    // for (i = 1; i <= r; i++)
    // {
    //     for (j = 1; j <= c; j++)
    //         cout << A[i][j] << " ";
    //     cout << endl;
    // }
    cout << fun(1, 1, 3);
    return 0;
}


Measured memory_bytes: 356044
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>

using namespace std;


int main() {
	int n, s[200] = {}, num[200] = {}, result = 0, lamp = 1, in, ax, h, w, m, a, b, c, d, r, tmp=1;
	string str ,str2;
	cin >>str;
	n = str.length();
	in = n;
  	tmp=n;
	for (int i = 1; i < n; i++) {
        
		if (str[i] != str[i - 1]) { tmp = max(i, n - i); }
		if (tmp < in) { in = tmp; }
    
	}
	cout << in;
	

}

Measured memory_bytes: 512
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <climits>
#include <cassert>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)

int main()
{
        int m; cin >> m;
        REP(_, m) {
                set<string> departures;
                string arrival; cin >> arrival;

                // For all division
                FOR(i, 1, arrival.length()) {
                        string a[2], b[2];
                        a[0] = string(arrival, 0, i);
                        b[0] = string(arrival, i);
                        a[1] = string(a[0]);
                        b[1] = string(b[0]);
                        reverse(ALL(a[1]));
                        reverse(ALL(b[1]));

                        // cerr << "---" << endl;
                        // cerr << a[0] << endl;
                        // cerr << a[1] << endl;
                        // cerr << b[0] << endl;
                        // cerr << b[1] << endl;

                        REP(ai, 2) {
                                REP(bi, 2) {
                                        departures.insert(a[ai] + b[bi]);
                                        departures.insert(b[bi] + a[ai]);
                                }
                        }
                }
                cout << departures.size() << endl;
        }
}

Measured memory_bytes: 1292
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll a[200001];

ll labs(ll x){
	if(x<0LL)return -x;
	return x;
}

int main(void){
	scanf("%d",&n);
	ll sum=0;
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	ll res=sum;
	ll sm=0;
	for(int i=0;i<n-1;i++){
		sm+=a[i];
		sum-=a[i];
		if(i==0){
			res=labs(sm-sum);
		}else{
			res=min(res,labs(sm-sum));
		}
	}
	printf("%lld\n",res);
	return 0;
}

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

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

int main() {
  int H,W;
  cin >> H >> W;
  vector< string > A(H);
  vector< vector<int> > d(H, vector<int>(W,-1));
  queue< pair<int,int> > q;
  REP(i,H) {
    cin >> A[i];
    REP(j,W) if (A[i][j] == '#') {
      q.emplace( i,j );
      d[i][j] = 0;
    }
  }
  int ans = 0;
  while ( !q.empty() ) {
    auto v = q.front(); q.pop();
    int y = v.first;
    int x = v.second;
    REP(i,4) {
      int ny = y+dy[i];
      int nx = x+dx[i];
      if ( (ny < 0) || (ny >=H) || (nx < 0) || (nx >= W)) continue;
      if ( d[ny][nx] != -1 ) continue;
      d[ny][nx] = d[y][x]+1;
      q.emplace( ny, nx );
      ans = max(d[ny][nx], ans);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 13456
package main

import (
	"fmt"
	"os"
)

func f(n int) int {
	if n == 1 {
		return 1
	} else {
		return 2*f(n/2) + 1
	}
}

func run() int {
	var h int
	fmt.Scanf("%d\n", &h)

	fmt.Println(f(h))

	return 0
}

func main() {
	os.Exit(run())
}


Measured memory_bytes: 512
#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;
const long long INF = 1LL << 60;
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; }
vector<char> Alphabet = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
vector<char> alphabet = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
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; }
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main()
{
  cout << fixed << setprecision(10);
  int N;
  cin >> N;
  int c = N;
  vector<ll> vec(2100);
  vec[0] = 1;
  for(int i=1;i<2010;i++)
  {
    vec[i] = vec[i-1] * i;
    vec[i] %= P;
  }
  if(N<=2)
  {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  ll count = 0;
  while(c>=0)
  {
    c -= 3;
    if(c<0) break;
    count ++;
    ll ue = vec[c + count - 1];
    ll shita = vec[c] * vec[count-1] % P;
    ll x = ue * modinv(vec[c],P);
    x %= P;
    x *= modinv(vec[count-1],P);
    x %= P;
    ans += x;
    ans %= P;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3612
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.FileNotFoundException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AXorBattle solver = new AXorBattle();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class AXorBattle {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = in.nextLongArray(n);
            String s = in.next();
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '1') {
                    if (a[i] != 0) {
                        out.println(1);
                        return;
                    }
                }

                for (int bit = 0; bit < 60; bit++) {
                    if (((a[i] >> bit) & 1) != 0) {
                        for (int j = 0; j < i; j++) {
                            if (((a[j] >> bit) & 1) != 0) {
                                a[j] ^= a[i];
                            }
                        }
                        break;
                    }
                }
            }
            out.println(0);
        }

    }

    static class FastScanner {
        public BufferedReader br;
        public StringTokenizer st;

        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        public FastScanner(String fileName) {
            try {
                br = new BufferedReader(new FileReader(fileName));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] nextLongArray(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

    }
}



Measured memory_bytes: 38660
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
char matrix[N][N];
bool isTrue[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void change(int H, int W, int sx, int sy, char ch) {
    queue<pair<int, int> > que;
    que.push(pair<int, int>(sx, sy));
    while(que.size()) {
        int nx = que.front().first;
        int ny = que.front().second;
        que.pop();
        for(int i = 0; i < 4; i++) {
            int x = nx + dx[i];
            int y = ny + dy[i];
            if(0 <= x && x < H && 0 <= y && y <= W && isTrue[x][y] == false && matrix[x][y] == ch) {
                isTrue[x][y] = true;
                matrix[x][y] = '.';
                que.push(pair<int, int>(x, y));
            }
        }
    } 
}

int solve(int H, int W) {
    int count = 0;
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            if(matrix[i][j] != '.') {
                change(H, W, i, j, matrix[i][j]);
                count++;
            } 
        }
    }
    return count;
}

int main() {
    int row = 1, col = 1;
    while(scanf("%d%d", &row, &col) && row !=0 && col != 0) {
        memset(isTrue, 0, sizeof(isTrue));
        for(int i = 0; i < row; i++) {
            scanf("%s", matrix[i]);
        }
        printf("%d\n", solve(row, col));
    }
}


Measured memory_bytes: 2760
#include<bits/stdc++.h>
 
#define REP(i,s,N) for (int i=s;i<(N); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;


int main(){
	string S;
	cin >> S;
	bool ans = true;
	int s=S.length()/2;
	if(s==0) ans = false;
	if(S.length()%2!=0){
		ans = false;
	}else{
		for(int i=0;i<s;i++){
			if(S[2*i] != 'h'){ ans = false;break;}
			if(S[2*i+1] != 'i'){ ans = false;break;}
		}
	}
	
	if(ans){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
n=input()
num=map(int,raw_input().split())
max=-1000000
min=1000000
sum=0
for i in range(n):
    if max<num[i]:
        max=num[i]
    if min>num[i]:
        min=num[i]
    sum+=num[i]
print str(min)+" "+str(max)+" "+str(sum)

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

int main(void)
{
  int N;
  cin >> N;
  string S;
  vector<string> v;
  for (int i = 0; i < N; i++)
  {
    cin >> S;
    v.push_back(S);
  }

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

  cout << v.size() << endl;

  return 0;
}

Measured memory_bytes: 11532
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep0(i,n) for(i=0;i<(n);i++)
#define repn(i,m,n) for(int i=(m);i<=(n);i++)

#define PUTLINE cout<<__LINE__<<endl;

int result;
int h,w,c;

void value(int a[10][10]){
	int used[10][10]={};
	int r;
	rep(i,h)rep(j,w){
		if(used[i][j]||a[i][j]!=c)continue;
		r=0;
		stack<pint> st;
		st.push(mp(i,j));
		while(!st.empty()){
			pint pos=st.top();
			st.pop();
			if(pos.first<0||h<=pos.first||pos.second<0||w<=pos.second)continue;
			if(used[pos.first][pos.second]||a[pos.first][pos.second]!=c)continue;
			used[pos.first][pos.second]=1;
			++r;
			int xx[]={1,-1,0,0};
			int yy[]={0,0,1,-1};
			rep(k,4){
				pint next=pos;
				next.first+=xx[k];
				next.second+=yy[k];
				st.push(next);
			}
		}
		chmax(result,r);
	}
}

void solve(int a[10][10],int n){
	if(n==0){
		value(a);
		return;
	}
	int color=a[0][0];
	int next[10][10];
	repn(i,1,6){
		if(i==color)continue;
		rep(j,h)rep(k,w)next[j][k]=a[j][k];
		stack<pint> st;
		st.push(mp(0,0));
		while(!st.empty()){
			pint pos=st.top();
			st.pop();
			if(pos.first<0||h<=pos.first||pos.second<0||w<=pos.second)continue;
			if(next[pos.first][pos.second]==color){
				next[pos.first][pos.second]=i;
				int xx[]={1,-1,0,0};
				int yy[]={0,0,1,-1};
				rep(k,4){
					pint next=pos;
					next.first+=xx[k];
					next.second+=yy[k];
					st.push(next);
				}
			}
		}
		solve(next,n-1);
	}
}

int main() {
	int a[10][10];
	for(;;){
		cin>>h>>w>>c;
		if(h==0)break;
		rep(i,h)rep(j,w){
			cin>>a[i][j];
		}
		result=0;
		solve(a,5);
		cout<<result<<endl;
	}
	return 0;
}

Measured memory_bytes: 0