akhauriyash/Code-Regression huggingface dataset:
n,m,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
i = 0
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)
i = 0
for i in range(2 ** n):
    for j in range(n):
        if ((i >> j) & 1):
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]
i = 0
j = 0
ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

if ans==[]:
    print(-1)
else:
    print(min(ans))


Measured memory_bytes: 11228
N, A, B, C, D = map(int, input().split())
S = input()
p = 0
t = 0
stri = 0
for i in range(A-1, max(C, D) - 1):
  if S[i:i+2] == '##':
    p = 1
for j in range(B-1, min(C, D) - 1):  
  if S[j:j+3] == '...':
    if stri == 0:
      stri = j + 1
    t = 1
if S[B] == '.' and S[B-2] == '.':
  t = 1
if (C < D and p == 0) or (C > D and p == 0 and t == 1 and stri <= D-1):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3572
package main

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

func main() {
	N := readInt()
	L := make([]int, N)
	for i := 0; i < N; i++ {
		L[i] = readInt()
	}

	sort.Sort(sort.IntSlice(L))
	result := 0
	for i := 0; i < N-2; i++ {
		for j := i + 1; j < N-1; j++ {
			result += sort.SearchInts(L[j+1:], L[i]+L[j])
		}
	}
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    int n,k; cin >> n >> k;
    vector<vector<int>> g(n+1);
    int m = 0;

    int lim = (n-1)*(n-2)/2;
    if(k > lim){
        puts("-1");
        return 0;
    }

    rep(i,n-1){
        g[1].push_back(i+2);
    }
    m += n-1;

    int cnt = 0;
    if(cnt < lim-k){
        FOR(j,2,n){
            FOR(i,j+1,n+1){
                g[j].push_back(i);
                cnt++;
                if(cnt == lim-k) break;
            }
            if(cnt == lim-k) break;
        }
    }    
    m += cnt;

    cout << m << endl;
    FOR(i,1,n+1){
        for(auto j : g[i]){
            cout << i << " " << j << endl;
        }
    }
}


Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
import sys
n= input()
n = int(n)
a = input()
b = a.split()
c=[]
for i in range(n) :
    c.append(int(b[i]))
m = mean(c)
for i in range(n) :
    if c[0] != c[i]: break
    if i == n-1:
        print(0)
        sys.exit()
for i in range(n) :
    c[i] = c[i] - m
    c[i] = abs(c[i])
f = min(c)
print(c.index(f))


Measured memory_bytes: 5396
#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define str string

ll MOD = 1000000007, INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Max = INF, Min = -1;
int a = 0, b = 0, c = 0, n = 0, m = 0, k = 0, sum = 0, MASK = 0;
ll A[500000] = {}, B[500000] = {}, X[1500][13], rui[500000] = {}, dp[1 << 12] = {};
int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
vector <ll> v;
str S, T;
bool check = true, check2 = false;

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

int main() {
	//Code Line
	cin >> a >> b;
	cout << max( 0,a - (2 * b)) << endl;

	return 0;
}


Measured memory_bytes: 256
an, bn, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

r = min(a) + min(b)
for i in range(m):
    x, y, c = map(int, input().split())
    r = min(r, a[x-1] + b[y-1] - c)

print(r)



Measured memory_bytes: 18648
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		double pai2=6.28318530717958623200;

		Scanner sc = new Scanner(System.in);
		long r = (long)sc.nextInt();
		sc.close();
		System.out.println(r*pai2);
	}
}


Measured memory_bytes: 27128
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;

int main(void){

  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if((a+b) == (c+d)){
    cout << "Balanced" << endl;
  } else if((a+b) > (c+d)){
    cout << "Left" << endl;
  } else {
    cout << "Right" << endl;
  }
  return 0;
}

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

int main (void){
  long long int n = 0,h = 1,z = 0;
  string s;
  cin >> s;

  n = s.size();
  reverse(s.begin(),s.end());

  vector<long long int> a(n);
  vector<long long int> b(n);
  vector<long long int> c(n,0);

  int l[2020] = {};
  for(int i = 0;i < n;i++){
    a[i] = s[i] - '0';
  }

  for(int i = 0;i < n;i++){
    b[i] = a[i] * h % 2019;
    h = h * 10 %2019;
  }

  h = 0;

  for(int i = 0;i < n;i++){
    h = h + b[i];
    c[i] = h % 2019;
  }

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

  for(int i = 0;i < 2019;i++){
    z = z + l[i] * (l[i] - 1) / 2;
  }

  cout << z << endl;

  return 0;

}

Measured memory_bytes: 8428
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <sstream>
#include <numeric>
#include <iomanip>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

///////////////////////////////////////////////////////////////
// namespace
///////////////////////////////////////////////////////////////
using namespace std;
// namespace mp = boost::multiprecision;

///////////////////////////////////////////////////////////////
// types
///////////////////////////////////////////////////////////////
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
// using mpi = mp::cpp_int;
// using mpf = mp::number<mp::cpp_dec_float<1024>>;

/////////////////////////////////////////////////////////////////
// https://github.com/atcoder-live/library/blob/master/mint.cpp
/////////////////////////////////////////////////////////////////
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main() {
    int A, B; std::cin >> A >> B;
    cout << A * B << endl;
    // cout << setprecision(10);
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <iomanip>
using namespace std;

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

  double ans = 0;
  for(int i = 0; i < N; i++) ans += 1/A[i];

  cout << fixed << setprecision(6) << 1/ans << endl;
  
}


