akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#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, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */



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

	LL A, B; cin >> A >> B;
	LL ans = (A%3==0||B%3==0||(A+B)%3==0);
	cout<<(ans?"Possible":"Impossible")<<endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 405
#define endl "\n"
#define mod 1000000007
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
ll n,ar[N]; ll dp[N][N];
ll minval(ll st,ll ed){
	if(st==ed)
		return 0;
	//cout<<st<<" "<<ed<<endl;
	if(dp[st][ed]!=-1){
		return dp[st][ed];
	}
	ll i,mn=1e18;
	for(i=st;i<ed;i++){
		mn=min(mn,minval(st,i)+minval(i+1,ed));
	}
	for(i=st;i<=ed;i++){
		mn+=ar[i];
	}
	return dp[st][ed]=mn;
}
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l;
	cin>>n;

	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
	memset(dp,-1,sizeof(dp));
	k=minval(1,n);
	cout<<k;
	return 0;
}

Measured memory_bytes: 1792
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int X = sc.nextInt();
    int T = sc.nextInt();
    if (N % X == 0) {
      System.out.println(N / X * T);
    } else {
      int min = (int)(N / X) + 1;
      System.out.println(min * T);
    }
  }
}


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

int main() {
  int a,b,c;cin>>a>>b>>c;
  if (c>=a && c <= b) cout << "Yes";
  else cout << "No";
}


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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod =(1e9)+7;
using P = pair<ll,ll>;

