akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
using ll = long long;
using P = pair<ll,ll>;

template< typename T >
T mod_pow(T x, T n, const T &p) {
  T ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= p;
    (x *= x) %= p;
    n >>= 1;
  }
  return ret;
}

// GCD, LCM
// https://youtu.be/8lm8o8L9Bmw?t=2285
// https://youtu.be/XI8exXVxZ-Q?t=3595
// https://youtu.be/F2p_e6iKxnk?t=843
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}

void solve(long long N, std::vector<long long> A, std::vector<long long> B){
    if(N==1){
        cout << 1 << endl;
        return;
    }
    map<P,ll> mp;
    ll zeroNum = 0;
    for(int i=0;i<N;i++){
        if(A[i] ==0 && B[i] ==0){
            zeroNum++;
            continue;
        }
        if(A[i] ==0){
            mp[P(0,1)]++;
            continue;
        }
        if(B[i] == 0){
            mp[P(1,0)]++;
            continue;
        }
        if((A[i]<0 && B[i] >0) ||(A[i] >0 && B[i] <0)){
            ll g = gcd(abs(A[i]),abs(B[i]));
            mp[P(-(abs(A[i])/g),abs(B[i])/g)]++;
        }else{
            ll g = gcd(abs(A[i]),abs(B[i]));
            mp[P(abs(A[i])/g,abs(B[i])/g)]++;
        }
    }
    ll ans =1ll;
    map<P,bool> already;
    for(auto itr = mp.begin();itr!=mp.end();itr++){
        P p  = itr->first;
        // cerr <<p.first <<", "<< p.second <<"val = "<< itr->second<< endl;
        P np;
        if(p.first<=0){
            np = P(p.second,-p.first);
        }else{
            np = P(-p.second,p.first);
        }
        if(mp.find(np) == mp.end()){
            ans *= mod_pow(2ll,itr->second,MOD);
            ans %= MOD;
        }else{
            //  cerr <<"np"<<np.first <<", "<< np.second <<"val = "<< mp[np]<< endl;
            if(already.find(p) != already.end()){
                // cerr <<"already checked" << endl;
                continue;
            }
            already[p] = true;
            already[np] = true;
            ans = ans * ((mod_pow(2ll,mp[p],MOD) + mod_pow(2ll,mp[np],MOD)-1+MOD)%MOD);
            ans %= MOD;
        }
        // cerr <<"ans="<<ans << endl;
    }
    
    cout << (ans+zeroNum-1+MOD)%MOD << endl;


}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 18840
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int main() {
	scanf("%d%d%d%d", &a, &b, &c, &d);
	if(b <= c || d <= a) {
		printf("0\n");
		return 0;
	}
	if(a <= c && b <= d) {
		printf("%d\n", b - c);
		return 0;
	}
	if(a >= c && b >= d) {
		printf("%d\n", d - a);
		return 0;
	}
	if(a <= c && d <= b) {
		printf("%d\n", d - c);
		return 0;
	}
	if(c <= a && b <= d) {
		printf("%d\n", b - a);
		return 0;
	}
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin>>k>>n;
    ll tot=0;
    for(int i=0;i<=k;i++)for(int j=0;j<=k;j++){
        if(n-i-j>=0&&n-i-j<=k)tot++;
    }
    cout<<tot<<endl;
    return 0;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)


