akhauriyash/Code-Regression huggingface dataset:
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;

int main(){
    long long n;
    cin >> n;
    long long N=n,ans=n;
    for(long long i=2; i*i<=N; i++){
        if(n%i==0){
            while(n%i==0){
                n/=i;
            }
            ans=ans*(i-1)/i;
        }
    }
    if(n>1) ans=ans*(n-1)/n;
    cout << ans << endl;
}



Measured memory_bytes: 3104
function main()
  
  (N,M) = map(x -> parse(Int,x), split(readline()))
  
  A = ["" for i in 1:N,j in 1:N]
  B = ["" for i in 1:M]
  
  count = 0
  check = false
  
  for i in 1:N
    A[i,:] = split(chomp(readline()),"")
  end
  
  for i in 1:M
    B[i] = chomp(readline())
  end
  
  
  for i in 1:N, j in 1:N-M+1
    
    if B[1] == join(A[i,j:j+M-1])

      for k in 1:M
        if i+k-1 <= N && B[k] == join(A[i+k-1,j:j+M-1])
          count += 1
        end
      end
      
      if count == M
        check = true
        break
      else
        count = 0
      end
      
    end
    
  end

  if check
    println("Yes")
  else
    println("No")
  end
  
end

main()

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

#define int           long long
#define S             second
#define F             first
#define pb            push_back
#define all(c)        (c).begin(),(c).end()
#define rall(c)       (c).rbegin(),(c).rend() 
#define lb            lower_bound
#define si(c)         (int)((c).size())
#define lcm(a, b)      (a * (b / __gcd(a,b)))  
#define inf           (long long)(1e15)
#define endl          '\n'
#define mp            make_pair
#define time(s)       (double(clock()-s)/double(CLOCKS_PER_SEC))
#define debug(args...)    _F(#args, args)
#define vi            std::vector<int>
#define pii           pair<int, int> 
#define vpi           vector<pii>

clock_t start;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template<typename T> void _F(const char *name, T arg1){
    cerr << name << " = " << arg1 << endl;
}template<typename T, typename... Args> void _F(const char *names, T arg1, Args... args){
    const char *name = strchr(names, ',');
    cerr.write(names, name-names) << " = " << arg1 << endl;
    _F(name+2, args...);
}
template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2> &q){
    in >> q.F >> q.S; return in;
}template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2> &q){
    out << q.F << " " << q.S; return out;
}template< typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> p1, pair<T1, T2> p2){
    return {p1.F+p2.F, p1.S+p2.S};
}template< typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> p1, pair<T1, T2> p2){
    return {p1.F-p2.F, p1.S-p2.S};
}


void solve(){
    int n;
    cin >> n;
    int cnt[n+1] = {0};
    for(int i = 1; i < n; i++){
        int x;
        cin >> x;
        cnt[x]++;
    }
    for(int i = 1; i <= n; i++){
        cout << cnt[i] << endl;
    }
}

signed main(){

    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);   

    int t = 1;
    start = clock(); 

    cout << fixed << setprecision(12);

    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin); 
    // freopen("output.txt", "w", stdout);
    // freopen("error.txt", "w", stderr);
    // #endif

    //cin >> t;

    for(int i = 1; i <= t; ++i){
        solve();
        //cout << endl;
    }
    //cerr << time(start);
    return 0;
}

Measured memory_bytes: 5184
ans = 1145141919

def dfs(board,y,x,dis,count):
    global ans
    if count <= 10 and count < ans:
        if (board[y][x] == '3'):
            ans = min(ans,count)
        else:
            if (0 <= y+dis[0] < h) and (0 <= x+dis[1] < w):
                if board[y+dis[0]][x+dis[1]] != '1':
                    dfs(board,y+dis[0],x+dis[1],dis,count)
                else:
                    board[y+dis[0]][x+dis[1]] = '0'
                    for ddd in dydx:
                        ppy = y + ddd[0]
                        ppx = x + ddd[1]
                        if (0 <= ppy < h) and (0 <= ppx < w):
                            if (board[ppy][ppx] != '1'):
                                dfs(board,ppy,ppx,(ddd[0],ddd[1]),count+1)
                    board[y+dis[0]][x+dis[1]] = '1'

while True:
    try:
        w,h = map(int , input().split())
        if ((not w) and (not h)):
            break
        board = [list(input().split()) for i in range(h)]
        for y,row in enumerate(board):
            try:
                spos = (y,row.index("2"))
                break
            except ValueError:
                pass
        dydx = [[-1,0],[1,0],[0,-1],[0,1]]

        for dd in dydx:
            py = spos[0]+dd[0]
            px = spos[1]+dd[1]
            if (0 <= py < h) and (0 <= px < w):
                if (board[py][px] != '1'):
                    dfs(board,py,px,(dd[0],dd[1]),1)

        if ans == 1145141919 :
            print('-1')
        else:
            print(ans)

        ans = 1145141919
    except:
        break


Measured memory_bytes: 5676
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;

vector<P>E[100000];
ll d1[100000],d2[100000];
P p1[100000],p2[100000];
int u[200000],v[200000],d[200000];
ll dp1[100000],dp2[100000];