Measured memory_bytes: 256
list1 = [list(map(int,input().split())) for i in range(3) ]

closs1 = 0
closs2 = 0

for i in range(2):
	if list1[i][1] - list1[i][0] == list1[i+1][1] - list1[i+1][0] and \
	list1[i][2] - list1[i][1] == list1[i+1][2] - list1[i+1][1]:
		continue
	else:
		print("No")
		exit()
print("Yes")

Measured memory_bytes: 38256
#include <stdio.h>

int function(int i, int x, int n, int a[])
{
	int judge;
	//true
	if (x == 0)
		return 1;
	//false
	if (i >= n)
		return 0;
	judge = function(i + 1, x, n, a) || function(i + 1, x - a[i], n , a);
	return judge;
}

int main(void)
{
	int i, n, m, p;
	int a[32];

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	scanf("%d", &m);
	for (i = 0; i < m; i++)
	{
		scanf("%d", &p);
		if (function(0, p, n, a))
			printf("yes\n");
		else
			printf("no\n");
	}

	return 0;
}


Measured memory_bytes: 1928
#include<stdio.h>
#include<stdlib.h>
#define NIL -1
#define N 500001

int n, A[N];

void buildMaxHeap();
void maxHeapify(int);

void init(){
  int i;
  for(i = 0; i < N; i++){
    A[i] = NIL;
  }
}

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

int right(int i){
   return 2*i+1;
}

void maxHeapify(int i){
  int l, r, largest, temp;
  l = left(i);
  r = right(i);

  if(l <= n && A[l] > A[i]) {
    largest = l;
    // printf("!%d!\n",largest);
  }  
else {
    largest = i;
    //printf("[%d]\n",largest);
  }
  if(r <= n && A[r] > A[largest]){
    largest = r;
    //printf("*%d*\n",largest);
  }

  if(largest != i){
    //printf("[%d],[%d]\n",A[i],A[largest]);
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    maxHeapify(largest);
  }

}

void buildMaxHeap(){
  int i;
  for(i = n/2; i > 0; i--){
    //printf("%d\n", i);
    maxHeapify(i);
  }
}



int main(){

  int i, p, l, r;

  scanf("%d", &n);
  init();
  
  for (i = 1; i <= n; i++){
    scanf("%d", &A[i]);
  }

  buildMaxHeap();

  for(i = 1; i <= n; i++){
    printf(" %d", A[i]);
  }

  printf("\n");

  return 0;

}

Measured memory_bytes: 2356
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[1001][4];
int main() {
    int n,m,i,j,k;
    scanf("%d%d",&n,&m);
    for (i = 0;i < n;i ++) {
        for (j = 0;j < 3;j ++)
            cin>>a[i][j];
    }
    long long ans = -1;
    for (i = 0;i < 8;i ++) {
        long long f[100010];
        for (j = 0;j < n;j ++) {
            long long sum = 0;
            for (k = 0;k < 3;k ++) {
                if(i >> k & 1)sum += a[j][k];
                else sum -= a[j][k];
            }
            f[j] = sum;
        }
        sort(f,f + n);
        long long s = 0;
        for (j = 1;j <= m;j ++)s += f[n - j];
        ans = max(s,ans);
    }
    cout<<ans;
    return 0;
}


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

A.insert(0,0)
A.append(0)

d1 = []
d2 = []
for i in range(1,N+2):
    if i != 1:
        d2.append(abs(A[i]-A[i-2]))
    d1.append(abs(A[i]-A[i-1]))
d1_total = sum(d1)

for i in range(N):
    print(d1_total-d1[i]-d1[i+1]+d2[i])

Measured memory_bytes: 17232
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>

#define MAX_LENGTH 1000
#define NIL -1
using namespace std;
//think easy make easy

int q;//num of datasets
string X;
string Y;
int map[MAX_LENGTH+1][MAX_LENGTH+1];

int findMaxLength(int x,int y){//x:Xの終端.y:Yの終端(0オリジン)
	int val;

	if(x < 0 || y < 0) return 0;

	if(map[x][y] == NIL){
		if(X.at(x) == Y.at(y)){
			val = findMaxLength(x-1,y-1) +1;
		}else{
			val = max(findMaxLength(x-1,y),findMaxLength(x,y-1));
		}
		map[x][y] = val;//メモ
		return val;
	}else return map[x][y];
}

int main(){
	
	scanf("%d",&q);

	for(int i=0;i<q;i++){
		cin >>X; cin >> Y;
		for(int i=0;i<X.size();i++){
			for(int j=0;j<Y.size();j++){
				map[i][j] = NIL;
			}
		}
	
		cout <<findMaxLength(X.size()-1,Y.size()-1) <<endl;
	}

	return 0;
}

Measured memory_bytes: 5228
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>
#include <regex>
#include <functional>
#include <algorithm>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

const int MAX_N = 200;
int gcd_table[MAX_N+1][MAX_N+1];
unsigned euclidean_gcd(unsigned a, unsigned b) {
	if (gcd_table[a][b] != 0) {
		return gcd_table[a][b];
	}
	if (a < b) return euclidean_gcd(b, a);
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	gcd_table[a][b] = b;
	return b;
}

int tri_gcd(int a, int b, int c) {
	int gcd;
	gcd = euclidean_gcd(euclidean_gcd(a, b), c);
	return gcd;
}



int main(void) {
	int n;	
	long long int sum = 0;
	cin >> n;
	REP(i , n) {
		REP(j, n) {
			REP(k, n) {
				sum += tri_gcd(i+1, j+1, k+1);
			}
		}
	}
	cout << sum << endl;
	return 0;
}



