akhauriyash/Code-Regression huggingface dataset:
package main

import (
        "fmt"
)
func abs(x int) int{
        if x>0{
                return x
        }
        return -x
}
func main(){
        var n,x int
        var l [102]bool
        fmt.Scanf("%d %d",&n,&x)
        for i := 0;i<x;i++ {
                var v int
                fmt.Scanf("%d",&v)
                l[v]=true
        }
        ans := 0
        pos := 1000
        for i := range l{
                if (!l[i] && abs(n-i)< pos){
                        ans = i
                        pos = abs(n-i)
                }
        }
        fmt.Println(ans)
}

Measured memory_bytes: 1820
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                    \
  ifstream in("abc147/abc147_a.txt"); \
  cin.rdbuf(in.rdbuf());
#else
#define INPUT_FILE
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
const int INF = 100100100;
const ll LINF = 1e18 + 100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int a, b, c;
  cin >> a >> b >> c;

  cout << (a + b + c < 22 ? "win" : "bust") << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int n, K, Res, D[2010], P[2010], CC[2010];
vector<int>E[2100];
void DFS(int a, int pp, int rr){
    P[a] = rr;
    for(int i=0;i<E[a].size();i++){
        if(E[a][i]!=pp){
            D[E[a][i]] = D[a]+1;
            if(pp == 0) rr = E[a][i];
            DFS(E[a][i],a,rr);
        }
    }
}
void Do(int a){
    D[a]=0;
    DFS(a,0,-1);
    int i, c = 0;
    for(i=1;i<=n;i++){
        CC[i]=0;
        if(D[i] <= K/2) c++;
    }
    if(K%2==1){
        for(i=1;i<=n;i++){
            if(D[i] == (K+1)/2) CC[P[i]]++;
        }
        int M = 0;
        for(i=1;i<=n;i++)M=max(M,CC[i]);
        c+=M;
    }
    Res = min(Res, n - c);
}
int main(){
    int i, a, b;
    scanf("%d%d",&n,&K);
    Res = n;
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        E[a].push_back(b);
        E[b].push_back(a);
    }
    for(i=1;i<=n;i++){
        Do(i);
    }
    printf("%d\n",Res);
}

Measured memory_bytes: 512
import numpy as np

def getNearestValue(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

NL = list(map(int,input().split()))
N = NL[0]
L = NL[1]

taste=[]

for i in range(N):
    taste.append(L+i)

print(sum(taste)-getNearestValue(taste, 0))

Measured memory_bytes: 13576
n,k = map(int,input().split())

def f(x,y):
  cnt = 0
  while x > y:
    y = y << 1
    cnt +=1
  return cnt

ans = 0
for i in range(1,n+1):
  i2 = bin(i)
  cnt = f(k,i)
  ans += 0.5**cnt

print(ans/n)

Measured memory_bytes: 9368
#include <bits/stdc++.h>
#define lli long long int
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
int main()
{
    fio
    lli n,w,i,j;
    cin>>n>>w;
    long long int wt[n],val[n],dp[n+2][w+2];
    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
        cin>>wt[i]>>val[i];
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=w;j++)
        {
            if(i==0|| j==0)
                dp[i][j]=0;
            else if(wt[i]>j)
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j], val[i]+dp[i-1][j-wt[i]]);
        }
    }
    cout<<dp[n][w];


return 0;
}


Measured memory_bytes: 80000
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long int
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second



int main(){
    fastio;
    ld x;
    cin >> x;
    vector<ll> balance(4000);
    balance[0] = 100;
    for(int i=1; i<4000; i++){
        balance[i] = floor(balance[i-1]*1.01);
    }
    cout << lb(all(balance), x) - balance.begin() << endl;
    return 0;
}

Measured memory_bytes: 3880
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()
# row = [int(input().rstrip()) for _ in range(n)]

def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())

    a_list = [int(x) for x in input().rstrip().split(" ")]
    length = sum(a_list)
    center = length * 0.5

    # できるだけ中心に近い切れ目
    center_cut = 0
    cut = 0
    for a in a_list:
        cut += a
        if abs(center_cut - center) > abs(cut - center):
            center_cut = cut
        if cut > center:
            break

    # 中心に近い切れ目を中心に一致させる
    print(int(abs(center_cut - center) * 2))


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 93188
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ;
#define MOD 1000000007
#define ll long long 
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
#define ff first
#define ss second

using namespace std;

const ll inf = 1e15;
int n , k;
int h[100010];
ll dp[100010];