signed main(){
	int n,m,s,t;scanf("%d%d%d%d",&n,&m,&s,&t);s--;t--;
	rep(i,m){
		scanf("%d%d%d",&u[i],&v[i],&d[i]);u[i]--;v[i]--;
		E[u[i]].push_back(P(d[i],v[i]));
		E[v[i]].push_back(P(d[i],u[i]));
	}
	
	priority_queue<P,vector<P>,greater<P>>que;
	memset(d1,0x3f,sizeof(d1));
	d1[s]=0;que.push(P(0,s));
	while(!que.empty()){
		P p=que.top();que.pop();
		if(d1[p.second]!=p.first)continue;
		for(auto u:E[p.second]){
			if(d1[u.second]>p.first+u.first){
				d1[u.second]=p.first+u.first;
				que.push(P(d1[u.second],u.second));
			}
		}
	}
	
	memset(d2,0x3f,sizeof(d2));
	d2[t]=0;que.push(P(0,t));
	while(!que.empty()){
		P p=que.top();que.pop();
		if(d2[p.second]!=p.first)continue;
		for(auto u:E[p.second]){
			if(d2[u.second]>p.first+u.first){
				d2[u.second]=p.first+u.first;
				que.push(P(d2[u.second],u.second));
			}
		}
	}
	
	rep(i,n){
		p1[i].first=d1[i];
		p1[i].second=i;
	}
	rep(i,n){
		p2[i].first=d2[i];
		p2[i].second=i;
	}
	
	sort(p1,p1+n);
	sort(p2,p2+n);
	
	dp1[s]=1;
	rep(i,n){
		for(auto u:E[p1[i].second]){
			if(d1[u.second]==p1[i].first+u.first){
				(dp1[u.second]+=dp1[p1[i].second])%=MOD;
			}
		}
	}
	
	dp2[t]=1;
	rep(i,n){
		for(auto u:E[p2[i].second]){
			if(d2[u.second]==p2[i].first+u.first){
				(dp2[u.second]+=dp2[p2[i].second])%=MOD;
			}
		}
	}
	
	ll ans=dp1[t]*dp1[t];
	
	rep(i,n){//頂点で重なる
		if(d1[i]+d2[i]!=d1[t])continue;
		if(d1[i]==d2[i]){
			ans=(ans+MOD-(dp1[i]*dp1[i]%MOD*dp2[i]%MOD*dp2[i])%MOD)%MOD;
		}
	}
	rep(i,m){//辺(頂点を除く)で重なる
		if(d1[u[i]]>d1[v[i]])swap(u[i],v[i]);
		if(d1[u[i]]+d[i]!=d1[v[i]])continue;
		if(d1[u[i]]+d2[v[i]]+d[i]!=d1[t])continue;
		ll L1=d1[u[i]]+1,R1=d1[u[i]]+d[i]-1;
		ll L2=d2[v[i]]+1,R2=d2[v[i]]+d[i]-1;
		if(!(R2<L1||R1<L2)){
			ans=(ans+MOD-(dp1[u[i]]*dp1[u[i]]%MOD*dp2[v[i]]%MOD*dp2[v[i]])%MOD)%MOD;
		}
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 22520
from collections import Counter
N = int(input())
A = list(map(int, input().split()))


def xor_circle(N, A):
    if sum(A) == 0:
        return "Yes"
    if N % 3 != 0:
        return "No"

    B = Counter(A)
    if len(B) == 3:
        a, b, c = B.keys()
        Na, Nb, Nc = B.values()
        if a ^ b ^ c == 0 and Na == Nb == Nc:
            return "Yes"
        else:
            return "No"
    elif len(B) == 2:
        a, b = B.keys()
        Na, Nb = B.values()
        if a == 0 and 2*Na == Nb:
            return "Yes"
        elif b == 0 and Na == 2*Nb:
            return "Yes"
        else:
            return "No"
    else:
        return "No"


ans = xor_circle(N, A)
print(ans)


Measured memory_bytes: 14468
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define all(v) v.begin(),v.end()
#define itr(r,v) for(auto r=v.begin();r!=v.end();r++)
#define FOR(i,n) for(ll i=0;i<n;i++)
#define ffo(i,a,b) for(ll i=a;i<=b;i++)
#define rfr(i,a,b) for(ll i=a;i>=b;i--)
#define space cout<<"\n\n";
#define endl "\n"
#define pqmx priority_queue<ll>
#define pqmn priority_queue<ll,vll,greater<ll>>
#define fps(x,y) fixed<<setprecision(y)<<x
#define merg(a,b,c) set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()))
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define ctime auto sttart = high_resolution_clock::now()
#define etime auto sttop = high_resolution_clock::now()
#define go_t ll testcases; cin>>testcases; for(ll caseno= 1 ;caseno <= testcases; caseno++)
#define ptime auto z1z = duration_cast<microseconds>(sttop-sttart); cout<<"\nTime taken : "<<z1z.count()<<" microseconds\n"
#define dbg1(x)             cout <<#x<<": "<<x<<'\n';
#define dbg2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<'\n';
#define dbg3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<'\n';
#define dbg4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<'\n';
#define dbg5(a, b, c, d, e) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<'\n';

using namespace std;
using namespace std::chrono;

const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
const ll maxN = 2e5 + 5;
const ll MAX_SIZE = 2e6 + 6;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double PI = 3.14159265359;

ll powerM(ll x, ll y, ll M = MOD) { // default argument
	ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v;
}

ll power(ll x, ll y) {
	ll v = 1; while (y > 0) {if (y & 1)v = v * x; y = y >> 1; x = x * x;} return v;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	FIO
	ll n, W; cin >> n >> W;
	ll wt[n], val[n];
	FOR(i, n) cin >> wt[i] >> val[i];
	// Linear dp - by taarasinh
	ll dp[W + 1] = {};
	FOR(i, n) {
		for (ll j = W; j >= 1; j--) {
			if (wt[i] <= j) {
				dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
			}
		}
	}
	cout << dp[W];
	return 0;
}


Measured memory_bytes: 4396
(* O(n!) *)
let n, m = Scanf.scanf " %d %d" @@ fun n m -> n, m
let g = Array.make n []
let visited = Array.make n false
let ans = ref 0
let c = ref 0
let rec dfs i v =
    if i >= n then incr ans
    else
      (visited.(v) <- true;
      for j = 0 to n - 1 do
        if not visited.(j) then
          let f v2 = if v2 = j then dfs (i + 1) v2 in
          List.iter f g.(v);
          visited.(j) <- false
      done)
let _ =
  for _ = 1 to m do
    Scanf.scanf " %d %d" @@ fun u v ->
      let u, v = u - 1, v - 1 in
      g.(u) <- v :: g.(u);
      g.(v) <- u :: g.(v);
  done;
  dfs 1 0;
  Printf.printf "%d\n" !ans

Measured memory_bytes: 1024
#include<stdio.h>

int main(){
  int x, y, n;

  scanf("%d %d", &x, &y);
  
  if(x < y) {
    n = x;
    x = y;
    y = n;
  }
  
  while(x % y != 0){
    n = x % y;
    x = y;
    y = n;
  }

  printf("%d\n", y);

  return 0;
}



Measured memory_bytes: 2144
#include<iostream>
using namespace std;
int main () {
    int a = 0, b = 0, temp;
    for(int i = 0; i < 3; i++){
        cin >> temp;
        if(temp == 5) a++;
        if(temp == 7) b++;
    }
    if(a == 2 && b == 1) cout << "YES";
    else cout << "NO";
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        if(Math.abs(a - b) >= 2){
            System.out.println("Alice");
        }else{
            System.out.println("Brown");
        }
    }
}


class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;
    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

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

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken("\n");
    }

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

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

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

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    } 
}


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