Measured memory_bytes: 3780
#include <iostream>
#include <cmath>
#include <map>
#include <utility>
#include <list>
#include <string>

using namespace std;

string sixString(int n){
    string raw_n = to_string(n);
    while(raw_n.length() < 6){
        raw_n = "0" + raw_n;
    }
    return raw_n;
}

bool comp(pair<string, int> p1, pair<string, int> p2){
    return p1.second < p2.second;
}

int main(void){
    int n, m;
    cin >> n >> m;
    map<int, list<pair<int, int>>> map;
    int p, y;
    for (int i=0; i < m; i++){
        cin >> p >> y;
        pair<int, int> pr (y, i);
        map[p].push_back(pr);
    }

    list<pair<string, int>> l;
    for (auto x : map){
        x.second.sort();
        int i = 1;
        for (list<pair<int, int>>::iterator it=x.second.begin(); it != x.second.end(); it++){
            it->first = i++;
            //cout << sixString(x.first) << sixString(it->first) << ", " << it->second << endl;
            pair<string, int> pr(sixString(x.first) + sixString(it->first), it->second);
            l.push_back(pr);
        }
    }

    l.sort(comp);
    for (int i=0; i<m; i++){
        cout << l.front().first << endl;
        l.pop_front();
    }

    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int count(int a)
{
    int cnt = 0;
    while (a % 2 == 0)
    {
        cnt++;
        a /= 2;
    }
    return cnt;
}

int main()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int ans = 0;
    rep(i, a + 1)
    {
        rep(j, b + 1)
        {
            int num = x / 50 - 10 * i - 2 * j;
            if (0 <= num && num <= c)
                ans++;
        }
    }

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


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			int in = Integer.parseInt(br.readLine());
			 System.out.println(in==25?"Christmas"
					           :in==24?"Christmas Eve"
					           :in==23?"Christmas Eve Eve"
					           :"Christmas Eve Eve Eve");
		}
	}
}

Measured memory_bytes: 25276
import java.util.Scanner;

/**
 * Pond
 */
public class Main {

    int d;
    int h;
    int[][] depth;
    int max = 0;

    public void scan() {
        Scanner sc = new Scanner(System.in);
        while (true) {
            d = sc.nextInt();
            h = sc.nextInt();
            if (d == 0 && h == 0) {
                return;
            }
            max = 0;
            depth = new int[d][h];
            for (int i = 0; i < d; i++) {
                for (int j = 0; j < h; j++) {
                    depth[i][j] = sc.nextInt();
                }
            }
            for (int i = 0; i < d; i++) {
                for (int j = 0; j < h; j++) {
                    for (int k = i; k < d; k++) {
                        for (int n = j; n < h; n++) {
                            calc(i, j, k, n);
                        }
                    }
                }
            }
            System.out.println(max);
        }
    }

    public void calc(int x0, int y0, int x1, int y1) {
        int borderMinHeight = -1;
        int innerMaxHeight = -1;
        for (int i = x0; i <= x1; i++) {
            for (int j = y0; j <= y1; j++) {
                if (i == x0 || i == x1 || j == y0 || j == y1) {
                    if (borderMinHeight == -1 || borderMinHeight > depth[i][j]) {
                        borderMinHeight = depth[i][j];
                    }
                } else {
                    if (innerMaxHeight == -1 || innerMaxHeight < depth[i][j]) {
                        innerMaxHeight = depth[i][j];
                    }
                }
            }
        }
        if (borderMinHeight <= innerMaxHeight) {
            return;
        } else {
            int sum = 0;
            for (int i = x0 + 1; i < x1; i++) {
                for (int j = y0 + 1; j < y1; j++) {
                    sum += (borderMinHeight - depth[i][j]);
                }
            }
            if (max < sum) {
                max = sum;
            }
        }
    }

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


Measured memory_bytes: 37216
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
cost = [[0]*3 for i in range(n+1)]
for i in range(n):
    cost[i+1][0] = max(cost[i][1], cost[i][2]) + a[i][0]
    cost[i+1][1] = max(cost[i][0], cost[i][2]) + a[i][1]
    cost[i+1][2] = max(cost[i][0], cost[i][1]) + a[i][2]
print(max(cost[n]))

Measured memory_bytes: 47364
#include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
     
