akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define V vector<long long>
#define VV vector<vector<long long>>
#define rep(i,n) for(ll (i)=0;(i)<(n);++(i))
using namespace std;

int main(){
    ll n,d,a;
    cin>>n>>d>>a;
    vector<pair<ll,ll>> e(n);
    rep(i,n){
        ll x,h;
        cin>>x>>h;
        e[i]=make_pair(x,h);
    }
    sort(e.begin(),e.end());
    V x(n),h(n);
    rep(i,n){
        x[i]=e[i].first;
        h[i]=e[i].second;
    }
    V imos(n+1,0);
    ll sumd=0;
    ll ans=0;
    rep(l,n){
        sumd+=imos[l];
        if(sumd>=h[l])continue;
        ll r=upper_bound(x.begin(), x.end(), x[l]+2*d)-x.begin();
        ll damage=((h[l]-sumd+a-1)/a)*a;
        imos[l]+=damage;
        imos[min(r,n)]-=damage;
        ans+=(h[l]-sumd+a-1)/a;
        sumd+=damage;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 8064
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int cost[100001];
vector<int> G[100001];
vector<int> F[100001];
int n,m;
priority_queue< int,vector<int>,greater<int> > q;
bool v[100001];



P cc[100001];
void dfs(int s){
  if(v[s]) return ;
  v[s]=true;
  q.push(cost[s]);
  for(int i=0;i<G[s].size();i++){
    dfs(G[s][i]);
  }
}
int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>cost[i];
    cc[i]=P(cost[i],i);
  }
  sort(cc,cc+n);
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  ll res=0;
  priority_queue< int,vector<int>,greater<int> > q2;
  vector<int> tmp;
  int num=0;
  for(int i=0;i<n;i++){
    if(!v[cc[i].second]){
      dfs(cc[i].second);
      res+=q.top();
      q.pop();
      while(!q.empty()){
        q2.push(q.top());
        q.pop();
      }
      num++;
    }


  }
  for(int i=0;i<2*(num-1)-num;i++){
    if(q2.empty()){
      cout<<"Impossible"<<endl;
      return 0;
    }
    res+=q2.top();
    q2.pop();
  }
  if(num==1) {
    cout<<0<<endl;
    return 0;
  }
  cout<<res<<endl;
  return 0;
}

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

int main () {
    vector <int> L(3);
    for (int i = 0; i < L.size(); i++)
        cin >> L[i];
    
    sort(L.begin(), L.end());
    cout << L[0] << " " << L[1] << " " << L[2] << endl;
}


Measured memory_bytes: 3120
def test():
    n = int(input())
    a = [(list(map(int,input().split()))) for i in range(n)]
    for cx in range(101):
        for cy in range(101):
            for x,y,h in a:
                if h > 0:
                    H = h + abs(x-cx) + abs(y-cy)
                    break
            for x,y,h in a:
                if max(H-abs(x-cx)-abs(y-cy),0) != h:
                    break
            else:
                print(cx,cy,H)
                return


if __name__ == "__main__":
    test()


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

using namespace std;

int main(){
   int N;
   string s,t;
   cin >> N >> s >> t;
   for(int i=0;i<N;i++){
      if(s.substr(i,N)==t.substr(0,N-i)){
         cout << N+i << endl;
         return 0;
      }
   }
   cout << 2*N << endl;
   return 0;
}


Measured memory_bytes: 256
//! ----------------------------------------------
//! Framework <https://github.com/vain0x/procon>
//!
//! See the bottom of file for solution.
//! ----------------------------------------------

#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cell::RefCell;
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Display, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;

/// Print values to standard error if debug mode.
#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), stderr());
            writeln!(err, "\x1B[33m{}\x1B[0m = {:?}", e, $e).unwrap()
        })*
    };
}

/// Read from standard input and parse each word.
/// - `read!(T, U, ..)` parses a line as a tuple of words.
/// - `read![[T]]` parses a line as an array of words.
/// - `read![..; N]` parses `N` lines, using `read!(..)` repeatedly.
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

/// Read a line from standard input.
#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();

    #[allow(deprecated)]
    buf.trim_right().to_owned()
}

// -----------------------------------------------
// Solution
// -----------------------------------------------

fn main() {
    let N = read!(usize);
    let V = read![[i64]];
    let C = read![[i64]];

    let m = (0..N).map(|i| max(V[i] - C[i], 0)).sum::<i64>();

    println!("{}", m)
}


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

int main(){
	long long n,x,a[100010]={ 0 },i,tmp,count=0;
	cin>>n>>x;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	
	for(i=1;i<n;i++){
		if(a[i-1]+a[i]>x) {
			tmp=a[i-1]+a[i];
			count+=(tmp-x);
			if(a[i]>=tmp-x) a[i]-=(tmp-x);
			else a[i]=0;
		}
	}
	
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 1024
def main():
    s = input()
    start = int(s[0:2])
    end = int(s[2:4])
    if start == 0 and (end > 0 and end <= 12):
        print("YYMM")
    elif (start > 0 and start <= 12) and end == 0:
        print("MMYY")
    elif 0 < start <= 12 and 0 < end <= 12:
        print("AMBIGUOUS")
    elif start > 12 and 0 < end <= 12:
        print("YYMM")
    elif 0 < start <= 12 and end > 12:
        print("MMYY")
    else:
        print("NA")
main()


Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


// Union Find
const int N_MAX = 100010;
int par[N_MAX];

void init_par(){
    REP(i, N_MAX) par[i] = i;
}

int root(int x){
    if(par[x] == x) return x;
    else return par[x] = root(par[x]);
}

bool same(int x, int y){
    return root(x) == root(y);
}

void unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y) return; // rank有りの場合ならこのifはあったほうがいい
    par[x] = y;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    init_par();
    int n, m;
    cin >> n >> m;
    VI p(n);
    REP(i, n) {
        cin >> p[i];
        p[i]--;
    }
    REP(i, m) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        unite(x, y);
    }

    int ans = 0;
    REP(i, n)if(same(p[i], i)) ans++;
    cout << ans << endl;

    return 0;
}


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