int main(){
  long long K;
  cin >> K;
  
  long long n=7;
  long long m=n;
  long long ans=1;
  
  if(K%2==0 || K%5==0){
    ans=-1;
  }
  else{
    for(int i=0; i<K; i++){
      if(m%K==0){
        break;
      }
      n = n*10%K;
      m=(m+n)%K;
      ans++;
    }
  }
  
  cout << ans << endl;
      
  
  return 0;
}

Measured memory_bytes: 3188
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int k=sc.nextInt();
    int[] a=new int[200001];
    for(int i=0;i<n;i++){
      a[sc.nextInt()]++;
    }
    Arrays.sort(a);
    long sum=0;
    for(int i=0;i<200001-k;i++){
      sum+=a[i];
    }
    System.out.println(sum);
  }
}

Measured memory_bytes: 85244
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long N,M;
    cin >> N >> M;
    vector<int> work(M);
    long long count=0;
    for(int i=0;i<M;i++){
        cin >> work.at(i);
        count+=work.at(i);
    }
    if(N>=count){
        cout << N-count << endl;
    }else{
        cout << "-1" << endl;
    }
    
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
#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 all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
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;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
struct SegmentTree {
    int n;
    vector<T> node;
    T calc(T a, T b) {
        return a + b;
        // return min(a, b);
        // return max(a, b);
    }
    T e = 0;
    SegmentTree(vector<T> v) {
        int sz = v.size();
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
        for (int i = 0; i < sz; i++) {
            node[i + n - 1] = v[i];
        }
        for (int i = n - 2; i >= 0; i--) {
            node[i] = calc(node[2 * i + 1], node[2 * i + 2]);
        }
    }
    SegmentTree(T sz) {
        n = 1;
        while (n < sz) {
            n *= 2;
        }
        node.resize(2 * n - 1, e);
    }
    void update(int x, T val) {
        x = n + x - 1;
        node[x] = val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    void add(int x, T val) {
        x = n + x - 1;
        node[x] += val;
        while (x > 0) {
            x = (x - 1) / 2;
            node[x] = calc(node[2 * x + 1], node[2 * x + 2]);
        }
    }
    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return e;
        if (a <= l && r <= b) return node[k];
        T vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return calc(vl, vr);
    }
    T at(int x) {
        return node[n + x - 1];
    }
};
SegmentTree<ll> segt(440);
int n;
vector<ll> a;
auto memo = make_vec<ll>(440, 440);
ll dp(int l, int r) {
    if (memo[l][r] != -1) return memo[l][r];
    int len = r - l + 1;
    if (len <= 1) return 0;
    ll ret = LINF;
    for (int m = l; m + 1 <= r; m++) {
        chmin(ret, dp(l, m) + dp(m + 1, r) + segt.query(l, r + 1));
    }
    return memo[l][r] = ret;
}
int main() {
    cin >> n;
    a.resize(n);
    rep(i, n) {
        cin >> a[i];
        segt.update(i, a[i]);
    }
    rep(i, 440) rep(j, 440) memo[i][j] = -1;
    cout << dp(0, n - 1) << endl;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

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

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

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll x = b / c - (a - 1) / c;
    ll y = b / d - (a - 1) / d;
    ll z = b / lcm(c, d) - (a - 1) / lcm(c, d);
    OUT(b - (a - 1) - (x + y - z));
}


