akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
char arr[1005][1005];
int r,c,ans,dis[1005][1005];
int x[]={1,-1,0,0};
int y[]={0,0,-1,1};
pair<int,int> now;
queue <pair<int,int> > q;
void bfs(){
	while(!q.empty()){
		now=q.front();
		q.pop();
		for(int i =0;i<=3;i++){
			int nextx=now.fi+x[i];
			int nexty=now.se+y[i];
			if(dis[nextx][nexty]>dis[now.fi][now.se]+1){
				dis[nextx][nexty]=dis[now.fi][now.se]+1;
				q.push({nextx,nexty});
			}
		}
	}
}
int main(){
	cin>>r>>c;
	for(int i =1;i<=r;i++){
		for(int j=1;j<=c;j++){
			dis[i][j]=1e9;
		}
	}
	for(int i =1;i<=r;i++){
		for(int j =1;j<=c;j++){
			cin>>arr[i][j];
			if(arr[i][j]=='#'){
				dis[i][j]=0;
				q.push({i,j});
			}
		}
	}

	bfs();
	for(int i =1;i<=r;i++){
		for(int j=1;j<=c;j++){
			ans=max(ans,dis[i][j]);
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 13328
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
int main() {
  int n, x;
  cin >> n >> x;
  vector<ll> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  a.push_back(x);
  sort(a.begin(), a.end());

  ll d = 1001001001;
  for(int i = 1; i <= n; i++) {
    ll tmp = a[i] - a[i - 1];
    d = min(d, tmp);
    ll r = tmp % d;
    while(r != 0) {
      tmp = d;
      d = r;
      r = tmp % d;
    }
  }
  cout << d << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>
#include <math.h>

struct vertex{
	int x;
	int y;
};

double areaTriangle(vertex p1, vertex p2, vertex p3)
{
	double vec1_x = p2.x - p1.x, vec1_y = p2.y - p1.y;
	double vec2_x = p3.x - p1.x, vec2_y = p3.y - p1.y;
	
	return (vec1_x * vec2_y - vec1_y * vec2_x) / 2;
}

int main(void)
{
	int cnt = 0;
	int n;
	vertex p[50];
	
	double area;
	
	while(1){
		scanf("%d", &n);
		if(n == 0) break;
		
		for(int i = 0; i < n; i++){
			scanf("%d %d", &p[i].x, &p[i].y);
		}
		
		area = 0;
		for(int i = 1; i+1 < n; i++){
			area += areaTriangle(p[0], p[i], p[i+1]);
		}
		area = fabs(area);
		
		cnt++;
		printf("%d %.1f\n", cnt, area);
	}
	
	return 0;
}

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

int main() {
    int h,w;
    cin>>h>>w;
    string board[50];
    for (int i=0; i<h; i++) {cin>>board[i];}

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

        for(int i=0; i<h; i++){
            for(int j =0; j<w; j++){
                if(board[i][j]=='#')continue;

                int num =0;
                for (int d =0; d<8; d++){
                    const int ni =i+ dy[d];
                    const int nj = j+ dx[d];

                    if (ni<0 or h<=ni) continue;
                    if (ni<0 or w<=nj) continue;
                    if (board[ni][nj]=='#') num++;

                }

                board[i][j] = char(num +'0'); 
            }
        }

        for(int i =0; i<h; i++ ) cout << board[i] << endl;

}


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

using namespace std;

int main(){
  int n,i,j,a,b,c,aa=0,bb=0,cc=0,ans = 0,ma;
  string s;
  cin >> a >> b >> c;
  if(a%2==0)aa=1;
  if(b%2==0)bb=1;
  if(c%2==0)cc=1;
  if(aa+bb+cc==1){
    if(aa==1){
      b++;
      c++;
    }
    if(bb==1){
      a++;
      c++;
    }
    if(cc==1){
      b++;
      a++;
    }
    ans++;
  }
  if(aa+bb+cc==2){
    if(aa==0){
      b++;
      c++;
    }
    if(bb==0){
      a++;
      c++;
    }
    if(cc==0){
      b++;
      a++;
    }
    ans++;
  }
  ma = max(a,max(b,c));
  ans+=(ma-a)/2;
  ans+=(ma-b)/2;
  ans+=(ma-c)/2;
  cout << ans << endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> l(N), r(N);
  for (int i = 0; i < N; i++) {
    cin >> l[i] >> r[i];
  }

  int ans = 0;

  for (int i = 0; i < N; i++) {
    ans += r[i] - l[i] + 1;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n;
	cin>>n;
	int t[n],dp[n];
	for(int i=0;i<n;i++){
		cin>>t[i];
	}
	dp[0]=0,dp[1]=abs(t[1]-t[0]);
	for(int i=2;i<n;i++)
		dp[i]=min(dp[i-1]+abs(t[i]-t[i-1]),dp[i-2]+abs(t[i-2]-t[i]));
	cout<<dp[n-1];
}


Measured memory_bytes: 4324
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = getInt(sc.nextLine());

        // エラトステネスの篩
        // https://gist.github.com/greymd/19ed7f18c0eba7e703ac2a6b69225ca8
        boolean[] isPrime = new boolean[100000];
        IntStream.rangeClosed(2, 100000)
                .filter(i -> IntStream.rangeClosed(2, (int)Math.sqrt(i)).allMatch(j -> i%j !=0))
                .forEach(x -> isPrime[x] = true);

        // 1〜その数までで2017に近い数の個数リストを作る
        int[] list = new int[100000];
        int count = 0;
        for (int i = 0;i < 100000;i++) {
            if(isPrime[i] && isPrime[(i+1)/2]) count++;
            list[i] = count;
        }

        // lからrまでの2017に近い数を出す
        for (int i = 0;i < n;i++){
            String[] line = sc.nextLine().split(" ");
            int l = Integer.parseInt(line[0]);
            int r = Integer.parseInt(line[1]);
            System.out.println(list[r] - list[l-1]);
        }
        sc.close();
    }
    static int getInt(String val) {
        return Integer.parseInt(val);
    }
}


Measured memory_bytes: 139976
T=int(input())
for i in range(T):
    n=[int(i) for i in input().split()]
    c=[i for i in input().split()]
    R=[[],[],[]]
    for i in range(9):
        if c[i]=="R":
            R[0].append(n[i])
        elif c[i]=="G":        
            R[1].append(n[i])
        else:
            R[2].append(n[i])
    y=1
    i=0
 #   print(R)
    while y>0 and i<3:
        l=len(R[i])
        if l%3!=0:
            y=0
        else:
            R[i].sort()
            s=l//3
            j=0
            while y>0 and s>0 and j<len(R[i])-2:
                if R[i][j]==R[i][j+1]:
                    if R[i][j+1]==R[i][j+2]:
                        for k in range(3):
                            R[i].pop(j)
                        s-=1
                    elif R[i][j+1]+1==R[i][j+2]:
                        k=j+3
                        while k<len(R[i]) and R[i][k]==R[i][j+2]:
                            k+=1
                        if k>=len(R[i]) or R[i][k]!=R[i][j+2]+1:
                            y=0
                        else:
                            R[i].pop(k)
                            R[i].pop(j+2)
                            R[i].pop(j)
                        s-=1
                    else:
                        y=0
                elif R[i][j]+1==R[i][j+1]:
                    k=j+2
                    while k<len(R[i]) and R[i][k]==R[i][j+1]:
                        k+=1
                    if k>=len(R[i]) or R[i][k]!=R[i][j+1]+1:
                        y=0
                    else:
                        R[i].pop(k)
                        R[i].pop(j+1)
                        R[i].pop(j)
                        s-=1
                else:
                    y=0
        i+=1
    print(y)


Measured memory_bytes: 5624
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
  int n;
  int x[1000], y[1000];
  double tmp, d1, d2, d3, dinf;

  d1 = d2 = d3 = dinf = 0;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x[i];
  for (int i = 0; i < n; i++) cin >> y[i];
  for (int i = 0; i < n; i++) {
    tmp = abs(x[i]-y[i]);
    d1 += tmp;
    d2 += tmp*tmp;
    d3 += tmp*tmp*tmp;
    dinf = max(tmp, dinf);
  }
  d2 = sqrt(d2);
  d3 = cbrt(d3);
  cout << setprecision(10);
  cout << d1 << endl;
  cout << d2 << endl;
  cout << d3 << endl;
  cout << dinf << endl;

  return 0;
}



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

long long MOD=1000000007;
long long expo(long long a,long long b){
	if(b==0)return 1;
	long long temp=expo(a,b/2);
	if(b%2==0)return (temp*temp)%MOD;
	return (((temp*temp)%MOD)*a)%MOD;
}

int main(){
	int n;
	scanf("%d",&n);
	long long x[n];
	for(int i=0;i<n;i++)scanf("%lld",&x[i]);
	long long fac[n];
	fac[0]=1;
	for(long long i=1;i<n;i++)fac[i]=(fac[i-1]*i)%MOD;
	long long p[n];
	for(int i=0;i<n;i++){
		if(i==0)p[i]=1;
		else p[i]=p[i-1]+expo(i+1,MOD-2);
		p[i]%=MOD;
	}
	long long ans=0;
	for(int i=0;i<n-1;i++){
		ans+=p[i]*(x[i+1]-x[i]);
		ans%=MOD;
	}
	printf("%lld",(((ans*fac[n-1])%MOD)+MOD)%MOD);
}

Measured memory_bytes: 2560
#include<stdio.h>


int main(){
  long long N,K;
  scanf("%lld %lld",&N,&K);
  if(N%K <= K-N%K){
    printf("%lld\n",N%K);
  }else{
    printf("%lld\n",K-N%K);
  }
  return 0;
}

Measured memory_bytes: 128
local n,k=io.read("n","n")
local h={}
for i=1,n do
    h[i]=io.read("n")
end

local INF=math.maxinteger
local dp={0}
for i=2,n do
    dp[i]=INF
end

for i=1,n do
    for j=1,k do
        if i+j<=n then
            dp[i+j]=math.min(dp[i+j],dp[i]+math.abs(h[i]-h[i+j]))
        end
    end
end
print(dp[n])

Measured memory_bytes: 6312
fact = [1]*500001

mod = 10**9 + 7

for i in range(1, 500001):
	fact[i] = fact[i-1]*i
	fact[i] %= mod


def nCr(n, r):
	global fact, mod
	if n < r:
		return 0
	return fact[n] * pow(fact[r]*fact[n-r], mod-2, mod)


n, m = map(int, input().split())
mult = fact[m] * pow(fact[m-n], mod-2, mod) % mod

a = 0
for i in range(0, n+1):
	add = nCr(n, i) * nCr(m-i, n-i) * fact[n-i] % mod
	if i%2 == 0:
		a += add
	else:
		a -= add

print(mult*a % mod)


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

int main(void){
	ll N,A,B,C,D,E;
	cin >> N >> A >> B >> C >> D >> E;
	
	ll min=A;
	if(B<min) min=B;
	if(C<min) min=C;
	if(D<min) min=D;
	if(E<min) min=E;
	
	cout << (N-1)/min+5;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
ls = []
for i in range(n):
    ls.append(int(input()))
ls.sort()
ls2 = []
for j in range(n - k + 1):
    a = ls[j + k - 1] -ls[j]
    ls2.append(a)
print(min(ls2))


Measured memory_bytes: 11288
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MP make_pair

inline int gn(){
    int s=0,f=1; 
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=s*10+ch-'0';ch = getchar();}
    return s*f;
}

inline ll gl(){
    ll s=0,f=1; 
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=s*10+ch-'0';ch = getchar();}
    return s*f;
}

const int N=2e5+100;

void solve(){
    int k=gn();
    int a=gn(),b=gn();
    if(a>b)swap(a,b);
    for(int i=a;i<=b;++i){
        if(i%k==0){
            puts("OK");
            return ;
        }
    }
    puts("NG");
}

int main(){
    // int t;
    // t=gn();
    // while(t--)
        solve();
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/


Measured memory_bytes: 3636
//
// Created by maze on 2019/09/15.
//

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int64)1e9
#define lp(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a); i < (b); i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

int main(void) {
    int s,t;
    cin>>s>>t;
    int p,q,m;
    cin>>p>>q>>m;
    int y;
    cin>>y;
    cout<<(s^t^y)<<endl;
}


Measured memory_bytes: 3108
X, Y = map(int, input().split())
ans = 0
if X == 1:
    ans+=300000
elif X == 2:
    ans+=200000
elif X == 3:
    ans+=100000
if Y == 1:
    ans+=300000
elif Y == 2:
    ans+=200000
elif Y == 3:
    ans+=100000
if X == 1 and Y == 1:
    ans+=400000
print(ans)


Measured memory_bytes: 38384
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

ll n,k;
vector<ll> Rank;
vector<ll> tmp;
vector<ll> sa;
string str;


bool less_cmp(ll a,const string &s){
    for(ll i=0;i<s.size();i++){
        if(i+a>=n){return true;}
        if(str[i+a]!=s[i]){return str[i+a]<s[i];}
    }
    return false;
}

bool equal_cmp(ll a,const string &s){
    for(ll i=0;i<s.size();i++){
        if(i+a>=n){return false;}
        if(str[i+a]!=s[i]){return false;}
    }
    return true;
}

bool cmp(ll i,ll j){
    if(Rank[i]!=Rank[j]){return Rank[i]<Rank[j];}
    return (i+k<=n?Rank[i+k]:-1)<(j+k<=n?Rank[j+k]:-1);
}

void build(const string &s){
    n=s.size();
    sa.resize(n+1);
    Rank.resize(n+1);
    tmp.resize(n+1);
    for(int i=0;i<=n;i++){
        sa[i]=i;
        Rank[i]=i<n?s[i]:-1;
    }
    for(k=1;k<=n;k<<=1){
        sort(sa.begin(),sa.end(),cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++){
            tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
        }
        for(int i=0;i<=n;i++){
            Rank[i]=tmp[i];
        }
    }
}


bool search(const string &s){
    ll l=0,r=n;
    while(r-l>=10){
        ll m=l+(r-l)/2;
        if(less_cmp(sa[m],s)){l=m+1;}
        else{r=m;}
    }
    for(ll i=l;i<=r;i++){
        if(equal_cmp(sa[i],s)){return true;}
    }
    return false;
}




int main(){
    cin>>str;
    build(str);
    /*
    cout<<endl;
    for(int i=0;i<=str.size();i++){
        cout<<i<<" "<<Rank[sa[i]]<<endl;
        for(ll t=sa[i];t<str.size();t++){cout<<str[t];}
        cout<<endl;
    }
     */
    ll q;
    cin>>q;
    while(q--){
        string p;
        cin>>p;
        cout<<search(p)<<endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 27448
import math
a, b, x = list(map(float, input().split()))
if x <= 0.5 * a * a * b:
    res = math.degrees(math.atan(2 * x / (a * b * b)))
elif x < a * a * b:
    res = math.degrees(math.atan(a / (2 * (b - x / a ** 2))))
else:
    res = 90.0
print(f'{90 - res:.7f}')


Measured memory_bytes: 9208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int arr[maxn];
int gcd(int a,int b){
    int c;
    while(b){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int main(){

    ios::sync_with_stdio(0);
    int n,k;
    cin>>n>>k;
    int ma=0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        ma=max(ma,arr[i]);
    }
    int ans=arr[0];
    for(int i=1;i<n;i++){
        ans=gcd(ans,arr[i]);
    }
    if(k%ans==0&&ma>=k){
        cout<<"POSSIBLE"<<endl;
    }
    else{
        cout<<"IMPOSSIBLE"<<endl;
    }
}


Measured memory_bytes: 640
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
hash = Hash.new(0)
a.each do |x|
  hash[x] += 1
end
cnt = 0
hash.each do |k,v|
  if v-k < 0
    cnt += v
  else
    cnt += v-k
  end
end
puts cnt

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

int main()
{
    ll N, K;
    cin >> N >> K;
    ll res = 0;
    for (ll i = K; i <= N + 1; i++)
    { // calculate over k.
        ll pattern = i * (2 * N - i + 1) / 2 - i * (i - 1) / 2 + 1;
        res = (res + pattern) % 1000000007;
    }
    cout << res;
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    vl a(n);
    vl rui(n+1);  // rui[i+1] : a[0]からa[i]までの和
    rep(i, n) {
        cin >> a[i];
        rui[i+1] = rui[i] + a[i];
    }

    vvl dp(n+1, vl(n+1));  // dp[L][R] : a[L],…,a[R-1]の状態からはじめて1匹にするためのコストの総和の最小値
    exrep(len, 2, n) {  // 区間の長さ(len = 1 のときdpの値は0)
        for(ll L = 0; L + len <= n; L++) {  // 区間[L,R)の左
            ll R = L + len;  // 区間[L,R)の右
            // まずa[L],…,a[x-1]を合成してcost1でスライム1を作る
            // 次にa[x],…,a[R-1]を合成してcost2でスライム2を作る
            ll u = INF;  // cost1 + cost2 の最小値
            exrep(x, L+1, R-1) {
                ll cost1 = dp[L][x];
                ll cost2 = dp[x][R];
                chmin(u, cost1 + cost2);
            }
            // 最後にスライム1とスライム2を合成してcost3でスライム3を作る
            ll cost3 = rui[R] - rui[L];  // スライム1の大きさ(rui[x] - rui[L]) + スライム2の大きさ(rui[R] - rui[x])
            dp[L][R] = u + cost3;
        }
    }

    out(dp[0][n]);
    re0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define rep(i,l,r) for(int i=l;i<r;i++)
#define bep(i,l,r) for(int i=l;i>=r;i--)
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define el '\n'
#define sz(s) s.size()
#define all(v) v.begin(),v.end()
#define mii map<int,int>
#define mr  make_pair

int mod = 1e9+7;
int inf = 1e18;
const int N = 3e5+5;
int powmod(int a,int b) {int res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
      int n,a,b;
      cin>>n>>a>>b;
      int x = n/(a+b);
      int y = n%(a+b);
      int ans = 0;
      ans+= x*a;
      if(y>=a)
        ans+=a;
      else
        ans+=y;
      cout<<ans<<el;


    }

    return 0;
}


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

#define rr(i, b)    for (int i = 0; i < int(b); i++)
#define vi(n, a) vector <int> a(n); rr(i, n) cin >> a[i]
#define pvec(a) rr(i, a.size()) cout << a[i] << " "; cout << endl
#define bug(x) cout << #x << " " << x << endl
#define ll long long
#define vii vector <int>

using namespace std;

vector<bool> visited;
vector<vii> graph;

void explore(int u) {
    visited[u] = true;
    for(int v : graph[u]) {
        if(!visited[v]) explore(v);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    visited = vector<bool> (n, 0);
    graph = vector<vii> (n);

    while(m--) {
        int u, v;
        cin >> u >> v;

        --u, --v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int counter = 0;

    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            explore(i);
            counter++;
        }
        //pvec(visited);
    }

    cout << counter - 1<< endl;

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

Measured memory_bytes: 9204
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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;
}

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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


int main(){
ll a,b,c,d,e,k;
cin>>a>>b>>c>>d>>e>>k;
if(max({a,b,c,d,e})-min({a,b,c,d,e})<=k){
    cout<<"Yay!"<<endl;
}else{
    cout<<":("<<endl;
}
}









Measured memory_bytes: 256
import { readFileSync } from 'fs'

function main(input: string) {
  const [[N, M], ...lines] = input.split('\n').map(v => v.split(' ').map(Number))

  const sorted = lines.slice().sort(([xa, _xb], [ya, _yb]) => xa - ya)

  let total = {
    amount: 0,
    qty: 0,
  }

  for (const [a, b] of sorted) {
    const qty = total.qty + b <= M ? b : M - total.qty
    const amount = a * qty

    total.amount += amount
    total.qty += qty

    if (total.qty >= M) break
  }

  console.log(total.amount)
}

main(readFileSync('/dev/stdin', 'utf8').trim())


Measured memory_bytes: 52012
#include <iostream>
using namespace std;
 
int main() {
  string s;
  cin >> s;
 
  int i, j;
  for(i=0; i<s.size(); i++) {
    if(s[i] == 'A') {
    break;
    }
  }
  for(j=s.size()-1; j>=0; j--) {
    if(s[j] == 'Z') {
    break;
    }
  }
 
  cout <<j-i+1 ;
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double EPS = 1e-10;
const int INF = 2147483647;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int a[] = { 11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381,1451,1471,1481,1511,1531,1571,1601,1621,1721,1741,1801,1811,1831,1861,1871,1901,1931,1951 };

int main()
{
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		if(i) cout << " " << a[i];
		else cout << a[i];
	}
	cout << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main(){
	int x,h;
	while(cin>>x>>h){
	if(x==0&&h==0)break;
		double S = (double)x*(double)x+4.0*(double)x*sqrt(((double)x/2)*((double)x/2)+(double)h*(double)h)/2.0;
		printf("%.6lf\n",S);
	}
	return 0;
}

Measured memory_bytes: 0
program apple
implicit none
integer::N,L,mi,miab,S,i
read(*,*)N,L
S=0
miab=10000
mi=0
do i=1,N
	S=S+L+i-1
    if(abs(L+i-1)<miab)then !絶対値の最小値のときの値を探す
    	miab=abs(L+i-1)
    	mi=L+i-1
    end if
end do
write(*,*)S-mi
end program apple

Measured memory_bytes: 256
/*
Author : Xinyuan
*/
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int  ll;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int nxt() {int x;scanf("%d", &x);return x;}


int main(){
    int s=nxt();
    int w=nxt();
    if(w>=s){
        printf("unsafe");
    } else{
        printf("safe");
    }
    return 0;
}



Measured memory_bytes: 3724
sx,sy,tx,ty = map(int,input().split())

x_diff = tx-sx
y_diff = ty-sy

up = 'U'*abs(y_diff)
down = 'D'*abs(y_diff)
left = 'L'*abs(x_diff)
right = 'R'*abs(x_diff)

ans = right+up+left+down
ans = ans+'DR'+right+up+'UL'+'UL'+left+down+'DR'

print(ans)

Measured memory_bytes: 62032
#include <bits/stdc++.h>
using namespace std;
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;
template <typename... Args> void dbg(Args &&... args) {
  using expander = int[];
  (void)expander{
      0,
      (static_cast<void>(void(cout << std::forward<Args>(args) << " ")), 0)...};
  cout << endl;
}
void gen() {
  exit(0);
}

int n;

void input() {
  scanf("%d", &n);
}

void solve() {
  if (n < 105) {
    printf("0\n");
  } else {
    int ans = 0;
    for (int i = 105; i <= n; i += 2) {
      int cur = 0;
      for (int j = 1; j <= i; j++) {
        if (i % j == 0)
          cur++;
      }
      if (cur == 8)
        ans++;
    }
    printf("%d\n", ans);
  }
}

int main() {
#ifdef DEBUG
  freopen("input", "r", stdin);
  // freopen("output", "w", stdout);
  // gen();
  while (!feof(stdin)) {
    input();
    solve();
    scanf(" ");
  }
#else
  input();
  solve();
#endif
  return 0;
}


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

const int MAX_N = 101;

int main() {
  while(1) {
    int N, T, H, L;
    int t[MAX_N], h[MAX_N];
    if(cin >> N >> T >> H >> L) ; else break;
    for(int i = 0; i < N; ++i) {
      cin >> t[i] >> h[i];
    }

    int p;
    int at, ah;
    for(p = 0, at = 0, ah = 0; ; p = (p+1)%N) {
      if(t[p]) {
        --t[p]; ++T; ++at;
        if(T > L) break;
      } else if(h[p]) {
        --h[p]; ++H; ++ah;
      } else {
        break;
      }

      int sum = at*10 + ah*100;
      if(sum >= 90) {
        int ot = (sum-90)/10;
        T -= ot; t[p] += ot;
        if(T < 0) break;
        at = ah = 0;
      }
    }
    cout << p+1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1164
#include<iostream>
#include<vector>
#include<utility>
template<typename iterator>
int partition(iterator first, iterator last, int p = 0 )
{
    iterator X = last - 1 ;
    int i = p - 1 ;
    for( iterator iter = first + p ; iter != last-1 ; ++iter )
    {
        if( *iter <= *X )
        {
            ++i ;
            std::swap( *iter, *(first+i) ) ;
        }
    }
    std::swap( *(first+i+1), *(last-1) ) ;
    return i+1 ;
}

int main()
{
    int n ;
    std::cin >> n ;
    std::vector<int> A(n) ;
    for( int i = 0 ; i < n ; ++i )
    {
        std::cin >> A.at(i) ;
    }

    int k = partition( A.begin(), A.end() ) ;

    for( int i = 0 ; i < n ; ++i )
    {
        if( i != 0 )
        {
            std::cout << " " ;
        }
        if( i == k )
        {
            std::cout << "[" << A.at(i) << "]" ;
            continue ;
        }
        std::cout << A.at(i) ;
    }
    std::cout << std::endl ;
}



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

int main(){
	int n, m;
	cin >> n >> m;
	string str;
	map<int, int> mp;
	for(int i = 0; i < n; ++i){
		cin >> str;
		for(int j = 0; j < m; ++j){
			if(str[j] == '#') ++ mp[i+j]; } }

	cout << (all_of(begin(mp), end(mp), [](const pair<int, int>& p){ return p.second == 1; }) ?
			"Possible" :
			"Impossible") << endl;

	return 0; }


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

main() {
    int A[5]; rep(i,5) cin >> A[i] ; int pos=100;
    int ans=0;
    rep(i,5){
        if(A[i]%10==0) ans+=A[i];
        else {ans+=((A[i]/10)+1)*10;
        pos=min(pos,A[i]%10);}
    }
    if(pos==100)cout << ans << endl;
    else cout << ans-(10-pos) << endl;
    return 0;
}

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

using namespace std;

const int maxn = 500010;

int n, p[maxn], ip[maxn], mx[maxn << 2], res[maxn], k, _;
int deg[maxn], l[maxn], e;

priority_queue<int> pq;

struct Edge {
	int v, x;
} E[maxn << 1];

void update(int p, int v, int l, int r, int rt) {
	mx[rt] = max(mx[rt], v);
	if (l == r) return;
	int m = (l + r) >> 1;
	if (p <= m) update(p, v, l, m, rt<<1);
	else update(p, v, m+1, r, rt<<1|1);
	mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
}

int query(int L, int R, int l, int r, int rt) {
	if (L <= l && r <= R) return mx[rt];
	int m = (l + r) >> 1;
	int ret = 0;
	if (L <= m) ret = max(ret, query(L, R, l, m, rt<<1));
	if (R > m) ret = max(ret, query(L, R, m+1, r, rt<<1|1));
	return ret;
}

inline void addEdge(int u, int v) {
	E[e].v = v, E[e].x = l[u], l[u] = e++;
}

int main() {
	memset(l, -1, sizeof(l));
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		ip[p[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		{
			int x = query(max(1, ip[i] - k + 1), ip[i], 1, n, 1);
			if (x) {
				addEdge(ip[i], ip[x]);
				++ deg[ip[x]];
			}
		}
		{
			int x = query(ip[i], min(n, ip[i] + k - 1), 1, n, 1);
			if (x) {
				addEdge(ip[i], ip[x]);
				++ deg[ip[x]];
			}
		}
		update(ip[i], i, 1, n, 1);
	}
	for (int i = 1; i <= n; i++) if (!deg[i]) pq.push(i);
	while (!pq.empty()) {
		int u = pq.top(); pq.pop();
		res[u] = n - (_ ++);
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			-- deg[v];
			if (!deg[v]) pq.push(v);
		}
	}
	for (int i = 1; i <= n; i++) printf("%d\n", res[i]);
	return 0;
}

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

static const ll MOD = 1000000007;

ll dp[100005][4][3];

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

  if(S[0]=='A' || S[0] == '?'){
    dp[0][0][0] = 1;
    dp[0][1][0] = 1;
  }
  if(S[0]=='B' || S[0] == '?'){
    dp[0][0][1] = 1;
  }
  if(S[0]=='C' || S[0] == '?'){
    dp[0][0][2] = 1;
  }
  REP(i,1,S.size()){
    rep(j,4){
      if(S[i] == 'A' || S[i] == '?'){
        dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2];
        dp[i][j][0] %= MOD;
      }
      if(S[i] == 'B' || S[i] == '?'){
        dp[i][j][1] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2];
        dp[i][j][1] %= MOD;
      }
      if(S[i] == 'C' || S[i] == '?'){
        dp[i][j][2] += dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2];
        dp[i][j][2] %= MOD;
      }
    }
    if(S[i] == 'A' || S[i] == '?'){
      dp[i][1][0] += dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2];
      dp[i][1][0] %= MOD;
    }
    if(S[i] == 'B' || S[i] == '?'){
      dp[i][2][1] += dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2];
      dp[i][2][1] %= MOD;
    }
    if(S[i] == 'C' || S[i] == '?'){
      dp[i][3][2] += dp[i-1][2][0] + dp[i-1][2][1] + dp[i-1][2][2];
      dp[i][3][2] %= MOD;
    }
  }

  /*
  rep(i,4){
    rep(k,3){
      rep(j,S.size()){
        cout << dp[j][i][k] << " ";
      }
      cout << endl;
    }

    cout << endl;
    cout << endl;
  }
   */
  ll ret = dp[S.size()-1][3][0] + dp[S.size()-1][3][1] + dp[S.size()-1][3][2];
  ret %= MOD;

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


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

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool same(int x, int y) { return root(x) == root(y); }

    void merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }

    int size(int x) { return -par[root(x)]; }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<set<int>> v(n);
    UnionFind uf(n);

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        v[a].insert(b);
        v[b].insert(a);
        uf.merge(a, b);
        cout << endl;
    }

    rep(i, k) {
        int c, d;
        cin >> c >> d;
        c--, d--;
        if (!uf.same(c, d)) continue;
        v[c].insert(d);
        v[d].insert(c);
    }

    rep(i, n) {
        cout << (uf.size(i) - 1) - v[i].size();
        if (i == n - 1)
            cout << endl;
        else
            cout << ' ';
    }

    return 0;
}


