akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iostream>
const long long mod=1000000007;
using namespace std;
long long pos[100003];
long long n,m;
struct node{
	long long x[3][3];	
	inline void operator *=(const node &a){
		long long c[3][3];
		c[0][0]=c[0][1]=c[0][2]=0;
		c[1][0]=c[1][1]=c[1][2]=0;
		c[2][0]=c[2][1]=c[2][2]=0;
		for(int i=0;i<=2;i++){
			for(int j=0;j<=2;j++){
				for(int k=0;k<=2;k++){
					c[i][j]=(c[i][j]+x[i][k]*a.x[k][j]%mod)%mod;
				}
			}
		}
		for(int i=0;i<=2;i++){
			for(int j=0;j<=2;j++){
				x[i][j]=c[i][j];
			}
		}
	}
}e,a,e1,e2;
inline void fsp(node &x,node y,long long t){
	node y1=y;
	for(;t;t>>=1){
		if(t&1){
			x*=y1;
		}
		y1*=y1;
	}
}
long long A[3],B[3];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>pos[i];
	}
	e.x[0][0]=e.x[1][1]=e.x[2][2]=e.x[1][2]=e.x[0][2]=1;
	e.x[0][1]=2;
	e2.x[0][0]=e2.x[1][1]=e2.x[2][2]=e2.x[2][0]=1;
	e1=e;
	e1*=e2;
	m++;
	pos[m]=n;
	B[0]=1;
	for(int l=1;l<=m;l++){
		int s=pos[l]-pos[l-1]-1;
		a.x[0][0]=1,a.x[0][1]=0,a.x[0][2]=0;
		a.x[1][0]=0,a.x[1][1]=1,a.x[1][2]=0;
		a.x[2][0]=0,a.x[2][1]=0,a.x[2][2]=1;
		fsp(a,e1,s);
		a*=e;
		for(int i=0;i<=2;i++){
			A[i]=0;
			for(int j=0;j<=2;j++){
				A[i]=(A[i]+B[j]*a.x[j][i]%mod)%mod;
			}
		}
		for(int i=0;i<=2;i++){
			B[i]=A[i];
		}
	}
	cout<<B[2]<<endl;
	return 0;
}
/*

in:
10 9
1 2 3 4 5 6 7 8 9

out:
100

*/
//f[i][0]=f[i-1][0];
//f[i][1]=f[i-1][0]+f[i-1][1];
//f[i][2]=2*f[i-1][1]+f[i-1][2]+f[i-1][0];  i-1到i无隔板

//f[i][0]=f[i-1][2];
//f[i][1]=f[i-1][2];
//f[i][2]=f[i-1][2];   i-1到i有隔板 

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int

int p[100100];
int r[100100];
int w[100100];

void init(int n){
  REP(i, n){
    p[i] = i;
    r[i] = 0;
  }
}

int find(int n){
	return (p[n] == n ? n : p[n] = find(p[n]));
}

void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  if(r[x] < r[y]){
		p[x] = y;
		w[y] += w[x];
	}
  else{
    p[y] = x;
		w[x] += w[y];
    if(r[x] == r[y]) r[x]++;
  }
}

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

struct edge{int to, cost;};

ll POW(ll a, ll b){
	if(b == 0) return 1LL;
	if(b == 1) return a;
	if(b %2 == 1) return (a*POW(a, b-1))%INF;
	return POW(a*a%INF, b/2);
}

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

int main(){
	int n, m;
	cin >> n >> m;
	init(100009);
	REP(i, m){
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		unite(a,b);
	}
	int ans = 0;
	REP(i, n) if(i == find(i)) ans++;
	cout << ans << endl;
	return 0;
} 


Measured memory_bytes: 1536
#include <iostream>
using namespace std;
int main() {
    int h1 , h2 , k1 , k2 , a , b , c ,d;
    cin >> h1 >> h2 >> k1 >> k2 >> a >> b >> c >> d;
    if((h1/10)*c + h1*a + (h2/20)*d + h2*b > (k1/10)*c + k1*a + (k2/20)*d + k2*b){
        cout << "hiroshi" << endl;
        }
        if((h1/10)*c + h1*a + (h2/20)*d + h2*b < (k1/10)*c + k1*a + (k2/20)*d + k2*b){
            cout << "kenjiro" << endl;
        }
        if((h1/10)*c + h1*a + (h2/20)*d + h2*b == (k1/10)*c + k1*a + (k2/20)*d + k2*b){
            cout << "even" << endl;
        }
    return 0;
}

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

int main(){
  int ans=0;
  char a[256];
  int i;
  cin >> a;
  for(i=0;i<=50;i++){
	if(a[i*2]=='L')ans=-1;
	if(a[2*i+1]=='R')ans=-1;
  }
  if(ans==0)cout << "Yes";
  else if(ans==-1) cout << "No";
  return 0;
}

