akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main(void) {
  int i, j, k, n, q, c, x, y;
  scanf("%d%d", &n, &q);
  int u[n];
  for(i = 0; i < n; ++i) u[i] = i;
  for(i = 0; i < q; ++i) {
    scanf("%d%d%d", &c, &x, &y);
    if(c) {
      while(u[x] != x) x = u[x];
      while(u[y] != y) y = u[y];
      if(x == y) printf("1\n");
      else printf("0\n");
    } else {
      while(u[x] != x) x = u[x];
      while(u[y] != y) y = u[y];
      u[y] = x;
    }
  }
  return 0;
}


Measured memory_bytes: 2732
N = int(input())
d = {}
for _ in range(N):
  s = input()
  if(s not in d):
    d[s] = 1
  else:
    d[s] += 1
d2 = sorted(d.items(),key=lambda x:x[1], reverse=True)
s1=[]
s1.append(d2[0][0])
p=d2[0][1]
for t in d2[1:]:
  q=t[1]
  if(q==p):
    s1.append(t[0])
  else:
    break
s1=sorted(s1)
for i in s1:
  print(i)


Measured memory_bytes: 48092
S = input()
p01 = 0
p10 = 0
p00 = 0
p11 = 0
for i in range(0, (len(S)//2 * 2), 2):
    if S[i:i+2] == '01':
        p01 += 1
    elif S[i:i+2] == '10':
        p10 += 1
    elif S[i:i+2] == '00':
        p00 += 1
    else:
        p11 += 1
#print(p01,p10,p00,p11)
c = 0
if (p01 == 0) and (p10 == 0):
    c = len(S) // 2
elif p01 >= p10:
    c = p10 * 2 + p00 + p11
    if len(S) & 1:
        if S[-1] == S[-2]:
            c += 1
else:
    c = p01 * 2 + p00 + p11
    if len(S) & 1:
        if S[-1] == S[-2]:
            c += 1
print(c)

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

using namespace std;

#define pb push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;

const int mn = 5e5 + 5;
const int mod = 1e9 + 7;

ll n;
string s;
int a, b;

int main() {
#ifdef LOCAL
	freopen("../1.txt", "r", stdin);
	freopen("../2.txt", "w", stdout);
	size_t bg = clock();
#endif

	cin >> n;
	ll ans = 0;
	for (ll k = 1; k * k <= n; k++) {
		if (n % k == 0) {
			ll m = n / k - 1;
			if (m > k)
				ans += m;
		}
	}
	cout << ans << "\n";


#ifdef LOCAL
	size_t ed = clock();
	printf("time: %f\n", (double) (ed - bg) / CLOCKS_PER_SEC);
#endif
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    string s;
    cin >> s;
    string str = "CODEFESTIVAL2016";
    int result = 0;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == str[i]){
            continue;
        }
        else{
            result++;
        }
    }
    cout << result << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) = abc155c()
// region
private inline fun printAnswer(function: StringBuilder.() -> StringBuilder) = print(StringBuilder().let(function))

private fun StringBuilder.println(message: Any?) = appendln(message)
private fun StringBuilder.print(message: Any?) = append(message)
// endregion
fun abc155c() = printAnswer {
    val n = readLine()!!.toInt()
    val list = (1..n).map { readLine()!! }

    val map = list.groupBy { it }.map { it.key to it.value.size }
    val max = map.maxBy { it.second }!!.second
    map.filter { it.second == max }.map { it.first }.sorted()
        .forEach { println(it) }

    return@printAnswer this
}


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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> ans(M, 0) ;
  
  int like_food = 0;
  
  for(int i = 0; i < N; i++ ){
    int K;
    cin >> K;
    for (int j= 0; j< K; j++){
      int A;
      cin >> A;
      ans[A-1] += 1;   
    }
  }
  for (int i = 0; i < M; i++) {
    if (ans[i] == N) {
      like_food += 1;
    }
  }
  cout << like_food <<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 100000
int a[100010];
int dp[100010];
int jump( int n, int curr)
{

	if(curr==n-1) return 0;
	if(curr>=n) return inf;
	if(dp[curr]!= -1 ) return dp[curr];

	return dp[curr]=min( abs(a[curr]-a[curr+1])+jump( n, curr+1) , curr+2>=n ?inf:(abs(a[curr]-a[curr+2])+ jump(n, curr+2)) ); 
}

int main()
{
	
 	memset(dp, -1, sizeof(dp));
	int n;
	cin>>n;

	for(int i=0; i<n; i++)
		cin>>a[i];
	cout<<jump(n, 0);
	return 0;
}

Measured memory_bytes: 3328
a, b, c = gets.chomp.split.map(&:to_i)

count = 0

while !(a == b && a == c)
  count += 1
  if [a, b, c].min == a
    if a == b
      a += 1
      b += 1
    elsif a == c
      a += 1
      c += 1
    else
      a += 2
    end
  elsif [a, b, c].min == b
    if b == c
      b += 1
      c += 1
    else
      b += 2
    end
  else
    c += 2
  end
