akhauriyash/Code-Regression huggingface dataset:
N,M,V,P = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

# idxでP-1番目まで（上からP個）は必ず選ばれうる
ok = P-1
# 最後が選ばれるかまだ分からない
ng = N

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2

    # idxでmid番目の問題が選ばれるか考える
    # M人全員が投票しても上位P位の最も小さいもの（P番目。idxでいうとP-1のやつ）を超えないなら無理
    if A[mid] + M < A[P-1]:
        ng = mid
        continue

    used = 0
    # 上からP-1個とmidには＋Mしてよい
    used += M*P

    # それ以外には、mid番目＋Mを超えないように＋してよい
    for i in range(P-1, N):
        # mid番目は既に足しているので飛ばす
        if i == mid:
            continue
        
        # mid番目＋Mを超えないように＋する。
        used += min(M, max(0, A[mid] + M - A[i]))

    # midにとって最も都合のいい割り振りで、投票数を使い切れるなら、上位P位に入れる可能性がある
    if used >= M*V:
        ok = mid
    else:
        ng = mid

# idxがokの問題までは選ばれうるので、ok+1個が選ばれうる
print(ok+1)

Measured memory_bytes: 14964
#include<stdio.h>
#define MAX 100000

int main(){
  int H, i;
  int A[MAX+1];

  scanf("%d",&H);

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

  for ( i = 1; i <= H; i++ ) {
    printf("node %d: key = %d, ",i,A[i]);

    if ( i / 2 >= 1 )
      printf("parent key = %d, ",A[i/2]);
    if ( 2*i <= H )
      printf("left key = %d, ",A[2*i]);
    if ( (2*i+1) <= H )
      printf("right key = %d, ",A[2*i+1]);

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



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

int n, m, x, ans, minn=1e9, a[20][20], c[20], f[20];
bool k;
void dfs(int pos)
{
    if(pos==n+1)
    {
        return;
    }
    
    for(int i=0; i<=1; i++)
    {
        k=true;
        ans+=c[pos]*i;
        for(int j=1; j<=m; j++)
        {
            f[j]+=i*a[pos][j];
            if(f[j]<x) k=false;
        }
        if(k==true)
        {
            minn=min(ans, minn);
            for(int j=1; j<=m; j++)
                f[j]-=i*a[pos][j];
            ans-=c[pos]*i;
            continue;
        }
        dfs(pos+1);
        for(int j=1; j<=m; j++)
            f[j]-=i*a[pos][j];
        ans-=c[pos]*i;
    }
}

int main(void)
{
    scanf("%d%d%d", &n, &m, &x);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &c[i]);
        for(int j=1; j<=m; j++)
            scanf("%d", &a[i][j]);
    }
    
    dfs(1);
    
    if(minn==1e9) printf("-1\n");
    else printf("%d\n", minn);
    return 0;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  V<lint> cum(n + 1);
  for (int i = 0; i < n; ++i) {
    cum[i + 1] = cum[i] + a[i];
  }
  V<lint> cum2(n + 1);
  for (int i = 0; i < n; ++i) {
    cum2[i + 1] = (i ? cum2[i - 1] : 0) + a[i];
  }
  while (q--) {
    int x; cin >> x;
    int k = lower_bound(begin(a), end(a), x) - begin(a);
    if (k == 0) {
      cout << cum[n] - cum[n / 2] << '\n';
      continue;
    }
    if (k == n) {
      cout << cum2[n] << '\n';
      continue;
    }
    auto is_taka = [&](int i) -> bool {
      int taka = n - 1 - i;
      int aoki = (begin(a) + i) - lower_bound(begin(a), end(a), 2 * x - a[i]);
      return taka <= aoki;
    };
    int ng = k - 1, ok = n - 1;
    while (ok - ng > 1) {
      int m = ng + ok >> 1;
      (is_taka(m) ? ok : ng) = m;
    }
    lint res = cum[n] - cum[ok];
    res += cum2[max(2 * ok - n, 0)];
    cout << res << '\n';
  }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
int main(){
    // Your code here!
  int a,b,c,count;
  cin>>a>>b>>c;
  count=0;
  for(int i=a;i<=b;i++){
     if(c%i==0){
         count++;
     } 
  }
  cout<<count<<endl;
}  




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

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    int a[q], b[q], c[q], d[q];
    map<int, int> mp;
    for (int i = 0; i < q; i++)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        mp.insert({d[i], i});
    }

    int A[n+1];
    int p[10];
    int max = 0;
    rep(p[0], 1, m) rep(p[1], p[0], m) rep(p[2], p[1], m) rep(p[3], p[2], m) rep(p[4], p[3], m) rep(p[5], p[4], m) rep(p[6], p[5], m) rep(p[7], p[6], m) rep(p[8], p[7], m) rep(p[9] , p[8], m)
    {
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            A[i+1] = p[i];
        }

        for (int i = 0; i < q; i++)
        {
            if (A[b[i]] - A[a[i]] == c[i])
            {
                res += d[i];
            }
        }

        if (res > max)
            max = res;
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 3632
import sys
import math
input = sys.stdin.readline

