akhauriyash/Code-Regression huggingface dataset:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(n,k):
        if n < k:
            return 0
        return f[n]*inv[k]*inv[n-k]%mod
    n,k = LI()
    a = LI()
    a.sort()
    f = [1]
    N = 10**6
    for i in range(1,N+1):
        f.append(f[-1]*i%mod)
    inv = [None]*(N+1)
    inv[N] = pow(f[N],mod-2,mod)
    for i in range(1,N+1)[::-1]:
        inv[i-1] = inv[i]*i%mod
    ans = 0
    d = defaultdict(lambda : 1)
    for i in a:
        l = bisect.bisect_right(a,i)-d[i]
        r = n-l-1
        d[i] += 1
        ans += i*(comb(l,k-1)-comb(r,k-1))%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 117484
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <iterator>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;
typedef ostringstream OSS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define DRANGE( c, p ) (c).begin(), (c).begin() + p, (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl
#define DEBUG( x ) cerr << __FILE__ << ":" << __LINE__ << ": " << #x << " = " << ( x ) << endl

string func_j( string msg )
{
	rotate( DRANGE( msg, msg.size() - 1 ) );
	return msg;
}

string func_c( string msg )
{
	rotate( DRANGE( msg, 1 ) );
	return msg;
}

string func_e( string msg )
{
	const int L = msg.size();
	const int mid = L / 2;
	string left = msg.substr( 0, mid );
	string right = msg.substr( L % 2 ? mid + 1 : mid );
	return right + ( L % 2 ? string( 1, msg[ mid ] ) : "" ) + left;
}

string func_a( string msg )
{
	reverse( ALL( msg ) );
	return msg;
}

string func_p( string msg )
{
	REP( i, 0, msg.size() )
	{
		if ( isdigit( msg[i] ) )
		{
			msg[i] = ( ( msg[i] - '0' ) + 10 - 1 ) % 10 + '0';
		}
	}
	return msg;
}

string func_m( string msg )
{
	REP( i, 0, msg.size() )
	{
		if ( isdigit( msg[i] ) )
		{
			msg[i] = ( ( msg[i] - '0' ) + 1 ) % 10 + '0';
		}
	}
	return msg;
}

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

	map< char, string (*)( string ) > funcs;
	funcs[ 'J' ] = func_j;
	funcs[ 'C' ] = func_c;
	funcs[ 'E' ] = func_e;
	funcs[ 'A' ] = func_a;
	funcs[ 'P' ] = func_p;
	funcs[ 'M' ] = func_m;

	int n;
	cin >> n;

	REP( case_num, 0, n )
	{
		string order, message;
		cin >> order >> message;

		for ( int i = order.size() - 1; 0 <= i; i-- )
		{
			message = funcs[ order[i] ]( message );
		}

		cout << message << endl;
	}

	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for(int i =0 ; i < n; ++i)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair < int, int >
typedef vector<int> vi;
typedef  long long ll;
const int mod =1e9+7;
const int N = (int)2e5 + 5;

void solve(){
	ll n,k;
	cin>>n>>k;
	ll a[n],b[n],sum=0,ans=0;
	bool ok=0;
	vector<pair<ll,ll> >v;
	rep(i,n){
		cin>>a[i]>>b[i];
		v.pb(mp(a[i],b[i]));
	}
	sort(all(v));
	rep(i,sz(v)){
		sum+=v[i].S;
		if(sum>=k && !ok){
			ok=1;
			ans=v[i].F;
		}
	}
	cout<<ans;
	
}

int main(){
	Red;
	int t=1;
	// cin>>t;
	while(t--)
	solve();
	return 0;
}

Measured memory_bytes: 3568
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

long long int D[110000];
int memo[110000];
vector<P> E[110000];
long long int ans[210000];
bool used[110000];

int main(){
	int N, M;
	cin >> N >> M;
	vector<P> v;
	for(int i = 1; i <= N; i++){
		cin >> D[i];
		v.push_back(P(D[i], i));
	}
	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		E[u].push_back(P(v, i));
		E[v].push_back(P(u, i));
	}
	sort(v.begin(), v.end());
	for(P p : v){
		int pos = p.second;
		if(used[pos]){
			continue;
		}
		int les;
		P e;
		bool flag = true;
		for(P ed : E[pos]){
			int to = ed.first;
			if(D[to] <= D[pos]){
				flag = false;
				les = to;
				e = ed;
			}
		}
		if(flag){
			cout << -1 << endl;
			return 0;
		}
		if(memo[les] == 0){
			memo[pos] = 1;
			memo[les] = -1;
			used[les] = true;
		}else if(memo[les] == 1){
			memo[pos] = -1;
		}else{
			memo[pos] = 1;
		}
		ans[e.second] = D[pos];
	}
	for(int i = 1; i <= N; i++){
		if(memo[i] == 1){
			cout << "B";
		}else{
			cout << "W";
		}
	}
	cout << endl;
	for(int i = 0; i < M; i++){
		if(ans[i] == 0){
			cout << (int)1e9 << endl;
		}else{
			cout << ans[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 19056
import java.util.*;
public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong();
      long b = sc.nextLong();
      long c = sc.nextLong();
      long cnt = 0;
      while(a%2==0&&b%2==0&&c%2==0){
        if(a==b&&b==c){
      	  System.out.println(-1);
          return;
        }
        long s = a;
        long t = b;
        long u = c;
      	a = (t+u)/2;
        b = (s+u)/2;
        c = (s+t)/2;
        cnt++;
      }
      System.out.println(cnt);
    }
}


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

// @author: pashka

int get_index(vector<int> p) {
    int n = p.size();
    vector<bool> z(n);
    int ans = 0;
    vector<int> fact(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) {
        fact[i] = fact[i - 1] * i;
    }
    for (int i = 0; i < n; i++) {
        int x = p[i];
        for (int j = 0; j < x; j++) {
            if (!z[j]) ans += fact[n - 1 - i];
        }        
        z[x] = true;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);

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

    int ai = get_index(a);
    int bi = get_index(b);
    cout << abs(ai - bi);

    return 0;
}

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

#define ll long long int

int main(){
    string s,ss;
    cin >> s >> ss;
    int sum = 0;
    for(int i=0;i<s.size();i++)
        sum += s[i] == ss[i];
    cout << sum << '\n';

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>

int num[10000];
int main( void ) 
{
 
    int n;
    scanf( "%d", &n );
    
    int i, j;

    int cnt = n;
    for( i=0; i<n; i++ ) {
        scanf( "%d", &num[i] );
    }
    for( i=0; i<n; i++ ) {    
        if( 2 == *(num+i) ) { continue; }
        
        if( 0 == *(num+i)%2 ) {
            cnt--;
        } else {
            int max = sqrt( num[i] );
            for( j=3; j<=max; j+=2 ) {
                if( 0 == *(num+i)%j ) {
                    cnt--;
                    break;
                }
            }
        }
    }
     
    printf( "%d\n", cnt );
    
    return 0;
}

Measured memory_bytes: 628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoderPre
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            if (N[0] - N[1] > N[2])
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(N[2]-(N[0]-N[1]));
            }
            

            
        }

    }
}



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