int main(){
    ll n;cin >>n;
    vector<ll>x(n),y(n),h(n);
    ll k=-1;
    for (int i = 0; i < n; ++i) {
        cin >>x[i]>>y[i]>>h[i];
        if(h[i]>0)k=i;
    }
    ll ax,ay,ah;
    for (int cx = 0; cx <=100 ; ++cx) {
        for (int cy = 0; cy <=100; ++cy) {
            ll H;bool flg=true;
            H=h[k]+abs(x[k]-cx)+abs(y[k]-cy);
            for (int i = 0; i < n; ++i) {
                ll tmp=max(H-abs(x[i]-cx)-abs(y[i]-cy),0LL);
                if(tmp!=h[i]){
                    flg=false;
                    break;
                }
            }
            if(flg){
                ax=cx;ay=cy;ah=H;
            }
        }
    }
    cout <<ax<<" "<<ay<< " "<<ah <<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  vector<string> s = {"Sunny", "Cloudy", "Rainy"};
  string t;
  cin >> t;
  REP(i, SZ(s)) {
    if (s[i] == t) {
      cout << s[(i + 1) % SZ(s)] << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	String s =sc.next();
      	int t = 0;	
     	for(int i = 0; i < 4; i++){
        	if(s.charAt(i) == '+') t++;
          	else t--;
        }
      	System.out.println(t);
    }
}

Measured memory_bytes: 35712
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n,l;
    cin >> n >> l;

    int sum = 0;
    for(int i=1; i<=n; i++){
        sum+=l+i-1;
    }
    // cout << sum << endl;
    int mi = 1e9;
    int ans = 0;
    for(int i=1; i<=n; i++){
        int tmp = 0;
        for(int j=1; j<=n; j++){
            if(i!=j) tmp+=l+j-1;
        }
        // cout << "this case " << tmp << endl;
        if(abs(tmp-sum) < mi) {
            mi = abs(tmp-sum);
            ans = tmp;
        }
    }

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

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(long long i=0; i<(n); 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; }


int main(){
    string t; cin>>t;
    string res = "";
    rep(i, t.size()){
        if(t[i]=='?'){
            res.push_back('D');
        }else{
            res.push_back(t[i]);
        }
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 3852
#include <iostream>

using namespace std;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if (a==b ){
        cout<<c<<endl;
    }
    if(a==c){
        cout<<b<<endl;
    }
    if(b==c){cout<<a<<endl;}
    return 0;
}


Measured memory_bytes: 256
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

class WeightUnionFindTree
    attr_accessor:par,:rank,:weight
    def initialize(n)
        @par=Array.new(n){|i| i}
        @rank=array(n,0)
        @weight=array(n,0)
    end

    def find(x)
        return x if @par[x]==x
        y=find(@par[x])
        @weight[x]+=@weight[@par[x]]
        @par[x]=y
        return y
    end

    def union(x,y,w)
        rx=find(x)
        ry=find(y)
        if @rank[rx]<@rank[ry]
            @par[rx]=ry
            @weight[rx]=w-@weight[x]+@weight[y]
        else
            @par[ry]=rx
            @weight[ry]=-w-@weight[y]+@weight[x]
            @rank[rx]+=1 if @rank[rx]==@rank[ry]
        end
    end

    def same?(x,y)
        return find(x)==find(y)
    end

    def diff(x,y)
        return @weight[x]-@weight[y]
    end
end

N,M=get_i
wuft=WeightUnionFindTree.new(N)
flag=true
M.times do
  l,r,d=get_i
  l-=1
  r-=1
  if wuft.same?(l,r) and wuft.diff(l,r)!=d
    flag=false
    break
  else
      wuft.union(l,r,d)
  end
end
puts yn_judge(flag)

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t,a,b;
	t = 1;
	while(t--) {
	 cin >> a >> b;
	 cout << 2 * b - a << endl;
	}
	return 0;
}



Measured memory_bytes: 256
<?php
$val = fgets(STDIN);
$val2 = explode(" ", fgets(STDIN));
$flag = 0;
for($i=0;$i<1000;$i++){
    $x = $i * $val;
    if($val2[1] < $x) break;
    if($x <= $val2[1] && $val2[0] <= $x) $flag++;
}
if($flag != 0)
    echo "OK";
else
    echo "NG";

Measured memory_bytes: 16208
#include <stdio.h>
#include <math.h>
using namespace std;
int main(){
	int n;
	double students[1000] = {0},sum,m,div;
	while(true){
		scanf("%d",&n);
		if(n == 0) break;
		div = sum = 0;
		for(int i = 0; i < n; i++){
			scanf("%lf",&students[i]);
			sum += students[i];
		}
		m = sum/n;
		for(int i = 0; i < n;i++){
			div += (students[i] - m)*(students[i] - m);
			students[i] = 0;
		}
		printf("%.8lf\n",sqrt(div/n));
	}
}



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

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

    if (n%2!=0){
        cout << "No" << endl;
    } else {
        int point = n / 2;
        if (s.substr(0, point) == s.substr(point, point)){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

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

using namespace std;

using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n >> m;
    cout << (n*(m-1) %m==0 ? -1 : (n*(m-1))) << endl;
}

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

using namespace std;

int main(int argc, char* argv[]) {
  string s;
  cin >> s;

  set<char> q;
  for (int i = 0; i < s.size(); ++i)
    q.insert(s[i]);

  if (s == "zyxwvutsrqponmlkjihgfedcba") {
    cout << -1 << endl;
  }

  if (s.size() == 26) {
    vector<char> past;
    for (int i = 25; i >= 0; --i) {
      int tmp = 1000;
      int tmp_index = 0;
      for (int j = 0; j < past.size(); ++j) {
        if (s[i] < past[j] && past[j] < tmp) {
          tmp = past[j];
        }
      }
      if (tmp != 1000) {
        s[i] = (char)tmp;
        cout << s.substr(0, i + 1) << endl;
        return 0;
      } else {
        past.push_back(s[i]);
      }
    }
  } else {
    for (char c = 'a'; c <= 'z'; ++c) {
      if (q.find(c) == q.end()) {
        s += c;
        cout << s << endl;
        return 0;
      }
    }
  }

  return 0;
}

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

void f(int& a, int& b){
    if(a & 1){
        --a;
    }
    b += a/2;
    a /= 2;
}

int main()
{
    int A, B, K;
    cin >> A >> B >> K;

    while(K > 0){
        f(A, B);
        --K;
        if(K == 0) break;
        f(B, A);
        --K;
    }
    
    cout << A << " " << B << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}

typedef vector<ll> vec;
typedef vector<vec> mat;

ll MOD;

void print_mat(mat A){
	for(int i=0;i<A.size();i++){
		for(int j=0;j<A[i].size();j++){
			cout << A[i][j] << ' ';
		}
		cout << endl;
	}
}

mat mul(mat &A,mat &B){
	assert(A[0].size()==B.size());
	mat C(A.size(),vec(B[0].size()));
	for(int i=0;i<A.size();i++){
		for(int k=0;k<B.size();k++){
			for(int j=0;j<B[0].size();j++){
				C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MOD;
			}
		}
	}
	return C;
}

mat pow(mat A, ll n){
	assert(A.size()==A[0].size());
	mat B(A.size(),vec(A.size()));
	for(int i=0;i<A.size();i++){
		B[i][i]=1ll;
	}
	while(n>0){
		if(n&1)B = mul(B,A);
		A = mul(A,A);
		n >>= 1;
	}
	return B;
}

ll pow(ll a,ll n){
	ll res = 1ll;
	a %= MOD;
	while(n>0){
		if(n&1)res = (res*a)%MOD;
		a = (a*a)%MOD;
		n >>= 1;
	}
	return res;
}

// 1 1 2 3 5 8 ...
ll fib(ll x){
	mat A(2,vec(2));
	A[0][0]=1;A[0][1]=1;A[1][0]=1;A[1][1]=0;
	A = pow(A,x);
	return A[1][0];
}


ll L,A,B,M;
ll k[25];
ll rui[25];
int main(){
	cin >> L >> A >> B >> M;
	MOD = M;
	rui[0]=1ll;
	for(int i=1;i<=18;i++)rui[i]=rui[i-1]*10ll;
	for(int i=1;i<=18;i++){
		ll l = -1, r = L;
		while(r-l>1ll){
			ll mid = (l+r)/2;
			if(A+mid*B<rui[i-1])l=mid;
			else r=mid;
		}
		k[i]=r;
		//cout << i << ' ' << r << endl;
	}
	k[19]=L;
	k[20]=L;
	/*for(int i=18;i>=1;i--){
		krui[i] = ((i*((k[i+1]-k[i])%M))%M);
	}
	for(int i=1;i<=18;i++){
		//cout << i << ' ' << krui[i] << endl;
	} */

	ll ans = 0ll;
	ll ret = 1ll;
	for(int i=18;i>=1;i--){
		//if(k[i]==k[i+1])continue;
		mat S(3,vec(3));
		S[0][0]=rui[i]%MOD;S[0][1]=1;S[0][2]=0;
		S[1][0]=0;S[1][1]=1;S[1][2]=B%MOD;
		S[2][0]=0;S[2][1]=0;S[2][2]=1;
		mat v(3,vec(1));
		v[0][0]=0ll;
		v[1][0]=(A+B*k[i])%MOD;
		v[2][0]=1ll;
		ll n = k[i+1]-k[i];
		mat ruiS = pow(S,n);
		mat res = mul(ruiS,v);
		for(int j=0;j<i+1;j++){
			//i+1
			ret = (ret*pow(10ll,k[i+2]-k[i+1]))%MOD;
		}
		//cout << res[0][0] << ' ' << ret << endl;
		ans = (ans+((res[0][0]*ret)%MOD))%MOD;
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main(){
    long long n, k;
    cin >> n >> k;
    vector<double> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    vector<double> expectedValues(n);
    expectedValues[0] = (p[0] + 1) / 2;
    for(long long i = 1; i < n; i++){
        expectedValues[i] = expectedValues[i - 1] + (p[i] + 1) / 2;
    }
    double ans = expectedValues[k - 1];
    for(long long i = 0; i < n - k; i++){
        ans = max(ans, expectedValues[k + i] - expectedValues[i]);
    }

    cout << fixed << setprecision(12) << ans << endl;
}

Measured memory_bytes: 3328
X, K, D = map(int, input().split())

n_min = abs(X // D)
n_remains = (K - n_min)

if n_remains < 0:
    print(min(abs(X - K * D), abs(X + K * D)))
elif n_remains % 2 == 0:
    print(abs(X % D))
else:
    print(abs(abs(X % D) - D))

Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x),end(x)
#define sz(x) ((int)(x).size())
#define F(i,n) for (int i = 0; i < n; ++i)
#define mp make_pair
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

template<typename T>
ostream& operator <<(ostream &s, const vector<T> &c) {
  s<<"[ "; for (auto it : c) s << it << " "; s<<"\b]\n";
  return s;
}

int main () {
	//ios_base::sync_with_stdio(0); cin.tie(0)
	int a, b, c; cin >> a >> b >> c;
	map<pair<int, int>, map<int, bool>> meow;
	int ans = 0;
	while (true) {
		if (meow[mp(a, b)][c]) {
			cout << "-1\n"; return 0;
		}
		meow[mp(a, b)][c] = true;
		if ((a & 1) || (b & 1) || (c & 1)) break;
	  int d = a, e = b, f = c;
	  a = (e + f) >> 1;
	  b = (f + d) >> 1;
	  c = (d + e) >> 1;
	  ++ans;
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#pragma comment(linker, "/STACK:400000000")

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(it=X.begin();it!=X.end();it++)
#define iss istringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sst stringstream
#define sz size()
#define vc vector
typedef vc<int> vi;
typedef vc<ll> vl;
typedef vc<string> vs;

int N;
string mark[10010];
int used[10010],nex[10010];
map<string,int> M;
vi ans;

void read(int cur){
	if(used[cur])return;
	ans.pb(cur);
	used[cur]=1;
	if(nex[cur]!=-1)read(nex[cur]);
}

int main(){
	while(cin>>N && N){
		rep(i,N)cin>>mark[i];
		fill(used,used+N,0);
		fill(nex,nex+N,-1);
		M.clear();
		ans.clear();
		
		rep(i,N){
			if(mark[i]=="-"){
				read(i);
			}else if(mark[i]=="v"){
				nex[i+1]=i;
			}else{
				string type;
				int number=0;
				int x=0;
				while(islower(mark[i][x])){
					type+=mark[i][x];
					x++;
				}
				while(x<mark[i].sz && isdigit(mark[i][x])){
					number=number*10+mark[i][x]-'0';
					x++;
				}
				if(M.find(type)!=M.end()){
					nex[i]=M[type];
				}
				if(number>1)M[type]=i;
				else M.erase(type);
				if(x<mark[i].sz)nex[i+1]=i;
				else if(number==1)read(i);
			}
		}
		
		rep(i,N)cout<<ans[i]+1<<endl;
	}
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
int main(){
    string s;
    cin >> s;
    bool ans = true;
    if(s.size() % 2 == 0){
        rep(i,s.size()){
            if(s[i] != 'h' || s[i+1] != 'i'){
                ans = false;
                break;
            }
            i++;
        }
    }
    else ans = false;
    cout << (ans? "Yes" : "No") << endl;
    return 0;
}

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

using namespace std;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

typedef long long int64;
const int INF = 1 << 30;

int64 N, R, s, t;
int64 a[100000], b[100000];
UnionFind tree(100000);
int64 ret[100000];

void ask(int v)
{
  map< int, vector< pair< int64, int > > > backet;
  for(int i = 0; i < N; i++) {
    backet[a[i]].push_back(make_pair(b[i], i));
  }
  for(auto &obj : backet) {
    sort(begin(obj.second), end(obj.second));
  }
  for(int i = 0; i < N; i++) {
    auto &cc = backet[a[i] - R];
    auto p = lower_bound(begin(cc), end(cc), make_pair(b[i] - R - v, +INF));
    auto q = lower_bound(begin(cc), end(cc), make_pair(b[i] + R + v, -INF));
    ret[i] += q - p;
    if(p != q) tree.unite(i, p->second);
  }
  for(int i = 0; i < N; i++) {
    auto &cc = backet[a[i] + R];
    auto p = lower_bound(begin(cc), end(cc), make_pair(b[i] - R - v, +INF));
    auto q = lower_bound(begin(cc), end(cc), make_pair(b[i] + R + v, -INF));
    ret[i] += q - p;
    if(p != q) tree.unite(i, p->second);
  }
}

int main()
{
  cin >> N >> s >> t;
  for(int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    a[i] = x + y;
    b[i] = x - y;
  }
  --s, --t;
  R = max(abs(a[s] - a[t]), abs(b[s] - b[t]));
  ask(false);
  for(int i = 0; i < N; i++) swap(a[i], b[i]);
  ask(true);
  long long res = 0;
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == tree.find(s)) res += ret[i];
  }
  cout << res / 2 << endl;
}

Measured memory_bytes: 29148
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

const int INF = 1e+8;
// d[k][y] := ビル k(k は 0 or 1), 位置 y の最短ジャンプの回数
int d[2][101] = {0};

int move(int y, vector<int>& v){
	if( v[y] == 0 ){
		return y;
	}else if( v[y] == 1 ){
		if( y == v.size()-1 ){
			return y;
		}else if( v[y+1] == 1 ){
			return move(y+1,v);
		}else{
			return y;
		}
	}else if( v[y] == 2 ){
		return move(y-1,v);
	}
	return y;
}

int bfs(vector<int>& a, vector<int>& b, int n){
	// 初期化
	for(int i=0 ; i < 101 ; i++ ){
		d[0][i] = d[1][i] = INF;
	}
	// (ビル,位置)を保持
	queue<P> q;
	q.push(P(0,0));
	q.push(P(1,0));
	d[0][0] = d[1][0] = 0;
	
	while( !q.empty() ){
		int k = q.front().first;
		int y = q.front().second;
		int cnt = d[k][y];
		q.pop();
		
		// y を次のジャンプの位置に更新
		y = k? move(y,b) : move(y,a) ;
		
		// ゴールの時
		if( y == n-1 ) return cnt;
		
		for(int i=0 ; i < 3 ; i++ ){
			int y_ = y + i;
			if( n <= y_ ) y_ = n-1;
			if( d[k^1][y_] == INF ){
				d[k^1][y_] = cnt+1;
				q.push( P(k^1,y_) );
			}
		}
	}
	return -1;
}

int main(){
	int n;
	while( cin >> n , n ){
		vector<int> a(n), b(n);
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		for(int i=0 ; i < n ; i++ ){
			cin >> b[i];
		}
		int ans = bfs(a,b,n);
		if( ans == -1 )
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
}

Measured memory_bytes: 1200
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 {

	public static void main(String[] args) throws Exception {
		FastScanner scanner = new FastScanner(System.in);
		int N = (int) scanner.nextInt();
		int M = (int) scanner.nextInt();
		PrintWriter printWriter = new PrintWriter(System.out);
		printWriter.println((int)Math.pow(2,M)*(1900*M+(N-M)*100));
		printWriter.close();
	}

	static class FastScanner {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;

		public FastScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			tokenizer = null;
		}

		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					return reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}

			return tokenizer.nextToken("\n");
		}

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

		public long nextInt() {
			return Integer.parseInt(next());
		}

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

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = (int) nextInt();
			return a;
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
	}
}

Measured memory_bytes: 21460
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x),putchar(' ');}
inline void pr2(int x){write(x),puts("");}
char ss[500010];
int s[500010];
inline int getdig(int x)
{
	int tot=0;
	while(x){tot+=x%10,x/=10;}
	return tot;
}
int main()
{
    //freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%s",ss+1);int n=strlen(ss+1);
	for(int i=1;i<=n;i++)s[i]=(ss[i]-'0')*9;
	int sum=0,now=ss[n]-'0',ans;
	for(int i=n;i>=1;i--){s[i-1]+=s[i]/10;s[i]%=10,sum+=s[i];}
	sum+=getdig(s[0]);
	s[n]+=now,sum+=now;
	while(1)
	{
		sum-=getdig(s[0]);
		for(int i=n;i>=1;i--)
		{
			if(s[i]>9)
			{
				sum-=s[i];
				s[i-1]+=s[i]/10,sum+=s[i]/10;s[i]%=10;
				sum+=s[i];
			}
			else break;
		}sum+=getdig(s[0]);
		if(sum<=now){ans=now;break;}
		now+=10,s[n]+=10,sum+=10;
	}pr2(ceil(1.0*ans/9));
	return 0;
}

Measured memory_bytes: 2560
#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>;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  int Q;
  cin >> Q;

  map<int,int> count;
  ll S = 0;
  for (int a: A) {
    count[a]++;
    S += a;
  }
  rep(i,Q) {
    int B, C;
    cin >> B >> C;
    S = S + (-B + C) * count[B];
    cout << S << endl;
    count[C] += count[B];
    count[B] = 0;
  }

  return 0;
}

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

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define FILE "parade"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int INF = numeric_limits<int>::max();
const ll LLINF = numeric_limits<ll>::max();
const ull ULLINF = numeric_limits<ull>::max();
const double PI = acos(-1.0);