    int main(){
        int N, T, i, j, k, ans = 0;
        scanf("%d %d", &N, &T);
     
        vector<int> t_i(N);
        for(i = 0; i < N; i++){
            scanf("%d", &t_i[i]);
        }
     
        for(i = 0, j = 0, k = 0; i < (t_i[N - 1] + T); i++, k--){
            if(t_i[j] == i){
                k = T;
                j++;
            }
            if(k > 0) ans++;
        }
     
        printf("%d", ans);
        return 0;
    }

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

vector<int>E[100];
bool used[200];
int match[200];

bool dfs(int u) {
	used[u] = true;
	for (int v : E[u]) {
		int w = match[v];
		if (w == -1 || (!used[w] && dfs(w))) {
			match[u] = v; match[v] = u;
			return true;
		}
	}
	return false;
}
int x[100], y[100], z[100], a[100], b[100];
double d[100][100];
int main() {
	int n, m;
	while (scanf("%d%d", &n, &m), n) {
		rep(i, n)scanf("%d%d%d", &x[i], &y[i], &z[i]);
		rep(i, m)scanf("%d%d", &a[i], &b[i]);
		rep(i, n)rep(j, m)d[i][j] = hypot(x[i] - a[j], y[i] - b[j]) / z[i];
		double l = 0, r = 14143;
		rep(i, 41) {
			double t = (l + r) / 2;
			rep(j, n) {
				E[j].clear();
				rep(k, m) {
					if (d[j][k] <= t)E[j].push_back(n + k);
				}
			}
			int cnt = 0;
			memset(match, -1, sizeof(match));
			rep(j, n) {
				if (match[j] == -1) {
					memset(used, 0, sizeof(used));
					cnt += dfs(j);
				}
			}
			if (cnt == m)r = t;
			else l = t;
		}
		printf("%.14lf\n", l);
	}
}

Measured memory_bytes: 3372
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

const MOD = 1000000007

func main() {
	sc := NewScanner()
	X, Y := sc.nextInt(), sc.nextInt()
	if (2*X-Y)%3 != 0 {
		fmt.Println(0)
		return
	}
	m := (2*X - Y) / 3
	if (Y-m)%2 != 0 {
		fmt.Println(0)
		return
	}
	n := (Y - m) / 2
	fmt.Println(modComb(m+n, n, MOD))
}

func modComb(big, small, mod int) int {
	if big < 0 || small < 0 || big < small {
		return 0
	}
	tmp := modFact(big, mod) * modInv(modFact(small, mod), mod) % mod
	return tmp * modInv(modFact(big-small, mod), mod) % mod
}

func modFact(a, mod int) int {
	res := 1
	for i := a; i > 0; i-- {
		res *= i
		res %= mod
	}
	return res
}

func modInv(a, mod int) int {
	b := mod
	u := 1
	v := 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= mod
	if u < 0 {
		u += mod
	}
	return u
}


Measured memory_bytes: 640
let rec power ( * ) one m = function
  | 0 -> one
  | n when n mod 2 = 0 ->
      power ( * ) one (m * m) (n / 2)
  | n ->
      m * power ( * ) one m (n - 1)

let memoize n f =
  let dp = Hashtbl.create n in
  let rec get x k =
    try k @@ Hashtbl.find dp x with
    | Not_found ->
        f get x @@ fun y ->
          Hashtbl.add dp x y; k y in get

let m = 1000000007
let ( +^ ) x y = (x + y) mod m
let ( *^ ) x y = (x * y) mod m
let inv n = power ( *^ ) 1 n (m - 2)

let () = Scanf.scanf "%d %d %d %d" @@ fun h w a b ->
  let fact = memoize (h + w) @@ fun fact n k ->
    if n <= 1 then k 1
    else fact (n - 1) @@ fun x -> k @@ n *^ x in
  let fact n = fact n @@ fun x -> x in
  let inv_fact = memoize (h + w) @@ fun inv_fact n k ->
    if n <= 1 then k 1
    else inv_fact (n - 1) @@ fun x -> k @@ inv n *^ x in
  let inv_fact n = inv_fact n @@ fun x -> x in
  Printf.printf "%d\n" @@ Array.fold_left ( +^ ) 0 @@ Array.init (h - a) @@ fun i ->
    fact(i + b - 1) *^ fact(h + w - 2 - i - b) *^ inv_fact(i) *^ inv_fact(b - 1) *^ inv_fact(h - i - 1) *^ inv_fact(w - b - 1)


Measured memory_bytes: 34176
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iterator>
#include <typeinfo>
using namespace std;


// define list


namespace  math{
    const double PI = 3.14;
    const int INF = 1000000007;
    int GCM(int a,int b); //最大公約数
    int LCM(int a,int b); //最小公倍数
    int Pemu(int n,int r); //順列
    int Comb(int n,int m); //組み合わせ
    int Digit(int N); //桁和
    
    int GCM(int a,int b){
        if(a<b){
            swap(a,b);
        }
        int r = a%b;
        while (r!=0)
        {
            a=b;
            b=r;
            r=a%b;
        }
        return b;
    }

    int LCM(int a,int b){
        return a*(b/GCM(a,b));
    }

    int Pemu(int n,int r){
        int ans = n;
        for(int i=1;i<r;i++){
            ans*=(ans-i);
        }
        return ans;
    }

    int Comb(int n,int m){
        int a=n,b=m;
        for(int i=1;i<m;i++){
            a *= (a-i);
        }
        for(int i=1;i<m;i++){
            b *= (b-i);
        }
        
        return a/b;
    }

