akhauriyash/Code-Regression huggingface dataset:
extern crate proconio;
use proconio::input;

fn main() {
    input! {
        x: i32,
    }
    println!(
        "{}",
        if 400 <= x && x < 600 {
            8
        } else if x < 800 {
            7
        } else if x < 1000 {
            6
        } else if x < 1200 {
            5
        } else if x < 1400 {
            4
        } else if x < 1600 {
            3
        } else if x < 1800 {
            2
        } else if x < 2000 {
            1
        } else {
            unreachable!();
        }
    );
}


Measured memory_bytes: 2172
import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    FastScanner in;
    PrintWriter out;

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

    void solve() {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("A", 1);
        map.put("B", 2);
        map.put("C", 3);
        map.put("D", 4);
        map.put("E", 5);
        map.put("F", 6);
        int a = map.get(in.nextToken());
        int b = map.get(in.nextToken());
        if (a > b) {
            out.println(">");
        } else if (a < b) {
            out.println("<");
        } else {
            out.println("=");
        }

    }

    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public class FastScanner {
        BufferedReader br;
        StringTokenizer st;

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

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

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

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

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

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

}

Measured memory_bytes: 20052
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    long long r, d, x;
    cin >> r >> d >> x;
    for(int i = 1; i <= 10; ++i) {
        x = r * x - d;
        cout << x << '\n';
    }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl

using namespace std;

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

const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

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

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

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

int n, nodeD[200];
bool s[200][200] = {}, seenD[200] = {}, isBip = true;

void dfs(int now, int color) {
    seenD[now] = true;
    nodeD[now] = color;
    rep(i, n) {
        if (s[now][i] && !seenD[i])
            dfs(i, abs(color - 1));
        else if (s[now][i] && seenD[i] && nodeD[i] == color)
            isBip = false;
    }
}

int main() {
    int ans = 0;
    cin >> n;
    rep(i, n) {
        string tmp;
        cin >> tmp;
        rep(next, n) {
            if (tmp[next] == '1')
                s[i][next] = true;
        }
    }
    dfs(0, 0); //二部グラフ判定
    rep(i, n) {
        int dis[n], maxDis = 0;
        bool seen[n] = {};
        dis[i] = 0;
        queue<int> que;
        que.push(i);
        seen[i] = true;
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            rep(next, n) {
                if (s[now][next] && !seen[next]) {
                    que.push(next);
                    dis[next] = dis[now] + 1;
                    maxDis = max(maxDis, dis[next]);
                    seen[next] = true;
                }
            }
        }
        ans = max(ans, maxDis);
    }
    if (!isBip)
        cout << -1 << endl;
    else
        cout << ans + 1 << endl;
}

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

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h);
    vector<vector<int>> dist(h, vector<int>(w, -1));
    int ans = h * w;
    for (auto &s: grid) {
        cin >> s;
        ans -= count(s.begin(), s.end(), '#');
    }
    queue<pair<int, int>> q;
    vector<pair<int, int>> dir = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    q.emplace(0, 0);
    dist[0][0] = 1;
    while (!q.empty()) {
        auto v = q.front();q.pop();
        int px = v.first, py = v.second;
        for (auto d: dir) {
            int x = v.first + d.first, y = v.second + d.second;
            if (x < 0 || y < 0 || x >= h || y >= w) continue;
            if (dist[x][y] != -1) continue;
            if (grid[x][y] == '#') continue;
            dist[x][y] = dist[px][py] + 1;
            q.emplace(x, y);
        }
    }
    if (dist[h-1][w-1] == -1) {
        cout << -1 << endl;
        return 0;
    }
    ans -= dist[h-1][w-1];
    cout << ans << endl;
    return 0;
}

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

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int A = 0;
    int B = 0;
    int C = 0;
    int r = 0;
    if (a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
      r = 0;
    } else if (a == b && b == c && a == c) {
      r = -1;
    } else {
      while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
        A = b / 2 + c / 2;
        B = a / 2 + c / 2;
        C = b / 2 + a / 2;
        a = A;
        b = B;
        c = C;
        ++r;
      }
    }
    System.out.println(r);
    sc.close();
  }
}


Measured memory_bytes: 35676
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define REPP(i, n) for(int i = 1; i <= n; ++i)
#define REPR(i, n) for(int i = n-1; i >= 0; --i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;
const ll INF = 1000000000;