int main(){   

fastio

cin>>n>>k;
for(int i =1 ; i<= n ;i++)cin>>h[i];

for(int i =0 ; i<= n ;i++)dp[i] = inf;


dp[1]=0;
for(int i = 2; i<= k ; i++){
	for(int j =1 ; j<i ; j++){
		dp[i] = min(dp[i] ,dp[i-j] + abs(h[i] - h[i-j]) );
	}
}

for(int  i =k+1; i<=n  ;i++){
	for(int j =1 ; j<=k ; j++){
		dp[i] = min(dp[i] , dp[i-j] + abs(h[i] - h[i-j]));
	}
}

cout<<dp[n];

return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <cmath>
#include <cstring>
#include <assert.h>
#include <utility>
#include <tuple>
#include <array>
#include <bitset>
#include <cstdlib>

using int64 = long long;

const int64 mod = 1e9 + 7;

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

    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    std::map<char, int> counter;
    for (char c : s) {
        counter[c]++;
    }

    int64 ans = 1;
    for (auto& mp : counter) {
        (ans *= mp.second + 1) %= mod;
    }
    ans--;

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 512
#include <stdio.h>

#define GOOD 1
#define BAD 0
#define NONE 2

int a,b,c,N;
int t[1001][4];
int part[301]; 

int main(){
	while(scanf("%d%d%d",&a,&b,&c), a != 0){
		scanf("%d",&N);
		for(int i = 0; i < N; i++){
			scanf("%d%d%d%d",&t[i][0],&t[i][1],&t[i][2],&t[i][3]);
		}
		for(int i = 0; i < 301;i++){
			part[i] = NONE;
		}

		bool modify = true;
		while(modify){
			modify = false;
			for(int i = 0; i < N; i++){
				int before = part[t[i][0]] + (part[t[i][1]] << 3) + (part[t[i][2]] << 6);
				if(t[i][3] == 1){
					part[t[i][0]] = part[t[i][1]] = part[t[i][2]] = GOOD;
				}
				else{
					if(part[t[i][0]] == GOOD && part[t[i][1]] == GOOD){
						part[t[i][2]] = BAD;
					}
					else if(part[t[i][1]] == GOOD && part[t[i][2]] == GOOD){
						part[t[i][0]] = BAD;
					}
					else if(part[t[i][2]] == GOOD && part[t[i][0]] == GOOD){
						part[t[i][1]] = BAD;
					}
				}
				int after = part[t[i][0]] + (part[t[i][1]] << 3) + (part[t[i][2]] << 6);
				modify = modify || before != after;
			}
		}

		for(int i = 1; i <= a + b + c; i++){
			printf("%d\n",part[i]);
		}
	}
	return 0;
}



Measured memory_bytes: 2572
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

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

	class Edge{
		int s;
		int t;
		long cost;
		Edge(int s, int t, long cost){
			this.s=s;
			this.t=t;
			this.cost=cost;
		}
	}

	ArrayList<Edge> g = new ArrayList<Edge>();
	int V;
	int E;
	long INF = 1L<< 50;
	public void run() {
		Scanner sc = new Scanner(System.in);
		V = sc.nextInt();
		E = sc.nextInt();

		for(int i=0; i<E; i++) {
			int s = sc.nextInt(); s--;
			int t = sc.nextInt(); t--;
			long cost = sc.nextLong(); cost = -cost;
			Edge e = new Edge(s,t,cost);
			g.add(e);
		}

		calc();

		sc.close();
	}

	private void calc() {
		long d[] = new long[V];
		for(int i=0; i<V; i++) {
			d[i] = INF;
		}
		d[0]=0;

		for(int i=0; i<V-1; i++) {
			for(int j=0; j<E; j++) {
				Edge e = g.get(j);
				if(d[e.s] == INF) continue;
				if(d[e.t] > d[e.s] + e.cost) {
					d[e.t]= d[e.s] + e.cost;
				}
			}
		}
		long ans = -d[V-1];
		if(negative(d)) {
			System.out.println("inf");
		}else {
			System.out.println(ans);
		}
	}

	private boolean negative(long d[]) {
		boolean negative[] = new boolean[V];

		for(int i=0; i<V; i++) {
			for(int j=0; j<E; j++) {
				Edge e = g.get(j);
				if(d[e.s] == INF) continue;
				if(d[e.t] > d[e.s] + e.cost) {
					d[e.t]= d[e.s] + e.cost;
					negative[e.t]=true;
					if(negative[e.s]==true) {
						negative[e.t]=true;
					}
				}
			}
		}
		if(negative[V-1]) {
			return true;
		}
		return false;
	}

}




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

bool isPrime(ll x){
    ll i = 0;
    while (i*i <= x)
    {
        i ++;
    }
    ll j = i-1;bool res = true;

    if (x <= 1) res = false;
    else if (x >= 4){
        for (ll u = 2; u <= j; u++){
            if (x % u == 0){
                res = false;break;
            }
        }
    }

    return res;
}

int main(){
    int N; cin >> N;
    int count = 0;
    for (int i = 0; i < N; i++)
    {
        ll v; cin >> v;
        if (isPrime(v)) count++;
    }
    
    cout << count << endl;
}


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

#define cn count
#define pb push_back
#define in insert
#define fs first
#define sc second
#define sz size
#define len length
#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define forni(i, n) for (ll i = 1; i < (ll) (n); ++i)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;
using ll = long long;
const ll inf = 1e9+7; 
const double PI =  3.141592653589793;

int main(){
	IO;
	ll h,a;
	cin>>h>>a;
	cout<<(h+a-1)/a<<"\n";
	
	return 0;
}