Measured memory_bytes: 256
A,B,C,D,E,F = (int(T) for T in input().split())
SugM = 0
WatM = 100*A
for TA in range(0,(F//100)+1):
    for TB in range(0,(F//100)+1):
        if TA==TB==0:
            continue
        else:
            Water = TA*100*A+TB*100*B
            RestW = F-Water
            if RestW>=0:
                for TC in range(0,RestW+1):
                    for TD in range(0,RestW+1):
                        Suger = TC*C+TD*D
                        RestS = RestW-Suger
                        if RestS>=0 and Water>=(100*Suger)/E:
                            if Suger/(Suger+Water)>SugM/(SugM+WatM):
                                SugM = Suger
                                WatM = Water
                        else:
                            break
            else:
                break
print('{} {}'.format(WatM+SugM,SugM))

Measured memory_bytes: 9112
w = list(input())
w.sort()
r = 1
for i in range(len(w)):
	if i!=(len(w)-1) and i%2==0 and w[i]!=w[i+1]:	r=0
if(i!=0):
	if(w[i]!=w[i-1]):	r=0
if(i==0):
	r=0
if r:	print("Yes")
else:	print("No")


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
    int n;
    while(cin >> n){
        if(n == 0)
            break;
        double s[n] = {};
        double m = 0;
        double a = 0;
        double sum = 0;
        for(int i = 0; i < n; i++){
            cin >> s[i];
            sum += s[i];
        }
        m = sum / n;
        for(int i = 0; i < n; i++){
            a += pow(s[i] - m, 2);
        }

        printf("%.5f\n" ,sqrt(a/n));
    }

    return 0;
}


Measured memory_bytes: 3216
import decimal
n,k=map(int,input().split())
num1=1
num2=0
for i in range(20):
    if num1>=k:
        break
    num1*=2
    num2+=1
num=n*(2**num2)
num1=num2
num3=0
for i in range(1,n+1):
    if i*(2**(num2-1))>=k:
        num2-=1
    if i>=k:
        num3+=2**num1
    else:
        num3+=2**(num1-num2)
print(decimal.Decimal(num3/num))


Measured memory_bytes: 10072
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

using i64 = long long;

struct Graph {
  struct edge {
    int to;
    i64 cap;
    i64 rev;
  };

  int n;
  vector<vector<edge>> edges;

  Graph(int N) {
    n = N;
    edges.resize(n, vector<edge>());
  }

  int size() const { return n; }

  vector<edge> &operator[](int v) { return edges[v]; }
};

struct Dinic {
  int N;
  vector<int> level;
  vector<int> itr;
  Graph G;

  Dinic(int n) : G(n) { N = n; }

  void add_edge(int from, int to, i64 cap, i64 rev_cap) {
    G[from].push_back({to, cap, (int)G[to].size()});
    G[to].push_back({from, rev_cap, (int)G[from].size() - 1});
  }

  bool g_level(int s, int t) {
    level.assign(N, -1);
    queue<int> que;
    que.push(s);
    level[s] = 0;
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (auto &e : G[v]) {
        if (e.cap > 0 && level[e.to] == -1) {
          level[e.to] = level[v] + 1;
          que.push(e.to);
        }
      }
    }
    return level[t] >= 0;
  }

  i64 dfs(int v, int t, i64 f) {
    if (v == t) return f;

    for (int &i = itr[v]; i < G[v].size(); i++) {
      auto &e = G[v][i];
      if (e.cap > 0 && level[e.to] > level[v]) {
        i64 mi_f = dfs(e.to, t, min(f, e.cap));
        if (mi_f > 0) {
          e.cap -= mi_f;
          G[e.to][e.rev].cap += mi_f;
          return mi_f;
        }
      }
    }
    return 0;
  }

  i64 max_flow(int s, int t) {
    i64 result = 0;
    i64 flow;
    while (g_level(s, t)) {
      itr.assign(N, 0);
      while ((flow = dfs(s, t, 1e9)) > 0) result += flow;
    }
    return result;
  }
};

/*

checked
    http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2723921#1
*/

int N;

int a[101];
int b[101];
int c[101];
int d[101];

int main(){
  cin >> N;
  rep(i,0,N - 1) cin >> a[i] >> b[i] ;
  rep(i,0,N - 1) cin >> c[i] >> d[i];

  Dinic dinic(202);
  int s = 200;
  int t = 201;

  rep(i,0,N - 1){
    dinic.add_edge(s,i,1,0);
    dinic.add_edge(i + N,t,1,0);
  }

  rep(i,0,N - 1){
    rep(j,0,N - 1){
      if(a[i] < c[j] && b[i] < d[j])
        dinic.add_edge(i,j + N,1,0);
    }
  }

  cout << dinic.max_flow(s,t) << endl;
}


Measured memory_bytes: 512
import numpy as np
def is_prime(N):
    is_prime = True
    for i in range(2, int(np.sqrt(N))):
        if N%i == 0:
            is_prime = False
            break
    return is_prime

X = int(raw_input())
maxx = 100003
for i in range(X, maxx+1):
    if is_prime(i):
        print i
        break


Measured memory_bytes: 19328
#include<stdio.h>
int main(){
	int a,n,i,k=0,x=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		if(scanf("%d",&a),a!=0)++k;
		else k=0;
		if(x<k)x=k;
	}
	printf("%d\n",x+1);
	return 0;
}


Measured memory_bytes: 2140
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s = sc.next();
        int x = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)) {
                x++;
            }
        }
        System.out.println(n - 1 - Math.max(x - k * 2, 0));
    }

}


Measured memory_bytes: 39408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = (int)1e9 + 7;
const int INF = (int)100100100;

int main() {
    //ll N; cin >> N;
    ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    if((N+M)%2==1)cout << "IMPOSSIBLE";
    else cout << (N+M)/2;
    


}

/*



 */



Measured memory_bytes: 764
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] sArray = new int[n];
		for (int i = 0; i < n; i++) {
			sArray[i] = scanner.nextInt();
		}
		int p = scanner.nextInt();
		int[] tArray = new int[p];
		int cnt = 0;
		for (int i = 0; i < p; i++) {
			tArray[i] = scanner.nextInt();
			if(binarySearch(sArray, tArray[i], 0, n-1)){
				cnt++;
			}
		}
		System.out.println(cnt);
	}
	
	public static boolean binarySearch(int[] sArray, int tElement, int start,
			int end) {

		if (tElement == sArray[(start + end) / 2]) {
			return true;
		} else if (start == end) {
			return false;
		} else {
			if (tElement < sArray[(start + end) / 2]) {
				return binarySearch(sArray, tElement, start,
						(start + end) / 2);
			} else {
				return binarySearch(sArray, tElement, (start + end) / 2+1, end);
			}
		}
	}
}