char s[100005];

int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    int tot=n-1,now=n;
    if(s[n]=='1'||s[1]=='0')
    {
        puts("-1");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1'&&s[n-i]=='0')
        {
            puts("-1");
            return 0;
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        if(s[i]=='1'){
            printf("%d %d\n",now,tot);
            now=tot--;
        }
        else
        {
            printf("%d %d\n",now,tot--);
        }
    }
    return 0;
}


Measured memory_bytes: 1536
import java.util.*;

public class Main {
  public static void main(String[] args ) throws Exception {
    Scanner sc = new Scanner(System.in);
    int K = sc.nextInt();
    String S = sc.next();
    if (S.length() <= K) {
        System.out.println(S);
    } else {
        System.out.println(S.substring(0, K) + "...");
    }
  }
}

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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    for (int i = 0; i <= n - 3; ++i) {
        if (s.substr(i, 3) == "ABC") ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())

ed = [[] for _ in range(n)]

for _ in range(n-1):
    u,v,w = map(int, input().split( ))
    ed[u-1].append([v-1,w])
    ed[v-1].append([u-1,w])#こっちも必要

c = [0]*n
done = [0]*n#無向だから
Q = deque()

Q.append(0)
while Q:
    u = Q.popleft()
    for e in ed[u]:
        if not done[e[0]]:
            c[e[0]] = (e[1]&1) ^ c[u]
            Q.append(e[0])
            done[e[0]] = 1

for i in range(n):
    print(c[i])

Measured memory_bytes: 84128
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	class Edge {
		int to, cost;

		public Edge(int to, int cost) {
			// TODO 自動生成されたコンストラクター・スタブ
			this.to = to;
			this.cost = cost;
		}
	}
	
	class Node implements Comparable<Node> {
		int num;
		int dist;
		Node(int num, int dist) {
			this.num = num;
			this.dist = dist;
		}
		@Override
		public int compareTo(Node o) {
			// TODO 自動生成されたメソッド・スタブ
			return this.dist - o.dist;
		}
	}
	
	int n, m;
	
	void dijkstra(int p, int q, ArrayList<LinkedList<Edge>> edges) {
		
		int INF = Integer.MAX_VALUE / 2;
		int[] d = new int[m + 1]; // 各駅への最短距離
		Arrays.fill(d, INF);
		PriorityQueue<Node> que = new PriorityQueue<Node>();
		d[p] = 0;
		que.add(new Node(p, 0));
		
		while(!que.isEmpty()) {
			Node n = que.poll();
			int v = n.num;
			if(v == q) {
				System.out.println(n.dist);
				return;
			}
			if (d[v] < n.dist) continue;
			for(Edge e : edges.get(v)) {
				if(d[e.to] > d[v] + e.cost) {
					d[e.to] = d[v] + e.cost;
					que.add(new Node(e.to, n.dist + e.cost));
				}
			}
		}
		
	}
	

	void run() {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			n = scanner.nextInt();
			m = scanner.nextInt();
			if (n == 0 || m == 0)
				break;
			ArrayList<LinkedList<Edge> > costedges = new ArrayList<LinkedList<Edge> >(m + 1);
			ArrayList<LinkedList<Edge> > timeedges = new ArrayList<LinkedList<Edge> >(m + 1);
			for(int i=0; i < m+1; i++) {
				costedges.add(new LinkedList<Edge>());
				timeedges.add(new LinkedList<Edge>());
			}
			for (int i = 0; i < n; i++) {
				int a = scanner.nextInt();
				int b = scanner.nextInt();
				int cost = scanner.nextInt();
				int time = scanner.nextInt();
				costedges.get(a).add(new Edge(b, cost));
				costedges.get(b).add(new Edge(a, cost));
				timeedges.get(a).add(new Edge(b, time));
				timeedges.get(b).add(new Edge(a, time));
			}
			int k = scanner.nextInt();
			if (k == 0)
				return;
			
			for (int i = 0; i < k; i++) {
				int p = scanner.nextInt();
				int q = scanner.nextInt();
				int r = scanner.nextInt();
				dijkstra(p, q, r == 0 ? costedges : timeedges);
			}
		}
		scanner.close();
	}

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		new Main().run();
	}

}

