akhauriyash/Code-Regression huggingface dataset:
<?php
define("MOD", 100);
$n = intval(trim(fgets(STDIN)));
$s = trim(fgets(STDIN));
$n = strlen($s);
$kigu = 0;
for($i = 0; $i < $n; $i++){
    $dp[$i] = ((int)$s[$i])-1;
    $kigu ^= ($dp[$i]%2) * ((($n-1) & $i) == $i);
}
if($kigu){
    echo 1;
}else{
    if(array_search(1, $dp)!==false){
        echo 0;
    }else{
        $kigu = 0;
        for($i = 0; $i < $n; $i++){
            $dp[$i] = ((int)$s[$i])-1;
            $kigu ^= (($dp[$i]/2)%2) * ((($n-1) & $i) == $i);
        }
        if($kigu){
            echo 2;
        }else{
            echo 0;
        }
    }
}

function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array: ";
            echo implode(" ", addIndex($val))."\n";
        }else{
            echo "array:array\n";
            if(isCleanArray($val)){
                foreach($val as $row)echo implode(" ", addIndex($row))."\n";
            }else{
                foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row))."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
function addIndex($val){
    if(!isCleanArray($val)){
        $val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);
    }
    return $val;
}
function isCleanArray($array){
    $clean = true;
    $i = 0;
    foreach($array as $k => $v){
        if($k != $i++)$clean = false;
    }
    return $clean;
}
/**
 * 座圧対象の配列を渡すと以下の値を返す
 * ・圧縮された配列
 * ・復元用のMap
 * ・圧縮用のMap
 **/
function atsu($array){
    $a = array_flip($array);
    $fuku = array_flip($a);
    sort($fuku);
    $atsu = array_flip($fuku);
    foreach($array as $i => $val)$array[$i] = $atsu[$val];
    return [$array, $fuku, $atsu];
}
//配列の最大公約数
function gcdAll($array){
    $gcd = $array[0];
    for($i = 1; $i < count($array); $i++){
        $gcd = gcd($gcd, $array[$i]);
    }
    return $gcd;
}

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

//配列の最小公倍数
function lcmAll($array){
    $lcm = $array[0];
    for($i = 1; $i < count($array); $i++){
        $lcm = lcm($lcm, $array[$i]);
    }
    return $lcm;
}

//最小公倍数
function lcm($a, $b) {
    return $a / gcd($a, $b) * $b;
}
//ビットカウント-1の数を数える
function popcount($x){
    $con = 0;
    while ($x) {
        $x &= $x-1;
        ++$con;
    }
    return $con;
}

function prepareMod($n){
    global $f, $invf;
    $f[0] = $invf[0] = $invf[1] = 1;
    for($i = 1; $i <= $n; $i++)$f[$i] = $f[$i-1]*$i%MOD;
    for($i = 2; $i <= $n; $i++)$invf[$i] = (MOD - intdiv(MOD, $i))*$invf[MOD%$i]%MOD;
    for($i = 2; $i <= $n; $i++)$invf[$i] = $invf[$i]*$invf[$i-1]%MOD;
}
function nCm($n, $m){
    global $f, $invf;
    if($n < 0 || $n - $m < 0)return 0;
    return $f[$n] * $invf[$n-$m] % MOD * $invf[$m] % MOD;
}

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

int main(){
  int n,p,t1,t2,a=0,b=0;
  cin>>n;
  set<int> st;
  vector<int> v(n);
  
  rep(i,n) st.insert(i+1);
  rep(i,n){
    cin>>p;
    t1=1;
    for(int j=i;j<n-1;j++) t1*=(n-j-1);
    t2=distance(st.begin(),lower_bound(ALL(st),p));
    st.erase(p);
    a+=t1*t2;
  }
  rep(i,n) st.insert(i+1);
  rep(i,n){
    cin>>p;
    t1=1;
    for(int j=i;j<n-1;j++) t1*=(n-j-1);
    t2=distance(st.begin(),lower_bound(ALL(st),p));
    st.erase(p);
    b+=t1*t2;
  }
  cout<<abs(a-b)<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  int n, x;
  while (cin >> n >> x, n || x)
  {
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
      for (int j = i + 1; j <= n; ++j)
      {
        for (int k = j + 1; k <= n; ++k)
          if (i + j + k == x)
            cnt++;
      }
    }
    cout << cnt << endl;
  }

  return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    ll n, m, d; cin >> n >> m >> d;
    ll x = max(n-2*d,(ll)0)*2;
    x += n-max(d+1,n-d+1)+1;
    x += min(n-d,d);
    x *= m-1;
    if (d == 0) x /= 2;
    double ans = (double)x/pow(n,2);
    printf("%.10f\n",ans);
}