end

puts count

Measured memory_bytes: 3836
#include "bits/stdc++.h"

//#include <atcoder/all>

using namespace std;
//using namespace atcoder;

//#define int long long
#define ll long long

ll INF = (1LL << 60);
int mod = 998244353;
using P = pair<ll, ll>;

signed main() {
	int n; cin >> n;
	cout << n * n*n << endl;
	return 0;
}



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


int main() {
    int N;
    cin >> N;
    int X[100],Y[100],H[100];
    rep(i,N){
        cin >> X[i] >> Y[i] >> H[i];
    }
    
    rep(xi,101){
        rep(yi,101){
            int H_C = 0;
            rep(i,N){
                if(H_C == 0 && H[i] != 0){
                    H_C = max(H[i] + abs(X[i]-xi) + abs(Y[i]-yi),0);
                    if(H_C != 0) i = 0;
                }
                if(max(H_C-abs(X[i]-xi)-abs(Y[i]-yi),0) != H[i]) break;
                if(i==N-1){
                    cout << xi << " " << yi << " " << H_C << endl;
                    return 0;
                }
            }
        }
    }
    
}

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

int main(){
	int n;
	cin >> n;
	int* data = new int[n];
	for (int i=0; i<n; i++){
		cin >> data[i];
	}
	int swapCount = 0;
	int temp;
	for (int i=0; i<n; i++){
		for (int j=n-1; j>i; j--){
			if (data[j] < data[j-1]){
				temp = data[j];
				data[j] = data[j-1];
				data[j-1] = temp;
				swapCount++;
			}
		}
	}
	for (int i=0; i<n-1; i++) {
		cout << data[i] << " ";
	}
	cout << data[n-1] << endl;
	cout << swapCount << endl;
	return 0;
}


Measured memory_bytes: 3112
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

int n, q;
int A[100100];
bool dp[5000];

int Partition(int p, int r) {
	int x = A[r];
	int i = p - 1;
	for (int j = p; j < r; j++) {
		if (A[j] <= x) {
			i = i + 1;
			swap(A[i], A[j]);
		}
	}
	swap(A[i + 1], A[r]);
	return i + 1;
}

int main() {
	cin >> n;
	rep(i, n)cin >> A[i];
	int q = Partition(0, n - 1);
	rep(i, n) {
		if(q==i)cout << "[";
		if (i != n - 1) {
			cout << A[i];
			if (q == i)cout << "]";
			cout << " ";
		}
		else {
			cout << A[i];
			if (q == i)cout << "]";
			cout << endl;
		}
	}
}

Measured memory_bytes: 3476
import math
[A,B,H,M] = map(int,input().split())
angA = (H+M/60)*30*(math.pi/180)
angB = M*6*(math.pi/180)
ang = abs(angA - angB)
# print(angA*(180/math.pi))
# print(angB*(180/math.pi))
# print(ang*(180/math.pi))
X = math.sqrt(A**2 + B**2 - 2*A*B*math.cos(ang))
print (X)

Measured memory_bytes: 9460
#include <stdio.h>
int main(void){
    char key[11];
    char out[11];
    for(int i=0;i<11;i++)
    {
        key[i] = out[i] = 0;    
    }
    gets(key);
    int i=0,j=0;
    while(1)
    {
        switch(key[i])
        {
            case '0':
                out[j] = '0';
                j++;
                break;
            
            case '1':
                out[j] = '1';
                j++;
                break;
                
            case 'B':
                if(j>0)
                {
                    out[--j] = 0;
                }
                break;
                
            default:
                puts(out);
                return 0;
        }
        i++;
    }
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<math.h>
#include<string>
#include<algorithm>

int main()
{
	/*int a, b;
	std::cin >> a >> b;
	auto ave = (a + b) / 2.0;
	ave = ceil(ave);
	std::cout << ave << std::endl;*/
	std::string s;
	std::string t;
	std::cin >> s >> t;
	std::vector<int> num0;
	std::vector<int> num1;
	for (auto it : s) {
		num0.push_back(it);
	}
	for (auto it : t) {
		num1.push_back(it);
	}
	std::sort(num0.begin(), num0.end(), [](int a, int b) {return a < b; });
	std::sort(num1.begin(), num1.end(), [](int a, int b) {return a < b; });//?
    
	auto len = (num0.size() < num1.size() ? num0.size() : num1.size());

	bool eq = false;
	for (auto c:num0) {
		eq = false;
		for (auto r : num1) {
			if (c < r) {
				std::cout << "Yes" << std::endl;
				return 0;
			}
			else if(c==r)
			{
				eq = true;
			}
		}
		if (!eq) {
			std::cout << "No" << std::endl;
			return 0;
		}
	}
	if (eq&&num0.size() < num1.size()) {
		std::cout << "Yes" << std::endl;
		return 0;
	}
	std::cout << "No" << std::endl;
	return 0;
}



Measured memory_bytes: 256
// header {{{
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <complex>
#include <utility>
#include <string>
#include <sstream>
#include <queue>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <tuple>
#include <cstdio>
#include <cmath>
using namespace std;

#define ALPHABET    (26)
#define EPS         (1e-10)
#define INF         (1000000005LL)
#define MOD         (1000000007LL)
#define EQ(a, b)    (abs((a)-(b)) < EPS)
// ciling(x/y) = (x+y-1)/y

typedef long long ll;
typedef unsigned long long ull;
// }}}

int main() {
    int n;cin >> n;
    cout << n*(n+1)/2 << endl;
    return 0;
}


Measured memory_bytes: 256
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define DEBUG
#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1)
	{
		cerr << name << " = " << arg1 << endl;
	}
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args)
	{
		const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " = " << arg1 << " || ";
		__f(comma+1, args...);
	}