Measured memory_bytes: 95252
#include<bits/stdc++.h>
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define bi(x) memset(x,0x3f,sizeof(x))
#define graph(x) for(int i=first[x];i;i=e[i].next)
#define ud  using namespace std
ud;
const int maxn=1e5+1000,inf=0x3f3f;
int n;
char s[maxn];
map<char,int> cnt,ans;
inline long long read()
{
	long long s=0,f=1;
	char ch;
	for(;ch<'0' || ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0' && ch<='9';ch=getchar()) s=(s<<1)+(s<<3)+ch-'0';
	return s*f;
}
int main()
{
	n=read(); 
	for(char i='a';i<='z';++i) ans[i]=inf;
	while(n--)
	{
		scanf("%s",s); int len=strlen(s);
		for(char i='a';i<='z';++i) cnt[i]=0;
		for(int i=0;i<len;++i)
		++cnt[s[i]];
		for(char i='a';i<='z';++i)
		ans[i]=min(ans[i],cnt[i]);
	}
	for(char i='a';i<='z';++i)
	{
		for(int j=1;j<=ans[i];++j)
		cout<<i;
	}
	cout<<endl;
	return 0;
}



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

# pattern1
goukei = 0
ans1 = 0
for i in range(n):
    goukei += A[i]
    if i % 2:
        if goukei >= 0:
            ans1 += goukei + 1
            goukei = -1
    else:
        if goukei <= 0:
            ans1 += 1 - goukei
            goukei = 1
# pattern2
goukei = 0
ans2 = 0
for i in range(n):
    goukei += A[i]
    if i % 2:
        if goukei <= 0:
            ans2 += 1 - goukei
            goukei = 1
    else:
        if goukei >= 0:
            ans2 += goukei + 1
            goukei = -1
print(min(ans1, ans2))


Measured memory_bytes: 19872
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long size = Long.MAX_VALUE;
		long time = 0;
		for (int i = 0; i < 5; i++) {
		    long max = sc.nextLong();
		    if (max < size) {
		        time = (n + max - 1) / max + i;
		        size = max;
		    } else {
		        time++;
		    }
		}
		System.out.println(time);
	}
}