Measured memory_bytes: 26908
#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <assert.h>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <math.h>
#include <stack>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long int
#define db double
#define ldb long double
#define MOD 1000000007
#define Fi first
#define Se second
#define INF INT_MAX
#define NINF INT_MIN
#define L_INF LLONG_MAX
#define L_NINF LLONG_MIN
#define gc getchar
#define sz(x) (int)(x).size()
#define pii pair<int,int>
#define pll pair<ll,ll>

void fsscan(){ios_base::sync_with_stdio(false);cin.tie(NULL);}

void scani(int &x)
{
    register int c = gc();x = 0;int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}

int main()
{
    fsscan();
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    int v1,v2,v3,v4,v5;
    v1=a*x+b*y;
    if(x>y)
    {
        v2=(x-y)*a+2*c*(y);
    }
    else
    {
        v2=2*c*(y);
    }
    if(y>x)
    {
        v3=(y-x)*b+2*c*(x);
    }
    else
    {
        v3=2*c*(x);
    }
    v4=(2*c*max(x,y));
    //cout<<v1<<" "<<v2<<" "<<v3<<" "<<v4<<endl;
    cout<<min(v1,min(v2,min(v3,v4)));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=2e5+5;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;cin>>n;
    ll a[n];for(ll i=0;i<n;i++)cin>>a[i];
    if(a[0]!=0)return cout<<"-1" , 0;
    for(ll i=0;i<n-1;i++)if(a[i+1]-a[i]>1)return cout<<"-1" , 0;
    ll ans = 0;
    for(ll i=0;i<n;i++){
        if(a[i]==a[i-1]+1)ans++;
        else ans+=a[i];
    }
    cout<<ans;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;
typedef long long LL;
const int maxn = 200005;

LL f[100][27];char s[maxn];int n,k,pre[maxn];
LL sum1[27],sum2[27];
void solve(LL n,int t,LL *c) {
	if (n<=0) return ;
	if (t<=2) {
		for (int j=1;j<=n;j++)
			c[s[j]-'a']++;
		return ;
	}
	if (f[t][26]==n) {
		for (int j=0;j<26;j++)
			c[j]+=f[t][j];
		return ;
	}
	if (f[t-1][26]>=n) solve(n,t-1,c);
	else {
		for (int j=0;j<26;j++)
			c[j]+=f[t-1][j];
		solve(n-f[t-1][26],t-2,c);
	}
}
int main()
{
	#ifdef Amberframe
		freopen("arc077f.in","r",stdin);
		freopen("arc077f.out","w",stdout);
	#endif
	scanf("%s",s+1);n=strlen(s+1)>>1;
	for (int i=2;i<=n;i++) {
		int p=pre[i-1];
		while (p&&s[p+1]!=s[i]) p=pre[p];
		if (s[p+1]==s[i]) pre[i]=p+1;
	}
	k=n-pre[n];f[1][26]=n;f[2][26]=n+k;
	for (int i=1;i<=n;i++) f[1][s[i]-'a']++;
	for (int i=1;i<=n+k;i++) f[2][s[i]-'a']++;
	int o=2;
	for (int i=3;;i++) {
		for (int j=0;j<=26;j++)
			f[i][j]=f[i-1][j]+f[i-2][j];
		o=i;
		if (f[i][26]>1e18) break;
	}
	
	LL l,r;scanf("%lld %lld",&l,&r);
	solve(r,o,sum1);solve(l-1,o,sum2);
	for (int i=0;i<26;i++)
		printf("%lld ",sum1[i]-sum2[i]);
	return 0;
}

Measured memory_bytes: 896
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using namespace std;

int main() {
	int a, b;
	string s;
	cin >> a >> b >> s;
	bool ans1 = false;
	bool ans2 = false;
	if (s[a] == '-') {
		rep(i, a ) {
			if ( s[i]>='0'  && s[i] <= '9') {
				ans1 = true;
			}
		}
		REP(i, a+1, a+b+1) {
			if (s[i] >= '0' && s[i] <= '9') {
				ans2 = true;
			}
		}
	}
	string ans;
	if (ans1 && ans2) ans = "Yes";
	else ans = "No";
	cout << ans << endl;
} 

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

int main() {
  int64_t n;
  std::cin >> n;
  int64_t x = 0, y = 0, t = 0;

  for (int64_t i = 0; i < n; i++) {
    int64_t ti, xi, yi;
    std::cin >> ti >> xi >> yi;
    const auto dis = std::abs(xi - x) + std::abs(yi - y);
    const auto time = ti - t;
    if (dis <= time && (dis - time) % 2 == 0) {
      t = ti;
      x = xi;
      y = yi;
    } else {
      std::cout << "No" << std::endl;
      return 0;
    }
  }

  std::cout << "Yes" << std::endl;
  return 0;
}


Measured memory_bytes: 256
N = input()
n = int(N)
l = len(N)

if l == 1:
  print(n)
elif l == 2:
  print(9)
elif l == 3:
  print(n-90)
elif l == 4:
  print(909)
elif l == 5:
  print(n-9090)
else:
  print(90909)

Measured memory_bytes: 3060
/*************************************************************************
  > File Name: c.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Sat Apr  4 20:10:10 2020
*************************************************************************/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, k;
    cin >> n >> k;
    ll t = n - n / k * k;
    cout << min(t, -(t - k));
    return 0;
}


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