int main()
{
    int N, K;
    cin >> N >> K;

    double ans = 0;
    REP(i, N){
        int count = 0, tmp = i+1;
        while(tmp < K){
            tmp *= 2;
            ++count;
        }
        ans += pow(0.5, count) * 1./N;        
    }
    cout << setprecision(10) << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
def gcd(a, b):

	while b:

		a, b = b, a % b

	return a

n,xs=map(int,input().split())

x=[abs(int(i)-xs) for i in input().split()]

ans=x[0]
for i in range(n):
    ans=gcd(ans,x[i])

print(ans)

Measured memory_bytes: 14224
import sys
N=int(input())

if N==0: print(0),sys.exit()

ans=""
dic=["00","01","10","11"]
a=[0,1,-2,-1]

while N!=0:
    i=N%4
    ans=dic[i]+ans
    N-=a[i]
    N//=4
print(ans if ans[0]=="1" else ans[1:])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef long double ld;


string s;
int N, K;
int dp[2][101][4][2];
ll solve(bool started, int n, int nz, bool smaller){
	if (n == N) return (nz == K)&&started; 
	if (dp[started][n][nz][smaller] != -1)
		return dp[started][n][nz][smaller];
	ll ret = 0;
	if (nz == K)
		ret+= solve(1, n+1, nz, smaller||(s[n]>'0')); //can only put 0
	else if (nz<K){
		ret += solve(started, n+1, nz, smaller||(s[n]>'0')); //put 0
		if (smaller) for(char h = '1'; h<='9'; h++) ret+= solve(1, n+1, nz+1, 1);			
		else {
			for(char h = '1'; h<s[n]; h++)
				ret+= solve(1, n+1, nz+1, 1); //smaller number here, can put w/e on next
			if (s[n]>'0') ret+= solve(1, n+1, nz+1, 0); //put same number
		}
	}
	return dp[started][n][nz][smaller] = ret;
}

int main(){
	cin >> s >> K;
	N = s.size();
	memset(dp, -1, sizeof(dp));
	cout << solve(0, 0, 0, 0) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

//この中では、互いにガチプレイ！
int simurate(vector<int> &F, vector<int> &P) {
    int i, j;
    
    j = 0;
    for (i = 0; i < P.size(); i++) {
        for (; j < F.size(); j++) {
            if (F[j] > P[i]) { break; }
        }
        if (j == F.size()) { break; }
        //F[j]とP[i]を割り当てる
        j++;
    }
    
    //この時点でのiが勝った回数に相当する
    return i;
}

int n;
int p[5000];
int f[5000];

int main() {
    int i, j;
    
    cin >> n;
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> f[i];
    
    vector<int> ans;    //答え（辞書順最大）
    
    vector<int> F;  //女の現在の手札
    rep(i, n) { F.push_back(f[i]); }
    sort(F.begin(), F.end());
    
    rep(i, n) {//p[i]に割り当てるカードを決める
        int index = upper_bound(F.begin(), F.end(), p[i]) - F.begin();
        //F[index]～F[F.size() - 1]はp[i]より強い
        if (index == F.size()) { //どうやっても無理
            index = 0;    //舐めプを考えなければ、最弱を渡せばよい
        }
        
        //とりあえず, p[i]にはF[index]を当てれば勝てるんですが、
        //どのくらい舐めプできますか？
        vector<int> F2;
        for (j = 0; j < F.size(); j++) {
            if (j == index) continue;
            F2.push_back(F[j]);
        }
        vector<int> P;    //男の持ってるカード
        for (j = i + 1; j < n; j++) { P.push_back(p[j]); }
        sort(P.begin(), P.end());
        
        //男カード:P, 女カード:F2のとき、女が何勝できる？(最適解)
        int maxWinCnt = simurate(F2, P);
        
        //じゃあ舐めてかかろう！
        int left = index, right = F.size(), mid;   //[left, right),
                                            //F:ooooxxxx
        while (right - left >= 2) {
            mid = (left + right) / 2;
            
            //p[i]にF[mid]を割り当ててもいいですか？
            vector<int> F3;
            for (j = 0; j < F.size(); j++) {
                if (j == mid) { continue; }
                F3.push_back(F[j]);
            }
            int winCnt = simurate(F3, P);
            
            if (winCnt == maxWinCnt) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        //F[left]を割り当てまーす！
        ans.push_back(F[left]);
        
        //女のカードがなくなっちゃう～
        vector<int> F4;
        for (j = 0; j < F.size(); j++) {
            if (j == left) { continue; }
            F4.push_back(F[j]);
        }
        
        //コピー(値のコピー)
        F = F4;
    }
    
    rep(i, ans.size()) {
        cout << ans[i];
        if (i + 1 < ans.size()) { cout << " "; }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3324
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define PB push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
#define inI(x) scanf("%d",&x)
#define inI2(x,y) scanf("%d %d",&x,&y)
#define inI3(x,y,z) scanf("%d %d %d",&x,&y,&z)
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
int a,b;
int main()
{
    scanf("%d %d",&a,&b);
    printf("%d",(a+b-1)/b);
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns, OverloadedStrings #-}
import Control.Arrow
import Control.Monad.Fix
import Data.Int
import Data.Foldable
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Internal (accursedUnutterablePerformIO)
import qualified Data.Set as S
import System.IO.Unsafe
import Debug.Trace

unew :: VUM.Unbox a => Int -> VUM.IOVector a
unew !n = accursedUnutterablePerformIO $ VUM.unsafeNew n

uread :: VUM.Unbox a => Int -> VUM.IOVector a -> a
uread !i !v = accursedUnutterablePerformIO $ VUM.unsafeRead v i

uwrite :: VUM.Unbox a => Int -> a -> VUM.IOVector a -> VUM.IOVector a
uwrite !i !a !v =
  accursedUnutterablePerformIO $ VUM.unsafeWrite v i a >> return v

uthaw :: VUM.Unbox a => VU.Vector a -> VUM.IOVector a
uthaw !v = accursedUnutterablePerformIO $ VU.unsafeThaw v

ufreeze :: VUM.Unbox a => VUM.IOVector a -> VU.Vector a
ufreeze !v = accursedUnutterablePerformIO $ VU.unsafeFreeze v

uset :: VUM.Unbox a => a -> VUM.IOVector a -> VUM.IOVector a
uset !a !v = accursedUnutterablePerformIO $ VUM.set v a >> return v

solve :: B.ByteString -> B.ByteString -> String
solve !s !t = walk
 where
  toIndex !i !j = j * succ (B.length s) + i
  fromIndex !n = (n `mod` succ (B.length s), n `div` succ (B.length s))

  dp :: VU.Vector Int16
  dp = ufreeze $ fst $ B.foldl'
    ( \(!dp, !i) (!si) -> flip (,) (i + 1) $ fst $ B.foldl'
      ( \(!dp, !j) (!tj) -> flip (,) (j + 1) $ uwrite
        (toIndex (i + 1) (j + 1))
        ( if si == tj
          then uread (toIndex i j) dp + 1
          else max (uread (toIndex (i + 1) j) dp) (uread (toIndex i (j + 1)) dp)
        )
        dp
      )
      (dp, 0)
      t
    )
    (uset 0 $ unew $ succ (B.length s) * succ (B.length t), 0)
    s

  walk = fst $ fix
    ( \(!f) (!acc, (!i, !j)) -> if i == 0 || j == 0
      then (acc, (i, j))
      else if s `B.index` (i - 1) == t `B.index` (j - 1)
        then f (s `B.index` (i - 1) : acc, (i - 1, j - 1))
        else if dp VU.! toIndex (i - 1) j < dp VU.! toIndex i (j - 1)
          then f (acc, (i, j - 1))
          else f (acc, (i - 1, j))
    )
    ([], (B.length s, B.length t))

main = do
  s <- B.getLine
  t <- B.getLine
  putStrLn $ solve s t


Measured memory_bytes: 19452
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,A[128];
map<set<int>,int>M;

int dfs(set<int> st){
    if(st.size()<=1)return 0;
    if(M.count(st))return M[st];
    int res=99;
    r(i,m){
        set<int>S1,S2;
        for(set<int>::iterator it=st.begin();it!=st.end();it++){
            int x=*it;
            if((1<<i)&A[x])S1.insert(x);
            else S2.insert(x);
        }
        if(S1.size()==st.size())continue;
        if(S2.size()==st.size())continue;
        res=min(res,max(dfs(S1),dfs(S2))+1);
    }
    return M[st]=res;
}

int main(){
    while(cin>>m>>n,n){
        M.clear();
        r(i,n){
            string s;
            cin>>s;
            A[i]=0;
            r(j,m)if(s[j]=='1')A[i]|=(1<<j);
        }
        set<int>st;
        r(i,n)st.insert(i);
        cout<<dfs(st)<<endl;
    }
}


Measured memory_bytes: 10488
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>

int main(void) {
	uint32_t D, N;

	scanf("%"PRIu32" %"PRIu32, &D, &N);

	if (D == 0) {
		printf("%"PRIu32, N + N / 100);
	}
	else if (D == 1) {
		printf("%"PRIu32, (N + N / 100) * 100);
	}
	else {
		printf("%"PRIu32, (N + N / 100) * 10000);

	}

	return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("O3")
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld  double
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int>
#define ppp pair<pii,pii>
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define warmup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 3003, mod=1e9+7;
const ll inf=(1e9+11);
ll dp[N][N];

signed main()
{
    warmup

    int n;
    cin>>n;
    int a[n+1],i,j,l,r;
    ll sum=0;
    for(i=1;i<=n;++i)
        cin>>a[i],sum+=a[i];

    for(l=n;l>=1;--l)
    {
        dp[l][l]=a[l];
        for(r=l+1;r<=n;++r)
        {
            if(r-l==1)
                dp[l][r]=max(a[l],a[r]);
            else
                dp[l][r]=max(a[l]+min(dp[l+2][r],dp[l+1][r-1]),a[r]+min(dp[l+1][r-1],dp[l][r-2]));
        }
    }
    cout<<2*dp[1][n]-sum;

    return 0;
}


Measured memory_bytes: 70016
import java.util.*;
public class Main{
    public static void main(String[] args) {
        int n;
        int m;
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        int [] a=new int [m];
        int sum=0;
        for(int i=0;i<m;i++){
            a[i]=sc.nextInt();
            sum+=a[i];
        }
        if(n>=sum){
            System.out.println(n-sum);
        }
        else{
            System.out.println("-1");
        }

    }
}

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

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	for (int i = 1; i <= n-1; ++i)
	{
		for (int j = i+1; j <= n; ++j)
		{
			int a=2,ans=1;
			while ((i*2/a%2)+(j*2/a%2)!=1)
			{
				a*=2;
				++ans;
			}
			if (j==i+1)
			{
				cout<<ans;
			}
			else
			{
				cout<<" "<<ans;
			}
		}
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 512
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++) {
            list.add(sc.nextInt());
        }
      
        int min = 100000000;

        for(int number : list) {
            int count = 0;

            while(number % 2 == 0) {
                number /= 2;
                count++;
            }

            if(min > count) {
                min = count;
            }
        }

        System.out.println(min);
    }
}

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




int main(){
    ll N; cin >> N;
    vector<ll> A(N), B(N), C(N);
    for(int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];
    vector<vector<ll>> DP(N+1, vector<ll>(3, 0));
    for(int i = 0; i < N; i++){
        DP[i+1][0] = A[i] + max(DP[i][1], DP[i][2]);
        DP[i+1][1] = B[i] + max(DP[i][0], DP[i][2]);
        DP[i+1][2] = C[i] + max(DP[i][0], DP[i][1]);
    }
    cout << max(DP[N][0], max(DP[N][1], DP[N][2])) << endl;
    
}

Measured memory_bytes: 8064
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())
    
L=[[0]*N for _ in range(N)]

for i in range(N):
    for j in range(i):
        L[i][j]=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        L[j][i]=L[i][j]

per = list(itertools.permutations(range(1,N+1),N))

ans=0
for path in per:
    for i in range(N-1):
        ans+=L[path[i]-1][path[i+1]-1]
print(ans/len(per))

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

template<class t> void vin(vector<t>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int main() {
    ll n, X;
    cin >> n >> X;
    vector<ll> x(n);
    vector<ll> d(n);
    rep(i, n) {
        cin >> x[i];
        d[i] = abs(x[i] - X);
    }
    ll ans = d[0];
    rep(i, n) {
        ans = __gcd(ans, d[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

int main()
{
	long N, M, P;
	std::vector<std::tuple<long, long, long>> edges;

	std::cin >> N >> M >> P;
	edges.resize(N);
	for (int i = 0; i < M; ++i) {
		long a, b, c;
		std::cin >> a >> b >> c;
		edges.emplace_back(a-1, b-1, c);
	}

	auto bf_edges = edges;
	for (auto& e : bf_edges) {
		std::get<2>(e) = P-std::get<2>(e);
	}
	std::vector<long> d(N);
	std::fill(d.begin(), d.end(), std::numeric_limits<long>::max()/2);
	d[0] = 0;

	for (int i = 0; i < N * 2; ++i) {
		for (const auto& e : bf_edges) {
			if (d[std::get<1>(e)] > d[std::get<0>(e)] + std::get<2>(e)) {
				d[std::get<1>(e)] = d[std::get<0>(e)] + std::get<2>(e);
				if (i >= N - 1 && std::get<1>(e) == N - 1) {
					std::cout << "-1\n";
					return 0;
				}
			}
		}
	}

	std::cout << std::max(0L, -d[N-1]) << "\n";
}


Measured memory_bytes: 720
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#define int  long long int
	#define pb push_back
	#define fe first
    #define lb lower_bound 
    #define ub upper_bound
    #define pii pair<pair<int,int>,pair<int,int> >
	#define se second
	#define endl "\n"
	#define pi pair<int, int>
	#define vi vector<int> 
	#define vvi vector<vi>
    #define bs   binary_search
	#define rep(i,a,b) for(int i=a;i<b;i++)
	#define rep1(i,a,b) for(int i=a;i<=b;i++)	
    #define all(c) (c).begin(),(c).end()
    #define sz(x)       (int)x.size() 
	#define PI 3.14159265358979323846
    
	const int N =1e6;
    
     int mod= 1e9+7;
     
     int dx[4]={0,0,+1,-1};
     int dy[4]={+1,-1,0,0};
   
  
      
     void solve(){
       
        int r;
        cin >>r;
        int ans=3*r*r;
        cout<<ans<<endl;
        
       
       
              
     }
   
   
   
   
      int32_t main() {
	    cool;
	    int t=1;
        //cin>>t;
	    while(t--)
	       solve();
	       
	       
	       return 0;	   
	   }


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
std::string S;

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

    std::cin >> S;

    N = S.size();

    bool exists = S[0] == '1' && S[N - 1] == '0';

    for(int i=0;i<N-1;++i){
        if(S[i] != S[N - 2 - i]){
            exists = false;
            break;
        }
    }

    unless(exists){
        std::cout << -1 << std::endl;
        return 0;
    }

    if(N == 2){
        std::cout << "1 2" << std::endl;
        return 0;
    }

    int root = 1, next = 2;
    for(int i=0;i<N/2;++i){
        std::cout << root << " " << next << std::endl;

        if(S[i] == '1'){
            root = next;
        }

        next += 1;
    }

    while(next <= N){
        std::cout << root << " " << next << std::endl;
        next += 1;
    }
}


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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}


int main() {
  int n,k;
  cin >> n >> k;
  int p[n];
  for (int i=0;i<n;i++){
    cin >> p[i];
  }
  qsort(p, n, sizeof(int), compare_int);
  
  int ans = 0;
  for (int i=0;i<k;i++){
    ans+=p[i];
  }
  cout << ans;
    

  return 0;
}

Measured memory_bytes: 3652
X,Y=map(int,input().split())

def cmb(n,k):
    x,y=1,1
    for i in range(k):
        x = x * (n-i)%mod
        y = y * (k-i)%mod
    return x*pow(y,mod-2,mod)%mod

if (X+Y)%3!=0:
    print(0)
else:
    m=(2*X-Y)//3
    n=(2*Y-X)//3
    if n<0 or m<0:
        print(0)
    else:
        mod=10**9+7
        ans=cmb(n+m,min(n,m))
        print(ans)

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

const int bB = 8;
const int B = 1 << bB;

int up(int x) {
	return (x + (1 << bB) - 1) >> bB;
}

int down(int x) {
	return x >> bB;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q;
	cin >> n >> q;
	const int H = up(n);
	vector<int> bv(H, INT_MAX), v(n, INT_MAX);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com == 0) {
			v[x] = y;
			int p = down(x);
			bv[p] = INT_MAX;
			for (int i = p << bB; i < n && i < (p << bB) + B; i++) {
				bv[p] = min(bv[p], v[i]);
			}
		}
		else {
			y++;
			int res = INT_MAX;
			for (int i = x; i < y && i < (up(x) << bB); i++) {
				res = min(res, v[i]);
			}
			if (up(x) <= down(y)) {
				for (int i = up(x); i < down(y); i++) {
					res = min(res, bv[i]);
				}
				for (int i = down(y) << bB; i < y; i++) {
					res = min(res, v[i]);
				}
			}
			printf("%d\n", res);
		}
	}
	return 0;
}



Measured memory_bytes: 3312
#include<iostream>
#include<string>
#include<math.h>

using namespace std;


string LCS(string a, string b){
	
	int tamLinha = a.length(), tamCol = b.length();
	
	int LCS[tamLinha+1][tamCol+1] = {};
	
	for(int i = 1; i <= tamLinha; i++){
		for(int j = 1; j <= tamCol; j++){
			if(a[i-1] == b[j-1])
				LCS[i][j] = 1 + LCS[i-1][j-1];
			else
				LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);
		}
	}
	//achar a LCS
	if(LCS[tamLinha][tamCol] == 0)
		return "";
	else{
		int tamLCS = LCS[tamLinha][tamCol];
		char palavra[tamLCS+1];
		palavra[tamLCS] = '\0';
		
		while(tamLCS > 0 && tamLinha > 0 && tamCol > 0){
			if((LCS[tamLinha - 1][tamCol] == LCS[tamLinha][tamCol - 1]) && LCS[tamLinha - 1][tamCol] < LCS[tamLinha][tamCol]){
				palavra[tamLCS-1] = a[tamLinha-1];
				tamLCS--;
				tamLinha--;
				tamCol--;
			}
			else if(LCS[tamLinha][tamCol] == LCS[tamLinha - 1][tamCol]){
				tamLinha--;
			}
			else if(LCS[tamLinha][tamCol] == LCS[tamLinha][tamCol - 1]){
				tamCol--;
			}

			
		} 
		
		return palavra;
	}
}

int main(){

	string A, B, C;
	
	cin>>A>>B;
	
	cout<<LCS(A, B)<<endl;
	

return 0;
}


Measured memory_bytes: 35456
A, B, K = map(int, input().split())

while True:
    if K<=0:
        break
    if A % 2 == 1:
        A -= 1
    t = A//2
    A -= t
    B += t
    K -= 1
    
    if K<=0:
        break
    if B % 2 == 1:
        B -= 1
    t = B//2
    B -= t
    A += t
    K -= 1
        
print(A, B)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int a,b,c,sum=0;
int main(){
	scanf("%d %d %d",&a,&b,&c);
  	for(int i=min(a,b);i>=1;i--){
      if(a%i==0&& b%i==0)
      	sum++;
    if(sum==c){
    	 printf("%d\n",i);
      return 0;
    }
     
    }
 
 
}

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

int main(){
  int n;
  long long int a[300];
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  bool flag=true;
  int c=0;
  
  do{
    for(int i=0;i<n;i++){
      if(a[i]%2==0) a[i]=a[i]/2;
      else flag=false;
    }
    if(flag) c++;
  }while(flag);

  cout<<c;

}


Measured memory_bytes: 3484
#!/usr/bin/env python
# -*- coding: utf-8 -*-

a = raw_input()
b = a.split()
c = [ i.lower() for i in b ]
e = {}
h = {}
for d in c:
  if d not in e:
    h[d] = len(d)
    e[d] = 1
  else:
    e[d] += 1
f = [ (v,k) for k,v in e.items() ]
f.sort()
f.reverse()
maxnum = f[0][0]
for g in f:
  if g[0] != maxnum:
    break
  print g[1],
i = [ (v,k) for k,v in h.items() ]
i.sort()
i.reverse()
maxnum = i[0][0]
for j in i:
  if j[0] != maxnum:
    break
  print j[1],

Measured memory_bytes: 4248
import collections as coll
n=int(input())
a=list(map(int,input().split()))
if a.count(0)>1:
    print('0')
    exit()
x=10**9+7
f=0
s=coll.defaultdict(int)
for i in range(n):
    if n%2:
        if a[i]%2: f=1
    else:
        if a[i]%2==0: f=1
    s[a[i]]+=1
    if s[a[i]]>2: f=1
    if f==1:
        print('0')
        exit()
ans=1
for i in range(1,n//2+1): ans=ans*2%x
print(ans)

Measured memory_bytes: 14820
#include <stdio.h>
#define MAX 101
#define WHITE 1
#define GRAY 2
#define BLACK 3

typedef struct{
  int tyo, de, list[MAX], color, stime, etime;
} node;

int n, time, tree[MAX][MAX] = {};

void df(node *);
void go(int, node *);

int main() {
  int i, j;
  node node[MAX];

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    scanf("%d %d", &node[i].tyo, &node[i].de);
    for(j = 0 ; j < node[i].de; j++){
      scanf("%d",&node[i].list[j]);
      tree[node[i].tyo][node[i].list[j]] = 1;
    }
  }

  df(node);

  for(i = 0 ; i < n ; i++) {
    printf("%d %d %d\n",node[i].tyo,node[i].stime,node[i].etime);
  }

  return 0;
}

void df(node *node) {
  int i;

  for(i = 0 ; i < n ; i++) {
    node[i].color = WHITE;
  }

  time = 0;

  for(i = 0 ; i < n ; i++){
    if(node[i].color == WHITE) go(i, node);
  }

}

void go(int x, node *node)
{
  int i, j, in;

  node[x].color = GRAY;
  node[x].stime = ++time;

  for(i = 0; i < node[x].de; i++){
    for(j = 0; j < n ; j++){
      if(node[x].list[i] == node[j].tyo) in = j;
    }
    if(tree[node[x].tyo][node[x].list[i]] == WHITE && node[in].color == WHITE) {
      go(in, node);
    }
  }

  node[x].color = BLACK;
  node[x].etime = ++time;

}



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

int main() {
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s.at(i);
  }
  priority_queue<pair<int, int>> q0, q1;
  for (int i = 0; i < n; i++) {
    int m = 0, t = 0;
    for (char c : s.at(i)) {
      if (c == '(') {
        t++;
      } else {
        t--;
        m = min(m, t);
      }
    }
    if (t >= 0) {
      q0.emplace(m, t);
    } else {
      q1.emplace(m - t, -t);
    }
  }
  int k0 = 0, k1 = 0;
  while (!q0.empty()) {
    auto x = q0.top();
    q0.pop();
    int m = x.first, t = x.second;
    if (k0 + m < 0) {
      cout << "No" << endl;
      return 0;
    }
    k0 += t;
  }
  while (!q1.empty()) {
    auto x = q1.top();
    q1.pop();
    int m = x.first, t = x.second;
    if (k1 + m < 0) {
      cout << "No" << endl;
      return 0;
    }
    k1 += t;
  }
  if (k0 == k1) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 42524
#include <iostream>

using namespace std;

int main(){
    int N, M;
    cin >> N >> M;

    const int NMMAX = 50;
    int A[NMMAX], B[NMMAX];

    for(int i=0; i < M; i++){
        cin >> A[i] >> B[i];
    }

    int road[NMMAX];
    for (int i = 0; i < N; i++){
        road[i] = 0;
    }

    for (int i = 0; i < M; i++){
        road[A[i] - 1] += 1;
        road[B[i] - 1] += 1;
    }

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

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define inf 1000000000

int *a, *ans, q;

void open(int i){
//	printf("open(%d)\n", i + 1);
	a[i]--;
	ans[q] = i;
	q++;
}

int main(){
	int N, K, i, j;
	scanf("%d%d", &N, &K);
	a = (int *)malloc(sizeof(int) * N);
	ans = (int *)malloc(sizeof(int) * 10000);
	q = 0;
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
	}
	int maxa, theni;
	for(i = 0, maxa = -1, theni = 0; i < N; i++){
		if(maxa < a[i]){
			maxa = a[i];
			theni = i;
		}
	}
	open(theni);
	int now = theni, mina, thenj;
	for(i = 0; i <= K; i++){
		for(j = 0, mina = inf, thenj = 0; j < N; j++){
			if(j != now && mina > a[j]){
				mina = a[j];
				thenj = j;
			}
		}
//		printf("thenj = %d\n", thenj);
		if(a[thenj] > 0){
			for(j = 0; j < N; j++){
				if(j != now && j != thenj){
					open(j);
				}
			}
			open(thenj);
			now = thenj;
		}
		else{
			printf("-1\n");
			return 0;
		}
/*		printf("a:\n");
		for(j = 0; j < N; j++){
			printf("%d ", a[j]);
		}
		printf("\n");
*/	}
	printf("%d\n", q);
	for(i = 0; i < q; i++){
		printf("%d ", ans[i] + 1);
	}
	printf("\n");
	return 0;
}

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

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define F first
#define S second
#define pb push_back
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ld long double
#define int long long

void SOLVE(){
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(all(a));
    int ans = 0;
    for (int i = 0; i < n - k; i++){
        ans += a[i];
    }
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    int Q = 1;
    //cin >> Q;
    while (Q--){
        SOLVE();
    }

    return 0;
}


Measured memory_bytes: 1792
n,k = map(int,input().split())
li = list(map(int,input().split()))
mod = 10**9 +7
 
ans_1 = 0
ans_2 = 0
for i in range(n):
  for j in range(i+1,n):
    if li[i] > li[j]:
      ans_1+= 1
for i in range(n):
  for j in range(n):
    if li[i] > li[j]:
      ans_2 += 1
ans = k*ans_1%mod + (k*(k-1)//2)%mod*ans_2%mod
print(int(ans%mod))

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

int main(void){
    int n, T;
    cin >> n >> T;
    
    int min_t = 1000001;
    vector<int> c(n), t(n);
    rep(i, n){
        cin >> c.at(i) >> t.at(i);
        if(t.at(i) <= T && min_t > c.at(i)){
            min_t = c.at(i);
        }
    }
    
    string s = "TLE";
    if(min_t == 1000001){
        cout << s << endl;
    } else {
        cout << min_t << endl;
    }
    return 0;
}

Measured memory_bytes: 256
s = str(input())
k = int(input())
kouho = [s]

for i in range(len(s)):
    for plus in range(k+1):
        st = s[i:i + plus]
        kouho.append(st)
so = list(sorted(set(kouho)))
if '' in so:
    so.remove('')
    
print(so[k-1])

Measured memory_bytes: 5040
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1<<30;
const long long LINF = 1LL << 60;
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    cin.tie(nullptr) ;
    ios::sync_with_stdio(false) ;

    int n;
    cin >> n;

    vector<P> v(n);
    rep(i, n) cin >> v[i].first >> v[i].second;
    rep(i, n) {
        int cnt = 0;
        while (i < n && v[i].first == v[i].second){
            cnt++;
            ++i;
        }
        if(cnt >= 3){
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#include<string>
#include<vector>
#include<stdbool.h>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<set>
#include<string>
typedef long long ll;
using namespace std;

int main() {
	string S;
	int num = 0;
	char a[27] = "abcdefghijklmnopqrstuvwxyz";
	cin >> S;
	set<char>s;
	sort(S.begin(), S.end());
	for (int i = 0;i<S.size();i++) {
		s.insert(S[i]);
	}
	for (int i = 0;i < 27;i++) {
		for (auto itr : s) {
			if (a[i] != itr) {
				num++;
			}
		}
		if (num == s.size()) {
			if (a[i] == NULL) {
				cout << "None\n";
				return 0;
			}
			else {
				cout << a[i] << endl;
				return 0;
			}
		}
	    else num = 0;

	}
	
	return 0;
}

Measured memory_bytes: 512
N = int(input())

if N < 10:
  print(N)
elif N < 100:
  print(9)
elif N < 1000:
  print(N-100+1+9)
elif N < 10000:
  print(909)
elif N < 100000:
  print(N-10000+1+909)
elif N == 100000:
  print(90909)

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

int main(void){
    int N, M;
    cin >> N >> M;
    int Nin[M], Rin[M];
    for (int i = 0; i < M; i++){
    cin >> Nin[i] >> Rin[i];
    }
    int Nmax = Nin[0], Rmin = Rin[0];
    for (int j = 0; j < M; j++){
        if (Nin[j] > Nmax) Nmax = Nin[j];
        if (Rin[j] < Rmin) Rmin = Rin[j];
    }
    int temp = Rmin - Nmax + 1;
    if (temp > 0) cout << temp << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>

using namespace std;


int main(){

	string data,data_copy;
	int m, h;


	for (;;){
		cin >> data;
		if (data == "-")break;
		data_copy = data;
		cin >> m;
		
		for (int i = 0; i < m; i++){
			cin >> h;

			for (int j = 0; j < data.length(); j++){
				if ((j + 1 - h) <= 0){
					data[data.length() - h + j] = data_copy[j];
			
				}
				else{
					data[j - h] = data_copy[j];
							}


			


			}//data?????¨????????????
			for (int j = 0; j < data.length(); j++){
				data_copy[j] = data[j];
			}


		}//?????£??????????????°???????????????
		cout << data << endl;

}





	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdio>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define int long long
using namespace std;

signed main() {
    string str;
    cin >> str;
    rep (i, 3) {
        if (str[i] == '1') {
            str[i] = '9';
        } else if (str[i] == '9') {
            str[i] = '1';
        }
    }
    cout << str << endl;
    return 0;
}


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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int nw[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};
int nh[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};

int main(){
	int H,W;
	vector<string> s;

	cin >> H >> W;
	s.resize(H);
	for(int i = 0; i < H; i++)
		cin >> s[i];

	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(s[i][j] == '#')
				cout << s[i][j];
			else{
				int num = 0;
				for(int k = 0; k < 8; k++){
					int h = i+nh[k];
					int w = j+nw[k];
					if(h < 0 || w < 0 || h >= H || w >= W)
						continue;
					if(s[i+nh[k]][j+nw[k]] == '#')
						num++;
				}
				cout << num;
			}
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,count=0;cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++)cin>>a.at(i);
  
  for(int i=0;i<N;i++)
    if(i==a.at(a.at(i)-1)-1)count++;
  
  cout<<count/2<<endl;
}



Measured memory_bytes: 640
n,m=map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
      return 0
    else:
      if par[x] > par[y]:
        x,y = y,x
      par[x] += par[y]
      par[y] = x
def size(x):
    return -par[find(x)]

max_size=0
for _ in range(m):
  a,b=map(int,input().split())
  unite(a,b)
  
print(-min(par))

Measured memory_bytes: 74356
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let mut x: i32 = read();
    let mut a: Vec<i32> = (0..n).map(|_| read()).collect();

    a.sort();

    let mut i = 0;

    for a_i in a {
        if a_i <= x {
            x -= a_i;
            i += 1;
        }
    }

    let ans = i - if i == n && x > 0 { 1 } else { 0 };

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
n = int(input())
line = input().split()

length = [int(line[i]) for i in range(n)]
length.sort(reverse = True)

count = 0

for i in range(n-2):
  long = length[i]
  
  for j in range(i+1,n-1):
    middle = length[j]
    if middle == long:
      continue
    if middle*2 <= long :
      break
      
    for k in range(j+1,n):
      short = length[k]
      if short == middle:
        continue
      if short + middle > long:
        count += 1
      else:
        break

print(count)

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

int abcd(int n) {
  int sum = 0;
  while (n%2 == 0) { 
    sum ++;
    n /= 2;
  }
  return sum;
}

int main(){
long long int a,b[3010],c;
cin >> a;

  for(int i=0;i<a;i++)
    cin >> b[i];
  
  c =0;
  
  for(int i=0;i<a;i++){
    c += b[i]-1;
  }
  
  cout << c << endl;
}


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

int main(){
  string a;
  cin >> a;
  int count = 0;
  for (char c : a){
    count += int(c)-48;
  }
  if (count%9==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3748
#include<bits/stdc++.h>
using namespace std;
#define nl '\n' 
#define FLASH ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pii pair <int,int>
ll m=998244353;
int main()
{
	FLASH
	int n,k;cin>>n>>k;
	int s[k+1],e[k+1];
	for(int i=0;i<k;i++)cin>>s[i]>>e[i];
	int dp[n+1]={0};
	int prefix[k+1]={0};
	dp[1]=1;
	prefix[1]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<k;j++){
			if(i<s[j])
				continue;
			int left=s[j];
			int right=min(e[j],i-1);
			int val=(prefix[i-left]-prefix[i-right-1]+m)%m;
			dp[i]=(dp[i]+val)%m;
		}
		prefix[i]=(dp[i]+prefix[i-1])%m;
	}
	cout<<dp[n];
}

Measured memory_bytes: 4372
#include <bits/stdc++.h>
//#include "atcoder/all"
using namespace std;
typedef long long ll;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
using pii = pair<int, int>;
const ll mod = 1e9 + 7;

vector<pair<long long, long long> > prime_factorize(long long N) {
  vector<pair<long long, long long> > res;
  for (long long a = 2; a * a <= N; ++a) {
    if (N % a != 0) continue;
    long long ex = 0;  // 指数

    // 割れる限り割り続ける
    while (N % a == 0) {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1) res.push_back({N, 1});
  return res;
}

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

  using pll = pair<ll, ll>;

  vector<pll> aa = prime_factorize(a);

  vector<pll> bb = prime_factorize(b);

  ll ans = 1;

  map<ll, ll> mp;

  for (int i = 0; i < aa.size(); i++) {
    mp[aa[i].first]++;
  }
  for (int i = 0; i < bb.size(); i++) {
    mp[bb[i].first]++;
  }

  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it->second == 2) {
      ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 3648
from fractions import gcd

a, b, c, d = map(int, input().split())
cx = b//c - (a-1)//c
dx = b//d - (a-1)//d
lcm = (c * d) // gcd(c, d)
lcmx = b//lcm - (a-1)//lcm
print(b-a+1-cx-dx+lcmx)

Measured memory_bytes: 5048
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

int n, m;
char a[10005];
vector<int> v[10005];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",a);
		int i, j, k;
		int level=0;
		for(i=0;i<10000;i++)
			v[i].clear();

		for(i=0;a[i];i++)
		{
			if(a[i] == '[')
			{
				level++;
				k=0;
			}
			else if(a[i] == ']')
			{
				if(a[i-1] >= '0' && a[i-1] <= '9')
				{
					k = (k+1)/2;
					v[level-1].push_back(k);
					k=0;
				}
				else
				{
					k=0;
					sort(v[level].begin(), v[level].end());
					for(j=0;j<(v[level].size()+1)/2;j++)
					{
						k+=v[level][j];
					}
					v[level-1].push_back(k);
					v[level].clear();
				}
				level--;
			}
			else
			{
				k*=10;
				k+=(a[i]-'0');
			}
		}
		printf("%d\n",v[0][0]);
	}
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

bool k1[11], k2[105], k3[1020];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >>n >>s;
	
	rep(i, n){
		int d = s[i] - '0';
		rep(j, 100) if(k2[j]) k3[j*10+d] = true;
		rep(j, 10)  if(k1[j]) k2[j*10+d] = true;
		k1[d] = true;
	}
	cout << count(k3, k3+1001, true) <<"\n";
	return 0;
}


Measured memory_bytes: 384
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

def solve():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ruia, ruib = [0], [0]
    for i in range(n): ruia.append(a[i]+ruia[i])
    for i in range(m): ruib.append(b[i]+ruib[i])
    ans = 0
    j = m
    for i in range(n+1):
        if ruia[i] > k:
            break
        while(ruib[j]>k-ruia[i]):
            j -= 1
        ans = max(ans, i+j)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 48872
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int MAX=1e1;
int sgn(double x)
{
    if (fabs(x)<eps) return 0;
    if (x<0) return -1;
    else return 1;
}
struct Point
{
    double x,y;
    Point(){}
    Point(double _x,double _y){
        x=_x;y=_y;
    }
    Point operator -(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator ^(const Point &b)const{
        return x*b.y - y*b.x;
    }
    double operator *(const Point &b)const{
        return x*b.x - y*b.y;
    }
    void transXY(double B){
        double tx=x,ty=y;
        x=tx*cos(B) - ty*sin(B);
        y=tx*sin(B) + ty*cos(B);
    }
};
double CalcArea(Point p[],int n)
{
    double res=0;
    for (int i=0; i<n; i++) {
        res+=(p[i]^p[(i+1)%n])/2;
    }
    return fabs(res);
}

Point p[MAX];
int main(void) {
    //freopen("/Users/mac/Desktop/C++?¨????/Computational_Geometry/Computational_Geometry/test.txt", "r", stdin);
    int n;
    scanf("%d\n",&n);
    for (int i=0; i<n; i++) {
        scanf("%lf%lf\n",&p[i].x,&p[i].y);
    }
    printf("%.1lf\n",CalcArea(p, n));
    return 0;
}

Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<ll,ll> pint;

int a[101],s[101];
int main(){
    int n,m,bi;
    cin>>n>>m;
    rep(i,m) cin>>a[i];
    rep(i,m){
        rep(j,n){
            cin>>bi;
            if(bi==a[i]) ++s[j];
            else ++s[a[i]-1];
        }
    }
    rep(i,n) cout<<s[i]<<endl;
    return 0;
}


Measured memory_bytes: 3112
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n = ni()
d = list(li())

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += d[i] * d[j]

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define setbits __builtin_popcount 
#define big 1e9+7;
using namespace std;
ll n,k,m = big;
string s;
ll height[100005],dp[100005];
int main()
{
	IOS;
	ll a,b;
	cin>>n>>k;
	for (int i = 0; i < n; ++i)
	{
		cin>>height[i];
		dp[i] = big;
	}
	dp[0] = 0;
	for (int i = 1; i < n; ++i)
		for (int j = (i-k)*(i > k-1); j < i; ++j)
			dp[i] = min(dp[j]+abs(height[j] - height[i]),dp[i]);
	cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    if(K > (N-1)*(N-2)/2) cout << -1 << endl;
    else{
        cout << (N-1)*(N-2)/2 - K + (N-1) << endl;
        for(int i=2; i<=N; i++){
            cout << 1 << " " << i << endl;
        }

        bool ok = true;
        int cnt = 0;
        for(int i =2 ; i<=N; i++){
            for(int j=i+1; j<=N; j++){
                if(cnt >= (N-1)*(N-2)/2 - K){
                    ok = false;
                    break;
                } 
                cout << i <<" " << j << endl;
                cnt++;              
            }
            if(!ok) break;
        }
    }
    return 0;
}   

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long ll;


int main()
{
	int n;
	cin>>n;
	ll ans = 0;
	for(int i = 0; i < n; i ++){
		int left,right;
		cin>>left>>right;
		ans += (right - left) + 1;
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3180
#include <cstdio>
#include <set>

using namespace std;

bool is_valid(const set<int> &D, int N) {
    while (N) {
        if (D.count(N%10)) return false;

        N /= 10;
    }
    return true;
}

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

    set<int> D;
    for (int i=0; i<K; ++i) {
        int d;
        scanf("%d", &d);
        D.insert(d);
    }

    while (!is_valid(D, N))
        ++N;

    printf("%d\n", N);
    return 0;
}


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

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			String S = in.next();
			int countA = 0;
			int countB = 0;
			int countC = 0;
			for(int i = 0; i < S.length(); i++) {
				if(S.charAt(i) == 'a') {
					countA++;
				}else if(S.charAt(i) == 'b'){
					countB++;
				}else {
					countC++;
				}
			}
			if(countA * countB * countC == 1) {
				out.println("Yes");
			}else {
				out.println("No");
			}
		}
	}
	
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

	}
}


Measured memory_bytes: 21460