#else
#define debug(...)
#endif
 
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}
 
template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}
 
#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"
 
// priority_queue<ll, vector<ll>, less<ll>>pq;     // Max Heap
// priority_queue<ll, vector<ll>, greater<ll>>pq;
 
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth (1 based indexing) smallest: " << *A.find_by_order(k - 1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;
 
int main()
{
	FAST_IO;
 
 	ll x;
 	cin >> x;
 	if(x >= 30) cout << "Yes" << endl;
 	else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3656
def main():
    MOD = 10 ** 9 + 7

    N, M = map(int, input().split())
    *X, = map(int, input().split())
    *Y, = map(int, input().split())

    def total(E):
        L = len(E)
        ret = 0
        for i, (frm, to) in enumerate(zip(E, E[1:]), start=1):
            ret = (ret + i * (L - i) * (to - frm)) % MOD
        return ret

    ans = total(X) * total(Y) % MOD
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 24304
from random import randint
import numpy as np
from numba import njit


#@njit
def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


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


def solve(S: str, T: str):
    counter = 0
    for s, t in zip(S, T):
        if s == t:
            counter += 1
    print(counter)
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char[] c = s.toCharArray();
		String res = "yes";
		for (int i=0; i<s.length(); i++) {
			for (int j=i+1; j<s.length(); j++) {
				if ( c[i] == c[j] ) res = "no";
			}			
		}
		System.out.println(res);
	}
}

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

const int MAXN = 2 * 100005;
ll t[4 * MAXN];


ll mx(int v, int tl, int tr, int l, int r) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	return max(mx(v*2, tl, tm, l, min(r,tm)),
		       mx(v*2+1, tm+1, tr, max(l,tm+1), r));
}

void update(int v, int tl, int tr, int pos, ll val) {
	if (tl == tr)
        t[v] = max(val, t[v]);
	else {
		int tm = (tl + tr) / 2;
		if (pos <= tm)
			update(v*2, tl, tm, pos, val);
		else
			update(v*2+1, tm+1, tr, pos, val);
		t[v] = max(t[v*2], t[v*2+1]);
	}
}

ll h[MAXN];
ll a[MAXN];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++)
    {
        ll b = mx(1, 0, n, 0, h[i]-1) + a[i];
        update(1, 0, n, h[i], b);
    }
    cout << mx(1, 0, n, 0, n);

    return 0;
}


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define ForE(it,v) for(auto it : v)
#define mod 1000000007
#define All(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
template<class T> T gcd(T a,T b) {return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b) {return a/gcd(a,b)*b; }
template<class T> bool isPrime(T num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (T i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

using namespace std;

int a,b,c;
int n,m,cnt,ans;
string s,t;

main()
{
        cin>>s;

        rep(i,s.size())
        {
            if(s[i]=='B')
            {
                if(!t.empty())t.pop_back();
            }
            else
            {
                t.push_back(s[i]);
            }
        }
        cout<<t<<endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
	ll n,m,k; cin>>n>>m>>k;
	vector<ll>pref(n);

	ll ar[n];
	for(int i=0;i<n;i++)
	{
		cin>>ar[i];
	}
	ll mx=0;
	pref[0]=ar[0];
	if(ar[0]<=k)
	{
		mx=1;
	}
	for(int i=1;i<n;i++)
	{
		pref[i]=pref[i-1]+ar[i];
		if(pref[i]<=k)
		{
			mx=max(mx,(ll)i+1);
		}
	}
	ll sm=0;
	
	for(int i=0;i<m;i++)
	{
	
		ll x; cin>>x;
		if(sm<=k){mx=max(mx,(ll)i);}
		sm+=x;
		if(sm<=k){
		ll it=upper_bound(pref.begin(),pref.end(),k-sm)-pref.begin();
        ll value=i+it+1;
		mx=max(mx,value);
		}
		
		
		
	}
	cout<<mx;
	
	
	
	
	
	
	
}


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

int main() {
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
  int64_t A,B,N;
  cin>>N>>A>>B;
  int64_t c=A+B;
  int64_t d=(N/c)*A+min(N%c,A);
  cout<<d;
}

Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n,A,B;
int x[MAXN];

bool can(int t) {
	ll have=(ll)t*B; int diff=A-B;
	ll need=0;
	REP(i,n) {
		if(x[i]<=have) continue;
		int cur=(x[i]-have+diff-1)/diff;
		need+=cur;
	}
	return need<=t;
}

void run() {
	scanf("%d%d%d",&n,&A,&B); REP(i,n) scanf("%d",&x[i]);
	int l=0,h=1000000000;
	while(l+1<h) {
		int m=l+(h-l)/2;
		if(can(m)) h=m; else l=m;
	}
	printf("%d\n",h);
}

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int ways(int mask, int woman, int n, vector<vector<int> > &match, vector<vector<int> > &dp) {
    if (woman == n)
        return !mask ? 1 : 0;
    if (dp[woman][mask] != -1)
        return dp[woman][mask];
    int currWays = 0;
    for (int man = 0; man < n; man++) {
        if ((mask & (1<<man)) && match[man][woman]) {
            currWays = (currWays % mod + ways(mask ^ (1<<man), woman+1, n, match, dp) % mod ) % mod;
        }
    }
    return dp[woman][mask] = currWays;
}
int main() {
    int n;
    cin>>n;
    vector<vector<int> > match(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cin>>match[i][j];
    }
    vector<vector<int> > dp(n, vector<int> (1<<n, -1));
    cout<<ways((1<<n)-1, 0, n, match, dp)<<"\n";
    return 0;
}


Measured memory_bytes: 183556
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc()) 
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

const int MOD = 998244353, G = 5;
inline void Add(int &x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int &x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD;
    b >>= 1;
  }
  return ret;
}

