akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16000000")
using namespace std;

typedef pair <int, int> ii;

const int Maxn = 5000005;

char s[Maxn];
int slen;
char t[Maxn];
int tlen;
char r[2 * Maxn];
int rlen;
int Z[2 * Maxn];
int dp[Maxn];

int Get(int ind)
{
    if (dp[ind] != 0) return dp[ind];
    if (Z[tlen + 1 + ind] >= tlen) {
        int nind = (ind + tlen) % slen;
        dp[ind] = -1;
        int got = Get(nind);
        if (got == -1) return -1;
        dp[ind] = got + 1;
        return dp[ind];
    } else return 0;
}

int main()
{
    scanf("%s", s); slen = strlen(s);
    scanf("%s", t); tlen = strlen(t);
    do {
        for (int i = 0; i < slen; i++)
            s[slen + i] = s[i];
        slen *= 2;
    } while (slen < 2 * tlen);
    slen /= 2;
    for (int i = 0; i < tlen; i++)
        r[rlen++] = t[i];
    r[rlen++] = '#';
    for (int i = 0; i < 2 * slen; i++)
        r[rlen++] = s[i];
    int lef = -1, rig = -1;
    for (int i = 1; i < rlen; i++) {
        if (i <= rig) Z[i] = min(rig - i, Z[i - lef]);
        while (i + Z[i] < rlen && r[Z[i]] == r[i + Z[i]])
            Z[i]++;
        if (i + Z[i] - 1 > rig) {
            rig = i + Z[i] - 1;
            lef = i;
        }
    }
    int res = 0;
    for (int i = 0; i < slen; i++) if (dp[i] == 0) {
        int g = Get(i);
        if (g == -1) { printf("-1\n"); return 0; }
        res = max(res, g);
    }
    printf("%d\n", res);
    return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll A, B, C; cin >> A >> B >> C;
    cout << min(C, B / A) << endl;
}


int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3644
import sys
from collections import *
from heapq import *
from fractions import gcd
import itertools
import math

sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

S = InS()

if(len(S) % 2 == 0):
    S1 = S[0:int(len(S) / 2)]
    S2 = S[int(len(S) / 2)::]
else:
    S1 = S[0:int(len(S) / 2)]
    S2 = S[int(len(S) / 2) + 1::]
res = 0
for i in range(int(len(S) / 2)):
    if(S1[i] != S2[-(i+1)]):
        res += 1


print(res)


Measured memory_bytes: 5580
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define mod 1000000007
#define vll vector<ll>

ll ti[5][100001];

ll fmax(ll x,ll y,ll z)
{
    vll v;
    v.pb(x);v.pb(y);v.pb(z);
    sort(v.rbegin(),v.rend());
    return v[0];
}

ll n,a[100001],b[100001],c[100001];

ll func(ll pre,ll len)
{
    if(len==0) return 0;

    if(ti[pre][len]!=-1) return ti[pre][len];

  if(pre==0)
   return ti[pre][len]=fmax(a[len-1]+func(1,len-1),b[len-1]+func(2,len-1),c[len-1]+func(3,len-1));
  else if(pre==1)
    return ti[pre][len]=max(b[len-1]+func(2,len-1),c[len-1]+func(3,len-1));
  else if(pre==2)
    return ti[pre][len]=max(a[len-1]+func(1,len-1),c[len-1]+func(3,len-1));
  else
    return ti[pre][len]=max(a[len-1]+func(1,len-1),b[len-1]+func(2,len-1));

}


int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    memset(ti,-1,sizeof ti);
	//ll n;
	cin>>n;

	for(ll i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];

      cout<<func(0,n)<<endl;;

	return 0;
}



Measured memory_bytes: 11136
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

int main(void) {
	string s;
	int k;
	cin >> k >> s;
	rep(i, 0, min((int)s.size(), k)) {
		printf("%c", s[i]);
	}
	if (k < s.size())printf("...");
	puts("");
	return 0;
}


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

