akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define PB push_back
#define MP make pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
typedef pair<int,int> pii;

int W,H,N;
int X1[1001],Y1[1001],X2[1001],Y2[1001];
int fld[2000][2000];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int ans;
vector<int> xs;

int compress(int* x1,int* x2,int w){
    xs.clear();
    for(int i=0;i<N;++i){
        for(int d=-1;d<=1;++d){
            int tx1=x1[i]+d;
            int tx2=x2[i]+d;
            if(0<=tx1&&tx1<w)xs.PB(tx1);
            if(0<=tx2&&tx2<w)xs.PB(tx2);
        }
    }
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    for(int i=0;i<N;++i){
        x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin();
        x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin();
    }
    return xs.size();
}

void bfs(int sx,int sy){
    queue<pii> que;
    que.push(pii(sx,sy));
    while(!que.empty()){
        pii p=que.front();
        que.pop();
        int x=p.FI;
        int y=p.SE;
        for(int i=0;i<4;++i){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx<0||nx>=W||ny<0||ny>=H)continue;
            if(fld[ny][nx]==1)continue;
            fld[ny][nx]=1;
            que.push(pii(nx,ny));
        }
    }
}

signed main(){
    while(1){
        cin>>W>>H;
        if(W==0&&H==0)break;
        cin>>N;
        for(int i=0;i<N;++i){
            cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
        }
        W=compress(X1,X2,W);
        H=compress(Y1,Y2,H);
        for(int i=0;i<N;++i){
            for(int y=Y1[i];y<Y2[i];++y){
                for(int x=X1[i];x<X2[i];++x){
                    fld[y][x]=1;
                }
            }
        }
        for(int y=0;y<H;++y){
            for(int x=0;x<W;++x){
                if(fld[y][x]==1)continue;
                queue<pii> que;
                que.push(pii(x,y));
                fld[y][x]=1;
                while(!que.empty()){
                    pii p=que.front();
                    que.pop();
                    int x=p.FI;
                    int y=p.SE;
                    for(int i=0;i<4;++i){
                        int nx = x+dx[i];
                        int ny = y+dy[i];
                        if(nx<0||nx>=W||ny<0||ny>=H)continue;
                        if(fld[ny][nx]==1)continue;
                        fld[ny][nx]=1;
                        que.push(pii(nx,ny));
                    }
                }
                ans++;
            }
        }
        cout<<ans<<endl;
        memset(fld,0,sizeof(fld));
        ans=0;
    }
}

Measured memory_bytes: 18772
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
typedef vector<int> vi;
typedef long long ll;
int Q;
int c[105];
int a[105];
int n[105];
int team[105];
int main(void)
{
    memset(team,0,sizeof(team));
    cin >> Q;
    for(int i=0;i<Q;i++)
    {
        cin >> c[i] >> a[i] >> n[i];
    }
    for(int i=0;i<Q;i++)
    {
        while(n[i]>0)
        {
            if(c[i]>0 && a[i]>0)
            {
                team[i]++;
                n[i]--;
                c[i]--;
                a[i]--;
            } else{break;}
        }
        while(a[i]>0)
        {
            if(c[i]>=2)
            {
                team[i]++;
                a[i]--;
                c[i]-=2;
            } else{break;}
        }
        team[i]+=(c[i]/3);
    }
    for(int i=0;i<Q;i++) cout << team[i] << endl;
    return 0;
}



Measured memory_bytes: 3124
n,m = map(int,input().split())
dig = [list(map(int,input().split())) for i in range(m)]

res = -1
st = 0 if n == 1 else 10**(n-1)
for i in range(st,1000):
    s = str(i)
    ju = True
    for j in dig:
        if j[0] > len(s):
            ju = False
            break
        else:
            if int(s[j[0]-1]) == j[1]:
                continue
            else:
                ju = False
                break
    if ju:
        res = i
        break