Measured memory_bytes: 76284
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

    const static long long MOD = 1e9 + 7;

    vector<long long> pow2;
    vector<long long> F;
    vector<long long> IF;

    long long norm(long long a) {
        a %= MOD;
        if (a < 0) {
            a += MOD;
        }
        return a;
    }

    long long inverse(long long a) {
        long long b = MOD;
        long long u = 0, v = 1;
        a = norm(a);
        while (a != 0) {
            long long d = b / a;
            b -= d * a;
            u -= d * v;
            swap(a, b);
            swap(u, v);
        }
        return norm(u);
    }

    long long powM(long long x, long long e) {
        long long res = 1;
        while (e > 0) {
            if (e & 1) {
                res = res * x % MOD;
            }
            x = x * x % MOD;
            e >>= 1;
        }
        return res;
    }

    void init(int n) {
        F.clear();
        F.resize(n + 1, 1);
        IF = F;
        pow2.clear();
        pow2.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            pow2[i] = pow2[i - 1] * 2 % MOD;
        }

        for (int i = 1; i <= n; ++i) {
            F[i] = F[i - 1] * i % MOD;
        }
        IF[n] = inverse(F[n]);
        for (int i = n - 1; i > 0; --i) {
            IF[i] = IF[i + 1] * (i + 1) % MOD;
        }
    }

    long long nCr(int n, int r) {
        if (r < 0 || r > n) {
            return 0;
        }
        long long res = F[n] * IF[r] % MOD * IF[n - r] % MOD;
        return res;
    }

    long long nAr(int n, int r) {
        if (r > n || r < 0) {
            return 0;
        }
        long long res = F[n] * IF[n - r] % MOD;
        return res;
    }

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;

    init(m + n + 10);
    auto calc = [&](int n, int m) {
        long long res = nAr(m, n);
        (res *= res) %= MOD;
        return res;
    };

    auto calc2 = [&](int n, int m, int c) {
        long long res = nCr(n, c) * 1LL * nAr(m, c) % MOD;
        (res *= calc(n - c, m - c)) %= MOD;
        return res;
    };

    long long res = 0;
    for (int i = 0, sign = 1; i <= n; ++i, sign = -sign) {
        res += (MOD + calc2(n, m, i) * sign) % MOD;
        res %= MOD;
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 26660
#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 int long long
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    priority_queue<int>que;
    REP(i,3){
        int a;cin>>a;
        que.push(a);
    }
    int K;cin>>K;
    REP(i,K){
        int d=que.top();
        d*=2;
        que.pop();
        que.push(d);
    }
    int ans=0;
    REP(i,3){
        ans+=que.top();
        que.pop();
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(x, y):
    return (x * y) // gcd(x, y)


N = int(input())
A = list(map(int, input().split()))
res = A[0]
for i in range(1, N):
    res = lcm(res, A[i])
res = res - 1
ans = 0
for a in A:
    ans += (res % a)
print(ans)


Measured memory_bytes: 41196
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
P = list(map(int, input().split()))

edges = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)


ans = 0
visited = set()
for i in range(N):
    q = [i]
    loop = set()
    values = set()
    while q:
        x = q.pop()
        if x in visited:
            continue
        visited.add(x)
        loop.add(x+1)
        values.add(P[x])

        for nx in edges[x]:
            if nx not in visited:
                q.append(nx)

    ans += len(loop & values)

print(ans)

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

#define int long long int
#define ff first
#define ss second
#define pb push_back
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int mod = 1e9 + 7;
const int N = 5e5 + 5;
const int inf = 1e16 + 2;
int n , m;
vector<vector<int>> grp(N);
int p[N];

void BFS(int idx) {
    
    queue<int > q;
    q.push(idx);
    p[idx] = 1;
    while(!q.empty()) {
        int top = q.front();
        q.pop();
        for(auto x : grp[top]) {
            if(p[x] == -1) {
                p[x] = top;
                q.push(x);
            }
        }
    }
}
void solve(int z) {
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++) p[i] = -1;
    for(int i = 0 ,a , b ; i < m ; i ++) {
        cin >> a >> b;
        a --;
        b --;
        grp[a].pb(b);
        grp[b].pb(a);
    }
    BFS(0);
    for(int i = 1 ; i < n ; i ++) {
        if(p[i] == -1) {
            cout << "No" << '\n';
            return;
        }
    }
    cout << "Yes" << '\n';
    for(int i = 1 ; i < n ; i ++) cout << p[i] + 1 << '\n';
}

/*
 */

int32_t main()
{
    fastio
    int testcase = 1;
    //cin >> testcase;
    int x = 1;
    while(testcase --) {
        solve(x ++);
    }
    
    return 0;
}
 



Measured memory_bytes: 22376
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    deque<int> a[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0, t; j < n - 1; j++) {
            cin >> t;
            a[i].push_back(t - 1);
        }
    }
    queue<int> que;
    for (int i = 0; i < n; i++) que.push(i);
    int v = n * (n - 1) / 2;
    int day = 0;
    while (que.size()) {
        day++;
        queue<int> preQ;
        swap(preQ, que);
        bool used[n] = {};
        while (preQ.size()) {
            int x = preQ.front(); preQ.pop();
            if (a[x].size() && a[a[x].front()].size() && !used[x] && !used[a[x].front()] && a[a[x].front()].front() == x) {
                used[x] = used[a[x].front()] = true;
                que.push(x);
                que.push(a[x].front());
                a[a[x].front()].pop_front();
                a[x].pop_front();
                v--;
            }
        }
        if (v == 0) break;
    }
    if (v) cout << -1 << endl;
    else cout << day << endl;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
typedef vector<vector<ll> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;

int D;
vector<int>c(26);

int main(){
    cin >> D;
    rep(i,26)cin>>c[i];
    vector<vector<int> >s(D,vector<int>(26));
    rep(i,D)rep(j,26)cin>>s[i][j];
    vector<int>t(D);
    rep(i,D){
        cin>>t[i];
        t[i]--;
    }
    vector<int>last(D,0);

    ll manzoku = 0;
    rep(i,D){
        manzoku += s[i][t[i]];
        last[t[i]]=i+1;
        rep(j,26){
            manzoku -= c[j]*(i+1-last[j]);
        }
        cout << manzoku << endl;
    }
    return 0;
}


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