#define rep(i,n) for(int i=0;i<(n);++i)
#define in(v) if (scanf("%lld", &v)<1);

int main() {
  ll N; in(N);

  ll A[N];
  rep(i, N)
    in(A[i]);

  ll sum = 0;
  rep(i, N) {
    ll b; in(b);
    if (A[i] > b)
      sum -= A[i] - b;
    else if (A[i] < b)
      sum += (b - A[i])/2;
  }
  if (sum>=0)
    printf("Yes\n");
  else
    printf("No\n");

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
ll gcd(ll a, ll b){
  if(b==0) return a;
  else gcd(b,a%b);
}
ll lcm(ll a, ll b){
  return a/gcd(a,b)*b;
}
int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  ll sumb = b-b/c-b/d+b/lcm(c,d);
  ll suma = (a-1)-(a-1)/c-(a-1)/d+(a-1)/lcm(c,d);
  
  cout <<sumb-suma << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <iomanip>
#include <iostream>
#include <map>

using namespace std;

const int CMax = 100005;

int main()
{
    int h, a;
    scanf("%d %d", &h, &a);
    printf("%d\n", (h / a) + (h % a > 0 ? 1 : 0));
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func solution(h, w int) int {
	if h == 1 || w == 1 {
		return 1
	}
	return (h*w + 1) / 2
}

func main() {
	var h, w int
	fmt.Scan(&h, &w)
	fmt.Println(solution(h, w))
}


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

using namespace std;

int ans, n, m, K;
int a[233], b[233], c[233], d[233];

vector<int> A;

void dfs(int nw, int lst) {
  if (nw >= n) {
    int sum = 0;
    for (int i = 1; i <= K; i++) {
      if (A[b[i] - 1] - A[a[i] - 1] == c[i]) sum += d[i];
    }
    ans = max(ans, sum);
    return;
  }
  for (int i = lst; i <= m; i++) {
    A.push_back(i);
    dfs(nw + 1, i);
    A.pop_back();
  }
}

int main() {
  scanf("%d%d%d", &n, &m, &K);
  for (int i = 1; i <= K; i++) scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);
  dfs(0, 1);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 3816
import sys
import bisect
MAX_INT = int(10e12)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
N = len(s)
ans = ["Yes","No"]
f = 0
for i in range(N):
  if i%2 == 0:
    if s[i] == "R" or s[i] == "U" or s[i] == "D":
      continue
    else:
      f = 1
  else:
    if s[i] == "L" or s[i] == "U" or s[i] == "D":
      continue
    else:
      f = 1

print(ans[f])

Measured memory_bytes: 38384
#include<stdio.h>
#include<string.h>
int main()
{
   char S[100];
   scanf("%s",&S);
   int d=strcmp(S,"Sunny");
   if(d==0)
    printf("Cloudy\n");
   int e=strcmp(S,"Cloudy");
   if(e==0)
    printf("Rainy\n");
    int f=strcmp(S,"Rainy");
   if(f==0)
    printf("Sunny\n");
    return 0;
}


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

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

    vector<int> a1(n);
    vector<int> a2(n);

    int i,j;

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

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

    int tmp, max = 0;

    for(i=0; i<n; i++) {
        tmp = 0;
        for(j=0; j<=i; j++) {
            tmp += a1[j];
        }
        for(j=i; j<n; j++) {
            tmp += a2[j];
        }

        if(max < tmp) {
            max = tmp;
        }
    }

    cout << max << endl;


}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        System.out.println(new Main().calc(n));

    }

    public double calc(int n){
        int odds = 0;
        if(n % 2 == 0){
            odds = n / 2;
        }else{
            odds = (int)(n / 2) + 1;
        }
        return (double)odds / n;
    }
}


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