ll f(ll b, ll n)
{
    if(n < b)
        return n;
    return f(b, n / b) + n % b;
}

int main()
{
//    freopen(FILE".in", "r", stdin);
//    freopen(FILE".out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, s;
    cin >> n >> s;
    ll ans = -1;
    for(ll i = 2; i * i <= n; i++)
    {
        if(f(i, n) == s)
        {
            cout << i;
            return 0;
        }
    }
    if(n == s)
    {
        cout << n + 1;
        return 0;
    }
    for(ll i = 1; i * i <= (n - s); i++)
    {
        if((n - s) % i == 0)
        {
            ll d = (n - s) / i + 1;
            if(f(d, n) == s)
                ans = d;
        }
    }
    cout << ans;
    return 0;
}


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

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

int main() {

    string s; cin >> s;

    int q; cin >> q;

    int rev_count = 0;

    string mae;
    string ato;

    for (int i = 0; i < q; ++i) {
        int t; cin >> t;

        if (t == 1) {
            ++rev_count;
        } else {
            int f; string c;
            cin >> f >> c;

            if (f == 1) {
                if (rev_count % 2 == 0) {
                    mae = c + mae;
                } else {
                    ato = ato + c;
                }
            } else {
                if (rev_count % 2 == 0) {
                    ato = ato + c;
                } else {
                    mae = c + mae;
                }
            }
        }
    }

    s = mae + s + ato;

    if (rev_count % 2 == 0) {
        cout << s << endl;
    } else {
        for (int i = 0; i < s.size(); ++i) {
            cout << s[s.size() - i - 1];
        }

        cout << endl;
    }
}