print(res)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char ma[60][60];
int main(void)
{
    int a,b;
    cin>>a>>b;
    if(a <= b)
        cout<<a<<endl;
    else if(a > b)
        cout<<a-1<<endl;
   return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    long int h, w;
    scanf("%ld%ld", &h, &w);
    long int ans;
    if(h%2==0){
        ans=h/2*w;
    }else if(w%2==0){
        ans=w/2*h;
    }else{
        ans=(h/2*w)+(w/2+1);
    }
    if(h==1 || w==1){
        ans=1;
    }
    printf("%ld\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <utility>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef pair<int, int> P;

int main()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    map<P, int> mp;
    int a[200005], b[200005];
    vector<int> v[200005];
    int na[200005] {0}, nb[200005] {0};
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        if(mp[P(a[i], b[i])]) continue;
        mp[P(a[i], b[i])] = 1;
        mp[P(b[i], a[i])] = 1;
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
        if(s[b[i]] == 'A') na[a[i]]++;
        else nb[a[i]]++;
        if(s[a[i]] == 'A') na[b[i]]++;
        else nb[b[i]]++;
    }
    bool f[200005];
    fill(f, f + n, true);
    for(int i = 0; i < n; i++){
        if(f[i] && (na[i] <= 0 || nb[i] <= 0)){
            queue<int> que;
            f[i] = false;
            que.push(i);
            while(que.size()){
                int now = que.front();
                que.pop();
                for(int next : v[now]){
                    if(!f[next]) continue;
                    if(s[now] == 'A') na[next]--;
                    else nb[next]--;
                    if(na[next] <= 0 || nb[next] <= 0){
                        f[next] = false;
                        que.push(next);
                    }
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(f[i]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


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

#define all(v) v.begin(), v.end()

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  string s,t;cin>>s>>t;
  int ans=0;
  for(int i=0;i<s.size();i++){
    if(s[i]!=t[i]){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
	int n,m,c;
  cin>>n>>m>>c;
  
  vector <int> b(m);
  rep(h,m)cin>>b[h];
  

  vector<vector<int>> data(n, vector<int>(m));
 
  // 入力 (2重ループを用いる)
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> data.at(i).at(j);
    }
  }


  int count = 0;
	int source=0;
 
  for (int k = 0; k < n; k++) {
    	source=0;
      for (int l = 0; l < m; l++) {
		source+=b[l]*data.at(k).at(l);
         }
    if(source+c>0){
    	count++;
    }
    
  }
    cout<<count<<endl;
}
    

Measured memory_bytes: 3616
N,M = map(int,input().split())
L_answer=0
R_answer=float('inf')
for i in range(M):
  L,R = map(int,input().split())
  L_answer=max(L_answer,L)
  R_answer=min(R_answer,R)
print(R_answer-L_answer+1 if R_answer-L_answer+1>0 else '0')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using piii = pair<pii, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    int K;
    cin >> K;
    string ans;
    for (int i = 0; i < K; ++i) {
        ans += "ACL";
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3648
package main

import "fmt"

func main() {
	var n, k int
	var s string
	fmt.Scan(&n, &k, &s)
	ans := ""
	for i := 0; i < n; i++ {
		if i+1 == k {
			if s[i] == 'A' {
				ans += "a"
			} else if s[i] == 'B' {
				ans += "b"
			} else {
				ans += "c"
			}
		} else {
			ans += string(s[i])
		}
	}
	fmt.Println(ans)
}


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

int main(){
  int K;
  int N;
  cin >> K >> N;
  int A[200000];
  for(int i=0; i<N; i++) cin >> A[i];
  
  int result=K-A[N-1]+A[0];
  for(int i=0; i<N-1; i++) result=max(result,A[i+1]-A[i]);
  cout << K-result << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>

int main(void){
    int a, b;
    scanf("%d %d", &a, &b);
    if(a<b){
    	printf("a < b\n");
    }
    else if(a>b){
    	printf("a > b\n");
    }
    else{
    	printf("a == b\n");
    }
	return 0;
}

Measured memory_bytes: 580
#include <stdio.h>

int main() {
  int a, b;
  char string[20];
  bool valid = true;
  
  scanf("%d %d", &a, &b);
  scanf("%s",string);
  
  if(string[a] != '-'){
  	valid = false;
  }
  
	for(int i=0;string[i] != '\0'; i++){
		if(i != a){
			if(string[i] < '0' || string[i] > '9'){
				valid = false;
				break;
			}
		}
	}
	
	(valid) ? puts("Yes") : puts("No");
	
  return 0;
}

Measured memory_bytes: 1660
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO ?????????????????????????????????????????????
		BufferedReader br =
				new BufferedReader(
						new InputStreamReader(System.in) );

		int n = Integer.parseInt( br.readLine() );
		String[] temp;

		int[] S = new int[n];
		temp = br.readLine().split(" ");
		for (int i=0; i < n; i++) {
			S[i] = Integer.parseInt(temp[i]);
		}

		int q = Integer.parseInt( br.readLine() );

		int[] T = new int[q];
		temp = br.readLine().split(" ");
		for (int i=0; i < q; i++) {
			T[i] = Integer.parseInt(temp[i]);
		}

		int count = 0;
		for (int i=0; i < T.length; i++) {
			for (int j=0; j < S.length; j++) {
				if (T[i] == S[j]) {
					count++;
					break;
				}
			}
		}

		System.out.println(count);
	}

}

Measured memory_bytes: 27540
#include <stdio.h>

int main(){
  int n,q,i=0,c=0,m,r,l,a;
  int s[100000];

 
    scanf("%d",&n);
    while(i<n){
      scanf("%d",&s[i]);
      if(0<=s[i]&&s[i]<=1000000000) i++;
    }

    scanf("%d",&q);
    for(i=0;i<q;i++){
      scanf("%d",&a);
      l=0;
      r=n;
      while(l<r){
	m=(l+r)/2;
	if(a==s[m]){
	  c++;
	  break;
	}
	else if(a<s[m]){
	  r=m;
	}
	else if(a>s[m]){
	  l=m+1;
	}
      }
    }

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

    return 0;
}



Measured memory_bytes: 2176
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 301;
const int K = N * N;
const int MOD = 998244353;

int add(int a, int b) {
	return (a + b) % MOD;
}

int sub(int a, int b) {
	return (a - b + MOD) % MOD;
}

int mul(int a, int b) {
	return (a * b) % MOD;
}

int binpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int divv(int a, int b) {
	return mul(a, binpow(b, MOD - 2));
}

int dp[N][K];
int dp2[N][K];


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

	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &t : a) {
		cin >> t;
	}
	dp[0][0] = 1;
	dp2[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < K; j++) {
			if (a[i] + j < K) {
				dp[i + 1][j + a[i]] = add(dp[i + 1][j + a[i]], dp[i][j]);
				dp2[i + 1][j + a[i]] = add(dp2[i + 1][j + a[i]], dp2[i][j]);

			}
			dp[i + 1][j] = add(dp[i + 1][j], mul(2, dp[i][j]));
			dp2[i + 1][j] = add(dp2[i + 1][j], mul(1, dp2[i][j]));
		}
	}
	int s = 0;
	for (auto t : a) {
		s += t;
	}
	int ans = 0;
	for (int tk = 0; tk < s; tk++) {
		if (tk >= s - tk) {
			int cnt = dp[n][tk];
			cnt = sub(cnt, mul(dp2[n][tk], 2));
			ans = add(ans, cnt);
		}
	}
	ans = mul(ans, 3);
	int all = binpow(3, n);
	all = sub(all, mul(3, sub(binpow(2, n), 2)));
	all = sub(all, 3);
	cout << sub(all, ans) << endl;
}


Measured memory_bytes: 425728
#include <stdio.h>
int main(){
	long n,i,j,k,a[222222],p[222222][21],sum[222222][21],t[21],m=1,flag1,flag2;
	long ans=0;
	for(i=0;i<21;i++){
		t[i]=m;
		m=m*2;
	}
	scanf("%ld",&n);
	for(i=0;i<n;i++)
	scanf("%ld",&a[i]);
	for(i=0;i<n;i++){
		for(j=0;j<20;j++){
			if(a[i]%t[j+1]>=t[j])
			p[i][j]=1;
			else
			p[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<20;j++){
			if(i==0)
			sum[i][j]=p[i][j];
			else
			sum[i][j]=sum[i-1][j]+p[i][j];
		}
	}
	i=0;
	j=0;
	while(j<n){
		flag2=1;
		for(k=0;k<20;k++){
			if(i==0){
				if(sum[j][k]>=2)
				flag2=0;
			}
			else if(sum[j][k]-sum[i-1][k]>=2)
			flag2=0;
		}
		if(flag2==0){
			ans+=j-i;
			i++;
		}
		else
		j++;
	}
	ans+=(j-i)*(j-i+1)/2;
	printf("%ld\n",ans);
	return 0;
}


Measured memory_bytes: 71424
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
using namespace std;

int main(){
  string S;
  cin >> S;
  int x = 0;
  x = S.size();
  if(S.at(x - 1) == 's'){
    cout << S << "es" << endl;
  }else{
    cout << S << "s" << endl;
  }
}


Measured memory_bytes: 3620
function Main(input) {
  input = input.split("\n");
  var s = input[0];
  var ssub = input[0].slice(2,s.length-1);
  var a = ssub.match(/C/g);
  var ssub2 = ssub.match(/[A-Z]/g);
  var ssub3 = (input[0].slice(s.length-1)).match(/[A-Z]/);
  var ssub4 = (input[0].slice(1,2)).match(/[A-Z]/);
  var ans = "WA";
  if(a!=null&&ssub2!=null&&ssub3==null&&ssub4==null){
  if(s.substr(0,1)=="A"&&a.length==1&&ssub2.length==1){
    ans = "AC";
  }
}
  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;


int main() {
  ll n, k; cin >> n >> k;
  Vll a(n); cin >> a;
  rep(i, n) --a[i];

  Vbo seen(n, false);

  int now = 0;
  int cnt = 0;
  V dist(n);

  while (1) {
    seen[now] = true;
    dist[now] = cnt;
    now = a[now];
    if (seen[now]) break;
    ++cnt;
  }
  int z = now;
  int l0 = dist[z];
  int l1 = cnt + 1 - l0;

  if (k >= l0) k = l0 + (k-l0)%l1;
  now = 0;
  rep(i, k) now = a[now];
  cout << (now+1) << "\n";

  return 0;
}


Measured memory_bytes: 5572
#include<cstdio>
#include<iostream>
using namespace std;
#define max lshfisdhflsih
int dp[2001][2001][2];
int main(void){
	int i,j,m,n,max,x,nn,k;
	char s[2001],t[2001];
	cin>>m>>n>>s>>t;
	for(i=0;i<=m;i++){
		for(j=0;j<=n;j++){
			dp[i][j][0]=-1; dp[i][j][1]=-1;
		}
	}
	dp[0][0][0]=0;
	for(i=0;i<=m;i++){
		for(j=0;j<=n;j++){
			if(i<m){
				if(dp[i][j][0]!=-1){
					if(s[i]=='I'){
						nn=dp[i][j][0]+1;
						if(dp[i+1][j][1]<nn) dp[i+1][j][1]=nn;
					}
					else {
						if(dp[i+1][j][0]==-1) dp[i+1][j][0]=0;
					}
				}
				if(dp[i][j][1]!=-1){
					if(s[i]=='O'){
						nn=dp[i][j][1]+1;
						if(dp[i+1][j][0]<nn) dp[i+1][j][0]=nn;
					}
					else {
						if(dp[i+1][j][1]==-1) dp[i+1][j][1]=1;
					}
				}
			}
			if(j<n){
				if(dp[i][j][0]!=-1){
					if(t[j]=='I'){
						nn=dp[i][j][0]+1;
						if(dp[i][j+1][1]<nn) dp[i][j+1][1]=nn;
					}
					else {
						if(dp[i][j+1][0]==-1) dp[i][j+1][0]=0;
					}
				}
				if(dp[i][j][1]!=-1){
					if(t[j]=='O'){
						nn=dp[i][j][1]+1;
						if(dp[i][j+1][0]<nn) dp[i][j+1][0]=nn;
					}
					else {
						if(dp[i][j+1][1]==-1) dp[i][j+1][1]=1;
					}
				}
			}
		}
	}
/*	for(i=0;i<=m;i++){
		for(j=0;j<=n;j++) printf("%d:%d ",dp[i][j][1],dp[i][j][0]);
		cout<<endl;
	}*/
	max=0;
	for(i=0;i<=m;i++){
		for(j=0;j<=n;j++){
			if(max<dp[i][j][1]) max=dp[i][j][1];
		}
	}
	cout<<max<<endl;
	return 0;
}

Measured memory_bytes: 34364
#include <stdio.h>

int ans = 123456789;
int check[20];
int S = 0;
int a,b,c;
int x[20],y[20][20];
void func(int k)
{
	if(k>a)
	{
		for(int j=1;j<=b;j++) if(check[j]<c) return;
		ans = ans<S?ans:S;
		return;
	}
	
	func(k+1);
	S += x[k];
	for(int j=1;j<=b;j++) check[j] += y[k][j];
	func(k+1);
	for(int j=1;j<=b;j++) check[j] -= y[k][j];
	S -= x[k];
}

int main()
{
	scanf("%d%d%d",&a,&b,&c);
	for(int i=1;i<=a;i++)
	{
		scanf("%d",&x[i]);
		for(int j=1;j<=b;j++) scanf("%d",&y[i][j]);
	}
	
	func(1);
	printf("%d",ans==123456789?-1:ans);
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }



// 約数列挙
vector<ll> calc_divisor(ll n) {
    vector<ll> res;
    for (ll i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            ll j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

// 素因数分解
//vector<ll> prime_factor(ll n) {
//    vector<ll> res;
//    if(n == 1) {
//        res.push_back(1);
//        return res;
//    }
//    if(n > 1) {
//        for(int i=2; i*i <= n; i++) {
//            while(n % i == 0) {
//                res.push_back(i);
//                n /= i;
//            }
//        }
//        if(n != 1) res.push_back(n);
//
//    }
//    return res;
//}


bool IsPrime(ll num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main() {
    ll a,b; cin >> a >> b;

    auto a_v = calc_divisor(a);
    auto b_v = calc_divisor(b);




    vector<ll> common_divisor;
    set_intersection(a_v.begin(), a_v.end(), b_v.begin(), b_v.end(), std::back_inserter(common_divisor));

    ll ans = 0;

    rep(i, common_divisor.size()) {
        if(IsPrime(common_divisor[i])) {
            ans++;
        }
    }


    // なぜか`1`が計算されないので
    cout << ans + 1 << endl;



    return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <sstream>
#include <type_traits>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pF first
#define pS second
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define GCD(a,b) __gcd((a),(b))
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> >
#define vll vector <long long>
#define allof(x) (x).begin(), (x).end()
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define printArr(a,l) cout<<#a<<": ";for(int i=0;i<(l);i++){cout<<a[i]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(int i=0;i<(r);i++){for(int j=0;j<(c);j++){cout<<a[i][j]<<" ";}cout<<endl;}
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector<string>vec_splitter(string s){s+=',';vector<string>res;while(!s.empty()){res.push_back(s.substr(0,s.find(',')));s=s.substr(s.find(',')+1);}
return res;}
void debug_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(vector<string>args,int idx,int LINE_NUM,Head H,Tail...T){if(idx>0)cerr<<", ";else cerr<<"Line("<<LINE_NUM<<") ";stringstream ss;ss<<H;cerr<<args[idx]<<" = "<<ss.str();debug_out(args,idx+1,LINE_NUM,T...);}
#ifdef LOCAL_DBG
#define dbg(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

int main () {
	fastCin;
	int n, k;
	cin >> n >> k;
	int a[200005];
	for (int x = 1; x <= n; x++) {
		cin >> a[x];
	}
	for (int x = k+1; x <= n; x++) {
		if (a[x] <= a[x-k]) {
			cout << "No\n";
		} else {
			cout << "Yes\n";
		}
	}
	return 0;
}

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

#define INF 1e9
using namespace std;
using ll = long long;

int main() {

    ll a, b, c, d; cin >> a >> b >> c >> d;

    if (abs(c - a) <= d) {
        puts("Yes");
    } else {
        if (abs(b - a) <= d && abs(c - b) <= d) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> p(m);
  vector<string> s(m);
  rep(i, m) cin >> p[i] >> s[i];
  rep(i, m) --p[i];

  vector<int> ac(n, 0), wa(n, 0);
  rep(i, m) {
    if (s[i] == "AC") ++ac[p[i]];
    else if (ac[p[i]] == 0) ++wa[p[i]];
  }

  int co = 0, pe = 0;
  rep(i, n) if (ac[i] > 0) {
    ++co;
    pe += wa[i];
  }
  printf("%d %d\n", co, pe);
  return 0;
}

Measured memory_bytes: 7464
N = int(input())
A = []

for i in range(N):
    A.append(int(input()))

max_list = sorted(A, reverse=True)
max_index = A.index(max(A))

for i in range(0, len(A)):
    if i == max_index:
        print(max_list[1])
    else:
        print(max_list[0])

Measured memory_bytes: 14112
#include <stdio.h>
int max(int a,int b){return a>b?a:b;}
int main(){
int n;
scanf("%d",&n);
int a[1000],ans=0;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j){ans=max(ans,a[i]-a[j]);
}
printf("%d\n",ans);
}

Measured memory_bytes: 128
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int mod = 1000000000+7;
        int[][] a = new int[100005][13];
        char[] num = new char[100005];
        int index = str.length()-1;
        for(int i = 100005-1; i>=0; i--) {
            if(index>=0) {
                num[i] = str.charAt(index);
                index--;
            }else num[i] = '0';
        }
        index=0;

        a[index][0] = 1;
        index++;
        while(index<100005) {
            if(num[index]=='?') {
                //System.out.println(index);
                for(int k = 0; k<10; k++) {
                    for(int i = 0; i<13; i++) {
                        int now = i*10+k;
                        //System.out.println(now);
                        a[index][now%13] += (a[index-1][i])%mod;
                        a[index][now%13] = a[index][now%13]%mod;
                    }
                }
            }else {
                for(int i = 0; i<13; i++) {
                    int now = i*10+ Character.getNumericValue(num[index]);

                    if(index==1) {
//                        System.out.println(now);
//                        System.out.println("char " + num[index]);
//                        System.out.println("char to int: "+ Character.getNumericValue(num[index]));
                    }
                    a[index][now%13] += a[index-1][i]%mod;
                    a[index][now%13] = a[index][now%13]%mod;
                }
            }
            index++;
        }
        //System.out.println(index);
        System.out.println(a[100004][5]);
    }
}

Measured memory_bytes: 33772
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b) { return b ? GCD(b, a%b) : a; }
int main(){
    ll n;
    cin>>n;
    vector<ll> x(n);
    for(int i=0; i<n; i++) cin>>x[i];
    int sum=0;
    for(int i=0; i<n; i++) sum+=x[i];
    ll sum_2=0;
    for(int i=0; i<n; i++) sum_2+=x[i]*x[i];
    ll ans=1e9;
    for(ll i=-1e5; i<1e5; i++){
        if(ans>(sum_2+(n*i*i)+(-2*sum*i))){
            ans=sum_2+(n*i*i)+(-2*i*sum);
            //cout<<i<<endl;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

using ll = long long;
using namespace std;

int main() {
    vector<int> a(9);
    for (int i=0; i<9; i++) {
        cin >> a.at(i);
    }
    for (int a_1=0; a_1<=100; a_1++) {
        int b_1 = a.at(0) - a_1, b_2 = a.at(1) - a_1, b_3 = a.at(2) - a_1;
        int a_2 = a.at(3) - b_1, a_3 = a.at(6) - b_1;
        if (a.at(4) == a_2+b_2 && a.at(5) == a_2+b_3 && a.at(7) == a_3+b_2 && a.at(8) == a_3+b_3) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
/*input
1 1
snuke
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}
int main()
{
	IOS;
	string s;
	cin>>s;
	cin>>s;
	cout<<"A";
	cout<<s[0];
	cout<<"C";
	
	return 0;
}


Measured memory_bytes: 256
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())

    def F(N):
        if N & 1:
            return 0
        N //= 2
        x = 0
        while N:
            N //= 5
            x += N
        return x

    answer = F(N)
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
const int N = (int)(1e5) + 5;
vi g[N];
int C[N];
int dp[N];
bitset < 20005 > cnt;
int main(void)
{
    int n;
    cin>>n;
    for (int i = 2;i <= n;++i)
    {
        int par;
        cin>>par;
        g[par].pb(i);
    }
    for (int i = 1;i <= n;++i)
        cin>>C[i];
    for (int i = n;i;--i)
    {
        for (int j = 0;j <= 2e4;++j)
            cnt[j] = 0;
        int sum = 0;
        for (auto it : g[i])
            sum += dp[it] + C[it];
        cnt[0] = 1;
        for (auto it : g[i])
            cnt = (cnt << dp[it]) | (cnt << C[it]);
        int mx = -1;
        for (int j = 0;j <= C[i];++j)
            if (cnt[j])
                mx = j;
        if (mx == -1)
            return puts("IMPOSSIBLE") * 0;
        dp[i] = sum - mx;
    }
    puts("POSSIBLE");
    return 0;
}


Measured memory_bytes: 2688
import sys
sys.setrecursionlimit(300000)
from decimal import Decimal, getcontext
getcontext().prec = 32

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')
from math import floor

A, B = input().split()
A = Decimal(A)
B = Decimal(B)
print(floor(A * B))

Measured memory_bytes: 71460
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define ll long long
#define DE(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG(a) DE("DEBUG: %d\n",a)
int read() {
	int x=0,f=1,ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=100000+10;

int n,x[MAXN],f[MAXN][20];

int binary_search(int k) {
	int l=1,r=n;
	while(l<r) {
		int mid=(l+r+1)>>1;
		if(x[mid]<=k) l=mid;
		else r=mid-1;
	}

	return r;
}

int main() {
	n=read();
	REP(i,1,n) x[i]=read();
	
	int l=read(),q=read();
	
	REP(i,1,n) f[i][0]=binary_search(x[i]+l);
	
	//DE("\n");REP(i,1,n) DE("%d ",f[i][0]);DE("\n");
	REP(j,1,16) REP(i,1,n) f[i][j]=f[f[i][j-1]][j-1];

	while(q--) {
		int a=read(),b=read();
		if(a>b) swap(a,b);
		int ans=0;
		DREP(i,16,0) {
			if(f[a][i]<b) a=f[a][i],ans+=(1<<i); 
		}

		printf("%d\n",ans+1);
	}
}

Measured memory_bytes: 9088
N = input()
T = [N]*(N+1)
T[0] = 0
for i in range(1,N+1):
  for j in xrange(20):
    if i-9**j<0:
      break
    T[i] = min(T[i], T[i-9**j]+1)
  for j in xrange(20):
    if i-6**j<0:
      break
    T[i] = min(T[i], T[i-6**j]+1)
print T[N]


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


int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  vector<int> v(n);
  for(int i = 0 ; i < n ; i++) cin >> v[i];
  int cnt = 0;
  for(int i = 1 ; i < n ; i++){
    if(v[i]==v[i-1] && v[i-1] != -1){
      v[i] = -1;
      cnt ++;
    }
  }
  cout << cnt;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

void run (void) {
  i32 h, w;
  scanf ("%" SCNi32 "%" SCNi32, &h, &w);
  i32 *dp = ALLOC (w + 1, i32) + 1;
  char *s = ALLOC (w + 1, char);
  const i32 mod = 1000000007;
  dp[0] = 1;
  while (h--) {
    scanf ("%s", s);
    for (i32 i = 0; i < w; ++i) {
      if (s[i] == '#') {
        dp[i] = 0;
      } else {
        dp[i] = (dp[i] + dp[i - 1]) % mod;
      }
    }
  }
  printf ("%" PRIi32 "\n", dp[w - 1]);
}

int main (void) {
  run();
  return 0;
}

Measured memory_bytes: 128
N=int(input())
MOD=10**9+7
MAX=N+1
def powermod(base,ind):
  if ind==1:
    return base
  elif ind%2==0:
    return (powermod(base,ind//2)**2)%MOD
  else:
    return ((powermod(base,ind//2)**2)*base)%MOD

print((powermod(10,N)-2*powermod(9,N)+powermod(8,N))%MOD)

Measured memory_bytes: 9188
mod=10**9+7

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

# ===========================素数判定 1:2以上の素数　,0：倍数    
def isPrime(x):
    if x < 2:
        return 0
    elif x == 2:
        return 1
    if x%2 == 0:
        return 0
    ir=int(x**(0.5))+1
    for i  in range(3,ir,2) :
        if x%i == 0:
            return 0
    return 1

n=int(input())

p=[]
for i in range(n+1):
    if isPrime(i):
        p.append([i,0])
        
for i in range(2,n+1):
    for j in range(len(p)):
        ii=i
        ip=0
        while ii>=p[j][0]:
            if ii%p[j][0]==0:
                ip=ip+1
                ii=ii//p[j][0]
            else:
                break
        p[j][1]=p[j][1]+ip

psum=1
for j in range(len(p)):
    if p[j][1]!=0:
        psum=mul(psum,p[j][1]+1)

print(psum)
        


Measured memory_bytes: 3064
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

size_l=(10**5)+5
kaijoy=[1]*(size_l)
inv = [0]*(size_l)
pre=1
for i,v in enumerate(kaijoy[1:], 1):
	pre *= i
	pre %= mod
	kaijoy[i]=pre

inv[-1] = modinv(kaijoy[-1], mod)
pre = inv[-1]
#print(pre*24)
for i, v in enumerate(inv[1:],1):
	pre *= (size_l-i)
	pre %= mod
	inv[-i-1]=pre
	
#print(kaijoy)
#print(inv)
#print([(v*s)%mod for v, s in zip(kaijoy, inv)])

def conv(n, k):
	if n < k:
		return 0
	
	global kaijoy
	global inv
	ret = kaijoy[n]
	ret *= inv[n-k]
	ret *= inv[k]
	return ret

def main():
	# = int(input())
	n, k = tin()
	#s = input()
	al = lin()
	al.sort()
	ret = 0
	
	for i in range(n-k+1):
		d= (al[-i-1] - al[i])*conv(n-i-1, k-1)
		#pa((d,kaijoy[max(0,n-i-1)],inv[k-1]))
		ret += d
		ret %= mod
	return ret
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

long long onum[3100][3100];
long long inum[3100][3100];

int main() {
    int N, M; cin >> N >> M;
    vector<string> fi(N);
    for (int i = 0; i < N; ++i) cin >> fi[i];

    // O
    for (int i = 0; i < N; ++i) {
        vector<long long> sum(M+1, 0);
        for (int j = 0; j < M; ++j) {
            int add = 0;
            if (fi[i][j] == 'O') ++add;
            sum[j+1] = sum[j] + add;
        }
        for (int j = 0; j < M; ++j) {
            onum[i][j] = sum[M] - sum[j+1];
        }
    }

    // I
    for (int j = 0; j < M; ++j) {
        vector<long long> sum(N+1, 0);
        for (int i = 0; i < N; ++i) {
            int add = 0;
            if (fi[i][j] == 'I') ++add;
            sum[i+1] = sum[i] + add;
        }
        for (int i = 0; i < N; ++i) {
            inum[i][j] = sum[N] - sum[i+1];
        }
    }

    long long res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (fi[i][j] != 'J') continue;
            res += onum[i][j] * inum[i][j];
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 169140
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

alias sread = () => readln.chomp();
ulong MOD = 1_000_000_007;
ulong INF = 1_000_000_000_000;
ulong MIDDLE = 100_000;
alias Pair = Tuple!(long, "flag", long, "num");

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}

void main()
{
    auto x = lread();
    long current, t = 1;
    while(current < x)
        current += t++;
    
    (t - 1).writeln();
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

int lg(LL v){
	int ret=0;
	while(v){
		v/=10;
		ret++;
	}
	return ret;
}
LL rev(LL v,int d){
	LL ret=0;
	for(int i=0;i<d;i++){
		ret*=10;
		ret+=v%10;
		v/=10;
	}
	return ret;
}
LL rev(LL v){
	LL ret=0;
	while(v){
		ret*=10;
		ret+=v%10;
		v/=10;
	}
	return ret;
}
vector<int> ret2;
vector<int> ret3;
LL g(LL D){
	LL ret=0;
	LL l=lg(D);
	LL u=pow(10,2*l);
	for(int k=0;k<=u;k++){
		if(rev(k)==k+D){
			ret++;
			cerr << k << endl;
			ret2.push_back(k);
		}
	}
	return ret;
}
LL f(LL D){
	LL z=0;
	while(D%10==0){
		z++;
		D/=10;
	}
	int d=lg(D);
	//cerr << d << endl;
	int h=d/2+1;
	LL p=1;
	for(int i=0;i<h;i++){
		p*=10;
	}
	LL q=p/10;
	//cerr << p << ", " << q << endl;
	LL ret=0;
	vector<LL> vs;
	if(d%2==0){
		for(int k=0;k<q;k++){
			LL v=(D+k)%q;
			LL u=rev(v,h-1)*q+k;
			//cerr << k << ": " << v << ", " << u << endl;
			if(z){
				if(rev(u,d)==u+D){
					ret++;
					ret3.push_back(u);
				}
			}
			else
			if(rev(u)==u+D){
				//cerr << u << endl;
				ret++;
					ret3.push_back(u);
			}
		}
		for(int k=0;k<p;k++){
			LL v=(D+k)%p;
			LL u=rev(v,h-1)*p+k;
			if(z){
				if(rev(u,d+1)==u+D){
					ret++;
					ret3.push_back(u);
				}
			}
			else if(rev(u)==u+D){
				//cerr << u << endl;
				ret++;
					ret3.push_back(u);
			}
		}
	}
	else{
		for(int k=0;k<p;k++){
			LL v=(D+k)%p;
			LL u=rev(v,h-1)*p+k;
			if(z){
				if(rev(u,d)==u+D){
					ret++;
					ret3.push_back(u);
				}
			}
			else if(rev(u)==u+D){
				ret++;
					ret3.push_back(u);
			}
		}
		for(int k=0;k<p;k++)
		{
			LL v=(D+k)%p;
			LL u=rev(v,h)*p+k;
			if(z){
				if(rev(u,d+1)==u+D){
					ret++;
					ret3.push_back(u);
				}
			}
			else if(rev(u)==u+D){
				//cerr << u << endl;
				ret++;
					ret3.push_back(u);
			}
		}
	}
	if(z){
		for(int i=1;i<z;i++){
			ret*=10;
		}
		ret*=9;
	}

	return ret;
}
LL ds[19];
LL h2(LL D,int i,int L, LL p){
	if(i==L/2){
		if(D==0){
			return p;
		}
		else{
			return 0;
		}
	}
	LL ret=0;
	int j=-9;
	LL v=ds[L-i-1]-ds[i];
	while(v*j+D<=0&&j<=9){
		j++;
	}
	if(j-1>=-9){
		LL m=10-abs(j-1);
		if(i==0&&j-1<=0){
			m--;
		}
		ret+=h2(D+v*(j-1),i+1,L,p*m);
	}
	if(j<=9){
		LL m=10-abs(j);
		if(i==0&&j<=0){
			m--;
		}
		ret+=h2(D+v*j,i+1,L,p*m);
	}
	return ret;
}
LL h(LL D){
	ds[0]=1;
	for(int i=1;i<19;i++){
		ds[i]=ds[i-1]*10;
	}
	LL l=lg(D);
	LL ret=0;
	for(int i=1;i<=2*l;i++){
		ret+=h2(D,0,i,i%2?10:1);
	}

	return ret;
}
int main() {
#if 0
	for(int i=1;i<1000;i++){
		if(f(i)!=h(i)){
			cerr << f(i) << ", " << h(i) << endl;
			break;
		}
	}
	return 0;
#endif
	LL D;
	cin >> D;
	cout << h(D) << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int , input().split()))
ans = []
bns = []
for i in A:
    if i % 2 == 0:
        ans.append(i)
for i in ans:
    if i % 3 == 0 or i % 5 == 0:
        bns.append(i)
if len(ans) == len(bns):
    print('APPROVED')
else:
    print('DENIED')

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

int main() {
	int n;
	cin >> n;
	vector<int> a(4);
	for (int i = 0; i < 4; i++) {
		a[i] = n % 10;
		n /= 10;
	}
	if ((a[0]==a[1]&&a[1]==a[2])||(a[1]==a[2]&&a[2]==a[3]))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cmath>
#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>
using namespace std;
#define EPS 1E-10

// 円に内接する多角形の面積を求める
double get_area(const vector<int>& polygon, double r)
{
	assert(accumulate(polygon.begin(), polygon.end(), 0) == 360);
	double S = 0.0;

	for (int n : polygon) {
		S += sin(n * M_PI / 180.0);
	}

	return S * r * r / 2;
}

int main()
{
	int m, n;

	while (cin >> m && m != 0) {
		vector<int> v1, v2;

		for (int i = 0, j; i < m - 1; i++) {
			cin >> j;
			v1.push_back(j);
		}
		v1.push_back(360 - accumulate(v1.begin(), v1.end(), 0));

		cin >> n;

		for (int i = 0, j; i < n - 1; i++) {
			cin >> j;
			v2.push_back(j);
		}
		v2.push_back(360 - accumulate(v2.begin(), v2.end(), 0));
		
		double S1 = get_area(v1, 1);
		double S2 = get_area(v2, 1);

		if (abs(S1 - S2) < EPS) {
			cout << '0' << endl;
		} else if (S1 > S2) {
			cout << '1' << endl;
		} else {
			cout << '2' << endl;
		}
	}
}

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

struct Kousha{
  int year;
  string name;
};

int main(){
  Kousha kousha[51];
  int n,q; cin >> n >> q;
  string ans = "none";
  kousha[0].year = 0;
  kousha[0].name = "kogakubu10gokan";
  
  for( int i = 1; i <= n; i++ ) cin >> kousha[i].year >> kousha[i].name;

  for( int i = 0; i <= n; i++ ){
    if( kousha[i].year <= q && kousha[i+1].year > q ){
      ans = kousha[i].name;
    }
  }
  if( ans == "none" ) cout << kousha[n].name << endl;
  else cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
using namespace std;
int main(){
  string g;
  cin>>g;
  if(g.at(0)==g.at(1)&&g.at(0)==g.at(2)) cout<<"Yes"<<endl;
  else if(g.at(1)==g.at(2)&&g.at(1)==g.at(3)) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

int main()
{

        int N, M;
        cin >> N >> M;
        vector<vector<int>> G(N);
        for (int i = 0; i < M; ++i) {
                int a, b;
                cin >> a >> b;
                G[a-1].push_back(b-1);
                G[b-1].push_back(a-1);
        }
#if 0
        for (int i = 0; i < N; ++i) {
                int len = G[i].size();
                for (int j = 0; j < len; ++j) {
                        cout << G[i][j] << " ";
                }
                cout << endl;
        }
#endif

        vector<int> dist(N, -1);
        queue<int> que;

        dist[0] = 0;
        que.push(0);
        int num = 1;

        while (1) {

                if (que.empty()) break;

                int v = que.front();
                que.pop();

                int l = G[v].size();
                for (int i = 0; i < l; ++i) {
                        int nv = G[v][i];
                        if (dist[nv] != -1) continue;
                        dist[nv] = v+1;
                        que.push(nv);
                        num++;
                }


        }

        if (num != N) {
                cout << "No" << endl;
        }
        else {
                cout << "Yes" << endl;
                for (int i = 1; i < N; ++i) {
                        cout << dist[i] << endl;
                }
        }
}


Measured memory_bytes: 10212
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,t,ans=0;
  cin >> n >> t;
  long long a[n];
  for(long long i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n-1;i++){
    if(a[i]+t<=a[i+1]){
      ans+=t;
    }else{
      ans+=a[i+1]-a[i];
    }
  }
  ans+=t;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int N,M;
long a[50],b[50],c[50],d[50];
main()
{
    cin>>N>>M;
    for(int i=0;i<N;++i){
        cin>>a[i]>>b[i];
    }
    for(int i=0;i<M;++i){
        cin>>c[i]>>d[i];
    }
    for(int i=0;i<N;++i){
        int p=0;
        for(int j=0;j<M;++j){
            if(abs(a[i]-c[j])+abs(b[i]-d[j])<abs(a[i]-c[p])+abs(b[i]-d[p])){
                p=j;
            }
        }
        cout<<p+1<<endl;
    }
}

Measured memory_bytes: 3580
import Data.List

chk s [] = []
chk s (x:xs) =
  if x >= 2
  then (s-(x-2)+2):(chk s xs)
  else (chk s xs)

ans' :: [Int] -> String
ans' l =
  let s = sum $ map (\x -> if x >= 1 then 1 else 0) l
      r = map (\x -> if x >= 1 then x-1 else 0) l
  in
    if nub(r) /= [0]
    then show (s+1)
    else "NA"

ans ("0":_) = []
ans (_:l:s) =
  let i = map read $ words l :: [Int]
      o = ans' i
  in
    o:(ans s)
    
main = do
  c <-getContents
  let i = lines c
      o = ans i
  mapM_ putStrLn o

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

int main()
{
    int num;
    std::cin >> num;
    std::string name;
    std::string tar("MARCH");
    long long list[5] = {0};
    for (int i = 0; i < num; i++)
    {
        std::cin >> name;
        for (int j = 0; j < 5; j++)
        {
            if (name[0] == tar[j])
            {
                list[j]++;
            }
        }
    }
    long long cnt = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = i + 1; j < 4; j++)
        {
            for (int k = j + 1; k < 5; k++)
            {
                cnt += list[i] * list[j] * list[k];
            }
        }
    }
    std::cout << cnt;
    return 0;
}

Measured memory_bytes: 256