Measured memory_bytes: 256
/**
 *  Make Purse Light (Problem B, Practice Contest for Japan Domestic, 2005-06-19)
 *  by Kenji Inoue, 2006-12-22
 **/

#include <iostream>
#include <cstring>

using namespace std;

int main() {
  int m, c[4], p[4], r[4]; // money, coins, paid coins, returned coins
  int d[4] = {10, 50, 100, 500};

  bool firstline = true;
  while (cin >> m, (m)) {
    if (!firstline) { cout << endl; }
    firstline = false;

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

    int min=20*20*20*20, minc[4];
    memset(minc, 0, sizeof(minc));
    for (p[0]=0; p[0]<=c[0]; p[0]++) {
      for (p[1]=0; p[1]<=c[1]; p[1]++) {
        for (p[2]=0; p[2]<=c[2]; p[2]++) {
          for (p[3]=0; p[3]<=c[3]; p[3]++) {
            memset(r, 0, sizeof(r));

            int sum = 0;
            for (int i=0; i<4; i++) {
              sum += d[i] * p[i];
            }
            if (sum < m) { continue; }

            sum -= m;
            for (int i=3; i>=0; i--) {
              while (sum >= d[i]) { sum -= d[i]; r[i]++; }
            }

            int remain = 0;
            for (int i=0; i<4; i++) {
              remain += c[i] - p[i] + r[i];
            }
            if (remain < min) {
              min = remain;
              for (int i=0; i<4; i++) { minc[i] = p[i]; }
            }
          }
        }
      }
    }

    for (int i=0; i<4; i++) {
      if (minc[i] > 0) {
        cout << d[i] << " " << minc[i] << endl;
      }
    }
  }
}

Measured memory_bytes: 864
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;

bool is_sorted(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n - 1; i++)
        if (a[i] > a[i + 1]) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b = a;
    sort(b.begin(), b.end());
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) cnt++;
    }
    if (cnt > 2) {
        cout << "NO";
    }
    else {
        cout << "YES";
    }

    return 0;
}

Measured memory_bytes: 3548
#include<iostream>
#include<vector>
using namespace std;
#define inRange(x,a,b) (a <= x && x <= b)

int enc(char c){
    if(inRange(c, 'a', 'z'))    return c-'a'+1;
    return c-'A'+26+1;
}

int main(){
    string s;
    while(cin >> s, s != "#"){
        int pos = 0;
        bool valid = false;
        while(pos < s.length()){
            vector<int> v;
            pos++;  // (
            for(int i = 0; i < 3; i++){
                int num = s[pos] == '~' ? 1 : -1;
                if(s[pos] == '~')   pos++;
                num *= s[pos++];
                v.push_back(num);
                pos++; // & or )
            }
            bool good = true;
            for(int i = 0; i < 3; i++){
                for(int j = i+1; j < 3; j++){
                        good &= v[i]+v[j]!=0;
                }
            }
            if(good)    valid = true;
            pos++;  // |
        }
        cout << (valid ? "yes" : "no") << endl;
    }
    return 0;
}



Measured memory_bytes: 3160
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),v.end()
const ll inf=(1e18);
const ll mod=1000000007;
const ll mod2=998244353;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
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 (a>b) { a=b; return 1; } return 0; }
map<int,int> mp;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s;
cin>>s;
int n=s.size();
int cnt=0;
for(int i=0;i<n;i++){
    if(s[i]=='g')cnt++;
}
cout<<cnt-(n+1)/2<<endl;
}

Measured memory_bytes: 512
/**********************************
	author:  mariogzsl
**********************************/

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,b,a) for(int i=b-1;i>=a;i--)
#define f first
#define s second
#define puts(x) cout<<x<<endl
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	map<char, char> c;
	c['A']='T';
	c['T']='A';
	c['C']='G';
	c['G']='C';
	char in;
	cin>>in;
	cout<<c[in]<<endl;
	return 0;
}


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

struct Card {char suit, value;};

void bubble(struct Card A[], int N){
	for (int i=0; i<N; i++){
		for (int j=N-1; j>=i; j--){
			if (A[j].value < A[j-1].value){
				Card t = A[j];
				A[j] = A[j-1];
				A[j-1] = t;
			}
		}
	}
}

void selection(struct Card A[], int N){
	for (int i=0; i<N; i++){
		int minj = i;
		for (int j=i; j<N; j++){
			if (A[j].value < A[minj].value) minj = j;
		}
		Card t = A[i];
		A[i] = A[minj];
		A[minj] =t;
	}
}