    int Digit(int N){
        if(N<10){
            return N;
        }
        int r = 0;
        while (N>=10)
        {
            r += (N%10);
            N /= 10;
        }
        r += N;
        return r;
    }
}

namespace SubLib{
    #define int long long
    #define double long double
    #define incin(n) int (n); cin >> (n);
    #define strcin(s) string (s); cin >> (s);
    #define incin2(a,b) int a,b; cin >> a >> b; 
    #define rap(n,i) for(int (i) = 0;i<(n);(i)++)
    #define input(n,v) (v) = SubLib::Input((n),(v))
    #define all(v) (v).begin(),(v).end()
    using intv = vector<int>;
    using douv = vector<double>;
    using strv = vector<string>;
    using charv = vector<char>;
    template <class T1>
    using pvec = vector<pair<T1,T1>>;
    template <typename T> vector<T> Input(int n,vector<T> v){
        for(int i=0;i<n;i++){
            cin >> v.at(i);
        }
        return v;
    }
    void YN (bool b){
        if(b){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
}

using namespace math;
using namespace SubLib;

signed main(){
    incin(n);
    int sum = 0;
    rap(n,i){
        incin2(a,b);
        sum += (b-a+1);
    }
    cout<<sum<<endl;
    return 0;
}

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

using namespace std;

string s;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '?') {
            s[i] = 'D';
        }
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3740
#include <bits/stdc++.h> 
using namespace std;
long long   n, cnt1, cnt, ans;
int main(){
  cin >> n;
  int a[n], b[n];
  for(int i = 0;i < n; i ++){
    cin >> a[i];
    b[i] = a[i];
      if(a[i] < 0)
      cnt ++;
	  }
      if(cnt % 2 == 1){
      for(int i = 0;i < n; i ++){
        if(b[i] < 0)
        b[i] *= (-1);
		}
        sort(b, b + n);
        int cnt1 = b[0];
        for(int i = 0; i < n; i ++){
          if(b[i] == cnt1)
          continue;
          else 
          ans += b[i];
		  }
          ans -= cnt1;
          cout << ans;
		  }
          else {
            for(int i = 0; i < n;i ++){
              if(a[i] < 0){
              a[i] *= (-1);
			}
              ans += a[i];
			}
              cout << ans;
        }
}

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

int y[100001];

void merge_sort(int x[], int n)
{
	if (n == 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p] < x[q])? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, K, h[100001];
	scanf("%d %d", &N, &K);
	for (i = 0; i < N; i++) scanf("%d", &(h[i]));
	
	merge_sort(h, N);
	
	int min = h[N-1];
	for (i = 0; i <= N - K; i++) {
		if (h[i+K-1] - h[i] < min) min = h[i+K-1] - h[i];
	}
	