def main():
    a, b, c = map(int, input().split())

    t = c - a - b

    if (t > 0) and  ((4 * a * b) < (t ** 2)):
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()


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

int main(){
  int N;
  cin >> N;
  vector<int> data(26);
  vector<string> data2;
  vector<int> data3;
  
  rep(i,N){
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    data2.push_back(S);
  }
  
  sort(data2.begin(), data2.end());
  data2.push_back("  ");
  
  int64_t count = 0;
  
  for(int i=0; i < N; i++){
    if(data2.at(i) == data2.at(i+1)) {
      count++;
    } else {
      data3.push_back(count);
      count = 0;
    }
  }
  
  int64_t ans = 0;
  for (int64_t x : data3){
    ans += x * (x + 1) /2;
  }
  cout << ans << endl;
  
}


Measured memory_bytes: 6644
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repin(Array,n) for(int i=0;i<n;i++){cin>>Array[i];}
using namespace std;

using ll = long long;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;
using Graph = vector<vector<int>>;

int main() {

	int N;
	cin >> N;
	vector<int>A(N);
	vector<bool>flag(N);
	rep(i, N) {
		int a;
		cin >> a;
		A[i] = a - 1;
	}

	int now = A[0];
	flag[0] = true;
	int count = 0;
	while (1) {
		count++;
		if (flag[now])
			break;
		if (now == 1) {
			cout << count << endl;
			return 0;
		}

		flag[now] = true;
		now = A[now];
	}

	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

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

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


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

    int k;
    cin >> k;

    vs64 a(k);
    rep (i, k) cin >> a[i];

    s64 nmax = 2;
    s64 nmin = 2;
    for (int i = k - 1; i >= 0; --i)
    {
        if (!IN(nmin, nmax + 1, CEIL(nmin, a[i]) * a[i]))
        {
            cout << "-1\n";
            return 0;
        }
        nmax = nmax / a[i] * a[i] + a[i] - 1;
        nmin = CEIL(nmin, a[i]) * a[i];
    }

    cout << nmin << " " << nmax << "\n";
    return 0;
}



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

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //-----------------------------------------
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if(s==u)
    {
        --a;
    }
    else
    {
        --b;
    }

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


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[]args) {
		Scanner sc=new Scanner(System.in);
		String po=sc.nextLine();
      String p[]=po.split("/",0);
		System.out.println((Integer.parseInt(p[1])<5)?"Heisei":"TBD");
	}
}


Measured memory_bytes: 21584
#include<bits/stdc++.h>
typedef long long     ll;
using namespace std;
ll mp[100005]={0};
int main()
{
    ll n,sum=0,x,y;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        mp[x]++;
        sum+=x;
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>x>>y;
        mp[y]+=mp[x];
        sum-=(mp[x]*x);
        sum+=(mp[x]*y);
        mp[x]=0;
        cout << sum << endl;
    }
}


Measured memory_bytes: 4384
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();

    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let ps = buf.split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect::<Vec<_>>();

    let mut ans = 0;

    for i in 2..n {
        if ps[i-1] < ps[i-2] && ps[i] < ps[i-1] {
            ans += 1;
        }
        else if ps[i-1] < ps[i] && ps[i-2] < ps[i-1] {
            ans += 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<string>
using namespace std;
 
int main() {
    int N;
    int re = 0;
    cin >> N ;

    for(int i = 0; i < N; i++){
        int a, b, c;
        cin >> a >> b;
        c = b - a +1;
        re += c;
    }

    cout << re << endl;
    return 0;
}

Measured memory_bytes: 256
x1,y1,x2,y2 = map(int,input().split())

vec_x = x2-x1
vec_y = y2-y1
x3,y3 = (x2-vec_y, y2+vec_x)
x4,y4 = (x3-vec_x, y3-vec_y)
print("{} {} {} {}".format(x3,y3,x4,y4))

Measured memory_bytes: 3060
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  int d,n;
  int degree[205];
  int clothes[200][3];
  int i,j,k;
  int dp[205][205]={};

  cin>>d>>n;
  rep(i,d)
    cin>>degree[i];
  rep(i,n)
    cin>>clothes[i][0]>>clothes[i][1]>>clothes[i][2];

  rep(j,n)
    if(clothes[j][0] > degree[0] || degree[0] > clothes[j][1])
      dp[0][j]=-1;

  for(i=1;i<d;i++)
    rep(j,n){
      if(clothes[j][0] > degree[i] || degree[i] > clothes[j][1]){
	dp[i][j]=-1;
	continue;
      }
      int m=0;
      rep(k,n)
	if(dp[i-1][k] >= 0)
	  m=max(m,dp[i-1][k]+abs(clothes[k][2]-clothes[j][2]));
      dp[i][j]=m;   
    }

  int ans=0;
  rep(j,n)
    ans=max(ans,dp[d-1][j]);
  cout<<ans<<endl;

}

Measured memory_bytes: 1336
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	char a,b,c;
	scanf("%c%c%c",&a,&b,&c);
	if(a=='9')a='1';else a='9';
	if(b=='9')b='1';else b='9';
	if(c=='9')c='1';else c='9';
	printf("%c%c%c\n",a,b,c);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define int int long long // 2e9 & 9e18
using namespace std; const int inf = numeric_limits<int>::max();
struct __io{__io(){ios_base::Init i; ios_base::sync_with_stdio(0); cin.tie(0);}} __io; // fast I/O
#ifdef LOCAL // setting up print debugging (yes lol)
template<class K, class V>ostream& operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.x<<", "<<p.y<<'>';return s;}
template<class T, class=typename T::value_type, class=typename enable_if<!is_same<T,string>::value>::type>
ostream& operator<<(ostream&s,const T&v){s<<'[';for(auto&x:v){s<<x<<", ";}if(!v.empty()){s<<"\b\b";}s<<']';return s;}
void __prnt(){cerr<<endl;} template<class T, class...Ts>void __prnt(T&&a,Ts&&...etc){cerr<<a<<' ';__prnt(etc...);}
#define print(...) __prnt(__VA_ARGS__)
#else
#define print(...)
#endif

