akhauriyash/Code-Regression huggingface dataset:
// #include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
// #include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), greater<type>())
#define SORTF(a, comp) sort(ALL(a), comp)
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) (lower_bound(ALL(a), (x)) - a.begin())
#define bisect_right(a, x) (upper_bound(ALL(a), (x)) - a.begin())
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUT2(a) REPx(&x, a) INPUT(x);
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define ENDL cout << endl;

const int INF = 2e9;
// const LL INF = 9e18;
const LL MOD = 1e9+7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, greater<T> >;
template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}
template<class T> inline void debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I ";else cout << A[i] << " ";}ENDL}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[i], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  LL n, a, b, ans;
  cin >> n >> a >> b;
  LL dif = b - a - 1;
  if (dif % 2) ans = dif/2 + 1;
  else ans = min(n-b+(b-a+1)/2, a-1+(b-a+1)/2);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3632
n = int(input())
s = tuple(input())
ans = ['SS','SW','WS','WW']

for i in range(1,n-1):
    for j in range(4):
        if (s[i] == 'o') ^ (ans[j][-1] == 'S'):
            ans[j] += 'SW'.strip(ans[j][-2])
        else:
            ans[j] += ans[j][-2]
for i in range(4):
    if (s[0] == 'o') ^ (ans[i][0] == 'S'):
        if ans[i][1] == ans[i][n-1]:
            continue
    else:
        if ans[i][1] != ans[i][n-1]:
            continue
    if (s[n-1] == 'o') ^ (ans[i][n-1] == 'S'):
        if ans[i][0] == ans[i][n-2]:
            continue
    else:
        if ans[i][0] != ans[i][n-2]:
            continue
    print(ans[i])
    exit(0)
print(-1)


Measured memory_bytes: 4568
P = 10**9 + 7
X, Y = map(int, input().split())
if (X + Y) % 3 > 0:
    print(0)
    exit()
n = (X + Y) // 3
x = X - n
y = Y - n
if 0 > x or 0 > y:
    print(0)
    exit()
fact = [0] * (x + y + 1)
inv = [0] * (x + y + 1)
fact_inv = [0] * (x + y + 1)
fact[0], fact[1] = 1, 1
inv[0], inv[1] = 0, 1
fact_inv[0], fact_inv[1] = 1, 1
for i in range(2, x + y + 1):
    fact[i] = (fact[i - 1] * i) % P
print((fact[x + y] * pow(fact[x], P - 2, P) * pow(fact[y], P - 2, P)) % P)


Measured memory_bytes: 39796
#include <iostream>
#include <cstdio>

using namespace std;

int main(){
	double a, b, c, d, e, f, x, y;
	
	while( scanf(" %lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF ){
		if(b==0){
			x=c/a;
			y=(f-d*x)/e;
		}
		else{
			if(e==0){
				x=f/d;
				y=(c-a*x)/b;
			}
			else{
				x=(b*f-c*e)/(b*d-a*e);
				y=(c-a*x)/b;
			}
		}
		
		if(x==0) x=0;
		if(y==0) y=0;
	
		printf("%.3lf %.3lf\n", x, y);
	}

	return 0;
}

Measured memory_bytes: 1236
n=int(input())
x=[int(i) for i in input().split(" ")]
x=sorted(x)
mind=-1
for i in range(x[0],x[len(x)-1]+1):
    sum=0
    for j in x:
        sum+=(j-i)**2
    if mind>sum or mind==-1:
        mind=sum

print(mind)


Measured memory_bytes: 3060
for a in iter(input,'0 0'):
 H,W=map(int,a.split())
 m=[input()for _ in[0]*H]
 y=x=0
 for _ in range(H*W):
  u,v=x,y
  c=m[y][x]
  if c=='>':x+=1;
  if c=='v':y+=1;
  if c=='<':x-=1;
  if c=='^':y-=1;
  if c=='.':print(x,y);break
 else:print('LOOP')


Measured memory_bytes: 5616
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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(){
    ll n;cin >> n;
    string s;cin >> s;
    ll q;cin >> q;
    while(q--){
        ll k;cin >> k;
        ll d=0,m=0,sum=0,ans=0;
        rep(i,k){
            if(s[i]=='D')d++;
            if(s[i]=='M')m++,sum+=d;
            if(s[i]=='C')ans+=sum;
        }
        //cout << d <<" " << m <<" " << sum <<" " <<ans <<endl;
        rep(i,n-k){
            if(s[i]=='D')sum-=m,d--;
            if(s[i]=='M')m--;
            if(s[i+k]=='D')d++;
            if(s[i+k]=='M')m++,sum+=d;
            if(s[i+k]=='C')ans+=sum;
            //cout << d <<" " << m <<" " << sum <<" " <<ans <<endl;
        }
        cout << ans <<endl;
    }
}

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

int main() {
  int64_t N, M, K;
  cin >> N >> M >> K;
  vector<int64_t> A(N);
  vector<int64_t> B(M);
  vector<int64_t> At(N + 1);
  vector<int64_t> Bt(M + 1);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    At.at(i + 1) = At.at(i) + A.at(i);
  }
  for (int i = 0; i < M; i++) {
    cin >> B.at(i);
    Bt.at(i + 1) = Bt.at(i) + B.at(i);
  }
  int j = M;
  int result = 0;
  for (int i = 0; i <= N; i++) {
    if (At.at(i) > K) {
      break;
    }
    else {
      while (Bt.at(j) > K - At.at(i)) {
        j--;
      }
    }
    result = max(result, i + j);
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 9596
n=int(input())
l=list(map(int,input().split()))
s=0
a=0
for i in range(n):
    s+=l[i]

    if i%2:
        if s<=0:
            a+=1-s
            s=1
    else:
        if s>=0:
            a+=s+1
            s=-1

b=0;s=0
for i in range(n):
    s+=l[i]
    if i%2==0:
        if s<=0:
            b+=1-s
            s=1
    else:
        if s>=0:
            b+=s+1
            s=-1
print(min(a,b))

Measured memory_bytes: 14468
#! /bin/bash

read s

case "$s" in
 "SUN")
  echo 7
  ;;
 "MON")
  echo 6
  ;;
 "TUE")
  echo 5
  ;;
 "WED")
  echo 4
  ;;
 "THU")
  echo 3
  ;;
 "FRI")
  echo 2
  ;;
 "SAT")
  echo 1
  ;;