void print(struct Card A[], int N){
	for (int i=0; i<N; i++){
		if(i>0) cout << " ";
		cout << A[i].suit << A[i].value;
	}
	cout << endl;
}

bool isStable(struct Card C1[], struct Card C2[], int N){
	for (int i=0; i<N; i++){
		if (C1[i].suit != C2[i].suit) return false;
	}
	return true;
}

int main(){
	Card C1[100], C2[100];
	int N;
	char ch;

	cin >> N;

	for (int i=0; i<N; i++){
		cin >> C1[i].suit >> C1[i].value;
	}

	for (int i=0; i<N; i++) C2[i] = C1[i];

	bubble(C1, N);
	selection(C2, N);

	print(C1, N);
	cout << "Stable"  << endl;
	print(C2, N);
	if (isStable(C1, C2,N)){
		cout << "Stable" << endl;
	} else{
		cout << "Not stable" << endl;
	}

	return 0;
}

Measured memory_bytes: 1156
using System;
using System.Text.RegularExpressions;

namespace algorithm
{
	class Program
	{
		static void Main(string[] args)
		{
			int i, j, k, l;

			i = int.Parse(Console.ReadLine());
			j = int.Parse(Console.ReadLine());
			k = int.Parse(Console.ReadLine());
			l = int.Parse(Console.ReadLine());
			int cnt = 0;
			for (int a = 0; a <= k; a++)
			{
				for (int b = 0; b<= j; b++)
				{
					for (int c = 0; c <= i; c++)
					{
						//脳死で総当たり
						if (a * 50 + b * 100 + c * 500 == l) cnt++;
					}

				}
			}

			Console.WriteLine(cnt);
		}
	}
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
int n, d;

int main(){
	IOS
	cin >> n >> d;
	cout << ceil((double)n/(2*d+1)) << '\n';
}


Measured memory_bytes: 3772
n = int(input())
E = [[]]*n

for i in range(n):
    inputs = list(map(int, input().split()))
    if inputs[1]==0:
        continue
    else:
        for j in inputs[2:]:
            E[i] = E[i] + [j-1]

beg = [-1]*n
fin = [-1]*n  

t = 0      
def f(i):
    global t
    #print(i,t)
    t += 1
    beg[i] = t
    for c in E[i]:
        if beg[c]>0:
            continue
        else:
            f(c)
    t+=1
    fin[i] = t
    

for i in range(n):
    if beg[i]<0:
        f(i)
for i in range(n):
    print(i+1, beg[i], fin[i])


Measured memory_bytes: 5660
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define M1 1000000007
#define M2 998244353

#define fl(i,a,b)  for(ll i=a;i<b;i++)
#define bfl(i,a,b) for(ll i=b-1;i>=a;i--)
#define f(i,n)     for(int i=0;i<n;i++)
#define bf(i,n)    for(int i=n-1;i>=0;i--)


#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl

#define bn "\n"

//------------------------------------------------------------------------ 
// #define V(a) vector<a>
// #define vt() vector< tuple < int ,int ,int > > ;
// #define vector< int ,int > pv;
// vector< pair <int,int> > vect;


//------------------------------------------------------------------------

ll modI(ll a,ll m);
ll gcd(ll a,ll b);
ll powM(ll x,ll y,ll m);
ll swap(ll a,ll b);

void swap(ll& a,ll& b)
{
    ll tp=a;
    a=b;
    b=tp;
}

ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    ll ans=1,r=1;
    x%=m;
    while(r>0&&r<=y)
    {
        if(r&y)
        {
            ans*=x;
            ans%=m;
        }
        r<<=1;
        x*=x;
        x%=m;
    }
    return ans;
}
 
ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

//---------------------------------------------------------------------------

// variable = Expression1 ? Expression2 : Expression3
// max = (n1 > n2) ? n1 : n2; 
// (n>m) ? cout<<"True"<<endl:cout<<"false"<<endl ;

// ---------------------------------------------------------------------------	

// int n;cin>>n;int a[n];for(int i=0;i<n;i++)cin>>a[i];    
// for(int i=0;i<n;i++)cout<<a[i];
// int a,b;cin>>a>>b;   

//----------------------------------------------------------------------------

// vector< tuple < int ,int ,int > > tv;
// vector< int ,int > pv;


//----------------------------------------------------------------------------