	printf("%d\n", min);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 896
def INT():
    return int(input())

def LI():
    return list(map(int, input().split()))

def MI():
    return map(int, input().split())

N, M = MI()
gate = [0] * (N + 2)
ans = 0

for _ in range(M):
    L, R = MI()
    gate[L] += 1
    gate[R + 1] -= 1

for i in range(1, N + 1):
    gate[i] += gate[i - 1]
    
for i in range(1, N + 1):
    if gate[i] == M:
        ans += 1
        
print(ans)

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

int main() {
  int X;
  cin >> X;
  int a,b;
  for (int i = 1; ;i++) {
    for (int j = - (i - 1); j < i; j++) {
      if(i*i*i*i*i - j*j*j*j*j == X) {
        a = i;
        b = j;
        goto OUT;
      }
    }
  }
OUT:
  cout << a << " " << b << endl;
}

Measured memory_bytes: 3608
N = int(input())
S = list(input())

forcuss = 0
j = 1
number = 1

while j != N:
    if S[forcuss] == S[j]:
        j = j + 1
        continue
    elif S[forcuss] != S[j]:
        number = number + 1
        forcuss = j
        j = forcuss + 1

print(number)

Measured memory_bytes: 4084
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
B = [0]+B
C = list(map(int,input().split()))
C = [0]+C

ans = B[A[0]]
for i in range(1,N):
    ans += B[A[i]]
    if A[i] == A[i-1]+1:
        ans += C[A[i-1]]
        
print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
#define sz(a) a.size()
#define re return 
#define MP make_pair
#define pb push_back
#define pii pair<int,int>
#define se second
#define fi first
using namespace std;
string s;
int cnt[26];
signed main(){
	ios_base::sync_with_stdio(0);
	cin>>s;
	for(int i=0;i<sz(s);i++) cnt[s[i]-'a']++;
	for(int i=0;i<26;i++){
		if(cnt[i]>1){
			cout<<"no";
			re 0;
		}
	}
	cout<<"yes";
	re 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) for(int i = 0; i < (a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
const int MOD = 1e9 + 7;

ll dp[100005][2];
vi g[100005];

void dfs(int c, int p){
	dp[c][1] = dp[c][0] = 1;
	for(int u : g[c]) if(u != p){
		dfs(u, c);
		dp[c][0] = (dp[c][0] * (dp[u][1] + dp[u][0])) % MOD;
		dp[c][1] = (dp[c][1] * dp[u][0]) % MOD;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1, 0);
	cout << (dp[1][1] + dp[1][0]) % MOD << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

int main(){
    ll n,x,k,max=0,ma=0;
    cin>>n;
    rep(i,n){
        cin>>x;
        if(max<x){
            ma=max;
            max=x;
            k=i;
        }else if(ma<x){
            ma=x;
        }
    }
    rep(i,n){
        if(i==k) cout<<ma<<endl;
        else cout<<max<<endl;
    }
}

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

using namespace std;

int main(){
    double a, b, c, d, e, f;
    double p, q;
    while(cin >> a >> b >> c >> d >> e >> f){
        cin >> p >> q;
        vector<int> x(3), y(3);
        x[0] = a; x[1] = c; x[2] = e;
        y[0] = b; y[1] = d; y[2] = f;
        int ret = 0;
        bool is = false;
        for(int i=0; i < x.size(); i++){
            double X1 = x[i%3], X2 = x[(i+1)%3], X3 = x[(i+2)%3];
            double Y1 = y[i%3], Y2 = y[(i+1)%3], Y3 = y[(i+2)%3];
            int ans = 0;
            if ((X2-X1)*(q-Y1)-(Y2-Y1)*(p-X1)>0.0) ans++;
            if ((X3-X2)*(q-Y2)-(Y3-Y2)*(p-X2)>0.0) ans++;
            if ((X1-X3)*(q-Y3)-(Y1-Y3)*(p-X3)>0.0) ans++;
            if(ans%3==0) is = true;
        }
        cout << (is?"YES":"NO") << endl;
    }
}

Measured memory_bytes: 1216
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);


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

    void run() {

        int k = sc.nextInt();
        int s = sc.nextInt();

        long res = 0;

        for (int x=0; x<=k; x++) {
            for (int y=0; y<=k; y++) {
                int z = s - (x + y);
                if (0 <= z && z <= k) res++;
            }
        }

        System.out.println(res);

    }


}


Measured memory_bytes: 22996
class Dice:
    def __init__(self, x):
        self.top = x[0]
        self.front = x[1]
        self.right = x[2]
        self.left = x[3]
        self.back = x[4]
        self.bottom = x[5]

    def N(self):
        self.top, self.front, self.bottom, self.back = self.front, self.bottom, self.back, self.top

    def E(self):
        self.top, self.right, self.bottom, self.left = self.left, self.top, self.right, self.bottom

    def S(self):
        self.top, self.front, self.bottom, self.back = self.back, self.top, self.front, self.bottom

    def W(self):
        self.top, self.right, self.bottom, self.left = self.right, self.bottom, self.left, self.top

*x,=map(int,input().split())
dice=Dice(x)
A=input()
for a in A:
    if a=='N':
        dice.N()
    if a=='E':
        dice.E()
    if a=='S':
        dice.S()
    if a=='W':
        dice.W()
print(dice.top)



Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mkp make_pair
#define rep(i,s,f) for(i=s;i<f;i++)
#define db cout<<'h'<<'i'<<endl 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define PI 3.14159265
#define mod 1000000007
#define mod2 998244353
#define space 100005
#define lg 18
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;

    cin>>n>>t;

    vector<pii> ans;
    ans.pb({1,2});

    int sum=0;
    if((n-1)*(n-2)/2 <t)
    {
        cout<<-1;
        return 0;
    }
    rep(i,3,n+1)
    {
        if(i-2 <=t)
        {
            t-=i-2;
            ans.pb({1,i});
        }
        else
        {
            ans.pb({1,i});
            t-=i-2;
            j=2;
            while(t<0)
            {
                ans.pb({j,i});
                t++;j++;
            }
        }
    }
    cout<<ans.size()<<'\n';
    for(auto z:ans)
    {
        cout<<z.F<<" "<<z.S<<'\n';
    }

    return 0;
}



Measured memory_bytes: 384
# coding: utf-8
# Your code here!
from collections import deque

K=int(input())
d = deque()

for i in range(1,10):
    d.append(i)

for i in range(1,K):
    s = d.popleft()
    v = s%10
    if v>0:
        d.append(10*s+v-1)
    d.append(10*s+v)
    if v<9:
        d.append(10*s+v+1)
print(d.popleft())    


Measured memory_bytes: 18868
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <stdio.h>
#include <string>
#include <ctype.h>
#include <iomanip>
#include <limits>

#define rep(i, n) for(int i = 0; i < (n); i++)
using ll = long long;
constexpr ll INF = 1000000000;

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; }

using namespace std;

int main() {
	int n, a, b, c, d; cin >> n >> a >> b >> c >> d;
	string s; cin >> s;

	s = "#" + s + "#";

	if (c < d) {
		for (int i = a; i + 1 <= c; i++) {
			if (s[i] == '#' && s[i + 1] == '#') {
				cout << "No" << endl;
				return 0;
			}
		}
		for (int i = b; i + 1 <= d; i++) {
			if (s[i] == '#' && s[i + 1] == '#') {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	else {
		bool okay = false;
		for (int i = b; i <= d; i++) {
			if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') {
				okay = true;
			}
		}
		if (!okay) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}


Measured memory_bytes: 772
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int ans = 0;
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] x = new int[m];
    if(n >= m) {
      System.out.println(0);
      System.exit(0);
    }
    for(int i=0; i<m; i++) {
      x[i] = sc.nextInt();
    }
    Arrays.sort(x);
    int[] span = new int[m-1];
    for(int i=0; i<m-1; i++) {
      span[i] = x[i+1] - x[i];
    }
    Arrays.sort(span);
    for(int i=0; i<m-n; i++) {
      ans += span[i];
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 49468
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=3500;i++)
		for(int j=1;j<=3500;j++){
			ll x=(ll)n*i*j;
			ll y=(ll)i*j*4-(ll)n*j-(ll)n*i;
			if(y<=0) continue;
			if(x%y==0){
				printf("%d %d %lld",i,j,x/y);
				return 0;
			}
		}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int N = 1e5+5;
int n,a,b,c,ans;
void solve(int &num,int add)
{
	ans+=min(num,n)*add;
	int mi=min(num,n);
	num-=mi;
	n-=mi;
}
int main()
{
	cin>>a>>b>>c>>n;
	solve(a,1);
	solve(b,0);
	solve(c,-1);
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);

int main() {
    cin>>S;
    ll ans = 0;
    for(char c : S) (ans += c - '0')%=9;
    cout<<(ans == 0 ? "Yes" : "No")<<endl;
}


Measured memory_bytes: 3748
//Author:xht37
#include <bits/stdc++.h>

#define ui unsigned int
#define ll long long
#define ul unsigned ll
#define ld long double

#define pi pair <int, int>
#define fi first
#define se second
#define mp make_pair

#define ls (p << 1)
#define rs (ls | 1)
#define md ((t[p].l + t[p].r) >> 1)

#define vi vector <int>
#define pb push_back
#define pq priority_queue

#define dbg(x) cerr << #x" = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)

#define fl(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

using namespace std;

namespace io {
	const int SI = 1 << 21 | 1;
	char IB[SI], *IS, *IT, OB[SI], *OS = OB, *OT = OS + SI - 1, c, ch[100];
	int f, t;
	#define gc() (IS == IT ? (IT = (IS = IB) + fread(IB, 1, SI, stdin), IS == IT ? EOF : *IS++) : *IS++)
	inline void flush() {
		fwrite(OB, 1, OS - OB, stdout), OS = OB;
	}
	inline void pc(char x) {
		*OS++ = x;
		if (OS == OT) flush();
	}

	template <class I>
	inline void rd(I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + (c & 15), c = gc());
		x *= f;
	}
	template <class I>
	inline void rd(I &x, I &y) {
		rd(x), rd(y);
	}
	template <class I>
	inline void rd(I &x, I &y, I &z) {
		rd(x), rd(y), rd(z);
	}
	template <class I>
	inline void rda(I *a, int n) {
		for (int i = 1; i <= n; i++) rd(a[i]);
	}
	inline void rdc(char &c) {
		for (c = gc(); c < 33 || c > 126; c = gc());
	}
	inline void rds(char *s, int &n) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (n = 0; c >= 33 && c <= 126; s[++n] = c, c = gc());
		s[n+1] = '\0';
	}
	inline void rds(string &s) {
		for (c = gc(); c < 33 || c > 126; c = gc());
		for (s.clear(); c >= 33 && c <= 126; s.pb(c), c = gc());
	}

	template <class I>
	inline void print(I x, char k = '\n') {
		if (!x) pc('0');
		if (x < 0) pc('-'), x = -x;
		while (x) ch[++t] = x % 10 + '0', x /= 10;
		while (t) pc(ch[t--]);
		pc(k);
	}
	template <class I>
	inline void print(I x, I y) {
		print(x, ' '), print(y);
	}
	template <class I>
	inline void print(I x, I y, I z) {
		print(x, ' '), print(y, ' '), print(z);
	}
	template <class I>
	inline void printa(I *a, int n) {
		for (int i = 1; i <= n; i++) print(a[i], " \n"[i==n]);
	}
	inline void printc(char c) {
		pc(c);
	}
	inline void prints(char *s, int n) {
		for (int i = 1; i <= n; i++) pc(s[i]);
		pc('\n');
	}
	inline void prints(string s) {
		int n = s.length();
		while (t < n) pc(s[t++]);
		pc('\n'), t = 0;
	}
	struct Flush {
		~Flush() {
			flush();
		}
	} flusher;
}
using io::rd;
using io::rda;
using io::rdc;
using io::rds;
using io::print;
using io::printa;
using io::printc;
using io::prints;

const int N = 107;
int n, x, a[N], s;

int main() {
	rd(n, x), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; s += a[i++])
		if (s + a[i] > x) return print(i - 1), 0;
	print(n - (s != x));
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, d[100008];
string str;

int main(){
	cin >> n;
	for(ll i = 0; i < n; i++){
		cin >> d[i];
	}
	sort(d, d+n);
	if(d[n/2-1] != d[n/2]){
		cout << d[n/2]-d[n/2-1] << endl;
	}
	else{
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

#define INF 100000000;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
int main(){
    int A,B,cnt = 1,ans = 0;
    cin >> A >> B;
    while(cnt < B){
        cnt--;
        cnt += A;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# _*_ coding:utf-8 _*_
#  Atcoder_Beginners_Contest113-B
#  https://beta.atcoder.jp/contests/abc113/tasks/abc113_b

def bestpalace(n,t,a,placeList) :
	repeatRange = range(0,n)
	bestTemp = 1000
	bestTempPlace = -1
	for i in repeatRange:
		aveTemp = abs(a-(t-placeList[i]*0.006))
		if aveTemp < bestTemp:
			bestTemp = aveTemp
			bestTempPlace = i

	return bestTempPlace


if __name__ == '__main__':
	line1 = input()
	line2 = input()
	line3 = input()
	n = int(line1)
	t,a = map(int,line2.split())
	placeList = list(map(int,line3.split()))
	ans=bestpalace(n,t,a,placeList)+1
	print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define eps 1e-9
using namespace std;

struct obs {
  double x, y, z, r;
  long long l;
};
struct obj {
  double sx, sy, sz, dx, dy, dz;
};
long long n, q;
vector<obs> lst;

long long solve(obj now);
bool ch(obs nows, obj nowj);
double mypow(double x);
double nrm(double x, double y, double z);

int main() {
  cin >> n >> q;
  lst.resize(n);
  for(int i = 0; i < n; ++i)
    cin >> lst[i].x >> lst[i].y >> lst[i].z >> lst[i].r >>
        lst[i].l;
  for(int i = 0; i < q; ++i) {
    obj now;
    cin >> now.sx >> now.sy >> now.sz >> now.dx >> now.dy >>
        now.dz;
    cout << solve(now) << endl;
  }
  return 0;
}

long long solve(obj now) {
  long long ans = 0;
  for(int i = 0; i < n; ++i)
    if(ch(lst[i], now)) ans += lst[i].l;
  return ans;
}

bool ch(obs nows, obj nowj) {
  double disa, disb, disc;
  disa = mypow(nowj.dx - nowj.sx) +
         mypow(nowj.dy - nowj.sy) +
         mypow(nowj.dz - nowj.sz);
  disb = mypow(nowj.dx - nows.x) + mypow(nowj.dy - nows.y) +
         mypow(nowj.dz - nows.z);
  disc = mypow(nowj.sx - nows.x) + mypow(nowj.sy - nows.y) +
         mypow(nowj.sz - nows.z);
  if(disc + disa - disb < 0 || disa + disb - disc < 0) {
    return nows.r - min(sqrtl(disb), sqrtl(disc)) >= -eps;
  }
  double chilx, chily, chilz, dmom, dchil;
  dmom = nrm(nowj.dx - nowj.sx, nowj.dy - nowj.sy,
             nowj.dz - nowj.sz);
  chilx = (nows.y - nowj.sy) * (nowj.dz - nowj.sz) -
          (nows.z - nowj.sz) * (nowj.dy - nowj.sy);
  chily = (nows.z - nowj.sz) * (nowj.dx - nowj.sx) -
          (nows.x - nowj.sx) * (nowj.dz - nowj.sz);
  chilz = (nows.x - nowj.sx) * (nowj.dy - nowj.sy) -
          (nows.y - nowj.sy) * (nowj.dx - nowj.sx);
  dchil = nrm(chilx, chily, chilz);
  return nows.r - dchil / dmom >= -eps;
}

double mypow(double x) { return x * x; }

double nrm(double x, double y, double z) {
  return sqrtl(mypow(x) + mypow(y) + mypow(z));
}


Measured memory_bytes: 3208
N,M = map(int,input().split())
INF = float('inf')
d = [[INF for i in range(N)] for j in range(N)]
es = []
for i in range(M):
    a,b,c = map(int,input().split())
    a,b = a-1,b-1
    d[a][b] = d[b][a] = c
    es.append((a,b,c))

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

ans = 0
for a,b,c in es:
    if c != d[a][b]:
        ans += 1
print(ans)


Measured memory_bytes: 3444
import numpy as np
first = [int(item) for item in input().split()]
second = [int(item) for item in input().split()]
third = [int(item) for item in input().split()]

grid = np.array([first, second, third])
# print(grid)

N = int(input())

num_list = [int(input()) for _ in range(N)]
# print(num_list)

flg_list = [0,0,0]

is_bingo = False

for i in range(3):
    flg_list = [0,0,0]
    for j in range(3):
        if grid[i,j] in num_list:
            flg_list[j] = 1

    if flg_list == [1,1,1]:
        is_bingo = True

for i in range(3):
    flg_list = [0,0,0]
    for j in range(3):
        if grid[j,i] in num_list:
            flg_list[j] = 1

    if flg_list == [1,1,1]:
        is_bingo = True


flg_list = [0,0,0]
for i in range(3):
    if grid[i,i] in num_list:
        flg_list[i] = 1

    if flg_list == [1,1,1]:
        is_bingo = True

flg_list = [0,0,0]
for i in range(3):

    if grid[2-i,i] in num_list:
        flg_list[i] = 1

    if flg_list == [1,1,1]:
        is_bingo = True

if is_bingo:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 18400
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a,a+n);
    int sum = 0;
    int key = 0;
    int count = 0;
    for(int i = 0; i < n; i++){
        if(key != a[i]){
            if(key > count){
                sum += count;
            }else{
                sum += count - key;
            }
            key = a[i];
            count = 1;
        }else{
            count++;
        }
        if(i == n-1){
            if(key > count){
                sum += count;
            }else{
                sum += count - key;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <complex>

using namespace std;

#define mod 1000000007

class UnionFind
{
    vector<int> root;
    vector<vector<int> > child;
    vector<long long int> dist;
    public:
    UnionFind(int n)
    {
    	child = vector<vector<int> >(n);
        for(int i=0;i<n;i++)
        {
            root.push_back(i);
            child[i].push_back(i);
            dist.push_back(0);
        }
    }

    int getroot(int n)
    {
        if(root[n]==n) return n;
        return root[n]=getroot(root[n]);
    }

    void set(int x,int y, long long int w)
    {
        int rx = getroot(x);
        int ry = getroot(y);
        if(rx == ry) return;
        if(child[rx].size() < child[ry].size()){
        	swap(x, y);
        	swap(rx, ry);
        	w = -w;
        }
        root[ry] = rx;
        int disty = dist[y];
        while(!child[ry].empty()){
        	int now = child[ry].back();
        	dist[now] = dist[now] - disty + dist[x] + w;
        	child[rx].push_back(now);
        	child[ry].pop_back();
        }
        // cout << "connect " << ry << " to " << rx << endl;
        // cout << "child of " << rx << " : " << endl;
        // for(int i = 0; i < child[rx].size(); i++){
        // 	cout << child[rx][i] << " (dist : " << dist[child[rx][i]] << " ) " << endl;
        // }
    }

    long long int getdist(int x)
    {
    	return dist[x];
    }
};

int main()
{
	while(1){
		int n, m;
		cin >> n >> m;
		if(n == 0) break;
		UnionFind uf(n);
		for(int i = 0; i < m; i++){
			char c;
			cin >> c;
			if(c == '!'){
				int a, b, w;
				cin >> a >> b >> w;
				a--;
				b--;
				uf.set(a, b, w);
			} else {
				int a, b;
				cin >> a >> b;
				a--;
				b--;
				if(uf.getroot(a) != uf.getroot(b)) cout << "UNKNOWN" << endl;
				else cout << uf.getdist(b) - uf.getdist(a) << endl;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 10228