akhauriyash/Code-Regression huggingface dataset:
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def my_round(a,dig=0):
    p = 10 ** dig
    return (a * p * 2 + 1) // 2 / p

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b): #最小公倍数
    return a/gcd(a,b)*b

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    s = input()
    ans = []
    for i in range(12):
        ans.append(s[i])
        if i == 3:
            ans.append(' ')
    print(''.join(ans))
    return

if __name__=='__main__':
    main()


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

vector<vector<int>> grid_bfs(int sx, int sy, vector<vector<char>> grid){
    int h = grid.size();
    int w = grid[0].size();
    queue<pair<int, int>> q; q.push({sx, sy});
    vector<vector<int>> dist(h, vector<int>(w));
    vector<vector<bool>> visited(h, vector<bool>(w));
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            dist[i][j] = -1;
            visited[i][j] = false;
        }
    }
    visited[sx][sy] = true;
    dist[sx][sy] = 0;

    vector<int> dx = {1, 0, 0, -1, 1, 1, -1, -1};
    vector<int> dy = {0, 1, -1, 0, 1, -1, 1, -1};

    while (!q.empty()){
        int x, y;
        tie(x, y) = q.front();
        q.pop();

        //２方向、４方向、８方向を設定
        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || h-1 < nx) continue;
            if (ny < 0 || w-1 < ny) continue;
            if (visited[nx][ny]) continue;
            if (grid[nx][ny] == '#') continue;
            q.push({nx, ny});
            dist[nx][ny] = dist[x][y] + 1;
            visited[nx][ny] = true;
        }
        
    }
    return dist;
};

int main() {
    int white = 0;
    int h, w; cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w));
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            cin >> grid[i][j];
            if (grid[i][j] == '.') white++;
        }
    }
    vector<vector<int>> dist = grid_bfs(0, 0, grid);
    if (dist[h-1][w-1] == -1){
        cout << -1 << endl;
    }
    else{
        cout << white - dist[h-1][w-1] - 1 << endl;
    }
    return 0;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll N;
vector<pll> abv[101010];
ll cc[101010];
ll i, j;

ll dfs(ll a,ll p,ll c){
    ll i, j = 1, ret = 0;
    fornum(i,0,abv[a].size()){
        pll b = abv[a][i];
        if(p==b.first)
            continue;
        if(c==j){
            j++;
        }
        cc[b.second] = j++;
        ret=max(dfs(b.first, a, j - 1),ret);
    }
    return max(ret,(ll)abv[a].size());
}

int main(){
    scanf("%lld", &N);
    fornum(i,1,N){
        ll a, b;
        scanf("%lld%lld", &a, &b);
        abv[a].push_back({b, i});
        abv[b].push_back({a, i});
    }
    printf("%lld\n", dfs(1, 0, 0));
    fornum(i,1,N){
        printf("%lld\n", cc[i]);
    }
    return 0;
}

Measured memory_bytes: 11648
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define SORT(x) sort(ALL(x))
#define REVERSE(x) reverse(ALL(x))
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

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

vector<P> factorize(ll n) {
  vector<P> result;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      result.pb({i, 0});
      while (n % i == 0) {
        n /= i;
        result.back().second++;
      }
    }
  }
  if (n != 1) {
    result.pb({n, 1});
  }
  return result;
}

signed main() {
  ll N, Q;
  cin >> N >> Q;

  vector<vector<ll>> to(N);
  rep(i, N - 1) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    to[a].pb(b);
    to[b].pb(a);
  }

  vector<ll> treeNum(N);
  rep(i, Q) {
    ll p, x;
    cin >> p >> x;
    p--;
    treeNum[p] += x;
  }

  vector<bool> done(N);
  vector<ll> ans(N);
  queue<P> q;
  q.push({0, 0});
  while (!q.empty()) {
    ll index = q.front().first;
    ll num = q.front().second;
    q.pop();

    if (index < 0 || index >= N) {
      continue;
    }
    if (done[index]) {
      continue;
    }

    done[index] = true;
    ans[index] = treeNum[index] + num;

    if (!to[index].empty()) {
      for (ll i : to[index]) {
        q.push({i, treeNum[index] + num});
      }
    }
  }

  rep(i, N) {
    cout << ans[i] << " ";
  }
  ENDL;

  return 0;
}

Measured memory_bytes: 21232
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