int main() {
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	int tt=1;
   // cin>>tt;
	while(tt--)
	{
	    
	   ll n;
	   cin>>n;
	   ll ans=n+(n*n)+(n*n*n);
	   p1(ans);
	   
	   
	    
	}
	
	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

llint n, m;
llint a[10005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	llint sum = 0;
	for(int i = 1; i <= m; i++){
		cin >> a[i];
		sum += a[i];
	}
	
	cout << max(-1LL, n-sum) << endl;
	
	return 0;
}

Measured memory_bytes: 3688
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A3 = list(map(int, input().split()))
N = int(input())


for i in range(N):
    b = int(input())
    for j in range(3):
        if A1[j] == b:
            A1[j] = 0
        if A2[j] == b:
            A2[j] = 0
        if A3[j] == b:
            A3[j] = 0

f = 0

if A1[0] == 0 and A1[1] == 0 and A1[2] == 0:
    f = 1
if A2[0] == 0 and A2[1] == 0 and A2[2] == 0:
    f = 1
if A3[0] == 0 and A3[1] == 0 and A3[2] == 0:
    f = 1
if A1[0] == 0 and A2[0] == 0 and A3[0] == 0:
    f = 1
if A1[1] == 0 and A2[1] == 0 and A3[1] == 0:
    f = 1
if A1[2] == 0 and A2[2] == 0 and A3[2] == 0:
    f = 1
if A1[0] == 0 and A2[1] == 0 and A3[2] == 0:
    f = 1
if A1[2] == 0 and A2[1] == 0 and A3[0] == 0:
    f = 1
if f == 1:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38384
#include <stdio.h>
int main(){
  int n, i, j, minj, tmp, count = 0;
  int A[100];

  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ){
    scanf("%d", &A[i]);
  }

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

    for ( j = i; j <= n ; j++){
      if( A[j]< A[minj] ){
	minj = j;
      }
    }
    if(minj != i){
      tmp = A[i];
      A[i] = A[minj];
      A[minj] = tmp;
      count++;
    }
  }
  
  for ( i = 1; i < n; i++){
    printf("%d ",A[i]);
  }
  printf("%d\n",A[n]);
  printf("%d\n",count);

  return 0;
}

Measured memory_bytes: 600
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int W=in.nextInt();
		int[] w=new int[n];
		int[] v=new int[n];
		int x=0;
		for (int i=0;i<n;++i) {
			w[i]=in.nextInt();
			v[i]=in.nextInt();
			x+=v[i];
		}
		long[] dp=new long[x+1];
		for (int i=1;i<=x;++i) dp[i]=Long.MAX_VALUE;
		for (int i=0;i<n;++i)
			for (int j=x;j>=v[i];--j) if (dp[j-v[i]]!=Long.MAX_VALUE)
				dp[j]=Math.min(dp[j],dp[j-v[i]]+w[i]);
		int res=0;
		for (int i=x;i>=0;--i) if (dp[i]<=W) {
			res=i;
			break;
		}
		System.out.println(res);
	}
}

Measured memory_bytes: 22804
// 問題の URL を書いておく
// 

#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)

int nums[100005];

int main(int, const char**)
{
    string s;
    cin >> s;
    int K;
    cin >> K;
    rep(i, (int)s.size())
    {
        nums[i] = s[i] - 'a';
    }
    int k = K;
    string ans = "";
    rep(i, (int)s.size() - 1)
    {
        auto t = (26 - nums[i]) % 26;
        if(k >= t)
        {
            k -= t;
            ans += 'a';
        }
        else
        {
            ans += s[i];
        }
    }
    auto lastNum = (nums[s.size() - 1] + k) % 26;
    ans += (char)('a' + lastNum);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4104
import sys
import numpy as np


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    t, a = nm()
    H = nl()
    T = np.array(list(map(lambda x: t - x * 0.006, H)))
    D = np.abs(a - T)
    S_i = sorted(range(0, n), key=lambda x: D[x])
    print(S_i[0] + 1)


if __name__ == '__main__':
    main()


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

int main() {
	ll n;
	cin >> n;
	ll ans = 0;
	for (ll i = 0; i < n; ++i) {
		ll p;
		cin >> p;
		if (p != i + 1)++ans;
	}
	if (ans <= 2)cout << "YES" << endl;
	else cout << "NO" << endl;
}


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


long long gcd(long long x, long long y){
    if(y == 0){
        return x;
    }

    return gcd(y, x%y);
}
int main(){
    long long n, x;

    cin >> n >> x;

    long long g = 0;

    long long xx[n];

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

    for(long long i = 0; i < n; i++){
        g = gcd(abs(xx[i] - x),g);
    }

    printf("%lld\n", g);

    return 0;

}

Measured memory_bytes: 1024
import java.util.Scanner;


public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		sc.close();
		int ct = 0;
		for(int i = a; i <= b; i++){
			if(c%i == 0)
				ct++;
		}
		System.out.println(ct);
	}
}

Measured memory_bytes: 17360
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a[] = new int[4+1];
    for(int i=0; i<6; i++) {
      int N = sc.nextInt();
      a[N]++;
    }
    for(int i=1; i<=4; i++) {
      if(a[i]>=3) {
        System.out.println("NO");
        return;
      }
    }
    System.out.println("YES");
  }
}


Measured memory_bytes: 23764
import itertools