int main() {
    string s; cin >> s;
    int w; cin >> w;
    string ans = "";
    for (int i = 0; i < s.length(); i+=w){
        ans += s[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
using namespace std;

int main() {
    ll a,b,k,x,y,i;
    cin>>a>>b>>k;
    for(i=0;i<k;i++){
        if(i%2==0){
            if(a%2!=0){
                x=a;
                x=x-1;
                x=x/2;
                b=b+x;
                a=x;
                
            }
            else{
                x=a;
                x=x/2;
                b=b+x;
                a=x;
            }
        }
        else{
            if(b%2!=0){
                y=b;
                y=y-1;
                y=y/2;
                a=a+y;
                b=y;
                
            }
            else{
                y=b;
                y=y/2;
                a=a+y;
                b=y;
            }
        }
    }
    cout<<a<<" "<<b;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, l;
  cin >> n >> l;
  int sum = (l + l + n - 1) * n / 2;
  if(l>=0) cout << sum - l;
  else if(abs(l) < n) cout << sum;
  else cout << sum - (l + n - 1);
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	long long n;
	cin>>n;
	
	long long ans=100;
	for (int i=1;;++i){
		if (ans>=n){
			cout<<i-1<<endl;
			return 0;	
		}
		ans=ans*1.01;	
	}
}

Measured memory_bytes: 3636
using System;

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            var X = long.Parse(Console.ReadLine());
            long A, B;
            var isEnd = false;
            for (A = 1; A <= 500; A++)
            {
                for (B = -500; B <= 500; B++)
                {
                    if (A * A * A * A * A - B * B * B * B * B == X)
                    {
                        Console.WriteLine($"{A} {B}");
                        isEnd = true;
                        break;
                    }
                }
                if (isEnd) break;
            }
        }
    }
}


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

using namespace std;

#define INF (1<<29)

int main(){
    int N,M,s,g1,g2,a,b,c;
    while(cin >> N >> M >> s >> g1 >> g2, N){
	s--; g1--; g2--;
	vector<vector<int> > d(N,vector<int>(N,INF));
	for(int i = 0 ; i < N ; i++){
	    d[i][i] = 0;
	}
	for(int i = 0 ; i < M ; i++){
	    cin >> a >> b >> c; a--; b--;
	    d[a][b] = c;
	}
	for(int k = 0 ; k < N ; k++){
	    for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
		    d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
		}
	    }
	}
	int res = INF;
	for(int i = 0 ; i < N ; i++){
	    res = min(res,d[s][i]+d[i][g1]+d[i][g2]);
	}
	cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1260
#include <stdio.h>
#include <algorithm>
using namespace std;
int K, N, A[2 * 100 * 1000 + 1];
int main(void)
{
	scanf("%d%d", &K, &N);
	for (int i = 0; i < N; i++) scanf("%d", A + i);
	int min_dist = 1e9;  // check!
	for (int s = 0; s < N; s++) {  // from every starting point
		int dist1,dist2;
		//clockwise
		int s1 = s - 1 >= 0 ? s - 1 : s + N - 1;
		if (A[s] > A[s1]) dist1 = K - (A[s] - A[s1]);
		else dist1 = A[s1] - A[s];
		//anti clockwise
		int s2 = s + 1 < N ? s + 1 : 0;
		if (A[s2] > A[s])  dist2 = K - (A[s2] - A[s]);
		else dist2 = A[s] - A[s2];

		int dist = min(dist1, dist2);
		min_dist = min(min_dist, dist);
	}
	printf("%d\n", min_dist);
	return 0;
}


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

#define MAX 500000
#define SNTNL 2000000000