signed main() {
    int x;
    cin >> x;
    int l = lcm(x, 360);
    cout << l / x << endl;
}


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

#define x first
#define y second
#define ndl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define bit __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
using namespace __gnu_pbds;

template<typename T> using indexed_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<int, ull> piu;
typedef vector<vector<int>> matrix;

const ll INF = 1e18 + 123;
const ld EPS = 1e-9;
const int inf = 1e9 + 123;
const int MOD = 1e9 + 7;
const int N = 5e5 + 123;
const int M = 1e6 + 123;
const double pi = acos(-1.0);
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

void solve(){
    int n;
    cin >> n;
    cout <<fixed<<setprecision(2) << 2*pi*n;
}

int main(){
    #ifdef KAZAKH
        //freopen("input.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++){
        //cout << "case #" << i << ": ";
        solve();
    }
    return 0;
}


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

int main() {
    int N, Y; cin >> N >> Y;
    bool b = false;
    for (int man = 0; man <= N; man++) {
        for (int gosen = 0; gosen <= N - man; gosen++) {
            int sen = N - man - gosen;
            int sum = 10000 * man + 5000 * gosen + 1000 * sen;
            if (sum == Y) {
                cout << man << " " << gosen << " " << sen << endl;
                b = true;
                break;
            }
        }
        if (b) break;
    }
    if (!b) cout << "-1 -1 -1" << endl;
    return 0;
}

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

struct Node {
	int key;
	Node *p, *l, *r;
};

Node *nil;
Node *root = nil;

void insert(int k) {
	Node *y = nil;
	Node *x = root;
	Node *z = new Node;
	z->key = k;
	z->l = nil;
	z->r = nil;
	while (x != nil) {
		y = x;
		if (z->key < x->key) x = x->l;
		else x = x->r;
	}
	z->p = y;
	if (y == nil) root = z;
	else {
		if (z->key < y->key) y->l = z;
		else y->r = z; 
	}
}

void inorder(Node *root) {
	if (root == nil) return;
	inorder(root->l);
	cout << ' ' << root->key;
	inorder(root->r);
}

void preorder(Node *root) {
	if (root == nil) return;
	cout << ' ' << root->key;
	preorder(root->l);
	preorder(root->r);
}

void print() {
	inorder(root);
	cout << endl;
	preorder(root);
	cout << endl;
}

void find(int key) {
	Node *x = root;
	while (x != nil) {
		if (key == x->key) {
			cout << "yes" << endl;
			return;
		} else if (key < x->key) {
			x = x->l;
		} else x = x->r;
	}
	cout << "no" << endl;
}

int main() {
	int n, key;
	char cmd[10];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> cmd;
		if (cmd[0] == 'i') {
			cin >> key;
			insert(key);
		} else if (cmd[0] == 'f') {
			cin >> key;
			find(key);
		} else print();
	}

	return 0;
}

