akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
long modpow(long a, long b,long mod){
	long res = 1;
	while (b > 0){
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b /= 2;
	}
	return res;
}
int main(){
    int n;
    string s;
    cin >> n >> s;
    int one=0;
    for(int i=0;i<n;i++)if(s[i]=='1')one++;
    long plus[n+1];
    long minus[n+1];
    long sum_plus=0;
    long sum_minus=0;
    for(long i=0;i<n;i++){
        if(one!=n){
            plus[i]=modpow(2L,i,(long)(one+1));
            if(s[n-1-i]=='1')sum_plus=(sum_plus+plus[i])%((long)(one+1));
        }
        if(one>1){
            minus[i]=modpow(2L,i,(long)(one-1));
            if(s[n-1-i]=='1')sum_minus=(sum_minus+minus[i])%((long)(one-1));
        }
    }
    for(int i=0;i<n;i++){
        long tmp;
        int ans=0;
        if(s[i]=='0'){
            tmp = (sum_plus + plus[n-1-i])%((long)(one+1));
            ans++;
            while(tmp>0){
                tmp = tmp % __builtin_popcount((int)tmp);
                ans++;
            }
            cout << ans << endl;
        }
        else{
            if(one==1)cout << 0 << endl;
            else{
            tmp = (sum_minus + one - 1 - minus[n-1-i])%((long)(one-1));
            ans++;
            while(tmp>0){
                tmp = tmp % __builtin_popcount((int)tmp);
                ans++;
            }
            cout << ans << endl;
            }
        }
    }
}

Measured memory_bytes: 6876
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

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

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);	
	
	int N, D; cin >> N >> D;
	D = 2*D+1;
	cout << (N+D-1)/D << endl;

    return 0;
}

// read the question correctly (ll vs int)
// template by bqi343


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int n; cin>>n;
    while(1){
        char ope; cin>>ope;
        if(ope=='='){
            cout<<n<<endl;
            break;
        } else{
            int i; cin>>i;
            if(ope=='+') n+=i;
            else if(ope=='-') n-=i;
            else if(ope=='*') n*=i;
            else if(ope=='/') n/=i;
        }
    }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,k,ma,cou,ans;
  cin>>a>>b>>k;
  cou=0;
  ma=max(a,b);
  for(int i=ma; i>0; i--){
    if(a%i==0 && b%i==0){
      cou++;
    }
    if(cou==k){
      ans=i;
      break;
    }
  }
  cout<<ans;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000
int main(){
  int i,j,p=0,r,n,t,x;
  int A[MAX];
  scanf("%d",&n);
  for(r=0;r<n;r++){
    scanf("%d",&A[r]);
  }
  //r=12 current point
  x=A[r-1];//A[r],r=0-11or[12]
  i=p-1;//i=-1
  for(j=p/*p=0*/;j<r-1/*n-2*/;j++){
    if(A[j]<=x/*end number compare*/){
      i+=1;
      t=A[i];
      A[i]=A[j];
      A[j]=t;
    }
  }
  t=A[i+1];// next to i number exchange
  A[i+1]=A[r-1];
  A[r-1]=t;

  for(j=0;j<n;j++){
    if(j==i+1)printf("[");
    printf("%d",A[j]);
    if(j==i+1)printf("]");
    if(j<n-1)printf(" ");
    }
 // printf("%d",r);
  printf("\n");
  return 0;
}

Measured memory_bytes: 996
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

int main()
{
    long long n, k;
    std::cin >> n >> k;

    std::string s;
    std::cin >> s;

    std::vector<long long> pos;
    pos.push_back(0);

    for (int i = 0; i < n - 1; i++) {
        if (s[i] != s[i + 1]) {
            pos.push_back(i + 1);
        }
    }

    pos.push_back(n);

    long long ans = 0;

    for (auto i = 0; i < pos.size() - 1; i++) {
        long long end_pos = 0;
        if (s[pos[i]] == '0') {
            end_pos = i + 2 * k;
        } else {
            end_pos = i + 2 * k + 1;
        }

        if (end_pos >= pos.size()) {
            end_pos = pos.size() - 1;
        }

        ans = std::max(ans, pos[end_pos] - pos[i]);
    }

    std::cout << ans << std::endl;
}


Measured memory_bytes: 1528
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs
#include <cstdio>	// require printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>	// require tolower, toupper
#include <fstream>	// require freopen
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
//	cut here before submit 
//	freopen ("testcase.swap_cipher", "r", stdin );
	int n;
	string str;

	while (cin >> n && n ){
		cin >> str;
		vector <P> ab (n );
		rep (i, n ){
			int a, b;
			cin >> a >> b;
			a--; b--;
			ab[i].first = a;ab[i].second = b;
		} 
		for (int i = n - 1; i >= 0; i-- ){
			string tmp = str;
			int diff = abs (ab[i].second - ab[i].first );
			swap (tmp[ab[i].first], tmp[ab[i].second] );
			tmp[ab[i].first] = (26 + diff + tmp[ab[i].first] - 'a' ) % 26 + 'a';
			tmp[ab[i].second] = (26 + diff + tmp[ab[i].second] - 'a' ) % 26 + 'a';
//			cout << tmp << endl;
			str = tmp;
		} // end rep
		cout <<  str << endl;
	} // end while
	

	return 0;
}