// _   .-')                .-. .-')                 .-')                                               
//( '.( OO )_              \  ( OO )               ( OO ).                                             
// ,--.   ,--.).-'),-----. ,--. ,--.  .-'),-----. (_)---\_) ,--. ,--.     .-----.  ,-.-')  .-'),-----. 
// |   `.'   |( OO'  .-.  '|  .'   / ( OO'  .-.  '/    _ |  |  | |  |    '  .--./  |  |OO)( OO'  .-.  '
// |         |/   |  | |  ||      /, /   |  | |  |\  :` `.  |  | | .-')  |  |('-.  |  |  \/   |  | |  |
// |  |'.'|  |\_) |  |\|  ||     ' _)\_) |  |\|  | '..`''.) |  |_|( OO )/_) |OO  ) |  |(_/\_) |  |\|  |
// |  |   |  |  \ |  | |  ||  .   \    \ |  | |  |.-._)   \ |  | | `-' /||  |`-'| ,|  |_.'  \ |  | |  |
// |  |   |  |   `'  '-'  '|  |\   \    `'  '-'  '\       /('  '-'(_.-'(_'  '--'\(_|  |      `'  '-'  '
// """    """     """""""" """  """"      """""""  """""""  """"""""      """"""   """         """""""
 


Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define STDIO
#define MOD 1000000007
using namespace std;
int n,k;
long long inv[200100],fac[200100],ifac[200100];//inverse,factorial,inverse of factorial
long long C(int x,int y){
	return ((fac[x]*ifac[y])%MOD*ifac[x-y])%MOD;
}
int main(){
	#ifndef STDIO
		freopen("input.in","r",stdin);
		freopen("output.out","w",stdout);
	#endif
	cin>>n>>k;
	inv[1]=1LL;
	for(int i=2;i<=n;i++)
		inv[i]=(MOD-((MOD/i)*inv[MOD%i])%MOD);
	fac[0]=1LL;
	ifac[0]=1LL; 
	for(int i=1;i<=n;i++){
		fac[i]=(fac[i-1]*(long long)(i))%MOD;
		ifac[i]=(ifac[i-1]*inv[i])%MOD;
	}
	long long res=0LL;
	for(int i=0;i<=min(n-1,k);i++){
		res=(res+(C(n,i)*C(n-1,i))%MOD)%MOD;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 4992
/*** akshaykumar99 ***/
 
#include<bits/stdc++.h> 
using namespace std;
 
const long long MOD = 1e9+7;
const long double PI = acos(-1);
const long long N = 2e9;
 
typedef long long ll;
typedef long double ld;

ll binpow(ll a, ll b, ll m) 
{
    a %= m;
    ll res = 1;
    while (b > 0) 
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll invv(ll x)
{
	return binpow(x, MOD-2, MOD);
}
void test_case()
{
	ll n;
	cin >> n;
	ll fact[n+1], inv[n+1];
	fact[0] = inv[0] = 1;
	for(ll i = 1; i <= n; i++)
	{
		fact[i] = fact[i-1] * i % MOD;
		inv[i] = invv(fact[i]);
	}
	ll ans = 0;
	for(ll i = 2; i <= n; i+= 2)
	{
		ll res = fact[n] * inv[i] % MOD * inv[n - i] % MOD;
		res = res * binpow(9, n-i, MOD) % MOD;
		ans = (ans + res) % MOD;
	}
	ans = ans * 2ll % MOD;
	cout << ans << '\n';

	
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    ll tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}


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

int main()
{
	int n,x[101];
	int ans = INT_MAX , i = 1, j = 1 ;
	int ximax = 0,hp=0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> x[i];
	//走査する最大値
	for (i = 1; i <= n; i++) {
		if (ximax < x[i]) ximax = x[i];
	}

	//体力計算
	for (i = 1; i <= ximax; i++) {
		//cout << i << endl; //debug
		//各整数値での総和
		for (j = 1; j <= n; j++) {
			hp = hp + pow((x[j] - i) ,2.0);
			//cout << hp << endl; //debug
		}
		//cout << "座標" << i << "消費体力" << hp << endl;
		if (ans > hp)ans = hp;
		hp = 0;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>

using namespace std;
using PII = pair<int, int>;

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

	if (n == 1) {
		cout << "First" << endl;
		return 0;
	}

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


	vector<bool> used(n + 1, false);
	queue<int> que;
	used[1] = true;
	que.push(1);

	int node1 = -1;
	while (!que.empty()) {
		auto x = que.front();
		// printf("x1 %d\n", x);
		que.pop();

		for (auto y: connect[x]) {
			if (used[y]) {
				continue;
			}
			used[y] = true;
			que.push(y);
			node1 = y;
		}
	}

	// printf("node %d\n", node1);


	queue<PII> que2;
	int dist = 0;
	used.assign(n + 1, false);
	used[node1] = true;
	que2.push(make_pair(node1, 0));
	while (!que2.empty()) {
		auto p = que2.front();
		que2.pop();
		int x = p.first;
		dist = max(dist, p.second);

		// printf("p %d %d\n", p.first, p.second);

		for (auto y: connect[x]) {
			if (used[y]) {
				continue;
			}
			used[y] = true;
			que2.push(make_pair(y, p.second + 1));
		}
	}
	// printf("dist %d\n", dist);

	// v1 = win
	// v2 = lose
	// vi2 = (vi1 == lose || vi0 == lose) ? win : lose
	// win lose win が繰り返す

	string ans = (dist + 1) % 3 == 2 ? "Second" : "First";
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 13684
#include<bits/stdc++.h>
#define ll      long long
#define pii     pair<int, int>
#define f       first
#define s       second

using namespace std;
ll cnt[200009];
int main()
{
    int n;
    cin>>n;

    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ans += cnt[i]*(cnt[i]-1)/2;
    }

    for(int i=0;i<n;i++){
        ll x = cnt[a[i]] - 1;
        cout<<ans - cnt[a[i]]*(cnt[a[i]]-1)/2 + x*(x-1)/2<<endl;;

    }
}




Measured memory_bytes: 4736
#include<stdio.h>

int main(){
  int a,i;
  scanf("%d",&a);
  if(a == 25) puts("Christmas");
  else {
    printf("Christmas ");
    for(i = 0; i<25-a; i++){
      printf("Eve ");
    }
    printf("\n");
  }
  return 0;
}


Measured memory_bytes: 128
n, k = input().split()
k = int(k)
 
import string
numbers = "0123456789"
alphabets = string.ascii_letters # a-z+A-Zをロード
characters = numbers + alphabets
 
def base_cvt(value, n=2):
    try:
        tmp = int(value)
    except:
        raise ValueError('Invalid value:', value)
 
    if n < 2 or n > len(characters):
        raise ValueError('Invalid n:', value)
 
    result = ''
    tmp = int(value)
    while tmp >= n:
        idx = tmp%n
        result = characters[idx] + result
        tmp = int(tmp / n)
    idx = tmp%n
    result = characters[idx] + result
    return result
  
print(len(str(base_cvt(n, k))))

Measured memory_bytes: 3768
import java.util.*;


import java.io.*;
 
public class Main {
	private static void solve(){
		//Implement solution here.
		int n = ni();		
		int m = ni();
		long result = 0L;
		List<Job> j = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			j.add(new Job(nl(),nl()));
		}
		Comparator<Job> dayComparator = Comparator.comparing(Job::getDay);
		Comparator<Job> salaryComparator = Comparator.comparing(Job::getSalary).reversed();
		j.sort(dayComparator);
		Queue<Job> jq = new PriorityQueue<>(salaryComparator);
		int jidx = 0;
		for(int i = m - 1; i >= 0; i--) {
			while(true) {
				if(jidx < n && j.get(jidx).day <= m - i) {
					jq.add(j.get(jidx));
					jidx++;
				} else {
					break;
				}
			}
			if(jq.size() > 0) {
				result += jq.poll().salary;
			}
		}
		System.out.println(result);
	}
	
	static class Job{
		private long day;
		private long salary;
		public Job(long day, long salary) {
			this.day = day;
			this.salary = salary;
		}
		public long getDay() {
			return day;
		}		
		public long getSalary() {
			return salary;
		}		
	}
 
	//Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		} 
		solve();
	}
 
	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 92560
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <iomanip>
#include <fstream>
using namespace std;
double pie=3.14159265358979;
long long mod=998244353;
//
int main(){
	int n;
	int a[200000];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int ans=0;
	set<int> seed;
	for(int i=0;i<n;i++){
		bool f=true;
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				if(seed.find(j)!=seed.end()){
					f=false;
					break;
				}else if(seed.find(a[i]/j)!=seed.end()){
					f=false;
					break;
				}
			}
		}
		if(f){
			if(i==0){
				if(i+1<n){
					if(a[i]!=a[i+1]){
						ans++;
					}
				}else{
					ans++;
				}
			}else if(a[i]!=a[i-1]){
				if(i+1<n){
					if(a[i]!=a[i+1]){
						ans++;
					}
				}else{
					ans++;
				}
			}
		}
		seed.insert(a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 13716
from collections import*
n,u,v=map(int,input().split())
e=[[]for _ in range(n+1)]
INF=10**18
d=[INF]*(n+1)
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
q=deque([(v,0)])
while q:
  now,c=q.popleft()
  d[now]=c
  for to in e[now]:
    if d[to]!=INF:continue
    q.append((to,c+1))
q=[(u,0)]
ans=0
vis=[1]*(n+1)
while q:
  now,c=q.pop()
  vis[now]=0
  f=1
  for to in e[now]:
    if vis[to]:
      f=0
      if d[to]>c+1:q+=[(to,c+1)]
      if d[to]==c+1:ans=max(c+1,ans)
      else:ans=max(c,ans)
  if len(e[now])==1:ans=max(d[to],ans)
print(ans)

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

int main() {
  int n;
  string s,t;
  cin >> n >> s >> t;
  string ne;
  for(int i=0;i<n;i++){
    ne += s.at(i);
    ne += t.at(i);
  }
  cout << ne << endl;
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

ll solve(string X) {
    int i = 0;
    while (!X.empty() && i < X.size()) {
        if (X[i] == 'S' && X[i+1] == 'T') {
            X = X.substr(0,i) + X.substr(i+2);
            if (--i < 0) i++;
        } else i++;
    }
    return X.size();
}

ll solve2(string X) {
    int N = X.size();
    ll S = 0;
    rep(i,N) {
        if (X[i] == 'S') S++;
        else if (S > 0) S--;
    }
    return S * 2;
}
int main() {
    string X; cin >> X;
//    cout << solve(X) << endl;
    cout << solve2(X) << endl;
}


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

using namespace std;

int main() {
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    int ans=0;
    ans+=min(x,y)*min(a+b,2*c);
    int n=abs(x-y);
    ans+=min(n*(x<y?b:a),2*n*c);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m,x = readInts()
C = [readInts() for _ in range(n)]
INF = float('inf')
ans = INF
for bit in range(1 << n):
    all = [0] * m
    money = 0
    for i in range(n):
        if bit & (1 << i):
            money += C[i][0]
            for j in range(m):
                all[j] += C[i][j+1]
    flag = True
    for k in range(m):
        if all[k] >= x:
            pass
        else:
            flag = False
            break
    if flag:
        ans = min(ans, money)
print(ans if ans != INF else '-1')


Measured memory_bytes: 10408
from functools import reduce
mod = 10**9+7
N, M = map(int, input().split())
A = abs(N-M)
if A > 1:
  print(0)
elif A == 1:
  print((reduce(lambda x,y:x*y%mod, range(1, N+1))*reduce(lambda x,y:x*y%mod, range(1, M+1)))%mod)
else:
  print((reduce(lambda x,y:x*y%mod, range(1, N+1))*reduce(lambda x,y:x*y%mod, range(1, M+1))*2)%mod)

Measured memory_bytes: 38512
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>

using namespace std;

/* PROBLEM

*/

/* INPUT

*/

/* OUTPUT

*/

int main(int argc, char const *argv[])
{
    
    int weight_amount;

    cin >> weight_amount;

    vector<int> weight_sums(weight_amount);

    cin >> weight_sums[0];

    for (int i = 1; i < weight_amount; i++)
    {
        cin >> weight_sums[i];
        weight_sums[i] += weight_sums[i-1];
    }
    
    int last = weight_sums[weight_amount-1];

    int min = 1000000000;

    for (int i = 0; i < weight_amount-1; i++)
    {
        int diff = abs(last-weight_sums[i] - weight_sums[i]);
        if (diff < min)
            min = diff;
    }
    
    cout << min << "\n";
    
    return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


void solve() {
    int i,j,k,l,r,x,y; string s;
    bool exit = false;
    int A,B;
    cin>>A>>B;
    if(A*B % 2 != 0){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    /*cin>>N;
    vector<ll> V;
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define for0(n) for(i=0; i<(n); i++)
#define for1(n) for(i=1; i<=(n); i++)
#define M 1000000007
#define N 10000
bool isPrime[N];

vector<ll> prime;

void seive()
{
    ll i,j,t=1,val;
    memset(isPrime,true,sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(i=4;i<=N;i+=2) isPrime[i]=false;
    for(i=3;i*i<=N;i+=2)
        if(isPrime[i])
            for(j=i*i;j<=N;j+=2*i )
                isPrime[j]=false;
    for(i=2;i<=N;i++)
        if(isPrime[i])
            prime.push_back(i);
}

ll primefactorization(ll n)
{
    ll c=1,i,j,cc;
    for(i=0;prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]==0)
        {
            cc=1;
            while(n%prime[i]==0)
            {
                n/=prime[i];cc++;
            }
            c*=cc;
        }
    }
    if(n>1) c*=2;
    return c;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll _,i,j,n,a,b,e,k,u,t,x=1,m,y,q,f=1,c=0,d=0,l,p,z,o,r,g;
    string ss,s;
    seive();
    cin>>n;
    for1(n-1)
    {
        x=n-i;
        p=primefactorization(x);
        c+=p;
    }
    cout<<c<<endl;
}



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

int main() {
    ll n, k; cin >> n >> k;
    ll ans;
    ans = n%k;
    ans = min(ans, abs(ans-k));
    cout << ans << endl;
    
    return 0;
}


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

//freopen("file_name.in", "r", stdin);
//freopen("file_name.out", "w", stdout);

#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,b) for(int i =a;i<=b;i++)

typedef long long ll;

#define eb emplace_back

#define all(v) (v).begin(),(v).end()

#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

//-DBL_MAX
//__builtin_popcountll(ll x) - __builtin_popcount(int x)

#define prin(a) cout << #a << " = " << (a) << endl
#define prinv(v) {cout << #v << " = "; for(auto it : v) cout << it << " "; cout << endl;}
#define ppal(a)  cout << #a << endl

const int N = 310;

long double dp[N][N][N];

int n;

long double rec(int n1, int n2, int n3){
    int sum = n1+n2+n3;
    if(sum==0) return 0;
    long double &ans = dp[n1][n2][n3];
    if(ans>-0.5) return ans;
    ans = 0;
    if(n1) ans += (1+rec(n1-1,n2,n3))*n1/n;
    if(n2) ans += (1+rec(n1+1,n2-1,n3))*n2/n;
    if(n3) ans += (1+rec(n1,n2+1,n3-1))*n3/n;
    ans += ((long double)n-sum)/n;
    ans = ans/(1.l-((long double)n-sum)/n);
    return ans;
}

int main(){

    int n1 = 0, n2 = 0, n3 = 0;
    cin >> n;
    
    fr(i,n){
        int x;
        scanf("%d", &x);
        if(x==1) n1++;
        else if(x==2)  n2++;
        else n3++;
    }
    
    fr(i,n+1) fr(j,n+1) fr(k,n+1) dp[i][j][k] = -1;
    
    printf("%.15Lf\n", rec(n1,n2,n3));
	
	return 0;
}


Measured memory_bytes: 452864
#include <bits/stdc++.h>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/sort.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using boost::irange;
using boost::sort;
using boost::adaptors::reversed;

int max_A = 0;

void CombinationRepetitionUtil(int chosen[], int arr[],
                    int index, int r, int start, int end, int a[], int b[], int c[], int d[], int q)
{
    // Since index has become r, current combination is
    // ready to be printed, print
    if (index == r)
    {
        int sum = 0;
        // for (int i = 0; i < r; i++) printf("%d ", arr[chosen[i]]);
        // printf("\n");

        for (int i = 0; i < q; i++) {
            if (arr[chosen[b[i] - 1]] - arr[chosen[a[i] - 1]] == c[i]) {
                sum += d[i];
            }



        }
        max_A = max(sum, max_A);
        // cout << sum;

        // printf("\n");
        return;
    }

    // One by one choose all elements (without considering
    // the fact whether element is already chosen or not)
    // and recur
    for (int i = start; i <= end; i++)
    {
        chosen[index] = i;
        CombinationRepetitionUtil(chosen, arr, index + 1,
                                               r, i, end, a, b, c, d, q);
    }
    return;
}

void CombinationRepetition(int arr[], int n, int r, int a[], int b[], int c[], int d[], int q)
{
    // Allocate memory
    int chosen[r+1];

    // Call the recursice function
    CombinationRepetitionUtil(chosen, arr, 0, r, 0, n-1, a, b, c, d, q);
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    int arr[m];
    for (int i = 0; i < m; i++) arr[i] = i + 1;

    int a[q], b[q], c[q], d[q];
    for (int i = 0; i < q; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];

    CombinationRepetition(arr, m, n, a, b, c, d, q);

    cout << max_A << endl;



    return 0;
}

Measured memory_bytes: 3652
n = int(input())
A = list(map(int, input().split()))

flag = True
for i in range(n):
    if A[i] % 2 != 0:
        flag = False

cnt = 0
while(flag):
    for i in range(n):
        A[i] = A[i] / 2
        if A[i] % 2 != 0:
            flag = False
            break
    cnt = cnt + 1
print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    deque<int> q;
    REP(i, 0, n) {
        int a; cin >> a;
        if (i % 2 == 0) q.push_back(a);
        else q.push_front(a);
    }

    if (n % 2 == 0) {
        for (auto itr = q.begin(); itr != q.end(); itr++) {
            cout << *itr;
            if (itr == q.end() - 1) cout << endl;
            else cout << " ";
        }
    } else {
        for (auto itr = q.rbegin(); itr != q.rend(); itr++) {
            cout << *itr;
            if (itr == q.rend() - 1) cout << endl;
            else cout << " ";
        }
    }
    return 0;
}

Measured memory_bytes: 2944
a,b,n=map(int,input().split())
x_kouho=[]
count=1
if b==1:
  res=0
else:
  while count<=n//b:
    x_kouho.append(b*count-1)
    count+=1
  if not x_kouho:
    x_kouho.append(n)

  res=0
  for i in range(0,len(x_kouho)):
    keep=x_kouho[i]
    kept=(a*keep)//b-a*(keep//b)
    if kept>res:
      res=kept
print(res)

Measured memory_bytes: 9204
r,g,b,n = gets.split.map(&:to_i)
ans=0

0.upto(n) do |i|
  0.upto(n) do |j|
    if n-r*i-g*j>=0 && (n-r*i-g*j)%b==0
      ans = ans + 1
    end
  end
end

puts ans

Measured memory_bytes: 1788
k = list(map(int, input().split()))
l = list(map(int, input().split()))
m = list(map(int, input().split()))
n = int(input())
count = 0

# bと等しければ数字を0に変更
for i in range(n):
  b = int(input())
  for j in range(3):
    if k[j] == b:
      k[j] = 0
    elif l[j] == b:
      l[j] = 0
    elif m[j] == b:
      m[j] = 0

# 数字の重複を判定（0以外の重複はない）
if k[0] == k[1] and k[1] == k[2]:
  count += 1
elif l[0] == l[1] and l[1] == l[2]:
  count += 1
elif m[0] == m[1] and m[1] == m[2]:
  count += 1
elif k[0] == l[1] and l[1] == m[2]:
  count += 1
elif k[2] == l[1] and l[1] == m[0]:
  count += 1
else:
  for i in range(3):
    if k[i] == l[i] and l[i] == m[i]:
      count += 1

print("Yes" if count > 0 else "No")

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

const int N = 2e6 + 10;
const int mod = 998244353;

inline int fpow (int a, int b) {
	int ret = 1;
	while (b) {
		if (b & 1) ret = 1ll * ret * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return ret;
}

int f[N], invf[N];

void predeal (int n) {
	f[0] = invf[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = 1ll * f[i - 1] * i % mod;
	}
	invf[n] = fpow(f[n], mod - 2);
	for (int i = n - 1; i >= 1; i--) {
		invf[i] = 1ll * invf[i + 1] * (i + 1) % mod; 
	}
}

inline int C (int n, int m) {
	return n >= m ? 1ll * f[n] * invf[m] % mod * invf[n - m] % mod : 0;
}

int main (void) {
	predeal(2e6);

	int n, m, ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= m; i++) {
		if ((m - i) & 1) continue;
		ans += 1ll * C(n, i) * C((3 * m - i) / 2 + n - 1, n - 1) % mod;
		if (ans >= mod) ans -= mod;
	}
	for (int i = 0; i < m; i++) {
		if ((m - 1 - i) & 1) continue;
		ans -= 1ll * C(n, 1) * C(n, i) % mod * C((m - 1 - i) / 2 + n - 1, n - 1) % mod;
		if (ans < 0) ans += mod;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 15872
/*
TLE発生
原因はvectorのreverseかな？
*/


#include <bits/stdc++.h>
using namespace std;

using LL = long long;

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

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

    vector<LL> b;
    b.reserve(n);

    if(n == 1){
        cout << a[0] << endl;
        return 0;
    }

    for (int i = 0; i < n; i = i + 2){
        b.push_back(a[i]);
    }
    reverse(b.begin(), b.end());
    for (int i = 1; i < n; i = i + 2){
        b.push_back(a[i]);
    }
    if(n % 2 == 0){
        reverse(b.begin(), b.end());
    }

    for (int i = 0; i < n; i++){
        cout << b[i] << " ";
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 5376
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
        var inputLine = Console.ReadLine();
        var splitInput = inputLine.Split(' ');
        var billNum = int.Parse(splitInput[0]);
        var targetTotalAmount = int.Parse(splitInput[1]);

        int resultN10000;
        int resultN5000;
        int resultN1000;

        Search(billNum, targetTotalAmount, out resultN10000, out resultN5000, out resultN1000);

        Console.WriteLine("{0} {1} {2}", resultN10000, resultN5000, resultN1000);
    }

    private static int GetTotalAmount(int n10000, int n5000, int n1000)
    {
        return n10000 * 10000 + n5000 * 5000 + n1000 * 1000;
    }

    private static bool Search(int billNum, int targetTotalAmount, out int resultN10000, out int resultN5000, out int resultN1000)
    {
        resultN10000 = -1;
        resultN5000 = -1;
        resultN1000 = -1;
        for (var n1000 = 0; n1000 <= billNum; n1000++)
        {
            for (var n5000 = 0; n5000 <= billNum - n1000; n5000++)
            {
                var n10000 = billNum - n1000 - n5000;
                if (GetTotalAmount(n10000, n5000, n1000) == targetTotalAmount)
                {
                    resultN10000 = n10000;
                    resultN5000 = n5000;
                    resultN1000 = n1000;
                    return true;
                }
            }
        }
        return false;
    }
}

Measured memory_bytes: 13140
import java.util.*;
public class Main {
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		String a=sc.next();
		String b="Sunny";
		String c="Cloudy";
		String d="Rainy";
		if(a.equals(b)){
			System.out.print("Cloudy");
		}
		else if(a.equals(c)){
			System.out.print("Rainy");
		}
		else if(a.equals(d)){
			System.out.print("Sunny");
		}
		
	}
}


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

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



Measured memory_bytes: 3264
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
 
#define REP(i,n) for(i=0;i<n;i++)
 
//prototype declaration
int iin();
long long llin();
double din();
char cin();
void stin(char *s);
void iout(int i);
void llout(long long i);
void dout(double i);
void cout(char c);
void stout(char *s);
int dfs(int v, int n, int *visited, int table[n][n]);
int gcd(int a, int b);
int lcm(int a, int b);
long long llgcd(long long a, long long b);
long long lllcm(long long a, long long b);
int asc(const void *a, const void *b);
int desc(const void *a, const void *b);
double to_deg(double rad);
 
//main function
int main() {
  int a = iin(), b = iin(), x = iin();
  if (a*a*b >= x*2) {
    dout(90.0 - to_deg(atan((double)(2*x)/(double)(a*b*b))));
  } else {
    dout(90.0 - to_deg(atan((double)(a*a*a)/(double)(2*(a*a*b - x)))));
  }
    return 0;
}
 
//body function
int iin() {
    int i;
    scanf("%d", &i);
    return i;
}
 
long long llin() {
    long long i;
    scanf("%lld", &i);
    return i;
}
 
double din() {
    double i;
    scanf("%lf", &i);
    return i;
}
 
char cin() {
    char c;
    scanf("%c", &c);
    return c;
}
 
void stin(char *s) {
    scanf("%s", s);
}
 
void iout(int i) {
    printf("%d\n", i);
}
 
void llout(long long i) {
    printf("%lld\n", i);
}
 
void dout(double i) {
    printf("%lf\n", i);
}
 
void cout(char c) {
    printf("%c\n", c);
}
 
void stout(char *s) {
    printf("%s\n", s);
}
 
int dfs(int v, int n, int *visited, int table[n][n]) {
    int all_visited = 1, i;
 
    REP(i,n) {
        if (!visited[i]) {
            all_visited = 0;
            break;
        }
    }
 
    if (all_visited) {
        return 1;
    }
 
    int count = 0;
 
    REP(i,n) {
        if (!table[v][i]) continue;
        if (visited[i]) continue;
 
        visited[i] = 1;
        count += dfs(i, n, visited, table);
        visited[i] = 0;
    }
 
    return count;
}
 
int gcd(int a, int b) {
    int r;
 
    if (a < b) {
        r = a;
        a = b;
        b = r;
    }
 
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
 
    return b;
}
 
int lcm(int a, int b) {
    int r = llgcd(a, b);
    a /= r;
    return a * b;
}
 
long long llgcd(long long a, long long b) {
    long long r;
 
    if (a < b) {
        r = a;
        a = b;
        b = r;
    }
 
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
 
    return b;
}
 
long long lllcm(long long a, long long b) {
    long long r = llgcd(a, b);
    a /= r;
    return a * b;
}
 
int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}
 
int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

double to_deg(double rad) {
    return rad * 180.0 / (atan(1.0) * 4.0);
}

Measured memory_bytes: 384
#include <iostream>

#define MAX_N 300000

using namespace std;

int N;
int p[MAX_N+1], ans[MAX_N+1];

int main(){
	for (int i = 0; i < MAX_N; i++)
	{
		if(i%7 != 1 && i%7 != 6) p[i] = 0;
		else p[i] = i;
	}
	p[1] = 0;
	for (int i = 6; i < MAX_N;)
	{
		for (int j = i*2; j < MAX_N; j += i)
		{
			p[j] = 0;
		}
		int k = i+1;
		while(p[k] == 0){
			k++;
			if(k >= MAX_N) break;
		}
		i = k;
	}
	while(1){
		cin >> N;
		if(N == 1) break;
		int count = 0;
		for (int i = 2; i <= N; i++)
		{
			if(N%i == 0 && p[i] != 0){
				ans[count] = i;
				count++;
			}
		}
		cout << N << ": ";
		for (int i = 0; i < count-1; i++)
		{
			cout << ans[i] << " ";
		}
		cout << ans[count-1] << endl;
	}
	return 0;
}

Measured memory_bytes: 2336
import sys
from io import StringIO
import unittest


def resolve():
    n = int(input())
    d = list(map(int, input().split()))

    d.sort()

    l = d[n // 2 - 1]
    r = d[n // 2]

    print(r - l)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """6
9 1 4 4 6 7"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """8
9 1 14 5 5 4 4 14"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """14
99592 10342 29105 78532 83018 11639 92015 77204 30914 21912 34519 80835 100000 1"""
        output = """42685"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 28244
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  
	
	ll n;
	cin>>n;
	string str;
	cin>>str;
	if(str.length()<=n)
	cout<<str;
	else
	{
		ll diff=str.length()-n;
		str=str.substr(0,str.length()-diff);
		
		for(ll i=1;i<=3;i++)
		str+='.';
		cout<<str;
	}
  
	
  	
	return 0;
}


Measured memory_bytes: 3628
my $N = <STDIN>;
my $s = <STDIN>;
my @s = split(/ /,$s);


$num = 1;
$count = 0;

for($i=0;$i<$N;$i++){
  if( $num == $s[$i]){
    $num++;
  }else{
    $count++;
  }
}
if( $num == 1 ){
  print "-1";
}else{
  print "$count";
}

Measured memory_bytes: 33316
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define uni(e) e.erase(unique(e.begin(),e.end()),e.end())
#define double long double
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 INF=1e10;
int MOD=1e9+7;
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void yesno(T b){if(b)out("yes");else out("no");}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
template<class T> void YESNO(T b){if(b)out("YES");else out("NO");}
template<class T> void noyes(T b){if(b)out("no");else out("yes");}
template<class T> void NoYes(T b){if(b)out("No");else out("Yes");}
template<class T> void NOYES(T b){if(b)out("NO");else out("YES");}
int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
}
int kurai(int a,int b){
  int m=pow(10,b),n=pow(10,b-1);
  return (a%m)/n;
}
int ketawa(int a){
  int k=0;
  rep(i,keta(a)){
  k+=kurai(a,i+1);
  }
  return k;
}
int gcd(int a,int b){
  if(a%b==0)
    return b;
  return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
int mid(int a,int b,int c){
  vector<int> k(3);
  k[0]=a;k[1]=b;k[2]=c;
  sort(all(k));
  return k[1];
}
bool sosuu(int a){
  bool b=1;
  if(a<=1)
    return 0;
  else{
  rep1(i,sqrt(a)-1){
  if(a%(i+1)==0)
  b=0;
  }
  return b;
  }
}
int modpow(int a,int b,int m=MOD){
 if(!b)return 1; if(b&1)return modpow(a,b-1,m)*a%m;
 int memo = modpow(a,b>>1,m);
 return memo*memo%m;
}
int fact_mod(int n) {
    int f=1; 
for(int i=2;i<n+1;i++) f=f*(i%MOD)% MOD;
    return f;
}
int mod_pow(int x,int n) {
    int res=1;
    while(n>0){
        if(n&1) res=(res*x)%MOD; 
        x=(x*x)%MOD;        
n>>=1; 
    }
    return res;
}
int c_mod(int n, int r) {
    if(r>n-r) r=n-r;
    if(r==0) return 1;
    int a=1;
    rep(i,r) 
a=a*((n-i)%MOD)%MOD;
    int b=mod_pow(fact_mod(r), MOD-2);
    return (a%MOD)*(b%MOD)%MOD;
}
signed main(){
  int a,b;
  cin>>a>>b;
  int c=b;
  rep(i,a-1)
    c*=b-1;
    out(c);
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

class Node():
    def __init__(self, parent=-1, left=-1, right=-1, depth=0, height=0, sibling=-1, degree=0):
        self.parent = parent
        self.left = left
        self.right = right
        self.depth = depth
        self.height = height
        self.sibling = sibling
        self.degree = degree

if __name__ == '__main__':

    n = int(input())
    T = [Node() for i in range(n)]

    for _ in range(n):
        i, left, right = [int(s) for s in input().split(" ")]
        has_left = (left != -1)
        has_right = (right != -1)
        if has_left:
            T[i].left = left
            T[left].parent = i
            T[i].degree += 1
        if has_right:
            T[i].right = right
            T[right].parent = i
            T[i].degree += 1
        if has_left and has_right:
            T[left].sibling = right
            T[right].sibling = left

    def setDepth(u, p):
        T[u].depth = p
        if T[u].right != -1:
            setDepth(T[u].right, p + 1)
        if T[u].left != -1:
            setDepth(T[u].left, p + 1)

    def setHeight(u):
        h1 = 0
        h2 = 0
        if T[u].right != -1:
            h1 = setHeight(T[u].right) + 1
        if T[u].left != -1:
            h2 = setHeight(T[u].left) + 1
        T[u].height = max(h1, h2)
        return T[u].height

    for i, n in enumerate(T):
        if n.parent == -1:
            root = i
        
    setDepth(root, 0)
    setHeight(root)

    for i, node in enumerate(T):
        if node.parent == -1:
            n_type = "root"
        elif node.left != -1 or node.right != -1:
            n_type = "internal node"
        else:
            n_type = "leaf"

        print("node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}".format(
            i, node.parent, node.sibling, node.degree, node.depth, node.height, n_type))
    


Measured memory_bytes: 5620
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

const int mod = 1e9+7;

int n;
int m;
long long cm[N];
long long rm[N];
map < long long , long long > cnt;

int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d" , &x);
        cm[i] = cm[i - 1] + x;
    }
    for(int i = 0; i <= n; i++){
        rm[i] = cm[i] % m;
        cnt[rm[i]]++;
    }
    long long ans = 0;
    for(auto v : cnt){
        ans += v.second * (v.second - 1) / 2;
    }
    printf("%lld\n" , ans);
}


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

int main() {
    double n, m;
    cin >> n >> m;
    vector<int> L(m), R(m);
    rep(i, m) cin >> L[i] >> R[i];
    int maxi = *max_element(L.begin(), L.end());
    int mini = *min_element(R.begin(), R.end());
    if(mini < maxi) {
        cout << 0 << endl;
    } else {
        cout << mini - maxi + 1 << endl;
    }
    return 0;
}

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

int main() {
  long long A,V,B,W;
  cin >> A >> V >> B >> W;
  
  long long dis;
  if (A < B)
    dis = B - A;
  else
    dis = A - B;
  
  long long T;
  cin >> T;
  
  if ((V - W) * T >= dis)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 3632
n, m, c = map(int, input().split())
b = tuple(map(int, input().split()))
ans = 0
for i in range(n):
    a = tuple(map(int, input().split()))
    x = 0
    for j in range(m):
        x += a[j] * b[j]
    if x + c > 0:
        ans += 1
print(ans)

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

int main() {
    int n, sum, curr;
    cin >> n >> curr;
    sum = 0;
    vector<int> v;
    for (int i=1; i<n; i++)
    {
        int h;
        cin >> h;
        if (curr >= h)
            sum += 1;
        else
        {
            v.push_back(sum);
            sum = 0;
        }
        curr = h;        
    }
    v.push_back(sum);
    cout << *max_element(v.begin(), v.end());   
    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int N, M; cin >> N >> M;
    vector<int> A(100002);
    for (int i = 0; i < M; i++) {
        int L, R; cin >> L >> R;
        A[L]++;
        A[R+1]--;
    }
    for (int i = 1; i <= N; i++) {
        A[i] += A[i-1];
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        if (A[i] == M) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 640