Measured memory_bytes: 19940
#include<iostream>
using namespace std;
long long H, W, L;
char x[102][102], T[5] = "NESW"; int dp[102][102][4];
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
int main() {
	while (true) {
		for (int i = 0; i < 102; i++) {
			for (int j = 0; j < 102; j++) {
				x[i][j] = '#';
				for (int k = 0; k < 4; k++)dp[i][j][k] = -1;
			}
		}
		cin >> H >> W >> L; int D = 0, X = 0, Y = 0;
		if (H == 0 && W == 0 && L == 0)break;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				cin >> x[i][j];
				if (x[i][j] != '#' && x[i][j] != '.') {
					for (int k = 0; k < 4; k++) {
						if (T[k] == x[i][j]) {
							x[i][j] = '.'; D = k; X = i; Y = j;
						}
					}
				}
			}
		}
		int cnt = 0; dp[X][Y][D] = 0; long long V = 0, Z = 0, C = 0, F = 0;
		while (true) {
			if (x[X + dx[D]][Y + dy[D]] == '#') {
				D = (D + 1) % 4;
			}
			else {
				X += dx[D]; Y += dy[D]; cnt++;
				if (dp[X][Y][D] != -1) {
					V = dp[X][Y][D]; Z = cnt; goto E;
				}
				else {
					dp[X][Y][D] = cnt;
					if (cnt == L) {
						cout << X << ' ' << Y << ' ' << T[D] << endl;
						goto F;
					}
				}
			}
		}
	E:;
		C = (Z - V); F = (L - Z) % C; F += V;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				for (int k = 0; k < 4; k++) {
					if (dp[i][j][k] == F) {
						cout << i << ' ' << j << ' ' << T[k] << endl;
					}
				}
			}
		}
	F:;
	}
	return 0;
}

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


void solve(long long K, std::string S){
  if (S.size() > K) {
    S = S.substr(0, K);
    S += "...";
  }
  cout << S << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long K;
    scanf("%lld",&K);
    std::string S;
    std::cin >> S;
    solve(K, S);
    return 0;
}

Measured memory_bytes: 3696
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define MAX 200000

int tail = 0;

int head = 0;

typedef struct _queue {
    char name[10];
    int time;
}queuecell;

queuecell queue[MAX];

void enqueue(char *name, int time) {
    tail++;
    strcpy(queue[tail].name, name);
    queue[tail].time = time;
    head++;
}

queuecell dequeue() {
    queuecell cell;

    strcpy(cell.name, queue[head].name);
    cell.time = queue[head].time;
    head++;

    return cell;
}

int main() {
    int n, maxtime;
    int sumtime = 0;
    cin >> n;
    cin >> maxtime;
    queuecell cell;

    for(int i=0; i<n; i++) {
        cin >> queue[i].name;
        cin >> queue[i].time;
    }
    tail = n-1;


    while(tail>=head) {
        if(queue[head].time>maxtime) {
            sumtime += maxtime;
            enqueue(queue[head].name, queue[head].time-maxtime);
        }
        else {
            cell = dequeue();
            sumtime += cell.time;
            printf("%s %d\n", cell.name, sumtime);
        }
    }
}


Measured memory_bytes: 5996
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){

	int n;
	int card[3][10];

	cin>>n;

	while(n--){
			
		int a[10];
			
		memset(card, 0, sizeof(card));

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

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

			char b;
			cin>>b;
			card[b=='R'?0:b=='G'?1:2][a[i]]++;
		}

		int cnt = 0;

		for(int c=0; c<3; ++c){
			for(int k=1; k<=9; ++k){
				
				cnt += card[c][k]/3;
				card[c][k] %= 3;
				
				if(k<=7){
					
					int sub = min(card[c][k], min(card[c][k+1], card[c][k+2]));

					for(int i=0; i<3; ++i){
						card[c][k+i] -= sub;
					}

					cnt += sub;
				}
			}
		}

		cout << (cnt>=3) << endl;
	}	
	
	return 0;
}

Measured memory_bytes: 1160
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e7+7;
const ll inf=1e18;
const ll ms=2e5+5;
fast;
void solve()
{
    ll n,m;
    cin>>n;
    if(n<105)
        cout<<0;
    else if(n<135)
        cout<<1;
    else if(n<165)
        cout<<2;
    else if(n<189)
        cout<<3;
    else if(n<195)
        cout<<4;
    else
        cout<<5;
}
int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    //int t;cin>>t;for(int te=1;te<=t;te++)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define mod (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<x<<endl
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
typedef vector<int> vi;