Measured memory_bytes: 0
import numpy as np

N = int(input())
A = list(map(int, input().split()))

B = list(set(A))
B.sort()
C = np.asarray(B)

while(len(C)>1):
    t = C[0]
    C = np.append(C[1:]%t,t)
    C = list(set(C))
    C.sort()
    if C[0]==0:
        C = np.asarray(C[1:])
    else:
        C = np.asarray(C)

print(C[0])

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

using namespace std;

int main(){
  string a, b;
  cin >> a >> b;
  string ans = "EQUAL";
  if(a.length() < b.length()) ans = "LESS";
  else if(a.length() > b.length()) ans = "GREATER";
  else{
    for(int i = 0; i < a.length(); i++){
      if(a[i] < b[i]){
        ans = "LESS";
        break;
      }else if(a[i] > b[i]){
        ans = "GREATER";
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long K = sc.nextLong();
		int[] A = new int[N];
		int[][] B = new int[N][2];
		for (int i = 0; i < N; ++i) {
			A[i] = sc.nextInt();
			B[i] = new int[] { A[i], i };
		}

		Arrays.sort(B, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] != o2[0])
					return Integer.compare(o1[0], o2[0]);
				else
					return Integer.compare(o1[1], o2[1]);
			}
		});

		long[][] sum = new long[N][60];
		int[][] dst = new int[N][60];
		for (int i = 0; i < sum.length; ++i)
			for (int j = 0; j < sum[i].length; ++j)
				sum[i][j] = -1;
		for (int i = 0; i < N; ++i) {
			int j = i;
			while (j + 1 < N && B[j][0] == B[j + 1][0]) {
				dst[B[j][1]][0] = (B[j + 1][1] + 1) % N;
				sum[B[j][1]][0] = B[j + 1][1] - B[j][1] + 1;
				++j;
			}
			sum[B[j][1]][0] = N + B[i][1] - B[j][1] + 1;
			dst[B[j][1]][0] = (B[i][1] + 1) % N;
			i = j;
		}
		for (int i = 0; i + 1 < sum[0].length; ++i) {
			for (int j = 0; j < N; ++j) {
				sum[j][i + 1] = Math.min(sum[j][i] + sum[dst[j][i]][i], Long.MAX_VALUE / 3);
				dst[j][i + 1] = dst[dst[j][i]][i];
			}
		}

		long res = K * N;
		int pos = 0;
		while (res > 0) {
			int ok = -1;
			int ng = 60;
			while (ng - ok > 1) {
				int middle = (ok + ng) / 2;
				if (sum[pos][middle] > res) {
					ng = middle;
				} else {
					ok = middle;
				}
			}
			if (ok == -1)
				break;
			res -= sum[pos][ok];
			pos = dst[pos][ok];
		}

		ArrayDeque<Integer> dq = new ArrayDeque<>();
		while (res > 0) {
			if (res >= sum[pos][0]) {
				res -= sum[pos][0];
				pos += sum[pos][0];
			} else {
				dq.addLast(A[pos]);
				++pos;
				--res;
			}
			pos %= N;
		}
		PrintWriter pw = new PrintWriter(System.out);
		while (!dq.isEmpty()) {
			pw.print(dq.pollFirst() + (dq.isEmpty() ? "\n" : " "));
		}
		pw.close();
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 294228
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(f) (f).begin(),(f).end()
#define allr(f) (f).rbegin(),(f).rend()
const int mod = 1e9+7, A = 1e2+5;
using namespace std;
int solve(string a, string tmp)
{
	int cnt = 1;
	do{
		if (a == tmp)
			break;
		cnt++;
	} while (next_permutation(all(tmp)));
	return cnt;
}
int main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	string a, b, s;
	for (int i = 0, x; i < n; i++)
		cin >> x, a.pb(x);
	for (int i = 0, x; i < n; i++)
		cin >> x, b.pb(x);
	for (int i = 0; i < n; i++)
		s.pb(i+1);
	int x = solve(a, s), y = solve(b, s);
	cout << abs(x - y);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値

using namespace std;
using ll = long long int;