class Dice{
public:
	int m_t, m_s, m_e, m_w, m_n, m_b;
	Dice(int a[6]){
		m_t = a[0];
		m_s = a[1];
		m_e = a[2];
		m_w = a[3];
		m_n = a[4];
		m_b = a[5];
	}
	~Dice(){}
	void south(){
		int tmp = m_t;
		m_t = m_n;
		m_n = m_b;
		m_b = m_s;
		m_s = tmp;
	}
	void east(){
		int tmp = m_t;
		m_t = m_w;
		m_w = m_b;
		m_b = m_e;
		m_e = tmp;
	}
	void west(){
		int tmp = m_t;
		m_t = m_e;
		m_e = m_b;
		m_b = m_w;
		m_w = tmp;
	}
	void north(){
		int tmp = m_t;
		m_t = m_s;
		m_s = m_b;
		m_b = m_n;
		m_n = tmp;
	}
};

int main(){
	int a[6];
	for (int i = 0; i < 6; i++) cin >> a[i];
	Dice k(a);
	int q;
	cin >> q;
	for (int i = 0; i < q; i++){
		int a, b;
		cin >> a >> b;
		for (int j = 0; j < 4; j++){
			k.north();
			if (k.m_t == a) break;
		}
		for (int j = 0; j < 4; j++){
			k.west();
			if (k.m_t == a) break;
		}
		k.north();
		while (k.m_t != b){
			k.west();
		}
		k.south();
		cout << k.m_e << endl;
	}
}


Measured memory_bytes: 3104
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>

using namespace std;

