akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>


int binarySearch(int A[], int key,int n){
	int left = 0;
	int right = n;
	int mid;
	while (left < right){
		mid = (left + right) / 2;
		if (A[mid] == key){
			return 1;
		}
		else if (key < A[mid]){
			right = mid;
		}
		else{
			left = mid + 1;
		}
	}
	return 0;
}

int main(){
	int S[100000],T[50000];
	int n,q;
	int count = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &S[i]);
	}
	scanf("%d", &q);
	for (int i = 0; i < q; i++){
		scanf("%d", &T[i]);
	}
	for (int i = 0; i < q; i++){
		if (binarySearch(S, T[i], n))
			count++;
	}
	printf("%d\n", count);
	return 0;
}

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

int main(){
	int a[110], i=1, b[110];
	vector<int> ans;
	for(int i=0 ; i<110 ; i++){
		b[i] = 0;
	}

	while(cin >> a[i]){
		if(i==100 || a[i]==-1)break;

		b[ a[i] ]++;
	}
	int num = 0;
	for(int i=1 ; i<=100 ; i++){
		if( num < b[i] ){
			ans.clear();
			num = b[i];
			ans.push_back(i);
		}
		else if( num == b[i] ){
			ans.push_back(i);
		}
	}

	sort( ans.begin() , ans.end() );
	for(int i=0 ; i<ans.size() ; i++){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 0
N,X = map(int,input().split())
a = [1]
p = [1]
for i in range(N):
    a.append(2*a[i]+3)
    p.append(2*p[i]+1)

def f(N,X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1+a[N-1]:
        return f(N-1, X-1)
    elif X == 2+a[N-1]:
        return p[N-1]+1
    elif 2+a[N-1] < X <= 2+2*a[N-1]:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])
    elif X == 3+2*a[N-1]:
        return 2*p[N-1] +1

print(f(N,X))

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

int main() {
  int H, W;
  bool loop = true;
  while (loop) {
    cin >> H >> W;
    if ((H == 0) && (W == 0)) {
      loop = false;
      continue;
    }
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        cout << "#";
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout << #x " = " << (x) << '\n';
#define P(x) cout << #x << '\n';    
#define int long long
typedef pair<int, int> pii;
const int mod = 1000000007;


int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(9);
	#ifdef LOCAL_DEFINE
		freopen("in.txt", "rt", stdin);
	#endif
	
	
	string s;
	cin >> s;
	int cnt = 0;
	int n = s.length();
	for(int i = 0; i <= (n - 1) / 2; ++ i)
	{
		if(s[i] != s[n - i - 1])
			++ cnt;
	}
	cout << cnt << '\n';
	
	return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
const int INF = 1000000001;

int N;
ll A[100001], B[100001];
ll ans = 0;

int main(){
  cin >> N;
  rep(i, N + 1) cin>>A[i];
  rep(i, N) cin>>B[i];
  
  rep(i, N){
    if(A[i] >= B[i]){
      ans += B[i];
    }else{
      ans += A[i];
      if(B[i] - A[i] > A[i+1]){
        ans = ans + A[i + 1];
        A[i+1] = 0;
      }else{
        ans  = ans + B[i] - A[i];
        A[i + 1] = A[i + 1] - B[i] + A[i];
      }
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdint>
#include<cstdlib>
template<typename T>
void fin(T const& t){ std::cout << t << std::endl; exit(0); }

template<typename T>
std::vector<std::vector<T>> mk2d(size_t s1, size_t s2, T const& val) {
  std::vector<T> tmp(s2, val);
  return std::vector<std::vector<T>>(s1, tmp);
}

int64_t const MOD = 998244353;

int main() {
  std::cin.tie(0); std::ios::sync_with_stdio(false);
  int N, S; std::cin >> N >> S;
  std::vector<int64_t> A(N);
  for(int i = 0; i < N; ++i) std::cin >> A[i];
  auto dp = mk2d(N+1, S+1, int64_t(0));
  dp[0][0] = 1;
  for(int i = 0; i < N; ++i) {
    // do not use A[i];
    for(int s = 0; s <= S; ++s) (dp[i+1][s] = dp[i][s]*2) %= MOD;
    // use A[i];
    for(int s = A[i]; s <= S; ++s) (dp[i+1][s] += dp[i][s-A[i]]) %= MOD;
  }
  fin(dp[N][S]);
  return 0;
}


Measured memory_bytes: 74148
#include <iostream>
#include <string>
#include <set>
using namespace std;
int  main() {
  
	int n;

	cin >> n;
	
	set<string> goods;

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

		string s;
		cin >> s;
		goods.insert(s);

	}
	cout << goods.size() << endl;
    return 0;
}


Measured memory_bytes: 15592
use std::io;

fn read_line() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s
}

macro_rules! from_line {
    ($($a:ident : $t:ty),+) => {
        $(let $a: $t;)+
        {
            let _line = read_line();
            let mut _it = _line.trim().split_whitespace();
            $($a = _it.next().unwrap().parse().unwrap();)+
                assert!(_it.next().is_none());
        }
    };
}

fn issquare(n: u64, p: u64) -> bool {
    if ((n as f64).powf(1.0/(p as f64)) as u64).pow(p as u32) == n {
        true
    }
    else {
        false
    }
}

fn main() {
    from_line!(x: u64);
    if x == 1000 {
        println!("1000");
    }
    else {
        let mut ret = false;
        for i in (1..x+1).rev() {
            if ret {
                break;
            }
            for j in 2..10 {
                if issquare(i, j) {
                    println!("{}", i);
                    ret = true;
                    break;
                }
            }
        }
    }
}


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

int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	vector<int> dp(n,2000000000);
	
	dp[0] = 0;
	dp[1] = abs(v[0] - v[1]);
	for (int i = 2; i < n; i++) {
		dp[i] = min(dp[i], min(dp[i - 1] + abs(v[i - 1] - v[i]), dp[i - 2] + abs(v[i - 2] - v[i])));
	}
	cout << dp[n - 1];
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n,m,x,y;cin>>n>>m>>x>>y;
  vector<int> N(n);
  vector<int> M(m);
  for(int i=0;i<n;i++){cin>>N[i];}
  for(int i=0;i<m;i++){cin>>M[i];}
  sort(N.begin(),N.end());
  reverse(N.begin(),N.end());
  sort(M.begin(),M.end());
  
  
  
  if(N[0]<M[0]&&x<M[0]&&N[0]<y&&y-1!=x){cout<<"No War"<<endl;}
  else{cout<<"War"<<endl;}}

Measured memory_bytes: 256
n, p = map(int, input().split())
a = list(map(int, input().split()))
os = list(filter(lambda x: x % 2 == 1, a))
es = list(filter(lambda x: x % 2 == 0, a))

def calc_even(o_num, e_num):
    if o_num < 0 or e_num < 0:
        return 0
    # 奇数の組み合わせ数
    res = 1
    tmp = 1
    for i in range(1, o_num // 2 + 1):
        tmp *= (o_num - i * 2 + 2) * (o_num - i * 2 + 1)
        tmp /= 2 * i * (2 * i - 1)
        res += tmp
    # 偶数の組み合わせ数
    res *= 2 ** e_num
    return res

def calc_odd(o_num, e_num):
    if o_num < 0 or e_num < 0:
        return 0
    # 奇数の組み合わせ数
    tmp = o_num
    res = tmp
    end = o_num if o_num % 2 == 1 else o_num-1
    for i in range(1, end // 2 + 1):
        tmp *= (o_num - i * 2 + 1) * (o_num - i * 2)
        tmp /= 2 * i * (2 * i + 1)
        res += tmp
    # 偶数の組み合わせ数
    res *= 2 ** e_num
    return res
if p == 0:
    res = calc_even(len(os), len(es))
    print(int(res))
else:
    res = calc_odd(len(os), len(es))
    print(int(res))

Measured memory_bytes: 9192
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

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

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

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

    vector<int> ans;
    int sz = inf;
    for(int i=0; i<n; i++){
        vector<int> prev(n, -1), dist(n, inf);
        dist[i] = 0;
        queue<int> que;
        que.emplace(i);
        while(que.size()){
            int cv = que.front(); que.pop();
            for(auto nv : G[cv]){
                if(dist[cv] + 1 < dist[nv]){
                    dist[nv] = dist[cv] + 1;
                    prev[nv] = cv;
                    que.emplace(nv);
                }
            }
        }

        for(int j=0; j<n; j++){
            if(i == j || dist[j] == inf) continue;

            for(auto nv : G[j]){
                if(nv == i){
                    vector<int> tmp;
                    for(int k=j; ; k=prev[k]){
                        tmp.emplace_back(k);
                        if(k == i) break;
                    }

                    if(sz > tmp.size()){
                        ans = tmp;
                        sz = tmp.size();
                    }
                }
            }
        }
    }

    if(sz == inf){
        cout << -1 << endl;
    }
    else{
        cout << sz << endl;
        sort(ans.begin(), ans.end());
        for(auto i : ans){
            cout << i + 1 << endl;
        }
    }

    return 0;
}

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

xyh = [None] * n 

for i in range(n):
    xyh[i] = list(map(int, input().split()))

isOk = False
i = 0
j = 0
constant = -1

for i in range(101):
    for j in range(101):

        constant = -1
        for xyhTemp in xyh:
            if xyhTemp[2] != 0:
                temp = xyhTemp[2] + abs(i - xyhTemp[0]) + abs(j - xyhTemp[1])

                if constant == -1:
                    constant = temp

                if constant != temp:
                    break
        else:

            for p in xyh:
                if p[2] == 0 and constant - abs(i - p[0]) - abs(j - p[1]) > 0:
                    break
            else:
                isOk = True
                break
        
    if isOk:
        break

print(i, j, constant)
        


Measured memory_bytes: 3188
def main():

    H1, M1, H2, M2, K = map(int, input().split())

    a = 60 * H1 + M1
    b = 60 * H2 + M2

    if b-a < K:
        return 0
    return b-a-K


if __name__ == '__main__':
    print(main())

Measured memory_bytes: 9168
//41
#include<iostream>
#include<complex>
#include<algorithm>

using namespace std;

typedef complex<double> P;

int main(){
  for(int n;cin>>n,n;){
    static bool g[5001][5001];
    fill_n(g[0],5001*5001,false);
    P p[3000];
    for(int i=0;i<n;i++){
      int y,x;
      cin>>y>>x;
      g[y][x]=true;
      p[i]=P(x,y);
    }
    int ans=0;
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
	if(i==j)continue;
	int k;
	P cp;
	for(k=0,cp=p[i];k<4;cp+=(p[j]-p[i])*pow(P(0,1),k),k++){
	  int y=cp.imag(),x=cp.real();
	  if(y<0||5000<y||x<0||5000<x||!g[y][x])break;
	}
	if(!(k<4)){
	  ans=max(ans,int(abs(p[j]-p[i])*abs(p[j]-p[i])+.5));
	}
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 25648
#include<iostream>
#include<string>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int N, a;
	cin >> N;
	if (N <= 90&&N>=65) {
		a = 1;
	}
	else if (N >= 97 && N <= 122) {
		a = 2;
	}
	else {
		a = 0;

	}
	cout << a << endl;
	return 0;
}


Measured memory_bytes: 3124
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	int root;
	Node[] T;
	int[] D;
	int[] H;
	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		T = new Node[n];
		
		for(int i = 0; i < n; i++) {
			T[i] = new Node(-1);
		}
		
		for(int i = 0; i < n; i++) {
			int id = sc.nextInt();
			int l = sc.nextInt();
			int r = sc.nextInt();
			T[id].left = l;
			T[id].right = r;
			if(T[id].left != -1) T[l].parent = id;
			if(T[id].right != -1) T[r].parent = id;
		}
		for(int i = 0; i < n; i++) {
			if(T[i].parent == -1) root = i;
		}
		
		//深さ
		Deque<Integer> deq = new ArrayDeque<>();
		D = new int[n];
		deq.push(root);
		while(!deq.isEmpty()) {
			int tmp = deq.pop();
			for(int i = 0; i < n; i++) {
				if(T[tmp].left == i) {
					deq.push(i);
					D[i] = D[tmp] + 1;
				}
			}
			for(int i = 0; i < n; i++) {
				if(T[tmp].right == i) {
					deq.push(i);
					D[i] = D[tmp] + 1;
				}
			}
		}
		
		//高さ
		H = new int[n];
		setHeight(root);
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++) {
			sb.append("node ");
			sb.append(i);
			sb.append(": parent = ");
			sb.append(T[i].parent);
			sb.append(", sibling = ");
			sb.append(getSibling(i));
			int deg = 0;
			if(T[i].right != -1) deg++;
			if(T[i].left != -1) deg++;
			sb.append(", degree = ");
			sb.append(deg);
			sb.append(", depth = ");
			sb.append(D[i]);
			sb.append(", height = ");
			sb.append(H[i]);
			sb.append(", ");
			if(T[i].parent == -1) sb.append("root\n");
			else if(T[i].left == -1 && T[i].right == -1) sb.append("leaf\n");
			else sb.append("internal node\n");
		}
		String s = sb.toString();
		System.out.print(s);
		
		sc.close();
	}
	
	int getSibling(int u) {
		if(T[u].parent == -1) return -1;
		if(T[T[u].parent].left != u && T[T[u].parent].left != -1) return T[T[u].parent].left;
		if(T[T[u].parent].right != u && T[T[u].parent].right != -1) return T[T[u].parent].right;
		return -1;
	}
	
	int setHeight(int u) {
		int h1 = 0;
		int h2 = 0;
		if(T[u].left != -1) h1 = setHeight(T[u].left) + 1;
		if(T[u].right != -1) h2 = setHeight(T[u].right) + 1;
		return H[u] = Math.max(h1, h2);
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}
class Node {
	int parent, left, right;
	public Node(int parent) {
		this.parent = parent;
	}
}


Measured memory_bytes: 26412
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}


int main()
{      
  fastio();
  int n,m,i,j,t;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)
  	cin>>a[i];
  ll ans=0;
  for(i=0;i<=63;i++)
  {
  	int num_zero=0;
  	int num_ones=0;
  	for(int j=0;j<n;j++) 
    { 
        if(a[j]%2==0) 
        	num_zero++; 
        else
        	num_ones++; 
        a[j]=a[j]>>1; 
    }
    ll k = (1ll << i) % mod;
    k = k * num_ones % mod;
    k = k *num_zero % mod;
    ans = (ans + k) % mod;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 2560
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	static int gcd(int a, int b) {

		if (b == 0)
			return a;

		return gcd(b, a % b);
	}

	public static void main(String args[]) throws Exception {
		MyScanner sc = new MyScanner();
		PrintWriter pr = new PrintWriter(System.out);

		char ch = sc.next().charAt(0);
		
		if(Character.isLowerCase(ch))
			pr.println('a');
		else
			pr.println('A');
		
		pr.close();
	}

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}


Measured memory_bytes: 32824
def upheap(a,i):
    if i == 0: return
    while i > 0:
        p = (i+1)/2-1
        if a[p] < a[i]:
            a[p],a[i]=a[i],a[p]
        i = p

def heapify(a,i):
    lid = (i+1)*2-1
    rid = (i+1)*2
    maxc = -1
    if lid < len(a):
        maxc = lid
    if rid < len(a):
        if a[maxc] < a[rid]:
            maxc = rid
    if maxc != -1:
        if a[i] < a[maxc]:
            a[i],a[maxc]=a[maxc],a[i]
            heapify(a,maxc)


def build_heap(a):
    for i in range(len(a)):
        j = len(a)-1-i # n-1 to 0
        heapify(a,j)

n = int(raw_input())
a = map(int,raw_input().split(' '))
build_heap(a)
print '',
print ' '.join(map(str,a))

Measured memory_bytes: 64920
#include<bits/stdc++.h>
using namespace std;
#define rep(_,a,b) for(int _=a;_<b;_++)
#define per(_,a,b) for(int _=b-1;_>=a;_--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define pb push_back
typedef long long ll;

int main(){
    unsigned long long ans=1,tmp;
    int n;
    scanf("%d",&n);
    bool flag1=1,flag2=1;
    rep(i,0,n){
        scanf("%llu",&tmp);
        if(flag1&&flag2&&tmp>(1000000000000000000/ans)&&ans<1000000000000000000){
            flag2=0;
        }
        if(flag1&&flag2) ans*=tmp;
        if(flag1&&flag2&&ans>1000000000000000000) flag2=0;
        if(flag1&&tmp==0){
            printf("0");
            flag1=0;
        }
    }
    if(flag1&&flag2==0){
        printf("-1");
    }
    if(flag1&&flag2)
    {
        printf("%llu",ans);
    }
}



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

#define pb push_back
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define int long long
#define ll long long


	
void solve(){
	int n, q, sum = 0;
	cin >> n;
	int a[n];
	map<int, int> mp;
	for(int i = 0 ; i < n ; i++){
		cin >> a[i];
		mp[a[i]]++;	
		sum += a[i];
	}
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		sum -= mp[x] * x;
		sum += mp[x] * y;
		mp[y] += mp[x];
		mp[x] = 0;
		cout << sum << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 10300
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).expect("");
    let iter = buf.split_whitespace();
    let mut v: Vec<T> = Vec::new();
    for i in iter {
        v.push(i.parse().ok().unwrap());
    }
    v
}

fn main() {
    let mut flag = false;
    let n:u64 = procon_read()[0];
    let mut bef = String::new();
    for i in 0..n {
        let v:Vec<u64> = procon_read();
        if v[0] == v[1] {
            bef = format!("{}1", bef);
        }else{
            bef = format!("{}0", bef);
        }
    }
    for i in 0..(bef.len()-2) {
        if &bef[i..(i+3 as usize)] == "111" {
            flag = true;
            break;
        }
    }
    if flag {
        println!("Yes");
    }else{
        println!("No");
    }
}

Measured memory_bytes: 2124
object Main extends App {
  var i = 0
  val sb = StringBuilder.newBuilder
  for(x <- io.Source.stdin.getLines() if x != "0") {
    i += 1
    sb.append("Case ").append(i).append(": ")
      .append(x).append('\n')
    // sb.append(s"Case $i : $x\n")
    // sb.append("Case " + i + ": " + x + "\n")
  }
  print(sb)
}


Measured memory_bytes: 48844
import java.util.Scanner;
public class Main{
    public static boolean prime(int x){
        if(x == 1)
            return false;
        else if(x == 2)
            return true;
        else if(x % 2 == 0)
            return false;
        else{
            for(int i = 3 ; i <= Math.sqrt(x) ; i += 2)
            {
                if(x % i == 0)
                    return false;
            }
            return true;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for(int i = 0 ; i < n ; i++)
        {
            int x = sc.nextInt();
            if(prime(x))
                count++;
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 40936
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#define WTF 11

using namespace std;

int n;
int q;
int v[1<<18], w[1<<18];
vector<pair<int, int>> dp[1<<WTF];

int fxxk(int x, vector<pair<int, int>>& brute_force) {
  if (x < (1 << WTF)) {
    return x;
  }
  int l = brute_force.size();
  for (int i = 0; i < l; i++) {
    brute_force.push_back({brute_force[i].first + w[x], brute_force[i].second + v[x]});
  }
  return fxxk(x/2, brute_force);
}

void solve(int u) {
    if (!dp[u].empty()) {
      return;
    }
    if (dp[u/2].empty()) {
      solve(u/2);
    }
    vector<pair<int, int>> wtf1, wtf2;
    for (pair<int, int> pii: dp[u/2]) {
      int ww = pii.first;
      int vv = pii.second;
      wtf1.push_back(pii);
      wtf2.push_back({ww + w[u], vv + v[u]});
    }
    int i = 0;
    int j = 0;
    while (true) {
      if (i == wtf1.size() && j == wtf2.size()) {
        break;
      } else if (i == wtf1.size()) {
        dp[u].push_back(wtf2[j++]);
      } else if (j == wtf2.size()) {
        dp[u].push_back(wtf1[i++]);
      } else if (wtf1[i] < wtf2[j]) {
        dp[u].push_back(wtf1[i++]);
      } else {
        dp[u].push_back(wtf2[j++]);
      }
    }
    for (int i = 1; i < dp[u].size(); i++) {
      if (dp[u][i].second < dp[u][i-1].second) {
        dp[u][i].second = dp[u][i-1].second;
      }
    }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &v[i], &w[i]);
  }
  dp[1].push_back({0, 0});
  dp[1].push_back({w[1], v[1]});
  for (int i = 1; i <= n && i < (1 << WTF); i++) {
    solve(i);
  }
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int u, l;
    scanf("%d %d", &u, &l);
    if (u < (1 << WTF)) {
      auto it = lower_bound(dp[u].begin(), dp[u].end(), make_pair(l+1, 0));
      if (it == dp[u].begin()) {
        printf("0\n");
      } else {
        printf("%d\n", (--it) -> second);
      }
    } else {
      vector<pair<int, int>> brute_force;
      brute_force.push_back({0, 0});
      brute_force.push_back({w[u], v[u]});
      int k = fxxk(u/2, brute_force);
      sort(brute_force.begin(), brute_force.end(), [] (auto x, auto y) {
        if (x.first == y.first) {
          return y.second < x.second;
        } else {
          return x.first < y.first;
        }
      });
      for (int j = 1; j < brute_force.size(); j++) {
        if (brute_force[j].second < brute_force[j-1].second) {
          brute_force[j].second = brute_force[j-1].second;
        }
      }
      int llllllll = brute_force.size();
      int p1 = dp[k].size() - 1;
      int p2 = 0;
      int ans = 0;
      while(p2 < llllllll && p1 >= 0) {
        if (dp[k][p1].first + brute_force[p2].first > l) {
          --p1;
        } else {
          ans = max(ans, dp[k][p1].second + brute_force[p2].second);
          ++p2;
        }
      }
      printf("%d\n", ans);
    }
  }
}


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

typedef long long LL;

template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar.size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}

int main(int argc, char const* argv[])
{
    int x,y,z;
    cin >> x >> y >> z;

    cout << x / (y + z) - (x - x/(y+z)*(y+z) < z) << endl;

    return 0;
}

// sortの仕方
// int a[N];
// array<int,N> ar;
// vector<int> v;
//
// sort(a, a+N); // 配列
// sort(ar.begin(), ar.end()); // array
// sort(v.begin(), v.end()); // vector 昇順
// sort(v.begin(), v.end(), greater<int>()); // 降順

// Template
// template <class T>
// T foomax(T x, T y){
//   if (x > y){
//     return x;
//   }else{
//     return y;
//   }
// }

// string を int に変換 stoi("1010")
// int を string に変換 to_string(1010)


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
const int INF = 1e18;

signed main(){
    int n, k; cin >> n >> k;
    int a[n];
    REP(i,n) cin >> a[i];
    sort(a,a+n);
    int ans = 0;
    REP(i,k) ans += a[i];
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define Fin             freopen("in.txt","r",stdin)
#define Fout            freopen("out.txt","w",stdout)
#define Case(T)         int T;for(scanf("%d",&T);T--;)
#define fo(i,a,b)              for(int i = a; i < b; ++i)
#define fd(i,a,b)              for(int i = a; i >= b; --i)
#define me(a,b) memset(a,b,sizeof(a))
#define fi(a,n,val)    fill(a,a+n,val);
#define Scand(n)       scanf("%d",&n);
#define Scans(s)       scanf("%s",s);
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b ? gcd(b,a%b): a; }
const int maxn = 110000 + 5;
const int INF = 0xffffff;

#ifndef ONLINE_JUDGE

#endif // ONLINE_JUDGE

char s[1500];
int w;

int main()
{
#ifndef ONLINE_JUDGE
    //Fin;
#endif // ONLINE_JUDGE
    scanf("%s",s+1);
    cin >> w;
    int len = strlen(s+1);
    if(w == 1){
        printf("%s",s+1);
        return  0;
    }
    fo(i,1,len){
        if(i%w == 1)
            cout << s[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MOD = 998244353;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr array<int, 4> dx = {1, 0, -1, 0};
constexpr array<int, 4> dy = {0, 1, 0, -1};
// constexpr int MOD = 100000000 + 7;

long long modpow(long long a, long long n)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

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

    int n;
    cin >> n;
    vector<int> d(n);
    int d_max = 0;
    bool cant = false;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        d[tmp]++;
        chmax(d_max, tmp);
        if (i == 0 && tmp != 0)
            cant = true;
        else if (i != 0 &&tmp == 0)
            cant = true;
    }

    int ans = 1;
    for (int i = 1; i <= d_max; i++)
    {
        ans = (ans * modpow(d[i - 1], d[i])) % MOD;
    }
    if (cant)
        ans = 0;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
# define ll int64_t
#define rep(i,n) for(ll i=0;i<n;i++)
#define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back

using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}


int main(){
    ll n,k,d[1000000],count=0,sum=0;
    cin>>n>>k;
    vector<ll> a(n),l(n);
    rep(i,n){
        cin>>a[i];
        d[a[i]]++;
        if(d[a[i]]==1) {
            count++;
        }
        l[a[i]-1]++;
    }
    if(count<=k){
        cout<<0<<endl;
        return 0;
    }else{
        sort(ALL(l),greater<ll>());
        rep(i,k) sum += l[i];
    }
    cout<<n-sum<<endl;
    return 0;
}


Measured memory_bytes: 6912
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
typedef long long ll;
typedef long double ld;
#define M(x,y) ((x)>(y)?(x):(y))
#define m(x,y) ((x)<(y)?(x):(y))
#define N 200001

int main() {
	int k, a, b;
	scanf("%d %d %d", &k, &a, &b);
	Rep(i, a, b + 1) {
		if (i % k == 0) { printf("OK"); return 0; }
	}
	printf("NG");
	return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, maxn = 303030;
int mul(long long a, long long b){
	return a * b % mod;
}
int xp(int a, int b){
	int r = 1;
	for(; b; b >>= 1, a = mul(a, a)) if(b&1) r = mul(r, a);
	return r;
}
int fat[maxn], ifat[maxn];
void init(){
	fat[0] = 1;
	for(int i = 1; i < maxn; i++) fat[i] = mul(i, fat[i - 1]);
	ifat[maxn - 1] = xp(fat[maxn - 1], mod - 2);
	for(int i = maxn - 2; i >= 0; i--) ifat[i] = mul(i + 1, ifat[i + 1]);
}
int ncr(int n, int r){
	if(n < r) return 0;
	return mul(fat[n], mul(ifat[r], ifat[n - r]));
}
int main(){
	init();
	int n, a, b; long long k; cin >> n >> a >> b >> k;
	int ans = 0;
	for(int i = 0; i <= n; i++){
		long long nk = k - 1ll * a * i;
		if(nk >= 0 && (nk%b) == 0 && nk/b <= n){
			ans += mul(ncr(n, i), ncr(n, nk/b));
			if(ans >= mod) ans -= mod;
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 2560
N, C, K = [int(x) for x in input().split()]
T_lst = [int(input()) for i in range(N)]
T_lst.sort()

bus = 1
st = T_lst[0]
num = 1
for i in range(1, N):
    if T_lst[i] <= st + K and num < C:
        num += 1
    else:
        bus += 1
        st = T_lst[i]
        num = 1
print(bus)


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

int main(void){
  int N;
  cin >> N;
  
  vector<int> t(1000000 +2);
  vector<int> x(1000000 +2);
  vector<int> y(1000000 +2);
  
  t.at(0) = 0;
  x.at(0) = 0;
  y.at(0) = 0;
  
  for (int i = 1; i <= N; i++) {
    cin >> t.at(i) >> x.at(i) >> y.at(i);
  }
  
  bool can = true;
 
  
  for (int i = 0; i < N; i++) {
    int dt = t.at(i+1) - t.at(i);
    int dist =  abs(x.at(i+1) - x.at(i)) + abs(y.at(i+1) - y.at(i));
    if (dt < dist) {
      can = false;
    }
    if (dt % 2 != dist % 2) {
      can = false;
    }
  }
  
  if (can) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 12032
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();
    int c = sc.nextInt();

    int[] b = new int[m];
    for (int i = 0; i < m ; i++ ) {
      b[i] = sc.nextInt();
    }

    int count = 0;

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

      int sum = 0;
      for (int j = 0; j < m ; j++ ) {
        int a = sc.nextInt();
        sum += a * b[j];
      }

      int result = sum + c;

      if (result > 0) {
        count++;
      }
    }

    System.out.println(count);
  }
}


Measured memory_bytes: 23892
// Why am I so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

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

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int mod = 998244353;
const int MAXN = (int)3e5 + 5;

int fact[MAXN], rev[MAXN];

ll a, b, k;

int n, ans;

int binPow(int a, int b, int m = mod) {
	int ret = 1;

	for (; b > 0; b >>= 1) {
		if (b & 1) {
			ret = (ret * 1ll * a) % m;
		}

		a = (a * 1ll * a) % m;
	}

	return ret;
}

void pre() {
	fact[0] = 1;

	for (int i = 1; i <= 300000; ++i) {
		fact[i] = (fact[i - 1] * 1ll * i) % mod;
	}

	for (int i = 0; i <= 300000; ++i) {
		rev[i] = binPow(fact[i], mod - 2);
	}
}

void addMod(int &a, int b, int m = mod) {
	a += b;

	if (m <= a) {
		a -= m;
	}	
}

int C(int n, int k) {
	return fact[n] * 1ll * rev[k] % mod * rev[n - k] % mod;	
}

void solve() {                   
	scanf("%d %lld %lld %lld", &n, &a, &b, &k);

    for (int x = 0; x <= n; ++x) {
    	ll left = k - a * x;

    	if (left < 0) {
    		break;
    	}

    	if (left % b || left / b > n) {
    		continue;
    	}

    	int y = left / b;
    	addMod(ans, C(n, x) * 1ll * C(n, y) % mod);
    }

    printf("%d\n", ans);
}

int main() {    
    int tt = 1;

    pre();

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
void chmin(LL& a, LL b) {
	a = min(a, b);
}
//////////////

void solve() {
	int N;
	cin >> N;
	vector<pair<LL,int>> A(N);

	for (int i = 0; i < N; ++i) {
		cin >> A[i].first;
		A[i].second = i;
	}

	sort(A.begin(), A.end());
	reverse(A.begin(), A.end());
	vector< vector<LL> > dp(N + 1, vector<LL>(N + 1, 0));
	for (int i = 0; i < N; ++i) {
		for (int L = 0; L <= i; ++L) {
			int R = i - L;
			//dp[L][R];
			int ter = L + R;
			//左に配置
			chmax(dp[L + 1][R], dp[L][R] + A[ter].first * abs(A[ter].second - L));
			
			//右に配置
			chmax(dp[L][R + 1], dp[L][R] + A[ter].first * abs(N-1-R - A[ter].second));
		}
	}
	LL ans = 0;
	for (int L = 0; L <= N; ++L) {
		int R = N - L;
		chmax(ans, dp[L][R]);
	}
	cout << ans << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 34612
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int ONE=100000;
int ZERO=100001;
int PW=1000;
int TMPAND=100002;

int x[201000];
queue<int> q;
stringstream os;
int cnt;

void add(int a,int b,int c) {
	cnt++;
	os<<"+ "<<a<<" "<<b<<" "<<c<<"\n";
	x[c]=x[a]+x[b];
}
void les(int a,int b,int c) {
	cnt++;
	os<<"< "<<a<<" "<<b<<" "<<c<<"\n";
	if (x[a]<x[b]) x[c]=1; else x[c]=0;
}

int newempty() {
	assert(!q.empty());
	int u=q.front();
	q.pop();
	return u;
}

int cand(int p,int q) {
	int r=newempty();
	add(p,q,TMPAND);
	les(ONE,TMPAND,r);
	return r;
}
int powx(int p,int c) {
	int r=newempty();
	add(p,r,r);
	rep(i,0,c) add(r,r,r);
	return r;
}

int ifthen(int cond,int p) { // if (cond) q=p else q=0
	int q=newempty();
	int p1=newempty();
	add(p,ONE,p1);
	int cursum=newempty();
	int tmpcur=newempty();
	int cc=newempty();
	for (int i=29;i>=0;i--) {
		add(cursum,PW+i,tmpcur);
		les(tmpcur,p1,cc);
		add(powx(cand(cc,cond),i),q,q);
		add(powx(cc,i),cursum,cursum);
	}
	return q;
}
int main() {
	//scanf("%d%d",x+0,x+1);

	add(0,1,ONE);
	les(ZERO,ONE,ONE);
	add(PW,ONE,PW);
	rep(i,0,31) add(PW+i,PW+i,PW+i+1); // pw[31]
	rep(i,10000,99999) q.push(i);
	int p1=newempty();
	add(0,ONE,p1);

	int cursum=newempty();
	int tmpcur=newempty();
	int cc=newempty();
	for (int i=29;i>=0;i--) {
		add(cursum,PW+i,tmpcur);
		les(tmpcur,p1,cc);
		add(powx(ifthen(cc,1),i),2,2);
		add(powx(cc,i),cursum,cursum);
	}
	printf("%d\n",cnt);
	printf("%s\n",os.str().c_str());
	//printf("%d\n",x[2]);
}

Measured memory_bytes: 5324
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,bool> Pair;
const long long INF = 1LL<<60;

int main(){

string S;
long long temp;
bool flg = true;

cin >> S;

temp = ((S.length() + 3)/2)-1;

for(long long i = 0;i < (S.length()-1)/2;++i)    if(S[i] != S[temp+i])        flg = false;

if(flg) cout << "Yes" << endl;
else cout << "No" << endl;

return 0;

}   


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define Ans(f, y, n) if(f) cout << y << endl; else cout << n << endl;
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i, v.size()){ cout << v[i] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

template<typename T> void readv(vector<T> &a){ REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a){ REP(i, a.size()){cin >> a[i]; a[i]--;} }

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};

int mod = 1000000007;
//int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod

struct edge{int to, cost;};

class Graph
{
public:
    int N;
    vector<vector<edge>> G;
    vec dp;

    Graph(int N): N(N){
        G = vector<vector<edge>>(N, vector<edge>(0));
        dp.resize(N);
    }

    void add_edge(int from, int to, int cost = 0){
        G[from].push_back(edge({to, cost}));
    }

    void add_edge2(int v1, int v2, int cost = 0){
        add_edge(v1, v2, cost);
        add_edge(v2, v1, cost);
    }

    void dfs(int v, int p = -1){
        dp[v] = 0;
        int z = 0;
        for(auto e: G[v]) if(e.to != p){
            dfs(e.to, v);
            dp[v] += dp[e.to];
            if(dp[e.to] == 0) z++;
        }
        if(z > 1) dp[v] += z - 1;
    }

};

signed main(){

    int N; cin >> N;
    Graph G(N);
    int a, b;
    REP(i, N - 1){
        cin >> a >> b;
        G.add_edge2(a, b);
    }
    //int r, c;
    vec r, c;
    IREP(i, N) if(SZ(G.G[i]) == 1){
        //r = i;
        //c = G.G[r][0].to;
        //break;
        r.pb(i);
        c.pb(G.G[i][0].to);
    }
    int ans = INF;
    REP(i, min(30LL, SZ(r))){
        G.dfs(r[i]);
        int tmp = G.dp[c[i]] + 1;
        Min(ans, tmp);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 12928
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(int a, int b) {
	return a > b;
}

int main() {
	string s;
	cin >> s;
	llint ans = 0;
	llint cnt = 0;
	rep(i, s.size()) {
		if (s[i] == 'A')cnt++;
		if (s[i] == 'B') {
			if (cnt == 0)continue;
			i++;
			if (i >= s.size())break;
			if (s[i] == 'C') {
				ans += cnt;
			}
			else if (s[i] == 'A') {
				cnt = 1;
			}
			else {
				cnt = 0;
			}
		}
		else if (s[i] == 'C') {
			cnt = 0;
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 100

int H, W;
char c[MAX + 1][MAX + 1];

int main() {
	cin >> H >> W;
	for( int i = 1; i <= H; i++ ) {
		for( int j = 1; j <= W; j++ ) {
			cin >> c[i][j];
		}
	}

	for( int i = 1; i <= H * 2; i++ ) {
		for( int j = 1; j <= W; j++ ) {
			cout << c[(i+1)/2][j];
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long;
using ll = long long;
#define rep(i,n) for(lint (i) = 0;(i) < (lint)(n);(i)++)
#define repInRange(i,start,end) for(lint (i) = (start);(i) < (end);++(i))
using lpair = pair<lint,lint>;
using Vecint = vector<lint>;
using Llist = list<lint>;

ll pow(ll k,ll l) {
	ll ret = 1;
	rep(i,l) {
		ret *= k;
	}
	return ret;
}

template <typename T>
T sum(vector<T> vec) {
	ll ret = 0;
	rep(i,vec.size()) {
		ret += vec.at(i);
	}
	return ret;
}

void Main() {
	string s;
	cin >> s;
	if (s.size() % 2 == 1) {
		cout << "No" << '\n';
		return;
	}
	rep (i,s.size()/2) {
		if (s[i*2] != 'h' || s[i*2+1] != 'i') {
			cout << "No" << '\n';
			return;
		}
	}
	cout << "Yes" << '\n';
}

signed main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	Main();
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
int main()
{
	int n,k;
	int a[Max];
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	int minn=inf;
	for(int i=k;i<=n;i++)
	{
		minn=min(minn,a[i]-a[i-k+1]);
	}
	printf("%d\n",minn);
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
    char s[4];
    
    for(int i = 0; i < 4; i++){
        cin >> s[i];
    }

    if(s[0] == s[1] && s[0] == s[2] && s[2] == s[3]) cout << "No\n";
    else if(s[0] == s[1]){
        if(s[2] == s[3]) cout << "Yes\n";
        else cout << "No\n";
    }
    else if (s[0] == s[2]){
        if(s[1] == s[3]) cout << "Yes\n";
        else cout << "No\n";
    }
    else if (s[0] == s[3]){
        if(s[1] == s[2]) cout << "Yes\n";
        else cout << "No\n";
    }
    else cout << "No\n";

    return 0;
}


Measured memory_bytes: 256
import copy

N = input()
S = list(map(int, input()[:]))
left = [False for i in range(10)]
right = [0 for i in range(10)]

for n in S[1:]:
    right[n] += 1
left[S[0]] = True
flag = [[[False for i in range(10)] for j in range(10)] for k in range(10)]
for n in S[1:-1]:
    right[n] -= 1
    for i, l in enumerate(left):
        if l:
            for j, r in enumerate(right):
                if r > 0:
                    flag[n][i][j] = True
    left[n] = True
count = 0
for i in flag:
    for j in i:
        for k in j:
            if k:
                count += 1
print(count)


Measured memory_bytes: 9868
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=2010;
int n,tt;
bool w[N];
int head[N],to[N],nxt[N],a[N],in[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline int gcd(int x,int y) {return y?gcd(y,x%y):x;}
inline void dfs(int x) {
    w[x]=1;
    for(int i=1;i<=n;i++)
	if(!w[i]&&gcd(a[x],a[i])>1) {
	    to[++tt]=i,nxt[tt]=head[x],head[x]=tt;
	    ++in[i],dfs(i);
	}
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi();
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
	if(!w[i]) dfs(i);
    for(int t=1;t<=n;t++)
	for(int x=n;x;x--)
	    if(!in[x]) {
		--in[x],printf("%d ",a[x]);
		for(int i=head[x];i;i=nxt[i]) --in[to[i]];
		break;
	    }
    return 0;
}

Measured memory_bytes: 384
from collections import deque
d = deque()
X = input()
for c in X:
    if d:
        last = d.pop()
        if last == "S" and c == "T":
            pass
        else:
            d.append(last)
            d.append(c)
    else:
        d.append(c)
print(len(d))


Measured memory_bytes: 48352
#include <bits/stdc++.h>
using namespace std;
long long int Fac[1000010]; 
long long int Inv(long long int a, long long int m) {
	long long int c[50];
	long long int e[50];  
	c[0] = (m-2) % 2, e[0] = (m-2) / 2; 
	for (int i = 0; i < 49; ++i){
		c[i+1] = e[i] % 2;
		e[i+1] = e[i] / 2;  
	}
	long long int d[50]; 
	d[0] = a; 
	for (int j = 0; j < 49; ++j){
		d[j+1] = (d[j] * d[j]) % m; 
	}
	long long int Q = 1; 
	for(int k = 0; k < 49; ++k){
		if(c[k]) Q = (Q * d[k]) % m; 
	}
	return Q;
}
int main(){
	int N; 
	cin >> N; 
	long long int P = 1000000007; 
	Fac[0] = 1; 
	for(int i = 1; i <= 1000005; i++){
		Fac[i] = (long long) i * Fac[i-1] % P; 
	}
	long long int ans1 = (long long) (N-1) * Fac[N-1] % P; 
	long long int ans2 = 0; 
	for(int i = N-2; i >= (N+1) / 2; i--){
		long long int tmp = (((Fac[i-1] * Fac[i]) % P) * Inv(Fac[2*i-N], P)) % P; 
		ans2 = (ans2 + tmp) % P; 
	}
	cout << (ans1 + P - ans2) % P << endl; 
}

Measured memory_bytes: 8192