Measured memory_bytes: 3772
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[u].append(v)

    # 辺を除かなかったときの期待値dp
    dp=[None]*n
    dp[n-1]=0.0
    for v in range(n-2,-1,-1):
        deg=len(E[v])
        res=0
        for nv in E[v]:
            res+=dp[nv]
        res/=deg
        dp[v]=res+1

    ans=dp[0]

    # 行き先の期待値が最も大きい辺を除いたときの期待値dp
    for v0 in range(n-1):
        if(len(E[v0])<=1): continue
        w0=max((dp[w],w) for w in E[v0])[1] # v0 -> w0 の辺を除く
        dp1=[None]*n
        dp1[n-1]=0.0
        for v in range(n-2,-1,-1):
            deg=len(E[v])
            res=0
            for nv in E[v]:
                if((v,nv)==(v0,w0)):
                    deg-=1
                else:
                    res+=dp1[nv]
            res/=deg
            dp1[v]=res+1
        ans=min(ans,dp1[0])

    print(ans)
resolve()

Measured memory_bytes: 53852
#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <numeric>

    using namespace std;
     
    int main() {
      int n;
      cin >> n;
      
      vector<int> v(n);
      for (int i=0;i<n;i++){
        cin >> v[i];
      }
      
      //int max = *std::max_element(v.begin(), v.end());
      std::vector<int>::iterator max_it = std::max_element(v.begin(), v.end());
      int max = *max_it;
      v.erase(max_it);
      int sum = std::accumulate(v.begin(), v.end(), 0);
      sum = sum + max/2;
      cout << sum << endl;
      return 0;
    }

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

al = {}
for i in range(n):
    a = input()
    if not a in al:
        al[a] = 1
    else:
        al[a] += 1

al = sorted(al.items(),key=lambda x:-x[1])
al = [(k, v) for k,v in al if v==al[0][1]]
al = sorted(al, key= lambda x: x[0])
for k, v in al :
    print(k)

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

using namespace std;

typedef long long int ll;

const ll mod = 1e9 + 7;
const ll MAXN = 1e5 + 5;

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

  ll n, m;
  cin >> n >> m;
  vector < pair < ll, ll > > v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i].second >> v[i].first;
    v[i].first = -v[i].first;
  }

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

  multiset < ll > s;
  for(int i = 0; i <= m; i++) s.insert(i);

  ll ans = 0;
  for(auto i : v){
    auto it = s.lower_bound(i.second);
    if(it != s.end()){
      ans -= i.first;
      s.erase(it);
    }
  }

  cout << ans << '\n';
}


Measured memory_bytes: 6528
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int main(){
  int D, G; cin >> D >> G;
  int p[D], c[D];
  rep(i, D){
    cin >> p[i] >> c[i];
  }
  int ans = inf;
  rep(i, (1<<D)){
    int MAX=-1, tmp = 0, goal = G; bool keta[D]={0};
    rep(j, D){
      if((1<<j) & i){
        goal -= p[j]*100*(j+1) + c[j];
        tmp += p[j];
        keta[j] = true;
      }
    }
    goal = max(0, goal);
    while(goal>0){
      for(int j=D-1; j>=0; j--){
        if(!(keta[j])){
          int ko = p[j];
          while(ko > 0 && goal>0){
            goal-=100*(j+1);
            ko--;
            tmp++;
          }
        }
        if(j==0) break;
      }
    }
    if(goal<=0) ans = min(ans, tmp);
    if(tmp==50) cout << i << endl;
  }
  cout << ans << endl;    
 }

Measured memory_bytes: 256
class SegmentTree:
    def __init__(self,n,ele=0):
        self.ide_ele = ele
        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

    def segfunc(self,x,y):
        return x|y

    def init(self,init_val):
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 

    def update(self,k,x):
        k += self.num-1
        if self.seg[k]==x:
          return 0
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
      
N,S,Q=int(input()),input(),int(input())
d={'a': 1, 'b': 2, 'c': 4, 'd': 8, 'e': 16, 'f': 32, 'g': 64, 'h': 128, 'i': 256, 'j': 512, 'k': 1024, 'l': 2048, 'm': 4096, 'n': 8192, 'o': 16384, 'p': 32768, 'q': 65536, 'r': 131072, 's': 262144, 't': 524288, 'u': 1048576, 'v': 2097152, 'w': 4194304, 'x': 8388608, 'y': 16777216, 'z': 33554432}

initial=[d[c] for c in list(S)]

ST=SegmentTree(N)
ST.init(initial)

for _ in range(Q):
    typ,a,b=input().split()
    if typ=='1':
        i,c=int(a),d[b]
        ST.update(i-1,c)
    else:
        l,r=int(a)-1,int(b)
        x=bin(ST.query(l,r))[2:]
        print(sum(map(int,list(x))))