int main(void){
    int K,N;cin>>K>>N;
    int A1,A2;cin >> A2;
    int a1 = A2 + K;
    int ans = 0;
    for(int i=0;i<N-1;i++){
        A1 = A2;
        cin >> A2;
        if(A2-A1>ans) ans = A2 - A1;
    }
    if(a1-A2>ans) ans = a1 - A2;
    cout << K - ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(void) {
  string s;
  cin>>s;
  int n=stoi(s);
  int x=0;
  for(auto it=s.begin(); it!=s.end(); it++) {
    x+=(*it)-'0';
  }
  if(n%x==0) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//int N;
//int num=0;
//vector<char> S;
//int cnt=2;
string S;
void solve(){
    cin>>S;
    if(S[0]!='A'){cout<<"WA"<<endl;return;}
    bool ch=false;
    for(int i=2;i<(S.length()-1);i++){
        if(S[i]=='C')ch=true;
    }
    if(ch==false){cout<<"WA"<<endl;return;}
    int cnt=0;
    for(int j=0;j<S.length();j++){
        if(S[j]<='Z')cnt++;
    }
    if(cnt!=2){cout<<"WA"<<endl;return;}
    cout<<"AC"<<endl;
}
int main(){
    solve();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
using namespace std;

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		if (n == pow(2, i))return cout << pow(2, i) << endl, 0;
		else if (n < pow(2, i))return cout << pow(2, i-1) << endl,0;
	}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
int N,max=0,count=0,x=0,j;
cin>>N;
vector <int> d(N);
vector <int> shurui(N);
for(int i=0;i<N;i++){
    cin >> d.at(i);
    for(j=0;j<count;j++){
        if(shurui[j]==d[i]) x=1;
    }
    if(x==0) shurui[count++]=d[i];
    x=0;
}
   cout << count << endl;
}

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

int n, q;

int mx(int x, int y){return max(x, y);}
int zero(){return 0;}

int main(){
    cin >> n >> q;
    vector<int> a(n);
    for(auto &elem:a)cin >> elem;
    atcoder::segtree<int,
                     mx,
                     zero>seg(a);

    while(q--){
        int t, x, v, l, r;
        cin >> t;
        if(t == 1){
            cin >> x >> v;x--;
            seg.set(x, v);
        }
        if(t == 2){
            cin >> l >> r;l--,r--;
            cout << seg.prod(l, r+1) << endl;
        }
        if(t == 3){
            cin >> x >> v;x--;
            cout << seg.max_right(x, [&](int x){return x < v;}) + 1<< endl;
        }
    }
}

Measured memory_bytes: 5828
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

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

	vector<int> h(n);

	for (int i = 0; i < n; i++)
	{
		cin >> h.at(i);
	}

	int c = 1;
	int m = h.at(0);
	for (int i = 1; i < n; i++)
	{
		if (m <= h.at(i))
		{
			c++;

			m = h.at(i);
		}
	}
	cout << c << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=333,mod=1000000007;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,f[maxn*2][maxn][maxn],cnt1,cnt2,ans;
bool vis[maxn*2],ind[maxn*2];
int main(){
	n=read();
	FOR(i,1,n){
		int x=read(),y=read();
		if(~x && ~y) vis[x]=vis[y]=true;
		else if(~x) ind[x]=true,cnt2++;
		else if(~y) ind[y]=true,cnt2++;
		else cnt1++;
	}
	f[2*n+1][0][0]=1;
	ROF(i,2*n,1) FOR(j,0,cnt1+cnt2) FOR(k,0,cnt2){
		if(vis[i]) f[i][j][k]=f[i+1][j][k];
		else if(ind[i]){
			if(k) f[i][j][k]=(f[i][j][k]+f[i+1][j][k-1])%mod;
			if(j!=cnt1+cnt2) f[i][j][k]=(f[i][j][k]+f[i+1][j+1][k])%mod;
		}
		else{
			if(j) f[i][j][k]=(f[i][j][k]+f[i+1][j-1][k])%mod;
			if(j!=cnt1+cnt2) f[i][j][k]=(f[i][j][k]+f[i+1][j+1][k])%mod;
			if(k!=cnt2) f[i][j][k]=(f[i][j][k]+1ll*(k+1)*f[i+1][j][k+1])%mod;
		}
	}
	ans=f[1][0][0];
	FOR(i,1,cnt1) ans=1ll*ans*i%mod;
	printf("%d\n",ans);
}
// fk

Measured memory_bytes: 261888
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

c = Counter(A).most_common()
c.sort(key=lambda x: x[0], reverse=True)

tmp = []
for i in range(len(c)):
    if c[i][1] >= 4 and len(tmp) == 0:
        print(c[i][0]**2)
        exit()
    elif c[i][1] >= 2:
        tmp.append(c[i][0])
    if len(tmp) == 2:
        print(tmp[0]*tmp[1])
        exit()
print(0)

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

typedef long long ll;

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


int main(){
    ll n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    ll g = gcd(n, m);
    ll l = n / g * m;
    ll sstep = n / g;
    ll tstep = m / g;
    for(int i=0; i<g; i++) {
        if(s[sstep*i] != t[tstep*i]) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << l << endl;
    
    return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void OUT(long a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
const int MOD=1e9+7;
int fact[1000001]={0},inv[1000001]={0};
static inline int ModPow(int a,int b){return b?1l*ModPow(1l*a*a%MOD,b>>1)*(b&1?a:1)%MOD:1;}
static inline void init(int sz)
{
  sz++;fact[0]=1;rep(i,sz-1)fact[i+1]=1l*fact[i]*(i+1)%MOD;
  inv[sz-1]=ModPow(fact[sz-1],MOD-2);
  rep(i,sz-1)inv[sz-2-i]=1l*inv[sz-1-i]*(sz-1-i)%MOD;
}
static inline int comb(const int n,const int k){if(k<0||n<k){return 0;}return 1l*fact[n]*inv[n-k]%MOD*inv[k]%MOD;}
static inline int P(const int n,const int k){if(k<0||n<k){return 0;}return 1l*fact[n]*inv[n-k]%MOD;}
int main(void)
{
  int S=IN();long A;init(S);
  rep(i,S/3){A=(A+1l*comb(S-(i+1)*3+i,S-(i+1)*3))%MOD;}
  return OUT(A),0;
}

Measured memory_bytes: 1528
while True:
    N = int(raw_input())
    if N == 0: break
    dic = {}
    for i in range(N):
        n, p, q = map(int, raw_input().split())
        if not n in dic:
            dic[n] = [i,p*q]
        else:
            dic[n][1] = dic[n][1]+p*q
            
    lis = [(v[0], k) for k, v in dic.items() if v[1] >= 1000000]
    if lis:
        for t in sorted(lis, key=lambda x: x[0]):
            print t[1]
    else:
        print 'NA'

Measured memory_bytes: 4468
#include <algorithm>
#include <cmath>
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

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

	int prev = 1e9;
	int cur = 0;

	long long sum = 0;
	for (int i = 0; i < n - 1; ++i)
	{
		cin >> cur;

		sum += min(prev, cur);

		prev = cur;
	}

	// An
	sum += cur;

	cout << sum << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <functional>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define PRINT1(table, D0) REP(d0, D0) cout<<table[d0]<<" "; cout<<"\n";
#define PRINT2(table, D0, D1) REP(d0, D0) { REP(d1, D1) cout<<table[d0][d1]<<" "; cout<<"\n"; }
#define PRINT3(table, D0, D1, D2) REP(d0, D0) { REP(d1, D1) { REP(d2, D2) cout<<table[d0][d1][d2]<<" "; cout<<"\n"; } cout<<"\n"; }
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }

#define MOD 1000000007LL
#define INF (1LL<<60)
ll ff(ll v) {
	ll ans=0;
	for(ll i=1;i<=v;i++) ans^=i;
	return ans;
}

ll f(ll v) {
	if(v<10) return ff(v);
	ll a=1;
	while(v>a) a=a<<1;
	a>>=1;
	return (((v-a)&1) ? 0 : a) ^ f(v^a);
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll A,B;
	while(cin>>A>>B) {


		ll ans=f(B)^f(A-1);
	
cout<<ans<<endl;
		
		
	}
	
	return 0;
}


Measured memory_bytes: 256
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>

using namespace std;

int main()
{
    int a, b;

    cin >> a >> b;

    if (a > b) {
        cout << a + a - 1 << endl;
    }
    else if (a == b) {
        cout << a + b << endl;
    }
    else {
        cout << b + b - 1 << endl;
        
    }
    return 0;
}



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

#define print(x) for(auto it : x) cout<< it << ' '; cout << '\n';
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string s; cin >> s;
    if (s == "RRR")
        cout << "3\n";
    else if (s == "RRS" || s == "SRR")
        cout << "2\n";
    else if (s == "SSS")
        cout << "0\n";
    else
        cout << "1\n";
    return 0;
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int N;
set< string > str_set;

void rec(string& str) {
	if (str.size() == 1 || str_set.count(str)) return;
	
	string lstr = str.substr(0, str.size() / 2);
	string rstr = str.substr(str.size() / 2);
	
	if (lstr != rstr) str_set.insert(str);
	rec(lstr);
	rec(rstr);
}

int main() {
	cin >> N;
	string str;
	cin >> str;
	rec(str);
	cout << str_set.size() << endl;
}

Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n;
  cin >> n;
  vl t(n);
  rep(i, n) cin >> t[i];
  
  ll sum=0;
  rep(i, n) sum += t[i];
  ll half=0, num;
  rep(i, n) {
    if(half>=sum/2) {num=i-1; break;}
    half += t[i];
  }
  cout << min(half*2-sum, sum-(half-t[num])*2) << newl;
  return 0;
}

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

int main(){
    int N; cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++){
        cin >> S.at(i); //S[i]ではなくS.at(i)
    }
    sort(S.begin(), S.end()); //いい感じに並べ替えてくれる書き方なので覚えよう！
    int i = 0, ans = 1;
    for ( int j = 1; j < N; j++){
        if ( S.at(i) != S.at(j)){ //並べ替えておいて、モノがかわったらansをたす
            ans++;
            i = j;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 9580
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
using namespace std;

int main() {
  int N = 0;
  int ans = 1;
  cin >> N;
  vector<int> A(N);
  rep(n, N){
    cin >> A[n];
  }

  // 次のインデックス
  // 0はじまりで用意
  int next = A[0]-1;
  if (next==1){
    cout << ans << endl;
    return 0;
  }
  // 問題文通りの処理を行う
  // 回数は鳩の巣原理よりN回で十分
  rep(n, N-1){
    next = A[next] - 1;
    ans ++;
    if (next==1){
      cout << ans << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 768
S = input()
ans = len(S) * (len(S)-1) // 2 + 1

for ch in 'abcdefghijklmnopqrstuvwxyz':
  n = S.count(ch)
  if n>0:
    #print(ch,n)
    ans -= n * (n-1) // 2
    
print(ans)

Measured memory_bytes: 3500
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <climits>
#include <cassert>
#include <algorithm>
#include <utility>

using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;

// 二つの値の最大値を求める関数
Int Max(const Int a, const Int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}
// 三つの値の最大値を求める関数
Int Max(const Int a, const Int b, const Int c) {
    return Max(a, Max(b, c));
}

int main(void) {
    Int a, b;
    cin >> a >> b;
    cout << Max(a + b, a - b, a * b) << endl;
    return 0;
}



Measured memory_bytes: 3608
N,M = list(map(int,input().split()))
path = [[False,False] for i in range(N)]
flag=False
for i in range(M):
    a,b = list(map(int,input().split()))
    if a==N:
        if path[b-1][0]:
            flag=True
            
        path[b-1][1]=True
    if a==1:
        if path[b-1][1]:
            flag=True
            
        path[b-1][0]=True
    if b==N:
        if path[a-1][0]:
            flag=True
            
        path[a-1][1]=True
    if b==1:
        if path[a-1][1]:
            flag=True
            
        path[a-1][0]=True

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 23540
using System;
using System.Collections.Generic;
using System.Linq;

namespace ziyuutyou
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = int.Parse(Console.ReadLine());
            var list = new List<int>();
            list.Add(s);

            for(var x=0; x<=1000000; ++x)
            {
                var y = list[x] * 3 + 1;
                var z = list[x] / 2;
                if (list[x] % 2 == 0)
                {
                    if(list.Contains(z))
                    {
                        Console.WriteLine(x+2);
                        break;
                    }
                    list.Add(z);
                }

                else
                {                                        
                    if (list.Contains(y))
                    {
                        Console.WriteLine(x+2);
                        break;
                    }
                    list.Add(y);
                }

            }
        }
        
    }
}


Measured memory_bytes: 13152
#include <cstdio>
static const int MAXN = 1e5 + 4;

int _n, n = 0, a_i, a[MAXN];

int main()
{
    scanf("%d", &_n);
    for (int i = 0; i < _n; ++i) {
        scanf("%d", &a_i);
        if (i == 0 || a_i != a[n - 1]) a[n++] = a_i;
    }
    //for (int i = 0; i < n; ++i) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');

    int ans = 0;
    for (int i = 0, j; i < n; i = j) {
        ++ans;
        for (j = i + 1; j < n; ++j) {
            if ((a[j] > a[j - 1]) ^ (a[i + 1] > a[i])) break;
        }
    }

    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define int long long
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
#define N 200005
int a[N],f[N];
int n,k;
bool cmp(int x,int y)
{
	return x>y;
}
bool judge(int x)
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]*f[i]<=x) continue;
		int ned=(x)/f[i];
		sum+=a[i]-ned;
	}
	return sum<=k;
}
signed main()
{
#ifdef __LOCAL__
	freopen("in.txt","r",stdin);
#endif
	cin>>n>>k;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) f[i]=read();
	sort(a+1,a+n+1);
	sort(f+1,f+n+1,cmp);
	int l=0,r=1e12+5,ans,mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(judge(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
#ifdef __LOCAL__
	printf("Time Used : %d\n",clock());
#endif
	return 0;
}



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

int main() {
	int n,m;
	cin>>n>>m;
	string s1,s2;
	for(int i=0;i<n;i++){
	    s1+=m+'0';
	}
	for(int i=0;i<m;i++){
	    s2+=n+'0';
	}
	if(n<=m){
	    cout<<s2<<endl;
	}
	else if(n>m){
	    cout<<s1<<endl;
	}

}

Measured memory_bytes: 3600
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#include<functional>
#define int long long
#define mod(int)(1000000007)
using namespace std;
const int INF = 1000000000000;
vector<int> prime_factor(int num) {
    vector<int>res;
    for (int i = 2; i <= num; i++) { // 他の素数で割っていく
        while (num % i == 0) {
			res.push_back(i);
            num /= i;
        }
    }
    return res;
}
int cnt[345678];
signed main() {
	int n, ans = 0; cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int h = 0; h < prime_factor(i).size(); h++) {
			cnt[prime_factor(i)[h]]++;
			//cout << i << ' ' << prime_factor(i)[h] << endl;
		}
	}
	int a = 0, b = 0, c = 0, d = 0, e = 0;
	for (int h = 2; h <= n; h++) {
		if (cnt[h] >= 74)ans++;
		if (cnt[h] >= 24)a++;
		if (cnt[h] >= 2)b++;
		if (cnt[h] >= 14)c++;
		if (cnt[h] >= 4)d++;
	}
	ans += a * (b - 1) + c * (d - 1) + (d * (d - 1) / 2) * (b - 2);
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int i, x, y, cnt[10], res;

void solve()
{
  int i = 3;
  while(i--) 
  {
    cin >> x >> y;
    cnt[x]++;
    cnt[y]++;
  }
  for(i = 1; i <= 4; i++) if(cnt[i] == 2) res++;
  if(res == 2) cout << "YES" << endl;
  	else cout << "NO" << endl;
}

int main()
{
  solve();
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

#a = [int(i) for i  in input().split()]

s = input()
a = len(s)
ok=0
for i in range(a):
    for j in range(i,a):
        c = s[:i]+s[j:]
#        print(c)
        if c == 'keyence':
            ok = 1
        
if ok:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 2940
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;

class program
{
    static long mod = 1000000007;
    static void Main(string[] args)
    {
        int[] input = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int N = input[0];
        int M = input[1];
        int[] indexes = index(M);
        BigInteger ans = 1;
        if (M!=1)
        {
            for (int i = 0; i < indexes.Count(); i++)
            {
                ans *= nHk(indexes[i]+N-1, N-1);
            }
        }

/*
        for (int i = 0; i < indexes.Length; i++)
        {
            Console.WriteLine(indexes[i]);
        }
*/

        Console.WriteLine(ans%mod);
    }

    static int[] index(int n)
    {
        var list = new List<int>();
        if (n==1)
        {
            list.Add(1);
        }
        else
        {
            int i = 2;
            int temp = 0;
            while (n!=1)
            {
                 if (n%i==0)
                 {
                    temp++;
                    n /= i;
                 }
                 else
                 {
                    if (temp != 0)
                    {
                        list.Add(temp);
                    }
                    temp = 0;
                    i++;
                 }
            }
            list.Add(temp);
        }
        int[] res = list.ToArray();
        return res;
    }

    static BigInteger nHk(int n, int r)
    {
        if (n < 0 || r < 0 || r > n) throw new ArgumentException("不正な引数です．");

        if (n - r < r) r = n - r;
        if (r == 0) return 1;
        if (r == 1) return n;

        int[] numerator = new int[r];
        int[] denominator = new int[r];

        for (int k = 0; k < r; k++)
        {
            numerator[k] = n - r + k + 1;
            denominator[k] = k + 1;
        }

        for (int p = 2; p <= r; p++)
        {
            int pivot = denominator[p - 1];
            if (pivot > 1)
            {
                int offset = (n - r) % p;
                for (int k = p - 1; k < r; k += p)
                {
                    numerator[k - offset] /= pivot;
                    denominator[k] /= pivot;
                }
            }
        }
        BigInteger result = BigInteger.One;
        for (int k = 0; k < r; k++)
        {
            if (numerator[k] > 1) result *= numerator[k];
        }

        return result;
        /*
        long result;
        long temp1 = 1;
        for (int i = k; i < n+k; i++)
        {
            temp1 *= i;
            temp1 %= 
        }
        long temp2 = 1;
        for (int i = 1; i <= n ; i++)
        {
            temp2 *= i;
        }
        result = temp1 / temp2;
        Console.WriteLine(result);
        return result;
        */
    }
}

Measured memory_bytes: 13652
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n,k; cin>>n>>k;
    ll x;
    ll sm=0;
    vector<int>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a.rbegin(),a.rend());
    for(int i=k;i<a.size();i++)
    {
        sm+=a[i];
    }
    cout<<sm;
    
}