int main(void){
    int N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> p(N);
    for(int i = 0; i < N; i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin(), p.end());
    long long ans = 0;
    for(int i = 0; i < N; i++){
        if(p[i].second < M){
            ans += p[i].first * p[i].second;
            M -= p[i].second;
        }else{
            ans += p[i].first * M;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll ans=0;
	
	int n,m; cin >> n >> m;
	//vector<int> a(m); rep(i,m) cin >> a[i];
	
	vector<ll> dp(n+1,0);
	
	rep(i,3){
		if(i+1!=n && i+1!=m) cout << i+1 << endl;
	}
	
	//cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#define min(a,b) (a<b?a:b)
using namespace std;


int main()
{
	int n;
	cin >> n;
	string str;
	cin >> str;
	int cnt = 0;
	vector<int> b, w;
	int black = 0, white = 0;
	for (int i = 0; i < n; i++)
	{
		if (str[i] == '#') black++;
		else white++;
		b.push_back(black);
		w.push_back(white);
	}
	cnt = min(black, white);
	cnt = min(cnt, w[n - 1]);
	for (int i = 1; i < n; i++)
	{
		cnt = min(cnt, b[i - 1] + w[n - 1] - w[i - 1]);
	}
	cout << cnt;
	system("pause");
	return 0;
}

Measured memory_bytes: 2416
#include <cstdio>
#define mod 1000000007
int n, m, f[3010][3010][2];
int main() {
	scanf("%d%d", &n, &m);
	f[0][0][1] = 1;
	for (int i = 1; i <= n; ++ i) f[0][i][0] = 1;
	for (int i = 0; i < m; ++ i) {
		for (int j = 0; j <= n; ++ j) {
			for (int k = 0; k <= 1; ++ k) {
				if (j) {
					(f[i + 1][j - 1][k | (j == 1)] += f[i][j][k]) %= mod;
					(f[i + 1][j][k | (j == 1)] += f[i][j][k]) %= mod;
				}
				if (n - j) {
					(f[i + 1][j][k] += f[i][j][k]) %= mod;
					(f[i + 1][j + 1][k] += f[i][j][k]) %= mod;
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++ i) (ans += f[m][i][1]) %= mod;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 70784
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

#[allow(unused_macros)]
macro_rules! echo {
    ($($e:expr),+) => ( { $(println!("{}", $e))+ } );
}

fn main() {
    input! {
        a: isize,
        b: isize,
        _c: isize,
        k: isize,
    }

    if k <= a {
        echo!(k);
    } else if k <= a + b {
        echo!(a);
    } else {
        echo!(2 * a + b - k);
    }
}


Measured memory_bytes: 2160
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second

int main() {
  int n;
  scanf("%d", &n);
  map<int, int> m;
  REP(i, n) {
    int x;
    scanf("%d", &x);
    m[x]++;
  }
  int ans = 0;
  for (auto it : m) {
    int x = it.F;
    int c = it.S;
    if (m.count(x - 1)) c += m[x - 1];
    if (m.count(x + 1)) c += m[x + 1];
    ans = max(ans, c);
  }
  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 3200
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def isprime(n):
  for i in range(2,int(n**0.5)+1):
    if n%i == 0:
      return False
  return True


def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  query = []
  for i in range(n):
    query.append((a[i],i+1))
  query.sort()

  ans = []
  for i in range(n):
    t,b = query[i]
    ans.append(b)
  print(*ans)
solve()


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

typedef long long lint;
typedef long double louble;

#define lf ('\n')

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 53 , __ = _<<1;

struct edges
{
	set<int> e[_];
	inline set<int>& operator [] (int x){return e[x];}
	inline void adde(int a,int b){e[a].emplace(b);}
	inline void addde(int a,int b){adde(a,b),adde(b,a);}
	void cls(){for(auto &i:e)i.clear();}
}e1,e2;

int n,du[_];
int fa1[_],fa2[_];
int col1[_],col2[_];

void dfsfa2(int x,int ff){fa2[x]=ff;for(auto b:e2[x])if(b!=ff)dfsfa2(b,x);}

int nowans;

void dfs(int x)
{
	col1[x]=col2[x]=2,nowans--;
	for(auto b2:e2[x])
	{
		if(b2==fa2[x])continue;
		if(e1[x].count(b2))dfs(b2);
		else col2[b2]=1;
	}
}

inline int able()
{
	for(int i=1;i<nowans;i++)
	{
		int x=0;
		for(int j=1;j<=n;j++)if(col1[j]==1 && col2[j]==1){x=j;break;}
		if(!x)return 0;
		col1[x]=col2[x]=2;
		for(auto b:e1[x])if(--du[b]==1 && col1[b]==0)col1[b]=1;
		for(auto b:e2[x])if(b!=fa2[x])col2[b]=1;
	}
	return 1;
}

int duBuf[_];

void finder()
{
	e1.cls(),e2.cls();
	memset(duBuf,0,sizeof(duBuf));
	
	n=ty();
	for(int i=1,a,b;i<n;i++)a=ty(),b=ty(),e1.addde(a,b),duBuf[a]++,duBuf[b]++;
	for(int i=1,a,b;i<n;i++)a=ty(),b=ty(),e2.addde(a,b);
	
	if(n<=2){cout<<0<<lf;return;}

	int ans=1e9;
	for(int i=1;i<=n;i++)
	{
		memset(col1,0,sizeof(col1)),memset(col2,0,sizeof(col2));
		nowans=n,col2[i]=1,dfsfa2(i,0),memcpy(du,duBuf,sizeof(du));
		for(int j=1;j<=n;j++)if(du[j]==1)col1[j]=1;
		if(able()){ans=n;break;}
	}
	for(int i=1;i<=n;i++)
	{
		memset(col1,0,sizeof(col1)),memset(col2,0,sizeof(col2));
		nowans=n,dfsfa2(i,0),dfs(i),memcpy(du,duBuf,sizeof(du));
		for(int j=1;j<=n;j++)if(!col1[j] && du[j]==1)col1[j]=1;
		if(nowans<ans && able())ans=nowans;
	}

	if(ans>n)ans=-1;
	cout<<ans<<lf;
}

int main()
{
	ios::sync_with_stdio(0),cout.tie(0);
	
	int t=ty();
	while(t--)finder();

	return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
N = 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % (10**9+7))
result = 0
if abs(n-m) < 2:
    if n == m:
        result = 2*(fact[n]**2)
    else:
        result = fact[n]*fact[m]
print(result%(10**9+7))

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

#define ARC(i, a, b) for(int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)

template<typename T> T ant(const T &a, const T &b){ return a > b ? a : b; }
template<typename T> T ont(const T &a, const T &b){ return a < b ? a : b; }
template<typename T> T rng(const T &a, const T &b){ return a > b ? a - b : b - a; }
template<typename T> T &anth(T &a, const T &b){ return a = ant(a, b); }
template<typename T> T &onth(T &a, const T &b){ return a = ont(a, b); }

template<typename T> T make_v(T val){ return val; }
template<typename... Ts> auto make_v(size_t n, Ts... ts){ return std::vector<decltype(make_v(ts...))>(n, make_v(ts...)); }

int main(){
	int n;
	int x[1234], y[1234];
	scanf("%d", &n);
	unsigned count = 0;
	RC(i, n){
		scanf("%d%d", x + i, y + i);
		count |= 1 << ((x[i] + y[i]) & 1);
	}
	if(count == 1){
		puts("40");
		RC(i, 39) printf("%llu ", 1llu << 38 - i);
		puts("1");
		RC(i, n){
			long long xt = 1, yt = 0;
			RC(j, 39){
				char dir;
				if(x[i] - xt > y[i] - yt){
					if(x[i] - xt > -(y[i] - yt)){
						dir = 'R';
						xt += 1llu << 38 - j;
					}else{
						dir = 'D';
						yt -= 1llu << 38 - j;
					}
				}else{
					if(x[i] - xt > -(y[i] - yt)){
						dir = 'U';
						yt += 1llu << 38 - j;
					}else{
						dir = 'L';
						xt -= 1llu << 38 - j;
					}
				}
				putchar(dir);
			}
			puts("R");
		}
	}else if(count == 2){
		int m = 40;
		printf("%d\n", m);
		RC(i, m) printf("%llu%c", 1llu << m - i - 1, " \n"[i == m - 1]);
		RC(i, n){
			long long xt = 0, yt = 0;
			RC(j, m){
				char dir;
				if(x[i] - xt > y[i] - yt){
					if(x[i] - xt > -(y[i] - yt)){
						dir = 'R';
						xt += 1ll << m - j - 1;
					}else{
						dir = 'D';
						yt -= 1ll << m - j - 1;
					}
				}else{
					if(x[i] - xt > -(y[i] - yt)){
						dir = 'U';
						yt += 1ll << m - j - 1;
					}else{
						dir = 'L';
						xt -= 1ll << m - j - 1;
					}
				}
				putchar(dir);
			}
			putchar('\n');
		}
	}else puts("-1");
}


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

int main(){
  int A,B;
  cin >> A >> B;
  if (A%3 == 0 || B%3 == 0 || (A+B)%3 == 0){
    cout << "Possible" <<endl;
  }else{
    cout << "Impossible" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef long long ll;
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n + m);
    auto ixa = [&](int i) { return i; };
    auto ixb = [&](int i) { return n + i; };
    repeat (i,n) {
        int k; cin >> k;
        repeat (j,k) {
            int l; cin >> l; -- l;
            g[ixa(i)].push_back(ixb(l));
            g[ixb(l)].push_back(ixa(i));
        }
    }
    vector<bool> used(n + m);
    function<void (int)> go = [&](int i) {
        used[i] = true;
        for (int j : g[i]) if (not used[j]) go(j);
    };
    go(ixa(0));
    bool ans = true;
    repeat (i,n) if (not used[ixa(i)]) ans = false;
    cout << (ans ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 8440
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        sc.close();

        int[] bnum = new int[n+1];
        bnum[0] = 0;
        for(int i=0; i<n; i++){
            if(s.charAt(i) == '#'){
                bnum[i+1] = bnum[i] + 1;
            }else{
                bnum[i+1] = bnum[i];
            }
        }

        int ans = Integer.MAX_VALUE;

        if(bnum[n] == 0 || bnum[n] == n){
            System.out.println(0);
            return;
        }

        for(int i=0; i<n; i++){
            int mans = bnum[i+1];
            mans += (n - bnum[n]) - (i+1 - bnum[i]);
            ans = Math.min(ans, mans);
        }

        System.out.println(ans);
    }
}

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


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

  rep(i,N){
    int min;
    int max;
    cin >> min >> max;
    count += max -min;
  }

  N += count;
  cout << N;
}


Measured memory_bytes: 256
#include <stdio.h>

int N, C;
int D[32][32];
int c[512][512];

int count[3][32];
int exists[3];

int main(void) {
	int i, j;
	int color[3];
	int AyaseHaruka = 1111111111;
	if (scanf("%d%d", &N, &C) != 2) return 1;
	for (i = 1; i <= C; i++) {
		for (j = 1; j <= C; j++) {
			if (scanf("%d", &D[i][j]) != 1) return 1;
		}
	}
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			if (scanf("%d", &c[i][j]) != 1) return 1;
		}
	}

	for (i = 1; i <= N; i++) {
		for (j = 1; j <= N; j++) {
			count[(i + j) % 3][c[i][j]]++;
			exists[(i + j) % 3] = 1;
		}
	}

	for (color[0] = 1; color[0] <= C; color[0]++) {
		for (color[1] = 1; color[1] <= C; color[1]++) {
			if (exists[0] && exists[1] && color[0] == color[1]) continue;
			for (color[2] = 1; color[2] <= C; color[2]++) {
				int cost = 0;
				if (exists[0] && exists[2] && color[0] == color[2]) continue;
				if (exists[1] && exists[2] && color[1] == color[2]) continue;
				for (i = 0; i < 3; i++) {
					for (j = 1; j <= C; j++) cost += D[j][color[i]] * count[i][j];
				}
				if (AyaseHaruka > cost) AyaseHaruka = cost;
			}
		}
	}

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


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

  int main(){
 cout << fixed << setprecision(12);
  
  int a, b;
 cin>>a>>b;
  int d = a / b;
  int r = a % b;
  double f =1.0 *  a / b;
 cout<<d<<" "<<r<<" "<<f<<endl;

  return 0;
}


Measured memory_bytes: 3276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll ans = min(a, k);
    if (a >= k) {
        cout << ans << endl;
        return 0;
    }
    k -= a;
    if (b >= k) {
        cout << ans << endl;
        return 0;
    }
    k = max(0LL, k - b);
    ans -= k;
    cout << ans << endl;
    return 0;
}


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

int main() {
  int N;
    cin>>N;
  vector<int> h(N);
for (int i = 0; i < N; i++) {
  cin >> h.at(i);
}

  int m=0;
  int ans=0;
  for(int j=0; j<N;j++){
    if(h.at(j)>=m){
      ans++;}
    m=max(m,h.at(j));
  }
  cout <<ans<< endl;
}

Measured memory_bytes: 256
import math
a, b, n = map(int, input().split())

m = 0
num = math.ceil(b/a)
for i in range(1, b+1, num):
    if n < i:
        break
    a_part = int(a * i / b)
    b_part = a * int(i/b)

    result = a_part - b_part
    if m <= result:
        m = result
    else:
        break

print(m)


Measured memory_bytes: 68016
#include<bits/stdc++.h>
#define st first
#define nd second
#define ii pair<int,int>
#define orta ((bas+son)>>1)
#define pb push_back
#define N 2005
#define LOG 22
#define ll long long
#define MOD 998244353
using namespace std;

int n,ans;
int inv[1000006];
int cnt[1000006];
int res[1000006];

int mul(int x,int y) {

	return (ll) x*y%MOD;

}

int add(int x,int y) {

	x+=y;

	while(x>=MOD) x-=MOD;
	while(x<0) x+=MOD;

	return x;

}

int fe(int x,int y) {

	if(y==0) return 1;

	if(y&1) return mul(fe(x,y-1),x);

	int res=fe(x,y>>1);

	return mul(res,res);

} 

int main() {

	scanf("%d",&n);

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

		int x;

		scanf("%d",&x);

		cnt[x]++;

	}

	for(int i=1;i<=1000000;i++) inv[i]=fe(i,MOD-2);

	for(int i=1000000;i>=1;i--) {

		int sum=0,all=0;

		for(int j=i;j<=1000000;j+=i) {

			for(int k=0;k<cnt[j];k++) {

				all=add(all,mul(sum,j));
				sum=add(sum,j);

			}

		}

		res[i]=mul(all,inv[i]);

		for(int j=i+i;j<=1000000;j+=i) {

			res[i]=add(res[i],-mul(mul(res[j],j),inv[i]));

		}

		ans=add(ans,res[i]);

	}

	printf("%d",ans);

}

Measured memory_bytes: 11904
a,b,c,k = map(int,input().split())
sum1 = 0
while(k>0):
    if(k>=a and a!=0):
        k = k-a
        sum1+=a
        a=0
    elif(k<a):
        a = a - k
        sum1 += k
        k = k-k
    
    elif(k>=b and b!=0):
        k = k-b
        b=0
    elif(k<b):
        b = b - k
        k = k-k
    
    elif(k>=c and c!=0):
        k = k-c
        sum1 = sum1 - c
        c=0
    elif(k<c):
        c  = c-k
        sum1 = sum1 - k
        k = k-k

print(sum1)


Measured memory_bytes: 8976
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  ll h, w, n;
  cin >> h >> w >> n;
  
  map<pair<ll, ll>, int> m;
  set<pair<ll, ll>> s;
  for (int i = 0; i < n; i++){
    ll a, b;
    cin >> a >> b;
    m[pair<ll, ll>(a, b)]++;
    for (int j = -1; j < 2; j++){
      for (int k = -1; k < 2; k++){
        if (a + j >= 2 && a + j <= h - 1 && b + k >= 2 && b + k <= w - 1)
          s.insert(pair<ll, ll>(a + j, b + k));
      }
    }
  }

  ll ret[10] = {};
  ret[0] = (h - 2) * (w - 2) - s.size();
  for (auto i = s.begin(); i != s.end(); i++){
    int num = 0;

    for (int j = -1; j < 2; j++){
      for (int k = -1; k < 2; k++){
        num += m[pair<ll, ll>(i->first + j, i->second + k)];
      }
    }
    ret[num]++;
  }

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

  return 0;
}


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

int main() {
    int N;
    string word[101];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> word[i];
    bool flag = true;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if(word[i] == word[j]) flag = false;
        }
    }
    for (int i = 0; i < N - 1; ++i) {
        if(word[i].back() != word[i + 1].front()) flag = false;
    }
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
  static void Main(string[] args)
  {
    var split = Console.ReadLine().Split(' ');
    int n = int.Parse(split[0]);
    int k = int.Parse(split[1]);
    List<int> list=new List<int>();
    for(int i=0;i<n;i++){
      list.Add(int.Parse(Console.ReadLine()));
    }
    
    var array = list.OrderBy(x=>x).ToArray();
    int min=int.MaxValue;
    for(int i=0;i<n-k+1;i++){
      int work = array[k+i-1] - array[i];
      if(min>work){min=work;}
    }
    Console.WriteLine(min);
  }
}

Measured memory_bytes: 18908
#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() {
    int n; cin >> n;
    vint a(n);
    ll sum_all = 0;
    rep(i,n) {
        int x; cin >> x;
        a[i] = x;
        sum_all += x;
    }
    ll ans = inf_l;
    ll sum = 0;
    rep(i,n-1) {
        sum_all -= a[i];
        sum += a[i];
        ans = min(ans,abs(sum_all-sum));
    }
    cout << ans << endl;
}