int main()
{
  string str;
  cin >> str;
  int ans = 0;
  for(int i = 0, end = str.size(), j = str.size() - 1; i < end / 2, j >= end / 2; i++, j--) 
  {
    if(str[i] != str[j]) 
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long int;

int main(){
    int n;
    cin >> n;
    vector<ll> A(n+1);
    for(int i = 0; i < n; i++)cin >> A[i];
    A[n] = 0LL;
    ll money = 1000;
    ll stack = 0LL;
    for(int i = 0; i < n; i++){
        if (A[i] < A[i+1]){
            ll nstack = money / A[i];
            stack += nstack;
            money -= nstack * A[i];
        }
        if (A[i] > A[i+1]){
            money += stack * A[i];
            stack = 0;
        }
    }
    cout << money << endl;
    return 0;
}

Measured memory_bytes: 3192
//2017-10-8
//miaomiao
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define LL long long
#define pb push_back
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)

#define N (100000+5)

vector<int> G[N];
int col[N], xtot, ytot;
bool flag, vis[N];

void Dfs(int now, int nc){
	if(flag) return;
	if(col[now] && col[now] != nc){
		flag = true; return;
	}
	if(vis[now]) return;

	vis[now] = true; col[now] = nc;
	For(i, 0, G[now].size()-1) Dfs(G[now][i], 3-nc);
}

int main(){
	int n, m, u, v;

	scanf("%d%d", &n, &m);
	For(i, 1, m){
		scanf("%d%d", &u, &v);
		G[u].pb(v); G[v].pb(u);
	}

	Dfs(1, 1);
	if(flag){
		printf("%lld\n", 1ll*n*(n-1)/2 - m);
		return 0;
	}
	
	For(i, 1, n){
		if(col[i] == 1) ++xtot;
		else ++ytot;
	}

	printf("%lld\n", 1ll*xtot*ytot - m);

	return 0;
}

Measured memory_bytes: 6656
n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
	s = list(map(int, input().split()))
	b = s.pop(0)
	c.append(b)
	a.append(s)

ans = 10**9
for i in range(2**n):
	cnt = 0
	b = [0 for i in range(m)]
	for j in range(n):
		if (i >> j) & 1:
			cnt += c[j]
			for k in range(m):
				b[k] += a[j][k]
	mn = min(b)
	if mn >= x:
		ans = min(ans,cnt)
if ans == 10**9:
	print (-1)
else:
	print (ans)



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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORE(i, a, b) for (int i = (a); i <= (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(v) (v).begin(), (v).end()
#define sp cout << fixed << setprecision(10)
typedef pair<int, int> P;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

    int r;
    cin >> r;

    cout << 3 * r * r << endl;

    return 0;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
# define rep(i, n) for(ll i = 0; i < (n); ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((int)(n)); i>0; --i)
# define ll long long
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define optimize_cin() cin.tie(0); ios::sync_with_stdio(false)
# define P pair<int, int>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll lmax(ll a, ll b){if(a>= b) return a;return b;}
ll lmin(ll a, ll b){if(a>= b) return b;return a;}

int main() {
  int n; cin >> n;
  vector<P> v(n);
  rep(i, n){
    int a; cin >> a;
    v[i] = make_pair(a, i+1);
  }

  sort(ALL(v));
  rep(i, n){
    cout << v[i].second << endl;
  }
}


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

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

  vector<vector<long long>> dp(S.size() + 1, vector<long long>(13));
  dp[0][0] = 1;
  int S_size = S.size();
  for (int i = 0; i < S_size; ++i) {
    int a;
    if (S[i] == '?')
      a = -1;
    else
      a = S[i] - '0';

    for (int j = 0; j < 10; ++j) {
      if (a != -1 && a != j)
        continue;
      for (int k = 0; k < 13; ++k)
        dp[i + 1][(k * 10 + j) % 13] += dp[i][k];
    }

    for (int j = 0; j < 13; ++j)
      dp[i + 1][j] %= 1000000007;
  }

  cout << dp[S_size][5] << endl;
}

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

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

    int64_t sum = 0;
    for(int tmp=0;tmp < (1<<N.size()-1);tmp++) {
        bitset<10> s(tmp);
        // cout << s << endl;

        vector<int64_t> select;
        string n = {N[0]}; //N[0]はcharなのでstringに変換
        select.push_back(stoi(n));
        int start_index = 1;
        for(int i=0;i<N.size()-1;i++) {

            //s=1のとき（分離）
            if(s.test(i)) {
                n = {N[start_index]};
                select.push_back(stoi(n));
                start_index++;
            }
            //s=0のとき（結合）
            else {
                //selectの末尾の要素に数字を結合
                n = {N[start_index]};
                select[select.size()-1] *= 10;
                select[select.size()-1] += stoi(n);
                start_index++;
            }
        }

        // for(int i=0;i<select.size();i++) {
        //     cout << select[i] << " ";
        // }
        // cout << endl;

        // 配列selectの要素の総和を求める（答え）
        for(int i=0;i<select.size();i++) {
            sum += select[i];
        }

    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(input())

# def LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

a = S_LIST()
b = S_LIST()
# a = input()
# b = input()
a.reverse()
if a == b:
    print("YES")
else:
    print("NO")


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

ll N;
int main () {
  cin >> N;

  cout << N*(N-1)/2 << endl;

  return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<string> blue(n);
  for (int i = 0; i < n; i++) cin >> blue[i];
  int m;
  cin >> m;
  vector<string> red(m);
  for (int i = 0; i < m; i++) cin >> red[i];
  
  map<string,int> mp;
  for (int i = 0; i < n; i++) mp[blue[i]]++;
  for (int i = 0; i < m; i++) mp[red[i]]--;

  int ans = 0;
  for(int i = 0; i < n; i++){
    ans = max(ans,mp[blue[i]]);
  }
  cout << ans << endl;

}

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

int main() {
  int a, b, c;
  cin >> a >> b;
  c = a * b;
  if (c % 2 == 0) {
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}
       

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


int main(){
    int n;
    cin >> n; //n : length
    vector<vector<int>> gd(n, vector<int>(n,0));
    ll sum =0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            gd[i][j] =__gcd(i+1,j+1);
        }
    }

    rep(i,n){
        rep(j,n){
            for(int k=1;k<=n;k++){
                sum += __gcd(k,gd[i][j]);
            }
        }
    }
    cout << sum << endl;
return 0;
}

Measured memory_bytes: 3764
// ref. https://img.atcoder.jp/arc085/editorial.pdf

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n, z, w;
  cin >> n >> z >> w;
  vector<ll> a(n);
  rep(i, n) {
    cin >> a[i];
  }
  if (n == 1) {
    cout << abs(w-a[n-1]) << endl;
    return 0;
  }
  // Here, n > 1
  ll ans = max(abs(w-a[n-1]), abs(a[n-1]-a[n-2]));
  cout << ans << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun May 31 10:46:22 2020

@author: NEC-PCuser
"""

N, M = map(int, input().split())
s = []
switch = [0] * N

for i in range(0, M):
    ks = list(map(int, input().split()))
    s.append(ks[1:])

p = list(map(int, input().split()))

count = 0;
for i in range(0, 2**N):
    switch = [0] * N
    for j in range(0, N):
        if ((i >> j) & 1):
            switch[j] = 1
    k = 0
    for p_split in p:
        t = 0
        for s_split in s[k]: 
            if (switch[s_split - 1]):
                t += 1
        if (t % 2 != p_split):
            break
        else:
            k += 1
    else:
        count += 1

print(count)
        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n;
    cin >> n;

    vector<int64_t> a(n);
    for (auto&& aa : a) {
        cin >> aa;
    }

    vector<int64_t> b(n, -1);
    for (auto i : irange(n - 1, -1L, -1L)) {
        int64_t s = 0;
        for (int64_t j = 2; (i + 1) * j <= n; ++j) {
            s += b[(i + 1) * j - 1];
        }

        b[i] = (s - a[i] + 2) % 2;
    }

    auto m = count_if(b.begin(), b.end(), [](int64_t bb) { return bb; });
    cout << m << endl;
    const auto* delim = "";
    for (auto i : irange(0L, n)) {
        if (b[i]) {
            cout << delim << i + 1;
            delim = " ";
        }
    }
    cout << "\n";
}

Measured memory_bytes: 3968
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}

#define MAX 110000


int main() {
	int n;
	cin>>n;
	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}
	stack<int> ans;
	while (n) {
		if (n % (-2) == 0) {
			ans.push(0);
			n /= -2;
		}
		else if (n % (-2) == 1) {
			ans.push(1);
			n /= -2;
		}
		else {
			ans.push(1);
			n /= -2;
			n++;
		}
	}
	while (!ans.empty()) {
		cout << ans.top();
		ans.pop();
	}
	cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
const int N=1e5+5;
using namespace std;
long long  a[N];
void Solve(){
	int cnt=0; long long  i=1;
	while(cnt<N){
		stringstream ss; string s;
		ss<<i;
		ss>>s;
		int fac=1; 
		for(int j=0;j<s.size()-1;j++){
			if(s[j]<s[j+1]-1||s[j]>s[j+1]+1){   i=i+pow(10,s.size()-j-2);   fac=0; break;	}
		}
		if(fac){
		//	cout<<i++<<endl;
			a[cnt++]=i++;
	//		cout<<cnt<<endl;
		}
	}
}
int main(){
	Solve();
	//for(int i=0;i<N;i++)
	//	cout<<a[i]<<endl;
	int n; cin>>n;
	cout<<a[n-1]<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j) for(int i=0;i<j;i++)
 
 
int main() {
  int A,B;
  cin >> A >> B;
  int count = 0;
  int accum = 1;
  while (B>accum) {
  accum+=A-1;
  count++;
  }
  
  cout << count <<endl;
 
}

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

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

int N, M;
ll P[1111];
ll PP[11111111];
int p;

int main(int argc, char *argv[])
{
  while(cin >> N >> M, N){
    int NN = N * N;
    rep(i, N) cin >> P[i];
    rep(i, N) rep(j, N) PP[i + j * N] = P[i] + P[j];
    sort(P,  P  + N );
    sort(PP, PP + NN);
    ll res = 0;
    res = max(res,  P[upper_bound(P,  P  + N,  M) -  P - 1]);
    res = max(res, PP[upper_bound(PP, PP + NN, M) - PP - 1]);    
    rep(i, N) res = max(res, PP[upper_bound(PP, PP + NN, M -  P[i]) - PP - 1] +  P[i]);
    rep(i, NN) if((p = upper_bound(PP, PP + NN, M - PP[i]) - PP - 1) >= 0) res = max(res, PP[p] + PP[i]);
    rep(i, NN) if((p = upper_bound(PP, PP + NN, M - PP[i]) - PP - 1) >= 0) res = max(res, PP[p] + PP[i]);
    cout << res << endl;
  }
  
  
  return 0;
}

Measured memory_bytes: 9372
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n, m = sc.nextInt()

  val mod = 1000000007

  def plus(a: Long, b: Long): Long = (a + b) % mod
  def minus(a: Long, b: Long): Long = (a - b + mod) % mod
  def times(a: Long, b: Long): Long = (a * b) % mod

  def pow(a: Long, n: Int, res: Long = 1): Long = {
    if (n == 0) {
      res
    } else if ((n&1) == 0) {
      pow(times(a,a), n >> 1, res)
    } else {
      pow(times(a,a), n >> 1, times(res,a))
    }
  }

  def inv(a: Long): Long = pow(a, mod-2)

  def initFactTable(n: Int): Array[Long] = {
    (1 to n).scanLeft(1L)(times(_,_)).toArray
  }

  val fact = initFactTable(m)

  def initInvFactTable(n: Int): Array[Long] = {
    (1 to n).scanRight(inv(fact(n)))(times(_,_)).toArray
  }

  val invFact = initInvFactTable(m)

  def perm(n: Int, k: Int): Long = {
    times(fact(n), invFact(n-k))
  }

  def comb(n: Int, k: Int): Long = {
    times(times(fact(n), invFact(k)), invFact(n-k))
  }

  val a = perm(m, n)
  val b = (0 to n).map(i => times(perm(m-i, n-i), comb(n, i))).reduceRight(minus)
  println(times(a, b))
}


Measured memory_bytes: 120216
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const double PI  =3.141592653589793238463;
long long mod = 1000000007;
int stringToInteger(string x){
    int gg=0;
    stringstream geek(x);
    geek >> gg;
    return gg;
}

ll powmod(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0){ if(b%2)
        {ans*=a; ans%=m;}
         b/=2; a=a*a; a=a%m;
        }
        return ans%m;
}
ll gcd(ll a,ll b)
{

    return __gcd(a,b);
}
ll mulmod(ll a,ll b,ll m)
{  ll ans=0;
    a %=m;
    while (b>0)
    {       if(b&1) ans = (ans + a) % m;
        a = (a * 2)%m;
        b /= 2;
    }
    return ans % m;
}
bool prime[100005];
void seive()
{  memset(prime,true,sizeof(prime));
    for(int i=2;i*i<=100005;i++)
    {
         if(prime[i]==true) {
        for(int j=2*i;j<=(100005);j+=i)
           { prime[j]=false;}
           }

    }
}








ll f[5000001];

ll pow(ll a, ll b, ll MOD)
{
 ll x=1,y=a;
 while(b > 0)
 	{
 		if(b%2 == 1)
 	{
 		x=(x*y);
 		if(x>MOD) x%=MOD;
 	}
 	y = (y*y);
 	if(y>MOD) y%=MOD;
 	b /= 2;
 	}
 return x;
}

/* Modular Multiplicative Inverse
 Using Euler's Theorem
 a^(phi(m)) = 1 (mod m)
 a^(-1) = a^(m-2) (mod m) */
ll InverseEuler(ll n, ll MOD)
{
 return pow(n,MOD-2,MOD);
}

ll C(ll n, ll r, ll MOD)
{

 return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}
int main()
{
    int n; cin>>n;double ans=0; vector<double>v;
    for(int i=0;i<n;i++) {
    double s; cin>>s;
    v.push_back(s);
    }
    while(v.size()>1)
    {
        sort(v.rbegin(),v.rend()); vector<double>vv;
        for(int i=0;i<v.size()-2;i++) vv.push_back(v[i]);
        vv.push_back((v[v.size()-1]+v[v.size()-2])/2.0);
        v=vv;
    }
    cout<<v[0]<<endl;
}









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

using namespace std;
using ll = long long;

int main(){
    int n; cin >> n;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    int sum = 0;
    rep(i, n){
        for (int j = i + 1; j < n; j++)
        {
            sum += d[i]*d[j];
        }
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_A
# 典型的なナップサック問題。動的計画法を使いたくなるが制約条件がゆるいので全探索でも十分間に合う。
# bit全探索を実装したくなるがここでは練習のために再帰関数で解く。

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

# i番目を以降の要素でmを作れるかどうかの関数solve(i,m)を再帰的に実装
# 例えば1 5 7 10 21が与えられたときsolve(4,21),solve(4,0)はTrue,solve(4,3)はFalseとすぐわかる
# ではsolve(3, x)はどうだろう。solve(3,31)はsolve(4,31)(つまり3番目の要素を選択しない)がTrueならTrueとなる。
# もしくはsolve(4,21)がTrueならsolve(3,31)もTrue (3番目の要素を選択したら実行可能).
# ここでは更に何も取らない選択も用意しておくと便利だろう。つまりsolve(5,0)ならばTrue
# つまり一般化すると、solve(i,m)はsolve(i+1,m)かsolve(i+1,m-A[i])がTrueならTrueでそれ以外はFalse
# またsolve(hoge,0)は必ず実行可能（再帰の終了条件）
# 以上を用いてDPテーブルを作成できちゃうが今回はあえて再帰的に実装する


from functools import lru_cache

# pythonだとTLEしてしまうためメモ化します


@lru_cache(maxsize=2**12)
def solve(i, m):
    # 終了条件 #dpテーブルの初期条件に相当
    if m == 0:
        return True
        # 数字をAでやりくりした結果切りよく0になるということは、その数字を実現可能だということ
        # 最大でi=len(A)、このときmは必ず0となるので無限ループは回避できる
    if i == n:
        # i==len(A)のときに前のifでm==0となればいいのだが、そうでないならば数字をAやりくりしても実現不可なのでFalseを返す
        return False

    return solve(i+1, m) or solve(i+1, m-A[i])


for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')



Measured memory_bytes: 7660
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#define INF 1<<28
#define F first
#define S second
using namespace std;

int sx, sy, gx, gy;
typedef pair < int, int > P;
vector < P > p[5];
int memo[5][5][1111];

int solve(int k, int t, int q){

  if(k == 4) return abs(p[t][q].F-gx) + abs(p[t][q].S-gy);
  if(memo[k][t][q]) return memo[k][t][q];

  int ans = INF, d = (t+1)%5, c;
  for(int i=0;i<p[d].size();i++){
    if(!k) c = abs(sx-p[d][i].F) + abs(sy-p[d][i].S);
    else c = abs(p[t][q].F-p[d][i].F) + abs(p[t][q].S-p[d][i].S);
    ans = min(ans, solve(k+1, d, i) + c);
  }

  return memo[k][t][q] = ans;
}

int main(){

  int w,h;
  char c;

  while(true){
    cin >> w >> h;
    if(!w && !h) break;

    for(int i=0;i<5;i++) p[i].clear();
    
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> c;
	if(c == 'S') sx = j, sy = i;
	if(c == 'G') gx = j, gy = i;
	else if(c != '.') p[c-'1'].push_back(P(j,i));
      }
    }
    
    P q = P(0,INF);
    for(int i=0;i<5;i++){
      memset(memo, 0, sizeof(memo));
      if(q.S > solve(0,i,0)) q.F = i+1, q.S = solve(0,i,0);
    }

    if(q.S == INF) cout << "NA\n";
    else cout << q.F << " " << q.S << endl;

  }
}

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


int main(){
    ll N; cin >> N;
    ll res = 0;

    if(N%2){
        cout << res << endl;
        return 0;
    }
    ll m = 10;
    while(m <= N){
        res += (N/m);
        m*=5;
    }
    cout << res << endl;

}

Measured memory_bytes: 3544
N,M = map(int,input().split())
query = [int(input()) for _ in range(M)]
ans = []
set_ = set()
for q in query[::-1]:
    if q not in set_:
        ans.append(q)
        set_.add(q)
for i in range(1,N+1):
    if i not in set_:
        ans.append(i)
print(*ans,sep="\n")


Measured memory_bytes: 20344
import math
import itertools

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i],y[i] = map(int,input().split())

arr = list(range(n))
p = list(itertools.permutations(arr))

def calc(x1,y1,x2,y2):
    return ((x1-x2) ** 2 + (y1-y2) ** 2) ** 0.5

ans = []

for p_arr in p:
    s = 0.0
    for i in range(1,len(p_arr)):
        s += calc(x[p_arr[i]],y[p_arr[i]],x[p_arr[i-1]],y[p_arr[i-1]])
    ans.append(s)

print(sum(ans) / len(ans))


Measured memory_bytes: 9460
from heapq import heappush, heappop


class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parents[y] = x

while 1:
    N = int(input())
    if N == 0:
        exit()
    q = []
    ans = 0
    S = UnionFind(N)
    x = [None] * N
    y = [None] * N
    z = [None] * N
    r = [None] * N

    for i in range(N):
        x[i], y[i], z[i], r[i] = map(float, input().split())

    for i in range(N):
        for j in range(i+1, N):
            d = (x[i]-x[j])**2 + (y[i]-y[j])**2 + (z[i]-z[j])**2
            d = d**0.5 - r[i] - r[j]
            heappush(q, (max(0,d), i, j))
    # クラスカル法
    while len(q) > 0:
        d, a, b = heappop(q)
        if S.find(a) != S.find(b):
            ans += d
            S.union(a, b)
    print('{:.3f}'.format(ans))


Measured memory_bytes: 6284
fn main() {
    let n: String = read();
    let n: Vec<char> = n.chars().collect();
    if n[0] == n[2] {
        println!("Yes");
    } else {
        println!("No");
    }
}



use std::io::*;
use std::str::FromStr;

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

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

using namespace std;

int main() {
	int A, B, K;
	cin >> A >> B >> K;
	int N = A <= B ? A : B;
	vector<int> num;
	for (int i = 1; i <= N; i++) {
		if (A%i == 0 && B%i == 0) {
			num.push_back(i);
		}
	}
	cout << num[num.size() - K] << endl;
	return 0;
}

Measured memory_bytes: 256
import itertools
N=int(input())
xy=[0]*N

for i in range(N):
    xy[i] = list(map(int, input().split()))

perm = list(itertools.permutations(range(N),N))

ans=0
for p in perm:
    for i,_ in enumerate(p[1:]):
        xi = xy[p[i-1]][0]
        xj = xy[p[i]][0]
        yi = xy[p[i-1]][1]
        yj = xy[p[i]][1]
        result = ((xi-xj)**2 + (yi-yj)**2) ** (1/2)
        ans+=result

print(ans/len(perm))


Measured memory_bytes: 8052
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long H, W, K;
    scan(H, W, K);
    auto S = new string[](H);
    foreach (i; 0 .. H)
        S[i] = sread();
    auto ans = new long[][](H, W);
    foreach (y; 0 .. H)
        ans[y][] = -1;
    auto cnt = new long[](H);
    long id = 1;
    foreach (y; 0 .. H)
        foreach (x; 0 .. W)
            if (S[y][x] == '#')
                cnt[y]++;
    foreach (y; 0 .. H)
        if (cnt[y] != 0)
        {
            foreach (x; 0 .. W)
            {
                if (S[y][x] == '#')
                {
                    ans[y][x] = id++;
                }
            }
            foreach (x; 0 .. W - 1)
            {
                if (ans[y][x] != -1 && ans[y][x + 1] == -1)
                {
                    ans[y][x + 1] = ans[y][x];
                }
            }
            foreach_reverse (x; 1 .. W)
            {
                if (ans[y][x] != -1 && ans[y][x - 1] == -1)
                {
                    ans[y][x - 1] = ans[y][x];
                }
            }
        }
    foreach (x; 0 .. W)
    {
        foreach (y; 0 .. H - 1)
        {
            if (ans[y][x] != -1 && ans[y + 1][x] == -1)
            {
                ans[y + 1][x] = ans[y][x];
            }
        }
        foreach_reverse (y; 1 .. H)
        {
            if (ans[y][x] != -1 && ans[y - 1][x] == -1)
            {
                ans[y - 1][x] = ans[y][x];
            }
        }
    }
    foreach (a; ans)
    {
        arywrite(a);
    }
}


Measured memory_bytes: 5868
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

template <class T>
bool chmax(T &a, const T &b);
template <class T>
bool chmin(T &a, const T &b);

int main() {
    int n;
    vector<lint> ga(3), gb(3);
    cin >> n;
    for (int i = 0; i < 3; i++) {
        cin >> ga[i];
    }
    for (int i = 0; i < 3; i++) {
        cin >> gb[i];
    }
    // dp1[i]:=iどんぐり使った時の価値最大
    vector<lint> dp1(n + 1, n);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < n; j++) {
            if (j + ga[i] <= n) {
                chmax(dp1[j + ga[i]], dp1[j] + gb[i] - ga[i]);
            }
        }
    }
    lint m = *max_element(all(dp1));
    vector<lint> dp2(m + 1, m);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < m; j++) {
            if (j + gb[i] <= m) {
                chmax(dp2[j + gb[i]], dp2[j] + ga[i] - gb[i]);
            }
        }
    }
    cout << *max_element(all(dp2)) << endl;
}

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

Measured memory_bytes: 195584
import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
LIMIT = 10 ** 18
n=int(input())
#a=(int,read.split())
a=[int(i) for i in input().split()]
if 0 in a:
	print(0)
	exit()

ans = 1
for i in a:
	ans *= i
	if ans > 10**18:
		print(-1)
		exit()
print(ans)
	

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

#define MOD (998244353)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define nl '\n'
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
#define input(vec,N) for(int i = 0; i < (N); i++) cin >> vec[i];
#define debug(x) cerr << #x << " = " << (x) << endl;

// template starts
typedef long long int ll;
#define int ll
// template ends here
vector<int> S;
int N, K;
void solve(){
	// code starts from here
	cin >> N >> K;
	vector<pair<int,int>> ran;
	for(int k = 0; k < K; k++){
		int l, r;
		cin >> l >> r;
		ran.pb(mp(l,r));
	}
	sort(all(ran));
	
	vector<int> dp(N+1,0);
	vector<int> p(N+2,0);
	dp[1] = 1;
	p[1] = 1;
	
	p[0] = 0;
	for(int i = 2; i <= N; i++){
		int add = 0;
		for(int j = 0; j < K; j++){
			if(ran[j].first >= i) break;
			
			int l = max((int)1,i-ran[j].second);
			int r = i-ran[j].first;
			
			add += p[r]-p[l-1];
			//debug(p[ran[j].second]);
			add %= MOD;
			add += MOD;
			add %= MOD;
		}
		//debug(add);
		dp[i] = add;
		dp[i] %= MOD;
		p[i] = (p[i-1] + dp[i])%MOD;
		
		//print(dp,0,N);
		//print(p,0,N);
		//cerr << endl;
	}
	cout << dp[N] << endl;
}

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

signed main(){
 	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	//startTime = clock();
	
	int T;
	//cin >> T;
	T = 1;
	while(T--){
		solve();
	}
	
	//cout << getCurrentTime() << endl;
	return 0;
}


Measured memory_bytes: 6328
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;

int main()
{
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();

    for(int i=0; i<n; ++i){
        if(s[i] == 'a')
            continue;
        int cost = 'z' - s[i] + 1;
        if(cost <= k){
            s[i] = 'a';
            k -= cost;
        }
    }
    k %= 26;
    s[n-1] += k;
    if(s[n-1] > 'z')
        s[n-1] -= 26;

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tc int t; cin>>t; while(t--)
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mod 1000000007
#define pb push_back
#define vi vector<int>
#define vc vector<char>
#define eb emplace_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define fo(i,x,n) for(int i=x;i<n;i++)
#define csb(x) __builtin_popcount(x)
#define tz(x) __builtin_ctz(x)
#define lsbp(x) __builtin_ffs(x)
#define msbp(x) __lg(x)
#define btoi(str,i) stoi(str,0,i)
#define ff first
#define ss second
const int inf=0x3f3f3f3f3f3f3f3f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



int32_t main(){

int n;cin>>n;
vector<double>v(n);
for(int i=0;i<n;i++)cin>>v[i];
vector<vector<double>>dp(n+1,vector<double>(n+1,0.0));
dp[0][0]=1;
for(int i=1;i<=n;i++)dp[0][i]=0;
dp[1][0]=(1-v[0]);
for(int i=2;i<=n;i++)dp[i][0]=(1-v[i-1])*dp[i-1][0];
for(int i=1;i<=n;i++){
   for(int j=1;j<=n;j++){
      dp[i][j]=v[i-1]*dp[i-1][j-1]+((double)(1.0-v[i-1]))*dp[i-1][j];
      // cout<<dp[i][j]<<" ";
   }
   // cout<<endl;
}
double s=0;
for(int i=(n+1)/2;i<=n;i++){
   s+=dp[n][i];
}
cout<<fixed<<setprecision(10)<<s<<endl;

}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define END getchar();getchar();return 0

signed main() {
	string s;
	int cnt = 0;
	cin >> s;
	for(int i=s.size();i>=0;i--){
		for(int j=0;j<s.size()-i+1;j++){
			bool bou = true;
			for (int k = j; k < j + i ; k++) {
				if (s[k] != 'A'&&s[k] != 'C'&&s[k] != 'G'&&s[k] != 'T') {
					bou = false;
					break;
				}
			}
			if (bou) {
				cout << i << endl;
				END;
			}
		}
	}
	cout << cnt << endl;

	END;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(M)]

par = [0]*(N+1)

for i in range (N+1): #[0,1,2,...,N]を作成
    par[i] = i

#木の根を求める関数
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

#根が同じならTrue,別ならFalseを返す関数
def find(x,y):
    return root(x)==root(y)

#経路を圧縮して連結させる関数
def union(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    par[x] = y

for l in L:
    union(l[0],l[1])

R = [0]
R[0] = root(par[1])
for i in range(2,N+1):
    if R[0] != root(par[i]):
        R.append(root(par[i]))

print(len(set(R))-1)

Measured memory_bytes: 102224
#include <stdio.h>

long max(long a,long b){
    if(a>b)return a;
    else return b;
}


int main(){
    int N;
    scanf("%d",&N);
    long a[100010];
    long b[100010];
    long c[100010];
    int i;
    for(i=0;i<N;i++){
        scanf("%lu%lu%lu",&a[i],&b[i],&c[i]);
    }
    long dp[100010][3];
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 0;
    dp[1][0] = max(b[0],c[0]);
    dp[1][1] = max(a[0],c[0]);
    dp[1][2] = max(b[0],a[0]);
    for(i=2;i<=N;i++){
        dp[i][0] = max(dp[i-1][1] + b[i-1],dp[i-1][2] + c[i-1] );
        dp[i][1] = max(dp[i-1][0] + a[i-1],dp[i-1][2] + c[i-1] );
        dp[i][2] = max(dp[i-1][0] + a[i-1],dp[i-1][1] + b[i-1] );
    }
    
    
    printf("%lu\n",max(dp[N][0],max(dp[N][1],dp[N][2])));
    return 0;
}

Measured memory_bytes: 4864
#include <iostream>
using namespace std;
int main() {
  int n;
  string s;
  cin >> n >> s;
  if (n % 2 == 1) {
    puts("No");
    return 0;
  } else {
    for (int i = 0; i < n / 2; ++i) {
      if (s.at(i) != s.at(n / 2 + i)) {
        puts("No");
        return 0;
      }
    }
    puts("Yes");
  }
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <assert.h>
typedef int64_t ll;
typedef uint64_t ull;
int acs(const void *a, const void *b){return *(int*)a - *(int*)b;} /* 1,2,3,4.. */
int des(const void *a, const void *b){return *(int*)b - *(int*)a;} /* 8,7,6,5.. */
#define min(a,b) (a < b ? a: b)
#define max(a,b) (a > b ? a: b)

#define MAXN (100000)
#define MOD (1000000007)

int d[MAXN];
int main(void)
{
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&(d[i]));
    }
    qsort(d,n,sizeof(int),acs);
    if(d[(n/2)-1]==d[n/2])
    {
        printf("0\n");
        return 0;
    }

    printf("%d\n",d[n/2]-d[(n/2)-1]);
    return 0;
}


Measured memory_bytes: 892
import java.util.*;
import java.io.*;
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
    
    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        // int n=sc.nextInt();
        // char c[][] = new char[h][w];
        // char c[]=sc.nextString().toCharArray();
        // int d[]=new int[n];
        // for(int i=0; i<n; i++) {d[i]=sc.nextInt();}

        int n=sc.nextInt();
        String d[] = new String[n];
        for (int i=0; i<n; i++) {
            d[i] = sc.nextString();
        }
        int ans=0;

        for(int i=0; i<n; i++) {
            int c=0;
            lp:for(int t=0; t<n; t++) {
                for (int w=0;w<n ;w++) {
                    if(d[(t+i)%n].charAt(w)!=d[(w+i)%n].charAt(t))break lp;
                    c++;
                }
            }
            if(c==n*n)ans+=n;
        }
    

        out.println(ans);
        out.flush();
    }


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

class P implements Comparable<P>{
    int id, d;
    P(int  id, int d) {
        this.id=id;
        this.d=d;
    }
    public int compareTo(P p){
        return d-p.d; //des
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


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

int main(){
	int a, b, count = 0;
	cin >> a >> b;
	for (int i = a; i <= b; ++i) {
		if (i % 10 == i / 10000 && (i / 10) % 10 == (i / 1000) % 10) ++count;
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

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

    cout << b * 2 - a << endl;

    return 0;
}

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

void solve() {
    int n;
    read(n);
    
    vt<int> a(n);
    
    read(a);
    
    int sum = 0;
    FOR(n) {
        sum += a[i];
    }
    
    sort(all(a));
    
    if (sum % 10) {
        print(sum);
        return;
    }
    
    FOR(n) {
        if (a[i] % 10 != 0) {
            print(sum - a[i]);
            return;
        }
    }
    
    print(0);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    //read(tt);
    FOR(tt) {
        
        solve();
        
    }
    
}



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


int main(){
	ll a, b;
	cin >> a >> b;
	ll tmp;

	if(a<b){
		tmp = a;
		a = b;
		b = tmp;
	}
	ll A = a;
	ll B = b;
	ll r = A % B;
	while(r!= 0){
		A = B;
		B = r;
		r = A % B;
	}

	ll ans = a*b/B; 
	//cout << "B" << B << endl;

	cout << ans << endl;

	return 0;
}

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

#define ll long long int
#define vi vector<int>

int main() {

    ll A, B, C, K;
    cin >> A >> B >> C >> K;

    if (K <= A) {
        cout << K << endl;
        return 0;
    }
    else if (K <= A + B) {
        cout << A << endl;
        return 0;
    }
    else  {
        cout << A - (K - A - B) << endl;
        return 0;
    }

    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);
void trace(int A[], int N);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/





int main()
{
	int n;
	char str[10], com[13];
	map<string, bool> T;
	
	cin >> n;
	REP(n)
	{
		scanf("%s%s", com, str);
		if (com[0] == 'i')
		{
			T[string(str)] = true;
		} else {
			if (T[string(str)]) printf("yes\n");
			else printf("no\n");
		}
	}
	
	return 0;
}


void trace(int A[], int N)
{
	REP(N)
	{
		if (i > 0) cout << " ";
		cout << A[i];
	}
	cout << endl;
}


double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

Measured memory_bytes: 45492
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
using namespace std;

int main(){
	int c500,c100,c50,x;
	cin >> c500 >> c100 >> c50 >> x;
	int cnt=0;
	for(int i=0;i<=c500;i++){
		for(int j=0;j<=c100;j++){
			for(int k=0;k<=c50;k++){
				if(500*i+100*j+50*k==x)cnt++;
			}
		}	
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int main(){

	int n, x[100], y[100];

	cin >> n;

	for ( int i = 0; i < n; i++ ) cin >> x[i];

	for ( int i = 0; i < n; i++ ) cin >> y[i];


	double d[4];

	for ( int i = 0; i < 4; i++ ) d[i] = 0.0;


	for ( int p = 1; p <= 3; p++ ){

		for ( int i = 0; i < n; i ++ ){

			d[p] += pow ( fabs(x[i] - y[i]), p);

		}

		d[p] = pow(d[p], 1.0/p);

	}

	for ( int i = 0; i < n; i++ ){

		d[0] = (d[0] < fabs(x[i] - y[i])?fabs(x[i] - y[i]):d[0]);

	}

	printf( "%1f\n", d[1]);

	printf( "%1f\n", d[2]);

	printf( "%1f\n", d[3]);

	printf( "%1f\n", d[0]);

	return 0;

}

Measured memory_bytes: 1244