const int N = 200010;
int rev[N];
void prework(int n) {
  rev[0] = 0;
  rep (i, 1, n-1)
    if (i&1) rev[i] = rev[i^1] | (n >> 1);
    else rev[i] = rev[i >> 1] >> 1;
}
void dft(int *a,int n,int sgn) {
  rep (i, 0, n-1) if (i < rev[i])
    swap(a[i], a[rev[i]]);
  int w, wp, u, v;
  for (int s = 2; s <= n; s <<= 1) {
    wp = power(G, (MOD - 1) / s);
    if (sgn) wp = power(wp, MOD - 2);
    for (int k = 0; k < n; k += s) {
      w = 1;
      for (int j = 0; j < (s >> 1); ++ j) {
	u = a[k + j];
	v = 1ll * a[k + j + (s >> 1)] * w % MOD;
	a[k + j] = (u + v >= MOD ? u + v - MOD : u + v);
	a[k + j + (s >> 1)] = (u - v < 0 ? u - v + MOD : u - v);
	w = 1ll * w * wp % MOD;
      }
    }
  }
  if (sgn) {
    w = power(n, MOD - 2);
    rep (i, 0, n-1) a[i] = 1ll * a[i] * w % MOD;
  }
}

const int M = 210;
int n, m;
int dp[M][N];
int jc[N], ijc[N];
void prework_comb(int sz) {
  jc[0] = 1;
  rep (i, 1, sz) jc[i] = 1ll * jc[i-1] * i % MOD;
  ijc[sz] = power(jc[sz], MOD - 2);
  rrp (i, sz-1, 0) ijc[i] = 1ll * ijc[i+1] * (i+1) % MOD;
}
int comb(int a,int b) {
  if (a < b || b < 0) return 0;
  return 1ll * jc[a] * ijc[b] % MOD * ijc[a-b] % MOD;
}
int ta[N], tb[N];
int main() {
  read(n), read(m);
  prework_comb(n + 2);
  dp[0][0] = 1;
  rep (i, 1, m) {
    rep (j, 0, n) {
      dp[i][j] = dp[i-1][j];
      Add(dp[i][j], 1ll * j * (j + 1) / 2 % MOD * dp[i-1][j] % MOD);
    }
    int l = 1;
    while (l < 2 * n + 1) l <<= 1;
    prework(l);
    rep (i, 0, l-1) ta[i] = tb[i] = 0;
    rep (k, 1, n) tb[k] = ijc[k + 2];
    rep (j, 0, n) ta[j] = 1ll * dp[i-1][j] * ijc[j] % MOD;
    dft(tb, l, 0), dft(ta, l, 0);
    rep (i, 0, l-1) ta[i] = 1ll * ta[i] * tb[i] % MOD;
    dft(ta, l, 1);
    rep (j, 0, n) Add(dp[i][j], 1ll * ta[j] * jc[j+2] % MOD);
    // rep (j, 0, n) {
    //   rep (k, 1, j) {
    // 	Add(dp[i][j], 1ll * dp[i-1][j - k] * comb(j + 2, k + 2) % MOD);
    //   }
    // }
    // rep (j, 0, n) cerr << dp[i][j] << ' ';
    // cerr << endl;
  }
  int ans = 0;
  rep (i, 0, n) Add(ans, 1ll * comb(n, i) * dp[m][i] % MOD);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 160128
#include <algorithm>
#include <cmath>
#include <climits>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

std::map<int, int> prime_factorize(int d) {
  std::map<int, int> primes;

  if (d % 2 == 0) {
    primes.insert(std::make_pair(2, 0));
    while(d % 2 == 0) {
      d /= 2;
      primes[2]++;
    }
  }

  int factor = 3;
  while(d > 1) {
    if (d % factor == 0) {
      primes.insert(std::make_pair(factor, 0));
      while(d % factor == 0) {
        d /= factor;
        primes[factor]++;
      }
    }
    factor += 2;
  }
  return primes;
}

int nCr(int n, int r) {
  if (n == r) return 1;
  if (n == 0 || r == 0) return 1;
  return nCr(n-1, r-1) + nCr(n-1, r);
}

int main() {
  int N; std::cin >> N;
  std::map<int,  int> factors;
  for (int i = 2; i <= N; ++i) {
    for (auto m : prime_factorize(i)) {
      if (factors.find(m.first) == factors.end()) {
        factors.insert(std::make_pair(m.first, 0));
      }
      factors[m.first] += m.second;
    }
  }

  std::vector<int> k = {75, 25, 15, 5, 3};
  std::map<int, int> results;
  for (int v : k) {
    int counter = 0;
    for (auto m : factors) {
      int num_factors = m.second + 1;
      if (num_factors >= v) {
        ++counter;
      }
    }
    results.insert(std::make_pair(v, counter));
  }

  int num_patterns = 0;

  // 75
  num_patterns += results[75];

  // 25, 3
  if (results[3]>1)
    num_patterns += results[25] * (results[3]-1);

  // 15, 5
  if (results[5]>1)
    num_patterns += results[15] * (results[5]-1);

  // 5, 5, 3
  if (results[5]>1 && results[3]>2)
    num_patterns += nCr(results[5], 2) * (results[3]-2);

  std::cout << num_patterns << std::endl;
}


Measured memory_bytes: 256
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

#define INFint 2e9+1

int main(){
  int V,E;
  cin>>V>>E;
  vector<pair<int,int>> G[100001];
  for(int i(0);i<E;i++){
    int s,t,w;
    cin>>s>>t>>w;
    G[s].push_back({w,t});
    G[t].push_back({w,s});
  }

  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;// cost,to
  q.push({0,1});
  vector<bool> visited(V+1,false);

  ll sum(0);
  while(!q.empty()){
    pair<int,int> now = q.top();q.pop();
    if(visited[now.second]) continue;
    sum += now.first; 
    visited[now.second] = true;
    for (auto next: G[now.second]){
      if (visited[next.second] == false) q.push(next);
    }
  }
  cout << sum << endl;
  return 0;
}




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

void swap(int* px, int* py){
  int z;
  z = *px;
  *px = *py;
  *py = z;
}

void output(int a[], int n){
  for(int i=0; i<n; i++){
    cout << a[i] << (i!=n-1 ? " ": "");
  }
  cout << endl;
}

void BubbleSort(int a[], int n){
  bool flag = 1;
  int count = 0;
  while(flag){
    flag = 0;
    for(int i=n-1; i>0; i--){
      if(a[i]<a[i-1]){
        swap(&a[i], &a[i-1]);
        flag = 1;
        count++;
      }
    }
  }
  output(a, n);
  cout << count << endl;
}

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

  int a[n];
  for(int i; i<n; i++){
    cin >> a[i];
  }

  BubbleSort(a, n);

  return 0;
}



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