Measured memory_bytes: 21716
# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 16:05:26 2019
DP_G
@author: maezawa
"""
import sys
sys.setrecursionlimit(10**7)

n, m = list(map(int, input().split()))
v = [-1]*(n+1)
adj = [[] for _ in range(n+1)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    adj[i].append(j)
    
def dfs(vi):
    if v[vi] != -1:
        return v[vi]
    res = 0
    for nb in adj[vi]:
        res0 = dfs(nb) +1
        if res < res0:
            res = res0
    v[vi] = res
    return res

ans = 0
for node in range(1, n+1):
    current = dfs(node)
    if current > ans:
        ans = current
print(ans)
    


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

#define lli long long
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(lli i=0;i<j;i++)
#define rep1(i,j) for(lli i=1;i<=j;i++)
#define rep0d(i,j) for(lli i=j-1;i>=0;i--)
#define MAX 1000000007

using namespace std;


bool cmpf(pair<lli, lli> left, pair<lli, lli> right) {
	return left.first < right.first;
}


int main() {
	lli n;
	cin >> n;
	vector<double> vec(n);
	rep0(i, n)cin >> vec[i];
	sort(all(vec));
	double ans = vec[0];
	rep1(i, n-1) {
		ans += vec[i];
		ans /= 2;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void){
  int i,dist=0;
  char S[100010];
  if(scanf("%s",S)<1)return 1;
  for(i=0;S[i];i++){
    if(i%2==0 && S[i]=='0') dist++;
    if(i%2==1 && S[i]=='1') dist++;
  }
  if(dist*2>i){
    printf("%d\n",i-dist);
  }
  else{
    printf("%d\n",dist);
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int x, a;
    cin >> x >> a;
    if(x < a)cout << 0;
    else cout << 10;
}


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

int main()
{
    long n,ans=0,zero=0; cin>>n;
    long a[n+1],b[n],c[n+1],d[n];
    
    for(int i=0;i<n+1;++i){
        cin>>a[i];
        c[i]=a[i];
    }
    for(int i=0;i<n;++i){
        cin>>b[i];
        d[i]=b[i];
    }
    
    for(int i=0;i<1;++i){
        if(a[i]>=b[i]){
            ans+=b[i];
            b[i]=0;
        }
        else {
            ans+=a[i];
            b[i]-=a[i];
    }
    }
    
    for(int i=1;i<n;++i){
        a[i]=max(a[i]-b[i-1],zero);
        b[i]=max(b[i]-a[i],zero);
        ans+=c[i]-a[i]+d[i]-b[i];
    }
        a[n]=max(a[n]-b[n-1],zero);
        ans+=c[n]-a[n];

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

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e15;

int main() {
  ll k, t;
  cin >> k >> t;
  vector<ll> a(t);
  REP(i, t) cin >> a[i];
  sort(ALL(a));

  ll sum = 0;
  REP(i, t - 1) sum += a[i];

  cout << max(0LL, a[t - 1] - 1 - sum) << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s;
int ansn,t,f,m;
char c;
bool q1;
deque<char>ans;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)ans.push_front(s[i]);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&t);
		if(t==1)q1^=1;
		else
		{
			scanf("%d",&f);
			f--;
			while((c=getchar())<'a'||c>'z');
			if(f^q1)ans.push_front(c);
			else ans.push_back(c);
		}
	}
	if(!q1)while(!ans.empty())putchar(ans.back()),ans.pop_back();
	else while(!ans.empty())putchar(ans.front()),ans.pop_front();
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P; 
#define INF 100000000
const int MAX = 1000000;
const int MOD = 1000000007;
int main(){
   int n;
   cin>>n;
   vector<int> a(n);
   REP(i,n){
       cin>>a[i];
   }
   int ans=0;
   REP(i,n){
       if(a[i]!=i+1-ans) ans++; 
   }
   if(ans==n) ans=-1;
   OUT(ans);
    return 0;
}

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

#define ll long long int
#define f(i,n) for(ll i = 0; i < n ; i++)
#define fn(i,n) for(ll i = 1; i <= n ; i++)
#define F first 
#define pb push_back
#define S second
using namespace std;
ll dp[105][100005];
ll n,W;
ll mn = INT_MAX;
ll sol(ll a[], ll w[],ll n, ll W)
{
   if(W <= 0 || n <= 0)
    return 0;
    if(dp[n][W] != -1) return dp[n][W];
   
        if(W >= w[n-1])
          return dp[n][W] = max(sol(a,w,n-1,W), a[n-1] + sol(a,w,n-1,W - w[n-1]));

        else
          return dp[n][W] = sol(a,w,n-1,W);

     
   
  // return dp[n][W];
}


 
int main()
{

     #ifndef ONLINE_JUDGE
     freopen("input.txt","r",stdin);
     freopen("output.txt","w",stdout);
     #endif
     
         //ll n;
          memset(dp,-1,sizeof(dp));
         cin>>n>>W;
         ll p[n],w[n];
        
         f(i,n)
         {
            cin>>w[i]>>p[i];
         }
         //f(i,10) dp[i] = 100;
         memset(dp,-1,sizeof(dp));
         cout<<sol(p,w,n,W);
         //cout<<dp[0][3]<<endl;
         
        
         
   return 0;
}


Measured memory_bytes: 85644
import java.util.*


data class Edge(val a: Int, val b: Int)

data class GF(val x: Long) {
    companion object {
        const val MOD: Long = (1e9 + 7).toLong()

        fun powGF(x: GF, t: Long): GF {
            if (t == 0L) return GF(1)
            val y = powGF(x, t / 2L)
            return if (t % 2L == 0L) {
                y * y
            } else {
                x * y * y
            }
        }
    }

    operator fun plus(that: GF): GF {
        return GF((this.x + that.x) % MOD)
    }

    operator fun minus(that: GF): GF {
        return GF((this.x - that.x + MOD) % MOD)
    }

    operator fun times(that: GF): GF {
        return GF((this.x * that.x) % MOD)
    }

    operator fun unaryMinus(): GF {
        return GF((-this.x + MOD) % MOD)
    }

    fun inv(): GF {
        return powGF(this, MOD - 2)
    }

    operator fun div(that: GF): GF {
        return this * that.inv()
    }
}

fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map(String::toInt)
    val edges = Array(n - 1) {
        val (a, b) = readLine()!!.split(" ").map(String::toInt)
        Edge(a - 1, b - 1)
    }

    val nextList = Array(n) {
        mutableListOf<Int>()
    }
    for (edge in edges) {
        nextList[edge.a].add(edge.b)
        nextList[edge.b].add(edge.a)
    }

    val queue: Queue<Int> = ArrayDeque()
    val visited = Array(n) { false }

    val numNextVisited = Array(n) { 0 }
    val score = Array(n) { -123 }

    queue.add(0)
    visited[0] = true
    score[0] = k

    while (queue.isNotEmpty()) {
        val current = queue.remove()
        for (next in nextList[current]) {
            if (!visited[next]) {
                queue.add(next)
                visited[next] = true

                score[next] = k - (1 + numNextVisited[current])
                numNextVisited[next]++
                numNextVisited[current]++
            }
        }
    }
    val result = score.map { GF(it.toLong()) }.fold(GF(1)) { x, y -> x * y }.x
    println(result)

}

Measured memory_bytes: 99576
import java.util.Arrays;
import java.util.Scanner;

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

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int a[] = new int[n];
		for(int i=0; i<n; i++) {
			a[i]=sc.nextInt();
		}
		Arrays.sort(a);
		int ans = a[0];

		while(true) {
			boolean ok=true;
			for(int i=0; i<n; i++) {
				int tmp=a[i]%ans;
				if(a[i]%ans != 0) {
					if(ans>tmp) {
						ok=false;
						ans=tmp;
						a[i]=tmp;
						break;
					}
				}
			}
			if(ok) {
				break;
			}
			Arrays.sort(a);
		}
		System.out.println(ans);
		sc.close();
	}

}


Measured memory_bytes: 50512
n = int(input())
S = list(input())

R = [0]*(n+1)
G = [0]*(n+1)
B = [0]*(n+1)

for i in range(n):
  if S[i]=='R':
    R[i+1] = 1
  if S[i]=='G':
    G[i+1] = 1
  if S[i]=='B':
    B[i+1] = 1
    
for i in range(1, n+1):
  R[i] += R[i-1]
  B[i] += B[i-1]
  G[i] += G[i-1]

ans = 0
for i in range(n):
  for j in range(i+1, n):
    color_selected = [S[i], S[j]]
    color_selected.sort()
    dif = j-i
    if color_selected == ['G', 'R']:
      ans += B[min(j+dif, n)] - B[j+1]
      ans += B[n] - B[min(j+dif+1, n)]
    elif color_selected == ['B', 'R']:
      ans += G[min(j+dif, n)] - G[j+1]
      ans += G[n] - G[min(j+dif+1, n)]
    elif color_selected == ['B', 'G']:
      ans += R[min(j+dif, n)] - R[j+1]
      ans += R[n] - R[min(j+dif+1, n)]

print(ans)

Measured memory_bytes: 69084
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    acc = [0] * (N + 1)
    for i in range(N):
        acc[i+1] = acc[i] + A[i]

    ans = INF
    for i in acc:
        ans = min(abs(acc[-1] - 2 * i ), ans)

    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 32572
# -*- coding: utf-8 -*-
"""
D - Five, Five Everywhere
https://abc096.contest.atcoder.jp/tasks/abc096_d