int main() 
{
    string s;
    unsigned long long k, i;
    cin >> s >> k;
    
    i = 0;

    while (i < s.length())
    {
        if (s[i] != '1')
        {
            cout << s[i] << endl;
            break;
        }
        else 
        {
            k -= 1;
            i++;
        }

        if (k == 0) 
        {
            cout << '1' << endl;
            break;
        }
    }
}

Measured memory_bytes: 384
/*  -*- coding: utf-8 -*-
 *
 * 2844.cc: Almost Infinite Glico
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 800;
const int MOD = 1000000007;

/* typedef */

typedef long long ll;
typedef int vec[MAX_N];

/* global variables */

vec av, bv, cv;
vec sv, tv;

/* subroutines */

inline void addmod(int &a, int b) { a = (a + b) % MOD; }

inline void initvec(const int n, vec a) {
  memset(a, 0, sizeof(vec));
}

inline void copyvec(const int n, const vec a, vec b) {
  memcpy(b, a, sizeof(vec));
}

inline void mulvec(const int n, const vec a, const vec b, vec c) {
  initvec(n, c);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      addmod(c[(i + j) % n], (ll)a[i] * b[j] % MOD);
}

/* main */

int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);

  initvec(n, av);
  av[0] = 1;
  for (int i = 0; i < m; i++) {
    int pi;
    scanf("%d", &pi);
    av[pi % n]++;
  }

  initvec(n, bv);
  bv[0] = 1;
  while (k > 0) {
    if (k & 1) {
      mulvec(n, bv, av, sv);
      copyvec(n, sv, bv);
    }

    mulvec(n, av, av, sv);
    copyvec(n, sv, av);
    k >>= 1;
  }

  for (int i = 0; i < n; i++) printf("%d\n", bv[i]);
  return 0;
}