int l[MAX/2+2], r[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int middle, int right){
  int n1=middle-left;
  int n2=right-middle;

  for(int i=0; i<n1; i++)
    l[i]=A[left+i];
  for(int i=0; i<n2; i++)
    r[i]=A[middle+i];

  l[n1]=r[n2]=SNTNL;

  int i=0, j=0;

  for(int k=left; k<right; k++){
    cnt++;
    if(l[i] <= r[j])
    {
      A[k]=l[i++];
    }
    else
    {
      A[k]=r[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right){
  if(left+1 < right)
  {
    int middle=(left+right)/2;

    mergeSort(A, n, left, middle);
    mergeSort(A, n, middle, right);
    merge(A, n, left, middle, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt=0;

  cin >> n;
  for(i=0; i<n; i++)
    cin >> A[i];

  mergeSort(A, n, 0, n);

  for(i=0; i<n; i++){
    if(i)
      cout << " ";
    cout << A[i];
  }

  cout << endl;

  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 6880
/**
 * @brief  : c++ code for AtCoder
 * @author : rk222
 * @created: 2019.06.02 20:56:01
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

#define disp(x) cout << #x << ": " << x << endl
#define disp_vec(v)                                                                           \
    cout << #v << ":";                                                                        \
    rep(i, v.size()) cout << " " << v[i];                                                     \
    cout << endl

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/* ------------------------------------- */

int main() {
    int n, a, b, c, d;
    string s;
    cin >> n >> a >> b >> c >> d;
    cin >> s;
    a--;
    b--;
    c--;
    d--;

    bool ret = true;

    if (c < d) {
        int ms = 0;
        int cnts = 0;
        for (int i = a; i < c; i++) {
            if (s[i] == '#') {
                cnts++;
                ms = max(cnts, ms);
            } else {
                cnts = 0;
            }
        }
        cnts = 0;
        for (int i = b; i < d; i++) {
            if (s[i] == '#') {
                cnts++;
                ms = max(cnts, ms);
            } else {
                cnts = 0;
            }
        }
        if (ms > 1) {
            ret = false;
        } else {
            ret = true;
        }
    } else {
        int ms = 0;
        int cnts = 0;
        for (int i = a; i < c; i++) {
            if (s[i] == '#') {
                cnts++;
                ms = max(cnts, ms);
            } else {
                cnts = 0;
            }
        }
        int md = 0;
        int cntd = 0;
        for (int i = b - 1; i <= d + 1; i++) {
            if (s[i] == '.') {
                cntd++;
                md = max(cntd, md);
            } else {
                cntd = 0;
            }
        }
        if (ms <= 1 && md >= 3) {
            ret = true;
        } else {
            ret = false;
        }
    }

    if (ret) {
        cout << "Yes" << '\n';
    } else {
        cout << "No" << '\n';
    }
    /* --------------------------------- */
    return 0;
}

Measured memory_bytes: 640
from scipy.sparse.csgraph import csgraph_from_dense
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N,M,L=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*M
for i in range(M):
    A[i],B[i],C[i] = map(int,input().split())
    A[i] -=1
    B[i] -=1
Q=int(input())
ST=[list(map(int,input().split())) for _ in range(Q)]


G = csr_matrix((C, (A, B)), shape=(N, N))
d = floyd_warshall(G, directed=False)
G=np.full((N,N), np.inf)
G[d<=L]=1
G = csr_matrix(G)
E = floyd_warshall(G, directed=False)

for s,t in ST:
    if E[s-1][t-1]==float('inf'):
        print(-1)
    else:
        print(int(E[s-1][t-1]-1))

Measured memory_bytes: 38640
import sys

sys.setrecursionlimit(10 ** 7)
r1 = sys.stdin.readline


def solve():
    n = int(r1())
    ans = 0
    for i in range(1, n + 1):
        if i % 3 == 0 or i % 5 == 0:
            continue
        else:
            ans += i

    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 9064
#include<stdio.h>
int main(void) {
	char ci[4];
	char cj[4];

	scanf("%s", ci);
	scanf("%s", cj);

	int i;
	int count = 2;
	for (i = 0; i < 3; i++) {
		if (ci[i] == cj[count]) {
			if (i == 2) {
				printf("YES\n");
			}
		}
		else {
			printf("NO\n");
			break;
		}
		count--;
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int num[maxn];

int main(int argc, char const *argv[])
{
	int n;
	while(~scanf("%d",&n)){
		int temp,two=0,four=0;
		for(int i=0;i<n;i++){
			scanf("%d",&temp);
			if(temp%4==0){
				four++;
			}
			else if(temp%4!=0&&temp%2==0){
				two++;
			}
		}
		int flag=0;
		if(2*four+two>=n||(2*four+1==n)){
			flag=1;
		}
		if(flag){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int mo = 998244353;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

const int nm = 1 << 14;

	int r[nm]; ll w[nm];
	void build() {
		for(int i = 1; i < nm; i *= 2) {
			w[i] = 1; ll v = ksm(3, (mo - 1) / 2 / i);
			ff(j, 1, i) w[i + j] = w[i + j - 1] * v % mo;
		}
	}
	void dft(ll *a, int n, int f) {
		ff(i, 0, n) {
			r[i] = r[i / 2] / 2 + (i & 1) * (n / 2);
			if(i < r[i]) swap(a[i], a[r[i]]);
		} ll v;
		for(int i = 1; i < n; i *= 2) for(int j = 0; j < n; j += 2 * i) ff(k, 0, i)
			v = a[i + j + k] * w[i + k], a[i + j + k] = (a[j + k] - v) % mo, a[j + k] = (a[j + k] + v) % mo;
		if(f == -1) {
			reverse(a + 1, a + n);
			v = ksm(n, mo - 2);
			ff(i, 0, n) a[i] = (a[i] + mo) * v % mo;
		}
	}

ll a[nm], b[nm];

const int N = 8005;

ll fac[N], nf[N];

void build(int n) {
	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;
	nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;
}

ll C(int n, int m) {
	if(n < m) return 0;
	return fac[n] * nf[m] % mo * nf[n - m] % mo;
}

int n, m, tt;
ll f[N][205];

int main() {
	build(8002);
	build();
	
	scanf("%d %d", &n, &m);
	
	while(1 << ++ tt <= 2 * n);
	
	fo(i, 1, n) b[i] = nf[i + 2];
	dft(b, 1 << tt, 1);
	
	f[0][0] = 1;
	
	fo(j, 1, m) {
		fo(i, 0, n) {
			f[i][j] = f[i][j - 1] * (C(i, 2) + i + 1) % mo;
//			fo(k, 1, i) f[i][j] = (f[i][j] + f[i - k][j - 1] * C(i + 2, k + 2)) % mo;
		}
		ff(i, 0, 1 << tt) a[i] = 0;
		fo(i, 0, n) a[i] = f[i][j - 1] * nf[i] % mo;
		dft(a, 1 << tt, 1); 
		ff(i, 0, 1 << tt) a[i] = a[i] * b[i] % mo;
		dft(a, 1 << tt, -1);
		fo(i, 0, n) f[i][j] = (f[i][j] + a[i] * fac[i + 2]) % mo;
	}
	
	ll ans = 0;
	fo(i, 0, n) ans = (ans + f[i][m] * C(n, i)) % mo;
	pp("%lld\n", ans);
}

Measured memory_bytes: 13696
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

int main() {
    long long n;
    cin >> n;
    vector<long long> a(n);
    rep(i, n) {
        cin >> a.at(i);
    }

    // i + Ai = j - Aj となればよい
    // L = i + Ai, R = j - Aj とおいて{値:個数}のmapで管理

    long long count = 0;
    map<long long, long long> L, R;

    for (long long i = 1; i < n + 1; i++) {
        // それまでのiを見て今回のiとL=Rになっているものがあるかを見る(無いなら0が足される)
        // Lの値と一致するものがあるかRの値を見てRの個数分を足し、その逆も行う
        count += R[i + a.at(i - 1)];
        count += L[i - a.at(i - 1)];

        // 個数を1増やす
        L[i + a.at(i - 1)]++;
        R[i - a.at(i - 1)]++;
    }

    cout << count << endl;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    map<int, int> cnt;
    rep(i,n){
        int a;
        cin >> a;
        cnt[a]++;
    }
    int ans = n;
    int rest = 0;
    for(auto p : cnt){
        int c = p.second;
        while(c > 1){
            if(c >= 3){
                c -= 2;
                ans -= 2;
            }
            else{
                if(rest > 0){
                    rest = 0;
                    c--;
                    ans -= 2;
                }
                else{
                    rest++;
                    c--;
                }
            }
        }
    }
    if(rest > 0) ans -= 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] a = new int[K];
        for(int i = 0; i < N; i++){
            a[i % K] += 1;
        }
        int bun = a[0] - a[K -1];
        System.out.println(bun);
    }
}


Measured memory_bytes: 21972
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
    // Here your code !
    int n;cin>>n;
    int min=1;
    int max=1;
    vector<int>v(n);
    for(int i=0;i<n;i++){cin>>v[i];}
    sort(v.begin(),v.end());
    vector<bool> flag(8,false);
    for(int i=0;i<n;i++){
        if(v[i] >= 3200){
            max++;
        }else{
            for(int j=0;j<8;j++){
            if(!flag[j] && 400*(j) <= v[i] && v[i] < 400*(j+1)){
                    flag[j] = true;
                    min++;max++;
                }
            }
                
        }
    }
    min = (min ==1)?1:min-1;
    max = (max == 1)?1:max-1;
    cout<<min <<" "<<max<<endl;
    return 0;
}


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

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007
#define INF (1 << 30)
#define REP(i, m, n) for(int i = (int)m; i < (int)n; ++i)
#define rep(i, n) REP(i, 0, n)


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

    ll d, g; cin >> d >> g;
    vector<ll> p(d), c(d);
    rep(i, d) cin >> p[i] >> c[i];

    ll ans = INF;
    rep(bit, (1 << d)) {
        ll sum = 0, cnt = 0;
        rep(i, d) {
            if(bit&(1 << i)) {
                sum += (i+1)*100*p[i] + c[i];
                cnt += p[i];
            }
        }
        if(sum >= g) ans = min(ans, cnt);
        else {
            for(int i = d-1; i >= 0; i--) {
                if(bit&(1 << i)) continue;
                rep(j, p[i]) {
                    if(sum >= g) break;
                    sum += (i+1)*100;
                    cnt++;
                }
                if(sum >= g) break;
            }
            ans = min(ans, cnt);
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

int N;
double dp[301][301][301]; //! [1 sushi][2 sushis][3 sushis] => expected number of moves to clear all deishes

double solve(int c1, int c2, int c3) 
{
    double ret = dp[c1][c2][c3];
    if (ret == 0 && (c1 || c2 || c3)) {
        ret = N;
        if (c1) ret += c1 * solve(c1-1, c2, c3);
        if (c2) ret += c2 * solve(c1+1, c2-1, c3);
        if (c3) ret += c3 * solve(c1, c2+1, c3-1);
        ret /= (c1+c2+c3);
        dp[c1][c2][c3] = ret;
    }
    return ret;
}

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

    cin >> N;

    int c[4];
    c[1] = c[2] = c[3] = 0;
    rep(i, N) {
        int a;
        cin >> a;
        ++c[a];
    }

    cout << setprecision(10) << solve(c[1], c[2], c[3]) << endl;

    return 0;
}


Measured memory_bytes: 213248
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

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


int main(){
    
    int h,w;
    cin >> h >> w;
    string s[h] = {};
    
    rep(i,0,h)cin >> s[i];
   
    
    rep(i,0,h){
	rep(j,0,w){
	    if(s[i][j] == '#')cout << s[i][j];
	    else{
		int c = 0;
		rep(k,0,8){
		    int ii = i+dy8[k], jj = j + dx8[k];
		    if(0 <= ii && ii < h && 0 <= jj && jj <  w){
			if(s[ii][jj] == '#')c++;
		    }
		}
		cout << (char)('0'+c);
	    }
	}cout << endl;
    }
    
    return  0;
}


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

int n,q,com,x,y,k;
int P[10010];
void init(int N) {
	for(int i=0; i<N; ++i) P[i] = i;
}
int root(int a){
	if(P[a] == a) return a;
	return (P[a] = root(P[a]));
}

bool same(int a, int b) {
	return root(a) == root(b);
}
void unite(int a, int b) {
	P[root(a)] = root(b);
}

int main() {
	cin >> n >> q;
	init(n);
	for(int i=0; i<q; ++i) {
		cin >>com >> x >> y;
		if(com == 0) {
			unite(x,y);
			/*for(int i=0; i<n-1; ++i) {
				cout << P[i] << " ";
			}
			cout << P[n-1] << endl; */
		} else {
			k = same(x,y);
			cout << k << endl;
		}
	}
}

Measured memory_bytes: 1320
#include <algorithm>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define eps LDBL_EPSILON
#define moder 1000000007
#define int long long
#define ll long long
#define double long double
#define INF LLONG_MAX
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, k, x, y;
int r[4][1010][1010];
char c;
signed main() {
	cin >> n >> k;
	rep(i, n) {
		cin >> x >> y >> c;
		if (c == 'B') {
			if ((x / k + y / k) % 2) {
				x %= k;
				y %= k;
				r[1][x][y]++;
			}
			else {
				x %= k;
				y %= k;
				r[0][x][y]++;
			}
		}
		else {
			if ((x / k + y / k) % 2) {
				x %= k;
				y %= k;
				r[3][x][y]++;
			}
			else {
				x %= k;
				y %= k;
				r[2][x][y]++;
			}
		}
	}
	rep(i, 4) {
		REP(j, k - 1) {
			rep(l, k)r[i][j][l] += r[i][j - 1][l];
		}
		rep(j, k) {
			REP(l, k - 1)r[i][j][l] += r[i][j][l - 1];
		}
	}
	int ans = 0;
	rep(i, k) {
		rep(j, k) {
			int cnt = 0;
			cnt += r[0][i][j];
			cnt += r[0][k - 1][k - 1] - r[0][i][k - 1] - r[0][k - 1][j] + r[0][i][j];
			cnt += r[2][i][k - 1] - r[2][i][j] + r[2][k - 1][j] - r[2][i][j];
			cnt += r[3][i][j];
			cnt += r[3][k - 1][k - 1] - r[3][i][k - 1] - r[3][k - 1][j] + r[3][i][j];
			cnt += r[1][i][k - 1] - r[1][i][j] + r[1][k - 1][j] - r[1][i][j];
			ans = max(ans, cnt);
			cnt = 0;
			cnt += r[1][i][j];
			cnt += r[1][k - 1][k - 1] - r[1][i][k - 1] - r[1][k - 1][j] + r[1][i][j];
			cnt += r[3][i][k - 1] - r[3][i][j] + r[3][k - 1][j] - r[3][i][j];
			cnt += r[2][i][j];
			cnt += r[2][k - 1][k - 1] - r[2][i][k - 1] - r[2][k - 1][j] + r[2][i][j];
			cnt += r[0][i][k - 1] - r[0][i][j] + r[0][k - 1][j] - r[0][i][j];
			ans = max(ans, cnt);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
int n;
cin >>n;
int a=0;
int b =n;
while(b>0){
 a+=b%10;
 b/=10;
}
if(n%a==0){
    cout <<"Yes"<<endl;
}
else{
    cout <<"No"<<endl;
}
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <numeric>

using namespace std;
typedef long long ll;

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

    multiset<ll> neg, nneg;
    for(int i = 0; i < n; ++i){
        ll a;
        cin >> a;
        if(a >= 0){
            nneg.insert(a);
        }else{
            neg.insert(a);
        }
    }

    ll ans = accumulate(nneg.begin(), nneg.end(), 0LL);
    for(auto a : neg){ ans -= a; }

    if(neg.size() % 2 == 1){
        ll tmpneg = *neg.rbegin();
        if(nneg.size()){
            ll tmpnneg = *nneg.begin();
            if(-tmpneg > tmpnneg){
                ans -= 2 * tmpnneg;
            }else{
                ans += 2 * tmpneg;
            }
        }else{
            ans += 2 * tmpneg;
        }
    }

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


Measured memory_bytes: 4992
n, m = map(int, input().split())
H = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(m)]

ans = [0] * n
for a, b in AB:
    if H[a-1] < H[b-1]:
        ans[a - 1] += 1
    elif H[a-1] > H[b-1]:
        ans[b - 1] += 1
    else:
        ans[a - 1] += 1
        ans[b - 1] += 1


print(ans.count(0))


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

int main() {
  vector<int> P(3);
  rep(i, 3) cin >> P[i];
  sort(P.begin(), P.end());
  cout << P[0] + P[1] << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

int main()
{
    int l, r, d;
    cin >> l >> r >> d;
    int count = 0;
    for (int i = l; i <= r; i++)
    {
        if (i % d == 0)
            count++;
    }
    dunk(count);
    return 0;
}

Measured memory_bytes: 3592
n = gets.to_i
n.times do
  x = gets.to_i
  count = 0
  while x > 9
    x   = x.to_s
    max = 0
    for i in 0 .. x.size - 2
      max = [max, (x[0 .. i].to_i) * (x[i + 1 .. x.size - 1].to_i)].max
    end
    if max >= x.to_i
      puts -1
      break
    end
    count += 1
    x = max
  end
  if x < 10
    puts count
  end
end



Measured memory_bytes: 6876
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main(void) {

	int a, b, c;
	int x = 0;
	int count = 0;

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

	for (x = a; x <= b; x++) {
		if (c%x == 0) {
			count++;
		}
	}
	printf("%d\n", count);

	return(0);

}


Measured memory_bytes: 2104
#include<bits/stdc++.h>
#define ll long long
#define rg register
using namespace std;
const int Mod=1e9+7;
const int MAXN=1e5+10;
int n,Ans=1,A[MAXN],Deg[MAXN],Vis[MAXN],Inc[MAXN],Fl[MAXN];
int Cs[MAXN],Dp[MAXN];
inline int Read()
{   rg int a=0,c=1;   rg char b=getchar();
	while(b!='-'&&(b<'0'||b>'9'))b=getchar();
	if(b=='-')c=-1,b=getchar();
	while(b>='0'&&b<='9')a=a*10+b-48,b=getchar();
	return a*c;
}
inline void Calc(rg int Np)
{   rg int Fd=-1,Ld=0,Nd=0,Lf=0;
	for(;Inc[Np];Inc[Np]=0,Np=A[Np],Nd++)
		if(Fl[Np]) Fd!=-1?Ans=1ll*Ans*((Fl[Np]<Nd-Ld)+(Fl[Np]<=Nd-Ld))%Mod:(Fd=Nd,Lf=Fl[Np]),Ld=Nd;
	Fd!=-1?Ans=1ll*Ans*((Lf<Fd+Nd-Ld)+(Lf<=Fd+Nd-Ld))%Mod:Cs[Nd]++;
}
int main()
{   n=Read();
	for(rg int i=1;i<=n;i++) A[i]=Read(),Deg[A[i]]++;
	for(rg int i=1,Pos;i<=n;i++)
	{   if(Vis[i]) continue ;
		for(Pos=i;!Vis[Pos];Pos=A[Pos]) Vis[Pos]=i;
		if(Vis[Pos]==i) while(!Inc[Pos]) Inc[Pos]=1,Pos=A[Pos];
	}
	for(rg int i=1;i<=n;i++) if(Deg[i]-Inc[i]>1) return puts("0"),0;
	for(rg int i=1,Pos,Nl;i<=n;i++)
	{	for(Pos=i,Nl=0;!Inc[Pos]&&!Deg[i];Pos=A[Pos]) Nl++;
		if(!Deg[i]) Fl[Pos]=Nl;
	}
	for(rg int i=1;i<=n;i++) if(Inc[i]) Calc(i);
	for(rg int i=1;i<=n;i++)
	{	if(!Cs[i]) continue ;   Dp[0]=1;
		for(rg int j=1;j<=Cs[i];j++)
		{   Dp[j]=(i>1&&i&1?2:1)*Dp[j-1]%Mod;
			if(j>=2) Dp[j]=(Dp[j]+1ll*Dp[j-2]*(j-1)%Mod*i)%Mod;
		}
		Ans=1ll*Ans*Dp[Cs[i]]%Mod;
	}
	printf("%d\n",Ans);
}


Measured memory_bytes: 2176
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    S=sorted(input())
    if S[0]==S[1] and S[1]!=S[2] and S[2]==S[3]:
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    do()

Measured memory_bytes: 3064
#include <stdio.h>
#define N 500000
void  maxHeapify(int*,int,int);
void  buildMaxHeap(int*,int);

int main(){
  int a,A[N],i;

  scanf("%d",&a);
  for(i=1;i<=a;i++)
    scanf("%d",&A[i]);
  buildMaxHeap(A,a);
  for(i=1;i<=a;i++)
    printf(" %d",A[i]);
  printf("\n");
  return 0;
}


void maxHeapify(int* A,int i,int H){
  int l,r,largest,k;

  
  l = i*2;    //左の子ノードleft(i)
  r = i*2+1;  //右の子ノードright(i)
  
  // 左の子、自分、右の子で値が最大のノードを選ぶ
  if(l <= H && A[l] > A[i])
    largest = l;
  else 
    largest = i;
  if(r <= H && A[r] > A[largest])
    largest = r;

  if(largest != i){//i の子の方が値が大きい場合
    k=A[i];
    A[i]=A[largest];
    A[largest]=k;
    maxHeapify(A,largest,H); // 再帰的に呼び出し
  }
}

void buildMaxHeap(int* A,int H){
  int i;
  
  for(i=H/2;i>=1;i--)
    maxHeapify(A,i,H);
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>	
#define pb push_back
typedef long long ll;
const int inf = 2e9;
using namespace std;
ll MOD = 1000000007;
typedef pair<int,int> ii;
typedef struct {int a,b;ll c;}aaa;

int a,b,n,k,m,ans=0,res,minimo; 
int grados[10];
int main(){


    for (int i = 0; i < 3; ++i)
    {
        scanf("%d%d",&a,&b);
        grados[a]++;
        grados[b]++;
    }

    

    for(int i=1; i<=4; i++){
        //cout<<grados[i]<<endl;
        if(grados[i]==3) return !printf("NO\n");
    }

    return !printf("YES\n");
}

Measured memory_bytes: 256
x,n=map(int,input().split())
if n!=0:
  p=list(map(int,input().split()))
else:
  p=[]
ans=0
if x in p:
  low=x
  high=x
  while True:
    low-=1
    high+=1
    if low in p:
      if high in p:
        continue
      else:
        ans=high
        break
    else:
      ans=low
      break
  print(ans)
else:
  print(x)

Measured memory_bytes: 9204
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int n = Integer.parseInt(line);

		int Tpt = 0;
		int Hpt = 0;
		for (int i = 0; i < n; i++) {
			String string = sc.nextLine();
			String[] str = string.split(" ");
			String T = str[0];
			String H = str[1];
			if (T.compareTo(H) == 0) {
				Tpt += 1;
				Hpt += 1;

			} else if (T.compareTo(H) > 0) {
				Tpt += 3;

			} else {
				Hpt += 3;

			}

		}
		System.out.println(Tpt + " " + Hpt);
	}

}

Measured memory_bytes: 31420
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static int INF = (int)(1e9);

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

  vector<int> v(100005, INF);
  rep(i,M){
    int a, b;
    cin >> a >> b;
    v[a] = min(v[a], b);
  }
  
  int ret = 0;
  int last = N+1;
  rep(i,v.size()){
    if(v[i] == INF) continue;
    if(last <= i){
      //cout << "\t" << i << " " << v[i] << endl;
      ret++;
      last = v[i];
    }else{
      last = min(last, v[i]);
    }
  }
  ret++;

  cout << ret << endl;
  
  return 0;
}


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

int cnt[100001], isa[100001], isc[100001];
int main(void) {
  int N, Q;
  string s;
  cin >> N >> Q;
  cin >> s;

  for (int i = 0; i < s.size() - 1; i++) {
    if (s[i] == 'A' && s[i + 1] == 'C') {
      cnt[i] = 1;
      isa[i] = 1;
      isc[i + 1] = 1;
    }
  }
  for (int i = 0; i < s.size() - 1; i++) {
    cnt[i + 1] += cnt[i];
  }

  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    l--;r--;
    int ret = cnt[r] - cnt[l] - isa[r];
    // cerr << cnt[r] << " " << cnt[l] << " " << isa[r] << endl;
    if (isa[l]) ret++;
    cout << ret << endl;
  }

  return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using P = pair<int, int>;

int a, b, n;

int calc(int x){
    return (int) (floor(a * x / b) - a * floor(x / b));
}

signed main() {

    cin >> a >> b >> n;

    cout << calc(min(b-1, n)) << endl;

    return 0;
}


Measured memory_bytes: 3596
// AOJ 0507: Square
// 2017.8.30 bal4u@uu
// 2017.11.29

#include <stdio.h>

int a[31], n;

void rec(int k, int n, int m)
{
	int i;

	if (n <= 0) {
		printf("%d", a[0]);
		for (i = 1; i < k; i++) printf(" %d", a[i]);
		putchar('\n');
		return;
	}
	if (n < m) m = n;
	for (i = m; i >= 1; i--) {
		a[k] = i;
		rec(k+1, n-i, i);
	}
}

int main()
{
	while (scanf("%d", &n) && n > 0) rec(0, n, n);
	return 0;
}

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

#define int long long
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

signed main(){
  int n;cin>>n;
  if(n==0){
    int a;cin>>a;if(a==1)fin(1);fin(-1);
  }
  int a;cin>>a;if(a)fin(-1);
  vector<int> v(n);
  for(int i=0;i<n;i++)cin>>v[i];
  vector<int> w(n+1,0);
  for(int i=0;i<n;i++)w[i+1]=w[i]+v[n-1-i];
  int now=1,ans=1;
  for(int i=0;i<n;i++){
    if(now*2<v[i])fin(-1);
    int A=w[n-i-1];
    int B=min(now*2,v[i]+A);
    ans+=B;
    now=B-v[i];
  }
  fin(ans);
}


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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int Q; scanf("%d", &Q);
  while (Q-- > 0) {
    ll A, B; scanf("%lld %lld", &A, &B);
    if (A > B) { swap(A, B); }
    ll ans = 2 * (A - 1);
    ll low = 0, high = 1e10, mid = -1;
    while (high - low > 1) {
      mid = (high + low) / 2;
      bool ok = true;
      if (A + mid > B) { ok = false; }
      for (ll m = mid / 2 - 2; ok and m <= mid / 2 + 2; ++m) {
        if (m <= 0 or (A + mid - m) >= B) { continue; }
        if ((A + m) * (A + mid - m) >= A * B) {
          ok = false;
          break;
        }
      }
      if (ok) { low = mid; }
      else { high = mid; }
    }
    ans += low;
    printf("%lld\n", ans);
  }
  return 0;
}


Measured memory_bytes: 256
def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

        
N = int(input())
C = input().split()

bubbleC = list(C)
selectionC = list(C)

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))

Measured memory_bytes: 6760
#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
const int MAXN = 2e5+2;
const int MOD = 1e9+7;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second 
#define debug(x)  do{cerr<<#x<<": "<<x<<"\n";}while(0)
#define debugv(x) do{cerr<<#x<<": ";for(auto&e: (x))cerr<<e<<" ";cerr<<"\n";}while(0)
#define FAIL0 {cout << "0\n"; return 0;}
#define FAIL1 {cout << "-1\n"; return 0;}
#define FAILNO {cout << "No\n"; return 0;}
#define YES {cout << "Yes\n"; return 0;}

int N,K;
int A[501];
int R[501];
int ans;

int main() {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> A[i];
    int s = 0;
    for (int i = 0; i < N; i++) s += A[i];
    vector<int> factors;
    for (int i = 1; i*i <= s; i++) {
        if (s%i == 0) {
            factors.pb(i);
            if (i*i < s) factors.pb(s/i);
        }
    }

    for (int x: factors) {
        for (int i = 0; i < N; i++) {
            R[i] = A[i]%x;
        }
        sort(R,R+N);

        int i;
        for (i = 0; i < N && !R[i]; i++);
        if (i == N) ans = max(ans, x);
        else {
            int j = N-1;
            int c = 0;
            int remain = K;
            while (i < j && remain) {
                int mn = min(R[i], x-R[j]);
                mn = min(mn, remain);
                remain -= mn;
                R[i] -= mn;
                if (R[i] == 0) i++;
                R[j] = (R[j]+mn) % x;
                if (R[j] == 0) j--;
            }

            if (i > j) ans = max(ans, x);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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



int main(void) {
	string s;
	int a[26] = {};
	bool flag = true;

	cin >> s;

	FOR(i, 0, s.size() - 1) {
		a[s[i] - 'a']++;
		if (a[s[i] - 'a'] > 1) {
			flag = false;
		}
	}

	if (flag) {
		cout << "yes" << endl;
	}
	else {
		cout << "no" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

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

int main(void)
{
	int a, b;
	
	while (scanf("%d %d", &a, &b) != EOF){
		printf("%d\n", gcd(a, b));
	}
	
	return (0);
}

Measured memory_bytes: 596
n,x,m=map(int,input().split())

am=[]

d={}

ch=0

for i in range(m):
  y=x%m
  
  if y==0:
    ch+=1
    break
  if y not in d:
    d[y]=0
    
    am.append(y)
    
    x=y*y
    
  else:
    stop=y
    break
    
if ch>0:
  st=0
  ans=0
  while st<=n-1 and st<=len(am)-1:
    ans+=am[st]
    st+=1
    
  print(ans)

else:
  for i in range(len(am)):
    if am[i]==y:
      now=i
      
  new_am=am[now:]
  s_new=sum(new_am)
  l=len(new_am)
  if n<i:
    print(sum(am[:n]))
    
  else:
    s=sum(am[:now])
    rest=n-now
    x=rest//l
    y=rest%l
    print(s+x*s_new+sum(new_am[:y]))
    
  

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

typedef long long ll;

const long long MOD = 998244353;


void solve(long long N, long long K, std::vector<long long> L, std::vector<long long> R){
  vector<ll> dp(N);
  vector<ll> dps(N+1);
  dp[0] = 1;
  dps[0] = 0;
  dps[1] = 1;

  for (ll i = 1; i < N; ++i) {
    ll t = 0;
    for (ll j = 0; j < K; ++j) {
      ll l = max(i - R[j], 0ll);
      ll r = max(i - L[j]+1, 0ll);
      t = (t + dps[r]) % MOD;
      t = (t - dps[l] + MOD) % MOD;
    }
    dp[i] = t;
    dps[i+1] = (dps[i] + dp[i]) % MOD;
  }
  cout << dp[N-1] << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long N;
  std::cin >> N;
  long long K;
  std::cin >> K;
  std::vector<long long> L(K);
  std::vector<long long> R(K);
  for(int i = 0 ; i < K ; i++){
    std::cin >> L[i];
    std::cin >> R[i];
  }
  solve(N, K, std::move(L), std::move(R));
  return 0;
}


Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

int a,b,c;
cin >> a >> b >> c;
if(b-a==c-b)cout << "YES" << endl;
else cout << "NO" << endl;





return 0;

}



Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			String line = null;
			while ((line = br.readLine()) != null) {
				int n = Integer.parseInt(line);
				System.out.println(fact(n));
			}
		}
	}

	public static long fact(long n) {
		if (n <= 1) {
			return n;
		}
		return n * fact(n - 1);
	}
}

Measured memory_bytes: 24276