esac


Measured memory_bytes: 1268
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    String[] name = { "black", "blue", "lime", "aqua",
		      "red", "fuchsia", "yellow", "white" };
    int[][] color = { {0, 0, 0}, {0, 0, 255}, {0, 255, 0}, {0, 255, 255},
		  {255, 0, 0}, {255, 0, 255}, {255, 255, 0}, {255, 255, 255} };
    int[] dk;
    String n;
    int[] c;
    int min, minN;

    void run(){
	while(sc.hasNext()){
	    n = sc.next();
	    if(n.equals("0")) break;
	    c = new int[3];
	    dk = new int[8];
	    set(n.substring(1, 3), n.substring(3, 5), n.substring(5, 7));

	    for(int i=0; i<dk.length; i++)
		dk[i] = getD(i);

	    min = Integer.MAX_VALUE;
	    minN = 0;
	    for(int i=0; i<dk.length; i++)
		if(min > dk[i]){
		    min = dk[i];
		    minN = i;
		}

	    System.out.println(name[minN]);
	}
    }

    void set(String r, String g, String b){
	c[0] = Integer.parseInt(r, 16);
	c[1] = Integer.parseInt(g, 16);
	c[2] = Integer.parseInt(b, 16);
    }

    int getD(int i){
	int re=0;
	for(int k=0; k<c.length; k++)
	    re += (c[k]-color[i][k])*(c[k]-color[i][k]);
	return re;
    }
}

Measured memory_bytes: 21896
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
const int INF = 2e9;
const int MOD = 1e9 + 7;

int main() {
   int a, b, K;
   cin >> a >> b >> K;
   int k = 0;
   rrep(i, 101, 1) {
      if (a % i == 0 && b % i == 0) k++;
      if (k == K) {
         cout << i << endl;
         return 0;
      }
   }
   return 0;
}

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

using namespace std;

#define int long long

signed main(){
	int n,k;
	cin >> n >> k;
	int a[n];
	int dp[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		dp[i]=INT_MAX;
	}
	dp[0]=0;
	for(int i=1;i<n;i++){
		for(int j=1;j<=k&&(i-j)>=0;j++){
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
		}
	}
	cout << dp[n-1] << endl;
}