int main()
{
	auto v = vector<int>(201);
	for(auto i = 1; i <= 200; ++i){
		switch(i){
			case 105: case 135: case 165: case 189: case 195:
			v[i] = 1;
			break;
		}
		v[i] += v[i - 1];
	}
	int n;
	cin >> n;
	cout << v[n] << endl;
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rep1c(i, n) for (int i = 1; i <= (int)(n); i++)
#define repc0(n, i) for (int i = (int)(n); i >= 0; i--)

using namespace std;
typedef long long ll;

struct DisjointSet {
  map<int, int> parent, rank, num;

  void makeSet(int x) {
    parent[x] = x;
    rank[x] = 0;
    num[x] = 1;
  }

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

  void unite(int x, int y) {
    link(findSet(x), findSet(y));
  }

  void link(int x, int y) {
    if(rank[x] < rank[y]) {
      parent[x] = y;
      num[y] += num[x];
    } else {
      parent[y] = x;
      num[x] += num[y];
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  int numberOf(int x) {
    return num[findSet(x)];
  }

  int findSet(int x) {
    if(x == parent[x]) return x;
    else return parent[x] = findSet(parent[x]);
  }
};

static const int MAX=100010;
ll N, M, A[MAX], B[MAX];
DisjointSet ds;

void solve() {
  ll current = N*(N-1)/2;
  list<ll> res;
  repc0(M-1, i) {
    res.push_front(current);
    if(!ds.same(A[i], B[i])) {
      current -= ds.numberOf(A[i]) * ds.numberOf(B[i]);
      ds.unite(A[i], B[i]);
    }
  }
  for(const ll& a : res) printf("%lld\n", a);
}

int main() {
  scanf("%d %d", &N, &M);
  rep(i, N) ds.makeSet(i);
  rep(i, M) {
    scanf("%d %d", &A[i], &B[i]);
    A[i]--;
    B[i]--;
  }
  solve();
  return 0;
}


Measured memory_bytes: 20096
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int ans = 0;
int  p,q,a,n;
void dfs(int num,int seki,int deno,int nume,int value){
  if(nume > 0){
	int g = __gcd(deno,nume);
	deno/=g;
	nume/=g;
  }
  if((nume/(double)deno) + (double)(n-num)/(double)value < (double) p/(double)q- 1e-7 )return;
  if(p*deno == q*nume){
	ans++;
  }
  if(p*deno <= q*nume) {
	return;
  }
  if(num == n)return;
  for(int i = value;i*seki <= a;i++){
	dfs(num+1,seki*i,deno*i,nume*i+deno,i);
  }
  
}
int main(){
 
  while(cin >> p >> q >> a >> n && q&&p){
	ans = 0;
	dfs(0,1,1,0,1);
	cout << ans << endl;
	
  }

  return 0;
}

Measured memory_bytes: 1160
using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    public static int Main()
    {
        do
        {
            new Program().solve();
        } while (false);
        return 0;
    }
    public int dfs(bool[,] matrix, bool[] check, int N, int row, int depth)
    {
        if (depth >= N - 1)
            return 1;

        int count = 0;
        for (int i = 1; i < N; ++i)
        {
            if (!check[i] && matrix[row, i])
            {
                check[i] = true;
                count += dfs(matrix, check, N, i, depth + 1);
                check[i] = false;
            }
        }
        return count;
    }
    public void solve()
    {
        string[] str = Console.ReadLine().Split(' ');
        int N = int.Parse(str[0]);
        int M = int.Parse(str[1]);

        bool[,] matrix = new bool[N, N];
        bool[] check = new bool[N];
        for (int i = 0; i < M; ++i)
        {
            str = Console.ReadLine().Split(' ');
            int a = int.Parse(str[0]) - 1;
            int b = int.Parse(str[1]) - 1;
            matrix[a, b] = true;
            matrix[b, a] = true;
        }

        Console.WriteLine(dfs(matrix, check, N, 0, 0));
    }
}


Measured memory_bytes: 2648
N, M = map(int, input().split())
AB = [0]*M
for i in range(M):
    a, b = map(int, input().split())
    AB[i] = a, b

def key(ab):
    a, b = ab

AB.sort()

a0, b0 = AB[0]
cnt = 1
for a, b in AB[1:]:
    #print(cnt, (a0, b0), " : ", (a, b))
    if b0 > a:
        a0 = max(a, a0)
        b0 = min(b, b0)
    else:
        a0, b0 = a, b
        cnt += 1
#print((a0,b0))
print(cnt)





Measured memory_bytes: 17372
//Author : Prakhar Asaiya
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define REPN(i,a,b) for(ll i = a; i <= b; ++i)
#define REPV(i,a,b) for(ll i = a; i >= b; --i)
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define with_tests int t; cin>>t; while(t--){ solve(); }
#define without_tests solve();
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 100000000
#define ff first
#define ss second
const int M=1e9+7;

void solve()
{
	ll n;
	cin>>n;
	vector<ll> A(n);
	for(auto&e : A)
	{
		cin>>e;
	}
	ll ans = 0;
	vector<ll> pref(n);
	pref[0] = A[0];
	REP(i,1,n)
	{
		pref[i] = pref[i-1] + A[i];
	}
	REP(i,0,n)
	{
		ll res = (pref[n-1] - pref[i]) % M;
		ans += A[i] * res;
		ans %= M;
	}
	cout<<ans<<"\n";
}
 
int main()
{/*
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#*/
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  //with_tests;
  without_tests;
  return 0;
}

Measured memory_bytes: 6368
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000001
#define VMAX 10000

main(){
  unsigned short *A, *B;

  int C[VMAX+1];
  int n, i, j;
  scanf("%d", &n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  for ( i = 0; i <= VMAX; i++ ) C[i] = 0;

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

  for ( i = 1; i <= VMAX; i++ ) C[i] = C[i] + C[i-1];

  for ( j = 1; j <= n; j++ ){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", B[i]);
  }
  printf("\n");
  return 0;
}



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

int main()
{
	int n;
	cin >> n;
	int a[n],b[n],c[n];
	int ans=0;
	for(int i=0 ; i<n ; i++)
	{
		cin >> a[i];
	}
	for(int i=0 ; i<n ; i++)
	{
		cin >> b[i];
	}
	for(int i=0 ; i<n ; i++)
	{
		c[i]=a[i]-b[i];
	}
	for(int i=0 ; i<n ; i++)
	{
		if(c[i]>0)
		ans+=c[i];
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>

const long long int Z = 1000000007;
const long long int INF = 1 << 30;
int flag = 0;
using ll = long long;

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

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

int main() {
	ll n, k;
	std::cin >> n >> k;
	std::vector<std::pair<int, int>>p(n);
	for (int i = 0;i < n;i++) {
		int a, b;
		std::cin >> a >> b;
		p[i] = std::make_pair(a, b);
	}
	std::sort(p.begin(), p.end());
	ll sum = 0;
	for (int i = 0;i < n;i++) {
		sum += p[i].second;
		if (sum >= k) {
			std::cout << p[i].first << std::endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  string left = "";
  string right = "";
  bool flag = true;
  int n = s.length();
  for(int i = 0; i < n / 2; ++i){
    left += s[i];
    right += s[n - i - 1];
  }
  flag = left != right ? false : true;
  n = left.length();
  for(int i = 0; i < n / 2; ++i){
    if(left[i] != left[n - i - 1] || right[i] != right[n - i - 1]){
      flag = false;
      break;
    }
  }
  string ans = flag ? "Yes" : "No";
  cout << ans << endl;
}


Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "damage", long, "cost");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, m, k;
    scan(n, m, k);
    // 総当り
    bool flag;
    foreach (i; iota(n + 1))
    {
        auto black = m * i;
        foreach (_; iota(m + 1))
        {
            black += (n - 2 * i);
            if (black == k)
                flag = true;
        }
    }
    if (flag)
        writeln("Yes");
    else
        writeln("No");
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main()
{
	int a,b;
	string c;
	cin>>a>>b>>c;
	bool flag1=true;
	for(int i=0;i<c.length();i++){
		if(c[i]=='-'&&i!=a){
			flag1=false;
			break;
		}
	}
	if(c[a]=='-'&&flag1){
		puts("Yes");
	}
	else puts("No");
	
 } 

Measured memory_bytes: 256
N = gets.to_i

m = N
(N+1).times do |num|
  cnt = 0
  n = num
  while n > 0
    cnt += n % 6 
    n /= 6
  end
  n = N - num
  while n > 0
    cnt += n % 9 
    n /= 9
  end
  m = [m, cnt].min
end
puts m


Measured memory_bytes: 3836
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<bitset>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
    int f=1,ans=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
    return f*ans;
}
const int MAXN=1e5+11;
char S[MAXN],T[MAXN];
int N,M,SS[MAXN][2],ST[MAXN][2],Q;
int main(){
    scanf("%s%s",S+1,T+1);N=strlen(S+1),M=strlen(T+1);
    for(int i=1;i<=N;i++) SS[i][0]=SS[i-1][0]+(S[i]=='A'),SS[i][1]=SS[i-1][1]+(S[i]=='B');
    for(int i=1;i<=M;i++) ST[i][0]=ST[i-1][0]+(T[i]=='A'),ST[i][1]=ST[i-1][1]+(T[i]=='B');
    Q=read();
    while(Q--){
        int l1=read(),r1=read(),l2=read(),r2=read();
        int sa=SS[r1][0]-SS[l1-1][0],sb=r1-l1+1-sa;
        int ta=ST[r2][0]-ST[l2-1][0],tb=r2-l2+1-ta;
        int Sa=sa+2*sb,St=ta+2*tb;
        if((Sa-St)%3) printf("NO\n");
        else printf("YES\n");
    }return 0;
}/*
  AAAAABBBBAAABBBBAAAA
  BBBBAAABBBBBBAAAAABB
  1
  2 15 2 13
  */


Measured memory_bytes: 4892
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];} 
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";} cout<<endl;
#define S second
#define F first
#define SZ(x) (int)x.size()
typedef long long ll;
const int  MOD = 1e9 + 7;
const int  N = 1e5 + 7;
int been[30][30];
char g[30][30];
int res = 0;
int h , w;


void bfs(int i , int j){
	been[i][j] = 1;
	queue<pair<int , int> > q;
	q.push({i , j});

	int curr = -1;
	while(q.size() > 0){
		queue<pair<int , int> > next;
		while(q.size() > 0){
			auto p = q.front();
			q.pop();
			for(int ii = p.F - 1; ii <= p.F + 1; ii++){
				for(int jj = p.S -1 ; jj <= p.S + 1 ; jj++){
					if(ii != p.F && jj != p.S) continue;
					if(ii <= 0 || ii > h) continue;
					if(jj <= 0 || jj > w) continue;
					if(been[ii][jj] || g[ii][jj] == '#') continue;
					been[ii][jj] = 1;
					next.push({ii, jj});
				}
			}
		}
		curr++;
		q = next;
	}
	res = max(res, curr);
}


void solve(){
	cin>>h>>w;
	for(int i = 1; i <= h; i++){
		for(int j = 1 ; j <= w ; j++){
			cin>>g[i][j];
		}
	}

	for(int i = 1; i <= h; i++){
		for(int j = 1 ; j <= w ; j++){
			memset(been , 0 , sizeof(been));
			if(g[i][j] == '#') continue;
			bfs(i , j);
		}
	}
	cout<<res<<endl;
}

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

Measured memory_bytes: 256
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

N = lines[0][0]
K = lines[0][1]
a = (lines[1]).sort
f = (lines[2]).sort.reverse

score_now = 0
for i in 1..N do
  if a[i-1] * f[i-1] > score_now then
    score_now = a[i-1] * f[i-1]
  end
end

found = false
twice = false
obj_max = score_now
obj_min = 0
objective = score_now / 2
while found == false do
  num_train = 0
  for i in 1..N do
    if f[i-1] * a[i-1] > objective then
      num_train += a[i-1] - objective / f[i-1]
    end
  end
  if num_train > K then  #failure
    obj_min = objective
    objective = (objective + obj_max) / 2
  else  #success
    obj_max = objective
    objective = (obj_min + objective) / 2
  end
  if obj_max == 0 then
    ans = 0
    found = true
  elsif obj_max == obj_min + 1 then
    if twice then
      ans = obj_max
      found = true
    else
      twice = true
    end
  end
end
    
print ans

Measured memory_bytes: 37260
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = I()
a = IR(n)
l = a[0]
for i in range(1,n):
    g = gcd(l,a[i])
    l *= a[i]//g
print(l)
#B

#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 38512
#include <stdio.h>

int main(void) {
	int a, b;
	char op;
	scanf("%d %c %d", &a, &op, &b);
	while (op!='?')
	{
		if (op=='+') {
			printf("%d\n", a+b);
		} else if (op=='-') {
			printf("%d\n", a-b);
		} else if (op=='*') {
			printf("%d\n", a*b);
		} else if (op=='/') {
			if (b!=0) {
			printf("%d\n", a/b);
			} else printf("divided by 0\n");
		} else break;
		scanf("%d %c %d", &a, &op, &b);
	}
	return 0;
}

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

int n;

int main(){
	cin >> n;
	if(n >= 1 && n < 105){
		cout << 0;
		return 0;
	}
	if(n >= 105 && n < 135){
		cout << 1;
		return 0;
	}
	if(n >= 135 && n < 165){
		cout << 2;
		return 0;
	}
	if(n >= 165 && n < 189){
		cout << 3;
		return 0;
	}
	if(n >= 189 && n < 195){
		cout << 4;
		return 0;
	}
	cout << 5;
	return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;

const ll inf=1e15;
const int MOD=1e9+7;

vector<P> g1[100100];
vector<P> g2[100100];
int n,m,s,t;
ll d1[100100];
ll d2[100100];

void solve1(int s){
    fill(d1,d1+n,inf);
    d1[s]=0;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty()){
        P q=que.top(); que.pop();
        ll cur=q.first;
        int u=q.second;
        if(d1[u]<cur) continue;
        for(auto t:g1[u]){
            int v=t.first;
            ll cost=t.second;
            if(d1[v]>(d1[u]+cost)){
                d1[v]=d1[u]+cost;
                que.push({d1[v],v});
            }
        }
    }
}

void solve2(int s){
    fill(d2,d2+n,inf);
    d2[s]=0;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push({0,s});
    while(!que.empty()){
        P q=que.top(); que.pop();
        ll cur=q.first;
        int u=q.second;
        if(d2[u]<cur) continue;
        for(auto t:g2[u]){
            int v=t.first;
            ll cost=t.second;
            if(d2[v]>(d2[u]+cost)){
                d2[v]=d2[u]+cost;
                que.push({d2[v],v});
            }
        }
    }
}

int main(){
    cin >> n >> m >> s >> t;
    for(int i=0;i<m;i++){
        ll u,v,a,b; cin >> u >> v >> a >> b;
        u--; v--;
        g1[u].push_back({v,a});
        g1[v].push_back({u,a});
        g2[u].push_back({v,b});
        g2[v].push_back({u,b});
    }
    s--; t--;
    solve1(s);
    solve2(t);
    ll res=1e15;
    ll snuke=1e15;
    vector<ll> ans;
    for(int i=n-1;i>=0;i--){
        res=min(res,d1[i]+d2[i]);
        ans.push_back(snuke-res);
    }
    for(int i=ans.size()-1;i>=0;i--){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 21432
#include<bits/stdc++.h>
    using namespace std;
     
     
    int main(){
        int a,b,c;
        cin>>a>>b>>c;
        int d=b/a;
    
        if(d>=c){
            cout<<c<<endl;
        
        
        }
        if(d<c){
        cout<<d<<endl;
        
        }
    
        return 0;
    }

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		String S = sc.next();
		String ABC = null;
		int count = 0;

		for (int i = 0; i < A - 2; i++) {
			ABC = S.substring(i, i + 3);
			if (ABC.equals("ABC")) {
				count++;
			}

		}
		System.out.print(count);
		sc.close();
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; ++i)
#define rep2(i,a,n) for(int i=(a); i<(n); ++i)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

int main(){
  ll N, A, B; cin >> N >> A >> B;
  ll ans;
  if((B-A)%2 == 0) ans = (B-A)/2;
  else{ //ans = min(B-1, N-A);  
  ll t = min(N-B, A-1);
    if(t == N-B){B = N; A = A+(t+1);}
    else { A = 1; B =B-(t+1);}
    ans = t+1 + (B-A)/2;
  }
  cout << ans << endl;  
  return 0;

}

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

int main(){
	double a,b,c,d,e,f;
	double x,y;
	
	while(cin>>a>>b>>c>>d>>e>>f){
		y = (c*d-a*f) / (b*d-a*e);
		x = (c-b*y)/a;
		printf("%.3lf %.3lf\n",x,y);
	}
	
	
}

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

int main()
{
    while(1) {
        int x;
        int y;
        
        cin >> x >> y;
        
        if (x == 0 && y == 0) {
            break;
        }
        
        if (x > y) {
            cout << y << " " << x << endl;
        } else {
            cout << x << " " << y << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3084
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>
#include <cmath>
#include <numeric>
#include <iomanip>

using namespace std;

#define int long long

#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define rrep(i, n) for (int i=(int)n-1;i>=0;--i)
#define rrep1(i, n) for (int i=n;i>=1;--i)
#define range(i, l, r) for (int i=l;i<(int)r;++i)
#define rrange(i, l, r) for (int i=(int)r-1;i>=(int)l;--i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using ll=long long;
using vi=vector<int>;
using pii=pair<int, int>;
using ld=long double;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
constexpr int TEN(int n){return n==0?1:10*TEN(n-1);}

const int mod = TEN(9)+7;
const int inf = TEN(18) * 3 + 10;

int N, K;
vi A, F;

bool check(int x)
{
	int counter = 0;

	range(i, 0, N) {
		int v = A[i] * F[i];
		int zan = max(v - x, 0ll);
		counter += min((zan + F[i] - 1) / F[i], A[i]);
	}

	return counter <= K;
}

signed main()
{
	cin >> N >> K;
	A.resize(N), F.resize(N);

	rep(i, N) cin >> A[i];
	rep(i, N) cin >> F[i];

	sort(all(A));
	sort(all(F), greater<int>());

	int ok = inf, ng = -1;

	while (abs(ok - ng) > 1) {
		int m = (ok + ng) / 2;

		(check(m) ? ok : ng) = m;
	}

	cout << ok << endl;
}




Measured memory_bytes: 3328
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	let a: Vec<i64> = s.take(n).map(|a| a.parse().unwrap()).collect();
	let sieve = Sieve::new(1000000);
	let primes: Vec<i64> = sieve.primes().collect();
	let mut cnt = vec![0; 1000000];

	for &a in a.iter() {
		if sieve.is_prime(a as usize) {
			cnt[a as usize] += 1;
		} else {
			let mut n = a;
			for &p in primes.iter() {
				if p * p > n {
					break;
				}
				if n % p == 0 {
					cnt[p as usize] += 1;
					while n % p == 0 {
						n /= p;
					}
				}
			}
			if n > 1 {
				cnt[n as usize] += 1;
			}
		}
	}

	let mut ty = 0;
	for &p in primes.iter() {
		if cnt[p as usize] == n {
			ty = 2;
			break;
		}
		if cnt[p as usize] > 1 {
			ty = 1;
		}
	}

	let s = match ty {
		0 => "pairwise coprime",
		1 => "setwise coprime",
		2 => "not coprime",
		_ => unreachable!(),
	};
	println!("{}", s);
}


pub struct Sieve {
	sieve: Vec<u64>,
	n: usize,
}

impl Sieve {
	const BIT_LENGTH: usize = std::mem::size_of::<u64>() * 8;

	pub fn new(n: usize) -> Self {
		let base = (1..Self::BIT_LENGTH).step_by(2).fold(0, |r, i| r | 1 << i);
		let mut sieve = vec![base; n / Self::BIT_LENGTH + 1];
		sieve[0] ^= 0b0110;
		for p in (3..).step_by(2).take_while(|&i| i * i < n) {
			if sieve[p / Self::BIT_LENGTH] & (1 << p % Self::BIT_LENGTH) != 0 {
				for q in (p * p..=n).step_by(2 * p) {
					sieve[q / Self::BIT_LENGTH] &= std::u64::MAX ^ (1 << q % Self::BIT_LENGTH);
				}
			}
		}
		let r = n % Self::BIT_LENGTH;
		*sieve.last_mut().unwrap() &= ((1 << r) - 1) | 1 << r;
		Self { sieve, n }
	}

	pub fn is_prime<T>(&self, p: T) -> bool
	where
		T: std::convert::TryInto<usize>,
	{
		if let Ok(p) = p.try_into() {
			assert!(p <= self.n);
			self.sieve[p / Self::BIT_LENGTH] & (1 << p % Self::BIT_LENGTH) != 0
		} else {
			false
		}
	}

	pub fn primes<'a, T>(&'a self) -> impl 'a + std::iter::Iterator<Item = T>
	where
		T: std::convert::TryFrom<usize>,
	{
		let mut it = self.sieve.iter();
		let mut bits = 0;
		let mut p = 0;
		std::iter::from_fn(move || {
			while bits == 0 {
				if let Some(next) = it.next().cloned() {
					bits = next;
					p += Self::BIT_LENGTH;
				} else {
					return None;
				}
			}
			let lsb = bits & 0u64.wrapping_sub(bits);
			bits ^= lsb;
			let q = (p - Self::BIT_LENGTH) + lsb.trailing_zeros() as usize;

			T::try_from(q).ok()
		})
	}
}


Measured memory_bytes: 24960
// Author : Rifayat Samee (Sanzee)
// Problem :
// Algorithm:

/*

*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double eps = 1e-12;
struct Line{
    ll m,b;
    Line(ll x,ll y){
        m = x;
        b = y;
    }
    ll get_val(const ll x){
        return m*x + b;
    }
    double intersec_x(const Line L)const {
        double bb = L.b - b;
        double mm = m - L.m;
        return (bb/mm);
    }
};

int main(){

	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int n;
	ll C;
	scanf("%d %lld",&n,&C);
	vector<ll>H(n+1);
	for(int i=0;i<n;i++){
		scanf("%lld",&H[i]);
	}
	vector<Line>Q;
    int st = 0;
	ll prev = 0;
    for(int i=0;i<n;i++){
        while(Q.size()-st >=2 && Q[st].get_val(H[i]) >= Q[st+1].get_val(H[i])){
            st++;
        }
        if(i != 0)
            prev =  Q[st].get_val(H[i]) + H[i]*H[i] + C;
            //printf("%d %lld\n",i,prev);
        Line newline = Line(-2*H[i],prev+H[i]*H[i]);
        while(Q.size()-st>=2 && Q[Q.size()-1].intersec_x(newline)+eps < Q[Q.size()-2].intersec_x(newline)){
            //printf("%d %d\n",Q.)
            Q.pop_back();
        }
        Q.push_back(newline);
    }
    printf("%lld\n",prev);
    return 0;
}


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

int n , m , x , c[100001] , a[100001][13] ,ans , ok;
int main()
{
    cin >> n >> m >> x;
    for (int i = 0 ; i < n ; i++)
    {
        cin >> c[i];
        for (int j = 0 ; j < m ; j++)
            cin >>a[i][j];
    }
    int mn = 1e9;
     for (int msk = 1 ; msk <= (1 << n) ; msk++)
     {
         ans = 0 , ok = 1;
         int cnt[m + 1] = {0};
         for (int i = 0 ; i < n ; i++)
       {
           if ((msk & (1 << i)) ==0)continue;
           ans += c[i];
           for (int j = 0 ; j < m ; j++)
            cnt[j] +=a[i][j];
       }
       for (int u = 0 ; u < m ; u++)
       {
           ok &= (cnt[u] >= x);
       }
       if (ok)mn = min(mn , ans);
     }
     if (mn == 1e9)mn = -1;
     cout <<mn <<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>

int main(void)
{
	int a, b;
	char op;

	scanf("%d %c %d", &a, &op, &b);

	while (op != '?') {
		if (op == '+')
			printf("%d\n", a + b);
		else if (op == '-')
			printf("%d\n", a - b);
		else if (op == '*')
			printf("%d\n", a * b);
		else if (op == '/')
			printf("%d\n", a / b);

		scanf("%d %c %d", &a, &op, &b);
	}

	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;
int main(){
    ll x;
    cin>>x;
    ll d=x/11;
    ll r=x%11;
    if(0==r){
        cout<<2*d<<endl;
    }else{
        if(r<7){
            cout<<2*d+1ll<<endl;
        }else{
            cout<<2*d+2ll<<endl;
        }
    }
    return 0;
}

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

#define int long long

pair<int,int> arr[200005];
int ind[200005],n,k,nex=1;

int ft[200005];
inline int ls(int x){
  return x&(-x);
}
void update(int p,int v=1){
  for(;p<=200000;p+=ls(p))ft[p]++;
}
int query(int p){
  int ans=0;
  for(;p;p-=ls(p))ans+=ft[p];
  return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>k;
    int ans=0;
    arr[0]=make_pair(0,0);
    for(int x=1;x<=n;x++){
      cin>>arr[x].first;
      arr[x].first-=k;
      arr[x].second=x;
      if(x>0){
        arr[x].first+=arr[x-1].first;
      }
    }
    sort(arr,arr+n+1);
    for(int x=0;x<=n;x++){
      if(x>0 && arr[x].first!=arr[x-1].first)nex++;
      ind[arr[x].second]=nex;
    }
    for(int x=0;x<=n;x++){
      ans+=query(ind[x]);
      update(ind[x]);
    }
    cout<<ans;
    return 0;
}


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

vector<int> g[20];
bool done[20];
vector<int> res;

void func(int s)
{
	for (int i = 0; i < g[s].size(); i++){
		int t = g[s][i];
		if (done[t]) continue;
		func(t);
	}
	res.push_back(s);
	done[s] = true;
}

int main()
{
	int m, n;
	scanf("%d %d", &m, &n);
	for (int i = 0; i < n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		g[--a].push_back(--b);
	}
	for (int i = 0; i < m; i++){
		if (!done[i]){
			func(i);
		}
	}
	for (int i = res.size() - 1; i >= 0; i--){
		printf("%d\n", ++res[i]);
	}
}

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

int main() {
    int N; long long K;
    cin >> N >> K;
    vector<pair<long long, long long> > v(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;

    // ソート
    sort(v.begin(), v.end());
    
    // a_i が小さい順に b_i を合計して K 以上になる瞬間をとらえる
    long long res = 0;
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += v[i].second;
        if (sum >= K) {
            res = v[i].first; // sum >= K になった瞬間の a_i
            break;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <vector>

// @author: pashka

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> d(n, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        d[a - 1]++;
        d[b - 1]++;
    }
    for (int i = 0; i < n; i++) {
        cout << d[i] << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
int m,k;

int main()
{
	cin>>m>>k;
	if(k > (1 << m) - 1){
		puts("-1");
		return 0;
	}
	if(m == 1){
		if(k == 0)
		    printf("0 0 1 1\n");
		else
		    puts("-1");
		return 0;
	}
	
	printf("%d ",k);
	for(int i = 0;i <= (1 << m) - 1;i++){
		if(i != k)
		    printf("%d ",i);
	}
	printf("%d ",k);
	for(int i = (1 << m) - 1;i >= 0;i--){
		if(i != k)
		    printf("%d ",i);
	}
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1LL << 60;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
#define INF INT_MAX/2

int n, k, q;
vector<ll>a;
vector<ll>b;
int check(int mi, int ma) {
	int cnt = 0;
	int tmp = 0;
	int l = 0;
	rep(i, 0, n) {
		if (mi<=a[i]) {
			tmp += (a[i] <= ma);
			l++;
		}
		else {
			if(l >= k)cnt += (l-tmp+1 >= k)?tmp:max(l-k+1,0);
			tmp = 0;
			l = 0;
		}
	}
	if(l >= k)cnt += (l - tmp + 1 >= k) ? tmp : max(l - k + 1, 0);
	return cnt >= q;
}
int main() {
	cin >> n >> k >> q;
	a.resize(n);
	b.resize(n);
	rep(i, 0, n) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(all(b));

	ll ans = inf;
	rep(i, 0, n) {
		if (!check(a[i],b[n-1]))continue;
		if (check(a[i], a[i]))ans = 0;
		int ng = lower_bound(all(b),a[i])-b.begin(), ok = n - 1;
		while (ok - ng > 1) {
			int mid = (ok + ng) / 2;
			if (check(a[i], b[mid]))ok = mid;
			else ng = mid;
		}
		ans = min(ans,b[ok]-a[i]);
	}
	puts(ans);

	return 0;
}


Measured memory_bytes: 256