int tmp,mi=inf,n,l,sum,sign;
int main(void){
    cin>>n>>l;
    rep(i,1,n+1){
        tmp=l+i-1;
        sum+=tmp;
        mi=min(mi,abs(tmp));
        if(tmp<0)sign=-1;
        else sign=1;
    }
    if(sign<0)p(sum+mi);
    else p(sum-mi);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int a,b;
cin>>a>>b;
int c[a];
int d[b];
for(int i=1;i<=a;i++){
c[i]=b;
}
for(int i=1;i<=b;i++){
d[i]=a;
}
/*if(c[1]<d[1]){
for(int i=1;i<=a;i++){
cout<<c[i];
}
}
else if(d[1]<c[1]){
for(int i=1;i<=a;i++){
cout<<d[i];
}
}
else{
int i=1;
while((c[i]==d[i]) || (i<=a) || (i<=b)){
i++;

}
if(i<=min(a,b)){
int k=c[i];
int l=d[i];
if(k<=l){
for(int i=1;i<=a;i++){
cout<<c[i];
}
}
else{
for(int i=1;i<=a;i++){
cout<<d[i];
}
}
}
else {
int k=min(a,b);
if(k==a){
for(int i=1;i<=a;i++){
cout<<d[i];
}
}
else{
for(int i=1;i<=a;i++){
cout<<c[i];
}
}
}
}
}*/
if(a==b){
    for(int i=1;i<=a;i++){
        cout<<c[i];
    }
}
else if(a<b){
    for(int i=1;i<=b;i++){
        cout<<d[i];
    }
}
else if(b<a){
    for(int i=1;i<=a;i++){
        cout<<c[i];
        
    }
}
}

Measured memory_bytes: 256
#include <stdio.h>
 
main(){
 
  long d = 1;
  long a,b,c;
 
  scanf("%ld %ld",&a,&b);
 
if(b>a){
c = a;
a = b;
b = c;
}
 
  while(d != 0){
    d = a % b;
    a = b;
    b = d;
  }
 
  printf("%ld\n",a);
}

Measured memory_bytes: 2696
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

using namespace std;

int main()
{
    IOS;
    char a,b;
    cin >> a >> b;
    if(a >= b)
        swap(a,b);
    for(int i = 1; i <= b-'0';i++)
        cout << a;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
int main(){
	int A,B;
	cin>>A>>B;
	if(A==1)A+=13;
	if(B==1)B+=13;
	if(A>B){
	        cout<<"Alice"<<endl;
	}else if(A<B){
		        cout<<"Bob"<<endl;
	}else{
		        cout<<"Draw"<<endl;
	}
	return(0);
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayDeque<Integer> ans = new ArrayDeque<Integer>();

		while(sc.hasNext()){
			int n = sc.nextInt();
			ans.push((n*(n+1)/2)+1);
			
		}
		int num = ans.size();
		for(int i=0;i<num;i++){
			System.out.println(ans.pollLast());
		}
	}
}

Measured memory_bytes: 17204
class combnk_mod(object):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.
    def __init__(self, maxn, p):
        self.maxn = maxn
        self.p = p
        self.x = [1] # 分母にあたる数 1 / n! mod p
        self.y = [1] # 分子にあたる数. n! mod p
        for i in range(1, self.maxn + 1):
            self.x.append(self.x[-1] * pow(i, self.p - 2, self.p) % self.p)
            self.y.append(self.y[-1] * i % self.p)

    def combnk(self, n, k):
        return (self.x[n - k] * self.x[k] * self.y[n]) % self.p

h, w, a, b = map(int, input().split())
MOD = 10 ** 9 + 7
c = combnk_mod(h + w, MOD)
ans = 0
for i in range(b + 1, w + 1):
    ans += c.combnk(h - a + i - 2, i - 1) * c.combnk(a + w - i - 1, a - 1) % MOD
    ans %= MOD
print(ans)


Measured memory_bytes: 18872
#include <stdio.h>
#include <math.h>
int judge(int);
int main(){
  int A[10000],i,n,cnt=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    }
  for(i=0;i<n;i++){
    if (judge(A[i])==3)cnt++;
    }
  printf("%d\n",cnt);
  return 0;
}

int judge(int x){
  int i;
  if(x==2)return 3;
  if(x<2)return 1;
  if(x%2==0)return 1;
  
  for(i=3;i<=sqrt((double)x);i+=2){
    if(x%i==0)return 1;
  }
  return 3;
}



Measured memory_bytes: 2064
N = int(input())

lis = [""]
ans = "Yes"
for i in range(1,N+1):
    W = input()
    if i == 1:
        pass
    else:
        if ((W in lis) == False) and (W[0] == lis[i-1][-1]):
            pass
        else:
            ans = "No"
    lis.append(W)

print(ans)

Measured memory_bytes: 9128
import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		ArrayList<ArrayDeque<Integer>> ar = new ArrayList<>();
		for (int i=0; i<n; i++) ar.add(new ArrayDeque<>());
		int m = sc.nextInt();
		for (int i=0; i<m; i++) {
			int mode = sc.nextInt();
			if (mode == 0) {
				ar.get(sc.nextInt()).addLast(sc.nextInt());
			}
			else if (mode == 1) {
				int temp = sc.nextInt();
				if (ar.get(temp).peekFirst() != null) System.out.println(ar.get(temp).getFirst());
			}
			else if (mode == 2) {
				int temp = sc.nextInt();
				if (ar.get(temp).peekFirst() != null) ar.get(temp).removeFirst();
			}
		}
		
	}
}