Measured memory_bytes: 37868
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {

	ll A, B, C,K;
	cin >> A >> B >> C >> K;
	while (B <= A) {
		B *= 2;
		K--;
	}
	while (C <= B) {
		C *= 2;
		K--;
	}
	if (K < 0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}
	
}


Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#define N 200005
using namespace std;
int n, k, l;
int par1[N], par2[N];
map<pair<int, int>, int> cnt;
int find(int u, int* par) {
  return u == par[u] ? u : par[u] = find(par[u], par);
}
int main() {
  cin>>n>>k>>l;
  for (int i = 1; i <= n; ++i) {
    par1[i] = i;
    par2[i] = i;
  }
  cnt.clear();
  for (int i = 0; i < k; ++i) {
    int p, q;
    cin>>p>>q;
    int px = find(p, par1);
    int py = find(q, par1);
    if (px != py) {
      par1[px] = py;
    }
  }
  for (int i= 0; i < l; ++i) {
    int r, s;
    cin>>r>>s;
    int pr = find(r, par2);
    int ps = find(s, par2);
    if (pr != ps) {
      par2[pr] = ps;
    }
  }
  for (int i = 1; i <= n; ++i) {
    cnt[make_pair(find(i, par1), find(i, par2))]++;
  }
  for (int i = 1; i <= n; ++i) {
    cout<<cnt[make_pair(find(i, par1), find(i, par2))];
    if (i < n) cout<<" ";
    else cout<<endl;
  }
	return 0;
}


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


int main(){
    int n;
    cin>>n;
    vector<int>edge[n];
    for(int i=0;i<n-1;i++){ 
    	int a,b; 
        cin>>a>>b;
        a--;
        b--;
    	edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    int color[n];
    int ans[2];
    ans[0]=0;
    ans[1]=0;
    memset(color,-1,sizeof color);
	queue<int>q; 
    q.push(0);
    q.push(n-1);
    color[0]=0;
    color[n-1]=1;
	while(!q.empty()){
        int now=q.front();
        q.pop();
        ans[color[now]]++;
        for(int i=0;i<edge[now].size();i++){
        	int nex=edge[now][i];
        	if(color[nex]==-1){
				color[nex]=color[now];
				q.push(nex);
			}
		}
	}
    if(ans[1]>=ans[0])cout<<"Snuke";else cout<<"Fennec"<<endl;
    return 0;
}

Measured memory_bytes: 6144
#include<string.h>
#include<stdio.h>

char str1[200001],str2[200001];
int main(){
int len,i,j;
int alphabets[26],checkcount = 0,error = 0;
for(i = 0;i < 26;i++){
alphabets[i] = -1;
}
scanf("%s",str1);
scanf("%s",str2);
len = strlen(str1);

for(i = 0;i < len;i++){
if(alphabets[str1[i] - 'a'] == -1){
alphabets[str1[i] - 'a']= str2[i] - 'a';
}
else if(alphabets[str1[i] - 'a'] != str2[i] -'a'){error = 1;break;}
}

for(i = 0;i < 26;i++){
checkcount = 0;
for(j = 0;j < 26;j++){
if(alphabets[j] == i){checkcount++;}
}
if(checkcount > 1){error = 1;break;}
}
if(error == 0){printf("Yes\n");}else{printf("No\n");}
return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int i,j,k,count1=0,count2=0;

int main(void){
    int h1,m1,h2,m2,k,ans;
    cin>>h1>>m1>>h2>>m2>>k;
    ans=(h2-h1)*60+(m2-m1)-k;
    cout<<((ans>=0)?ans:0)<<endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,d,x;cin >> n >> d >> x;
	int a[n+5];
	int ans = 0;
	for(int i = 0;i<n;i++) cin >> a[i];
	for(int i = 1;i<=d;i++){
		for(int j = 0;j<n;j++){
			if((i-1)%a[j] == 0 || i == 1){
				ans++;
//				cout << i << ' ' << j << endl;
			}
		}
	}
	cout << ans+x;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    auto hw = readints;
    int h = hw[0], w = hw[1];

    auto g = new int[][](h, w);
    for (int i = 0; i < h; i++) {
        g[i][] = readints;
    }

    int[][] ans;
    for (int r = 0; r < h; r++) {
        for (int c = 0; c < w; c++) {
            if (g[r][c] % 2 == 1) {
                if (c + 1 < w) {
                    g[r][c]--;
                    g[r][c+1]++;
                    ans ~= [r, c, r, c + 1];
                }
                else if (r + 1 < h) {
                    g[r][c]--;
                    g[r+1][c]++;
                    ans ~= [r, c, r + 1, c];
                }
            }
        }
    }

    writeln(ans.length);
    foreach (a; ans) {
        writeln(a.map!(e => (e + 1).to!string).join(" "));
    }
}


Measured memory_bytes: 23932
#include<iostream>
#include<map>
#include<queue>
using namespace std;

typedef pair<string,int> P;

int main(){
  int h,w,d;
  string tmp,g;
  int dx[] = {0,1,0,-1}, dy[] = {-1,0,1,0};

  while(cin >> h >> w, h||w){
    g = "";
    for(int i=0;i<h;i++){
      cin >> tmp;
      g += tmp;
    }

    map<string,int> m;
    deque<P> q;
    q.push_back(P(g,1));

    string hoge = "";
    bool f = false;
    while(!q.empty()){
      P p = q.front(); q.pop_front();
      g = p.first;
      d = p.second;
      if(m[g])continue;
      m[g] = d;

      if(hoge == g)break;
      hoge = g;
      int y,x;
      for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
	  if(g[i*w+j] == '@'){
	    y = i; x = j; break;
	  }
	}
      }

      for(int i=0;i<4;i++){
	int sy = y+dy[i], sx = x+dx[i];
	if(g[sy*w+sx] == '#' || g[sy*w+sx] == 'w')continue;
	if(g[sy*w+sx] == 'E'){
	  cout << d << endl;
	  f = true; break;
	}
	if(g[sy*w+sx] == '.'){
	  tmp = g;
	  tmp[y*w+x] = '.';
	  tmp[sy*w+sx] = '@';
	  q.push_back(P(tmp,d+1));
	}
	if(g[sy*w+sx] == 'c'){
	  tmp = g;
	  tmp[sy*w+sx] = '.';
	  for(;;){
	    sy += dy[i]; sx += dx[i];
	    if(tmp[sy*w+sx] == '#' || tmp[sy*w+sx] == 'c'){
	      tmp[(sy-dy[i])*w+(sx-dx[i])] = 'c';
	      break;
	    }
	    if(tmp[sy*w+sx] == 'w'){
	      tmp[sy*w+sx] = '.';
	      break;
	    }
	  }
	  q.push_front(P(tmp,d));
	}
      }
      if(f)break;
    }
    if(!f)cout << -1 << endl;
  }
}