Measured memory_bytes: 4044
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P; 
const int inf = 1<<21;
const ll INF = 1LL << 60;
const ll mod = 1e9+7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<P> sc(m);
    rep(i, m){
        int s, c;
        cin >> s >> c;
        s--;
        sc[i] = make_pair(s, c);
    }
    string ans;
    rep(i, n) ans += '0';
    if (n!=1) ans[0] = '1';

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

    if (sc.size()>n){
        cout << -1 << endl;
        return 0;
    }

    rep(i, m){
        int s = sc[i].first, c = sc[i].second;
        ans[s] = c + '0';
    }
    rep(i, m){
        int s = sc[i].first, c = sc[i].second;
        if (ans[s] != c +'0'){
            cout << -1 << endl;
            return 0;
        }
    }

    if (ans[0]=='0' and n!=1){
        cout << -1 << endl;
        return 0;
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;

int main() {

    ll n;
    cin >> n;

    vector<ll> counter(5, 0);

    rep(i, n) {

        string s;
        cin >> s;
        switch (s[0]) {
            case 'M':
                counter[0]++;
                break;
            case 'A':
                counter[1]++;
                break;
            case 'R':
                counter[2]++;
                break;
            case 'C':
                counter[3]++;
                break;
            case 'H':
                counter[4]++;
                break;
        }
    }

    ll ans = 0;
    for (int x = 0; x < 5; x++) {
        for (int y = x + 1; y < 5; y++) {
            for (int z = y + 1; z < 5; z++) {
                ans += counter[x] * counter[y] * counter[z];
            }
        }
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Integer k = sc.nextInt();
		String s = sc.next();

		if (s.length() <= k) {
			System.out.print(s);
		} else {
			for (int i = 0; i < k; i++) {
				System.out.print(s.charAt(i));
			}
			System.out.print("...");
		}
	}
}


Measured memory_bytes: 35560
from collections import Counter
import time

N = int(input())
line = list(map(int, input().split()))
dic = Counter(line)
nums = 0
for num, cnt in dic.items():
    if cnt > 1:
        nums += (cnt * (cnt - 1)) // 2
for i in line:
    print(nums - (dic[i] - 1))

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<ll> L(N);
    for(int i=0; i<N; i++) cin >> L[i];

    int ans = 0;
    for(int i=0; i<N; i++)
    {
        for(int j=i+1; j<N; j++)
        {
            for(int k=j+1; k<N; k++)
            {
                if(L[i]+L[j] > L[k] && L[j]+L[k] > L[i] && L[k]+L[i] > L[j] && L[i] != L[j] && L[j] != L[k] && L[k] != L[i]) ans++;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

int INF=1e8;
int main(){
    int n,e,t;
    cin>>n>>e>>t;
    t--;
    vector<int> dp(n,INF);
    for(int i=0;i<n;i++){
        int w;
        cin>>w;
        if(w){
            dp[i]=1;
        }
    }
    vector<int> g(e);
    vector<vector<int>> s(e);
    for(int i=0;i<e;i++){
        cin>>g[i];
        g[i]--;
        int c;
        cin>>c;
        s[i].assign(c,0);
        for(int j=0;j<c;j++){
            cin>>s[i][j];
            s[i][j]--;
        }
    }
    bool update=true;
    while(update){
        update=false;
        for(int j=0;j<e;j++){
            int ma=0;
            int mi=INF;
            bool isok=false;
            vector<int> vals(s[j].size());
            for(int k=0;k<s[j].size();k++){
                vals[k]=dp[s[j][k]];
            }
            sort(vals.rbegin(),vals.rend());
            int sc=0;
            for(int k=0;k<s[j].size();k++){
                sc=max(sc,k+vals[k]);
            }
            if(sc<dp[g[j]]){
                dp[g[j]]=sc;
                update=true;
            }
        }
    }
    if(dp[t]>=INF){
        cout<<-1<<endl;
    }
    else{
        cout<<dp[t]<<endl;
    }
    return 0;
}


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


int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
	}
	
	sort(a.begin(),a.end(),greater<int>());
	
	int alice = 0;
	int bob = 0;
	for (int j = 0; j * 2 < n; ++j) {
		alice += a[2*j];
		bob += a[2*j+1];
	}
	
	cout << alice - bob << endl;
}



Measured memory_bytes: 256
inp = input().split(" ")
n = int(inp[0])
l = int(inp[1])

taste_list = [l+i-1 for i in range(1,n+1)]
abs_taste_list = [abs(i) for i in taste_list]
min_index = abs_taste_list.index(min(abs_taste_list))
min = taste_list[min_index]
print(sum(taste_list)-min)


Measured memory_bytes: 3060
import math

n=int(input())

t_prev,a_prev=1,1
for i in range(n):
  t,a=map(int,input().split())
  #n_koho1=math.ceil(t_prev/t)
  #n_koho2=math.ceil(a_prev/a)

  n_koho1 = t_prev // t
  n_koho2 = a_prev // a
  if t_prev % t != 0:
      n_koho1 += 1
  if a_prev % a != 0:
      n_koho2 += 1
        
  n=max(n_koho1,n_koho2)
  t=n*t
  a=n*a
    
  t_prev=t
  a_prev=a

print(t_prev+a_prev)

Measured memory_bytes: 3064
import java.util.*;
public class Main {
    public static void main (String[] args) {
        Scanner inp = new Scanner (System.in);
        while(inp.hasNext()){
            int num_1 = inp.nextInt();
            int num_2 = inp.nextInt();
            int sum = num_1+num_2;
            int digit = (int)(Math.log10(sum)+1);;
            System.out.println(digit);
        }
    }
}

Measured memory_bytes: 26400
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
     int a,b,c,d,s;
     scanf("%d%d%d%d",&a,&b,&c,&d);
     if(c>b||d<a)s=0;
     else if(c>=a&&d>=b)s=b-c;
     else if(c<a&&d<b&&d>=a)s=d-a;
     else if(c>=a&&d<=b)s=d-c;
     else s=b-a;
	 
	 printf("%d\n",s);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
//#include <set>
//#include <map>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
#include <vector>
//#include <string>
//#include <list>
//#include <deque>
//#include <unordered_map>
//typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main() {
    vector<int> x(4);
    vector<int> y(4);

    cin >> x[0] >> y[0] >> x[1] >> y[1];
    x[2] = x[1]+(y[0]-y[1]);
    y[2] = y[1]+(x[1]-x[0]);
    x[3] = x[2]+(y[1]-y[2]);
    y[3] = y[2]+(x[2]-x[1]);

    cout << x[2] << " " << y[2] << " " << x[3] << " " << y[3] << endl;

    return 0;
}

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

main(){
  int i,n,l,all,m,near=999;
  cin >> n >> l;
 
  for(i=0;i<n;i++) all += l+i;
  for(i=0;i<n;i++){
    if(abs(l+i) < near){
      near = abs(l+i);
      m = l +i;
    }
  }
  
  cout << all -m << endl;
}

            
  
  
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
const int INF (1 << 30);
const ll LLINF (1LL << 55LL);
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;



ll d[200][200];
ll V,E;

void warshallfloyd(){
    rep(k,V)rep(i,V)rep(j,V){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cin>>V>>E;
    rep(i,V)rep(j,V){
        d[i][j]=LLINF;
        if(i==j) d[i][j]=0;
    }
    rep(i,E){
        ll a,b,c;
        cin>>a>>b>>c;
        d[a][b]=c;
    }
    warshallfloyd();
    rep(i,V){
        if(d[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    rep(i,V){
        rep(j,V){
            if(d[i][j]>=LLINF/2) cout<<"INF";
            else cout<<d[i][j];
            if(j!=V-1) cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3324
#include "bits/stdc++.h"

    using namespace std;
    typedef long long ll;
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int n,k; cin >> n >> k;
        int x;
        ll ans=0;
        for(int i=0;i<n;i++){
            cin >> x;
            if(x>=k) ans++;
        }
        cout << ans << endl;


    }


Measured memory_bytes: 256
public class Main {
  private static void solve() {
    int n = ni();
    long[] a = nal(n);
    
    long now = 0;
    long count = 0;
    for (int i = 0; i < n; i ++) {
      if (a[i] == now) {
        now ++;
        count ++;
      } else {
        if (a[i] > now) {
          System.out.println(-1);
          return;
        } else {
          now = a[i] + 1;
          count += a[i];
        }
      }
    }
    System.out.println(count - 1);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

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

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




Measured memory_bytes: 45676
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;



int main(){
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    
    if(a >= k){
        cout << k << endl;
    }
    else if(a + b >= k){
        cout << a << endl;
    }
    else{
        ll minus = k - a - b;
        cout << a - minus << endl; 
    }

   

}

Measured memory_bytes: 3624
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		String[] ss = s.split(" ");
		int a = Integer.parseInt(ss[0]);
		int b = Integer.parseInt(ss[1]);

		BigDecimal aa = new BigDecimal(ss[0]);
		BigDecimal bb = new BigDecimal(ss[1]);
		
		BigDecimal ff = aa.divide(bb,6,BigDecimal.ROUND_HALF_UP);

		System.out.print(a / b);
		System.out.print(" ");
		System.out.print(a % b);
		System.out.print(" ");
		System.out.println(ff);

	}

}

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

int main() {
    int n, a[100005], b[100005];
    long long ans = 0;
    cin >> n;
    for (int i = 0; i < n + 1; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        if (a[i] <= b[i]) {
            b[i] -= a[i];
            ans += a[i];
            a[i] = 0;
        } else {
            a[i] -= b[i];
            ans += b[i];
            b[i] = 0;
        }
        if (a[i + 1] <= b[i]) {
            ans += a[i + 1];
            a[i + 1] = 0;
        } else {
            ans += b[i];
            a[i + 1] -= b[i];
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 4332