akhauriyash/Code-Regression huggingface dataset:
//
//AtCoder Beginner Contest 131
//C - Anti-Division
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;

const double PI = 3.14159265358979323846;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int main()
{
    ll a, b, c, d;

    cin >> a >> b >> c >> d;

    ll lcmv = lcm(c, d);
    ll ans = (b-a+1) - ((b/c)-((a-1)/c)) - ((b/d)-((a-1)/d)) + ((b/lcmv)-((a-1)/lcmv));

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


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i, j;
	int data[2][4];
	int blow, hit;
	
	while (1){
		blow = hit = 0;
		
		for (i = 0; i < 2; i++){
			for (j = 0; j < 4; j++){
				if (scanf("%d", &data[i][j]) == EOF){
					return (0);
				}
			}
		}
		
		for (i = 0; i < 4; i++){
			if (data[0][i] == data[1][i]){
				hit++;
			}
			
			for (j = 0; j < 4; j++){
				if (i != j && data[0][i] == data[1][j]){
					blow++;
					break;
				}
			}
		}
		
		printf("%d %d\n", hit, blow);
	}
	
	return (0);
}

Measured memory_bytes: 596
require 'set'; require 'prime'
INF=Float::INFINITY
n = gets.chomp.to_i
a, b = gets.chomp.split.map(&:to_i)
probs = gets.chomp.split.map(&:to_i).sort

count1 = probs.select{|prob| prob <= a}.count
count2 = probs.select{|prob| a < prob && prob <= b}.count
count3 = probs.select{|prob| b < prob}.count

puts [count1, count2, count3].min

Measured memory_bytes: 2300
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define dprint(Exp,...) if(Exp){fprintf(stderr, __VA_ARGS__);}
#define printe(...) fprintf(stderr, __VA_ARGS__);
#define PrtExp(_Exp)  cerr<< #_Exp <<" = "<< (_Exp)
#define PrtExpN(_Exp)  cerr<< #_Exp <<" = "<< (_Exp) <<"\n"

#define SINT(n) scanf("%d",&n)
#define SINT2(n,m) scanf("%d %d",&n,&m)
#define SINT3(n,m,o) scanf("%d %d %d",&n,&m,&o)
#define SINT4(n,m,o,p) scanf("%d %d %d %d",&n,&m,&o,&p)
#define SINT5(n,m,o,p,q) scanf("%d %d %d %d %d",&n,&m,&o,&p,&q)
#define SLL(n) scanf("%lld",&n)
#define SLL2(n,m) scanf("%lld %lld",&n,&m)
#define SLL3(n,m,o) scanf("%lld %lld %lld",&n,&m,&o)
#define SST(s) scanf("%s",s)
#define SCH(c) scanf("%c",&c)

#define GC() getchar()

#define PINT(n) printf("%d",(int)(n))
#define PINT2(n,m) printf("%d %d",(int)(n),(int)(m))
#define PINT3(n,m,l) printf("%d %d %d",(int)(n),(int)(m),(int)(l))
#define PLL(n) printf("%lld",(long long)(n))
#define PST(s) printf("%s",(s))
#define PCH(s) printf("%c",(s))

#define PINTN(n) printf("%d\n",(int)(n))
#define PINT2N(n,m) printf("%d %d\n",(int)(n),(int)(m))
#define PINT3N(n,m,l) printf("%d %d %d\n",(int)(n),(int)(m),(int)(l))
#define PLLN(n) printf("%lld\n",(long long)(n))
#define PSTN(s) printf("%s\n",(s))
#define PCHN(s) printf("%c\n",(s))

#define PSP() printf(" ")
#define PN() printf("\n")

#define PC(c) putchar(c)
#define CSP (' ')
#define SN ("\n")

#define rep(i,a) for(ll i=0;i<a;i++)
#define reP(i,a) for(int i=0;i<=a;i++)
#define Rep(i,a) for(int i=a-1;i>=0;i--)
#define ReP(i,a) for(int i=a;i>=0;i--)

#define rEp(i,a) for(i=0;i<a;i++)
#define rEP(i,a) for(i=0;i<=a;i++)
#define REp(i,a) for(i=a-1;i>=0;i--)
#define REP(i,a) for(i=a;i>=0;i--)

#define repft(i,a,b) for(int i=a;i<b;i++)
#define repfT(i,a,b) for(int i=a;i<=b;i++)
#define Repft(i,a,b) for(int i=a-1;i>=b;i--)
#define RepfT(i,a,b) for(int i=a;i>=b;i--)

#define foreach(a,it) for(auto it = a.begin(); it != a.end(); ++it)

#define FILL(a,v) fill(begin(a),end(a), v)
#define FILL0(a) memset(a,0,sizeof(a))
#define FILL1(a) memset(a,-1,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll>   Pll;


const int INF = 0x2aaaaaaa; // 715,827,882
const ll INFLL = 0x1f1f1f1f1f1f1f1fLL;//2,242,545,357,980,376,863

template <class A, class B> inline ostream& operator<<(ostream& st, const pair<A, B>& P) { return st << "(" << P.first << "," << P.second << ")"; };
template <class A, class B> inline pair<A, B> operator+(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first + Q.first, P.second + Q.second); };
template <class A, class B> inline pair<A, B> operator-(const pair<A, B>& P, const pair<A, B>& Q) { return pair<A, B>(P.first - Q.first, P.second - Q.second); };


#define fs first
#define sc second



int main() {
	int n,m;

	map<int, int>ds;

	cin >> n;

	rep(i, n) {
		int d;
		cin >> d;
		ds[d]++;
	}
	cin >> m;

	rep(i, m) {
		int t;
		cin >> t;

		if (ds[t] <= 0) {
			puts("NO");
			return 0;
		}
		ds[t]--;
	}
	cout << "YES" << endl;



	return 0;
}

Measured memory_bytes: 9728
from collections import deque, defaultdict