Measured memory_bytes: 1024
import scala.io.StdIn._

object Main extends App {


  val n = readInt()
  val as = readLine().split(" ").map(_.toInt)

  def solve() = {
    as.zipWithIndex.foldLeft(0) { case (acc, (num, i)) =>
      if((i+1)%2 != 0 && num %2 != 0) acc+1 else acc
    }
  }

  println(solve())

}



Measured memory_bytes: 54620
mod = 10**9+7
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [[0]*(C+1) for i in range(N+1)]
dp[-1][0] = 1
S = [[0]*(C+1) for _ in range(N+1)]
for i in range(N):
    power = [1]*(400+1)
    for j in range(C+1):
        for x in range(A[i], B[i]+1):
            S[i][j]+=power[x]
            S[i][j]%=mod
            power[x]*=x
            power[x]%=mod
for i in range(N):#iばんめ
    for j in range(C+1):#jこのキャンディー
        for k in range(j+1):#iばんめにk子くばる
            dp[i][j] += dp[i-1][j-k]*S[i][k]
            dp[i][j]%=mod
print(dp[-2][-1])



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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    long long n; cin >> n;
    vector<int> c(n);
    for (auto &x: c) cin >> x;
    vector<vector<int>> e(n);
    vector<long long> ans(n+1, n * (n+1) / 2);
    vector<stack<int>> s(n+1);
    vector<vector<int>> sv(n);
    vector<long long> sz(n, 1);
    vector<long long> r(n+1, n);
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    auto f = [&](auto f, int curr, int prev) -> void {
        if (!s[c[curr]].empty()) sv[s[c[curr]].top()].emplace_back(curr);
        s[c[curr]].push(curr);
        for (auto &to: e[curr]) {
            if (to == prev) continue;
            f(f, to, curr);
            sz[curr] += sz[to];
            long long rem = sz[to]+1;
            for (auto &xto: sv[curr]) {
                rem -= sz[xto];
            }
            sv[curr].clear();
            r[c[curr]] -= rem - 1;
            ans[c[curr]] -= (rem-1) * (rem) / 2;
        }
        r[c[curr]]--;
        s[c[curr]].pop();
    };
    f(f, 0, -1);
    for (int i = 1; i <= n; i++) {
        ans[i] -= (r[i]+1) * (r[i]) / 2;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 190800
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int main()
{
	int n[3];
	for (int i = 0; i < 3; i++) { cin >> n[i]; }
	sort(n, n + 2);
	if (n[0]<n[2]&&n[1]>n[2]) {
		cout << "Yes" << endl;
	}
	else { cout << "No" << endl; }
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    R = [list(map(int,input().split())) for i in range(N)]
    B = [list(map(int,input().split())) for i in range(N)]
    R.sort(key=lambda x:x[1])
    R.sort()
    B.sort(key=lambda x:x[1])
    B.sort()
    ret = 0
    for b in B:
        pairfg = False
        pair = [1000, -1000]
        for r in R:
            if r[0] < b[0] and r[1] < b[1]:
                if r[1]>pair[1]:
                    pairfg = True
                    pair = r
        if pairfg:
            ret += 1
#            print(pair,b)
            R.remove(pair)
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <iostream>
#include <string>
 
using namespace std;
 
int main(){
 
int a;
int b;
cin >> a;
cin >> b;
 
int num = 0;
int count = 1;
while(true){
  if(count >= b){
    
    break;
  
  }
  
  num++;
  count+= (a-1);
 
}
  cout << num;
}

Measured memory_bytes: 256
MOD = 998244353
n, m, k = map(int, input().split())

MAX = 2 * 10**5 + 5
fact = [1] * (MAX + 1)  # i!
finv = [1] * (MAX + 1)  # (i!)^{-1}
iinv = [1] * (MAX + 1)  # i^{-1}
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * iinv[i] % MOD


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n - k] % MOD


mm = [1]
for j in range(n):
    mm.append((mm[-1] * (m - 1)) % MOD)
# print(mm)
dp = [(comb(n - 1, j) * m * mm[n - 1 - j]) % MOD for j in range(k + 1)]
# print(dp)

ans = sum(dp) % MOD
print(ans)


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



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef vector< vector< vector<ll> > > vvvint;
typedef vector<string> vstring;
typedef vector< vector<string> > vvstring;
typedef vector<char> vchar;
typedef vector< vector<char> > vvchar;
typedef vector<long double> vdouble;
typedef vector< vector<long double> > vvdouble;
typedef vector< vector< vector<long double> > > vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ALL(obj) (obj).begin(), (obj).end()
// #define LLONG_MAX 9223372036854775806
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define MOD 1000000007
// #define MOD 998244353
// #define MOD LLONG_MAX
const double PI=3.14159265358979323846;

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




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



void printv(vint &v){
  for(auto e:v) cout<<e<<" ";
  cout<<endl;
}


// 繰り返し二乗法
ll power(ll a, ll b){
  if(a==1)return a;
  // if(a==0)re
  ll res=1;
  while(b>0){
    if(b&1) res=res*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return res;
}

const int MAX=2100000;
 
ll fact[MAX], fact_inv[MAX];
 
void init_fact(ll n){
  fact[0]=1;
  // 階乗の計算
  rep(i, n) fact[i+1]=fact[i]*(i+1)%MOD;
  fact_inv[n]=power(fact[n], MOD-2);
  // 逆元の計算
  for(ll i=n-1;i>=0;i--) fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
}
 
ll comb(ll n, ll r){
  return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
 
ll perm(ll n, ll r){
  return (fact[n]*fact_inv[n-r])%MOD;
}






int main() {
  cout<<fixed<<setprecision(10);


  ll h,w,k; cin>>h>>w>>k;
  vstring s(h); rep(i,h) cin>>s[i];

  auto f = [&](vvint &v){
    // puts("hoge");
    ll rtn = 0;
    ll x, y;
    y = v.size();
    x = v[0].size();

    vint cnt(v.size(), 0);
    rep(i, x){
      ll maxval = 0;
      ll par = 0;
      rep(j,y){
        cnt[j] += v[j][i];
        chmax(par, v[j][i]);
        chmax(maxval, cnt[j]);
      }
      if(par > k){
        return 100000ll;
      }
      if(maxval > k){
        rtn++;
        rep(j,y) cnt[j] = v[j][i];
      }
    }
    return rtn;
  };

  ll ans = LLONG_MAX;
  rep(i, 1<<(h-1)){
    vvint v(1, vint(w, 0));
    rep(ii, w){
      if(s[0][ii] == '1') v.back()[ii]++;
    }
    ll tmp = 0;
    rep(j, h-1){
      if(i&(1<<j)){
        v.push_back(vint(w, 0));
        tmp++;
      }
      rep(ii, w){
        if(s[j+1][ii] == '1') v.back()[ii]++;
      }
    }
    // cout<<tmp<<" "<<f(v)<<endl;
    chmin(ans, tmp+f(v));
  }
  cout<<ans<<endl;

}






Measured memory_bytes: 384
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int MAX_N = 3005;

char a[MAX_N],b[MAX_N];
int n,m,dp[MAX_N][MAX_N];

int main()
{
	scanf("%s",a);
	scanf("%s",b);
	n=strlen(a),m=strlen(b);
	for (int i=n-1; i>=0; i--)
		for (int j=m-1; j>=0; j--)
			if (a[i]==b[j])
				dp[i][j]=1+dp[i+1][j+1];
			else
				dp[i][j]=max(dp[i+1][j],dp[i][j+1]);
	int i=0,j=0;
	while (i<n&&j<m)
		if (a[i]==b[j])
		{
			putchar(a[i]);
			i++,j++;
		}
		else if (dp[i][j]==dp[i+1][j])
			i++;
		else
			j++;
	printf("\n");
	return 0;
}


Measured memory_bytes: 35328
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  Int ans=1,sum=1;
  n--;
  while(1){
    Int x=(sum+k-1)/k;
    if(x>n) break;
    n-=x;
    sum+=x;
    ans++;
  }
  cout<<ans<<endl;
  return 0;
}



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

int main(){
    string s;
    cin>> s;
    int count=0;
    for(int i=0;i<4;i++) {
    }
    for(int i=1;i<4;i++) {
       if(s[i]==s[i-1]) count=1;
    }

    if(count==0) cout << "Good" << endl;
    else cout << "Bad" << endl;
    }


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
 
int dp[105][100005];
 
signed main(){
    int n, Wt; cin>>n>>Wt;
    
    int w[n+1], v[n+1];
    for(int i=1; i<=n; i++){
        cin>>w[i]>>v[i];
    }
    
    for(int i=0; i<=n; i++){
    	for(int j=0; j<100003; j++){
    		dp[i][j]=10000000007;
    	}
    }
    
    
    dp[0][0]=0;
    
    int ans = 0, val=100000;
    
    for(int i=1; i<=n; i++){
        for(int j=0; j<=val; j++){
            if(dp[i-1][j]==10000000007)
                continue;
                
            dp[i][j+v[i]]=min((dp[i-1][j]+w[i]), dp[i][j+v[i]]);
            
            dp[i][j]=min(dp[i-1][j], dp[i][j]);
            
            if(dp[i][j+v[i]] <= Wt){
                ans = max(ans, j+v[i]);
            }
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 80128
n,k=map(int,input().split())
d=[i for i in input().split()]
while True:
    s=str(n)
    s=list(s)
    check=0
    for i in s:
        if i in d:
            break
        check+=1
        if check==len(s):
            print(''.join(s))
            exit()
    n+=1
            


Measured memory_bytes: 2940
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <complex>

#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)(b);i<(int)(e);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define RALL(c) (c).rbegin(), (c).rend()
#define ALLA(a,n) ((a)+0), ((a)+n)

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<string> vstring;
typedef vector<double> vdouble;

template<class T>void pp(T v,int n){ REP(i,n)cout<<v[i]<< ' ' ; cout << endl; }
template<class T>void pp(T v){ EACH(it,v) cout << *it << ' ' ; cout << endl;  }
template<class T>T& ls(T& a,T b){ if(b<a) a=b; return a; }
template<class T>T& gs(T& a,T b){ if(b>a) a=b; return a; }
inline ll to_i(const string& s){ll n;sscanf(s.c_str(),"%lld",&n);return n;}
inline string to_s(ll n){char buf[32];sprintf(buf,"%lld",n);return string(buf);}

struct __scanner__{ bool e; operator bool(){ return e; } } IN = { false };
inline __scanner__& operator>>(__scanner__& in,int &n)
{ in.e = scanf("%d",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,ll &n)
{ in.e = scanf("%lld",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,double &n)
{ in.e = scanf("%lf",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,char &n)
{ in.e = scanf(" %c",&n)==1; return in; }
inline __scanner__& operator>>(__scanner__& in,string &n) // BUFFER SIZE!
{ static char buf[1000000]; in.e = scanf(" %s",buf)==1; n = buf; return in; } 

const ll inf = 1LL << 32;

int main(){
  int n, m, r;
  while (cin >> n >> m >> r) {
    static ll v[256][256];
    vint rs(r);
    REP(i,r) { cin >> rs[i]; rs[i]--; }
    REP(i,n) REP(j,n) v[i][j] = inf;
    REP(i,n) v[i][i] = 0;
    REP(i,m) {
      int s, d, c;
      cin >> s >> d >> c;
      s--; d--;
      v[s][d] = v[d][s] = c;
    }

    REP(k,n) REP(i,n) REP(j,n) ls(v[i][j], v[i][k] + v[k][j]);
    sort(ALL(rs));

    ll result = inf;
    do {
      ll cnt = 0;
      REP(i,rs.size()-1) cnt += v[rs[i]][rs[i+1]];
      ls(result, cnt);
    } while (next_permutation(ALL(rs)));

    cout << result << endl;
  }
}


Measured memory_bytes: 640
import sys
input = sys.stdin.buffer.readline
import bisect

def main():
    N =  int(input())
    
    odd,al = [],[]
    for i in range(N):
        a = int(input())
        if i%2 == 0:
            odd.append(a)
        al.append(a)
            
    odd.sort()
    al.sort()
    ans = 0
    for i in range(-(-N//2)):
        num = odd[i]
        index = bisect.bisect_left(al,num)
        if index%2 == 1:
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 7956
import java.util.*;

public class Main {
	public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
		int[] a = new int[4];
		for (int i = 0; i < 4; i++) {
			a[i] = (int)(s.charAt(i) - '0');
		}

		for (int i = 0; i < (1 << 3); i++) {
			int num = a[0];
			char[] op = new char[3];
			for (int j = 0; j < 3; j++) {
				if ((1 & (i >> j)) == 1) {
					num += a[j + 1];
					op[j] = '+';
				} else {
					num -= a[j + 1];
					op[j] = '-';
				}
			}

			if (num == 7) {
				String ans = "" + a[0];
				for (int j = 0; j < 3; j++) {
					ans += "" + op[j] + a[j + 1];
				}
				ans += "=7";
				System.out.println(ans);
				return;
			}
		}
	}
}


Measured memory_bytes: 21844