Measured memory_bytes: 1792
//uvwzyx
//uvwyzx
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;cin>>s;
//if atleast is not there, then it is easy
  vector<int >nos(26,-1);
  for(int i=0;i<s.size();i++){
  	nos[s[i]-'a']=i;
  }
  //if anything is -1
  int repl=-1;
  for(int i=0;i<26;i++)if(nos[i]==-1){repl=i;break;}
  if(repl!=-1){cout<<s;cout<<(char)('a'+repl);}
  else{
  	for(int i=s.size()-1;i>0;i--){
    	if(s[i]>s[i-1]){
        	//swapping has to work
          	
            	//something special
              for(int j=0;j<i-1;j++)cout<<s[j];
              repl=-1;
              for(int j=0;j<26;j++){
              	if(('a'+j > s[i-1] ) && nos[j]>=i){repl=j;break;}
              }
              if(repl==-1)break;
              cout<<(char)('a'+repl);
              return 0;
            }
          
    }
    cout<<-1;
  }
}


Measured memory_bytes: 3608
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>
 
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
using PP = pair<P, P>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;
 


int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>> fld(h, vector<int>(w));
  rep(i, h)rep(j, w)cin >> fld[i][j];
  queue<PP> que;
  rep(i, h){
    rep(j, w){
      if(fld[i][j] % 2 == 0)continue;
      if(j != w - 1){
        que.push(PP(P(i, j), P(i, j + 1)));
        fld[i][j + 1]++;
      }
      else if(i != h - 1){
        que.push(PP(P(i, j), P(i + 1, j)));
        fld[i + 1][j]++;
      }
    }
  }
  cout << que.size() << endl;
  while(!que.empty()){
    P p = que.front().first, q = que.front().second;
    int y = p.first, x = p.second, yy = q.first, xx = q.second;
    que.pop();
    y++;x++;yy++;xx++;
    cout << y << " " << x << " " << yy << " " << xx << endl;
  }
}
 

Measured memory_bytes: 8616
N, M = map(int, input().split())
ab = [[int(i) for i in input().split()] for _ in range(N)]
cd = [[int(i) for i in input().split()] for _ in range(M)]

for a, b in ab :
    mi, mv = 0, float('inf')
    for i, (c, d) in enumerate(cd) :
        if abs(a-c) + abs(b-d) < mv :
            mi = i
            mv = abs(a-c) + abs(b-d)
    print(mi+1)

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

int main() {
    int H,W;
    cin >> H>>W;
    vector<string> s(H);
    rep(i,H) cin >> s[i];
    vector<vector<int>> dp(H,vector<int>(W,(int)1e9));
    dp[0][0] = (s[0][0] == '#' ? 1 : 0);
    rep(h,H)rep(w,W){
        if(h==0&&w==0) continue;
        if(h != 0)
            dp[h][w] = min(dp[h][w],dp[h-1][w] + ((s[h-1][w] == '.' && s[h][w] == '#') ? 1: 0));
        if(w != 0)
            dp[h][w] = min(dp[h][w],dp[h][w-1] + ((s[h][w-1] == '.' && s[h][w] == '#') ? 1: 0));
    }
    
    cout << dp[H-1][W-1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// #define rep(i,n) for(int i=0;i<n;++i)
#define rep(i,i0,n) for(int i=i0;i<n;++i)
#define ALL(x) (x).begin(),(x).end()
#define pb(x)  push_back(x);
#define INF12 1000000000000 //10^12
#define INF9 1000000000 //10^9
#define MOD 1000000007 //10^9+7
using ll=long long;
using pii=pair<ll,ll>;
using vi=vector<int>;

int main() {
    int X, A;
    cin >> X >> A;
    cout << (X<A?0:10) << endl;
    return 0;
}


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

int main() {
    //
    int num;
    string str;

    cin >> num >> str;

    if(num % 2 == 0){
        string tmp1, tmp2;
        tmp1 = str.substr(0, num / 2);
        tmp2 = str.substr(num / 2);
        
        if (tmp1 == tmp2)
            cout << "Yes";
        else cout << "No";
    } else {
        cout << "No";
    }

    //
}


Measured memory_bytes: 3624
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))

ans = 0

for i in range(n):
	ans += bisect.bisect_left(a, b[i]) * (n - bisect.bisect_right(c, b[i]))

print(ans)

Measured memory_bytes: 23244
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int d, n;
	cin >> d >> n;
	if (d == 0)
	{
		if (n == 100)
			printf("%d", ++n);
		else
		printf("%d", n);
		
	}
	else
		if (d == 1)
		{
			if (n == 100)
				printf("%d00", ++n);
			else
			printf("%d00", n);
		}
		else
			if (d == 2)
			{
				if (n == 100)
					printf("%d0000", ++n);
				else
				printf("%d0000", n);
			}
	return 0;
}


Measured memory_bytes: 256
s = input()
if(s == "SUN"):
  print(7)