Measured memory_bytes: 1512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc090_b
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);
            int sum = 0;
            for(int i = a; i <= b; i++)
            {
                string word = i.ToString();
                if (word.Substring(0,1)==word.Substring(4,1)&&word.Substring(1,1)==word.Substring(3,1))
                {
                    sum++;
                }
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 15184
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

int main(){
	IO_STREAM;
	int X,Y;	cin>>X>>Y;
	cout<<(X+Y/2)<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include <cstdio>  
#include <string>  
#include <cstring>  
#include <cmath>  
#include <iostream>   
#include <algorithm>  
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 500;
int a[maxn],b[maxn];
int main() {
	int n;
	while (~scanf("%d", &n))
	{
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		memset(b, 0, sizeof(b));
		for (int i = 1; i <= n; i++)
			b[i] = abs(a[i] - a[i - 1]) + b[i - 1];
		//for (int i = 1; i <= n; i++)
		//	cout << b[i] << " ";
		//cout << endl;
		for (int i = 1; i < n; i++)
			printf("%d\n", abs(0 - a[n]) + abs(a[i+1] - a[i-1]) + b[n]-b[i+1]+b[i - 1]);
		printf("%d\n", abs(0 - a[n-1]) + b[n - 1]);
	}
	return 0;
}


Measured memory_bytes: 2048
from math import log
n = int(input())


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


yakusu_list = make_divisors(n)
ans_list = []
# print(yakusu_list)
ans = 0
for r in yakusu_list:
    if r == 1:
        continue
    if len(factorization(r)) == 1 and n % r == 0:
        n //= r
        ans += 1
        ans_list.append(r)
    if n == 1:
        break
# print(ans_list)
print(ans)



Measured memory_bytes: 9560
A,B=map(int,input().split())
C=1
D=A
E=B
if A<=B:
    if B%A==0:
        print(B)
    else:
        for k in range(2,int(B**(1/2)+2)):
            if A%k==0 and B%k==0:
                A=A/k
                B=B/k
                C=int(A*E)
                while True:
                    if A%k==0 and B%k==0:
                        A=A/k
                        B=B/k
                        C=int(A*E)
                    else:
                        break
        if C==1:
            C=int(A*B)
        print(C)
else:
    if A%B==0:
        print(A)
    else:
        for k in range(2,int(A**(1/2)+2)):
            if A%k==0 and B%k==0:
                A=A/k
                B=B/k
                C=int(D*B)
                while True:
                    if A%k==0 and B%k==0:
                        A=A/k
                        B=B/k
                        C=int(D*B)
                    else:
                        break
        if C==1:
            C=int(A*B)
        print(C)

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

#define MAX 100100

using namespace std;

int main(){
    vector<int> map[MAX];
    vector<int> value;
    int n, m;
    int count = 0;
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        int t;
        cin >> t;
        value.push_back(t);
    }
    while(m--){
        int a, b;
        cin >> a >> b;
        map[a - 1].push_back(b - 1);
        map[b - 1].push_back(a - 1);
    }

    for(int i = 0;i < n;i++){
        if(!map[i].size()) count++;
    }

    while(n--){
        bool flag = true;
        if(map[n].size()){
            for(auto &x:map[n]){
                if(value[n] <= value[x]){
                    flag = false;
                    map[n].clear();
                    break;
                }else{
                    map[x].clear();
                }
             }
            if(flag == true)count++;
        }
    }
    cout << count << endl;
    return 0;
}



Measured memory_bytes: 8780
from itertools import accumulate

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = [0] + list(accumulate(p))
mx = 0
mx_n = 0
for i in range(len(c)-k):
    if mx < c[i+k] - c[i]:
        mx = c[i+k] - c[i]
        mx_n = i
ans = 0
for i in range(k):
    ans += (p[mx_n + i] + 1) / 2

print(ans)



Measured memory_bytes: 25152
#include<stdio.h>

int main(void)


{


int a,b,c;


int count=0;


int i;


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


for(i=a;i<=b;i++)


{


if(c%i==0) count++;


}


printf("%d\n",count);


return 0;


}

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

const long long oo = 1e18;

using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j]);
        }
    }
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    string res;
    while (1) {
        // cout << n << " "  << m << endl;
        if (n < 1 || m < 1) {
            break;
        }
        if (dp[n][m] == dp[n-1][m]) {
            n--;
        } else {
            if (dp[n][m] == dp[n][m-1]) {
                m--;
            } else {
                if (dp[n][m] == dp[n-1][m-1] + 1) {
                    n--;
                    m--;
                    res += s[n];
                }
            }   
        }
    }
    for (int i = res.size() - 1; i >= 0; i--) {
        cout << res[i];
    }
}