ll comb2(ll n) {
	return n * (n - 1) / 2;
}

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]]++;
	}

	ll S = 0;
	for (int i = 1; i <= n; i++) {
		S += comb2((long long)b[i]);
	}
	vector<ll> s(n);
	for (int i = 0; i < n; i++) {
		s[i] = S - comb2((long long)b[a[i]]) + comb2((long long)b[a[i]] - 1);
	}
	for (int i = 0; i < n; i++) {
		cout << s[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 5760
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EColorfulBlocks solver = new EColorfulBlocks();
        solver.solve(1, in, out);
        out.close();
    }

    static class EColorfulBlocks {
        public void solve(int testNumber, Scanner in, PrintWriter out) {

            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();

            ModInt res = new ModInt(0);
            ModComb mc = new ModComb(n);

            for (int i = 0; i <= k; i++) {
                res = res.add(new ModInt(m).mul(new ModInt(m - 1).pow(n - i - 1)).mul(mc.combination(n - 1, i)));
            }

            out.println(res.getVal());
        }

    }

    static class ModComb {
        private int size;
        private ModInt[] fac;
        private ModInt[] inv;

        public ModComb(int n) {
            size = n;
            fac = new ModInt[n + 1];
            inv = new ModInt[n + 1];
            makeFac();
        }

        private void makeFac() {
            for (int i = 0; i <= size; i++) {
                if (i == 0) {
                    fac[i] = new ModInt(1);
                } else {
                    fac[i] = fac[i - 1].mul(i);
                }
                inv[i] = fac[i].inv();
            }
        }

        public ModInt combination(int n, int k) {
            if (n < k || k < 0) return new ModInt(0);
            return fac[n].mul(inv[k].getVal()).mul(inv[n - k].getVal());
        }

    }

    static class ModInt {
        public long val;
        final int MOD = (int) 998244353;

        public ModInt(long i) {
            this.val = (i + MOD) % MOD;
        }

        public ModInt mul(long l) {
            return new ModInt(this.val * l);
        }

        public ModInt add(ModInt m) {
            return new ModInt(this.val + m.val);
        }

        public ModInt mul(ModInt m) {
            return new ModInt(this.val * m.val);
        }

        public ModInt inv() {
            return this.pow(MOD - 2);
        }

        public ModInt pow(long l) {
            ModInt res = new ModInt(1);
            ModInt v = new ModInt(this.val);
            while (l > 0) {
                if (l % 2 != 0) {
                    res = res.mul(v.val);
                }
                v = v.mul(v.val);
                l /= 2;
            }
            return res;
        }

        public long getVal() {
            return val;
        }

        public String toString() {
            return Long.toString(val);
        }

    }
}



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

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

    int a = 0, b = 0;
    for (auto& c : s) {
        c -= '0';
        a *= 10;
        a += c;
        b += c;
    }

    cout << (a % b == 0 ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

//C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
const int dx[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int dy[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
const int lr[4] = { 0, 1, 0, -1 };
const int ud[4] = { 1, 0, -1, 0 };



//LOVE Ayane Sakura



using namespace std;

long long GCD(long long a, long long b) {
	if (a < b) {
		swap(a, b);
	}
	long long r = -1;
	while (r != 0) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main() {
	long long K;
	cin >> K;
	long long ans = 0;
	for(int i = 1; i <= K; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 1; k <= K; k++) {
				long long g = GCD(i, j);
				g = GCD(g, k);
				ans += g;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

string board[1001];
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int h, w;
bool hantei(int y, int x){
	if(0 <= y && y < h && 0 <= x && x < w) return true;
	else return false;
}

int main(void){
	cin >> h >> w;
	rep(i, h) cin >> board[i];
	queue<pair<int, int> > q1, q2;
	rep(i, h)rep(j, w){
		if(board[i][j] != '.') q1.push(make_pair(i, j));
	}

	int ans = -1, cnt = 0, nowy, nowx;
	bool flag = true;
	while(flag){
		// printf("cnt %d\n", cnt);
		flag = false; ans++;
		vector<pair<int, int> > memo;//???????????¢??§????????°??????????????§?¨?????¨????????????????
		set<pair<int, int> > s;
		if(cnt % 2 == 0){
			while(!q1.empty()){//q1???????????¨???
				pair<int, int> now = q1.front(); q1.pop();
				if(board[now.first][now.second] == '.') continue;
				int tmp = 0;
				rep(i, 8){
					int nowy = now.first + dy[i], nowx = now.second + dx[i];
					if(!hantei(nowy, nowx)) continue;
					if(board[nowy][nowx] == '.')tmp++;
				}
				if(tmp >= board[now.first][now.second] - '0'){
					// printf("q1 y:%d  x:%d\n", now.first, now.second);
					memo.push_back(make_pair(now.first, now.second));
					// printf("mawari\n");
					rep(k, 8){//???????´?????????¨?????????????¬??????¢??§?´???????????????§??????????????§
						int ny = now.first + dy[k], nx = now.second + dx[k];
						if(!hantei(ny, nx)) continue;
						if(board[ny][nx] != '.'){
							// q2.push(make_pair(ny, nx));
							s.insert(make_pair(ny, nx));
						}
						// printf("q2 ny:%d  nx:%d\n", ny, nx);
					}
					flag = true;
				}
			}
		}else{
			while(!q2.empty()){//q2???????????¨???
				pair<int, int> now = q2.front(); q2.pop();
				if(board[now.first][now.second] == '.') continue;
				int tmp = 0;
				rep(i, 8){
					int nowy = now.first + dy[i], nowx = now.second + dx[i];
					if(!hantei(nowy, nowx)) continue;
					if(board[nowy][nowx] == '.')tmp++;
				}
				if(tmp >= board[now.first][now.second] - '0'){
					// printf("q2 y:%d  x:%d\n", now.first, now.second);
					memo.push_back(make_pair(now.first, now.second));
					// printf("mawari\n");
					rep(k, 8){//???????´?????????¨?????????????¬??????¢??§?´???????????????§??????????????§
						int ny = now.first + dy[k], nx = now.second + dx[k];
						if(!hantei(ny, nx)) continue;
						if(board[ny][nx] != '.'){
							// q1.push(make_pair(ny, nx));
							s.insert(make_pair(ny, nx));
						}
						// printf("q1 ny:%d  nx:%d\n", ny, nx);
					}
					flag = true;
				}
			}
		}
		//????????°???
		rep(k, memo.size()){
			board[memo[k].first][memo[k].second] = '.';
		}
		if(cnt % 2 == 0){
			for(auto x : s) q2.push(make_pair(x.first, x.second));
		}else{
			for(auto x : s) q1.push(make_pair(x.first, x.second));
		}
		cnt++;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 11904
#include<stdio.h>
#define N 100

int p[ N ],m[ N ][ N ],n;

 
  void MatrixChainOrder(){
 
  int i,j,l,k,q;
 
 
  for( i = 1 ; i <= n ; i++){
    m[  i  ][  i  ]=0;
  }

  for( l = 2 ; l <= n ; l++ ){
    for( i = 1 ; i <= n - l + 1 ; i++ ){
     
      j = i + l - 1;
      m[ i ][ j ] = 100000;
      
      for( k = i ; k <= j - 1 ; k++ ){
    q = m[ i ][ k ] + m[ k + 1 ][ j ] + p[ i ]  *  p[ k + 1 ] * p[ j + 1 ] ;
    
    if( q < m[ i ][ j ] ){
      m[ i ][ j ] = q;
    }
      }
    }
  }

  printf("%d\n", m[ 1 ][ n ]);

}
 
main(){
   
  int i,a,count;
 
  scanf("%d",&n);
   
  for( i = 0 ; i < n ; i++ ){
    scanf("%d %d",&p[ i + 1 ],&a);
     
  }

  p[ i + 1 ] = a;
   
  MatrixChainOrder();
   
  return 0;
}

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

int n, m;

void solve() {
    int nC2, mC2;
    if (n < 2) {
        nC2 = 0;
    } else {
        nC2 = n * (n - 1) / 2;
    }
    if (m < 2) {
        mC2 = 0;
    } else {
        mC2 = m * (m - 1) / 2;
    }
    cout << nC2 + mC2 << endl;
}

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

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

int main() {
  string str;
  long int n,m,p[100000]={},ac = 0,wa = 0,tmp = 0;
  int ans[100000]={},v[100000] = {};
  cin >> n >> m;
  for(int i=0;i<m;i++){
    cin >> p[i] >> str;
    if(str == "AC")
      ans[i] = 1;
    else
      ans[i] = -1;
  }
  for(int i=0;i<m;i++){
    if(v[p[i]]==0){
      if(ans[i]==1){
      	ac++;
      	v[p[i]] = 1;
      }else if(ans[i]==-1){
        wa++;
      }
    }
  }
  for(int i=0;i<m;i++){
    if(v[p[i]]==0&&ans[i]-1){
      tmp++;
    }
  }
  cout << ac <<" "<< wa-tmp << endl;
}


Measured memory_bytes: 1792
//let a: [Int] = readLine()!.split(" ").map { Int($0)! }
//print(a)

extension String: CollectionType {} // splitを使うためのおまじない

let na: [Int] = readLine()!.split(" ").map { Int($0)! }
let n = na[0]
let a = na[1]
let xs: [Int] = readLine()!.split(" ").map { Int($0)! }

var v: [Int] = (0...n*50*4).map { _ in 0 }
let gap = n*50*2
v[gap]=1

for x in xs {
    if a-x>0 {
        for(var i = n*a; i >= -n*a; i--){
            v[i+a-x+gap]+=v[i+gap]
        }
    } else {
        for(var i = -n*a; i <= n*a; i++){
            v[i+a-x+gap]+=v[i+gap]
        }
    }
    
}
print(v[gap]-1)

Measured memory_bytes: 4208
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

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

    string S;
    cin >> S;
    int N = S.size() + 1;
    vector<int> left(N, 0), right(N, 0);

    for (int i = 1; i < N; i++)
        left[i] = S[i - 1] == '<' ? left[i - 1] + 1 : 0;

    for (int i = N - 2; i >= 0; i--)
        right[i] = S[i] == '>' ? right[i + 1] + 1 : 0;

    long long total = 0;

    for (int i = 0; i < N; i++)
        total += max(left[i], right[i]);

    cout << total << '\n';
}


Measured memory_bytes: 4764
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	int res = 0;
	for (int i = 1; i < n - 1; i++) {
		if ((p[i - 1] < p[i] && p[i] < p[i + 1]) || (p[i - 1] > p[i] && p[i] > p[i + 1])) {
			res++;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 256
n,m = gets.chomp.split(' ').map(&:to_i)
h = gets.chomp.split(' ').map(&:to_i)
array = Array.new(n,true)
m.times do
  a,b = gets.chomp.split(' ').map(&:to_i)
  if (h[a-1] >= h[b-1])
    array[b-1] = false
  end
  if(h[a-1] <= h[b-1])
    array[a-1] = false
  end
end
puts array.count(true)

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

typedef vector<int> veci;
typedef pair<int, int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9 + 7)
#define fi first
#define se second
#define endl '\n'

void solve() {
    ll h;
    cin >> h;

    ll sum = 0;
    ll base = 1;
    while (h>1) {
        sum += base;

        h /= 2;
        base *= 2;
    }
    cout << sum + base << endl;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST
    (void)argc;
    const string strpath = string(argv[0]) + string("-test.in");
    freopen(strpath.c_str(), "r", stdin);
    int tcs;
    cin >> tcs;
    while (tcs-- > 0)
#endif
        solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
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; }
typedef long long ll;
typedef pair<int,int> P;
const ll M = 9223372036854775807;

int main(){
    int n;
    cin >> n;
    ll a[n];
    rep(i,n)cin >> a[i];
    ll ans = 1;
    rep(i,n){
        if(a[i]==0){
            cout << 0 << endl;
            return 0;
        }
    }
    rep(i,n){
        if(M/a[i]<=ans){
            cout << -1 << endl;
            return 0;
        }
        ans *= a[i];
        if(ans>(ll)1000000000000000000){
            cout << -1 << endl;
            return 0;
        }      
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4416
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author amotoma3
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long h = in.nextLong();

            long[] a = new long[n];
            long[] b = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextLong();
                b[i] = in.nextLong();
            }

            long maxA = 0;
            for (int i = 0; i < n; i++) {
                maxA = Math.max(maxA, a[i]);
            }

            Arrays.sort(b);
            long cnt = 0;
            for (int i = 0; i < n; i++) {
                if (b[n - 1 - i] <= maxA) {
                    cnt += (h + maxA - 1) / maxA;
                    out.println(cnt);
                    return;
                }

                cnt++;
                h -= b[n - 1 - i];
                if (h <= 0) {
                    out.println(cnt);
                    return;
                }
            }
            cnt += (h + maxA - 1) / maxA;
            out.println(cnt);
        }

    }

    static class InputReader {
        BufferedReader in;
        StringTokenizer tok;

        public String nextString() {
            while (!tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(in.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return tok.nextToken();
        }

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

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

        public InputReader(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
            tok = new StringTokenizer("");
        }

    }
}



Measured memory_bytes: 43108
/*
我的心脏怦怦跳，监管者就在附近
name:
Algorithm:
writer:Lxs(cdx)
place:
nothing is impossible
*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<string>
#include<iostream>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<unistd.h>
#include<stdio.h>
#include<cstring>
#define random(a,b) (rand()%(b-a+1)+a)
using namespace std;
bool prime(int x){
	 int i;
	 if(x<2) return 0;
	 for(i=2;i*i<=x;i++){
		if(x%i==0){return 0;}
	 }
	 return 1;
}
int main()
{
	string st;
	cin>>st;
	cout<<st[0]<<st[1]<<st[2];
	return 0;
}


Measured memory_bytes: 3624
#!/usr/bin/env python3
import sys
def S(): return list(sys.stdin.readline())[:-1]
def f():
    s = S()
    t = S()
    ls = len(s)
    lt = len(t)
    dp = [[0]*(ls+1) for _ in range(lt+1)]
    for i in range(lt):
        for j in range(ls):
            if t[i] == s[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

    ans = ""
    while lt > 0 and ls > 0:
        if dp[lt][ls] == dp[lt-1][ls]:
            lt -= 1
        elif dp[lt][ls] == dp[lt][ls-1]:
            ls -= 1
        elif dp[lt][ls] == dp[lt-1][ls-1] + 1:
            ans += t[lt-1]
            lt -= 1
            ls -= 1
    print(ans[::-1])

if __name__ == '__main__':
    f()


Measured memory_bytes: 111708
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}


signed main(){
	ll n; cin>>n;
	VL a(n); rep(i,n) cin>>a[i]; sort(ALL(a));
	vector<bool> dp(a[n-1]+5,true);
	int ans=0;
	rep(i,n-1) if(a[i]==a[i+1]){
		for(ll j=a[i];j<=a[n-1];j+=a[i]) dp[j]=false;
	}
	rep(i,n) if(dp[a[i]]){
		ans++;
		for(ll j=a[i];j<=a[n-1];j+=a[i]) dp[j]=false;
	}
	cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 5040
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <math.h>
#include <map>

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl


int main(){
    string a,b;cin >> a >> b;
    string s;
    bool f=false;
    if(a.size()==b.size())f=true;
    for(int i=0;i<b.size();i++){
        s.push_back(a[i]);
        s.push_back(b[i]);
    }
    if(!f)s.push_back(a[a.size()-1]);
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
N, M=map(int, input().split())
A=[]
B=[]
for i in range(M):
    a,b=map(int, input().split())
    A.append(a)
    B.append(b)
# AB= [map(int, input().split()) for _ in range(M)]
# A, B = [list(i) for i in zip(*AB)]
def find(x,parent):
    if parent[x]==x:
        return x
    else:
        parent[x]=find(parent[x],parent)
        return(parent[x])
        
def union(x,y,parent,rank):
    xroot=find(x,parent)
    yroot=find(y,parent)
    if rank[xroot]>rank[yroot]:
        parent[yroot]=xroot
    elif rank[yroot]>rank[xroot]:
        parent[xroot]=yroot
    elif rank[yroot]==rank[xroot]:
        parent[yroot]=xroot
        rank[xroot]+=1
    return(parent,rank)

    
parent=[i for i in range(N+1)]
rank=[0]*(N+1)
for i in range(M):
    parent,rank=union(A[i],B[i],parent,rank)
for i in range(N+1):
    find(i,parent)
G=parent[1:]
import collections
c=collections.Counter(G)
print(int(c.most_common()[0][1]))

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

int main() {
  char a;
  cin >> a;
  if(a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
} 

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

using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int s = 0;
    int a = n;

    while (n)
        s += n % 10, n /= 10;
    if (a % s == 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BBounding solver = new BBounding();
        solver.solve(1, in, out);
        out.close();
    }

    static class BBounding {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            int n = s.nextInt(), x = s.nextInt(), ans = 1, pre = 0;
            for (int i = 1; i <= n; i++) {
                if ((pre += s.nextInt()) <= x) {
                    ans++;
                }
            }
            w.println(ans);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 22740
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100500;
set < int > used;
vector < pair < int , int > > g[maxn];
int res[maxn];
void solve(int u, int p = -1, int c = 0){
    int cur = 1;
    for(auto v : g[u])
        if(v.first != p){
            cur += (c == cur);
            used.insert(cur);
            solve(v.first, u, cur);
            res[v.second] = cur;
            cur++;
        }
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for(int i = 0 ; i < n - 1 ; ++i){
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    solve(0);
    cout << (int)used.size() << '\n';
    for(int i = 0 ; i < n - 1 ; ++i)
        cout << res[i] << '\n';
    return 0;
}


Measured memory_bytes: 9344
#include <stdio.h>
#include <string.h>

int main(void)
{
  char s[202], p[101], temp[101];

  scanf("%s", s);
  scanf("%s", p);

  strcpy(temp, s);
  strcat(s, temp);

  if(strstr(s,p)==NULL)
    printf("No\n");
  else
    printf("Yes\n");
  return 0;
}

Measured memory_bytes: 2736
#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 = INT32_MAX;
const ll INFL = INT64_MAX;
const int mod = 1e9 + 7;

template <typename T>
void print_vec(vector<T> v) {
  for (T i : v) cout << i << " ";
  cout << endl;
}

int main() {
  int x, a;
  cin >> x >> a;
  if (x < a)
    cout << 0 << endl;
  else
    cout << 10 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

int main()
{
    
        int count = 0;
        string n;
        cin >> n;

        for (int i = 0; i < 3; i++)
        {
            if (n[i] == '7')
            {
                count++;
                break;
            }
        }

        if (count >= 1)
        {
            cout << "Yes";
        }
        else
        {
            cout << "No";
        }

	return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
using lint=long long;
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int n,D;cin>>n>>D;
  vector<int> d(n);
  rep(i,n)cin>>d[i];
  int Q;cin>>Q;
  vector<int> q(Q);
  rep(i,Q)cin>>q[i];
  int cur=D;
  vector<int> p(n);
  rep(i,n){
      p[i]=cur;
      if(abs(cur-d[i])<=cur){
          cur=abs(cur-d[i]);
      }
  }
  vector<int> ok(n);
  int last=1;
  for(int i=n-1;i>=0;--i){
      if(d[i]>=last*2)ok[i]=last;
      else{
          ok[i]=last+d[i];
          last=ok[i];
      }
  }
  rep(i,n){
      //printf("p[%d]=%d, ok[%d]=%d\n",i,p[i],i,ok[i]);
  }
  ok.push_back(1);
  rep(i,Q){
      if(ok[q[i]]<=p[q[i]-1]){
          cout<<"YES"<<"\n";
      }
      else{
          cout<<"NO"<<"\n";
      }
  }
  return 0;
}

Measured memory_bytes: 13024
n = input()
t,a = map(int,raw_input().split())
arr = map(int,raw_input().split())
val = 10**20
ind = -1
for i in range(n):
	z = t-arr[i]*.006
	if abs(z-a) < val:
		ind = i+1
		val = abs(z-a)
print ind

Measured memory_bytes: 29164
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919LL
#define MOD 1000000007
#define int long long

int modpow(int x, int k) {
  int a = 1;
  while (k > 0) {
    if (k & 1) a = (1LL*a*x) % MOD;
    x = (1LL*x*x) % MOD;
    k >>= 1;
  }
  return a;
}
int gcd(int a, int b) {
  if (a > b) swap(a, b);
  if (a == 0) return b;
  return gcd(b%a, a);
}
int xGCD(int a, int b, int &x, int &y) {
  if(b == 0) {
     x = 1;
     y = 0;
     return a;
  }
  int x1, y1, gcd = xGCD(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return gcd;
}

int S;
int num[11];
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  num[1] = 9;
  for (int i=2; i<=10; i++) num[i] = 10LL*num[i-1];

  cin >> S;
  vector<int> ds;
  for (int d=1; d*d<=S; d++) if (S%d == 0) ds.pb(d), ds.pb(S/d);
  sort(all(ds)); uniq(ds);
  int s = 0;
  for (int f : ds) {
    int n = S/f;
    if (f <= 9 && n > num[f]) continue;
    s = (s + 9LL*modpow(10, f-1)+1+MOD-n) % MOD;
  }
  for (int a=10; a<=S; a++) {
    int lo = 1+S/(a+1), hi = (S-1)/a;
    if (lo <= hi) {
      s += hi-lo+1;
      if (s >= MOD) s -= MOD;
    }
  }

  for (int a=1; a<=10; a++) {
    for (int b=a+1; b<=10; b++) {
      int g = gcd(a, b);
      long long c = S;
      for (int x=a+1; x<=b-1; x++) c -= 1LL*x*num[x];
      if (c <= 0 || c % g) continue;
      int x0, y0;
      xGCD(a, b, x0, y0);
      x0 *= c/g;
      y0 *= c/g;
      assert(a*x0+b*y0==c);
      int a2 = a/g, b2 = b/g;
      int lo = max((INF*b2+b2-x0)/b2, (INF*a2+y0-num[b]+a2-1)/a2)-INF;
      int hi = min((INF*b2+num[a]-x0)/b2, (INF*a2+y0-1)/a2)-INF;
      if (lo <= hi) s = (s+hi-lo+1) % MOD;
    }
  }
  cout << s << "\n";
  return 0;
}


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

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 FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

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

void vprint(vector<ll> A){
    ll L = A.size();
    FOR(i, 0, L){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
}

ll D[200];

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

    // input
    ll N, X;
    cin >> N >> X;

    vector<ll> L(N+1);
    FOR(i, 1, N+1){
        cin >> L.at(i);
    }
    // vprint(L);

    D[1] = 0;
    FOR(i, 2, N+2){
        D[i] = D[i-1] + L[i-1];
    }

    // FOR(i, 1, 10){
    //     pn(D[i]);
    // }

    ll count = 0;
    FOR(i, 1, N+2){
        if(D[i]<=X){
            count++;
        }
    }
    p(count);
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>
 
using namespace std;
 
int main(){
    int h,w;
    cin>>h>>w;
    vector<string> hoge(h);
    for(int i=0;i<h;i++) cin>>hoge.at(i);
    
    for(int i=-1;i<=h;i++){
        for(int j=-1;j<=w;j++){
            if(i==-1 || i==h || j==-1 || j==w){
                cout<<'#';
            }else{
                cout<<hoge.at(i).at(j);
            }
        }
        cout<<endl;
    }
    
    return 0;
}

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

struct unionfind {
    vi root; // 各要素の根
    vi size; // 自分以下の子の数(根の場合は集合の要素数)
    unionfind(int n) {
        root.resize(n);
        size.resize(n, 1);
        rep(i, n) {
            root[i] = i;
        }
    }
    int find(int x) { // 要素xの根を返す
        if (x == root[x]) return x;
        return root[x] = find(root[x]);
    }
    void unite(int x, int y) { // 要素xとyを同一の集合(根)に結合する
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (size[x] >= size[y]) {
            root[y] = x;
            size[x] += size[y];
        } else {
            root[x] = y;
            size[y] += size[x];
        }
    }
    bool same(int x, int y) { // 要素xとyが同一の集合に属するか真偽値を返す
        return find(x) == find(y);
    }
};

int main() {
    // input
    int n, k , l;
    cin >> n >> k >> l;
    unionfind road(n);
    unionfind train(n);
    set<pii> a;
    rep(i, k) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        road.unite(p, q);
    }
    rep(i, l) {
        int r, s;
        cin >> r >> s;
        r--; s--;
        train.unite(r, s);
    }
    // solve
    map<pii, int> m;
    rep(i, n) {
        pii p = make_pair(road.find(i), train.find(i));
        m[p]++;
    }
    // output
    rep(i, n) {
        pii p = make_pair(road.find(i), train.find(i));
        printf("%d ", m[p]);
    }
}

Measured memory_bytes: 17792
#include<vector>
#include<iostream>

using namespace std;

int main() {
  int n;

  cin >> n;
  while(n != 0) {
    vector<int> data;
    for(int i = 0; i < n; i++) {
      int x;
      cin >> x;
      data.push_back(x);
    }


    int sum = 0;
    for(int i = 0; i < data.size(); i++) {
      sum += data.at(i);
    }
    double ave = sum / data.size();

    int cnt = 0;
    for(int i = 0; i < data.size(); i++) {
      if(ave >= data.at(i)) {
        cnt++;
      }
    }

    cout << cnt << endl;
    cin >> n;
  }
}


Measured memory_bytes: 3272
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n,c,k ;
	cin >> n >> c >> k ;
	vll t(n) ;
	for(int i=0;i<n;i++) cin >> t.at(i) ;
	mysort(t) ;

	ll ans = 0 ;
	for(int i=0;i<n;i++){
		ans++ ;
		ll sub = i ;
		for(int j=0;j<c;j++){
			if(i+j>=n||t.at(i)+k<t.at(i+j)){
				sub = i+j-1 ;
				break ;
			}else{
				sub = i+j ;
			}
		}
		i = sub ;
	}
	cout << ans << endl ;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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;
	vector<ll> a(n);
	rep(i,n){
		cin >> a[i];
		a[i] -= (i+1);
	}
	sort(a.begin(), a.end());
	ll mid = a[n/2];
	ll ans = 0;
	rep(i,n) ans += llabs(a[i] - mid);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4764
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
  static InputReader in;
  static PrintWriter out;

  static class Solution {
    void solve() throws IOException {
      int n = in.nextInt();
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
    	   a[i] = in.nextInt();
      }
      long sum = 0;
      int max = -1000000;
      int min = 1000000;
      
      for (int i = 0; i < n; i++) {
    	  sum += a[i];
    	  max = Math.max(max, a[i]);
    	  min = Math.min(min, a[i]);
      }
      out.println(min+" "+max+" "+sum);
      
  }
}
    
  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out);
    Solution solver = new Solution();
    solver.solve();
    out.close();
}

  static class InputReader {
    public BufferedReader br;
    public StringTokenizer st;

    public InputReader(InputStream stream) {
      br = new BufferedReader(new InputStreamReader(stream));
    }

    public int nextInt() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Integer.parseInt(st.nextToken());
    }

    public long nextLong() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Long.parseLong(st.nextToken());
    }

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

    public double nextDouble() throws IOException {
      while (st == null || !st.hasMoreTokens()) {
        st = new StringTokenizer(br.readLine());
      }
      return Double.parseDouble(st.nextToken());
    }

  }

}

Measured memory_bytes: 28420
#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
    if(x>y)swap(x,y);
    for(int i=x; i >= 1; i--){
        if(i == 1)return 1;
        else if( x % i  == 0 && y % i == 0)return i;
        //最大公約数、lcm = x*y/gcd 僕のVSCではgcd関数が使えませんでした(泣)だれか教えてください。
    }
}
typedef long long ll;

int main(){ 
    int n,x;
    cin >> n >> x;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin >> a[i];
    sort(a.begin(),a.end());
    int ans = 0,sum = 0;
    for(int i=0;i<n;i++){
        sum += a[i];
        if(sum > x){
            cout << i << endl;
            return 0;
        }
    }
    if(sum == x)cout << n << endl;
    else cout << n-1 << endl;    
    
}

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

#define long long long

const int N = 1e5+5;

int n, k;
long d[N];

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%lld", d+i), d[i] += d[i-1]; 
    map<int, int> M;
    M[0]++;
    long sum = 0;
    for(int i = 1; i <= n; ++i) {
        d[i] %= k;
        sum += M[d[i]];
        M[d[i]]++;
    }
    cout << sum << endl;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
const int mod=1e9+7;
int n,i,a[200005],d[200005],z[200005],c[200005],inv[200005],lst[200005],ans;
int s1[200005],s2[200005];
int pw(int x,int y){
	int z=1;
	while(y){
		if(y&1) z=1ll*z*x%mod;
		x=1ll*x*x%mod;y/=2;
	}
	return z;
}
int lowbit(int x){
	return (x&-x);
}
void add(int x,int y){
	while(x<=n){
		s1[x]=(s1[x]+y)%mod;
		s2[x]++;
		x+=lowbit(x);
	}
}
int query1(int x){
	int s=0;
	while(x){
		s=(s+s1[x])%mod;
		x-=lowbit(x);
	}
	return s;
}
int query2(int x){
	int s=0;
	while(x){
		s=s+s2[x];
		x-=lowbit(x);
	}
	return s;
}
int main(){
	inv[1]=1;
	for(i=2;i<=200000;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	}
	cin>>n;
	rep(i,n){
		cin>>a[i];
		c[a[i]]++;
	}
	for(i=n-1;i;i--)c[i]+=c[i+1];
	int all=1;
	rep(i,n){
		c[i]-=n-i;
		all=1ll*all*c[i]%mod;
	}
	if(all==0){
		puts("0");
		return 0;
	}
	d[0]=1;z[0]=0;
	rep(i,n){
		int x=1ll*(c[i]-1)*inv[c[i]]%mod;
		if(x){
			z[i]=z[i-1];
			d[i]=1ll*d[i-1]*x%mod;
		}
		else{
			d[i]=d[i-1];
			z[i]=z[i-1]+1;
			lst[z[i]]=i;
		}
	}
	rep(i,n){
		ans=(ans+1ll*(query1(a[i])-query1(lst[z[a[i]]]-1)+mod)%mod*d[a[i]]%mod*all%mod*inv[2])%mod;
		add(a[i],pw(d[a[i]],mod-2));
	}
	rep(i,n) s1[i]=s2[i]=0;
	for(i=n;i>=1;i--){
		ans=(ans-1ll*(query1(a[i]-1)-query1(lst[z[a[i]]]-1)+mod)%mod*d[a[i]]%mod*all%mod*inv[2])%mod;
		if(ans<0)ans+=mod;
		ans=(ans+1ll*query2(a[i]-1)*all)%mod;
		add(a[i],pw(d[a[i]],mod-2));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> pii;
 
#define REP(a,b,c) for(ll (a)=(b);(a)<(c);(a)++)
#define PER(a,b,c) for(ll (a)=(b);(a)>=(c);(a)--)
 
void ii(ll &x){ cin >> x; }
void is(string &x){ cin >> x; }
void oi(ll x){ cout << x << " "; }
void os(string x){ cout << x; }
void oie(ll x){ cout << x << endl; }
void ose(string x){ cout << x << endl; }
void oe(){ cout << endl; }
 
ll INF = 1e9+7;
 
int main(){
    ll H, W;
    ii(H);
    ii(W);
    if(H==1 || W==1){
        oie(1);
    }else{
        oie(((W+1)/2)*((H+1)/2)+(W/2)*(H/2));
    }
    return 0;
}

Measured memory_bytes: 256