elif(s == "MON"):
  print(6)
elif(s == "TUE"):
  print(5)
elif(s == "WED"):
  print(4)
elif(s == "THU"):
  print(3)
elif(s == "FRI"):
  print(2)
elif(s == "SAT"):
  print(1)
  

Measured memory_bytes: 2940
import sys
input = sys.stdin.readline

W, H = map(int, input().split())
costs = []
for _ in range(W):
    costs.append((int(input()), 0))
for _ in range(H):
    costs.append((int(input()), 1))
costs.sort(key=lambda x: x[0])

h = H+1
w = W+1
ans = 0
for cost, flg in costs:
    if flg == 0:
        ans += cost * h
        w -= 1
    else:
        ans += cost * w
        h -= 1
print(ans)


Measured memory_bytes: 64604
#include<stdio.h>

int main(void)
{
  int N,M,X[500],x,i;
  int Y[500] = {0};

  scanf("%d",&N);
  scanf("%d",&M);

    for(i = 0;i < M;i++) {
      if(M == 0) break;
      else {
      scanf("%d",&Y[i]);
      if(Y[i] == 0) {
	Y[i] = 2;
      }
      }
    }

  x = N-M;

  printf("%d\n",x-1);

  return 0;
}

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

#define t_case ll test;cin>>test;while(test--)
#define left(nod) 2*nod
#define right(nod) 2*nod+1
#define ss second
#define ff first
#define pb push_back
#define pll pair<ll,ll>
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define deb(a) cout<<#a<<": "<<a;cout<<endl;
#define deba(a...) cout<<endl;cout<<#a<<": ";for(auto it:a)cout<<it<<" ";cout<<endl;

ll a[1000009];
ll lpf[1000009];
ll f[1000009];

int main()
{
	FAST;//not faster than scanf printf
	
	for(ll i=1;i<=1000005;i++)lpf[i]=i;
	
	for(ll i=2;i<=1000005;i++)
	{
		if(lpf[i]==i)
		{
			for(ll j=2*i;j<=1000005;j+=i)if(lpf[j]==j)lpf[j]=i;
			
		}
		
	}
	
	ll n;cin>>n;ll ans=0;cin>>a[1];ll gcd=a[1];
	
	for(ll i=2;i<=n;i++){cin>>a[i];gcd=__gcd(gcd,a[i]);}
	
	for(ll i=1;i<=1000005;i++)f[i]=0;
	
	if(gcd==1)ans=1;
	
	bool is=true;
	for(ll i=n;i>=1;i--)
	{
		set <ll> fac;
		ll te=a[i];
		
		while(te!=1)
		{
			fac.insert(lpf[te]);
			te/=lpf[te];
		}
		
		for(auto it:fac){if(f[it]>0){is=false;}f[it]=1;}
	}
	if(is)ans=2;
	
	if(ans==0)cout<<"not coprime";
	else if(ans==1)cout<<"setwise coprime";
	else cout<<"pairwise coprime";
	
	
}


Measured memory_bytes: 27072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // メインプログラムここから
    ll s, c; cin >> s >> c;
    ll ans = min(s, c/2);
    s -= ans;
    c -= ans*2;
    ans += c/4;
    cout << ans << endl;
    // ここまで
}


Measured memory_bytes: 256
import math
n=int(input())
i=1
while n>=i:                                                     #終了条件
    s=list(map(float,input().split()))
    #print("s",s)
    d=math.sqrt((s[3]-s[0])*(s[3]-s[0])+(s[4]-s[1])*(s[4]-s[1]))
    #print("d",d)
    if d>s[2]+s[5]:                                             #AとBが重なっていない
        print(0)
    elif abs(s[5]-s[2])<=d<=s[2]+s[5]:                          #AとBが共有点をもつ
        print(1)
    elif d<s[2]-s[5]:                                           #BがAの中にある
        print(2)
    elif d<s[5]-s[2]:                                           #AがBの中にある
        print(-2)
    i+=1



Measured memory_bytes: 5660
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n, x;
  cin >> n >> x;

  vector<int> l(n);
  REP(i,n){
    cin >> l[i];
  }

  int d = 0;
  int ans = 1;
  REP(i,n){
    d = d + l[i];
    if(d <= x) ans++;
  }

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



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <sstream>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;

const int MAX_N = 200005;
queue<int> q;
int N, C;
int v[MAX_N], s[MAX_N], t[MAX_N], c[MAX_N], total[MAX_N];