namespace ABC113 {
	class ABC113_A {
		static void Main(string[] args) {
			var line = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
			Console.WriteLine(line[0] + line[1] / 2);
		}
	}
}


Measured memory_bytes: 11348
using System;

namespace atcoderA
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            Array.Sort(input);
            Console.WriteLine(input[0] + input[1] == input[2] ? "Yes" : "No");
        }
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  
 ll N,M;
  cin>>N>>M;
  for(ll i=0;i<M;i++) {
ll A;
    cin>>A;
    N-=A;
  }
  if(N<0) {
cout<<-1<<endl;
  }
  else {
cout<<N<<endl;
  }
}


Measured memory_bytes: 3632
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use std::cmp::*;
use std::collections::*;
use std::mem::*;

fn main() {
    let (r, w, e) = (std::io::stdin(), std::io::stdout(), std::io::stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    let X: i64 = io.read();
    let mut money = 100;
    let mut count = 0;
    while money < X {
        money = (money as f64 * 1.01) as i64;
        count += 1;
    }
    io.writeln(count);
}

static MOD: i64 = 1000000007;
// IO
use std::io::*;
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
    fn debug3<S: std::fmt::Debug, T: std::fmt::Debug, U: std::fmt::Debug>(
        &mut self,
        val1: S,
        val2: T,
        val3: U,
    ) {
        writeln!(
            self.Error,
            "(debug3) {:?} -> {:?} -> {:?}",
            val1, val2, val3
        );
    }
}


Measured memory_bytes: 2092
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>
#include <random>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define int long long

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;
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; }

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