N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]
data = list(range(1, M + 1))
L = list(itertools.combinations_with_replacement(data, N))
ans = 0
for l in L:
    tmp = 0
    for a, b, c, d in X:
        if l[b - 1] - l[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 21512
bingo = [0 for i in range(9)]
check = [False for i in range(9)]
complete = [[0, 1, 2], [3, 4, 5], [6, 7, 8],
            [0, 3, 6], [1, 4, 7], [2, 5, 8],
            [0, 4, 8], [2, 4, 6]]
for i in [0, 3, 6]:
    bingo[i], bingo[i+1], bingo[i+2] = map(int, input().split(" "))

N = int(input())
for i in range(N):
    bi = int(input())
    try:
        number_index = bingo.index(bi)
    except:
        continue
    if number_index != -1:
        check[number_index] = True

Yes = False
for a, b, c in complete:
    if True == check[a] == check[b] == check[c]:
        print("Yes")
        Yes = True
        break
if Yes == False:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

ll ppow(ll a,ll b){
	a%=MOD;
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
ll t=MOD/2+1;
ll calc(ll h){
	return (h-1)*h%MOD*t%MOD;
}
class Fact{
	vector<ll>fact;
	vector<ll>inv;
public:
	Fact(){}
	Fact(int n){
		n=n*2+10;
		fact=inv=vector<ll>(n);
		fact[0]=inv[0]=1;
		for(int i=1;i<n;i++){
			fact[i]=(fact[i-1]*i)%MOD;
			inv[i]=ppow(fact[i],MOD-2);
		}
	}
	ll get(int n){
		return fact[n];
	}
	ll nPr(int n,int r){
		return fact[n]*inv[n-r]%MOD;
	}
	ll nCr(int n,int r){
		return nPr(n,r)*inv[r]%MOD;
	}
	ll nrP(int n,int r){
		return nPr(n+r,n);
	}
	ll nrC(int n,int r){
		return nCr(n+r,n);
	}
};
int main(){
	int n,m,K;cin>>n>>m>>K;
	ll sum=0;
	Fact fac(n*m);
	rep(i,n)rep(j,m){
		(sum+=(calc(i+1)+calc(n-i))%MOD*m)%=MOD;
		(sum+=(calc(j+1)+calc(m-j))%MOD*n)%=MOD;
	}
	(sum*=t)%=MOD;
	cout<<sum*fac.nCr(n*m-2,K-2)%MOD<<endl;
}

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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<int, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	double t, x;
	cin >> t >> x;
	
	cout << t / x << endl;
	
	return 0;
}

Measured memory_bytes: 256
//参加気分でさ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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


	int N;
	cin >> N;

	int odd = (N + 1) / 2;

	double kotae = 1.0 * odd / N;

	cout << setprecision(12) << kotae << endl;

	Would you please return 0;
}

Measured memory_bytes: 256
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 入力値を文字の配列で返却する
def gets_nsp_list()
  gets.chomp.split("")
end

s = gets_nsp_list
t = gets_nsp_list
n = s.size-1
0.upto(n) do |i|
  ss = s[i..n] + s[0...i]
  if ss.join == t.join
    puts "Yes"
    exit
  end
end

puts "No"


Measured memory_bytes: 14628
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<int, pii> pipii;
typedef vector<vector<ll>> matrix;

vector<int> edges[2001];

int dfs(int curr, int par, int depth) {
  if(depth == 0) return 1;
  int ret = 1;
  for(int out: edges[curr]) {
    if(out == par) continue;
    ret += dfs(out, curr, depth-1);
  }
  return ret;
}