int main() {
  cin >> N >> C;

  for(int i = 0; i < N; i ++) {
    cin >> s[i] >> t[i] >> c[i];
  }

  for(int i = 1; i <= C; i++) {
    for(int j = 0; j < MAX_N; j++) {
      v[j] = 0;
    }

    for(int j = 0; j < N; j++) {
      if(i == c[j]) {
        v[s[j] * 2 - 1] += 1;
        v[t[j] * 2] -= 1;
      }
    }

    for(int j = 0; j < MAX_N; j++) {
      v[j + 1] += v[j];
      if(v[j] > 0)  {
        total[j] += 1;
      }
    }
  }

  int M = 0;
  for(int i = 0; i < MAX_N; i ++) {
    M = max(total[i], M);
  }

  // for(int i = 0; i< 25; i++) {
  //   cout << i << " " << v[i] << endl;
  // }

  cout << M << endl;

  return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
int dp[105][10005][2], d;
string s;

int solve(int i, int val, int tight, int actual_sum) { 
	val %= d;
	if (i == s.length()) {
		if (val % d == 0) {
			return 1;
		}
		return 0;
	}

	if (dp[val][i][tight] != -1) {
		return dp[val][i][tight];
	}

	int limit = 9, ans = 0;
	if (!tight) {
		for (int num = 0; num <= limit; num++) {
			ans += solve(i + 1, val + num, tight, actual_sum + num);
			ans %= mod;
		}	
	}

	if (tight) {
		limit = s[i] - '0';
		for (int num = 0; num < limit; num++) {
			ans += solve(i + 1, val + num, !tight, actual_sum + num);
		}	
		ans += solve(i + 1, val + limit, tight, actual_sum + limit);
		ans %= mod;
	}

	return dp[val][i][tight] = ans;
} 

void c_p_c()
{
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);  
   
   cin >> s >> d;
   memset(dp, -1, sizeof dp);
   cout << (solve(0, 0, 1, 0) - 1 + mod) % mod; // excluding zero

}
 
int32_t main()
{
    c_p_c();
    return 0;
}

Measured memory_bytes: 21032
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
a1=a%10
b1=b%10
c1=c%10
d1=d%10
e1=e%10
ar=[a1,b1,c1,d1,e1]
a2=a//10
b2=b//10
c2=c//10
d2=d//10
e2=e//10
k=10
s=0
minimini=-1
for i in ar:
    if i==0:
        continue
    minimini=min(i,k)
    if i<k:
        k=i
for i in ar:
    if i==0:
        continue
    if i==minimini:
        minimini-=1
        continue
    else:
        s+=10
print((a2+b2+c2+d2+e2)*10+minimini+1+s)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
  string a,b;
  int hit, blow;
  bool flag[4];
  while(cin >> a >> b){
    if(a[0] == '0' && b[0] == '0') return 0;
    for(int i=0; i<4; i++){
    }

    hit = 0; 
    blow = 0;
    for(int i=0; i<4; i++)
      flag[i] = false;

    for(int i=0; i<4; i++){
	if(a[i] == b[i]){
	  hit++;
	  flag[i] = true;
	}
	for(int j=0; j<4; j++){
	  if( a[i] == b[j] &&  flag[i] != true){
	    blow++;
	  }
	}
    }
    cout << hit << " " << blow << endl;
  }
}
	  

Measured memory_bytes: 916
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#define debug(x)   cerr<<#x<<" = "<<x<<endl
#else
#define debug(x) 
#endif
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define input_from_file freopen("input.txt","r",stdin)
#define output_to_file freopen("output.txt" , "w",stdout)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define fi first
#define se second 
#define mp make_pair
#define int long long
const int inf = 1e18 + 5;
signed main()
{
    #ifdef LOCAL
        input_from_file;
        output_to_file;
    #endif 
    IOS
    int r; cin>>r;
    double pi = 3.14159265359;
    double ans = 2*pi*r;
    cout<<fixed<<setprecision(20)<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3800
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <stack>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int main(){
	
	int N, M;
	cin >> N >> M;
	
	bool E[10][10] = {};
	
	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		E[a][b] = true;
		E[b][a] = true;
	}
	
	int num[10] = {2, 3, 4, 5, 6, 7, 8};
	int ans = 0;
	
	do{
		bool flag = E[1][num[0]];
		for(int i = 0; i < N - 2; i++){
			flag = (flag && E[num[i]][num[i + 1]]);
		}
		if(flag){
			ans += 1;
		}
	}while(next_permutation(num, num + (N - 1)));
	
	cout << ans << endl;
	
	return 0;
}


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