long long power(long long x, long long n, long long mod = 1000000007) {
    if (n == 0) return 1;
    if (n % 2 == 0) return power(x * x % mod, n/2, mod);
    else return x * power(x, n-1, mod) % mod;
}

class CNK {
    vector<long long> prod, inv;
public:
    CNK(int n): prod(n+1), inv(n+1) {
        prod[0] = 1;
        for (int i = 1; i <= n; ++i) prod[i] = (prod[i-1] * i) % MOD;
        inv[n] = power(prod[n], MOD-2);
        for (int i = n - 1; i >= 0; --i) inv[i] = (inv[i+1] * (i+1)) % MOD;
    }
    int get(const int &n, const int &k) const {
        if (n < k || k < 0) return 0;
        return (prod[n] * ((inv[k] * inv[n-k]) % MOD)) % MOD;
    }
};

LL calc(const CNK &cnk, int x, int y) {
    if (x < y) swap(x,y);
    LL sum = 0;
    REP(i,0,y) {
        sum += cnk.get(x+i, i + 1);
        if (sum >= MOD) sum -= MOD;
    }
    return sum;
}

void solve() {
    VI r(2), c(2);
    cin >> r[0] >> c[0] >> r[1] >> c[1];
    CNK cnk(r[1] + c[1] + 100);
    cout << (calc(cnk,r[1]+1,c[1]+1) - calc(cnk,r[0],c[1]+1) - calc(cnk,r[1]+1,c[0]) + calc(cnk,r[0],c[0]) + MOD) % MOD << endl;
}

signed main() {
    solve();
    
    return 0;
}

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

int main() {
  string S;
  cin >> S;
  if (S.find("RRR") != S.npos) {
    cout << 3 << endl;
  } else if (S.find("RR") != S.npos) {
    cout << 2 << endl;
  } else if (S.find("R") != S.npos) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
using namespace std;
#define ll long long
#define mod 1000000007;

int main() {
	int m, d, ans = 0, d1, d10;
	cin >> m >> d;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= d; j++) {
			d1 = j % 10;
			d10 = j / 10;
			if (d1 >= 2 && d10 >= 2 && d1 * d10 == i) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define N_MAX 10000
#define Q_MAX 500

bool LinearSearch(int* pArray, int size, int key)
{
	bool bIsFind = false;
	//for (int i = 0; i < size; ++i)
	//{
	//	if (pArray[i] == key)
	//	{
	//		bIsFind = true;
	//		break;
	//	}
	//}


	pArray[size] = key;
	int i = 0;
	while (pArray[i] != key) ++i;
	bIsFind = i != size;

	return bIsFind;
}

int main()
{
	int count = 0;
	int n, S[N_MAX + 1];
	cin >> n; 
	for (int i = 0; i < n; ++i) cin >> S[i];
	//int q, T[Q_MAX];
	int q, key;
	cin >> q;
	for (int i = 0; i < q; ++i)
	{
		cin >> key;
		if (LinearSearch(S, n, key)) ++count;
	}

	cout << count << endl;

	return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main(){
    int n; cin >> n;
    vector<int> a(n+1);
    rep(i,n) cin >> a[i+1];//1-index

    vector<int> b(n+1,0);

    for(int i = n; i >= 1; --i){
        //大きい方から見ていく
        int sum = 0;
        for(int j = i; j <= n; j+= i){
            //j以上のiの倍数を見る
            sum += b[j];
        }
        if((sum+a[i]) % 2 == 1) b[i]++;
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(b[i]) ans.pb(i);
    }
    cout << ans.size() << endl;
    rep(i,ans.size()){
        printf("%d%c", ans[i], i+1==ans.size()?'\n':' ');
    }
    return 0;
}

Measured memory_bytes: 3192
#include "bits/stdc++.h"
using namespace std;
using lint = long long;
#define low lower_bound
#define upp upper_bound
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define Rep(i, n) for (int i = int(n); i >= 0; --i)
#define all(vec) (vec).begin(), (vec).end()
#define cend printf("\n");
#define prique(T) priority_queue<T, vector<T>, greater<T>>
#define prique2(T) priority_queue<T>

struct edge { int to; double cost; };
using P = pair<lint, lint>;
using D = pair<double, double>;
using DI = pair<double, int>;
//const lint mod = 998244353LL;
const lint mod = 1000000007LL;
const lint inf = 3LL * mod * mod;

template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

lint modpow(lint x, lint n, lint m) {
	lint ans = 1;
	while (n > 0) {
		if (n & 1) {
			ans *= x;
			if (m <= ans) ans %= m;
		}
		x *= x;
		if (m <= x) x %= m;
		n >>= 1;
	}
	return ans;
}

lint fact[1000000];
void f_init(lint n) {
	if (1000000 <= n) return;
	fact[0] = fact[1] = 1;
	for (lint i = 2; i <= n; ++i) {
		fact[i] = i * fact[i - 1];
		if (mod <= fact[i]) fact[i] %= mod;
	}
	return;
}

lint inver[1000000]; bool inve[100000];
lint inv(lint x) {
	if (x == 0) return 0;
	else if (inve[x]) return inver[x];
	else {
		inve[x] = true;
		return inver[x] = modpow(x, mod - 2, mod);
	}
}

lint comb(lint n, lint r) {
	if (n < r) return 0;
	if (n == r) return 1;
	lint ans = fact[n] * inv(fact[n - r]) % mod * inv(fact[r]) % mod;
	if (ans < 0) return ans + mod;
	return ans;
}

lint nck[1010][1010];
void comb(lint n) {
	rep(i, n + 1) {
		rep(j, i + 1) {
			if (j == 0 || i == j) nck[i][j] = 1;
			else nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j];
		}
	}
}

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

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

bool pri(lint p) {
	for (lint i = 2; i * i <= p; i == 2 ? ++i : i += 2) if (p % i == 0) return false;
	return p > 1;
}

map<lint, lint> factring(lint n) {
	map<lint, lint>ans;
	for (lint i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			n /= i;
			++ans[i];
		}
	}
	if (n != 1) ++ans[n];
	return ans;
}

double dis(D a, D b) { return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); }