Measured memory_bytes: 3244
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
typedef pair<ll,ll> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);
//ios::sync_with_stdio(false);

ll dp[100010];

void init(ll num){
    rep(i,num){
        dp[i]=-1;
    }
}

vector<vector<ll>> e(100010,vector<ll>(0));

ll solve(ll x){//与えられた場所から、更新済みか、行く先がない場所まで更新する
    if(dp[x]!=-1)return dp[x];

    ll res=0;
    rep(i,siz(e[x])){
        res=max(res,solve(e[x][i])+1);
    }

    dp[x]=res;

    return dp[x];
}

signed main(){
    ll n,m,ans=-1;cin>>n>>m;
    
    init(n+1);

    rep(i,m){
        ll x,y;cin>>x>>y;
        e.at(x).pb(y);
    }

    for(ll i=1;i <= n;i++)
    {
        ans=max(ans,solve(i));
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int N; cin >> N;
  vector<int> A(N);
  rep(i, N) cin >> A[i];
  
  int ans = 0;
  
  rep(i, N-1) {
    if(A[i+1] < A[i]) {
      ans += A[i] - A[i+1];
      A[i+1] = A[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 4772
#include <bits/stdc++.h>
#define sync                    \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0)
#define ss second
#define ff first
#define ll long long
#define mp make_pair
#define endl "\n"
#define pb push_back
#define ld long double
#define M_PI 3.14159265358979323846
#define puss vector
#define ull unsigned long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i >= (a); --i)
#define no {cout<<"NO";return 0;}
#define yes {cout<<"YES";return 0;}
const int MAXN=10000;
double EPS = 0.0000001;
const ll INF = 1000000007;
using namespace std;


int main(){
    int n,a,b;
    cin>>n>>a>>b;
    if (n==2){
        cout<<"Borys";
        return 0;
    }
    bool g=true;
    if (a<b){
        while (b-a>1){
            if (g) a++;
            else b--;
            g=!g;
        }
    }
    else{
        while (a-b>1){
            if (g) a--;
            else b++;
            g=!g;
        }
    }
    if (g)
        cout<<"Borys";
    else
        cout<<"Alice";
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

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

int main(){
    int n,a,g;
    cin>>n>>g;
    for(int i=1;i<n;i++){
        cin>>a;
        g=gcd(g,a);
    }
    cout<<g<<endl;
}


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

int main() {
    int n;cin>>n;
    int t,x,y;
    t=x=y=0;
    int f=1;
    for (int i=0;i<n;i++) {
        int nt,nx,ny;
        cin>>nt>>nx>>ny;
        int dt=nt-t;
        int dd=abs(x-nx)+abs(y-ny);
        f&=dd<=dt&&dt%2==dd%2;
    }
    if (f)
        puts("Yes");
    else
        puts("No");
    return 0;
}

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

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

    int A;
    int idx;
    for (int i = 0; i < N; i++)
    {
        cin >> A;
        if (A == 1)
        {
            idx = i;
        }
    }

    int ans = (idx / (K - 1)) + ((N - idx - 1) / (K - 1));
    int remain = idx % (K - 1) + (N - idx - 1) % (K - 1);
    if (0 < remain && remain <= K - 1)
    {
        ans++;
    }
    else if (K - 1 < remain)
    {
        ans += 2;
    }
    cout << ans << endl;
}


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

int main(){ 
    int n,m;
    int mi=200000;
    int ma=0;
    cin >> n>> m;
    vector<vector<int>> data(m, vector<int>(2));

      for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> data.at(i).at(j);
    }
  } 
  
  for (int i = 0; i < m; i++) {
    ma=max(data.at(i).at(0),ma);
    }
  for(int i=0;i<m;i++){
      mi=min(data.at(i).at(1),mi);
  }
  if(mi<ma){
      cout << 0 << endl;
  }else{
    cout << mi-ma+1 <<endl;
  }

    return 0;
}


Measured memory_bytes: 5760
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


S = LS2()
N = len(S)

print(sum(S[i] != S[i+1] for i in range(N-1)))


Measured memory_bytes: 77904
#include <iostream>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
    }
    cout << ((n - k) + k - 2) / (k - 1) + 1 << endl;
}

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

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

int main(void)
{
    ll n,Wc=0,Rc=0,sikiri;
    cin >> n;
    ll mini=n;
    char c[n];
    for(int i=0;i<n;i++)
    {
        cin >> c[i];
        if(c[i]=='R')
        {
            Rc++;
        }
    }
    for(int i=0;i<=n;i++)
    {
        if(Rc==n)
        {
            cout << 0 << endl;
            return 0;
        }
//        mini=min(mini,Rc+Wc);
        if(Wc<=Rc)
        {
            mini=min(mini,Rc);
        }
        else if(Wc>Rc)
        {
            mini=min(mini,Wc);
        }            
        if(c[i]=='W')
        {
            Wc++;
        }
        else if(c[i]=='R')
        {
            Rc--;
        }
    }
    cout << mini << endl;
    return 0;
}


Measured memory_bytes: 3804