#define REP(i, n) for(int i = 0; i < N; i++)
#define SORT(v) sort(v.begin(), v.end())
#define veci(a, n) vector<int> a(n)
#define vecs(a, n) vector<string> a(n)
#define pb(a) push_back(a)

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> a(H);

    for(int i=0; i<H; i++) cin >> a.at(i);

    for(int i=0; i<W+2; i++) cout << "#";
    cout << endl;

    for(int i=0; i<H; i++) cout << "#" << a[i] << "#" << endl;

    for(int i=0; i<W+2; i++) cout << "#";
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b, c;
	cin >> a >> b >> c;
	cout << max({ a,b,c }) - min({ a,b,c }) << endl;
	return 0;
}


Measured memory_bytes: 256
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
signed main() {
    int A, B, C, X; cin >> A >> B >> C >> X;
    int ans = 0;
    repq(i,0,A) repq(j,0,B) repq(k,0,C) {
        int price = 500 * i + 100 * j + 50 * k;
        if(price == X) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int n,m;
    cin>>n;
    map<int,int> mp;
    for(int i=0;i<n;i++)
    {
        cin>>m;
        mp[m]++;
    }
    map<int,int> ::iterator it;
    int ans=0;
    for(it=mp.begin();it!=mp.end();it++)
    {
        if((*it).first!=(*it).second)
        ans+=(*it).second>=(*it).first?(*it).second-(*it).first:(*it).second;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(v) v.begin(), v.end()
//
int main(){
   int r,d,x;
   cin>>r>>d>>x;
   int a=x;
   rep(i,10){
      a=r*a-d;
      cout<<a<<endl;
   }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n-n%10==0)
	{
		cout<<n;
	}
	else
	{
		if(n-n%100==0)
		{
			cout<<"9";
		}
		else
		{
			if(n-n%1000==0)
			{
				int a=n-90;
				cout<<a;
			}
			else
			{
				if(n-n%10000==0)
				{
					cout<<"909";
				}
				else
				{
					if(n-n%100000==0)
					{
						int b=n-9090;
						cout<<b;
					}
					else
					{
						cout<<"90909";
					}
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
let s = read_line ()
let rec f i a p n = match String.length s - i with 0 -> a | -1 -> a - 1 | _ -> if n = 2 then f (i + 1) (a + 1) s.[i] 1 else if p = s.[i] then f (i + 2) (a + 1) p 2 else f (i + 1) (a + 1) s.[i] 1
let _ = f 0 0 ' ' 2 |> Printf.printf "%d\n"

Measured memory_bytes: 2688
N = int(input())

dp = [[0, 0, 0] for _ in range(N)]
a, b, c = map(int, input().split())
dp[0][0] = a
dp[0][1] = b
dp[0][2] = c

for i in range(1, N):
    a, b, c = map(int, input().split())

    dp[i][0] = max(dp[i][0], dp[i - 1][1] + a, dp[i - 1][2] + a)
    dp[i][1] = max(dp[i][1], dp[i - 1][0] + b, dp[i - 1][2] + b)
    dp[i][2] = max(dp[i][2], dp[i - 1][0] + c, dp[i - 1][1] + c)

print(max(dp[N - 1]))


Measured memory_bytes: 59952
#!/usr/bin/env python3
import sys


def solve(N: int):
    if N%2 == 0:
        print(1/2)
    else:
        print((N//2+1)/N)


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


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

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;
}
struct Unionfind {
    vector<int> par;

    Unionfind(int n) : par(n) {
        for(int i = 0; i < n; ++i) par[i] = i;
    }

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

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        par[rx] =ry;
    }

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

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }

    const int INF = 1e9;
    vector<int> dist(n, INF);
    vector<int> par(n, 0);
    dist[0] = 0;
    queue<int> q;
    q.push(0);

    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int next_v : graph[v]) {
            if(dist[next_v] != INF) continue;
            dist[next_v] = dist[v] + 1;
            par[next_v] = v;
            q.push(next_v);
        }
    }

    cout << "Yes" << endl;

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

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


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

    i64 cnt = 0;
    REP(i, N - 1) {
        if (A[i] == i + 1) swap(A[i], A[i + 1]), cnt++;
    }
    if (A[N - 1] == N) cnt++;
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3976
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <tuple>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rep1(i, n) for(int i=1; i<=n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
#define countof(array) (sizeof(array) / sizeof(array[0]))
typedef long long ll;

#define MAX_N 100000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

string ab = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string as = {"abcdefghijklmnopqrstuvwxyz"};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

void yes() {
  cout << "Yes" << endl;
}

void no() {
  cout << "No" << endl;
}

void print_array(int array[], int len) {

  for(int i=0; i<len; ++i) {
    cout << array[i] << endl;
  }

}

ll absolute(ll x) {
  return (x<0)? (-1)*x : x;
}

//g++ AtCoder.cpp -o AtCoder
//AtCoder

//--------------------------
//提出するときC++に帰る
//--------------------------

int main() {

  int k, a, b;
  cin >> k >> a >> b;

  for(int i=a; i<=b; ++i) {
    if(i%k==0) {
      cout << "OK" << endl;
      return 0;
    }
  }

  cout << "NG" << endl;

  return 0;
}


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

using namespace std;

int main() {
    int N;
    cin >> N;
    long long res = 0;
    for (long long  i = 1; i <= N; i++) {
        long long Y = N / i;
        res += Y * (Y+1)/2 * i ;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
 
int main(){
    int i;
    int n, x;

    scanf("%d",&n);
 
    for( i = 1; i<= n ; i++ ){
        if(i%3 == 0)
            printf(" %d",i);
        else{
            x = i;
            do{
                if( x%10 == 3 ){
                    printf(" %d", i);
                    break;
                }
                x/=10;
            }while(x);
        }
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 2076
def solve():
  n = int(input())
  cost = list(map(int, input().split(' ')))
  dp = [-1 for _ in range(n)]
  dp[0] = 0
  dp[1] = abs(cost[1] - cost[0])
  for i in range(2, n):
    dp[i] = min(dp[i-2] + abs(cost[i] - cost[i-2]), 
                dp[i-1] + abs(cost[i] - cost[i-1]))
  print(dp[-1])
  
  
solve()

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

int main() {
  string N;
  cin >> N;
  if(N[0] == N[1] && N[1] == N[2] || N[1] == N[2] && N[2] == N[3] || N[0] == N[1] && N[1] == N[2] && N[2] == N[3]) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3600
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())printf("%d ",v[_]);cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
// int dx[]={0,1,0,-1};
// int dy[]={1,0,-1,0};//RDLU
#define yes puts("YES")
#define no puts("NO")

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

	int n,m;
	cin>>n>>m;
	vi dp(m+2,1);
	dp[0]=0;
	int MOD=1000000007;
	rep(i,n){
		int a;cin>>a;
		vi ndp(m+2);
		rep(j,m+1)ndp[j+1]=(MOD+ndp[j]+dp[j+1]-dp[max(0ll,j-a)])%MOD;
		dp=ndp;
	}

	cout<<(MOD+dp[m+1]-dp[m])%MOD<<endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
 #define int long long

#define all(X) (X).begin(), (X).end()
#define reset(X) memset(X, 0, sizeof(X))
#define mp(a, b) make_pair(a, b)
#define pb push_back
#define endl '\n'
#define fi first
#define se second


using namespace __gnu_pbds;
using namespace std;
// const int mod=1e9+7;
 const int mod=998244353;
 // const int mod=1e9+9;
const int INF=4e18+10;
// const int INF=4e18+10;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define read(n) int n; cin>>n;
#define readv(x, n) vector<int> x(n); for(auto &i:x) cin>>i;


typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

template<typename T1,typename T2>
void set_min(T1& a, T2 b)
{
    a=min(a, (T1)b);
}


int multiply(int a, int b, int in_mod){return (a*b)%in_mod;}
int mult_identity(int a){return 1;}


auto power(auto a, int b, int in_mod)
{
    auto prod=mult_identity(a);
    auto mult=a%in_mod;
    while(b!=0)
    {
        if(b%2)
        {
            prod=multiply(prod,mult, in_mod);

        }
        mult=multiply(mult, mult,in_mod);
        b/=2;
    }
    return prod;
}
int mod_inv(int q, int in_mod)
{

    return power(q, in_mod-2,in_mod);
}


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


    string output;
    while(n)
    {
        n--;
        char ch = (n)%26;
        n = n/26;
        output+=string(1,ch+'a');
    }
    reverse(all(output));
    cout<<output<<endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen("INPUT.txt", "r", stdin);
        freopen("OUTPUT.txt", "w", stdout);
    }
#endif
    auto clk = clock();
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    // -------------------------------------Code starts here---------------------------------------------------------------------

    int t = 1;
    // cin>>t;

    for (int test = 1; test <= t; test++)
    {
        // cout<<"Case #"<<test<<": ";
        // cout<<endl;
        solve();
        // cout<<endl;
    }

    // -------------------------------------Code ends here------------------------------------------------------------------

    clk = clock() - clk;
    // cerr << fixed << setprecision(6) << "Time: " << ((long double)clk) / CLOCKS_PER_SEC << "\n";
    return 0;
}


Measured memory_bytes: 3576
import java.util.*;
public class Main {
	public static class Work{
		private int A;
		private int B;
		
		public Work(int A, int B) {
			this.A = A;
			this.B = B;
		}
		
		public int getA() {
			return A;
		}
		public int getB() {
			return B;
		}
	}
	
	public static class Comp implements Comparator<Work> {
	    public int compare(Work x1, Work x2) { 
	        if(x1.getB() < x2.getB()) {
	            return -1;
	        } 
	        else if(x1.getB() > x2.getB()){
	            return 1;
	        } 
	        else{ 
	        	if(x1.getA() < x2.getA()) {
	        		return 1;
	        	}
	        	else if(x1.getA() > x2.getA()) {
	        		return -1;
	        	}
	        	else {
	        		return 0;
	        	}
	        }
	    }
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		ArrayList<Work> x = new ArrayList<Work>();
		
		for(int i = 0; i < N; i++) {
			int A = stdIn.nextInt();
			int B = stdIn.nextInt();
			Work work = new Work(A,B);
			x.add(work);
		}
		
		Collections.sort(x, new Comp());
		long sum = 0;
		for(Work y:x) {
			sum += y.getA();
			if(sum > y.getB()) {
				System.out.println("No");
				System.exit(0);
			}
		}
		System.out.println("Yes");

	}

}

Measured memory_bytes: 106392
import copy
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

now = 0
while k > 0:
    if k & 1:
        now = a[now]

    a_next = [-1] * n
    for i in range(n):
        a_next[i] = a[a[i]]

    a = copy.copy(a_next)
    k = k >> 1

ans = now + 1
print(ans)


Measured memory_bytes: 171040
# coding: utf-8
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
Acum = list(accumulate(A))
l_cut = [None] * N  # 左のリストで2つに切り分けるindex
l_cut[1] = 0
l = A[0]; r = A[1]
for i in range(2, N):
    r += A[i]
    diff = abs(r-l)
    index = l_cut[i-1]
    while index < i - 1:
        temp = abs(l + A[index+1] - (r - A[index+1]))
        if temp < diff:
            index += 1
            l += A[index]
            r -= A[index]
            diff = temp
        else:
            break
    l_cut[i] = index

r_cut = [None] * N
r_cut[-2] = N-2
l = A[-2]; r = A[-1]
for i in range(N-3, 0, -1):
    l += A[i]
    diff = abs(r-l)
    index = r_cut[i+1]
    while index > i:
        temp = abs(r + A[index] - (l - A[index]))
        if temp < diff:
            index -= 1
            r += A[index+1]
            l -= A[index+1]
            diff = temp
        else:
            break
    r_cut[i] = index

answer = 10 ** 17
for i in range(1, N-2):
    a = Acum[l_cut[i]]
    b = Acum[i] - a
    c = Acum[r_cut[i+1]] - Acum[i]
    d = Acum[-1] - (a + b + c)
    temp = max(a, b, c, d) - min(a, b, c, d)
    if temp < answer:
        answer = temp

print(answer)
# 27r

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

bool palindrome(string str)
{
    string str_r = str;
    reverse(str_r.rbegin(), str_r.rend());
    return str == str_r;
}

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    if (palindrome(s) && palindrome(s.substr(0, (n - 1) / 2)) && palindrome(s.substr((n + 3) / 2 - 1)))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

LL dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
LL dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

///**************************DONE****************************///

LL a[2 * mx5], b[2 * mx5];

int main()
{

    LL n, m, k;
    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];

    for(int i = 1; i <= m; i++)
        cin >> b[i], b[i] += b[i - 1];

    int ans = 0;
    for(int i = 0; i <= n; i++){

        if(a[i] > k)
            continue;
        if(a[i] == k){
            ans = max(ans, i);
            continue;
        }

        int l = 0, r = m;
        while(l <= r){
            int mid = (l + r) / 2;
            if(b[mid] + a[i] > k)
                r = mid - 1;
            else
                l = mid + 1;
        }

        ans = max(ans, i + r);
    }

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




Measured memory_bytes: 6756
#include<bits/stdc++.h>
#define endl '\n'
#define INF 1 << 21
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, i;
  cin >> n >> i;

  cout << n - i + 1 << endl;
  return 0;
}


Measured memory_bytes: 256