Measured memory_bytes: 12184
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<list>
#include<utility>
#include<tuple>
#include<cstdio>
#include<map>
#include<unordered_map>
#include<ios>
#include<iomanip>
using namespace std;
typedef long long llong;
llong gcd(llong a, llong b) {
	if (a < b) std::swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
llong lcm(llong a, llong b) {
	llong g = gcd(a, b);
	return a * b / g;
}
//ここまで共通
int N, D;
int main() {
	cin >> N >> D;
	D = 2 * D + 1;
	int ans = N / D;
	if (N % D != 0) {
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
using System;

class Program {
    static void Main(string[] args) {
        //入力
        string s = Console.ReadLine();
        //文字数
        int len = s.Length;

        //出力する文字列
        string ans;
        string ans_0;
        string ans_1;
        string ans_2;

        //判定
        if (len == 2) {
            ans = s;
        } else {
            ans_0 = s.Substring(2, 1);
            ans_1 = s.Substring(1, 1);
            ans_2 = s.Substring(0, 1);
            ans = ans_0 + ans_1 + ans_2;
        }

        //出力
        Console.WriteLine(ans);
    }
}

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

int main(void) {
    int N;
    cin>>N;
    string S;
    cin>>S;
    int sum = 0;
    for (int i = 0; i < S.size() - 2; i++) {
        if (S.substr(i, 3) == "ABC") {
            sum++;
            i += 2;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
#define inf 0x3f3f3f3f
#define read(x) scanf("%d",&x)
#define lowbit(x) (x&-x)
const int N=2e5+7;
int T;
int n;
int main()
{
    read(n);
    for(int i=0;i<n;i++) printf("ACL");




    return 0;
}
/**


**/


Measured memory_bytes: 3720
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
const double PI = acos(-1);
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
using ll =long long;
const int mod = 1000000007;

//map<string>a
class mint {
	long long x;
public:
	mint(long long 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 {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint & a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint & a) const {
		mint res(*this);
		return res *= 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 {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream & os, const mint & m) {
		os << m.x;
		return os;
	}
};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
//組み合わせ
void recursive_comb(vector<int> indexes, int s, int rest, std::function<void(vector<int>)> f) {
	if (rest == 0) {
		f(indexes);
	}
	else {
		if (s < 0) return;
		recursive_comb(indexes, s - 1, rest, f);
		indexes[rest - 1] = s;
		recursive_comb(indexes, s - 1, rest - 1, f);
	}
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(vector<int>)> f) {
	vector<int>indexes(k);
	recursive_comb(indexes, n - 1, k, f);
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

int main() {
	ll A, B;
	cin >> A >> B;
	cout << lcm(A, B);
}


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;
using P = pair<int,int>;
 
 
int main() {
    int D;
    cin >> D;
    if(D==25) cout << "Christmas" << endl;
    if(D==24) cout << "Christmas Eve" << endl;
    if(D==23) cout << "Christmas Eve Eve" << endl;
    if(D==22) cout << "Christmas Eve Eve Eve" << endl;
}

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

int main(){
  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;
  }
}


Measured memory_bytes: 256
import sys


def main(S, K):
    # len(S) <= 100
    # K <= 10^18
    # 5,000,000,000,000,000

    one = 0 
    for d in S:
        if d == '1':
            one += 1
        else:
            c = d
            break
    print("one", one, file=sys.stderr)
    if one != 0 and K <= one:
        return '1'
    else:
        return d

if len(sys.argv) == 3:
    S = sys.argv[1]
    K = int(sys.argv[2])
    print(main(S, K))
else:
    S = input()
    K = int(input())
    print(main(S, K))


Measured memory_bytes: 3064
from bisect import bisect_right

N = int(input())
L = list(map(int,input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i):
        m = L[i]-L[j]
        k = bisect_right(L,m)
        n = max(0, j-k)
        ans += n

print(ans)


Measured memory_bytes: 43100
#include <stdio.h>

int main(void)
{
    int x, y;
    int i, j;
    int ans = 0;
    scanf("%d %d", &x, &y);
    for (i = 0; i <= x; i++) {
        j = i * 2 + (x - i) * 4;
        if (j == y) {
            ans = 1;
            break;
        }
    }
    printf("%s\n", (ans == 1) ? "Yes" : "No");
    return 0;
}

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

void show(const int a[], const int N){
  for(int i =0; i<N;++i){
    std::cout << (i==0 ? "" : " ") << a[i];
  }
  std::cout << std::endl;
}

int main(){
  int N;
  int a[100];
  std::cin >> N;
  
  for (int i=0;i<N;++i){
    std::cin >> a[i];
  }
  
  show(a, N);
  for (int i=1; i<N; ++i){
    int k = a[i];
    int j = i -1;
    while( j >= 0 && a[j] > k){
      a[j+1] = a[j];
      --j;
    }
    a[j+1] = k;
    show(a, N);
  }

  std::cout << std::flush;
}

Measured memory_bytes: 1160
// 2012/07/27 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int n;
		cin >> n;

		if(n==0)
			break;

		for(int i=0; i<n; i++){
			int x1, y1, z1, w1, x2, y2, z2, w2;
			cin >> x1 >> y1 >> z1 >> w1 >> x2 >> y2 >> z2 >> w2;

			int x3, y3, z3, w3;
			x3 = x1*x2-y1*y2-z1*z2-w1*w2;
			y3 = x1*y2+y1*x2+z1*w2-w1*z2;
			z3 = x1*z2+z1*x2+w1*y2-y1*w2;
			w3 = x1*w2+w1*x2+y1*z2-z1*y2;

			cout << x3 << ' ' << y3 << ' ' << z3 << ' ' << w3 << endl;
		}
	}

	return 0;
}

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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    int n,c=1; string s; cin >> n >> s;
    forsn(i,1,n) if(s[i] != s[i-1]) c++;
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 512
import java.io.*
import java.util.*

var pw = PrintWriter(System.out)
fun solve(A: Long, B: Long, K: Long){
    if (2 * K >= B-A+1){ (A..B).forEach{println(it)}; return }
    (A until A+K).forEach{println(it)}
    (B - K+1..B).forEach{println(it)}
    return
}


fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val A = sc.next().toLong()
    val B = sc.next().toLong()
    val K = sc.next().toLong()
    solve(A, B, K)
}



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

int main()
{

    // ll t;
    // cin >> t;

    // while(t--){
        ll a, b, c, i, j, k, l, m, n, x, y, z;
        char ch;
        string s;

        cin >> x >> y >> z;
        cout << z << " " << x << " " << y << endl;
    // }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
//int dp[300006];
int dp[102][102*500];
int32_t main(){
    int n,m;
    cin>>n>>m;
    int degree[n+1]={0};
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        degree[a]++;
        degree[b]++;
    }
    for(int i=1;i<=n;i++)cout<<degree[i]<<endl;
  return 0;
}

Measured memory_bytes: 256
S = input()
K = int(input())
Sdash = [x for x in S if not x == '1'] 

if len(Sdash) == 0:
    n = len(S) 
else:
    n = S.index(Sdash[0])

if n >= K:
    print(1)
else:
    print(Sdash[0])

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

// ----------- define --------------
#define int long long
#define ii pair<int,int>
#define fi first
#define sc second
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void MAIN() {
  int n; cin >> n;
  map<char, int> m;
  set<char> s = {'M', 'A', 'R', 'C', 'H'};
  for (int i = 1; i <= n; i++) {
    string t; cin >> t;
    if (s.count(t[0])) m[t[0]]++;
  }
  int ans = 0;
  vector<char> v(all(s));
  for (int i = 0; i < 3; i++)
  for (int j = i + 1; j < 4; j++)
  for (int k = j + 1; k < 5; k++) {
    ans += m[v[i]] * m[v[j]] * m[v[k]];
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3596
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>

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

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long mod = 1000000007LL;
//const long long mod = 998244353LL;

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

ll C[20];
ll x[25000];
ll dp[25000][260];
int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	while (1) {
		ll N, M; scanf("%lld %lld", &N, &M);
		if (N == 0 && M == 0) break;
		for (ll i = 0; i < M; i++) scanf("%lld", &C[i]);
		for (ll i = 0; i < N; i++) scanf("%lld", &x[i]);
		for (ll i = 0; i <= N + 1; i++) for (ll j = 0; j < 260; j++) dp[i][j] = INF;
		dp[0][128] = 0;
		for (ll i = 0; i < N; i++) {
			for (ll j = 0; j <= 255; j++) {
				if (dp[i][j] == INF) continue;
				for (ll k = 0; k < M; k++) {
					ll next = j + C[k];
					chmin(next, 255LL);
					chmax(next, 0LL);
					chmin(dp[i + 1][next], dp[i][j] + (x[i] - next) * (x[i] - next));
				}
			}
		}
		ll res = INF;
		for (ll i = 0; i <= 255; i++) chmin(res, dp[N][i]);
		printf("%lld\n", res);
	}
	return 0;
}


Measured memory_bytes: 44000
/*

Coded by peyha X

*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n,k;
string s;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	
	cin >> s >> k;
	n=s.size();
	
	int id=0;
	
	while(n>id && s[id]=='1') id++;
	
	if(k<=id){
		cout << "1\n";
	}
	else{
		cout << s[id] << '\n';
	}
	return 0;
	
	
}

Measured memory_bytes: 256
n = int(input())
r = [int(input()) for i in range(n)]

#min_rは，r[0:i]での最小値
#max_rは，r[0:i]での最大値
min_r = min(r[0], r[1])
max_r = max(r[0], r[1])
ans = r[1] - r[0]
for i in range(2, n):
    #高々考えられる可能性は2通り
    if min_r > r[i]:
        min_r = r[i] #最小値を更新する
    else:
        ans = max(r[i] - min_r, ans) #答えを更新する

print(ans)
    
        


Measured memory_bytes: 13592
#include<bits/stdc++.h>
using namespace std;
int main(){
   string s;
   cin>>s;
   int i,k=0;
   for(i=0;i<=s.size()-1;i++){
        if(s[i]=='9'){
            cout<<"Yes";
            k=1;
            break;
        }
    }
    if(k==0)cout<<"No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define inf 0x7f7f7f7f7f7f7f7f 
#define maxn 1000010
#define ri register int
#define il inline
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define mod 998244353
#define db(x) cout << x << endl; 
#define eps 0.0001
using namespace std;
int a[maxn],v[maxn]={0};
int ans[maxn];
signed main()
{
	ios::sync_with_stdio(0);
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	int p = 1;
	int cnt=0;
	while(!v[p])
	{
		v[p] = 1;
		ans[cnt++] = p;
		p = a[p];
	}
	ans[cnt++] = p;
	int pp = 1;
	for(int i=0;i<cnt-1;i++)
		if(ans[i] == ans[cnt-1])
			pp = i+1;
	int x = cnt-pp;
	if(k<=pp)
	{
		cout << ans[k];
		return 0;
	}
	k=(k-pp)%x;
		cout << ans[pp+k];
	return 0;
}

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

int main(){
  int N, sum=0;
  float K;
  
  cin >> N >> K;
  
  for(int i=0; i<N; i++){
    int x;
    cin >> x;
    
    if(x < K/2.0) sum += x*2;
    else sum += 2*(K-x);
  }
  cout << sum << endl;
}
    
    

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

using namespace std;

int main() {
  int n; cin >> n;
  vector <int> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int j = 0; j < n; j++) {
    int x; cin >> x;
    a[j] = a[j] - x;
  }
  sort(a.rbegin(), a.rend());
  int best = 0;
  for(int i = 0; i < n; i++) {
    best += (a[i] >= 0) * a[i];
  }
  cout << best << '\n';
}


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;
using P = pair<int,int>;

int h, w;
int ch, cw;
int dh, dw;
vector<vector<int>> s;
vector<vector<int>> visited;
vector<int> dx = { -1, 1, 0, 0, 0 };
vector<int> dy = { 0, 0, 0, 1, -1 };

bool is_can(int ny, int nx) {
  if(nx <= 0 || nx > w || ny <= 0 || ny > h) {
    return false;
  }
  if(s[ny][nx] == 1) {
    return false;
  }
  return true;
}

int main() {
  cin >> h >> w;
  s.resize(h+1, vector<int>(w+1, 0));
  visited.resize(h+1, vector<int>(w+1, -1));
  cin >> ch >> cw;
  cin >> dh >> dw;

  rep(i, h) {
    rep(j, w) {
      char a;
      cin >> a;
      if(a == '.') {
        s[i+1][j+1] = 0;
      } else {
        s[i+1][j+1] = 1;
      }
    }
  }

  int ans = -1;

  // ワープX回目での到達可能距離
  queue<P> que;
  queue<P> cur_que;

  que.push(P(ch, cw));

  int warp = 0;
  while(true) {
    bool finished = false;

    while(!que.empty()) {
      auto p = que.front();
      que.pop();

      int y = p.first;
      int x = p.second;
      // cout << warp << ": " << y << "," << x << endl;
      for(int i=0;i<5;i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(is_can(ny, nx) && visited[ny][nx] == -1) {
          que.push(P(ny, nx));
          cur_que.push(P(ny, nx));
          visited[ny][nx] = warp;
          if(P(ny, nx) == P(dh, dw)) {
            ans = warp;
            finished = true;
          }
        }
      }
    }

    if(finished) {
      break;
    }

    // ワープ
    queue<P> next_que;
    while(!cur_que.empty()) {
      auto p = cur_que.front();
      int y = p.first;
      int x = p.second;
      cur_que.pop();

      for(int wx=-2;wx<=2;wx++) {
        for(int wy=-2;wy<=2;wy++) {
          int nx = x + wx;
          int ny = y + wy;
          if(is_can(ny, nx) && visited[ny][nx] == -1) {
            next_que.push(P(ny, nx));
          }
        }
      }
    }

    if(next_que.size() == 0) {
      break;
    }
    que = next_que;
    warp++;
  }

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


Measured memory_bytes: 11648
#include <cstdio>
#include <cstdint>
#include <algorithm>

int main() {
  intmax_t N, K;
  scanf("%jd %jd", &N, &K);

  if (K == 0)
    return !printf("%jd\n", N*N);

  intmax_t res = 0;
  for (int b = K+1; b <= N; ++b) {
    intmax_t unit = std::max<intmax_t>(0, b-K);
    intmax_t rem = std::max<intmax_t>(0, N%b-(K-1));
    res += N/b*unit + rem;
  }

  printf("%jd\n", res);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
int N;

double dp[310][310][310];

double dfs(int i,int j,int k){
    if(dp[i][j][k]>=0.0) return dp[i][j][k];
    if(i==0&&j==0&&k==0) return 0.0;

    double ret=1.0;
    if(i>0) ret+=dfs(i-1,j,k)*i/N;
    if(j>0) ret+=dfs(i+1,j-1,k)*j/N;
    if(k>0) ret+=dfs(i,j+1,k-1)*k/N;

    return dp[i][j][k]=ret*N/(i+j+k);

}

int main(){
    cin>>N;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <=N; ++j) {
            for (int k = 0; k <=N; ++k) {
                dp[i][j][k]=-1.0;
            }
        }
    }
    dp[0][0][0]=0.0;

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

    printf("%.12f\n",dfs(val[0],val[1],val[2]));
    return 0;
}



Measured memory_bytes: 227584
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // Initialize
        	var intN = cin.ReadInt;
          	var aryNum = cin.ReadIntArray(intN).Distinct();
            // Process

          	// Output
        	WriteLine(aryNum.Count());
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 28124
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define vv(T) std::vector<std::vector<T>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

int		main(void)
{
	int n, k;
	cin >> n >> k;

	vector<int> P(n);
	for (int i = 0; i < n; i++)
	{
		cin >> P[i];
		P[i]--;
	}
	vector<ll> C(n);
	for (int i = 0; i < n; i++)
		cin >> C[i];
	
	ll ans = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		vector<int> seen(n);
		ll tmp = 0;
		int j = P[i];
		int cnt = 0;
		while (seen[j] < 1 && cnt < k)
		{
			tmp += C[j];
			ans = max(tmp, ans);
			seen[j]++;
			cnt++;
			j = P[j];
		}
		// cout << "cnt" << cnt << endl;
		ll sum = 0;
		for (int m = 0; m < n; m++)
		{
			if (seen[m])
				sum += C[m];
		}
		sum *= (k / cnt) - 1;
		for (int m = 0; m < k % cnt + cnt; m++)
		{
			sum += C[j];
			ans = max(sum, ans);
			j = P[j];
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 3732
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def find(self, x):
        """
        親が同じか判別する
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        if not uf.same(a - 1, b - 1):
            uf.union(a - 1, b - 1)
    res = 0
    for i in range(1, n):
        if uf.same(0, i):
            continue
        else:
            uf.union(0, i)
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10708
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bits/stdc++.h>
#include<queue>
#include <numeric>
using namespace std;
 
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
 template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define fore(i,a) for(auto &i:a)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
 
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
 



int main(){
    long long N;
    cin >> N;
    double S=sqrt(N);
    long long pos_x,pos_y;
    long long ans=(long long) pow(10,13);
    for(int i=1;i<=S;++i){
        if(N%i==0){
            pos_x=i;
            pos_y=N/i;
            ans=min(ans,pos_y+pos_x-2);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
typedef struct{
  int parent;
  int left;
  int right;
} Tree;
Tree tree[10000];
//int s=0,t=0;
#define NIL -1
int getheight(int);
int main()
{
  int i,id,j,n,k,depth=0,num,l,r,degree=0,height=0;
 
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    tree[i].parent=NIL;
  }
 
  for(i=0;i<n;i++){
    scanf("%d%d%d",&id,&l,&r);
    tree[id].left=l;
    tree[id].right=r;
    if(l!=NIL && r!=NIL){
      tree[l].parent=id;
      tree[r].parent=id;
    }
    else if(l!=NIL && r==NIL){
      tree[l].parent=id;
    }
    else if(l==NIL && r!=NIL){
      tree[r].parent=id;
    }
  }
   
  for(i=0;i<n;i++){
    printf("node %d: parent = %d, ",i,tree[i].parent);
    if(tree[i].parent==NIL){
      printf("sibling = -1, ");
    }
    else if(tree[tree[i].parent].left==i){
      printf("sibling = %d, ",tree[tree[i].parent].right);
    }
    else{
      printf("sibling = %d, ",tree[tree[i].parent].left);
    }
    printf("degree = ");
    if(tree[i].left!=NIL && tree[i].right!=NIL){
      printf("2, ");
    }
    else if(tree[i].left==NIL && tree[i].right==NIL){
      printf("0, ");
    }
    else printf("1, ");
 
    num=i;
    while(tree[num].parent!=NIL){
      depth++;
      num=tree[num].parent;
    }
    printf("depth = %d, ",depth);
    depth=0;
 
    printf("height = ");
    height=getheight(i);
    printf("%d,",height);
    //s=0;t=0;
     
    if(tree[i].parent==NIL){
      printf(" root\n");
    }
    else if(tree[i].left==NIL && tree[i].right==NIL){
      printf(" leaf\n");
    }
    else {
      printf(" internal node\n");
      }
  }
  return 0;
}

int getheight(int i)
{
  int s=0,t=0;
  if(tree[i].left==NIL && tree[i].right==NIL)return 0;

  if(tree[i].left!=NIL){
  s=getheight(tree[i].left)+1;
  }
  if(tree[i].right!=NIL){
  t=getheight(tree[i].right)+1;
  }
  if(s>t){
    
    return s;
  }
  else{
    return t;
  }
}


Measured memory_bytes: 2112
#include<stdio.h>
int main()
{
	int N, M, K;
	int  count[31] = { 0 };

	scanf("%d %d", &N, &M);
	for (int i = 0;i < N;i++)
	{
		scanf("%d", &K);
		for (int j=0;j < K;j++)
		{
			int A;
			scanf("%d", &A);
			A--;
			count[A]++;//j番目の食べ物が好きならcount[j]を+1する
		}
	}
	int ans = 0;
	for (int i = 0;i < M;i++)
	{
		if (count[i] == N)ans++;/*全員i番目の食べ物が好き,つまり
		count[i]==Nならansを+1*/
	}
	printf("%d\n",ans);
	return 0;
}



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

int main(){
	int n,a[200005],k;
	cin >> n >> k;
	for(int i=0;i<k;i++) cin >> a[i];
	sort(a,a+k);
	int ans = n;
	for(int i=0;i<k-1;i++) ans = min(n-(a[i+1]-a[i]),ans);
	ans = min(a[k-1]-a[0],ans);
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)


int main() {

    ll N, M;
    cin >> N >> M;

    ll tmp1 = 1, tmp2 = M, tmp3 = 1;
    while(tmp1 * tmp1 <= M){
        if (M % tmp1 == 0) {
            tmp2 = M / tmp1;
            if(tmp1 >= N) tmp3 = max(tmp3, tmp2);
            if(tmp2 >= N) tmp3 = max(tmp3, tmp1);
        }
        tmp1++;
    }
    cout << tmp3 << endl;
    return 0;
}

Measured memory_bytes: 256
input = gets.chomp.to_i
ans = 0
#2の倍数かどうかのフラグ
isBinary = false
 
while true do
  #素数の確認は半分で良い
  #素数かどうかのフラグ
  flag = true
  (Math.sqrt(input).to_i + 1).times do |i|
    next if i <= 1
    if input != i && input % i == 0
      #素数でない場合
      flag = false
      break
    end
  end
  
  if flag
    ans = input
    break
  end
  
  #isBinaryがtrueの場合は１つ飛ばしにする
  if isBinary
    input += 2
    next
  end
 
  if input % 2 == 0
    input += 1
    isBinary = true
    next
  end
    
  input += 1
end
 
puts ans

Measured memory_bytes: 1788
/******************************************************************************

                            Online Java Compiler.
                Code, Compile, Run and Debug java program online.
Write your code in this editor and press "Run" button to execute it.

*******************************************************************************/
//2 1 1 3

import java.util.*;

public class Main
{
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int a= sc.nextInt();
	int b = sc.nextInt();
	int c = sc.nextInt();
	int k = sc.nextInt();
	int count =0;
	int res=0;
	
	if(k>0){
	    if(a>k){
	        res+=k;
	    }else{
	        res+=a;
	        k-=a;
	    }
	}
	if(k>0){
	    k-=b;
	}
	if(k>0){
	    if(c>k){
	        res-=k;
	    }else{
	        res-=c;
	        
	    }
	}
	System.out.println(res);
// 	while(k>0){
// 	    count=a;
// 	  System.out.println(k+"a");
// 	    k-=count;
// 	      System.out.println(k+"av");
// 	    k-= b;
// 	      System.out.println(k+"an");
// 	    count= count -c;
// 	      System.out.println(k+"am");
// 	    k-= c;
// 	      System.out.println(k+"ao");
// 	}
// 	     System.out.println(count);

	}
}


Measured memory_bytes: 35772