N, M = map(int, input().split())
ab = []
for _ in range(N + M - 1):
    ab.append(tuple(map(int, input().split())))

in_cnt = defaultdict(int)
rev = defaultdict(list)
outs = defaultdict(list)
for a, b in ab:
    in_cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    rev[b - 1].append(a - 1)

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while queue:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

order = [i for i, v in sorted(enumerate(res), key=lambda x: x[1])]

ans = [0] * N
ans[res[0]] = 0
for v in res[:0:-1]:
    ans[v] = max([(order[v2], v2) for v2 in rev[v]])[1] + 1

for a in ans:
    print(a)


Measured memory_bytes: 121432
# -*- coding: utf-8 -*-

def main():

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

    ans = 1

    if 0 not in A:
        for i in A:
            ans *= i
            if ans > 10 ** 18:
                ans = -1
                break

    else:
        ans = 0

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 21628
def main():
    WEEK = ['SUN', 'MON', 'TUE', 'WED', 'THU', 'FRI', 'SAT']
    w = input()
    d = 7
    for week in WEEK:
        if w == week:
            print(d)
            return
        d -= 1


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
def main():
    s=list(input())
    t=list(input())
    key=0
    index=0
    if len(s)<len(t):
        print("UNRESTORABLE")
        return
    key2=0
    for i in range(len(s)-len(t)+1):
        for j in range(len(t)):
            if s[i+j]!="?" and s[i+j]!=t[j]:
                key2=1
                break
        if key2==0:
            index=i
            key=1
        key2=0
    if key==0:
        print("UNRESTORABLE")
        return
    for i in range(len(t)):
        s[index+i]=t[i]
    for i in range(len(s)):
        if s[i]=="?":
            s[i]="a"
    print(''.join(s))
if __name__ == "__main__":
    main()

Measured memory_bytes: 38384
N, M, C = map(int, input().split())
B = [int(i) for i in input().split()]
ans = 0
for _ in range(N):
  A = [B[i] * int(j) for i,j in enumerate(input().split())]
  ans += 1 if sum(A) + C > 0 else 0
print(ans)

Measured memory_bytes: 3060
#include <stdio.h>
#include <math.h>
int isprime(int x){
  int i;
  if(x==2){
    return 1;
  } else if(x%2==0){
    return 0;
  }
  i=3;
  while(i<=sqrt(x)){
    if(x%i==0){
      return 0;
    }
    i+=2;
  }
  return 1;
}
int main(){
  int n,x,i;
  int count=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    if(isprime(x)){
      count++;
    }
  }
  printf("%d\n",count);
  return 0;
}

Measured memory_bytes: 2700
#include<bits/stdc++.h>
#define ll long long 
#define sum (1<<X+Y+Z)-1

using namespace std;

const ll mod=1e9+7;
ll n,X,Y,Z,goal,ans=1;
ll f[50][1<<18];

inline int read()
{
	int x=0,f=1;char st=getchar();
	while(st<'0'||st>'9'){if(st=='-') f=-1;st=getchar();}
	while(st>='0'&&st<='9') x=x*10+st-'0',st=getchar();
	return x*f;
}

int main()
{
	n=read();X=read();Y=read();Z=read();
	goal=1<<X+Y+Z-1;
    goal=goal|(1<<Y+Z-1);
    goal=goal|(1<<Z-1);
    
    f[0][0]=1;
    
    for(int i=1;i<=n;i++)
    {
    	ans*=10;
    	ans%=mod;
    	for(int j=0;j<=sum;j++)
    	{
    		if(f[i-1][j]==0) continue;
    		for(int k=1;k<=10;k++)
    		{
    			int now=(j<<k)|(1<<k-1);
    			now&=sum;
    			if((now&goal)!=goal)
    				f[i][now]=(f[i][now]+f[i-1][j])%mod;
    		}
    	}
    }
    
    for(int i=0;i<=sum;i++)
        ans=(ans-f[n][i]+mod)%mod;
    printf("%lld",ans);
    return 0;
} 

Measured memory_bytes: 82176
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
using ll = long long;
using uint = unsigned int;
using graph = std::vector<std::vector<ll>>;
using wGraph = std::vector<std::vector<std::pair<ll,ll>>>;
#define rep(i,n) for (int i=0; i < int(n); i++)

using namespace std;
ll MOD7 = 1000000007;
ll MOD9 = 1000000009;
vector<ll> InputVec(ll N){
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    return A;
}
void OutputVec(vector<ll> A){
    for (int i = 0; i < A.size(); ++i) {
        cout << A[i] << ",";
    }
    cout << endl;
}
vector<vector<ll>> InputVec2d(ll H,ll W){
    vector<vector<ll>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<ll>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        for (int xi = 0; xi < W; ++xi) {
            cin >> A[yi][xi];
        }
    }
    return A;
}
vector<vector<char>> InputVec2dStr(ll H,ll W){
    vector<vector<char>> A(H);
    for (int yi = 0; yi < H; ++yi) {
        A[yi] = vector<char>(W);
    }
    for (int yi = 0; yi < H; ++yi) {
        string S;
        cin >> S;
        for (int xi = 0; xi < W; ++xi) {
            A[yi][xi] = S[xi];
        }
    }
    return A;
}
void OutputVec2d(vector<vector<ll>> A){
    for (int yi = 0; yi < A.size(); ++yi) {
        for (int xi = 0; xi < A[yi].size(); ++xi) {
            cout << A[yi][xi] << ",";
        }
        cout << endl;
    }
}
graph InputGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    return G;
}
graph InputDGraph(ll N,ll M){
    graph G(N);
    for (int i = 0; i < M; ++i) {
        ll a,b;
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
    }
    return G;
}
void OutputGraph(graph G){
    for (int i = 0; i < G.size(); ++i) {
        cout << i << ":";
        for (int j = 0; j < G[i].size(); ++j) {
            cout << G[i][j]<< ",";
        }
        cout << endl;
    }
}
void OutputAnswerBool(bool b,bool isUpperCase = false){
    if(b){
        if(isUpperCase){
            cout << "YES" << endl;
        }else{
            cout << "Yes" << endl;
        }
    }else{
        if(isUpperCase){
            cout << "NO" << endl;
        }else{
            cout << "No" << endl;
        }
    }
}