void solve() {
  int n, k;
  cin >> n >> k;
  for(int i = 1; i < n; i++) {
    int a, b;
    cin >> a >> b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  int maxIn = 0;
  if(k%2 == 0) {
    for(int i = 1; i <= n; i++) {
      maxIn = max(maxIn, dfs(i, -1, k/2));
    }
  }
  else {
    for(int i = 1; i <= n; i++) {
      for(int out: edges[i]) {
        maxIn = max(maxIn, dfs(i, out, k/2) + dfs(out, i, k/2));
      }
    }
  }
  cout << n - maxIn << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll A,B,C,D,ans;cin>>A>>B>>C>>D;
  ans=B/C-(A-1)/C+B/D-(A-1)/D;
  ll G=C*D/__gcd(C,D);
  ans-=B/G-(A-1)/G;
  cout<<B-A+1-ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  vector<int> P(N),out(N);
  for(int i=0;i<N;i++){
    out.at(i) = i + 1;
    cin >> S.at(i) >> P.at(i);
  }
  for(int j=0;j<N-1;j++){
    for(int i=0;i<N-1;i++){
      if(S.at(i) > S.at(i+1)){
        swap(S.at(i),S.at(i+1));
        swap(P.at(i),P.at(i+1));
        swap(out.at(i),out.at(i+1));
      }
    }
  }
   for(int j=0;j<N-1;j++){
    for(int i=0;i<N-1;i++){
      if(P.at(i) < P.at(i+1)&&S.at(i)==S.at(i+1)){
        swap(S.at(i),S.at(i+1));
        swap(P.at(i),P.at(i+1));
        swap(out.at(i),out.at(i+1));
      }
    }
   }
      for(int i=0;i<N;i++)printf("%d\n",out.at(i));
  return 0;
}

Measured memory_bytes: 3748
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
 
class Program{
    static void Main(){
        string s = Console.ReadLine();
        int b = -1, e = -1;
        for(int i = 1; i < s.Length; i++){
            if(s[i - 1] == s[i]){
                b = i;
                e = i + 1;
                break;
            }
            if(i + 1 < s.Length && s[i - 1] == s[i + 1]){
                b = i;
                e = i + 2;
                break;
            }
        }
        Console.WriteLine("{0} {1}", b, e);
    }
}

Measured memory_bytes: 3032
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define FOR(i,k,n) for((i)=(k);(i)<(n);(i)++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define pb push_back
#define all(a) (a).begin(),(a).end()  //greater<int>()
using namespace std;

int main(){
	int N,i,x,A;
	string S;
	cin>>N;
	cin>>S;
	x=0;
	A=0;

	REP(i,N){
		if(S[i]=='I') x++;
		else if(S[i]=='D') x--;
		if(x>A) A=x;
	}
	
	cout<<A<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
 
int main()
{
  int a, b, c, d;

  scanf("%d %d %d %d ", &a, &b, &c, &d);
  
  if ((a*b) >= (c*d))
   {
     printf("%d", a*b);
   }
  else
   {
     printf("%d", c*d);
   }


  

  
  return 0;
  
}

Measured memory_bytes: 128
N,W = map(int,input().split())
w,v = [0]*N,[0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())
    
# dp[i][j]:i番目の品物を詰めて価値jのときの重さの最小値
dp = [[10**9+1]*(sum(v)+1) for i in range(N+1)]
dp[0][0] = 0

#v[i-1]を使うかどうか
for i in range(1,N+1):
    #価値がjのときの最小の重さ
    for j in range(sum(v)+1):
        if j >= v[i-1]:
            dp[i][j] = min(dp[i-1][j-v[i-1]]+w[i-1],dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

# 重さがW以下のもので価値が最大となるものを探す
ans = 0
for i in range(sum(v)+1):
    if dp[-1][i] <= W:
        ans = max(ans,i)
print(ans)

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

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;// 10^9+7

pair<ll,ll> f(ll n, ll b)
{
    pair<ll,ll> res;
    while(n>0)
    {
        res.first += n%b;
        n/=b;
        res.second++;
    }
    return res;
}


pair<bool,ll> greedy(const ll n, const ll s)
{
    ll now = 2;
    while(true)
    {
        auto res = f(n, now);
        if(res.first==s)return {true, now};
        if(res.second<=2) return {false, now};
        now++;
    }
}

ll doubles(ll start, const ll n, const ll s)
{
    start = n/start;
    assert(start < n);
    //cerr << start << "  " << n/start/start <<","<<n/start<<","<<n%start << endl;
    for(ll i = start; i>1; i--)
    {
        const ll target = s - (i - 1);
        ll l = n/i;
        ll r = n/(i-1);
        ll mid = r;
        //cerr << target <<" : " << l << " , "<< r<<endl;
        while(r-l>1)
        {
            ll mid = (l+r)/2;
            if(n%mid<=target) r = mid;
            else l = mid;
            //cerr << mid << " : "<<n%mid << endl;
        }
        if(n%mid==target)return mid;
        if(n%r==target) return r;
    }
    if(s==1)return n;
    if(n==s)return n+1;
    return -1;
}

//���C���֐�
int main()
{
    ll n,s;
    cin >> n >> s;
    auto res = greedy(n,s);
    if(res.first) cout << res.second << endl;
    else cout << doubles(res.second, n, s) << endl;
    return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
num=[]
for i in range(n):
    num.append([a[i],i])
s1= lambda val: val[0]
num.sort(key=s1)
num1=0
num[0].append(0)
for i in range(1,n):
    if num[i][0]==num[i-1][0]:
        num[i].append(num1)
    else:
        num1=i
        num[i].append(num1)
num2=0
num3=0
s2=lambda val: val[1]
num.sort(key=s2)
for i in range(n):
    num2+=num[i][2]
    for j in range(i):
        if num[i][0]>num[j][0]:
            num3+=1
ans=((num2-num3)*k)%(10**9+7)
ans+=(num2*((((k-1)*k)//2)%(10**9+7)))%(10**9+7)
print(ans%(10**9+7))


Measured memory_bytes: 9396
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define AfterDecimal(n) cout << fixed << setprecision(n);
#define ll long long int
#define ld long double
#define all(a) a.begin(), a.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define bits(x) __builtin_popcount(x)

using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")

//template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update>
    ordered_set;

#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << "# "<< name << " = " << arg1 << '\n';
}
template<typename Arg1, typename... Args>
void __f(const char* names, Arg1 && arg1, Args &&... args){
        const char* comma = strchr(names + 1 ,',');
        cout << "# ";
        cout.write(names, comma - names)<< " = " << arg1 << " | ";
        __f(comma + 1, args...);
}
#else
#define debug(...) 36
#endif


std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int ri(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

ll power(ll x, ll y, ll p){
   ll res = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         res = (res * x) % p;
      y = y >> 1;
      x = (x * x) % p;
   }
   return res;
}

const ll INF = (ll)(8e18);
const ll MOD = (ll)(1e9 + 7);
const ll HMOD = (ll)4222234727;
const ll Hashprime = (ll)31;

const int maxn = 100100;

int32_t main(){
    IOS;
    #ifndef ONLINE_JUDGE
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    #endif
    int t = 1; // cin >> t;
    while(t--){
       int n,k,s; cin >> n >> k >> s;
       for(int i = 1; i <= k; i++) cout << s << ' ';
       if(s == int(1e9)){
         for(int i = k + 1; i <= n; i++) cout << 1 << ' ';
       }else{
         for(int i = k + 1; i <= n; i++) cout << int(1e9) << ' ';
       }
       cout << '\n';
    }
    #ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
}
//g++ -DLOCAL -std=c++17 -Wshadow -Wall -o "c" "comp.cpp" -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g


Measured memory_bytes: 3620