int n;
string s, t, ans;
int main() {
	cin >> n >> s >> t;
	rep(i, n) {
		ans += s[i];
		ans += t[i];
	}
	cout << ans << endl;
}

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

int main()
{
	long long h, w;
	cin >> h >> w;

	if (h == 1 || w == 1) {
		cout << 1 << endl;
		return 0;
	}

	if (w % 2 == 0) {
		cout << h * (w / 2) << endl;
	}
	else {
		long long ret = 0;
		if (h % 2 == 0) {
			ret += (h / 2) * (w / 2);
			ret += (h / 2) * (w / 2 + 1);
		}
		else {
			ret += (h / 2) * (w / 2);
			ret += (h / 2 + 1) * (w / 2 + 1);
		}
		cout << ret << endl;
	}

	return 0;
}

Measured memory_bytes: 256
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(m)]
 
C = [[0] * l for i in range(n)]
 
for i in range(n):
    for j in range(l):
        C[i][j] = str(sum(A[i][k] * B[k][j] for k in range(m)))
 
for i in range(n):
    print(' '.join(C[i]))

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("t5.in","r",stdin);
   //freopen("t5.out","w",stdout);
    int i,j,n,m;
    int flag1=0,flag2=0;
    string x;
    cin>>x;
    for(i=0;i<3;i++)
    {
        if(x[i]=='A')flag1=1;
        else flag2=1;
    }
    if(flag1&&flag2)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

const li mod = 1e9 + 7;

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

    li n;
    cin >> n;

    vector<li> xs(n);
    for (int i = 0; i < n; ++i) {
        cin >> xs[i];
    }

    vector<li> cs;
    for (int i = 0; i < n; ++i) {
        if (cs.empty() || xs[i] != cs.back()) {
            cs.push_back(xs[i]);
        }
    }

    li m = cs.size();

    vector<li> dp(n + 1);
    vector<li> colsum(3e5);

    dp[0] = 1;

    for (int i = 0; i < m; ++i) {
        dp[i + 1] = dp[i] + colsum[cs[i]];
        dp[i + 1] %= mod;
        colsum[cs[i]] += dp[i];
        colsum[cs[i]] %= mod;
    }

    cout << dp[m] << endl;

    return 0;
}

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

int main() {
  int N;
  cin >> N;
  int count = 0;
  for(int i = 1 ; i <= N ; i++){
  	//正の整数Nの桁数を調べる
  	int count_i = 1;
    int x = i;
  	while(x / 10 != 0){
  		x /= 10;
    	count_i++;
  	}
    //桁数が奇数か
    if(count_i % 2 == 1){
    	count++;
    }
  }
  cout << count << endl;
}

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

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

    string s;

    cin>>s;

    int posA=0,posB=0;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='A'){
               posA=i+1;
               break;
        }
    }
    for(int i=s.size()-1; i>=posA; i--){
        if(s[i]=='Z'){
            posB=i+1;
            break;
        }
    }
    cout<<posB-posA+1<<endl;
}


Measured memory_bytes: 720
n = int(input())
s = 0
if n > 81:
    print("No")
    exit()
for i in range(1 , 10):
    if n % i == 0 and n // i < 10:
        s = "Yes"
    else:
        s = "No"
    if s == "Yes":
        print(s)
        exit()
print(s)

Measured memory_bytes: 9168
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>

int lcm(ll a, ll b)
{
    return a * b / __gcd(a, b);
}
ll INF = 10010001010;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    int N, M;
    cin >> N >> M;
    int X;
    cin >> X;
    vector<int> C(N);
    vector<vector<int>> A(N, vector<int>(M));
    for (int i = 0; i < N; i++)
    {
        cin >> C[i];
        for (int j = 0; j < M; j++)
        {
            cin >> A[i][j];
        }
    }
    ll ans = INF;
    for (int bit = 0; bit < (1 << N);bit++)
    {
        vector<int> U(M,0);
        ll pre = 0;
        for (int i = 0; i < N;i++)
        {
            if(bit & (1 << i)){
                for (int j = 0; j < M;j++)
                {
                    U[j] += A[i][j];
                }
                pre += C[i];
            }

        }
        bool ok = true;
        for (int i = 0; i < M; i++)
        {
            if(U[i] < X){
                ok = false;
            }
        }
        if(ok){
            ans = min(ans, pre);
        }
    }
    if(ans == INF){
        cout << -1 << endl;
    }
    else{
    cout << ans << endl;
    }
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)
#define Graph vector<vecctor<ll>>
#define pairs vector<pair<ll,ll>>
#define pb push_back