Measured memory_bytes: 167928
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main(void){
  string A;
  cin >> A;
  if(A.at(5) == '1'){
    cout << "TBD";
  } else if(A.at(6) == '1' || A.at(6) == '2' || A.at(6) == '3' || A.at(6) == '4'){
    cout << "Heisei";
  } else {
    cout << "TBD";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int k,a[100001],a1,b[2000001],b1=1,b2=9;
int main()
{
	memset(a,0x3f,sizeof(a));
	scanf("%d",&k);
	for(int i=1;i<10;i++)b[i]=a[i]=i;
	while(b1<=b2)
	{
		for(int i=0;i<10;i++)if(a[(b[b1]*10+i)%k]>a[b[b1]]+i)a[b[++b2]=(b[b1]*10+i)%k]=a[b[b1]]+i;
		++b1;
	}
	printf("%d",a[0]);
	return 0;
}

Measured memory_bytes: 8448
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
 
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;


#define PB push_back
#define MP make_pair
#define F first
#define S second

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}


int main(){
	ll a,b;
  	cin >> a >> b;
  	if(a>b){
    	cout << "safe" << endl;
    }else{
    	cout << "unsafe" << endl;
    }
}



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

int main(){
    int K,X;
    cin >> K >> X;
    for(int i= -K+1;i<K;i++){
        if(i != K-1){
            cout << X+i << " ";
        }else{
            cout << X+i << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#define rep(i, n) for(int i = 0; i < (int)n ; i++)
using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    int count = 0;

    for(int i=A; i <= B ; i++){
        int number = i;
        int number_1 = number % 10;//1の位
        number /= 10;//10の位
        int number_10 = number % 10;//10の位
        number /= 10;
        number /= 10;
        int number_1000 = number % 10;//1000の位
        number /= 10;
        int number_10000 = number % 10000;//10000の位

        if(number_1 == number_10000 && number_10 == number_1000){
            count++;
        }

    }

    cout << count << endl;
}

Measured memory_bytes: 3604
n = int(input())
nLis = []
for i in range(n):
    nLis.append(input())
m = int(input())
mLis = []
for i in range(m):
    mLis.append(input())
cnt = 0
sLis = set(nLis)
for j in sLis:
    tmp = nLis.count(j) - mLis.count(j)
    cnt = max(cnt,tmp)
print(max(cnt,0))

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <limits>
#include <algorithm>
#include <utility>
#include <sstream>
#include <numeric>
#include <iterator>

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef pair<int, int> P;

int main(int argc, const char * argv[]) {
  int n, m;
  cin >> n >> m;
  // vector<int> vec;
  // rep(i, n) vec.push_back()
  // do {
  //   print(v);
  // } while (std::next_permutation(v.begin(), v.end()));
  if(n == 1 && m == 1){
    cout << 0 << endl;
    return 0;
  }
  if(n == 1){
    cout << (m * (m-1)) / 2 << endl;
    return 0;
  }
  if(m == 1){
    cout << n * (n-1) / 2 << endl;
    return 0;
  }
  cout << (n * (n-1) / 2) + (m * (m-1) / 2) << endl;
  return 0;
}


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

#define pb push_back
#define mp make_pair

typedef long long ll;

const int inf = 1e9;
const ll linf = 1e18;
const ll mod = 1e9 + 7;

int n, m;
vector<int> e[50];
int a[50], b[50];
bool used[50];

void dfs(int x, int y)
{
  if(used[x]) return;

  used[x] = true;

  for(auto u : e[x]){
    if((x == a[y] and u == b[y]) or (x == b[y] and u == a[y])) continue;

    dfs(u, y);
  }
}

int main()
{
  cin >> n >> m;

  for(int i = 0; i < m; i++){
    cin >> a[i] >> b[i];
    a[i]--; b[i]--;
    e[a[i]].pb(b[i]);
    e[b[i]].pb(a[i]);
  }

  int ans = 0;
  for(int i = 0; i < m; i++){
    for(int i = 0; i < n; i++) used[i] = false;

    dfs(0, i);

    int cnt = 0;
    for(int i = 0; i < n; i++) if(used[i]) cnt++;
    if(cnt != n) ans++;
  }

  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define x   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;
typedef vector<int>     vi;

int a[N];

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

    int n;  cin >> n;
    int k;  cin >> k;
    int q;  cin >> q;

    vector<int> val;

    for(int i = 1 ; i <= n ; ++i)   {
        cin >> a[i];
        val.pb(a[i]);
    }
    sort(all(val));
    val.erase(unique(all(val)),val.end());

    int ans = 1e9;

    for(int x : val)    {
        vector<vi>  vec;
        vector<int> cur;

        for(int i = 1 ; i <= n ; ++i)   {
            if (a[i] < x)   {
                if (cur.size()) {
                    vec.pb(cur);
                    cur.clear();
                }
                continue;
            }
            cur.pb(a[i]);
        }
        if (cur.size())
            vec.pb(cur);
        
        vector<int> nvec;

        for(vi  V : vec)    {
            sort(all(V));

            for(int i = 0 ; i <= sz(V) - k ; ++i)
                nvec.pb(V[i]);
        }
        sort(all(nvec));

        if (sz(nvec) < q)
            continue;

        if (ans > nvec[q - 1] - x)
            ans = nvec[q - 1] - x;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

main = do
  [a, b, c] <- readInt
  if a + b >= c
    then putStrLn "Yes"
    else putStrLn "No"


Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
 
#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	long long N,M;
  cin >> N >> M;
  long long ans = N % M;
  if(ans > abs(ans - M)){
    cout << abs(ans - M) <<endl;
  }else{
    cout << ans << endl;
  }
}

Measured memory_bytes: 3612
import sys
n, m = map(int, input().split())
a = list(map(int, input().split()))

sum_touhyou = sum(a)

a.sort(reverse=True)
for i in range(m):
  if a[i] / sum_touhyou < 1 / (4*m):
    print('No')
    sys.exit()

print('Yes')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,ans=0,m;
    cin>>n;
    m=n+2;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(m>a[i]){ans++;}
        m=min(m,a[i]);
    }
    cout<<ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int n; cin >> n;
    ll d = n%10;

    if(d == 3){
        cout << "bon" << endl;
    }
    else if(d == 0 || d == 1 ||d == 6 ||d == 8){
        cout << "pon" << endl;
    }
    else{
        cout << "hon" << endl;
    }
    
}

Measured memory_bytes: 3636
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int n;
    string s;
    R(n,s);
    int an=0;
    REP(i,n){
        if(s.substr(i,3)=="ABC")an++;
    }
    W(an);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  string s;
  cin >> s;
  if (s[len(s) - 1] == 's') {
    s += "es";
  } else {
    s += "s";
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define mems(p) memset(p,0,sizeof(p))
#define mp make_pair

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

struct Exam {
	ll b, l, u;

	Exam() {

	}

	Exam(ll b, ll l, ll u) {
		this->b = b;
		this->l = l;
		this->u = u;
	}
};

ll n, x, b, l, u, bSum;

ll calculateGain(Exam exam) {
	ll examB = exam.b * exam.u;
	ll examA = x * exam.u;
	ll examLB = exam.b * exam.l;
	return examA - examB + examLB;
}

bool sorter(Exam exam1, Exam exam2) {
	return calculateGain(exam1) > calculateGain(exam2);
}

Exam exams[100001];

bool canWin(ll scores) {
	int idx;
	ll tempSum = 0;
	for (int i = 0; i < scores/x + 1; ++i)
	{
		tempSum += calculateGain(exams[i]);
	}

	if (scores % x == 0) {
		return bSum - (tempSum - calculateGain(exams[scores/x])) <= 0;
	}
	ll bestGain;
	ll left = scores % x;
	for (int i = 0; i < n; ++i)
	{
		idx = (i < scores/x + 1) ? i : scores/x;
		if (left > exams[i].b) {
			bestGain = exams[i].u * (left - exams[i].b) + exams[i].b * exams[i].l;
		} else {
			bestGain = exams[i].l * left;
		}

		if (bSum - tempSum + calculateGain(exams[idx]) - bestGain <= 0) {
			return true;
		}
	}
	return false;
}

ll binSer() {
	ll l = 0;
	ll r = n * x;
	ll mid;
	while (l <= r) {
		mid = (l + r) / 2;
		bool win = canWin(mid);
		if (win) {
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	for (ll i = max(0ll, mid - 1); i <= n * x; ++i)
	{
		if (canWin(i)) {
			return i;
		}
	}
	return 0;
}

int main() {
	fast();
	cin >> n >> x;
	bSum = 0ll;
	for (int i = 0; i < n; ++i)
	{
		cin >> b >> l >> u;
		exams[i] = Exam(b, l, u);
		bSum += l * b;
	}
	sort(exams, exams + n, sorter);
	cout << binSer() << endl;
	// 1715610791
}

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

template <typename T> void read_stdin(const size_t size, vector<T>& array)
{
   T value;
   for (size_t i(0); i < size; ++i) {
      cin >> value;
      array.push_back(value);
   }
}

template <typename T> void output_stdout(const vector<T>& array)
{
   for (const auto& value : array) {
      cout << value << endl;
   }
}

int main() {
   string output;

   // read
   size_t inputA, inputB;
   {
      cin >> inputA;
      cin >> inputB;
   }

   // process
   {
      if (inputA > inputB) {
         output = string(inputA, to_string(inputB).c_str()[0]);
      } else {
         output = string(inputB, to_string(inputA).c_str()[0]);
      }
   }

   // output
   {
      cout << output << endl;
   }
   
   return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))

counter = defaultdict(int)
for ai in a:
    counter[min(ai // 400, 8)] += 1
ans = 0
for i in range(8):
    if counter[i] > 0:
        ans += 1
if ans == 0:
    print(1, counter[8])
else:
    print(ans, ans + counter[8])


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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5+5;


int main(){
    string s;
    cin >> s;
    if(s[2] == s[3] && s[4] == s[5]){
        cout << "Yes";
    } else {
        cout << "No";
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
    long long x;
public:
    mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }

    mint operator^(const ll& t)const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD - 2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream& operator<<(ostream& os, const mint& m) {
        os << m.x;
        return os;
    }
};

//////////////////////////


int main() {
    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A(N + 1);
    repn(i, N) cin >> A[i];

    ll ans = INF;
    
    repn(i, N) {
        ll M = A[i];
        vector<ll> elim;
        vector<vector<ll>> use(N+1);
        ll c = 1;
        repn(j, N) {
            if (A[j] >= M) { use[c].push_back(A[j]); }
            else { c++; }
        }

        repn(j, N) {
            if (use[j].size() < K) { continue; }
            sort(use[j].begin(), use[j].end());
            rep(k, use[j].size() - K + 1) { elim.push_back(use[j][k]); }
        }

        if (elim.size() < Q) { continue; }
        sort(elim.begin(), elim.end());

        ans = min(ans, elim[Q - 1] - elim[0]);
    }

    cout << ans;

	system("PAUSE");
}

Measured memory_bytes: 632
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
memo = [0]*(100001)
for i in a:
    memo[i]+=1
ans=sum(a)
for i in range(q):
    b,c=bc[i][0],bc[i][1]
    heru=b*memo[b]
    hueru=c*memo[b]
    memo[c]+=memo[b]
    memo[b]=0
    ans = ans-heru+hueru
    print(ans)

Measured memory_bytes: 32256
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;

#define rep(i,b) for(i=0;i<b;++i)
#define repp(i,a,b) for(i=a;i<b;++i)

int main() {
    double n, k;
    cin >> n >> k;
    ll ans = ceil(double(n/k));
    cout << ans;

    return 0;
}
/*
         ,--"""",--.__,---[],-------._
       ,"   __,'            \         \--""""""==;-
     ," _,-"  "/---.___     \       ___\   ,-'',"
    /,-'      / ;. ,.--'-.__\  _,-"" ,| `,'   /
   /``""""-._/,-|:\       []\,' ```-/:;-. `. /
             `  ;:::      ||       /:,;  `-.\
                =.,'__,---||-.____',.=
                =(:\_     ||__    ):)=
               ,"::::`----||::`--':::"._
             ,':::::::::::||::::::::::::'.
    .__     ;:::.-.:::::__||___:::::.-.:::\     __,
       """-;:::( O )::::>_|| _<::::( O )::::-"""
   =======;:::::`-`:::::::||':::::::`-`:::::\=======
    ,--"";:::_____________||______________::::""----.          , ,
         ; ::`._(    |    |||     |   )_,'::::\_,,,,,,,,,,____/,'_,
       ,;    :::`--._|____[]|_____|_.-'::::::::::::::::::::::::);_
      ;/ /      :::::::::,||,:::::::::::::::::::::::::::::::::::/
     /; ``''''----------/,'/,__,,,,,____:::::::::::::::::::::,"
     ;/                :);/|_;| ,--.. . ```-.:::::::::::::_,"
    /;                :::):__,'//""\\. ,--.. \:::,:::::_,"
   ;/              :::::/ . . . . . . //""\\. \::":__,"
   ;/          :::::::,' . . . . . . . . . . .:`::\
   ';      :::::::__,'. ,--.. . .,--. . . . . .:`::`
   ';   __,..--'''-. . //""\\. .//""\\ . ,--.. :`:::`
   ;    /  \\ .//""\\ . . . . . . . . . //""\\. :`::`
   ;   /       . . . . . . . . . . . . . . . . .:`::`
   ;   (          . . . . . . . . . . . . . . . ;:::`
   ,:  ;,            . . . . . . . . . . . . . ;':::`
   ,:  ;,             . . . . . . . . . . . . .;`:::
   ,:   ;,             . . . . . . . . . . . . ;`::;`
    ,:  ;             . . . . . . . . . . . . ;':::;`
     :   ;             . . . . . . . . . . . ,':::;
      :   '.          . . . . . . . .. . . .,':::;`
       :    `.       . . . . . . . . . . . ;::::;`
        '.    `-.   . . . . . . . . . . ,-'::::;
          `:_    ``--..___________..--'':::::;'`
             `._::,.:,.:,:_ctr_:,:,.::,.:_;'`
________________`"\/"\/\/'""""`\/"\/""\/"____________________________

*/


Measured memory_bytes: 256