int main() {
    #ifdef DEBUG
        freopen("solve.inp", "r", stdin);
        freopen("solve.out", "w", stdout);
    #endif
    solve();
    return 0;
}   

Measured memory_bytes: 35584
/* 
 * Author: aps
 * Time: 2020-01-26 21:57:22
**/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
using namespace __gnu_pbds;
using namespace std;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
 
const ll inf = 1e18;
const ll mod = 1e9+7;
 
inline ll add(ll x, ll y) { x += y; if (x >= mod) x -= mod; return x;}
inline ll sub(ll x, ll y) { x -= y; if (x < 0) x += mod; return x;}
inline ll mul(ll x, ll y) { return ((x % mod) * (y % mod)) % mod;}
inline ll gcd(ll x, ll y) { return x == 0 ? y : gcd(y % x, x); }
inline ll power(ll a, ll b) {
    ll x = 1;
    while (b) {
        if (b & 1) x = mul(x, a);
        a = mul(a, a);
        b >>= 1;
    }
    return x;
}
inline ll inv(ll a) { return power(a, mod - 2);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll h; cin >> h;
    ll ans = 0, val = 1LL;
    while(h) {
        ans += val;
        val *= 2;
        h /= 2;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int a[10];
int num;
bool fl=false;

int main()
{
  
  for (int i(1); i<=3; i++) 
  {
    cin >> num;
    if (a[num]==1) 
    	fl=true;
    else if (a[num]==2)
      		fl=false;
    a[num]++;
  }
  if (fl) cout <<"Yes";
  else		cout <<"No";
  return 0;
}
    

Measured memory_bytes: 256
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, q = map(int, readline().split())
    cum = [[0] * 502 for _ in range(502)]

    for _ in range(m):
        l, r = map(int, readline().split())
        cum[l][r] += 1

    ans = [[0] * 502 for _ in range(502)]

    for i in range(1, 501):
        for j in range(1, 501):
            ans[i][j] = ans[i][j - 1] + cum[i][j]

    for i in range(500, 0, -1):
        for j in range(1, 501):
            ans[i][j] += ans[i + 1][j]

    for _ in range(q):
        l, r = map(int, readline().split())
        print(ans[l][r])


if __name__ == '__main__':
    main()


Measured memory_bytes: 54108
#include <stdio.h>

int main(void) {
	int h,w;
	int x,y;
	while(1){
	scanf("%d",&h);
	scanf("%d",&w);
	if(h==0 && w==0){
		break;
	}
	for(y=0;y<h;y++){
		for(x=0;x<w;x++){
			if((x+y)%2==0){
				printf("#");
			}else{
				printf(".");
			}
		}
		printf("\n");
	}
	printf("\n");
	}
	return 0;
}

Measured memory_bytes: 572
main :: IO ()
main = do
  n <- readLn :: IO Int
  k <- readLn :: IO Int
  print $ solve n k

solve :: Int -> Int -> Int
solve n k = go n 1
  where
    go i j
      | i == 0 = j
      | j >= k = go (i-1) (k+j)
      | otherwise = go (i-1) (2 * j)
        


Measured memory_bytes: 508
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define FIND(x, target) find(x.begin(),x.end(),target)
#define pb(x) push_back(x)
#define output(x) cout<<x<<endl
#define ERASE(x, n) x.erase(x.begin(), x.begin()+n)
// #define int long long
#define P pair<int, int>
typedef long long ll;

const long long int MOD = 1e9+7;
const int INF = -1;

signed main(void) {
  	int N;
  	cin >> N;
  	vector<int> A;
  	int ans = 0;

  	rep(i, N) {
  		int tmp;
  		cin >> tmp;
  		if (tmp != i+1) {
  			ans++;
  		}
  		A.pb(tmp);
  	}

  	if (ans <= 2) {
  		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.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
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);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int lr[][] = new int[n][2];
            for (int i = 0; i < n; i++) {
                lr[i][0] = Integer.parseInt(in.next());
                lr[i][1] = Integer.parseInt(in.next());
            }
            long ans = 0;

            for (int i = 0; i < n; i++) {
                ans += lr[i][1] - lr[i][0] + 1;
            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 22996
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define file(x)freopen(x".in","r",stdin);freopen(x".out","w",stdout)
#define rt register int
#define l putchar('\n')
#define ll long long
#define r read()
using namespace std;
inline ll read(){
    ll x=0;char zf=1;char ch=getchar();
    while(ch!='-'&&!isdigit(ch))ch=getchar();
    if(ch=='-')zf=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;
}
void write(ll y){if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
int a[200010],num[200010],sta[200010],top;
bool check(int x){
	memset(num,0,sizeof(num));
	for(rt i=1;i<=min(n+1,a[1]);i++)num[i]=1;top=0;
	for(rt i=2;i<=n;i++)if(a[i]<=n+1){
		int pl=a[i];num[pl]++;
		while(num[pl]>=x){
			if(pl==1)return 0;
			num[pl]=1,num[pl-1]++;
			pl--;
		}
		while(top&&sta[top]>a[i]){
			num[sta[top]]=0;
			top--;
		}
		sta[++top]=a[i];
	}
	return 1;
}
int main(){
	n=r;bool fla=1;
	for(rt i=1;i<=n;i++){
		a[i]=r;
		if(i>1&&a[i]<=a[i-1])fla=0;
	}
	if(fla)return cout<<1,0;
	int L=2,R=n;
	while(L<=R){
		const int mid=L+R>>1;
		if(check(mid+1))ans=mid,R=mid-1;
		else L=mid+1;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

bool cmp(P x, P y){return x.second<y.second;}

int main(){
        ll n, m;
        scanf("%lld %lld", &n, &m);
        vector<P> ab(m);
        for(int i=0; i<m; i++) scanf("%lld %lld", &ab[i].first, &ab[i].second);
        sort(ab.begin(), ab.end(), cmp);

        ll ans = 0, h = -1;
        for(P tpl: ab){
                ll a = tpl.first-1, b = tpl.second-1;
                if(h<a){
                        h = b-1;
                        ans ++;
                }
        }
        printf("%lld\n", ans);
        return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
const int N = 100006;

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

    vector<int> a(n);
    for(int &x : a) cin >> x;

    sort(a.begin(), a.end());
    
    ll ans = 0;

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(a[i] + a[j] > a[k] && a[i] != a[j] && a[j] != a[k] && a[i] != a[k]) {
                    ans++;
                    // cout << a[i] << ' ' << a[j] << ' ' << a[k] << '\n';
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

// 


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;cin>>s;
if(s=="RRR")cout<<3<<endl;
if(s=="RRS")cout<<2<<endl;
if(s=="SRR")cout<<2<<endl;
if(s=="RSR")cout<<1<<endl;
if(s=="RSS")cout<<1<<endl;
if(s=="SSR")cout<<1<<endl;
if(s=="SSS")cout<<0<<endl;
if(s=="SRS")cout<<1<<endl;
}

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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

int sum(int x){
    int res=0;
    while(x){
        res+=x%10;
        x/=10;
    }
    return res;
}

void solve(){
    int N;
    cin >> N;

    int ans=inf;
    rep(A,1,N){
        ans=min(ans,sum(A)+sum(N-A));
    }

    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 256
from math import factorial
# int(input()) # 入力が1つ
n, m = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
mod = 10 ** 9 + 7

if abs(n - m) > 1:
    ans = 0
else:
    ans = factorial(n) * factorial(m) % mod
    if n == m:
        ans = ans * 2 % mod
print(ans)

Measured memory_bytes: 54768
# ABC 165 D - Floor Function
# https://atcoder.jp/contests/abc165/tasks/abc165_d

a, b, n = gets.split(/ /).map(&:to_i)

def calc(a, b, x)
  x_per_b = x * 1.0 / b
  (a * x_per_b).floor - a * x_per_b.floor
end

if n < b
  puts calc(a, b, n)
elsif a > b
  puts (0..(b - 1)).map { |x| calc(a, b, x) }.max
else
  puts a - 1
end


Measured memory_bytes: 14328
N, M = map(int, input().split())
line = []

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
first = set()
second = set()

for l in line:
    if end in l:
        second.add(l[0])
        second.add(l[1])
    elif start in l:
        first.add(l[1])
        first.add(l[0])


for f in first:
    if f in second:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Measured memory_bytes: 58904
#include <stdio.h>
#include <math.h>
int main(int argc, const char * argv[])
{
    int x[10000],i=0,c;
for(c=0;c<10000;c++){
x[c]=0;
}
   while(1){
      scanf("%d",&x[i]);
      if(x[i]==0){
         break;
      }
      i++;
   }
   i=0;
   while(1){
     if(x[i]==0){
         break;
     }
     printf("Case %d: %d\n",i+1,x[i]);
     i++;
   }
    return 0;
}

Measured memory_bytes: 636
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if(abs(a-b)<=d&&abs(b-c)<=d)cout<<"Yes"<<endl;
	else if(abs(a-c)<=d)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
using ll = long long;
using vll = vector<long long>;
using vvll = vector<vll>;
const double EPS = 1e-9;
const long long MOD=1e9+7;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define SZ(x) ((int)(x).size())
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; }

int main(){
  int n; cin>>n;
  stringstream ss;
  rep(i,n){
    ss << "ACL";
  }
  cout<<ss.str()<<endl;
}

Measured memory_bytes: 3632