akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<algorithm>
using namespace std;

int main()
{
	int h[25];
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
	}
	int ans = 0;
	int ok = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if(h[j] <= h[i]) ok++;
		}
		if (ok == i)ans++;
		ok = 0;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    int n,k,i,l=100000;
    scanf("%d",&n);
    k=sqrt(n);
    for(i=1;i<=k;i++)
    {
        if(n%i==0)
        {
        l=n/i;
        }
    }
      if(l>=10)
      {
          printf("No\n");
      }
      else
      {
          printf("Yes\n");
      }
      return 0;
}


Measured memory_bytes: 256
//11
#include<string>
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  while(n--){
    string s;
    cin>>s;
    if(s.size()>=6&&s==">'"+string((s.size()-4)/2,'=')+'#'+string((s.size()-4)/2,'=')+'~'){
      cout<<'A'<<endl;
    }else{
      int r=(s.size()-4)/2;
      string b;
      while(r--){
	b+="Q=";
      }
      if(s.size()>=6&&s==">^"+b+"~~"){
	cout<<'B'<<endl;
      }else{
	cout<<"NA"<<endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
{-# LANGUAGE BangPatterns #-}
 
module Main
  ( main
  )
where
 
import           Control.Applicative
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import           Data.Ord
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import qualified Data.Vector.Unboxed           as UV

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine


main = do
  n <- readInt
  print $ (n * (n + 1)) `div` 2


Measured memory_bytes: 380
#include <iostream>
using namespace std;
int main() {
    string S;
    int K;
    cin >> K >> S;
    if (S.size()<=K) {
        cout << S << endl;
    }
    else {
        for (int i=0;i<K; i++) {
            cout << S.at(i);
        } cout << "..." << endl;
    }
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int A,B; cin >> A >> B;
    if(A >= 13) {
        cout << B << endl;
    } else if(A <= 5) {
        cout << 0 << endl;
    } else {
        cout << B / 2 << endl;
    }
    return 0;
}



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

#define ld long double
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vl vector<ll>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define repd(i, a, b) for (int i=(a);i<(b);i++)
#define rep(i, n) repd(i,0,n)
#define ALL(v) v.begin(), v.end()
#define INF 1e9

using namespace std;

/**
 * calculate GCD(greatest common divisor)
 * @param a
 * @param b
 * @return
 */
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

/**
 * change minimum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMinimum(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * change maximum
 * @tparam T
 * @param a
 * @param b
 * @return bool
 */
template<class T>
inline bool changeMaximum(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

/**
 * output answer
 * @tparam T
 * @param answer
 * @return
 */
template<typename T>
T output(T answer) {
    cout << answer << endl;
    return 0;
}

/** ----from here ---------------------------------------------------------- */

int main() {

    int N, M;
    cin >> N;
    vector <string> a(N);
    map<string, int> s;
    for (int i = 0; i < N; ++i) {
        cin >> a.at(i);
    }
    cin >> M;
    vector <string> b(M);
    for (int i = 0; i < M; ++i) {
        cin >> b.at(i);
    }

    for (int i = 0; i < N; ++i) {
        s[a[i]] += 1;
    }
    for (int i = 0; i < M; ++i) {
        s[b[i]] -= 1;
    }


    int ans = 0;
    string str;

    for (pair<string, int> p:s) {
        // cout << p.first << " " << p.second << endl;
        ans = max(p.second, ans);
    }


//    for (const auto& [key, value] : s){
//        if (value > ans ){
//            str = key;
//        }
//    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[5];
void query(long long x){printf("? %lld\n",x);fflush(stdout);scanf("%s",s);}
int main()
{
	long long x=1e9;
	query(x);
	if(s[0]=='Y')
	{
		for(int i=9;i>=1;i--)
		{
			query(x-1);
			if(s[0]=='N')break;
			x/=10;
		}
		printf("! %d\n",x);
		return 0;
	}
	while(s[0]=='N')query(x/=10);
	long long l=x+1,r=x*10-1,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		query(mid*10);
		if(s[0]=='Y')r=mid;
		else l=mid+1;
	}
	printf("! %d\n",r);
	return 0;
}

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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue;
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second

template<typename T>
ll sz(vector<T> vec){ return (ll)vec.size(); }
ll sz(string s){ return (ll)s.size(); }

ll gcd(ll a,ll b){ return ((!b) ?a :gcd(b, a%b)); }

int main(){
    ll n,m;
    cin >> n >> m;
    ll a[m] = {};
    ll memo[m] = {};
    
    rep(i,0,m){
        ll b;
        cin >> a[i] >> b;
        rep(j,0,b){
            ll c;
            cin >> c;
            memo[i] |= (1 << (c-1)); 
        }
    }

    vector<ll> dp((ll)pow(2,n),LINF);
    dp[0] = 0;
    rep(i,0,(ll)pow(2,n)){
        rep(j,0,m){
            dp[i | memo[j]] = min(dp[i | memo[j]],dp[i] + a[j]);
        }
    }

    if(dp[(ll)pow(2,n)-1] == LINF) cout << -1 << endl;
    else cout << dp[(ll)pow(2,n)-1] << endl;

    return 0;
}




Measured memory_bytes: 4096
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int x[3];
	cin >> x[0] >> x[1] >> x[2];
	sort(x, x+3);
	cout << x[0]+x[1] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace  std;
template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

	
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define re(n) for (int i = 0; i < n; ++i)
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define eb emplace_back

//OutPut
#define ps(x) cout << x << endl;
#define ps_end(x) {ps(x); return;}


const int md = 1e9 + 7; //998244353 ;
const int dir[4][2] = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
ll pw(auto x, auto y) {	 ll s = 1; while(y) { if (y & 1) s = s * x % md; x= 1LL * x * x % md; y /= 2; } return s;}

const int maxn = 1e6 + 10;

int n, m, nq, nk;
string str;
ll s[100][100];
void task() {
	cin >> n;
	vector<ll> a(n);
	vii b(n);
	re(n) {

    cin >> str;
		int x = str.size() - 1;    
		for (int j = 0; j < str.size(); ++j) {
			if (str[j] == '.') x = j;
			else a[i] = a[i] * 10 + str[j] - '0';
		}
		debug(str.size() - 1 -  x);
		rep(j, 0, 9 - (str.size() - 1 - x))
		 a[i] *= 10;
		debug(a[i]);
		int n2 = 0, n5 = 0;
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			++n2;
		}
		while (a[i] % 5 == 0) {
			a[i] /= 5;
			++n5;
		}		
		
		//n2 -= 9;
		//n5 -= 9;
		s[n2][n5]++;	
		debug(n2, n5);
	};
  ll ans = 0;
	re(100) {
		rep(j, 0, 30)  if (s[i][j])
		  rep(k, 0, 100)
		    rep (p, 0, 30) if (s[k][p]) if (i + k >= 18 && j + p >= 18){
					
					//debug(i, j, k, p, s[i][j], s[k][p]);
		      if (i == k && j == p) ans += s[i][j] * (s[i][j] - 1);
		      else ans += s[i][j] * s[k][p];					
				}

	}
	ps(ans / 2);
	
	//Read the stuff at the bottom
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout<<fixed<<setprecision(20);
  int T = 1;
  //cin >> T;
  for (int ti = 1; ti <= T; ++ti) {
    task();
  }
  return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* write down
*/


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

using namespace std;
#define REPP(i,a,b,c) for(int i=a; i<=b; i+=c)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,c) for(int i=a; i>=b; i-=c)
#define REV(i,a,b) REVV(i,a,b,1)
#define FOR(i,a) REP(i,0,(int)a-1)
#define FORD(i,a) REV(i,(int)a-1,0)
#define PB push_back
#define POB pop_back
#define FI first
#define SE second
#define MP make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > pii;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef pair < ll , ll > pll;

const double PI = acos(-1);
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
	

ll addMod(ll a, ll b){
	if(a + b >= MOD) return a + b - MOD;
	return a + b;
}

ll mulMod(ll a, ll b){
	return (a*b)%MOD;
}

ll fast(ll a, ll b){
	if(b == 0) return 1;
	ll tmp = fast(a,b/2);
	tmp = mulMod(tmp,tmp);
	if(b%2 == 1) tmp = mulMod(tmp,a);
	return tmp;
}

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

//////////////////////////////////////////////


string str;

bool solve(){
	FOR(i,3){
		if(str[i] == str[i+1]) return true;
	}
	return false;
}

int main(){
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> str;
	if(solve()) cout << "Bad" << endl;
	else cout << "Good" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1e9+100;
const ll MOD = 1e9;
const double EPS = 1e-10;
const bool debug = 0;
//------------------------------//
 
int N, M;
vector<int> g[112345];
int d[112345];
int a[112345], b[112345];
 
int color[112345];
 
// 彩色
bool binary_color(int u, int c) {
	color[u] = c;
	
	REP(i, g[u].size()) {
		int v = g[u][i];
		
		if (c == 0) {
			if (color[v] != 0) binary_color(v, c);
		}
		else {
			if (color[v] == -c) continue;
			
			if (color[v] == c) return false;
			if (!binary_color(v, -c)) return false;
		}
	}
	return true;
}
 
bool solve(int v) {
	fill(color, color + N, 0);
	return binary_color(v, 1);
}
 
int main() {
	cin >> N >> M;
	
	REP(i, M) {
		scanf("%d %d", a + i, b + i);
		a[i]--; b[i]--;
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
		
	}
	
	ll ans = 0;
	
	if (!solve(0)) {
		ans = (ll)N * (N - 1) / 2 - M;
	}
	else if (N <= 3) {
		ans = 0;
	}
	else {
		ll ecnt = 0;
		REP(i, N) if (color[i] == -1) ecnt++;
		REP(i, N) {
			if (color[i] == -1) continue;
			ans += ecnt - g[i].size();
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 7680
using System;

namespace ConsoleApp1
{
    class Program
    {
  
        static void Main(string[] args)
        {
            int X = int.Parse(Console.ReadLine());

            for (int i = 0; i < X; i++)
            {
                for (int j = 0; j < X; j++)
                {
                    if (X == i * 4 + j * 7)
                    {
                        Console.WriteLine("Yes");
                        return;
                    } 
                }
            }
            Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 13140
from functools import reduce

# input
N = int(input())
T = [int(input()) for _ in range(N)]

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers_list):
    return reduce(lcm_base, numbers_list, 1)

print(lcm_list(T))



Measured memory_bytes: 3572
a = int(input())
b = int(input())
c = int(input())
x = int(input())

choice_cnt = 0

for i in range(a+1):
    tmp_sum_a = i*500
    if tmp_sum_a > x:
        continue
    elif tmp_sum_a == x:
        choice_cnt += 1
        continue
    for j in range(b+1):
        tmp_sum_b = tmp_sum_a + j*100
        if tmp_sum_b > x:
            continue
        elif tmp_sum_b == x:
            choice_cnt += 1
            continue
        for k in range(c+1):
            tmp_sum_c = tmp_sum_b + k*50
            if tmp_sum_c > x:
                continue
            elif tmp_sum_c == x:
                choice_cnt += 1

print(choice_cnt)


Measured memory_bytes: 3064
def main():
    n, l = list(map(int, input().split()))
    a = [l + i for i in range(n)]
    if l < 0 and abs(l) >= n:
        score = sum(a[:n - 1])
    if l < 0 and abs(l) < n:
        score = sum(a)
    if l >= 0:
        score = sum(a[1:])
    print(score)


main()

Measured memory_bytes: 3060
#include<stdio.h>
 
int main(void)
 
{
 
int S, h, m, s;
 
scanf("%d", &S);
 
h = S / 3600;
m = (S % 3600) / 60;
s = S % 60;
 
printf("%d:%d:%d\n", h, m, s);
 
return 0;
 
}


Measured memory_bytes: 2112
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int A,B,C;
	while(cin>>A>>B>>C)
	{
		if(A==5&&B==5&&C==7)
		{
			cout<<"YES"<<endl;
		}
		else if(A==5&&B==7&&C==5)
		{
			cout<<"YES"<<endl;
		}
		else if (A==7&&B==5&&C==5)
		{
			cout<<"YES"<<endl;
		}
		else cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){

    int N;

    scanf("%d", &N);

    int min = 1000000000;

    int A[N];

    for(int i = 0; i < N; i++){
        int c = 0;
        scanf("%d", &A[i]);
        while(A[i] % 2 == 0){
            A[i] /= 2;
            c++;
        }
        if(c < min){
            min = c;
        }
    }

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

    return 0;
}

Measured memory_bytes: 1736
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,x,n) for(int i=x;i<n;i++)
#define breps(i,x,n) for(int i=x;i>=n;i--)
#define exrep(x,vec) for(auto&& x : vec);
#define PI 3.14159265358979323846264338327950288
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

/**
* ------------- ここからコード -------------
*/

int main(void) {

	ll a, b, c, d, x, y, n, m;
	ll ans = 0, cnt = 0;
	
	cin >> x;
	cout << (x >= 30 ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 3620
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func out(x ...interface{}) {
	//	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	Sa := getString()
	Sb := getString()
	Sc := getString()

	win := ""
	next := byte('a')
L:
	for {
		out("now", string(next), ":", string(Sa), string(Sb), string(Sc))
		switch next {
		case 'a':
			if len(Sa) == 0 {
				win = "A"
				break L
			}
			next = Sa[0]
			Sa = Sa[1:]
			//			out("A", Sa, "next", string(next))
		case 'b':
			if len(Sb) == 0 {
				win = "B"
				break L
			}
			next = Sb[0]
			Sb = Sb[1:]
			out("B", Sb, "next", string(next))
		case 'c':
			if len(Sc) == 0 {
				win = "C"
				break L
			}
			next = Sc[0]
			Sc = Sc[1:]
			//			out("C", Sc, "next", string(next))
		}
	}

	fmt.Println(win)
}


Measured memory_bytes: 640
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

int main(){
    std::ios::sync_with_stdio(false);
    ll n;
    ll v[5];
    ll min_v = 1ll << 62;
    cin >> n;
    for(int i=0;i<5;++i)
    {
        cin >> v[i];
        min_v = min(min_v, v[i]);
    }

    cout << (n-1) / min_v + 5 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4765
const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
 
mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}
mint f2(int n, int k) {
  return comb(n+k-1,k-1);
}
mint f(int n, int k) {
  if (n < k) return 0;
  if (n == 0 && k == 0) return 1;
  if (k < 1) return 0;
  return f2(n-k,k);
}
 
int main() {
  init();
  int n, k;
  cin >> n >> k;
 
  for (int i = 1; i <= k; i++) {
    mint blue = f(k,i);
    mint red = 0;
    {
      red += f(n-k,i-1);
      red += f(n-k,i);
      red += f(n-k,i);
      red += f(n-k,i+1);
    }
    mint ans = blue*red;
    printf("%lld\n", ans.x);
  }
  return 0;
}

Measured memory_bytes: 125568
#include<algorithm>
#include<chrono>
#include<ctime>  
#include<climits>
#include<functional>
#include<numeric>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<random>
#include<set>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<cassert>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
// #include<bits/stdc++.h>
using namespace std;
 
struct Debug{
    int cnt = 0;
    bool on = false;
    char debug[10] = "debug";
    template<class T>
    Debug & operator<<(const T & v) {
        if(on && cnt++ == 0) cerr << "debug: ";
        if(on) cerr << v << ' ';
        return *this;
    }
    Debug & operator<<(ostream&(*pManip)(ostream&)) {
        if(on) cerr << (*pManip);
        cnt = 0;
        return *this;
    }
} debug;
#define rep(i, a, b) for(auto i = (a); i < (b); i++)
#define rrep(i, a, b) for(auto i = (a); i > (b); i--)
#define all(v) (v).begin(), (v).end()
#define print(v) {if(debug.on){for(auto x : v) debug << x; debug << endl;}}
#define printn(v, n) {if(debug.on){for(int _i = 0; _i < n; _i++) debug << *(v + _i); debug << endl;}}
 
typedef unsigned long long ull;
typedef long long ll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

const int MAXN = 1e6 + 10;

int main(int argc, char * argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    if(argc > 1 && !strcmp(argv[1], debug.debug)) debug.on = true;

    int n;
    string s;
    cin >> n;
    cin >> s;
    int i = 0, j = 0, res = 0;
    while(i < n) {
    	for(j = i; j < n && s[i] == s[j]; j++);
    	res++;
    	i = j;
    }
    cout << res << endl;
    return 0;
 
}























Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set =
tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int a;
    cin>>a;
    vector<int>vec(a),att(a+1);
    for(auto &x:att)
        cin>>x;
    for(auto &x:vec)
        cin>>x;
    ll ans=0;
    for(int i=0;i<a;i++){
        int r=min(vec[i],att[i]);
        ans+=r;
        att[i]-=r;
        vec[i]-=r;
        r=min(vec[i],att[i+1]);
        ans+=r;
        att[i+1]-=r;
        vec[i]-=r;
    }
    cout<<ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
    using namespace std;
 
    #define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
    #define mod 1000000007
    #define qmod 998244353
    #define M 1000001
    #define endl "\n"
    #define all(a) (a).begin(),(a).end()
    #define rep(i,a,b) for(int i=a;i<b;++i)
    #define repr(i,a,b) for(int i=a;i>=b;--i)
    #define F first
    #define S second
    #define pb push_back
    #define mp make_pair
 
    typedef long long ll;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    typedef vector<string> vs;
    typedef vector<pii> vii;
    typedef vector<vi> vvi;

    struct node {
    ll num;
    string all;
};
    int main(){
        
   /* #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin); 
    freopen("output.txt","w",stdout);   
    #endif */ 

        fast;
        ll k;
        cin >> k;

        if (k <= 9) {
            cout << k << endl;
            return 0;
        }

        queue<struct node> q;
        rep(i, 1, 10) {
            struct node temp = {i, to_string(i)};
            q.push(temp);
        }

        ll cnt = 0;

        struct node t;
        while (cnt < k) {
            t = q.front(); q.pop();
            rep(i, t.num - 1, t.num + 2) {
                if (i < 0 || i > 9) continue;
                struct node temp = {i, t.all + to_string(i)};
                q.push(temp);
            }
            cnt++;
        }

        cout << t.all << endl;
        return 0;  
    }       
 
 
    //keep it simple stupid


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

using namespace std;
inline void
prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
//printf("%.12lf\n",mid);
int mod;

int mymod(int num){
  if (num< 0){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
map<string, vector<int> > cities;
int main ()
{
  prep ();
  
  int n;
  cin >> n;
  set<string> thiss;
  map<pair<string, int>, int> inds;
  for (int i=0; i<n; i++){
    string s;
    int sc;
    cin >> s >> sc;
    thiss.insert(s);
    cities[s].push_back(sc);
    inds[{s, sc}] = i;
  }
  for (string s : thiss){
    sort(cities[s].rbegin(), cities[s].rend());
  }
  for (string s : thiss){
    vector<int> vect = cities.find(s)->second;
    for (int i=0; i<vect.size(); i++){
      cout << inds.find({s, vect[i]})->second+1 << endl;
    }
  }
  return 0;
}
// in dp problems think: up until here, intervals, or "what if there's 1, 2, 3..."
// in math problems write out equations
// also in math problems to change multiplication/division to addition/subtraction use logs, add/subtract something to make the multiplication easier (like if it's 3*f(x)+2, change it to 3*(f(x)+1)-1)
// if printint pow function, put an (int) or (long long) next to it
// if checked everything check for bugs (like sorting wrong way or not putting a break in a loop)
// if n is 10^7 try brute force if the operations are simple
// if can't do dp do brute force/greedy
// to save time don't copy maps/vectors into variables if it already exists
// only use long long if need to
// if wrong on decimal problem, check if program rounds or if you can round to a certain amt of decimals
// if decimals too, if can subtract instead of divide
// in grid traversal problems check if doing sideways or not
// if TLE try to take away loop
// in recursion looking math problems look at things from the point of view of both sides (the start and the end sections of the recursion)
// think about how many possible answers there are to the problem
// if it makes it easier use +1 indexing
// think twice when writing things down that you're going to use later


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <iomanip>
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1001001000;
const int MOD = 1000000007;

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

using Graph = vector<vector<int>>;
//再帰とかグラフを使うときは予めNの最大値のグローバル配列を取っておく
int N;
vector<int> E[200001];
vector<bool> seen;
typedef pair<int, int> P;
int D[101];
//頂点状態を表すcolor[]において、0は未訪問、1は訪問中、2は完了を表す。
int color[101];
int find_time = 0;

//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;
    
    return res %= MOD;;
}
long long nCr(long long n, long long r) {
    long long A = 1, B = 1;
    //Aが分子Bが1/r!
    for (long long i = n - r + 1; i <= n; i++) {
        A = A * i % MOD;
    }
    for (long long i = 1; i <= r; i++) {
        B = B * i % MOD;
    }
    B = mod_pow(B, MOD - 2);
    B %= MOD;
    //Bは割るのではなく掛ける
    return (A * B) % MOD;
}

int main() {
    int N; cin >> N;
    int A = 0, B = 0;
    while (N >= 500) {
        A++;
        N -= 500;
    }
    while (N >= 5){
        B++;
        N -= 5;
    } 

    cout << A * 1000 + B * 5 << endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <list>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <ostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <iomanip>

#define N 30
#define INF (1 << 30)
#define NIL -1
using namespace std;
struct Node { int parent, lchild, rchild, sibling, depth, degree, height; } T[N];
int depth[N];
void setDepth(int root, int d)
{
	T[root].depth = d;
	if (T[root].lchild != NIL)
		setDepth(T[root].lchild, d + 1);
	if (T[root].rchild != NIL)
		setDepth(T[root].rchild, d + 1);
}
const char *str[3] = { "root", "leaf", "internal node" };
void print(int id)
{
	int status = 0;
	if (T[id].parent == NIL)
		status = 0;
	else if (T[id].lchild + T[id].rchild == -2)
		status = 1;
	else
		status = 2;
	printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, %s\n",
			id, T[id].parent, T[id].sibling, T[id].degree, T[id].depth, T[id].height, str[status]);
}

int getHeight(int root)
{
	if (root == NIL)
		return -1;
	return T[root].height = max(getHeight(T[root].lchild), getHeight(T[root].rchild)) + 1;
}
int main()
{
	int n, id, k, lchild, rchild;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		T[i].parent  = T[i].sibling  = NIL;
	}
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &id);
		scanf("%d %d", &T[id].lchild, &T[id].rchild);
		if (T[id].lchild != NIL)
		{
			T[T[id].lchild].parent = id;
			T[T[id].lchild].sibling = T[id].rchild;
			++T[id].degree;
		}
		if (T[id].rchild != NIL)
		{
			++T[id].degree;
			T[T[id].rchild].parent = id;
			T[T[id].rchild].sibling = T[id].lchild;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		if (T[i].parent == NIL)
		{
			setDepth(i, 0);
			getHeight(i);
			break;
		}
	}
	for (int i = 0; i < n; ++i)
		print(i);
	return 0;
}

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


Measured memory_bytes: 5164
#include <bits/stdc++.h>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

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

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}
template<typename T1, typename T2> ostream& operator << (ostream& s, const pair<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}

void zeta(vec<P>& f)
{
   int n = f.size();
   for (int i = 0; (1 << i) < n; i++) {
      for (int j = 0; j < n; j++) {
         if ((j >> i) & 1) {
            vec<int> tmp;
            tmp.PB(f[j].first);
            tmp.PB(f[j].second);
            tmp.PB(f[j ^ (1 << i)].first);
            tmp.PB(f[j ^ (1 << i)].second);
            RSORT(tmp);
            f[j].first = tmp[0];
            f[j].second = tmp[1];
         }
      }
   }
}

signed main()
{
   int N; cin >> N;
   vec<int> A(1 << N);
   rep(s, 0, 1 << N) {
      cin >> A[s];
   }


   vec<P> f(1 << N, MP(0,0));
   rep(s, 0, 1 << N) {
      f[s].first = A[s];
   }

   dump(f)

   zeta(f);

   int MAX = 0;
   rep(s, 1, 1 << N) {
      MAX = max(MAX, f[s].first + f[s].second);
      cout << MAX << endl;
   }

   return 0;
}


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

using namespace std;

// #define LOG(...) fprintf(stderr,__VA_ARGS__)
#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int main() {
    string line;
    while (cin >> line, line != "#") {
        vector<bool> nw;
        int idx = 0;
        char flag = 0;
        char n_flag = 1;
        char w_flag = 2;
        while(idx < line.length()){
            if (line[idx] == 'n'){
                nw.push_back(true);
                idx += 5;
                flag |= n_flag;
            }else{
                nw.push_back(false);
                idx += 4;
                flag |= w_flag;
            }
        }

        LOG("flag %d\n", flag);
        switch (flag) {
            case 1:
                cout << 0 << endl;
            break;
            case 2:
                cout << 90 << endl;
            break;
            case 3:
                ll a = 45, b = 1;
                for(int i = nw.size()-3; i >= 0; i--){
                    bool r = nw[i];
                    a *= 2;
                    b *= 2;
                    if (r){
                        a -= 45;
                    }else{
                        a += 45;
                    }
                }
                LOG("a: %d \n", a);
                while(a % 2 == 0)
                    a /= 2;

                cout << a;
                if (b != 1)
                    printf("/%d", b);
                cout << endl;
            break;
        }
    }
}

Measured memory_bytes: 1228
import java.util.*;

public class Main {
	 
	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		
		int res[]=new int[26];
		
		while(cin.hasNext()) {
			String str=cin.nextLine();
			for(int i=0;i<str.length();i++) {
				char c=str.charAt(i);
				if(c>=65 && c<=90)res[c-65]++;
				else if(c>=97 && c<=122)res[c-97]++;
			}
		}
		
		for(int i=0;i<26;i++) {
			System.out.println((char)(i+97)+" : "+res[i]);
		}
		
	}
	
}


Measured memory_bytes: 26164
#include <bits/stdc++.h>
#define sz(x) (int((x).size()))
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
template<typename T> bool domax(T &a, T b) { return (b > a ? (a = b, true) : false); }
template<typename T> bool domin(T &a, T b) { return (b < a ? (a = b, true) : false); }
typedef long long ll;

int n, m, a[105];
std::vector<int> o;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", a+i);
        if (a[i]%2) o.pb(i);
    }
    if (sz(o) > 2) {
        printf("Impossible\n");
    } else {
        if (sz(o) >= 1) std::swap(a[o[0]], a[0]);
        if (sz(o) >= 2) std::swap(a[o[1]], a[m-1]);
        for (int i = 0; i < m; i++) printf("%d%c", a[i], " \n"[i == m-1]);
        if (m == 1 && a[0] > 1) {
            a[0]--;
            a[1] = 1;
            m++;
        } else {
            a[0]++;
            a[m-1]--;
            if (!a[m-1]) m--;
        }
        printf("%d\n", m);
        for (int i = 0; i < m; i++) printf("%d%c", a[i], " \n"[i == m-1]);
    }
}


Measured memory_bytes: 256
P = 10**9+7
fac = [1]
ifac = [1]
ff = 1
for i in range(1,200001):
  ff *= i
  ff %= P
  fac.append(ff)
  ifac.append(pow(ff, P-2, P))
def ncr(n, r): 
  return (fac[n] * ifac[r] % P * ifac[n-r] % P);

h,w,a,b = map(int,input().split())
s = 0
nC = b-1
kC = 0
nD = w-b-1+h-1
kD = h-1
for i in range(h-a):
  C = ncr(nC, kC)
  D = ncr(nD, kD)
  s = (s + C * D) % P
  nC += 1
  kC += 1
  kD -= 1
  nD -= 1
print(s)


Measured memory_bytes: 24808
from functools import reduce
N,M = map(int,input().split())
a = list(map(int,input().split()))
count = 0
while True:
    if a[0] % 2 == 1:
        break
    a[0] //= 2
    count += 1

flag = True
for i in range(1,N):
    if a[i] % (2**count) == 0 and a[i]% (2**(count+1)) != 0:
        a[i] //= 2**count
    else:
        flag = False
        break

def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a # int
    return a * b // gcd(a, b) # int
if not flag:
    print(0)
else:
    L = reduce(lcm,a)*2**(count-1)
    print((M//L+1)//2)

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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define X first
#define Y second
#define INF 1000 * 1000 * 1000
#define LL long long
#define LINF INF * (LL)INF
#define PB push_back
#define SZ(a) ((LL)a.size())
#define INVALID 2392139
const LL MAX = 300005;
const LL minim = -1000 * 1000 - 1;
const LL mod = 1000 * 1000 * 1000 + 7;
const LL zsuv = MAX;
using namespace std;
using namespace __gnu_pbds;
int n;
int main()
{
	string s;
	cin >> s;
	int ans = 0;
	for(auto x : s)
		ans += x == 'o';
	cout << ((ans + 15 - SZ(s)) >= 8 ? "YES" : "NO");
	
}


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

int main()
{
    int h, w;

    while (true)
    {
        cin >> h >> w;
        
        if(h == 0 && w == 0){
            break;
        }
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3092
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

int main(){
	double x1,x2,xp,y1,y2,yp1,yp,naiseki,norm1,norm2,gaiseki;
	int q;

	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	scanf("%d",&q);

	for(int i=0; i < q; i++){
		scanf("%lf %lf",&xp,&yp);
		norm1 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
		norm2 = sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));
		naiseki = (xp-x1)*(x2-x1)+(yp-y1)*(y2-y1);
		gaiseki = (x2-x1)*(yp-y1)-(xp-x1)*(y2-y1);
		if(fabs(naiseki/(norm1*norm2)+1) < 0.00000001){
			printf("ONLINE_BACK\n");
		}else if(fabs(naiseki-norm1*norm2)< 0.00000001){
			if(norm1 >= norm2){
				printf("ON_SEGMENT\n");
			}else{
				printf("ONLINE_FRONT\n");
			}
		}else if(gaiseki > 0){
			printf("COUNTER_CLOCKWISE\n");
		}else{
			printf("CLOCKWISE\n");
		}
	}

    return 0;
}



Measured memory_bytes: 2752
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
#define PI acos(-1.0);

const double EPS = 1e-10;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;



int main(){
	int N; cin >> N;
	vector<Pl> xl(N);
	rep(i,N){
		cin >> xl[i].first >> xl[i].second;
		xl[i].first += xl[i].second;
	}
	sort(xl.begin(),xl.end());
	ll now = -LINF;
	int ans = 0;
	rep(i,N){
		if(xl[i].first-xl[i].second*2 >= now){
			now = xl[i].first;
			ans++;
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

void ABC106C()
{
	string S;
	cin >> S;
	ll K;

	cin >> K;
	--K;
	ll N = 5000000000000000;
	for (int i = 0; i < S.size(); ++i)
	{
		char s = S[i];
		int x = atoi(&s);
		if (x > 1)
		{
			cout << std::to_string(x) << endl;
			return;
		}
		if (i == K)
		{
			break;
		}
	}
	cout << '1' << endl;
}

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

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

int main()
{
	int n, p[3][1000],ans=0;
	bool flag[1000];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> p[0][i] >> p[1][i] >> p[2][i];

		if (p[1][i] > p[2][i]) {
			swap(p[1][i], p[2][i]);
		}
		if (p[0][i] > p[1][i]) {
			swap(p[0][i], p[1][i]);
		}
		if (p[1][i] > p[2][i]) {
			swap(p[1][i], p[2][i]);
		}
	}

	for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j < n; j++) {
			if (p[0][i] == p[0][j] && p[1][i] == p[1][j] && p[2][i] == p[2][j]) {
				flag[j] = true;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (flag[i] == true) {
			ans += 1;
		}
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

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

	int N;
	cin >> N;
	int A[100005];
	int sum = 0;

	for (int i = 1; i <= N; i++)
	{
		cin >> A[i];
	}
	for (int i = 0; i <= N; i++) {
		sum += abs(A[i] - A[i+1]);
	}

	for (int i = 1; i <= N; i++)
	{
		int ans = sum - abs(A[i-1] - A[i]) - abs(A[i] - A[i + 1]) + abs(A[i - 1] - A[i + 1]);
		cout << ans << endl;
	}
	return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(){
	ll R, G;
	cin >> R >> G;

	cout << R + 2*(G - R) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
	ll n,a,b;
	scanf("%lld %lld %lld",&n,&a,&b);
	if(a>b)swap(a,b);
	if((b-a)%2==0){
		printf("%lld\n",(b-a)/2);
	}else{
		ll ans=min(a-1,n-b)+1;
		printf("%lld\n",ans+(b-a)/2);
	}
	return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL bit[100001];
int n;
LL max_q(int i) {
	LL ret = 0;
	while (i > 0) {
		ret = max(ret, bit[i]);
		i -= i&-i;
	}
	return ret;
}
void update(int i, LL x) {
	bit[i] = max(bit[i], x);
	while (i <= n) {
		bit[i] = max(bit[i], x);
		i += i&-i;
	}
}
int main() {
	cin >> n;
	LL sum = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		LL r = max_q(x - 1);
		update(x, r + x);
		sum += x;
	}
	cout << sum - max_q(n) << endl;
}


Measured memory_bytes: 3872
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 整数の入力
        int n = sc.nextInt();
        
        String[] b = new String[n];
        for(int i=0;i<n;i++){
            b[i] = sc.next();
        }
        Arrays.sort(b);
        String tmp = "";
        int cnt = 0;
        for(int i=0;i<n;i++){
            if(!tmp.equals(b[i])){
                cnt++;
                tmp = b[i];
            }
        }

        System.out.println(cnt);
    }
}


Measured memory_bytes: 69924
N = int(input())
S = input()

animals_ans = []
# sheep = 1, wolf = 0
def hypo(sheep, ans, w):
    animals = []
    for _ in range(N):
        animals.append(-1)
    animals[0] = sheep
    if sheep + ans != 1:
        if w == 0:
            animals[N-1] = 1
            animals[1] = 1
        else:
            animals[N-1] = 0
            animals[1] = 0
    else:
        if w == 0:
            animals[N-1] = 0
            animals[1] = 1
        else:
            animals[N-1] = 1
            animals[1] = 0
    for n in range(1, N):
        if (animals[n] == 1 and S[n] == 'o') or  (animals[n] == 0 and S[n] == 'x'):
            if n == N-2 and animals[n+1] != animals[n-1]:
                return 0
            elif n == N-1:
                if animals[n-1] != animals[0]:
                    return 0
                else:
                    return animals
            else:
                animals[n+1] = animals[n-1]
        else:
            if n == N-2 and animals[n+1] == animals[n-1]:
                return 0
            elif n == N-1:
                if animals[n-1] == animals[0]:
                    return 0
                else:
                    return animals
            else:
                animals[n+1] = 1 - animals[n-1]

def arr2str(arr):
    st = ''
    for n in arr:
        if n == 1:
            st += 'S'
        else:
            st += 'W'
    return st

ans = 1 if S[0] == 'o' else 0

# how to print the answer...
animals_ans = hypo(1, ans, 0)
if animals_ans == 0:
    animals_ans = hypo(1, ans, 1)
    if animals_ans == 0:
        animals_ans = hypo(0, ans, 0)
        if animals_ans == 0:
            animals_ans = hypo(0, ans, 1)
            if animals_ans == 0:
                print(-1)
            else:
                print(arr2str(animals_ans))
        else:
            print(arr2str(animals_ans))
    else:
        print(arr2str(animals_ans))
else:
    print(arr2str(animals_ans))

Measured memory_bytes: 4332
#include<stdio.h>

void trace(int A[], int N){
    int i;
    for( i = 0; i < N; i++ ) {
        if( i > 0 ) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

void insertionSort(int A[], int N){
    int i, j, v;
    for(i = 1; i < N; i++){
        v = A[i];
        j = i - 1;
        while(j >= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        trace(A, N);
    }
}

int main(){
    int N, i, j;
    int A[100];
    
    scanf("%d", &N);
    for(i = 0; i < N; i++) scanf("%d", &A[i]);
    
    trace(A, N);
    insertionSort(A, N);
    
    return 0;
}


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

int main() {
  string a,b,c;
  cin >> a >> b >> c;
  bool flag = false;
  if(a.at(a.size()-1) == b.at(0)) {
    if(b.at(b.size()-1) == c.at(0)) flag = true;
  }
  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

int main() {
	int n,k;
	cin>>n>>k;
   long long int arr[n]={0},brr[n];
	int i=0,j=0;
	for(i=0;i<n;i++)
	{
	    cin>>arr[i];
	}
brr[0]=0;
	for(i=1;i<n;i++)
	{
	   brr[i]=1000000000;
	    for(j=1;j<=k;j++)
	    if(j<=i)
	   brr[i]=min(brr[i],brr[i-j]+abs(arr[i]-arr[i-j])) ;
	}
	
	cout<<brr[n-1];
	
	return 0;
}


Measured memory_bytes: 1792
def compute_xor(n: int)->int:
    if n % 4 == 0:
        return n
    if n % 4 == 1:
        return 1
    if n % 4 == 2:
        return n + 1
    return 0


def xor_world(A: int, B: int)->int:
    return compute_xor(B) ^ compute_xor(A-1)


if __name__ == "__main__":
    A, B = map(int, input().split())
    ans = xor_world(A, B)
    print(ans)


Measured memory_bytes: 3060