int main() {
    ll N,K;
    cin >> N >> K;
    auto A = InputVec(N);
    ll res = 0;
    for (int i = 0; i < N; ++i) {
        ll count = 0;
        for (int j = i+1; j < N; ++j) {
            if(A[i] > A[j]){
                count+=K;
                count %= MOD7;
            }
        }
        for (int j = 0; j < N; ++j) {
            if(A[i]>A[j]){
                count += (K) * (K-1)/2;
                count %= MOD7;
            }
        }
        //cout << count << endl;
        res += count;
        res %= MOD7;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include<cstdio>

char s[200000];
int main(void) {
    int a = 0, b = 0;
    scanf("%s", s);

    for(char *p=s; *p; p++) {
        a += ((p-s) ^ *p)&1;
        b += 1^((p-s) ^ *p)&1;
    }

    int m = a < b ? a : b;
    printf("%d\n", m);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <map>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
using namespace std;

int main()
{
	int a;
	string s;
	cin >> a >> s;

	if (3200 <= a)
	{
		cout << s << endl;
	}
	else
	{
		cout << "red" << endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#define MN 101000

int main()
{
	int n; scanf("%d", &n);
	int m = 1; while(m * 2 <= n) m <<= 1;
	if(n == m) return 0 * puts("No");
	int k = n ^ m;
	if(n & 1) k = 0;
	int s = k / 4 * 4; 
	puts("Yes");
	if(!s)
	{
		puts("1 2"); puts("2 3"); printf("3 %d\n", n + 1); printf("%d %d\n", n + 1, n + 2); printf("%d %d\n", n + 2, n + 3);
	}
	else
	{
		for(int i = 0; i < 3; i++) 
		{
			printf("%d %d\n", s + i, s + i + 1);
			printf("%d %d\n", s + i + n, s + i + 1 + n);
		}
		printf("%d %d\n", s + 3, s + n);
	}
	for(int i = 0; i < s; i += 2) 
	{
		if(i)
		{
			printf("%d %d\n", i, i + 1);
			printf("%d %d\n", i + n, i + 1 + n);
		}
		printf("%d %d\n", k == 0 ? 1 : k, i == 0 ? 1 : i);
		printf("%d %d\n", k + 1, i + 1 + n);
	}
	for(int i = s + 4; i < n; i += 2) 
	{
		if(i)
		{
			printf("%d %d\n", i, i + 1);
			printf("%d %d\n", i + n, i + 1 + n);
		}
		printf("%d %d\n", k == 0 ? 1 : k, i == 0 ? 1 : i);
		printf("%d %d\n", k + 1, i + 1 + n);
	}
	if(!(n & 1))
	{
		printf("%d %d\n", n, m);
		printf("%d %d\n", k, n + n);
	}
}

Measured memory_bytes: 2688
H, W = map(int, input().split())
s = [[x for x in input()] for i in range(H)]

from collections import deque

def dfs(maze, sh, sw):
    visited = [[0]*W for _ in range(H)]
    queue = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    maxlen = 0
    while queue:
        h, w , tmplen = queue.pop()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            temp = tmplen
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == 0:
                visited[new_h][new_w] = 1
                temp += 1
                maxlen = max(maxlen, temp)
                queue.appendleft([new_h, new_w, temp])
    
    return maxlen

res = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            continue
        res = max(res, dfs(s, i, j))

print(res)


Measured memory_bytes: 3316
#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> ;
const int INF = 1e9;
const int MOD = 1000000007;

int main(){
    ll n,k;
    cin >> n >> k;
    ll ans = 1;
    for(ll i=k;i<=n;i++){
        ans = (ans + (((i*n)%MOD - (i*i)%MOD + MOD)%MOD + i + 1)%MOD)%MOD;
        //cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

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

int main () {
  int a,b,k;
  cin >> a >> b >> k;
  int cnt=0;
  
  for(int i=min(a,b);i>0;i--){
    if(a%i==0&&b%i==0){
      cnt++;
    if(cnt==k){
      cout << i << endl;
    }
    }
  }
}
      

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
#include <set>
using namespace std;

 
int main(){
  int N, M;
  int a, b;
  set<int> st;
  cin >> N >> M;
  //int H[N];
  vector<int> H(N+1);
  for(int i=1; i<=N; i++){
    cin >> H.at(i);
  }
  for(int j=1; j<=M; j++){
    cin >> a >> b;
    //cout << H[a] << " " << H[b] << endl;
    if(H.at(a) == H.at(b)){
      st.insert(a);
      st.insert(b);
    }
    if(H.at(a) > H.at(b)){
      st.insert(b);
    }
    if(H.at(a) < H.at(b)){
      st.insert(a);
    }
  }
  cout << N - st.size();
  return 0;
}

Measured memory_bytes: 6432
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;
using ll = long long int;

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

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

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};
const ll mod = 1e9+7;
using modint = ModInt< mod >;


string K;
int D;
void input(){
  #ifdef __LOCAL
      fs::path p = __FILE__;
      fs::path input,output;
      input = output = p.parent_path();
      input += string("/input/") + string(p.stem()) + string(".txt");
      output += string("/output/") + string(p.stem()) + string(".txt");
      freopen(input.c_str(), "r", stdin);
      freopen(output.c_str(), "w", stdout);
  #endif
  cin >> K >> D;
}

modint dp[10010][110][3];

int solve(){
  int n = K.length();
  // dp[i][smaller]
  memset(dp,0,sizeof(dp));
  dp[0][0][0] = 1;
  for (int i = 0; i < n; i++)
  {
    for (int d = 0; d < D; d++)
    {
      dp[i+1][(d+K[i]-'0')%D][0] += dp[i][d][0];
      for (int k = 0; k < 10; k++)
      {
        if(k<K[i]-'0') dp[i+1][(d+k)%D][1] += dp[i][d][0];
        dp[i+1][(d+k)%D][1] += dp[i][d][1];
      } 
    }
  }
  cout << (dp[n][0][0]+dp[n][0][1]-1) << endl;
  return 0;
}

int main()
{
  // maketestcase(400);
  input();
  solve();
  return 0;
}


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

typedef long long ll;
const ll mod=1e9+7;
const ll N=1e6+1;
const ll INF=1e10;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n;
	cin>>n;
	vector<int> a(n);
	vector<bool> dp(N,true);
	for(int &i:a) cin>>i;
	sort(a.begin(),a.end());
	for(int i=0;i<n;i++){
		if(i and a[i]==a[i-1]){
			dp[a[i]]=false;
			continue;
		}
		for(int j=2*a[i];j<=N;j+=a[i]) dp[j]=false; 
	}
	int ans=0;
	for(int i=0;i<n;i++) ans+=dp[a[i]];
	cout<<ans;
}


Measured memory_bytes: 4304
N = int(raw_input())
A = map(int, raw_input().split())
R = [A[i]-(i+1) for i in range(N)]
R.sort()
b1 = sum(R)/N
b2 = sum(R)/N+1
b3 = R[N/2]
print min(sum([abs(b1-r) for r in R]), sum([abs(b2-r) for r in R]), sum([abs(b3-r) for r in R]))


Measured memory_bytes: 23760
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<utility>
#include<set>
#include<stack>
#include<complex>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
#define bv vector<bool>
using namespace std;
typedef pair<int, int>PI;
using namespace std;
#define MAX  999999
int main(){
    int c,d;
    while(cin>>c >> d,c+d){
        double ans = INF;
        for(int i = 0; i<=c;i++)
            for(int j = 0; j<=c;j++){
                if(i+j == c){
                    double temp = abs(sqrt((int)(i*i+j*j))-d);
                    ans =min(ans,temp);
                }
            }
        printf("%lf\n",ans);
        
    }
}

Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <string>

int main() {
    int N, Q;
    std::string S;
    std::cin >> N >> Q >> S;

    std::vector<std::pair<char, char>> query(Q);
    for (auto& p : query) std::cin >> p.first >> p.second;

    // idxが左(右)に出るなら-1(1)、出ないなら0を返す
    auto judge = [&](int idx) {
        for (auto& p : query) {
            if (S[idx] != p.first) continue;
            idx += (p.second == 'L' ? -1 : 1);
            if (idx < 0) return -1;
            if (idx >= N) return 1;
        }
        return 0;
    };

    // 左に出る中で一番右のやつ
    int l;
    {
        int ok = -1, ng = N;
        while (ng - ok > 1) {
            int mid = (ng + ok) / 2;
            (judge(mid) < 0 ? ok : ng) = mid;
        }
        l = ok;
    }

    // 右に出る中で一番左のやつ
    int r;
    {
        int ok = N, ng = -1;
        while (ok - ng > 1) {
            int mid = (ng + ok) / 2;
            (judge(mid) > 0 ? ok : ng) = mid;
        }
        r = ok;
    }

    std::cout << r - l - 1 << std::endl;
    return 0;
}


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

using V = vector<int>;
using P = pair<int, int>;
struct edge {
	int to, d, i;
};
signed main() {
	int N, M, C; cin >> N >> M >> C;
	vector<vector<edge>> g(N);
	int sum = 0;
	rep(i, M) {
		int a, b, d; cin >> a >> b >> d;
		a--; b--;
		g[a].push_back({ b,d,i });
		g[b].push_back({ a,d,i });
		sum += d;
	}

	int ans = sum;
	priority_queue<P, vector<P>, greater<P>> que;
	que.push(P(0, 0));
	V dists(N, 1 << 29);
	dists[0] = 0;
	V used(M);
	while (!que.empty()) {
		int pd, pv;
		tie(pd, pv) = que.top(); que.pop();
		for (auto e : g[pv]) {
			if (dists[e.to] <= pd && !used[e.i]) {
				used[e.i] = true;
				sum -= e.d;
				ans = min(ans, C * pd + sum);
			}
			int nd = pd + e.d;
			if (dists[e.to] <= nd) continue;
			dists[e.to] = nd;
			que.push(P(nd, e.to));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 23096
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Main main = new Main();
		main.solveC();
	}

	private void solveC() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long t = sc.nextLong();
		long ans = t * n;
		long prev = -t;
		for (int i = 0; i < n; i++) {
			long tmp = sc.nextLong();
			if (tmp - prev < t) {
				ans -= t - tmp + prev;
			}
			prev = tmp;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 63380
#include <stdio.h>

int N[101], d[101], f[101], C[101][101], nt[101];
int time, n;

typedef struct stack{
  int arry[101];
  int top;
}Stack;

struct stack S;

int push(int input){
  
  if(S.top < 101){
    S.top++;
    S.arry[S.top] = input;
    return 0;
  } 
  return -1;
}

int pop(){
  if(S.top != 0){
    int temp = S.top;
    S.top--;
    return S.arry[temp];
  }
  else return -1;
}

void init(){
  int i;
  for(i = 0; i < 101; i++){
    S.arry[i] = 0;
  }
  S.top = 0;
}

int next(int u){
  int v;
  for(v = nt[u]; v <= n; v++){
    nt[u] = v + 1;
    if(C[u][v] == 1){
      return v;
    } 
  }
  return -1;
}

void visit(int r){
  for(int i = 0; i < n; i++) nt[i] = 0;

  int u, v;
  push(r);
  N[r] = 1;
  time++;
  d[r] = time;

  while(S.top != 0){
    u = S.arry[S.top];
    v = next(u);

    if(v != -1){
      if(N[v] == 0){
        N[v] = 1;
        time++;
        d[v] = time;
        push(v);
      }
    }
    else
      {
        pop();
        N[u] = 2;
        time++;
        f[u] = time;
      }
  }

}

void dfs(void){
  int i;
  for(i = 0; i < n; i++){ // 0:white 1:gray 2:black
    N[i] = 0;
    nt[i] = 0;
  }
  time = 0;

  for(i = 1; i <= n; i++){
    if(N[i] == 0) visit(i);
  }
}

int main(){
  int  i, j, k, l, q;

  init();

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      C[i][j] = 0;
    }
  }    

  for(i = 1; i <= n; i++){
    scanf("%d%d", &k, &l);
    for(j = 1; j <= l; j++){
      scanf("%d", &q);
      C[k][q] = 1;
    } 
  }

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



Measured memory_bytes: 2112
import numpy as np

N,W = map(int,input().split())
DP= np.full(N*1000+1,W+1)
DP[0] = 0
for i in range(N):
  w,v = map(int,input().split())
  DP[v:] = np.minimum(DP[v:],DP[:-v]+w)

print(np.max(np.where(DP <= W)))

Measured memory_bytes: 14908
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=105;
LL read(){
	LL x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)&&ch!='-')
		ch=getchar();
	if (ch=='-')
		f=-1,ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+ch-48,ch=getchar();
	return x*f;
}
int n,m=0,L;
int A[N],B[N],C[N];
void push(int a,int b,int c){
	m++;
	A[m]=a;
	B[m]=b;
	C[m]=c;
}
int main(){
	L=read()-1;
	n=20;
	int cnt=1;
	while (L>=0){
		if (L==0){
			if (cnt<n)
				push(cnt,n,0);
			break;
		}
		if (L==1){
			push(cnt,n,0);
			push(cnt,n,1);
			break;
		}
		if (L%2==0)
			push(cnt,n,L);
		L=(L+1)/2;
		push(cnt,cnt+1,0);
		push(cnt,cnt+1,L);
		L--;
		cnt++;
	}
	printf("%d %d\n",n,m);
	for (int i=1;i<=m;i++)
		printf("%d %d %d\n",A[i],B[i],C[i]);
	return 0;
}

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

using namespace std;

int main()
{
	long long int N , M , ans = 0;
	cin >> N >> M;
	vector<int>data((N + 2)*2);
	for(size_t i = 0; i < M; i++)
	{
		int a , b;
		cin >> a >> b;
		if(b > a)
		{
			data[a*2]++;
			data[b*2+1]--;
		}
	}
	for(size_t i = 1; i < (N + 2)*2; i++)
	{
		data[i] += data[i - 1];
	}
	ans += N + 1;
	long long int begin = 0 , end;
	bool flag = 0,flag2=0;
	for(size_t i = 0; i < (N + 2)*2; i++)
	{
		if(data[i] > 0)
		{
			flag = 1;
		}
		if(data[i] == 0)
		{
			if(flag)
			{
				flag = 0;
				ans += ( i - begin - 2 ) ;
			}
			begin = i;
		}
	}/*
	for(size_t i = 0; i < (N + 2)*2; i++)
	{
		cout << data[i] << " ";
	}
	cout << endl;*/
	cout << ans << endl;
}

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

int main() {
  int K, A, B;
  cin >> K >> A >> B;
  string flg = "NG";

  for(A; A <= B; A++) {
    if(A % K == 0) {
      flg = "OK";
      break;
    }
  }
  cout << flg << endl;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")

using namespace std;

typedef long long ll;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>pb_ds;

#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define pi pair<int,int>
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define mod 1000000007
#define pai acos(-1)
#define N 100005

ll ar[N],dp[N];

int main ()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int n;cin>>n;
   for(int i=1;i<=n;i++) cin>>ar[i];
   dp[n]=0;
   for(int i=n-1;i>=1;i--){
      dp[i]=min(dp[i+1]+abs(ar[i]-ar[i+1]),(i+2<=n)?dp[i+2]+abs(ar[i]-ar[i+2]):INT_MAX);
   }
   cout<<dp[1]<<"\n";
   return 0;
}


Measured memory_bytes: 5180
# include <iostream>
# include <cstdio>
# include <string>
# include <cmath>
# include <cstdio>
# include <cstring>
# include <set>
# include <algorithm>
using namespace std;

int main()
{
   long int n,a,b,i,k,s,ss;
   scanf("%ld%ld%ld",&n,&a,&b);
   if(a>b)
   printf("0");
   else if(n==1&&a!=b)
   printf("0");
   else if(n==1&&a==b)
   printf("1");
   else if(n==2)
    printf("1");
   else
   {
       k=n-2;
       s=a*k;
       ss=b*k;
       printf("%ld",ss-s+1);

   }

    return 0;
}


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

int main(){
  int n, k; cin >> n >> k;
  vector<int> l(n); for(int i = 0; i < n;i++) cin >> l.at(i);
  
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  int length = 0;
  for(int i = 0; i < k; i++) length += l.at(i);
  cout << length << endl;
}

Measured memory_bytes: 256
#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 ll  = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

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

    vector<vector<ll>> g(n);
    rep(i, m){
        ll a, b;
        cin >> a >> b;
        a--, b--;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    queue<int> que;
    que.push(0);

    ll dist[n];
    rep(i, n)dist[i] = -1;
    dist[0] = 0;

    ll parent[n];
    rep(i, n)parent[i] = -1;

    while(!que.empty()){
        int pos = que.front();

        que.pop();

        rep(i, g[pos].size()){
            int child = g[pos][i];

            if(dist[child] >= 0)continue;

            dist[child] = dist[pos] + 1;

            parent[child] = pos;

            que.push(child);
        }
    }

    for(ll i = 1; i < n; ++i){
        if(parent[i] < 0){
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    for(ll i = 1; i < n; ++i)cout << parent[i] + 1 << endl;
}

Measured memory_bytes: 13444
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

int calc(int total, int num) {
    int s1 = num;
    int s2 = total - num;
    return abs(s1 - s2);
}

int main() {
    int n;
    cin >> n;
    vector<int> w(n);
    vector<int> cumulative_sum(n, 0);
    int total = 0;
    rep(i, n) {
        cin >> w[i];
        total += w[i];
    }

    // 累積和
    cumulative_sum[0] = w[0];
    for(int i = 1; i < n; i++) {
        cumulative_sum[i] = cumulative_sum[i - 1] + w[i];
    }

    // 半分を求める
    int mid = total / 2;

    // 半分より大きい和になった番号を求める
    int temp = n - 1;
    rep(i, n) {
        if(cumulative_sum[i] >= mid) {
            temp = i;
            break;
        }
    }

    // 求めた番号とそのひとつ前について、s1,s2の差を求める
    int right = calc(total, cumulative_sum[temp]);
    int left = calc(total, cumulative_sum[temp - 1]);

    cout << min(right, left) << endl;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

#define lf else if

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
	int Getint()
	{
		char ch;
		while (Getchar(ch) && (ch < '0' || ch > '9'));
		int s = ch - '0';
		while (Getchar(ch) && ch >= '0' && ch <= '9')
			s = s * 10 + ch - '0';
		return s;
	}
}

using io::Getint;

const int maxn = 3e5 + 10;

int x[maxn];
bool l[maxn], r[maxn];

int main()
{
	int n = Getint(), L = Getint(), dL = L * 2;
	for (int i = 1; i <= n; ++ i) x[i] = Getint();
	LL ans = 0;
	for (int i = 1; i <= n; ++ i)
	{
		int t = Getint();
		if (t % dL == 0)
		{
			ans += t;
			continue;
		}
		ans += 1ll * (t / dL + 1) * dL;
		t %= dL;
		l[i] = t <= x[i] * 2;
		r[i] = t <= (L - x[i]) * 2;
	}
	int cnt0 = 0, cnt1 = 0;
	for (int i = 1; i < n; ++ i)
	{
		if (l[i] && r[i])
		{
			if (cnt0)
			{
				ans -= dL;
				-- cnt0;
				++ cnt1;
			} else ++ cnt0;
		}
		lf (l[i])
		{
			++ cnt0;
		}
		lf (r[i])
		{
			if (cnt0)
			{
				ans -= dL;
				-- cnt0;
			}
			lf (cnt1)
			{
				-- cnt1;
				++ cnt0;
			}
		}
	}
	ans += r[n] ? 0 : dL;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int32_t main(){
	int a, b, c;
	cin >> a >> b >> c;
	
	if(a+b+c >= 22){
		cout << "bust";
	}
	else
		cout << "win";
	

	return 0;
}



Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
using namespace std;
int _P=1000000007;
int main(){
	int a, b;
	cin >> a >> b;
	cout << a*b << endl;
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repR(i, n) for(int i = n; i >= 0; ++i)
#define FDS(i, n) for(ll i = 0; i < n; ++i)
#define FDSR(i, n) for(int i = n; i >= 0; ++i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define FORR(i, m, n) for(int i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define itn int
#define ednl endl
using namespace std;
typedef long long ll;template<typename TypeInt>TypeInt G_C_D(TypeInt a, TypeInt b){if (a < 0) a = -a;if (b < 0) b = -b;while (b != 0) {a %= b;if (a == 0) return b;b %= a;}return a;}template<typename TypeInt>
TypeInt G_C_D(const std::vector<TypeInt> &list){TypeInt a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = G_C_D(a, list[i]);}return a;}template<typename TypeInt>TypeInt L_C_M(TypeInt a, TypeInt b) {if( a == 0 && b == 0)return 0;return a / G_C_D(a, b) * b;}
template<typename TypeInt>TypeInt L_C_M(const std::vector<TypeInt> &list){TypeInt a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = L_C_M(a, list[i]);}return a;}

int main(){
	int N;
	double T,A;
	cin>>N>>T>>A;
	vector<double> H(N);
	FDS(i,N){
	    cin>>H[i];
	}
	int ans;
	double sub=INF,subsub;
	FDS(i,N){
		subsub=T-H[i]*0.006;
		if(abs(subsub-A)<sub){
			sub=abs(subsub-A);
			ans=i+1;
		}
	}
	cout<<ans<<endl;
}

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

#define cc(x) cout << (x) << endl
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<long long> vll;

template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

const ll inf = 1LL<<58;
const int iinf = 1<<30;

int main(){
    string s;
    cin >> s;
    if((s[0]-'0')*10+(s[1]-'0')>0 && (s[0]-'0')*10+(s[1]-'0')<13){
        if((s[2]-'0')*10+(s[3]-'0')>0 && (s[2]-'0')*10+(s[3]-'0')<13){
            cc("AMBIGUOUS");
            return 0;
        }
        cc("MMYY");
        return 0;
    }
    if((s[2]-'0')*10+(s[3]-'0')>0 && (s[2]-'0')*10+(s[3]-'0')<13){
        cc("YYMM");
        return 0;
    }
    cc("NA");
}

Measured memory_bytes: 256
N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
import math
nP = 1
nQ = 1
n = N-1
work = [i for i in range(1, N+1)]
for p in P:
    nP += work.index(p) * math.factorial(n)
    work.remove(p)
    n -= 1
n = N-1
work = [i for i in range(1, N+1)]
for q in Q:
    nQ += work.index(q) * math.factorial(n)
    work.remove(q)
    n -= 1
print(abs(nP-nQ))

Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib> 
int n,a[300010];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void cmin(int&a,int b){b<a?a=b:1;}
void cmax(int&a,int b){b>a?a=b:1;}
int g[300010],sum[300010];
int calc(){
	int s[2]={0};
	for(int i=0;i<n;i++)s[i%2]+=a[i];
	if(n%2==0)return max(s[0],s[1]);
	sum[n]=0;
	for(int i=n;i--;)sum[i]=sum[i+1]+(i&1?-a[i]:a[i]);
	int left=0,right=1<<29,mid;
	while(right-left>1){
		mid=left+right>>1;
		int val=0;
		for(int i=n-1;i;i-=2){
			if(sum[i]-val>=mid)cmin(val,sum[i-1]);
		}
		if(sum[0]-val>=mid)left=mid;
		else right=mid;
	}
	return s[1]+left;
}
int main(){
	scanf("%d",&n);
	int sum=0;
	for(int i=0;i<n;i++)scanf("%d",a+i),sum+=a[i];
	int ans=calc();
	printf("%d %d\n",ans,sum-ans);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
#define pw(x) (1LL<<(x))
static const int fast_io = [](){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();
static const int precise_doubles = [](){cout<<fixed<<setprecision(20);return 0;}();
typedef pair<int, int> PII;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(k) - iterator to kth largest, order_of_key(k) - #things < k
typedef long double LD;
typedef long long LL;
#define EVAL(x) x
#define SPA(x) EVAL({cout << #x" = " << x << ' ';})
#define NEWL EVAL({cout << '\n';})
#define SPAR(a, b) EVAL({cout<<#a" = ";for(auto it=a;it!=b;)cout<<*(it++)<<" ";cout<<'\n';})
#define SPAV(v) EVAL({cout<<#v" = ";for(auto it=v.begin();it!=v.end();)cout<<*(it++)<<" ";cout<<'\n';})
const int INF = 0x3f3f3f3f; // 1.0e9
const LL LINF = 0x3f3f3f3f3f3f3f3fll; // 4.5e18
const LD eps = 1e-20;
const int mod = 1e9 + 7;
inline int msum(int x, int y) {return (x+y<mod ? x+y : x+y-mod);}
inline int mdif(int x, int y) {return (x>=y ? x-y : x-y+mod);}
inline int mprod(int x, int y) { return (1ll*x*y) % mod; }
inline int mpow(int x, LL y) {LL r=1;while(y){if(y&1)r=mprod(r,x);x=mprod(x,x);y>>=1;}return r;}
inline int minv(int x) { return mpow(x, mod-2); }
//------------------------------------------------------------------------------------------------------

const int N = 1e5 + 10;
const int LOG = 17;
int n, L;
int x[N];
int jmp[N][LOG];

void build() {
    int far = 0;
    REP(i, n) {
        while(far+1 < n and x[far+1] - x[i] <= L) far++;
        jmp[i][0] = far;
    }
    FOR(log, 1, LOG) {
        REP(i, n) {
            jmp[i][log] = jmp[jmp[i][log-1]][log-1];
        }
    }
}

int main() {
    cin >> n;
    REP(i, n) cin >> x[i];
    cin >> L;

    build();

    int q;
    cin >> q;
    while(q--) {
        int source, dest;
        cin >> source >> dest;
        source--, dest--;
        if(source > dest) {
            swap(source, dest);
        }
        int ans = 0;
        for(int log = LOG-1; log >= 0; log--) {
            if(jmp[source][log] < dest) {
                source = jmp[source][log];
                ans += (1<<log);
            }
        }
        cout << ans+1 << '\n';
    }
}
























Measured memory_bytes: 7936
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define fo(i,n) for(int i=1;i<=n;i++)
#define fo1(i,n) for(int i=0;i<n;i++)
#define lli long long int
#define llu unsigned long long int
#define vi vector <int>
#define vii vector <long long int>
#define pb push_back
#define eb emplace_back
#define pi pair<int,int>
#define mk make_pair
#define mpp map<int,int>
#define ff first
#define ss second
#define mod 1000000007

using namespace std;

int main()
{
	//fast;
    int t=1;
    //cin>>t;
    while(t--)
	{
		int l,r,d;
		cin>>l>>r>>d;
		int cnt=0;
		for(int i=l;i<=r;i++)
		{
			if((i%d) == 0)
				cnt++;
		}
		cout<<cnt<<"\n";
	}
}


Measured memory_bytes: 3600
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7;
#define N 1010
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,m,a[22],inv[N],C[N][N],dp[N][N];
int main(){
	n=read(),m=read();
	C[0][0]=1;
	for(int i=1;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=i;++j){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	for(int i=1;i<=m;++i){
		a[i]=read();
	}
	dp[0][0]=1;
	for(int i=1;i<=m;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=min(j,a[i]);++k){
				dp[i][j]=(dp[i][j]+1LL*dp[i-1][j-k]*C[j][k]%mod*C[n-k][a[i]-k])%mod;
			}
		}
	}
	printf("%d\n",dp[m][n]);
	return 0;
}



Measured memory_bytes: 7784
import Control.Monad
import Data.List
import Data.Maybe

type Information = (Int,Int,Int)

main = do
  n <- readLn
  infos <- replicateM n $ (\[a,b,c]->(a,b,c)).map read.words<$>getLine
  putStr $ (\(a,b,c) -> unwords$map show [a,b,c]) $ solve infos

solve :: [Information] -> Information
solve infos = fromJust $ find isAns candidates where
  candidates = [(x,y,ih+abs(x-ix)+abs(y-iy))|x<-[0..100],y<-[0..100]]
  info@(ix,iy,ih) = fromJust $ find (\(_,_,h)->h/=0) infos
  isAns (cx,cy,ch) = all eval infos where
    eval (x,y,h) = h == max (ch-abs(x-cx)-abs(y-cy)) 0

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    n--;
    cout << max({n/a, n/b, n/c, n/d, n/e}) + 5 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  fspcnt = 0;
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}*/


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  int64_t h,w;
  cin >> h >> w;
  int64_t diff = 1000000000000000000;
  for(int64_t i=1;i <= w-1;i++){
    int64_t a,b,c;
    b = (i*h);
    c = (h/2)*(w-i);
    a = h*(w-i) - c;
    //cout << max(a,b)-min(b,c) << endl;
    diff = min(diff,max(a,b)-min(b,c));
    c = ((w-i)/2)*h;
    a = h*(w-i) - c;
    diff = min(diff,max(a,b)-min(b,c));
  }
  for(int64_t i=1;i <= h-1;i++){
    int64_t a,b,c;
    b = (i*w);
    c = (w/2)*(h-i);
    a = w*(h-i) - c;
    //cout << max(a,b)-min(b,c) << endl;
    diff = min(diff,max(a,b)-min(b,c));
    c = ((h-i)/2)*w;
    a = w*(h-i) - c;
    diff = min(diff,max(a,b)-min(b,c));
    
  }
  cout << diff << endl;
  
    
    
    
    
}

Measured memory_bytes: 256
n, p = map(int, input().split())
a = list(map(int, input().split()))

cnt = {}
cnt[0] = 0
cnt[1] = 0
for i in range(n):
    cnt[a[i] % 2] += 1
tmp_ans= 1
for _ in range(cnt[0]):
    tmp_ans *= 2
ans = 0
for i in range(cnt[1] + 1):
    if i % 2 == p:
        tmp = 1
        for j in range(i):
            tmp *= (cnt[1] - j)
        for j in range(i):
            tmp //= (j+1)
        ans += tmp
print(ans * tmp_ans)

Measured memory_bytes: 3064
import math
import numpy as np


def count_2(n):
    i = 0
    while True:
        if n % 2 == 0:
            i += 1
            n = n // 2
        else:
            break
    return i

N = int(input())

a = [int(b) for b in input().split()]

sum = 0
for aa in a:
    sum += count_2(aa)

print(sum)


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

int main() {
    int M; cin >> M;
    int64_t keta = 0, sum = 0;
    for(int i = 0; i < M; ++i) {
        int64_t d, c; cin >> d >> c;
        keta += c;
        sum += d * c;
    }
    int64_t ans = keta + (sum - 1) / 9 - 1;
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

void inp_str(int*);

int main(void) {

int input1[100];
inp_str(input1);

int A,B;

A=input1[0];
B=input1[1];

if(A>=13) {
	printf("%d\n",B);
} else if ((A>=6)&&(A<=12)) {
	printf("%d\n",B/2);
} else {
	printf("0\n");
}
    return 0;

}


void inp_str(int instr[]){
char *ptr;
int z,i,count;
char str[100]={'\0'};
char *ln;

fgets(str, 100, stdin); // 入力："123456\n"
ln = strchr(str, '\n'); /* 改行文字を検索 */
if (ln != NULL) { /* 改行が読み取られていたかどうか */
   *ln = '\0';    /* 改行文字を終端文字に置き換える */
}
else {            /* 入力ストリーム上に文字が残ってる場合 */
   while (1) {    /* 改行文字が読み取られるまで空読みする */
       z = getchar();
      if (z == '\n' || z == EOF) break;
   }
}
	count=0;
    ptr = strtok(str, " ");
    i = atoi(ptr);
    instr[count]=i;
    count=count+1;
    // 2回目以降
    while(ptr != NULL) {
        // strtok関数により変更されたNULLのポインタが先頭
        ptr = strtok(NULL, " ");
        // ptrがNULLの場合エラーが発生するので対処
        if(ptr != NULL) {
		    i = atoi(ptr);
    instr[count]=i;
    		count=count+1;
        }
    }
}



Measured memory_bytes: 128
#include <iostream>
using namespace std;
 
char c[55][55]; int H, W, cnt;
 
int main() {
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) cin >> c[i][j];
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (c[i][j] == '#' && c[i][j - 1] != '#' && c[i - 1][j] != '#' && c[i][j + 1] != '#' && c[i + 1][j] != '#') cnt++;
		}
	}
	if (cnt == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
a,b,c,k = gets.split(" ").map(&:to_i)
a = a.to_i
b = b.to_i
c = c.to_i
$k = k.to_i

def count(x,point)
    return 0 if $k == 0
    case $k <=> x
    when 1 then
        $k = $k - x
        return point * x
    when 0 then
        $k = 0
        return point * x
    when -1 then
        point = point * $k
        $k = 0
        return point
    end
end

puts count(a,1) + count(b,0) + count(c,-1)

Measured memory_bytes: 14224
#include<stdio.h>
int main(void){
 int A,B,C,K=0,d,i;
 scanf("%d %d %d",&A,&B,&C);
 scanf("%d",&K);
 if(A>B){
  d=A;
  A=B;
  B=d;
 }
 if(B>C){
  d=B;
  B=C;
  C=d;
 }
 for(i=0;i<K;i++){
  C=2*C;
 }
 d=A+B+C;
 printf("%d",d);
 return 0;
}

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

 class Main{
             
     static boolean[] ints=new boolean[104729+1];
     static int[] primes=new int[10000+1];
     static void makePrimes(){//System.out.println("ee");
         ints[0]=true;ints[1]=true;
         int primeCounter=0;
         for(int i=2;i<104730;i++){
             if(!ints[i]){primes[primeCounter]=i;primeCounter++;
             for(int j=2;j*i<104730;j++)ints[j*i]=true;}
         }
     }
     public static void main(String args[]){
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         try{
             String line;
             makePrimes();
             while((line=br.readLine())!= null){if(line.isEmpty())break;
                long nn = Long.parseLong(line), count=0;
                if(nn==0)break;
                int c=0;
                
                for(int i=0;i<nn;i++){
                   // System.out.println(primes[i]);
                    c+=primes[i];
                }
                 System.out.println(c);
             }
             
         }catch(Exception e){}         
     }
   
 }

Measured memory_bytes: 19420