akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define int long long
#define F first
#define S second
using namespace std;
typedef long long ll;
ll n,m,r;
typedef pair<ll,ll> pii;
typedef vector<pii> vii;
ll a[105],b[105];
string s;
signed main()
{

    //ios_base::sync_with_stdio(0),cin.tie(0);
    while(cin>>n)
    {
        ll ans=0;
        rep1(i,n)
        {
            if(i<10) ans++;
            if(i>=100&&i<=999) ans++;
            if(i>=10000&&i<=99999) ans++;
        }
        cout<<ans<<"\n";
    }
}


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

int main (){
  int N ,A,B;
  cin >>N >> A >>B;
  vector<int> P(N);
  for(int i = 0;i < N;i++){
    cin >> P.at(i);
  }
  int count1 = 0,count2 = 0,count3 = 0;
  for(int j = 0;j < N;j++){
    if(P.at(j) <= A){
      count1++;
    }
  }
  for(int k = 0;k < N;k++){
    if(A + 1 <= P.at(k) && P.at(k) <= B){
      count2++;
    }
  }
  for(int l = 0;l < N;l++){
      if(P.at(l) >= B + 1){
        count3++;
      }
    }
  if(count1 <= count2 && count1 <= count3){
    cout << count1 <<endl;
  }
  if(count2 < count1 && count2 <= count3){
    cout << count2 << endl;
  }
  if(count3 < count1 && count3 < count2){
    cout << count3 << endl;
  }
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
a.sort()
M=max(a)
p=[]
for i in range(n):
    if i+1<=n-1:
        if a[i]==a[i+1]:
            p+=[j for j in range(a[i],M+1,a[i])]
        else:
            p+=[j for j in range(a[i]*2,M+1,a[i])]
    else:
        p+=[j for j in range(a[i]*2,M+1,a[i])]

print(len(set(set(a)-set(p))))

Measured memory_bytes: 192024
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

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

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

int main(){
    ll n;
    cin >> n;
    ll a[n+1], b[n];
    rep(i, n+1) cin >> a[i];
    rep(i, n) cin >> b[i];
    ll ans = 0;
    rep(i, n){
        ans += min(a[i], b[i]);
        b[i] = max((ll)0, b[i] - a[i]);
        ans += min(a[i+1], b[i]);
        a[i+1] = max((ll)0, a[i+1] - b[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 5104
import java.util.*;

class Main{
    static Long n;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        Integer p = Integer.parseInt(n.substring(n.length()-1, n.length()));
        String res = "hon";
        if(p==0|p==1|p==6|p==8){
            res = "pon";
        }
        else if(p==3){
            res = "bon";
        }
        System.out.println(res);
    }

}


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

int main() {
	int n, x; cin >> n >> x;
	vector<int> l;
	int ans = 1, sum = 0;
	for (int i = 0; i < n; i++) {
		int tmp; cin >> tmp;
		l.push_back(tmp);
		sum += tmp;
		if (sum <= x)ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const ll MOD = 1000000007;
// const int INF = 2000000000;

int R, G, B, N;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> R >> G >> B >> N;

  int ans = 0;

  for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= N; j++) {
      int sum = R * i + G * j;
      if (sum < N && (N - sum) % B == 0) {
        ans++;
      } else if (sum == N) {
        ans++;
      }
    }
  }

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

Measured memory_bytes: 256
// http://abc073.contest.atcoder.jp/tasks/abc073_a
#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  string s;
  cin >> s;
  cout << (s.find("9") != string::npos? "Yes": "No") << endl;
  

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int n,m,s=0,l=0,c=0;
  scanf("%d%d",&n,&m);
  m*=4;
  int a[102];
  for(int i=0;i<n;i++)
  {
    scanf("%d",&a[i]);
    s+=a[i];
  }
  l=s/m;
  if(s%m)
  {
    l++;
  }
  for(int i=0;i<n;i++)
  {
    if(a[i]>=l)
    {
      c++;
    }
  }
  m/=4;
  if(c>=m)printf("Yes\n");
  else printf("No\n");
}

Measured memory_bytes: 128
main(){
	int n,c[200],d[200],m,k,i;
	scanf("%d%d",&n,&m);
	for(i=0;i<2*n;i++)
		c[i]=1+i;
	for(;m--;){
		scanf("%d",&k);
		if(k){
			memcpy(d,c+k,sizeof(int)*(2*n-k));
			memcpy(d+2*n-k,c,sizeof(int)*k);
		}else{
			for(i=0;i<n;i++){
				d[i*2]=c[i];
				d[i*2+1]=c[n+i];
			}
		}
		memcpy(c,d,sizeof(int)*2*n);
	}
	for(i=0;i<2*n;i++)
		printf("%d\n",c[i]);
	exit(0);
}

Measured memory_bytes: 0
#include <stdio.h>

typedef struct {
	int key, id;
} data;

typedef struct {
	data obj[400001];
	int size;
} min_heap;

void push(data x, min_heap* h)
{
	int i = ++(h->size);
	data tmp;
	h->obj[i] = x;
	while (i > 1) {
		if (h->obj[i].key < h->obj[i>>1].key) {
			tmp = h->obj[i>>1];
			h->obj[i>>1] = h->obj[i];
			h->obj[i] = tmp;
			i >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j = i << 1;
		} else break;
	}
	return output;
}

void add_BIT(int N, int BIT[], int i, int k)
{
	while (i <= N) {
		BIT[i] += k;
		i += (i & -i);
	}
}

int sum_BIT(int BIT[], int r)
{
	int sum = 0;
	while (r > 0) {
		sum += BIT[r];
		r -= (r & -r);
	}
	return sum;
}

int main()
{
	int i, H, W, A, B;
	scanf("%d %d", &H, &W);
	
	int j, s[200002], left[200002], right[200002], BIT[200001] = {}, L, R, M, tmp;
	data d;
	min_heap h;
	h.size = 0;
	for (i = 0; i <= W + 1; i++) {
		s[i] = i;
		left[i] = i - 1;
		right[i] = i + 1;
	}
	for (i = 1, d.key = 0; i <= W; i++) {
		d.id = i;
		push(d, &h);
		add_BIT(W, BIT, i, 1);
	}
	for (i = 1; i <= H; i++) {
		scanf("%d %d", &A, &B);
		tmp = sum_BIT(BIT, A - 1);
		if (sum_BIT(BIT, B) == tmp) {
			printf("%d\n", h.obj[1].key + i);
			continue;
		}
		
		L = A;
		R = B++;
		while (L < R) {
			M = (L + R) / 2;
			if (s[M] >= 0) {
				L = M;
				break;
			} else if (sum_BIT(BIT, M) > tmp) R = M;
			else L = M + 1;
		}
		
		if (s[B] < 0) add_BIT(W, BIT, B, 1);
		for (j = left[L]; j >= A; j = left[j]) {
			s[B] = (s[j] > s[B])? s[j]: s[B];
			s[j] = -1;
			add_BIT(W, BIT, j, -1);
		}
		left[B] = j;
		right[j] = B;
		for (j = L; j < B; j = right[j]) {
			s[B] = (s[j] > s[B])? s[j]: s[B];
			s[j] = -1;
			add_BIT(W, BIT, j, -1);
		}
		if (j != B) {
			left[j] = B;
			right[B] = j;
		}
		if (B <= W) {
			d.key = B - s[B];
			d.id = B;
			push(d, &h);
		}
		
		while (h.size > 0 && s[h.obj[1].id] < h.obj[1].id - h.obj[1].key) pop(&h);
		if (h.size > 0) printf("%d\n", h.obj[1].key + i);
		else break;
	}
	for (; i <= H; i++) printf("-1\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 6644
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(M)]
P=list(map(int,input().split()))
c=0
for i in range(2**N):
    A=[0]*N
    for j in range(N):
        if (i>>j&1):
            A[j]=1
    T=True
    for j in range(M):
        s=0
        for k in range(L[j][0]):
            s+=A[L[j][k+1]-1]
        if s%2!=P[j]:
            T=False
    if T:
        c+=1
print(c)

Measured memory_bytes: 9240
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (int i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using PL = pair<long long, long long>;
const int INF = 1001001007;
const int mod = 1000000007;

int main(){
    int n, m, c; cin >> n >> m >> c;
    vector<int> ar(m);
    rep(i,m) cin >> ar[i];
    vector<vector<int>> cr(n, vector<int>(m));
    rep(i,n)rep(j,m) cin >> cr[i][j];
    int ans = 0;
    rep(i,n){
        int ac = c;
        rep(j,m) ac += ar[j] * cr[i][j];
        if (ac > 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline().rstrip()
def main():
    def scoring(ans, d, t, C, S, L):
        ans += S[d][t]
        L[t] = d
        ans -= sum([c * (d - l) for (c, l) in zip(C, L)])        
        return ans, L
    D = int(input())
    C = list(map(int, input().split()))
    S = [list(map(int, input().split())) for _ in range(D)]
    L = [-1] * 26
    ans = 0
    for d in range(D):
        t = int(input()) - 1
        ans, L = scoring(ans, d, t, C, S, L)
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9388
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	int ans = 0;
	if (n >= 10) {
		ans += 9;
		if (n >= 1000) {
			ans += 900;
			if (n >= 100000) ans += 90000;
			else if (n >= 10000) ans += (n - 9999);
		} else if (n >= 100) ans += (n - 99);
	}
	else ans = n;

	cout << ans << endl;

	return 0;
}

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

static const ll INF = 1e15;

int main(void)
{
	int n, m, q;
	cin >> n >> m >> q;
	vector<vector<ll>> grid(n, vector<ll>(n, 0));
	rep(i, m) {
		ll s, t;
		cin >> s >> t;
		s--; t--;
		grid[s][t]++;
	}
	vector<vector<ll>> gridSum(n, vector<ll>(n + 1, 0));
	rep(i, n) {
		rep(j, n) {
			gridSum[i][j + 1] = gridSum[i][j] + grid[i][j];
		}
	}
	vector<ll> ans;
	rep(_, q) {
		ll s, t;
		cin >> s >> t;
		s--; t--;
		ll c = 0;
		for (int i = s; i < t + 1; i++) {
			c += gridSum[i][t + 1] - gridSum[i][s];
		}
		ans.push_back(c);
	}
	rep(i, q) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 5748
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

int main(){
  ll h, n;
  cin >> h >> n;
  vector<ll> A(n), B(n);
  vector<vector<ll>> H(n+1, vector<ll>(h+1, pow(10,9)));
  RAP(i, n){
    cin >> A[i] >> B[i];
  }
  H[0][0]=0;
  for(ll i=0; i<n; i++){
    for(ll j=0; j<=h; j++){
      if(j-A[i]>=0){
        H[i+1][j] = min(H[i+1][j-A[i]] + B[i], H[i][j]);
      }else{
        H[i+1][j] = min(H[i+1][0]+B[i], H[i][j]);
      }
    }
  }
  cout << H[n][h] << endl;
  return 0;
}


Measured memory_bytes: 78592
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <stdio.h>
//#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main(){
  int ope[8][3] = {
    { 1, 1, 1},
    { 1, 1, -1},
    { 1, -1, 1},
    { 1, -1, -1},
    { -1, 1, 1},
    { -1, 1, -1},
    { -1, -1, 1},
    { -1, -1, -1},
  };
  int N[4];
  string ans,s;
  cin >> s;
  N[0] = s[0] - '0';
  N[1] = s[1] - '0';
  N[2] = s[2] - '0';
  N[3] = s[3] - '0';
  for(int i=0;i<8;i++){
    if(N[0] + ope[i][0]*N[1] + ope[i][1]*N[2] + ope[i][2]*N[3] == 7){
      ans += to_string(N[0]);
      if(ope[i][0]==1){
        ans+="+";
      }else{
        ans+="-";
      } 
      ans += to_string(N[1]);
      if(ope[i][1]==1){
        ans+="+";
      }else{
        ans+="-";
      }
      ans += to_string(N[2]);
      if(ope[i][2]==1){
        ans+="+";
      }else{
        ans+="-";
      }
      ans += to_string(N[3]);
      ans += "=7";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

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

string dp[71][71];
int W, H;
string c[71];

string dfs(int h, int w) {	
	if ( dp[h][w] != "" ) return dp[h][w];

	string ret = "";
	if ( h < H-1 && '0' <= c[h+1][w] && c[h+1][w] <= '9' ) {
		ret = dfs(h+1, w);
	}
	if ( w < W-1 && '0' <= c[h][w+1] && c[h][w+1] <= '9' ) {
		string tmp = dfs(h, w+1);
		if ( tmp.size() > ret.size() ) ret = tmp;
		else if ( tmp.size() == ret.size() ) ret = max(ret, tmp);		
	}

	return dp[h][w] = c[h][w]+ret;
}

int main() {
	while ( cin >> W >> H, W|H ) {
		for ( int i = 0; i < H; i++ ) cin >> c[i];	 

		for ( int i = 0; i < 71; i++ ) {
			for ( int j = 0; j < 71; j++ ) dp[i][j] = "";
		}
		
		string ans = "";
		for ( int i = 0; i < H; i++ ) {
			for ( int j = 0; j < W; j++ ) {
				if ( '1' <= c[i][j] && c[i][j] <= '9' ) {
					string tmp = dfs(i, j);
					if ( tmp.size() > ans.size() ) ans = tmp;					
					else if ( tmp.size() == ans.size() ) ans = max(ans, tmp);
				}
			}
		}

		cout << ans << endl;		
	}
}



Measured memory_bytes: 3332
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int n = Integer.parseInt(sc.next());
    int k = Integer.parseInt(sc.next());
    pw.println(
      IntStream.range(0, n)
        .mapToObj(i -> sc.next())
        .mapToInt(Integer::parseInt)
        .filter(h -> h >= k)
        .count());
  }
}


Measured memory_bytes: 48524
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

//------------------------------------------------------

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, a;
    cin >> x >> a;
    if (x < a) cout << 0 << endl;
    else cout << 10 << endl;

    return 0;
}



Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
	public static void main(String[]args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str=br.readLine();
		double r=Double.parseDouble(str);
		double pi=3.141592653589;
		double are = r*r*pi;
		double circ = 2*r*pi;
		System.out.printf("%.8f %.8f%n",are,circ);
	}
}

Measured memory_bytes: 17052
#include <stdio.h>

int main(void) {
    int x, y, tmp;
    for(;;) {
        scanf("%d %d", &x, &y);
        if(x == 0 && y == 0) {
            break;
        } else if(x > y) {
            tmp = x;
            x = y;
            y = tmp;
        }
        printf("%d %d\n", x, y);
    }
}


Measured memory_bytes: 2052
#include <stdio.h>
#include <algorithm>
using namespace std;

int N, D, A; pair<int, int> M[200200];
int cnt = 1, coord[400400];
long long sum[400400];

void push(int x, long long p)
{
	x = lower_bound(coord + 1, coord + cnt, x) - coord;
	while (x < cnt){
		sum[x] += p;
		x += x & (-x);
	}
}

long long pop(int x)
{
	long long r = 0;
	x = lower_bound(coord + 1, coord + cnt, x) - coord;
	while (x){
		r += sum[x];
		x -= x & (-x);
	}
	return r;
}

int main()
{
	scanf ("%d %d %d", &N, &D, &A);
	for (int i = 0, x, h; i < N; i++){
		scanf ("%d %d", &x, &h); x -= D;
		M[i] = { x, h };
		coord[cnt++] = x;
		coord[cnt++] = x + 2 * D + 1;
	}

	sort(coord + 1, coord + cnt);
	sort(M, M + N);

	long long drop = 0;
	for (int i = 0; i < N; i++){
		long long nh = M[i].second - pop(M[i].first);
		if (nh > 0){
			long long d = (nh + A - 1) / A;
			push(M[i].first, d * A);
			push(M[i].first + 2 * D + 1, -d * A);
			drop += d;
		}
	}

	printf ("%lld\n", drop);

	return 0;
}

Measured memory_bytes: 6400
#include<iostream>

const int N = 5;

void solve(int *a){
	int r=0,s=0,p=0;
	for(int i=0; i<N; i++){
		switch(a[i]){
		case 1:
			r++;
			break;
		case 2:
			s++;
			break;
		case 3:
			p++;
			break;
		}
	}
	if((r && s && p) || r==5 || p==5 || s==5)
		for(int i=0; i<N; i++)
			std::cout << 3 << std::endl;
	else{
		int x = 0, y = 3;
		if(r == 0)
			y = 2;
		else if(p == 0)
			y = 1;
		for(int i=0; i<N; i++){
			if(a[i] == y)
				x = 1;
			else
				x = 2;
			std::cout << x << std::endl;
		}
	}
}

int main(){
	int n[N];
	while(true){
		for(int i=0; i<N; i++){
			std::cin >> n[i];
			if(!n[i])
				return 0;
		}
		solve(n);
	}

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define num 1000000007
//#define num 998244353
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define inarr(i,a,n,A) for(ll i=a;i<n;i++) { cin>>A[i]; }
#define vll vector<long long>
#define pii pair <int,int>
#define pll pair<long long, long long>
#define vpii vector< pair <int,int>>
#define vpll vector< pair<long long, long long>>
//#define max(a,b) ((a>b)?a:b)
//#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define avg(a,b) ((a)+(b))/2
#define pb push_back
#define pob pop_back
#define sf int flag=0     //Remember semicolon
// #define assmin(a,b) if(b<=a) { a=b; }
// #define assmax(a,b) if(b>=a) { a=b; }
#define f first
#define s second
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define all(x) x.begin(), x.end()
#define M_PI 3.14159265358979323846
#define epsilon (double)(0.00000000001)
#define side 1e9
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
ll mod(ll a, ll b)
{
	if(a%b<0)
	{
		return a%b + b;
	}
	return a%b;
}
 
 
ll mod_exp(ll a, ll b, ll c)
{
	ll res=1;
	a=a%c;
	while(b>0)
	{
		if(b%2==1)
		{
			res=(res*a)%c;
		}
		b/=2;
		a=(a*a)%c;
	}
	return res;
}
ll mymod(ll a,ll b)
{
    return ((a%b)+b)%b;
}
bool prime[200001];
void SieveOfEratosthenes() 
{ 
    memset(prime, true, sizeof(prime)); 
    prime[1]=false;
    for (int p=2; p*p<=200000; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=200000; i += p) 
                prime[i] = false; 
        } 
    } 
    return;
}
ll powe[200005];
void power()
{
    powe[0]=1;
    REP(i,1,200005)
    {
        powe[i]=mymod(2*powe[i-1],num);
    }
}
ll gcdExtended(ll,ll,ll *,ll *);
ll modInverse(ll a, ll m) 
{ 
    ll x, y; 
    ll g = gcdExtended(a, m, &x, &y); 
        ll res = (x%m + m) % m;
        return res;
} 
ll gcdExtended(ll a, ll b, ll *x, ll *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
    ll x1, y1; 
    ll gcd = gcdExtended(b%a, a, &x1, &y1); 
    *x = y1 - (b/a) * x1; 
    *y = x1; 
    return gcd; 
}
struct node
{
	vll adj;
    ll height;
};

ll find(ll n, ll wt, ll nm)
{
    ll st = 1;
    ll en = nm;
    ll mid = (st) + (en - st)/2;
    while(st<=en)
    {
        if(wt+3*(nm+mid)>=n && wt+2*(nm+mid)<=n)
        {
            return mid;
        }
        else if(wt+3*(nm+mid)<n)
        {
            st = mid+1;
        }
        else
        {
            en = mid-1;
        }
        mid = (st) + (en - st)/2;
    }
    if(wt+3*(nm+mid)>=n && wt+2*(nm+mid)<=n)
    {
            return mid;
     }
    return 0;
}
bool my(pair<ll, char> p1, pair<ll, char> p2)
{
    return p1.first > p2.first;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll h[n+1];
    map<ll,ll> m;
    ll ans = 0;
    REP(i,1,n+1)
    {
        cin>>h[i];
        ans+=m[i-h[i]];
        m[h[i]+i]++;
    }
    cout<<ans<<"\n";
    return 0;
}


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

const int mod = 1000000007;

// K の桁数
int N;
int D;

// K の上から n 桁目 (0-indexed)
int K[10009];

int dp[10009][2][109];

int main() {
    // K は文字列として受け取る
    string s;
    cin >> s;
    N = s.size();
    for(int i = 0; i < N; i++)
        K[i] = s[i] - '0';

    cin >> D;

    dp[0][0][0] = 1;

    for(int i = 0; i < N; i++) {
        for(int d = 0; d < D; d++) {
            // j = 1 -> j = 1
            for(int k = 0; k <= 9; k++)
                if((dp[i + 1][1][(d + k) % D] += dp[i][1][d]) >= mod)
                    dp[i + 1][1][(d + k) % D] -= mod;
            // j = 0 -> j = 1
            for(int k = 0; k < K[i]; k++)
                if((dp[i + 1][1][(d + k) % D] += dp[i][0][d]) >= mod)
                    dp[i + 1][1][(d + k) % D] -= mod;
            // j = 0 -> j = 0
            if((dp[i + 1][0][(d + K[i]) % D] += dp[i][0][d]) >= mod)
                dp[i + 1][0][(d + K[i]) % D] -= mod;
        }
    }

    // 0 が含まれているので、1 引く
    int res = dp[N][0][0] + dp[N][1][0] - 1;
    if(res >= mod) res -= mod;
    if(res < 0) res += mod;
    cout << res << endl;

    return 0;
}


Measured memory_bytes: 8832
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m;
  
  cin >> n >> m;
  
  vector<int> a(m+10);
  
  for(int i = 1; i < m+1; i++) cin >> a[i];
  
  int sum = 0;
  
  for(int i = 1; i < m + 1; i++) sum += a[i];
  
  while(1){
    
    if(sum > n){
      cout << -1 << endl;
      break;
    }else{
      cout << n - sum << endl;
      break;
    }
  }
}


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

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define rep(i,n) FOR (i,0,n)
#define int long long
#define vi vector<int>
#define pb(a) push_back(a)

signed main () {
	int n, m, p; cin >> n >> m >> p;
	vector<int> D;
	rep (i, m) {
		int d; cin >> d;
		d -= p;
		if (d < 0) d += n;
		D.pb(d);
	}
	sort(D.begin(), D.end());
	int an = 10000000;
	
	rep (i, D.size()-1) {
		int now = D[i], nxt = D[i+1];
		int tmp = n - (nxt-now);
		tmp += min(now, n - (nxt));
		an = min(an, tmp);
	}

	int tmp = n - (D[0] + n - D.back());
	tmp += min(D[0], n - D.back());
	an = min(an, tmp);


	cout << an * 100 << endl;
}


Measured memory_bytes: 3252
#include <stdio.h>
#include <algorithm>
#include <functional>
int main(void){
	int N;
	int a[100];
	int res=0;
	scanf("%d",&N);
	for(int i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	std::sort(a,a+N,std::greater<int>());
	for(int i=0;i<N;i++){
		if(i % 2 == 0){
			res += a[i];
		}else{
			res -= a[i];
		}
	}
	printf("%d\n",res);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
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;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    string s;
    cin >> s;
    string ans;
    REPS(c, s) {
        if (c != 'B') {
            ans += c;
        } else {
            if (sz(ans)) ans = ans.substr(0, sz(ans) - 1);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#import<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
main(){int a[5];rep(i,5) std::cin>>a[i];int k;std::cin>>k;int m=0;rep(i,5)rep(j,5) if(abs(a[i]-a[j])>k)m++;std::cout<<(m>0?":(":"Yay!");}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void c_p_c(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int maxHappiness(int arr[][3],int n){
	int dp[n][3];
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];
	for(int i=1;i<n;i++){
		dp[i][0] = arr[i][0] + max(dp[i-1][1],dp[i-1][2]);
		dp[i][1] = arr[i][1] + max(dp[i-1][0],dp[i-1][2]);
		dp[i][2] = arr[i][2] + max(dp[i-1][0],dp[i-1][1]);
	}
	return max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}
int main()
{
	c_p_c();
	int n;
	cin>>n;
	int arr[n][3];
	for(int i=0;i<n;i++)
		for(int j=0;j<3;j++)
			cin>>arr[i][j];
	cout<<maxHappiness(arr,n);
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <list>
#include <math.h>
#include <algorithm>
#include <functional>
#include <string>
#include <iomanip>
#include <queue>
#include <map>
#include <unordered_map>
typedef long long ll;
using namespace std;

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

//	cout << s.length();

	int count =0 ;
	for(int i=0; i<s.length(); i++){
		if(s[i]=='1'){
			count++;
		}
	}

	cout << count << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N,K;
	cin >> N;
	char S[100];
	for (int i = 0; i < N; i++)	{cin >> S[i];}
	cin >> K;
	for (int i = 0; i < N; i++)
	{
		if (S[i]!=S[K-1]) {S[i] = '*';}
	}
	for (int i = 0; i < N; i++)	{cout << S[i];}
}


Measured memory_bytes: 256
#include <iostream>
#include <stdlib.h>
#include <utility>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <string.h>
#define   FOR(i,n) for(int i=0;i<n;i++)
#define INF 10000000000
using namespace std;
int int_sort(const void*a,const void *b) {
	return *(  int *) b - *(int *) a;
	//qsort(b, a, sizeof(long long int), int_sort);
}

template<typename T>
istream& operator >>(istream& is, vector<T>& vec){
	for(T& x: vec) is >>x;
	return is;
}
int main() {
	int N;
	cin >> N;
	std::vector<long> A(1000000);
	long max=0,max_flag=0,min=INF,min_flag=0;
	long sum=0;
	FOR(i, N)
		cin >> A[i];

	while(true) {
		sum=0;
		FOR(i, N) {
			sum += A[i];
			if (max < A[i]) {
				max_flag = i;

			}
			if (min >= A[i] && A[i] != 0) {
				min = A[i];
				min_flag = i;
			}
		}
		FOR(i,N){
			if(i!=min_flag)
			A[i]=A[i]%min;
		}
		max=min;
		max_flag=min_flag;
		//cout<<sum<<" "<<min<<endl;
		if(sum==min){
			cout<<min<<endl;
			return 0;
		}
	}

	return 0;

}




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


int main(){
  int s,a[10000000],flag=0,i=1,ans,memo[10000000];
  cin >> s;
  a[0]=s;
  memo[0]=s;
  while(flag==0){
    if(a[i-1]%2==0){
      a[i]=a[i-1]/2;
      memo[i]=a[i];
    }else{
      a[i]=a[i-1]*3+1;
      memo[i]=a[i];
    }
    for(int j=0;j<i;j++){
      if(memo[j]==a[i]){
        flag=1;
        ans=i+1;
      }
    }
    i++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2304
/*
(1)for binary shift operator always use 'LL' 1LL<<63

*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll M=2e6+1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll s,w;cin>>s>>w;
	if(s>w)
		cout<<"safe";
	else cout<<"unsafe";
	cout<<endl;
	return 0;
} 

Measured memory_bytes: 3608
N,K=map(int,input().strip().split())
A=list(map(int,input().strip().split()))

i=A.index(1)+1
if i<=K or i>=N-K:
    ans=(N-K)//(K-1)+1 if (N-K)%(K-1)==0 else (N-K)//(K-1)+2
else:
    for a in range(K):
        if (i-a)%(K-1)==0 and (N-(i+(K-a)))%(K-1)==0:
            b=0
        else:
            b=1
    front=i//(K-1)
    back=(N-(i+K))//(K-1)
    ans=front+back+1+b
print(ans)

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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef pair<int, int> p;

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<int>> vv(n,vector<int>());
  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int vsize;
    cin >> vsize;
    for (int j = 0; j < vsize; j++) {
      int tmp;
      cin >> tmp;
      mp[tmp]++;
      vv[i].push_back(tmp);
    }
  }

  int res = 0;
  for(auto a : mp){
    if(a.second == n) res++;
  }

  cout << res << endl;
}


Measured memory_bytes: 256
s = input()

y, m, d = s.split("/")

if(int(y) < 2019):
    print("Heisei")
    exit()
elif(int(y) == 2019):
    if(int(m) < 4):
        print("Heisei")
        exit()
    elif(int(m) == 4):
        if(int(d) <= 30):
            print("Heisei")
            exit()

print("TBD")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <unordered_set>
#include <stdio.h>

using namespace std;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define PI 3.141592653589793
#define vi vector<int>
#define vll vector<long long>
#define p pair<int,int>
const int MOD = 1000000007;
inline double degcos(double ang) {return cos(ang*PI/180);}
inline double degsin(double ang) {return sin(ang*PI/180);}
#define rep(i,j,k,in) for (int i = j; i < k; i += in)


/*---END OF TEMPLATE---*/
vector<int> in[100005],out[100005];
int dist[100005];


int dfs(int node) {
    int d = 0;
    rep(i,0,out[node].size(),1) {
        if (dist[out[node][i]] == -1) {
            d = max(d,1+dfs(out[node][i]));
        }
        else {
            d = max(d,1+dist[out[node][i]]);
        }
    }
    return dist[node] = d;
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    //ifstream fin("data.in");
    //ofstream fout("data.out");
    rep(i,0,100005,1) dist[i] = -1;
    int n,m;
    cin >> n >> m;
    int sta,fin;
    rep(i,0,m,1) {
        cin >> sta >> fin;
        out[sta].push_back(fin);
        in[fin].push_back(sta);
    }
    vector<int> startNodes;
    rep(i,1,n+1,1) {
        if (out[i].size() > 0 && in[i].size() == 0) {
            startNodes.push_back(i);
        }
    }


    int mx = -1;

    for (int startNode : startNodes) {
        if (mx < dfs(startNode)) mx = dfs(startNode);
    }
    cout << mx << endl;

    



}

Measured memory_bytes: 19548
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
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;}
typedef long long ll;
typedef pair<int,int> pii;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    ll ans = 0;
    for(int i = 0; i*i <= N; ++i){
        ans = i*i;
    }
    cout << ans << '\n';
    return 0;
}

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

int main()
{
    int n, q, time_sum = 0;
    cin >> n >> q;
    queue<string> name;
    queue<int> time;
    vector<string> answer_n;
    vector<int> answer_t;
    for (int i = 0; i < n; i++)
    {
        string name_tmp;
        int time_tmp;
        cin >> name_tmp >> time_tmp;
        name.push(name_tmp);
        time.push(time_tmp);
    }
    while (time.size() != 0)
    {
        if (time.front() > q)
        {
            time_sum += q;
            time.push(time.front() - q);
            time.pop();
            name.push(name.front());
            name.pop();
        }
        else
        {
            time_sum += time.front();
            time.pop();
            answer_n.push_back(name.front());
            name.pop();
            answer_t.push_back(time_sum);
        }
        //        cout << time.front() << " " << name.front() << " " << time_sum << endl;
    }
    for (int i = 0; i < n; i++)
    {
        cout << answer_n.at(i) << " " << answer_t.at(i) << endl;
    }
    return 0;
}



Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
typedef long long Int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
double PI = acos(-1);  // PI = 3.141593...

int main() {
    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double a_s = (double)h*30 + 0.5* m;
    double b_s = (double)m * 6;
    //cout << a_s << " " << b_s << endl;
    double kakudo = max(a_s, b_s) - min(a_s, b_s);
    //cout << "long=" << max(a_s, b_s) << endl;
    //cout << "short=" << min(a_s, b_s) << endl;
    //cout << "before kakudo=" << kakudo << endl;
    if (kakudo > 180.0) kakudo = (double)360-kakudo;
    //cout << "after kakudo=" << kakudo << endl;

    double  rad = kakudo * PI / 180;
    double ans = (double)(b*b) + (a*a) - ((2*a*b)*cos(rad));
    ans = sqrt(ans);
    printf("%.12f\n", ans);

}


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

typedef long long ll;
typedef pair<ll, ll> P;
const int mod = 1e9 + 7;
ll N, X;
vector<ll> a, p;

ll f(ll n, ll x) {
    if (n == 0) {
        if (x <= 0) {
            return 0;
        } else {
            return 1;
        }
    } else if (x <= 1 + a[n - 1]) {
        return f(n - 1, x - 1);
    } else {
        return p[n - 1] + 1 + f(n - 1, x - 2 - a[n - 1]);
    }

}

int main() {
    cin >> N >> X;
    a.push_back(1);
    p.push_back(1);

    rep(i, N) {
        a.push_back(a[i] * 2 + 3);
        p.push_back(p[i] * 2 + 1);
    }

    cout << f(N, X) << endl;
}

Measured memory_bytes: 256
n = int(input())
F = [[int(x) for x in input().split()] for i in range(n)]
P = [[int(x) for x in input().split()] for i in range(n)]
res = -10**12
for bit in range(1, 2 ** 10):
    cc = 0
    for i in range(n):
        cc += P[i][sum([(F[i][j]==1 and (1 & (bit >> j))==True) for j in range(10)])]
    res = max(res, cc)
print(res)


Measured memory_bytes: 3064
N,K=map(int,input().split())
D=[0]*(K+1)
ans=0
mod=10**9+7
for i in range(K,0,-1):
  D[i]=(pow(K//i,N,mod)-sum(D[i::i]))%mod
  ans+=(D[i]*i)%mod
  ans%=mod
print(ans)

Measured memory_bytes: 12048
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
#define int long long int
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll m = 998244353;
/*ll power(ll x, ll y) 
{ 
    ll res = 1;
    x = x % MOD;
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % MOD;
            y = y>>1; 
        x = (x*x) % MOD;   
    } 
    return res; 
} */
ll mod(ll x)
{
	if(x<0)
	return -x;
	else
	return x;
}
signed main()
{
 read(n);readarr(h,n);
 int dp[n+1]={0};
 dp[2]=mod(h[2]-h[1]);
 FOR(i,3,n)
 {
  dp[i]=min(dp[i-1]+mod(h[i]-h[i-1]),dp[i-2]+mod(h[i]-h[i-2])); 	
 }	
 cout<<dp[n]<<endl;
}

Measured memory_bytes: 1920
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
constexpr long long LINF = 1000100010001000100LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i, j, n) for(int i=(j); i<(n); i++)
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() { 
    int n, x; cin >> n >> x;
    vector<ll> A(n); rep(i, n) cin >> A[i];
    A.push_back(x);
    sort(all(A));
    
    ll res = A[1]-A[0];
    fo(i, 1, A.size()-1){
        ll dist = A[i+1] - A[i];
        res = __gcd(res, dist);
    }
    cout << res << ln;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define MAX 52

int n;
int a;
vector<int> v;

long long int dp[MAX][MAX][MAX*MAX];
int main(){
	cin >> n>>a;
	int sum = 0;
	for (int i = 0; i < n; i++){
		int x;
		scanf("%d", &x);
		v.push_back(x);
		sum += v[i];
	}
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j <= i; j++){
			for (int k = 0; k <= sum; k++){
				if (dp[i][j][k]){
					dp[i + 1][j][k] += dp[i][j][k];
					dp[i + 1][j + 1][k + v[i]] += dp[i][j][k];
				}
			}
		}
	}
	long long int way = 0;
	for (int i = 1; i <= n; i++){
		way += dp[n][i][i*a];
	}
	printf("%lld\n", way);
	return 0;
}
//A

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

struct Edge {
    int to, cost;
};

vector<Edge> G[100010];
int dist[100010];

void dfs(int idx, int par) {
    for(auto &e : G[idx]) {
        if(e.to == par) continue;
        dfs(e.to, idx);
        dist[idx] = max(dist[idx], dist[e.to] + e.cost);
    }
}

int dfs2(int idx, int d_par, int par) {
    vector<pii> rec;
    rec.push_back(pii(0, -1));
    for(auto &e : G[idx]) {
        if(e.to == par) rec.push_back(pii(d_par + e.cost, e.to));
        else rec.push_back(pii(dist[e.to] + e.cost, e.to));
    }
    sort(rec.rbegin(), rec.rend());
    int ret = rec[0].first + rec[1].first;
    for(auto &e : G[idx]) {
        if(e.to == par) continue;
        ret = max(ret, dfs2(e.to, rec[ rec[0].second == e.to ].first, idx));
    }
    return ret;
}

signed main() {
    int n; cin >> n;
    rep(i,0,n-1) {
        int s, t, w; cin >> s >> t >> w;
        G[s].push_back(Edge{t, w});
        G[t].push_back(Edge{s, w});
    }
    dfs(0, -1);
    cout << dfs2(0, 0, -1) << endl;
}

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

int main() {
  int a, s = 0;
  cin >> a;
  
  for (int i = 2; i >= 0; i--) {
    s += a / (int)pow(10, i);
    a = a % (int)pow(10, i);
  }
  
  cout << s << endl;
}


Measured memory_bytes: 640
#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 FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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 (a>b) { a=b; return 1; } return 0; }

struct UnionFind {
public:
  vector<ll> par; 
  vector<ll> siz; 

    
  UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
    for (ll i = 0; i < sz_; ++i) par[i] = i; 
  }
  void init(ll sz_) {
    par.resize(sz_);
    siz.resize(sz_, 1);
    for (ll i = 0; i < sz_; ++i) par[i] = i;
  }

  ll root(ll x) { 
    while (par[x] != x) {
      x = par[x] = par[par[x]];
    }
    return x;
  }

  bool merge(ll x, ll y) {
    x = root(x);
    y = root(y);
    if (x == y) return false;
    if (siz[x] < siz[y]) swap(x, y);
    siz[x] += siz[y];
    par[y] = x;
    return true;
  }

  bool issame(ll x, ll y) {
    return root(x) == root(y);
  }

  ll size(ll x) {
    return siz[root(x)];
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a[m];
  rep(i, n) {
    int k;
    cin >> k;
    rep(j, k) {
      int l;
      cin >> l;
      a[l - 1].push_back(i);
    }
  }

  UnionFind uf(n);
  rep(i, m) {
    if (a[i].size() <= 1) continue;
    rep(j, a[i].size() - 1) {
      if (!uf.issame(a[i][j], a[i][j + 1])) uf.merge(a[i][j], a[i][j + 1]);
    }
  }
  cout << (uf.size(0) == n ? "YES" : "NO") << endl;


  
  return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < static_cast<int>(n); ++i)
#define per(i, n) for(int i = static_cast<int>(n)-1; i >= 0; --i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);
#define ppp(a) (cout << (a) << endl); 
#define cop(a) for(auto x:(a)){cout << x << endl;}

using ll = long long;

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

constexpr char sp = ' ';
constexpr ll MOD = 1e9+7;
constexpr ll Mod = 998244353;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr double phi = (1+sqrt(5))/2;
constexpr double pi = 3.14159265358979323846264338327950288;
inline ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
inline ll inverse(ll n, ll m=MOD){ll a=n,b=m,x=1,y=0;while(b){ll t=a/b;a-=t*b;swap(a,b);x-=t*y;swap(x,y);}return (a%m+m)%m;}
inline void Yes(){puts("Yes");}
inline void No(){puts("No");}
inline void Judge(bool b){b?Yes():No();}
inline void YES(){puts("YES");}
inline void NO(){puts("NO");}
inline void JUDGE(bool b){b?YES():NO();}
inline ll powmod(ll b, ll e, ll m=MOD){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
inline double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
inline double d2r(double d){return d*pi/180;}
inline double r2d(double r){return r*180/pi;}

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; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s<<'[';for(size_t i=0;i<v.size();++i){s << v[i];if(i < v.size()-1) s << ", ";}s<<']';return s;
}
struct __{ __(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15); } };



int dp[10101];

int main(){

    int h, n;
    cin >> h >> n;
    vector<int> a(n), b(n);

    for(int i = 0; i < n; ++i) cin >> a[i] >> b[i];

    fill_n(dp, 10101, INF);
    dp[0] = 0;

    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= h; ++j){
            int x = 0;
            if(j-a[i] >= 0) x = dp[j-a[i]];
            dp[j] = min(dp[j], x+b[i]);
        }
    }
    cout << dp[h] << '\n';
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int N,K,x=1,i;
	scanf("%d",&N);
	scanf("%d",&K);
	for(i=1;i<=N;i++){
		if(x*2>=x+K) x+=K;
		else         x*=2;
	}
	printf("%d\n",x);
	return 0;
}

Measured memory_bytes: 128
#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 FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  int sx,sy,tx,ty;
  cin >> sx >> sy >> tx >> ty;
  int difx = tx-sx;
  int dify = ty-sy;
  REP(i,difx){
    cout << "R";
  }
  REP(i,dify){
    cout << "U";
  }
  REP(i,difx){
    cout << "L";
  }
  REP(i,dify){
    cout << "D";
  }
  cout << "D";
  REP(i,difx+1){
    cout << "R";
  }
  REP(i,dify+1){
    cout << "U";
  }
  cout << "L";
  cout << "U";
  REP(i,difx+1){
    cout << "L";
  }
  REP(i,dify+1){
    cout << "D";
  }
  cout << "R" << endl;
}

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

void display(int A[], int n)
{
	for(int i = 1; i <= n; i++)
	{
		cout << A[i];
		if(i < n)
		{
			cout << " ";
		}
	}
	cout << endl;
}

int main(void)
{
	int N = 1000;
	int n;
	int A[N];

	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> A[i];
	}

	for(int j = 1; j <= n; j++)
	{
		int v = A[j];
		int k = j-1;
		while(k >= 1 && A[k] > v)
		{
			A[k+1] = A[k];
			k--;
		}
		A[k+1] = v;
		display(A, n);
	}
	return 0;
}

Measured memory_bytes: 3064