"""
import sys
from sys import stdin
input = stdin.readline


def create_prime_list(limit):
    """ エラトステネスの篩でlimitまでの素数リストを求める
    https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
    """
    x = limit**0.5
    primes = []
    nums = [x for x in range(2, limit+1)]
    while nums[0] <= x:
        primes.append(nums[0])
        current_prime = nums[0]
        nums = [x for x in nums if x % current_prime != 0]
    primes.extend(nums)
    return primes


def pick_numbers(N, primes):
    ans = []
    for p in primes:
        if p % 5 == 1:
            ans.append(p)
            if len(ans) == N:
                return ans
    return []


def main(args):
    primes = create_prime_list(55555)
    N = int(input())
    ans = pick_numbers(N, primes)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 5528
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  string s;
  cin >> s;
  cout << "2018/01/" << s[8] << s[9] << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define double long double
#define endl "\n" 
const int INF = (int) 1e9 + 9;
const int maxn = (int) 1e6 + 6;
//const mod = (int) 1e9 + 7;

using namespace std;

signed main() {
    int N, W;
    cin >> N >> W;

    vector<int> v(N), w(N);
    vector<vector<int> > dp(N+1, vector<int>(W+1));
    for(int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    dp[0][w[0]] = v[0];

    for(int i = 1; i < N; i++) {
        for(int j = 0; j <= W; j++) {
            if(j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]) + v[i];
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }

    int ans = 0;
    for(int i = 0; i <= W; i++) {
        ans = max(ans, dp[N-1][i]);
    }


    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

#define mem(ar,a)       memset(ar,a,sizeof ar)
#define iOS               ios_base::sync_with_stdio(false);cin.tie(NULL); 
#define pb(x)           push_back(x)
#define all(c)          c.begin(), c.end()
#define int             long long
#define ff              first
#define ss              second
#define nl              '\n'

int32_t main()
{
    iOS
    int n;cin>>n;
    cout<<n + n*n + n*n*n;
}



Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long ll;
#define print(x) cout<<(x)<<endl


#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007


// DONT USE "int", USE "ll" !!!!!!!!!!!!
int main() {
	int N, K;
	cin >> N >> K;

	int out = 1;

	for (int i = 0; i < N; i++) {
		if (out >= K)out += K;
		else out *= 2;
	}
	print(out);





	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
typedef long long int UINT;

int main(void)
{
	UINT n;
	UINT i;
	UINT fact;
	
	scanf("%lld", &n);
	
	fact = 1;
	for (i = 1; i <= n; i++){
		fact *= i;
	}
	
	printf("%lld\n",fact);
	
	return (0);
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;

ll min(ll *p1, ll *p2){
        ll m = p1[0];
        REP(i,p2-p1){
                if(p1[i] < m) m = p1[i];
        }
        return m;
}

ll max(ll *p1, ll *p2){
        ll m = p1[0];
        REP(i,p2-p1){
                if(p1[i] > m) m = p1[i];
        }
        return m;
}

int main(void)
{
        ll h, w;
        cin >> h >> w;
        ll inf[4];
        // h や w が 3 の倍数なら 0, そうでないなら 1
        inf[0] = (h%3) ? w : 0;
        inf[1] = (w%3) ? h : 0;
        ll s[3];
        ll smax, smin;
        ll diff;
        ll old = LONG_MAX;
        REP(i,h){
                s[0] = w/2 * (i+1);
                s[1] = (w+1)/2 * (i+1);
                s[2] = w * (h - i- 1);
                smax = max(s, s+3);
                smin = min(s, s+3);
                diff = smax - smin;
                if(old <= diff) break;
                old = diff;
        }
        inf[2] = old;
        old = LONG_MAX;
        REP(i,w){
                s[0] = h/2 * (i+1);
                s[1] = (h+1)/2 * (i+1);
                s[2] = h * (w - i- 1);
                smax = max(s, s+3);
                smin = min(s, s+3);
                diff = smax - smin;
                if(old <= diff) break;
                old = diff;
        }
        inf[3] = old;
        cout << min(inf, inf+4) << endl;
        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
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 const INF = 1e9;


int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> dist(n,vector<int>(n,INF));
    vector<tuple<int,int,int>> G;
    rep(i,n) dist[i][i] = 0;
    rep(i,m) {
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = c;
        dist[b][a] = c;
        G.emplace_back(a,b,c);
    }

    rep(k,n) {
        rep(i,n) {
            rep(j,n) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int res = 0;
    rep(iter,m) {
        int i = get<0>(G[iter]);
        int j = get<1>(G[iter]);
        int d = get<2>(G[iter]);
        bool ok = true;
        for(int x = 0; x < n; ++x) {
            for(int y = x+1; y < n; ++y) {
                if(dist[x][y] == dist[x][i] + d + dist[j][y] 
                || dist[x][y] == dist[x][j] + d + dist[i][y]) {
                    ok = false;
                }
            }
        }
        if(ok) res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = Integer.valueOf(sc.next());
        int b = Integer.valueOf(sc.next());
        int c = Integer.valueOf(sc.next());
        int d = Integer.valueOf(sc.next());
        int l = a+b;
        int r = c+d;
        System.out.println(whichLean(l,r));
        sc.close();
    }

    public static String whichLean(int l, int r) {
        if (l < r) {
            return "Right";
        } else if (l > r) {
            return "Left";
        } else {
            return "Balanced";
        }
    }
}

Measured memory_bytes: 21844
let input() = stdin.ReadLine()
let inputs() = input().Split()

let YN b = printfn "%s" (if b then "Yes" else "No")
let print x = printfn "%A" x
let printS (s: string) = printfn "%s" s

open System.Linq
open System.Text.RegularExpressions


let S = input()

seq {
    for s in Regex.Split(S, "[^ATGC]") do
        yield s.Length
}
|> Array.ofSeq
|> Array.max
|> print


Measured memory_bytes: 16720
n = int(input())
x = sorted(list(map(int,input().split(" "))))

d_min = 10**18
for i in range(min(x), max(x)+1):
  d = 0
  for j in range(len(x)):
    d += (i-x[j])**2
    
  if d<d_min:
    d_min = d
    
print(d_min)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  string s;
  cin >> s;

  int MAX = 0;
  vector<int> d(N, 0);
  REP(i, N){
    if(i != 0) d[i] += d[i-1];
    if(s[i] == ')') d[i]++;
    else d[i]--;
    chmax(MAX, d[i]);
  }

  REP(i, MAX) s = '('+s;

  d = vector<int>(s.size(), 0);
  REP(i, s.size()){
    if(i != 0) d[i] += d[i-1];
    if(s[i] == ')') d[i]--;
    else d[i]++;
  }

  REP(i, d.back()) s += ')';
  cout << s << "\n";

  return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(){
  int a,b;
  while(std::cin>>a>>b){
    if(!a&&!b)return 0;
    char c[101][101];
    for(int y=0;y<a;y++){
      std::string s;
      std::cin>>s;
      for(int x=0;x<b;x++)
        c[y][x] = s[x];
    }
    int r[101][101]={0},t_x=0,t_y=0;
    while(1){
      switch(c[t_y][t_x]){
      case '>':
        t_x++;
        break;
      case '<':
        t_x--;
        break;
      case 'v':
        t_y++;
        break;
      case '^':
        t_y--;
        break;
      }
      if(c[t_y][t_x]=='.'){
        std::cout<<t_x<<" "<<t_y<<std::endl;
        break;
      }
      if(r[t_y][t_x]){std::cout<<"LOOP"<<std::endl;break;}
      r[t_y][t_x]=1;
    }
  }
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main(void) {
	char tmp[1000];
	//?????¨?????????????????°?????°????????????
	fgets(tmp, sizeof(tmp), stdin);
	int loop=atoi(tmp);

	int spade[13] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
	int heart[13] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
	int dia[13] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
	int club[13] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };

	int i;
	//??????????????°?????????
	for (i = 0; i < loop;i++) {
		
		//???????????¨??°????????\????????????
		char mark;
		int num;
		scanf("%c %d\n", &mark, &num);

		//???????????§??????
		//??????????????°?????????????????¨??§????¶???§??????????????¨????¢????
		switch (mark) {
		case 'S':
			spade[num - 1] -= num;
			break;
		case 'H':
			heart[num - 1] -= num;
			break;
		case 'C':
			club[num - 1] -= num;
			break;
		case 'D':
			dia[num - 1] -= num;
			break;
		}

	}
	//??????????????°???????????????

	//???????????§????????????
	for (i = 0; i < 4;i++) {
		//?¶???????????????????????????????????????????
		//????????????????????????????????????????????????????????§?°???????????????????????????????
		int j;
		for (j=0;j<13;j++)
		switch (i) {
		case 0:
			//0?????¨???????¶??????????????????§??????????????????
			if (spade[j] == 0) break;
			printf("S %d\n", spade[j]);
			break;
		case 1:
			//0?????¨???????¶??????????????????§??????????????????
			if (heart[j] == 0) break;
			printf("H %d\n", heart[j]);
			break;
		case 2:
			//0?????¨???????¶??????????????????§??????????????????
			if (club[j] == 0) break;
			printf("C %d\n", club[j]);
			break;
		case 3:
			//0?????¨???????¶??????????????????§??????????????????
			if (dia[j] == 0) break;
			printf("D %d\n", dia[j]);
			break;

		}
		//???????????????
	}
	//???????????§??????????????????
	return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
// #define int ll
// #define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const int D=4,dx[]={+1,0,-1,0},dy[]={0,+1,0,-1};
const int N=3e5+5,K=400;
int p[N],l[N],r[N],a[N];
int32_t main(){
    int n,m;
    cin>>n>>m;
    forn(i,n){
        cin>>l[i]>>r[i];
        int pl=N;
        for(int k=1;k<=N;++k){
            int cl=(l[i]+k-1)/k,cr=r[i]/k;
            if(cl<K){
                if(min(cr,pl-1)>=K-1){
                    p[K]++;
                    p[min(cr,pl-1)+1]--;
                }
                break;
            }
            p[cl]++;
            p[min(cr,pl-1)+1]--;
            pl=cl;
        }
        for(int j=1;j<K;++j){
            int x=(l[i]+j-1)/j;
            if(x*j<=r[i])a[j]++;
        }
    }
    int ans=p[0];
    for(int i=1;i<=m;++i){
        ans+=p[i];
        cout<<ans+a[i]<<'\n';
    }
    return 0;
}

Measured memory_bytes: 6284
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define sz(x) ((int)(x).size())

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const int INF = 1 << 30;//10^9
const ll MOD = 1000000007;
//const ll MOD = 998244353;
double EPS = 1e-10;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A){printf("%.12lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

void solve(){
  while(true){
    int n, r;
    cin >> n >> r;
    if(n == 0 && r == 0) return;
    vector<int> now(n), ne(n);
    rep(i, n) now[i] = n - i;
    rep(_, r){
      int p, c;
      cin >> p >> c;
      rep(i, c){
        ne[i] = now[i+p-1];
      }
      rep(i, p-1){
        ne[i+c] = now[i];
      }
      rep(i, n-p-c+1){
        ne[i+p+c-1] = now[i+p+c-1];
      }
      now = ne;
    }
    cout << now[0] << endl;
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  solve();
}



Measured memory_bytes: 3224
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
int main(){
   double a,b,h,m;
   cin>>a>>b>>h>>m;
   double ans=a*a+b*b-2*a*b*cos(2*M_PI*((h+m/60)/12-m/60));
   printf("%.12lf\n",sqrt(ans));
   return 0;
}


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

const int N = 100;

int main(){
	int n, k, a[N];
	int b = -1, c = 0;
	cin >> k >> n;
	for(int i = 0;i < n;++i){
		cin >> a[i];
	}
	for(int i = 0;i < k;++i){
		int t = 0, id;
		for(int j = 0;j < n;++j){
			if(t < a[j] && b != j){
				id = j;
				t = a[j];
			}
		}
		if(t){
			--a[id];
			b = id;
		}
		else{
			--a[b];
			++c;
		}
	}
	cout << c << endl;
	return 0;
}


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

int main(){
	int n,m,i,cnt,x,min,max,cent;
	cin>>n;
	vector<int> num(n);
	for(i=0; i<n; i++){
		cin>>x;
		num[i]=x;
	}
	sort(num.begin(),num.end());
	cin>>m;
	int a[m];
	for(i=0; i<m; i++){
		cin>>a[i];
	}
	cnt=0;
	for(i=0; i<m; i++){
		min=0;
		max=num.size()-1;
		while(min<=max){
			cent=(min+max)/2;
			if(num[cent]==a[i]){
				cnt++;
				break;
			}else if(num[cent]<a[i]){
				min=cent+1;
			}else if(num[cent]>a[i]){
				max=cent-1;
			}
		}
	}
		
	cout<<cnt<<endl;
	
	return 0;
}


Measured memory_bytes: 3336
#include <iostream>
#include <string>
using namespace std;
#define ll long long

void solve() {
  string S;
  ll K;
  cin >> S >> K;

  ll pos = 0;
  for (ll si = 0; si < S.size(); si++) { 
    if (S[si] != '1') {
      pos = si; 
      break;
    }
  }

  if (K > pos) {
    cout << S[pos] << endl;
  } else {
    cout << '1' << endl;
  }

}

int main(void) {
  solve();  
  return 0;
}

Measured memory_bytes: 256
from itertools import product
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))

cnt = 0
for x in list(product([-1, 0, 1], repeat=n)):
  temp = a.copy() - np.array(x)
  if np.prod(temp) % 2 == 0:
    cnt+=1
print(cnt)
  



Measured memory_bytes: 20448
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using T = tuple<int, int, int>;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w, sx, sy, gx, gy;
  cin >> h >> w >> sx >> sy >> gx >> gy;
  --sx, --sy, --gx, --gy;
  vector<string> s(h);
  rep(i, h) cin >> s[i];
  vector<vector<int>> grid(h, vector<int>(w, INF));
  deque<T> deq;
  grid[sx][sy] = 0;
  deq.emplace_front(sx, sy, 0);
  while (!deq.empty()) {
    int x, y, cost;
    tie(x, y, cost) = deq.front();
    deq.pop_front();
    if (cost > grid[x][y])
      continue;
    rep(i, 4) {
      if (x+dx[i] < 0 || x+dx[i] >= h || y+dy[i] < 0 || y+dy[i] >= w)
        continue;
      if (s[x+dx[i]][y+dy[i]] == '#')
        continue;
      if (chmin(grid[x+dx[i]][y+dy[i]], cost))
        deq.emplace_front(x+dx[i], y+dy[i], cost);
    }
    for (int i = -2; i <= 2; i++) {
      for (int j = -2; j <= 2; j++) {
        if (x+i < 0 || x+i >= h || y+j < 0 || y+j >= w)
          continue;
        if (s[x+i][y+j] == '#')
          continue;
        if (chmin(grid[x+i][y+j], cost+1))
          deq.emplace_back(x+i, y+j, cost+1);
      }
    }
  }
  if (grid[gx][gy] == INF)
    cout << -1 << endl;
  else
    cout << grid[gx][gy] << endl;
  return 0;
}

Measured memory_bytes: 8828
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

int main(){
  double n,t,a,j;
  int i;
  vector <double> v,w;
  
  cin>>n>>t>>a;
  for(i=0;i<n;i++){
    cin>>j;
    if((t-j*0.006)>=a){
   v.push_back((t-j*0.006)-a);
   w.push_back((t-j*0.006)-a);}
    else{
      v.push_back(a-(t-j*0.006));
      w.push_back(a-(t-j*0.006));
    }
  }
  sort(v.begin(),v.end());
  for(i=0;i<n;i++){
    if(w[i]==v[0])
      break;
  }
  
  cout<<i+1<<endl;
  
  return 0;
  
}


Measured memory_bytes: 256
main(i,j,k,n,c){int a[3][3];for(i=0;i<3;i++)for(j=0;j<3;j++)scanf("%d",&a[i][j]);scanf("%d",&n);int b[n];for(i=0;i<n;i++)scanf("%d",&b[i]);for(i=0;i<3;i++)for(j=0;j<3;j++)for(k=0;k<n;k++)if(b[k]==a[i][j])a[i][j]=0;for(i=0;i<3;i++)if(((a[i][0]==a[i][1])&&(a[i][1]==a[i][2]))||((a[0][i]==a[1][i])&&(a[1][i]==a[2][i])))c=1;if(((a[0][0]==a[1][1])&&(a[1][1]==a[2][2]))||((a[0][2]==a[1][1])&&(a[1][1]==a[2][0])))c=1;c==1?puts("Yes"):puts("No");}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long int
#define fip ios_base::sync_with_stdio(false); cin.tie(NULL) 
#define reptUsual(b) for(i=0; i<b; ++i)
#define reptArIn(i,a,b,ar) for( i=a; i<b; ++i) cin>>ar[i];
#define rept(i,a,b) for(i=a; i<b; ++i)
#define maX(a,b)    ( (a) > (b) ? (a) : (b))
#define miN(a,b)    ( (a) < (b) ? (a) : (b))
#define pb(a) push_back(a)
#define bigPrime 1000000007
using namespace std;

ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 



int main()
{   
    fip; 
    ll a,b,c,d,i;
    cin>>a>>b>>c>>d;
    ll lcm = (c*d)/(gcd(c,d));
    //cout<<lcm<<"\n";
    ll a1=a/c;
    if(a%c!=0)
        a1++;

    ll a2=a/d;
    if(a%d!=0)
        a2++;

    ll a3=a/lcm;
    if(a%lcm!=0)
        a3++;

    ll b1 = b/c;
    ll b2 = b/d;
    ll b3 = b/lcm;
    /*
    ll a1 = (ll)(ceil((double)a/(double)c));
    ll b1 = (ll)(floor((double)b/(double)c));
    ll a2 = (ll)(ceil((double)a/(double)d));
    ll b2 = (ll)(floor((double)b/(double)d));
    ll a3 = (ll)(ceil((double)a/(double)lcm));
    ll b3 = (ll)(floor((double)b/(double)lcm));
    //cout<<a1<<" "<<a2<<" "<<a3<<"\n";
    //cout<<b1<<" "<<b2<<" "<<b3<<"\n";*/
    ll c1 = b1-a1+1;
    ll d1 = b2-a2+1;
    ll lcm1 = b3-a3+1;
    //cout<<c1<<" "<<d1<<" "<<lcm1<<"\n";
    ll res1 = (b-a+1);
    ll res2 =(c1+d1-lcm1);
    ll res = res1-res2;
    cout<<res;
    return 0;
    
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;

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

    int com = 1;
    char S[N];

    cin >> S[0];
    for(int i=1;i<N;i++){
      cin >> S[i];
      if(S[i-1]!=S[i]) com++;
    }

    int lastcom = max(1, com - 2*K);
    cout << N - lastcom <<endl;

    
  	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 998244353;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

ll fastPow(ll x, ll n)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

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

    int n, d[112345];

    int m[112345];

    int ma = 0;

    cin >> n;
    REP(i, n)
    {
        cin >> d[i];

        m[d[i]]++;

        ma = max(ma, d[i]);
    }

    ll res = 1;

    if (m[0] != 1)
    {
        cout << 0 << endl;
        return 0;
    }

    if (d[0] != 0)
    {
        cout << 0 << endl;
        return 0;
    }

    int i = 1;
    while (true)
    {
        if (m[i] == 0)
        {
            if (i - 1 != ma)
            {
                cout << 0 << endl;
                return 0;
            }
            break;
        }

        (res *= fastPow(m[i - 1], m[i])) %= MOD;

        i++;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int A,B,R;
	char op;
	
	cin >> A >> op >> B;
	
	if (op == '+') {
		cout << A+B << endl;
	}
	else {
		cout << A-B << endl;
	}
	
}

Measured memory_bytes: 256
n, k, q = gets.chop.split.map(&:to_i)
a = []


q.times { a << gets.to_i}


# nums = [].fill(k, 0, n)

count = Hash.new(0)

a.each do |elem|
  count[elem] += 1
end



for i in 0..n-1 do

  if k - q + count[i+1] > 0
    puts "Yes"
  else
    puts "No"
  end

end


Measured memory_bytes: 7220