using namespace std;
using ll = long long;
const ll INF = 1e18;
const double PI = acos(-1);

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const ll mod = 1e9 + 7;








int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s[s.size()-1] == 's'){
        s += 'e';
        s+= 's';
        cout << s << endl;
    }else{
        s += 's';
        cout << s << endl;
    }

    return 0;
}


Measured memory_bytes: 3648
#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;
    cin >> n;
    string s,t;
    cin >> s >> t;
    rep(i, n){
        cout << s.at(i) << t.at(i);
    }
    cout << '\n';
    return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] temp = Console.ReadLine().Split(' ');
        int cou = 0;
        int[] colle = new int[3];
        foreach (string s in temp)
        {
            colle[cou] = int.Parse(s);
            cou++;
        }
        if (colle[0] - colle[1] * 2 + colle[2] == 0)
        {
            Console.WriteLine("YES");
        }
        else
        {
            Console.WriteLine("NO");
        }
    }

}


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

auto chmin = [](auto&& l, auto r) { return r < l ? l = r, 1 : 0; };

template <class T> struct dijkstra {
  struct edge {
    int to;
    T w;
  };
  vector<vector<edge>> g;
  const T inf;
  dijkstra(int n, T _inf = numeric_limits<T>::max()) : g(n), inf(_inf) {}
  void add_edge(int from, int to, T w) { g[from].push_back({to, w}); }
  void add_undirected_edge(int u, int v, T w) {
    add_edge(u, v, w), add_edge(v, u, w);
  }
  vector<T> run(int s) const {
    vector<T> dist(g.size(), inf);
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
    pq.emplace(dist[s] = 0, s);
    while (not pq.empty()) {
      T d;
      int v;
      tie(d, v) = pq.top(), pq.pop();
      if (d > dist[v]) continue;
      for (auto e : g[v])
        if (chmin(dist[e.to], dist[v] + e.w)) pq.emplace(dist[e.to], e.to);
    }
    return dist;
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  dijkstra<int> g(n);
  for (int i = 0; i < n; ++i) {
    int p;
    cin >> p;
    if (p) {
      g.add_edge(i, i + p, 0);
    } else {
      for (int j = 1; j <= 6; ++j) {
        if (i + j < n) {
          g.add_edge(i, i + j, 1);
        }
      }
    }
  }
  cout << g.run(0).back() << '\n';
}



Measured memory_bytes: 10196
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

const int N = 2e5 + 1;

void solve(){
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	while(1){
		c = c - b;
		if(c <= 0){
			cout << "Yes" << newl;
			return;
		}
		a = a - d;
		if(a <= 0){
			cout << "No" << newl;
			return;
		}
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3604
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		long N = sc.nextLong();
		long K = sc.nextLong();
		long[] H = nextLongArray(sc, (int) N);

		sc.close();

		Arrays.sort(H);

		long sum = 0;
		for (int i = 0; i < Math.max(N - K, 0); i++) {
			sum += H[i];
		}

		out.println(sum);

	}

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

	@SuppressWarnings("unused")
	private long[] nextLongArray(Scanner sc, int n) {
		long[] result = new long[n];
		for (int i = 0; i < n; i++) {
			result[i] = sc.nextLong();
		}
		return result;
	}
}


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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] number = line.split(" ");
        int n = Integer.parseInt(number[0]);
        int m = Integer.parseInt(number[1]);
        for(int i = 0; i < m + 2; i++) {
            System.out.printf("#");
        }
        System.out.println();
        for(int i = 0; i < n; i++) {
            line = br.readLine();
            System.out.println("#" + line + "#");
        }
        for(int i = 0; i < m + 2; i++) {
            System.out.print("#");
        }
        System.out.println();
    }
}

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

const long long mod = 1e9 + 7;

int main() {
  string l;
  cin >> l;
  int n = l.size();

  long long dp[n+1][2];
  dp[0][0] = 1;
  dp[0][1] = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( l[i] == '1' ) {
      dp[i+1][1] = (dp[i][1] * 3 + dp[i][0]) % mod;
      dp[i+1][0] = (dp[i][0] * 2) % mod;
    }
    if ( l[i] == '0' ) {
      dp[i+1][0] = dp[i][0];
      dp[i+1][1] = (dp[i][1] * 3) % mod;
    }
  }

  cout << (dp[n][0] + dp[n][1]) % mod << endl;
  return 0;
}


Measured memory_bytes: 5256