akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;
 
/* constant */
 
/* typedef */
 
typedef vector<int> vi;
 
struct Node {
  int key;
  struct Node *l, *r;
  Node(): l(NULL), r(NULL) {}
  Node(int _k): key(_k), l(NULL), r(NULL) {}
};
 
/* global variables */
 
/* subroutines */
 
void insert(Node *(&root), Node *z) {
  Node *y = NULL, *x = root;
 
  while (x != NULL) {
    y = x;
    if (z->key < x->key) x = x->l;
    else x = x->r;
  }
 
  if (y == NULL) root = z;
  else if (z->key < y->key) y->l = z;
  else y->r = z;
}
 
bool find(Node *root, int key) {
  Node *x = root;
 
  while (x != NULL) {
    if (key == x->key) return true;
    x = (key < x->key) ? x->l : x->r;
  }
  return false;
}
 
void inorder(Node *nd, vi &v) {
  if (nd != NULL) {
    inorder(nd->l, v);
    v.push_back(nd->key);
    inorder(nd->r, v);
  }
}
 
void preorder(Node *nd, vi &v) {
  if (nd != NULL) {
    v.push_back(nd->key);
    preorder(nd->l, v);
    preorder(nd->r, v);
  }
}
 
void print_vec(vi &v) {
  for (int i = 0; i < v.size(); i++) printf(" %d", v[i]);
  putchar('\n');
}
 
/* main */
 
int main() {
  Node *root = NULL;
 
  int m;
  cin >> m;
 
  while (m--) {
    string op;
    cin >> op;
 
    if (op[0] == 'i') {
      int key;
      cin >> key;
      insert(root, new Node(key));
    }
    else if (op[0] == 'f') {
      int key;
      cin >> key;
      cout << (find(root, key) ? "yes" : "no") << endl;
    }
    else {
      vi v;
 
      v.clear();
      inorder(root, v);
      print_vec(v);
 
      v.clear();
      preorder(root, v);
      print_vec(v);
    }
  }
  return 0;
}


Measured memory_bytes: 17368
#include<bits/stdc++.h>
      using namespace std;
      #define ll long long
      #define pb push_back
      #define pll  pair <long long,long long>
      #define mp make_pair
      #define ss second
      #define ff first
      #define maa 1000000007
      #define endl '\n'
      #define ld long double
      #define all(x) x.begin(),x.end()
      ll  power(ll  i,ll  j)
      {
        if(j==0)
        return 1 ;
        ll t=power(i,j/2)%maa ;
        if(j%2==0)
        return (t%maa*t%maa)%maa ;
        else
        return ((t%maa*t%maa)%maa*(i%maa)%maa)%maa ;
      }
      bool is(ll  i)
      {
        if(i==1)
            return 0 ;
        ll  f=0 ;
        for(ll  j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                f=1 ;
                break ;
            }
        }
        return !f ;
      }
      int main()
      {

        /// 50-4
        /// freopen("input.txt","r",stdin);
        /// freopen("output.txt","w",stdout);
        ll  n ;
        cin>>n ;
        ll r[n+1];
        for(ll i=1;i<=n;i++)
        cin>>r[i] ;
        
        ll pre[n+1] ;
        memset(pre,0,sizeof(pre)) ;
        for(ll i=1;i<=n;i++)
        {
            pre[i]=pre[i-1]+r[i] ;
        }
        ll dp[n+1][n+1] ;
        for(ll i=0;i<=n;i++)
        {
            dp[i][i]=0 ;
            
        }
        for(ll l=2;l<=n;l++)
        {
            for(ll i=1;i<=n;i++)
            {
                ll j=i+l-1 ;
                if(j>n)
                break ;
                
                 dp[i][j]=LLONG_MAX ;
                
                for(ll k=i;k<j;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]) ;
                }
            }
        }
        cout<<dp[1][n]<<endl ;
        
        

      }








Measured memory_bytes: 1536
#include<iostream>
using namespace std;
int main(){
    int n , i , j;
    cin >> n;
    bool flg=0;
    for(i=1;i<=9;i++){
      for(j=1;j<=9;j++){
              if(i*j==n) flg=1;
      }
    }
    if(flg) 
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
}


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) begin(v),end(v)
#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; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int a, b;
	cin >> a >> b;
	puts([&] {
		return a * b % 2;
	}() ? "Odd": "Even");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<typename Integer>
bool isPrime(Integer x){
    for(Integer i = 2; i <= sqrt(x); i++){
        if(x%i == 0) return false;
    }
    return true;
}

int main(){
    int x;
    cin >> x;
    for(int i=0;;i++){
        if(isPrime(x+i)){
            cout << x+i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
  int n, m;
  cin >> n >> m;
  int l[110000], r[110000];
  rep(i,m) cin >> l[i] >> r[i];
  int left = 0;
  int right = n;
  rep(i,m) {
    left = max (left, l[i]);
    right = min (right, r[i]);
  }
  int ans = max(0, right-left+1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<functional>
#include<cmath>

#define REP(i,n) for(int i=0;i<n;i++)
#define ll long long int

using namespace std;

int to_int(string s) {
  return atoi(s.c_str());
}

int main() {
  int n,k;
  cin >> n >> k;
  if(n%k == 0) {
    cout << 0 << endl;
  } else {
    cout << 1 << endl;
  }
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int N = 1e2+5;
int bit[N],a[N],n;//N is the size of array + 1

void update(int x, int delta)
{
	for(;x <= n; x += x&(-x))
	{
		bit[x] += delta;
	}
}

int query(int x)
{
	int sum = 0;
	for(;x > 0;x -= x&(-x))
	{
		sum += bit[x];
	}
	return sum;
}

int sum(int l, int r)
{
    return query(r) - query(l-1);
}

void fileIO()
{
        #ifndef ONLINE_JUDGE
        freopen("int.txt","r",stdin);
        freopen("out.txt","w",stdout);
        #endif
}
int main()
{
	IOS;
   // fileIO();
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int x;cin >> x;
        update(i,x);
    }
    int m = 2e9;
    for(int i = 1;i <=n; i++)
    {
        m = min(m,abs(sum(1,i) - sum(i+1,n)));
    }
    cout << m;
	return 0;
}


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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, l;
  cin >> n >> l;
  vi a(n);
  int min_abs = INT_MAX;
  int min_abs_idx = 0;
  int sum = 0;
  for (int i = 0; i < n; i++) {
    a[i] = l + i + 1 - 1;
    // printf("%d ", a[i]);
    sum += a[i];
    if (min_abs > abs(a[i])) {
      min_abs = abs(a[i]);
      min_abs_idx = i;
    }
  }
  // printf("\n%d\n", min_abs);
  cout << sum - a[min_abs_idx] << endl;

  return 0;
}


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

int a,b,c,d,e,p[101];

int main()
{
cin>>a>>b;
ref(i,b) {
    cin>>c;
    p[c]++;}
    ref(i,100){
        if(a-i<=0) {cout<<a-i;return 0;}
        else if(!p[a-i]){cout<<a-i;return 0;}
        if(!p[a+i]) {cout<<a+i;return 0;}
    }

    return 0;
}


Measured memory_bytes: 3588
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] c = new int[m];

        for(int i=0; i<n; i++) {
            int k = sc.nextInt();
            for(int j=0; j<k; j++) {
                c[sc.nextInt()-1]++;
            }
        }
        int res = 0;
        for(int i=0; i<m; i++) {
            if(c[i]==n) res++;
        }
        System.out.println(res);
    }

}


Measured memory_bytes: 22868
#include <stdio.h>

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

int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  printf("%d\n", gcd(a, b));
  return 0;
}

Measured memory_bytes: 2716
#include<stdio.h>
#include<string.h>

int main()
{
    int ans=0,n,k,r,s,p,i;
    scanf("%d %d %d %d %d",&n,&k,&r,&s,&p);
    char t[n];
    int a[n];
    scanf("%s",t);
    for(i=0;i<n;i++)
    {
        a[i]=0;
    }
    for(i=0;i<k;i++)
    {
        a[i]=1;
        if(t[i]=='r')
        ans += p;
        else if(t[i]=='p')
        ans += s;
        else if(t[i]=='s')
        ans += r;
    }
    for(i=k;i<n;i++)
    {
        if(t[i]=='r')
        {
            if(t[i-k]!='r')
            {   
                ans += p;
                a[i]=1;
            }
            if(t[i-k]=='r' && a[i-k]!=1)
            {
                ans += p;
                a[i]=1;
            }
        }
        else if(t[i]=='p')
        {
            if(t[i-k]!='p')
            {
                ans += s;
                a[i]=1;
            }
            if(t[i-k]=='p' && a[i-k]!=1)
            {
                ans += s;
                a[i]=1;
            }
        }
        else if(t[i]=='s')
        {
            if(t[i-k]!='s')
            { 
                ans += r;
                a[i]=1;
            }
            if(t[i-k]=='s' && a[i-k]!=1)
            {
                ans += r;
                a[i]=1;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int bit[2005];
int n, a[2005];
int main() {
	cin >> n;
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	sort(a, a+n);
	long long ans = 0;
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			int k = upper_bound(a+j+1, a+n, a[i] + a[j] - 1) - a - 1;
			ans += max(0, k - j);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
	int num;
	long ans = 0;
	cin >> num;
	for(int i = 1;i <= num;i++){
		if(i % 3 != 0 && i % 5 != 0)ans += i;
	}

	cout << ans << endl;
 }



Measured memory_bytes: 3596
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: i32 = read();
    let m: i32 = read();
    let ans = n*(n-1)/2 + m*(m-1)/2;
    println!("{}", ans);
}

fn read<T: FromStr>() -> T {
	let stdin = stdin();
	let stdin = stdin.lock();
	let token: String = stdin
		.bytes()
		.map(|c| c.expect("failed to read char") as char)
		.skip_while(|c| c.is_whitespace())
		.take_while(|c| !c.is_whitespace())
		.collect();
	token.parse().ok().expect("failed to parse token")
}



Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <array>


std::array<long long, 13> updateState(
	const std::array<long long, 13>& last, int rightDigit)
{
	std::array<long long, 13> result = {0,0,0,0,0,0,0,0,0,0,0,0,0};
	for(int i=0; i<13; i++)
	{
		int newMod = (i*10 + rightDigit) % 13;
		result[newMod] += last[i];
	}
	return result;
}

std::array<long long, 13> updateStateAll(
	const std::array<long long, 13>& last)
{
	std::array<long long, 13> result = {0,0,0,0,0,0,0,0,0,0,0,0,0};
	for(int i=0; i<10; i++)
	{
		auto addArray = updateState(last,i);
		for(int k=0; k<13; k++)
		{
			result[k] += addArray[k];
		}
	}

	for(int i=0; i<13; i++)
	{
		result[i] = result[i] % 1000000007;
	}
	return result;
}



int main()
{
	std::string str;
	std::cin >> str;
	
	std::array<long long, 13> state = {1,0,0,0,0,0,0,0,0,0,0,0,0};
	for(const auto& c: str )
	{
		if( '0' <= c && c <= '9' )
		{
			state = updateState(state, c-'0');
		}
		else
		{
			state = updateStateAll(state);
		}
	}
	std::cout << state[5];
}


Measured memory_bytes: 512
A, B, C, D = gets.chomp.split("").map(&:to_i)

def sum_to_s(a, b)
  a.to_s + "+" + b.to_s
end

def minus_to_s(a, b)
  a.to_s + "-" + b.to_s
end

def ans_to_s(a)
  a + "=7"
end

sum_all = A + B + C + D

case (sum_all - 7) / 2
when 0
  ans = ans_to_s(sum_to_s(sum_to_s(A, B), sum_to_s(C, D)))
when B
  ans = ans_to_s(sum_to_s(minus_to_s(A, B), sum_to_s(C, D)))
when C
  ans = ans_to_s(minus_to_s(sum_to_s(A, B), sum_to_s(C, D)))
when D
  ans = ans_to_s(sum_to_s(sum_to_s(A, B), minus_to_s(C, D)))
when B + C
  ans = ans_to_s(minus_to_s(minus_to_s(A, B), sum_to_s(C, D)))
when B + D
  ans = ans_to_s(sum_to_s(minus_to_s(A, B), minus_to_s(C, D)))
when C + D
  ans = ans_to_s(minus_to_s(sum_to_s(A, B), minus_to_s(C, D)))
when B - C
  ans = ans_to_s(minus_to_s(minus_to_s(A, B), sum_to_s(C, D)))
when B - D
  ans = ans_to_s(sum_to_s(minus_to_s(A, B), minus_to_s(C, D)))
when C - D
  ans = ans_to_s(minus_to_s(sum_to_s(A, B), minus_to_s(C, D)))
end

puts ans


Measured memory_bytes: 1788
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var x = Console.ReadLine();

		var r = n;
		while (r % 2 == 0) r /= 2;
		var b = 2 * n / r;
		var cycles = Enumerable.Range(1, r).Where(i => r % i == 0).Select(i => b * i).ToArray();
		var counts = new MInt[cycles.Length];

		for (int i = 0; i < cycles.Length; i++)
		{
			var t = cycles[i] / 2;
			var sub = x.Substring(0, t);

			MInt p = 1;
			for (int j = t - 1; j >= 0; j--, p *= 2)
				counts[i] += p * (sub[j] - '0');

			var subs = new[] { sub, new string(sub.Select(c => c == '0' ? '1' : '0').ToArray()) };
			var x2 = string.Join("", Enumerable.Range(0, n / t).Select(j => subs[j % 2]));
			if (x2.CompareTo(x) <= 0) counts[i] += 1;
		}
		for (int i = 0; i < cycles.Length; i++)
			for (int j = i + 1; j < cycles.Length; j++)
				if (cycles[j] % cycles[i] == 0)
					counts[j] -= counts[i];

		Console.WriteLine(cycles.Zip(counts, (t, c) => t * c).Aggregate((u, v) => u + v).V);
	}
}

struct MInt
{
	const int M = 998244353;
	public long V;
	public MInt(long v) { V = (v %= M) < 0 ? v + M : v; }

	public static implicit operator MInt(long v) => new MInt(v);
	public static MInt operator +(MInt x, MInt y) => x.V + y.V;
	public static MInt operator -(MInt x, MInt y) => x.V - y.V;
	public static MInt operator *(MInt x, MInt y) => x.V * y.V;
}


Measured memory_bytes: 31224
#include <iostream>
#include <queue>
#include <map>
#include <deque>
#include <algorithm>
#include <set>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <cstring>
#include <climits>
#include <iostream>


#define ll long long
#define p 1000000007
using namespace std;
//const ll MOD = (int) 10e9 + 7;

/*ll dp[100001];
vector<vector<ll>>adj;
ll dfs(ll node)
{
    if (dp[node] != -1)
        return dp[node];

    ll ans = 0;
    for (int i = 0; i < adj[node].size(); i++)
    {
        ans = max(dfs(adj[node][i]) + 1, ans);

    }
    return dp[node] = ans;
}
*/


ll factorial(ll n)
{
    if (n == 1 || n == 0)
        return 1;
    return  n * factorial(n - 1);
}

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

    ll n;
    cin >> n;
    int mp[n][n];
    ll dp[1 << n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> mp[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (ll mask = 0; mask < (1 << n); mask++)
    {
        ll men = __builtin_popcount(mask);
        if (men == n)
            continue;
        for (ll g = 0; g < n; g++)
        {
            if (mp[men][g] && !((1 << g) & mask))
            {
                ll newMask = mask | (1 << g);
                dp[newMask] += dp[mask];
                dp[newMask] %= p;
            }
        }
    }
    cout << dp[(1<<n) - 1];

    /*std::cout<<std::fixed;
    std::cout<<std::setprecision(10)<<ans;*/
             //   dp[i][i + 1 + j] = min(dp[i][i + j] + (pre[i + j + 2] - pre[i]),dp[i + 1][i + 1 + j] + (pre[i + j + 2] - pre[i]));

    return 0;
}


Measured memory_bytes: 16768
import java.util.*;
public class Main {
	public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
      // 取得
	  String s = sc.next();
      if(check(s)){
        System.out.println("YES");
      }else{
        System.out.println("NO");
      }
    }
    //キーエンスかな
    static boolean check(String s){
        if(s.equals("keyence")){
          return true;
        }else{
          for(int i=0;i<s.length();i++){
          	for(int j=i+1;j<=s.length();j++){
            	 String str = s.substring(0,i)+s.substring(j);
                 if(str.equals("keyence")){
                   return true;
                 }
          	}
          }
        }
      return false;
    } 
}

Measured memory_bytes: 40428
n, x = map(int, input().split())

layers, patties = [1],[1]
for i in range(n):
    layers.append(layers[-1] * 2 + 3)
    patties.append(patties[-1] * 2 + 1)

def solve(cur, level):
    if level == 0:
        return 1 if cur > 0 else 0
    elif (layers[level] // 2) >= cur:
        return solve(cur - 1, level - 1)
    else:
        return solve(cur - layers[level-1] - 2, level - 1) + patties[level-1] + 1

print(solve(x,n))

Measured memory_bytes: 3064
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {
        n:usize,m:usize,
        lr:[(Usize1,Usize1);m],
    }
    let mut lmax = 0;
    let mut rmax = n;
    for &(l, r) in lr.iter() {
        lmax = max(lmax, l);
        rmax = min(rmax, r + 1);
    }
    println!("{}", max(0, rmax.saturating_sub(lmax)));
}


Measured memory_bytes: 4612
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=155;
int n,k,mod;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
namespace Case1 //Even number solver
{
	int f[N][N];
	inline int calc(CI n,CI k)
	{
		RI i,j; for (f[0][0]=i=1;i<=n;++i) for (f[i][0]=f[i-1][0],j=1;j<=k;++j)
		inc(f[i][0],f[i-1][j]),f[i][j]=f[i-1][j-1];
		int ret=0; for (i=0;i<=k;++i) inc(ret,f[n][i]); return ret;
	}
	inline void solve(void)
	{
		printf("%d",1LL*calc(n>>1,k>>1)*calc(n-(n>>1),k>>1)%mod);
	}
};
namespace Case2 //Odd number solver
{
	int f[N][N][N],ans;
	inline void solve(void)
	{
		RI i,j,p; for (f[0][0][0]=i=1;i<=n;++i)
		{
			int r=i<<1,l=r-k,fl=1<=l&&l<=n,fr=1<=r&&r<=n;
			for (j=0;j<=n;++j) for (p=0;p<=k+1;++p)
			{
				inc(f[i][0][0],f[i-1][j][p]); if (fr) inc(f[i][j+1][0],f[i-1][j][p]);
				if (fl&&p+1<k+2) inc(f[i][0][p?p+1:p],f[i-1][j][p]);
				if (fl&&fr&&max(j+2,p+1)<k+2) inc(f[i][j+1][max(j+2,p+1)],f[i-1][j][p]);
			}
		}
		for (i=0;i<=n;++i) for (j=0;j<=k+1;++j)
		inc(ans,f[n][i][j]); printf("%d",ans);
	}
};
int main()
{
	scanf("%d%d%d",&n,&k,&mod); if (k&1) Case2::solve();
	else Case1::solve(); return 0;
}

Measured memory_bytes: 14464
#include<stdio.h>

int main(void){
    int a,x;
    int max=-1000000,min=1000000;
    long int sum=0;
    
    scanf("%d\n",&a);
    for(int i=0;i<a;i++){
       scanf("%d ",&x);
       if(min>x){
           min = x;
       }
       if(max<x){
           max = x;
       }
       sum += x;
    }
    printf("%d %d %ld\n",min,max,sum);
}


Measured memory_bytes: 2092
gets
a=gets.split.map(&:to_i).group_by(&:itself)
puts a.map{|k, v|
    x=a[k-1] ? a[k-1].size : 0
    y=v.size
    z=a[k+1] ? a[k+1].size : 0
    x+y+z
}.max


Measured memory_bytes: 18308
import math

data = input().split()
N = int(data[0])
A = int(data[1])
B = int(data[2])

#各桁の和を計算する関数
def digit_total(x):
    total = 0
    while x > 0:
        total += x % 10
        x /= 10
        x = math.floor(x)#小数点以下を切り捨てる
    return(total)

total = 0
ans = 0
for i in range(1,N+1):
    total = digit_total(i)
    if A <= total and total <= B:
        ans += i
        
print(ans)

Measured memory_bytes: 40432
<?php
fscanf(STDIN, "%d %d", $N, $K);
fscanf(STDIN, "%s", $S);
$a = str_split($S);
$l = $r = [];
$cursor = 0;
for ($i = 0; $i < $N; $i++) {
    if ($i === 0) {
        if ($a[$i] === '0') {
            $l[$cursor] = $i + 1;
            $cursor++;
        }
        if ($a[$i] === '1') {
            $l[$cursor] = $i + 1;
        }
    } else if ($i === $N - 1) {
        if ($a[$i] === '0') {
            if ($a[$i - 1] === '1') $cursor++;
            $r[$cursor] = $N;
        } else {
            $r[$cursor] = $N;
        }
    } else {
        if ($a[$i] === '1') {
            if ($a[$i - 1] === '0') {
                $l[$cursor] = $r[$cursor] = $i + 1;
            }
            $r[$cursor] = $i + 1;
        }
        if ($a[$i] === '0') {
            if ($a[$i - 1] === '1') {
                $cursor++;
            }
        }
    }
}
$tmp = [];
if ($r) {
    for ($i = max(array_keys($r)); $i > 0; $i--) {
        if (!isset($l[$i - $K])) break;
        $tmp[] = $r[$i] - $l[$i - $K] + 1;
    }
}

if (! $tmp) $tmp[] = $N;

printf("%d", max($tmp));


Measured memory_bytes: 18936
#include <iostream>
using namespace std;
typedef long long ll;
bool ans = true;
ll res;
string str;
int main(void){
    // Your code here!
    cin >> str;
    ll len = str.length(), r = 0, l = len - 1;
    while(r < l){
        if (str[r] == str[l]) {
            r++, l--;
        } else if (str[r] == 'x') {
            r++, res++;
        } else if (str[l] == 'x') {
            l--, res++;
        } else {
            ans = false;
            break;
        }
    }
    cout << (ans ? res : -1) << endl;
}


Measured memory_bytes: 512
s = gets.chomp.chars
k = gets.to_i

arr = (s * 2).chunk_while{|a,b|a==b}.to_a
# p arr
res = arr.map{|a|
  a.size/2
}.inject(:+) # S2つ分の書き換える量

if arr[0][0] == arr[-1][-1] && arr[0].size.odd? && arr[-1].size.odd?
  res += 1
end
result = res * (k/2)
result += res/2 if k.odd? # 調整分


result -= 1 if arr[0][0] == arr[-1][-1] && arr[0].size.odd? && arr[-1].size.odd?


# result += res if k.odd?
# p res
# p res/2

p result
#                       # #
# 1 2  3          4 5 6 7 8 9 10 11 12
# 4 81 8999939997 3 1 1 2 5 6 6  1  2


Measured memory_bytes: 1788
#include<iostream>

using namespace std;

int main()
{
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            cout << i << 'x' << j << '=' << i * j << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2984
#include <stdio.h>
#include <stdlib.h>

#define LINE_BUF_SIZE 1024

int main(void){
    // Your code here!
    static char line[LINE_BUF_SIZE];
    
    while(fgets(line, sizeof(line), stdin) != NULL) {
        int a, b;
        sscanf(line, "%d %d", &a, &b);
        if(a == 0 && b == 0) {
            break;
        }
        
        int ans1 = 0;
        int ans2 = a + b;
        int i;
        
        for(i = 1; i < 5; i++) {
            fgets(line, sizeof(line), stdin);
            sscanf(line, "%d %d", &a, &b);
            if(ans2 < a + b) {
                ans2 = a + b;
                ans1 = i;
            }
        }
        
        char c = ans1 + 'A';
        printf("%c %d\n", c, ans2);
    }
    return 0;
}



Measured memory_bytes: 1972
let () =
  let max = Scanf.scanf "%d\n" (fun a -> a) in

  let rec pow (x, y) =
    if y = 0 then 1 else x * pow (x, y - 1)
  in

  let rec f x n res = 
    if x = 1 then res else (
      let v = pow (x,n) in
      let res = (if v <= max && v > res then v else res) in
      (
        if v > max then
          f (x-1) 2 res
        else
          f (x) (n+1) res
      )
    )
  in

  print_endline (string_of_int (f max 2 1))


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int n,k;cin>>n>>k;
    vector<int> x(n);
    ll ans=1e18;
    for(int i=0;i<n;i++) cin>>x[i];
    for(int l=0;l<n-k+1;l++){
        int r=l+k-1;
        ll time;
        if(x[l]<0&&x[r]<=0) time=abs(x[l]);
        else if(x[l]>=0&&x[r]>0) time=x[r];
        else time=x[r]+abs(x[l])+min(x[r],abs(x[l]));
        ans=min(ans,time);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
X, K, D = map(int, input().split())
X = -X if X < 0 else X
N = X // D
if D * K < X:
  ret = X - (D * K)
else:
  M = X % D
  if (K - N) % 2 == 0:
    ret = M
  else:
    ret = D - M
print(ret)

Measured memory_bytes: 9176
#include <cstdio>

int main() {
  int N;
  scanf("%d", &N);

  double res = 0;
  for (int i = 0; i < N; ++i) {
    double u;
    char x[4];
    scanf("%lf %s", &u, x);

    if (*x == 'B') u *= 380000;
    res += u;
  }
  printf("%.12e\n", res);
}


Measured memory_bytes: 256
s=list(input())
o0=o1=e0=e1=0
for i in range(len(s)//2):
    if s[i*2]=="0":
        o0+=1
    elif s[i*2]=="1":
        o1+=1
    if s[i*2+1]=="0":
        e0+=1
    elif s[i*2+1]=="1":
        e1+=1
if len(s)%2==1:
    if s[len(s)-1]=="0":
        o0+=1
    else:
        o1+=1
print(min( o1+e0,e1+o0 ))


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

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

template <typename T1, typename T2> 
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VVLL item(n, VLL(3, 0));
  rep(i, n) cin >> item[i][0] >> item[i][1] >> item[i][2];
  ll dp[n + 1][3] = {0};
  rep(i,n){
    rep(j,3){
      rep(k,3){
        if(k == j)
          continue;
        chmax(dp[i + 1][j], dp[i][k] + item[i][j]);
      }
    }
  }
  ll ans = 0;
  rep(i, 3) chmax(ans, dp[n][i]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 11104
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N=II()
#ans=[0 for _ in range(10050)]
ans=[0]*10050
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      n=i*i+j*j+k*k+i*j+j*k+k*i
      if n<10050:
        ans[n]+=1
for i in range(1,N+1):
  print(ans[i])


Measured memory_bytes: 9460
N, X, M = map(int, input().split())
list=[0]*M
X1=X
for i in range(M):
  list[i]=(i**2)%M
  
l=[0]*M
l[X]=1
while l[list[X]]==0:
  l[list[X]]+=1
  X=list[X]
while l[list[X]]==1:
  l[list[X]]+=1
  X=list[X]
  
n1=l.count(1)
n2=l.count(2)

loop1=[0]*n1
for i in range(n1):
    loop1[i]+=X1
    X1=list[X1]
    
loop2=[0]*n2
for i in range(n2):
    loop2[i]+=X1
    X1=list[X1]
        
if N<=n1:
  print(sum(loop1[:N]))
else:
  print(sum(loop1)+(N-n1)//n2*sum(loop2)+sum(loop2[:(N-n1)%n2]))

Measured memory_bytes: 72128
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int K, X;
    cin >> K >> X;
    write(500 * K >= X ? "Yes" : "No");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k;
char s[505];
int d,n,r;
int calc(int len){
    int ret=0,f=0;
    for (int i=1;i<len;i++){
        if (s[i]==s[i-1]){
            if (!f) f=1,ret++;
            else f=0;
        } else f=0;
    }
    return ret;
}
int main(){
    scanf("%s%lld",s,&k);
    n=strlen(s);
    for (int i=0;i<n*3;i++) s[i+n]=s[i];
    d=calc(n*3)-calc(n);
    r=(k-1)%2+1;
    printf("%lld\n",(k-r)/2*d+calc(r*n));
}


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

int main(){
    int h, w;
    
    while(1){
        cin >> h >> w;
        
        if((h == 0) && (w == 0)) break;
        
        for(int i = 0;i < w; i++){
            cout << "#";
        }
        cout << endl;
        
        for(int i = 0;i < h - 2; i++){
            cout << "#";
            for(int j = 0;j < w - 2; j++){
                cout << ".";
            }
            cout << "#" << endl;
        }
        
        for(int i = 0;i < w; i++){
            cout << "#";
        }
        
        cout << endl << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3116
/*

*/
#include <bits/stdc++.h>

using namespace std;

#define ll           long long int
#define vi 			 vector<int>
#define pb           push_back
#define fi           first
#define si           second
#define pii 		 pair<int,int>
#define vii 		 vector<pair<int,int>>
#define F(a,n)       for(int i=0;i<n;i++){cin>>a[i];}
#define P(a,n)       for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define fastIO       ios_base::sync_with_stdio(false); cin.tie(NULL);
#define F1(a,n)      for(int i=1;i<=n;i++){cin>>a[i];}
#define P1(a,n)      for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;
#define mem(a,b)     memset(a, b, sizeof a)
#define matrix(x) 	 vector<vector<x>>
#define NF(a,n,m)    for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}
#define NF1(a,n,m)   for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}
#define PNF(a,n,m)   for(int i=0;i<n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
#define PNF1(a,n,m)  for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}cout<<endl;}cout<<endl;
const int nax = 1e6 + 1;
const int mod = 1e9+7;
ll n, dp[nax][2][2];
ll func(int i, bool nine, bool zero){
	//base case
	if(i == n){
		return ((nine)&&(zero));
	}
	//recursive case
	if(dp[i][nine][zero]!=-1){return dp[i][nine][zero];}
	ll op1 = func(i+1, 1, zero)%mod;
	ll op2 = func(i+1, nine, 1)%mod;
	ll op3 = (8 * func(i+1, nine, zero))%mod;

	return dp[i][nine][zero] = (op1 + op2 + op3)%mod;
}

int main(){
	fastIO
    mem(dp, -1);
	cin>>n;
	cout<<func(0, 0, 0);
}

Measured memory_bytes: 112848
N = int(input())
P = list(map(int, input().split()))


A = [i * N for i in range(1, N + 1)]
B = [-1] * N

p = P[0]
B[p - 1] = N * (N - p + 1)

for x, y in zip(P[:-1], P[1:]):
    x -= 1
    y -= 1
    Xsum = A[x] + B[x]
    Ysum = Xsum + 1
    B[y] = Ysum - A[y]

print(*A)
print(*B)


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
//#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector< vvi > vvvi;
typedef vector<short> vs;
typedef vector<vs> vvs;
typedef vector<vvs> vvvs;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<ld> vld;
typedef vector<vld> vvld;
typedef vector<vvld> vvvld;
typedef vector<string> vst;
typedef vector<vst> vvst;
typedef pair<ld, ld> pld;
typedef complex<double> base;

#define inmin(a, b) a = min(a, (b))
#define inmax(a, b) a = max(a, (b))
#define mp(a,b) make_pair(a,b)
#define modsum(a, b) ((a) + (b) >= M ? (a) + (b) - M : (a) + (b))
#define modsubtract(a, b) ((a) - (b) < 0 ? (a) - (b) + M : (a) - (b))
#define modmultiply(a, b) (((a) * (b)) % M)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define sqr(x) ((x) * (x))
#define fori(i, n) for(int i = 0; i < int(n); ++i)
#define cint const int &
#define SZ(a) ((int)((a).size()))
#define watch(x) cout << (#x) << " = " << (x) << endl;

const double PI = 2 * acos(0.0);

const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";


inline void transpose(vector<string> &a) {

    int n = a.size();
    if (n == 0) return;
    int m = a[0].size();
    vector<string> b(m, string(n, ' '));
    fori (i, n) fori (j, m) b[j][i] = a[i][j];
    a = b;
}


template<class T>
inline ostream & operator << (ostream &out, vector<T> &a) {
    out << "{";
    fori (i, SZ(a))
        out << a[i] << vector<string>{", ", "}"}[i + 1 == SZ(a)];
    return out;
}

void smain();

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


#ifdef MAX_HOME
    freopen("input.txt", "r", stdin);
    clock_t start = clock();
#define cerr cout
#endif
    cout << setprecision(12) << fixed;
    smain();
#ifdef MAX_HOME
    cout << "\n\n\n\n";
    cout << "TOTAL EXECUTION TIME: " << float( clock () - start ) /  CLOCKS_PER_SEC << endl;
#endif
}


const int N = 1e5 + 9;
const ll M = 1e9 + 7;
vi g[N];
int n;

ll dp[N][2];

void dfs(int v, int par) {

    ll dp0 = 1;
    ll dp1 = 1;
    for (int to : g[v]) if (to != par) {
        dfs(to, v);
        dp0 = (dp0 * (dp[to][1] + dp[to][0])) % M;
        dp1 = (dp1 * dp[to][0]) % M;
    }
    dp[v][0] = dp0;
    dp[v][1] = dp1;
}


void smain() {

    cin >> n;
    fori (iter, n - 1) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, -1);
    cout << (dp[1][0] + dp[1][1]) % M;
}

Measured memory_bytes: 14208
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

template<class T>
inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T>
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T>
inline T GCD(T a, T b) { return b ? GCD(b, a % b) : a; }
template<class T>
inline T LCM(T a, T b) { return (a + (b - 1)) / b; }
template<class T>
inline T round_int(T a, T b) {return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

class UnionFind {
private:
    int n;
    vector<int> a;
public:
    UnionFind(int n) : n(n), a(n, -1) {}
    int find(int x) { return a[x] < 0 ? x : (a[x] = find(a[x])); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool same(ii& p) { return same(p.first, p.second); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (a[x] > a[y]) swap(x, y);
        a[x] += a[y];
        a[y] = x;
        n--;
        return true;
    }
    bool unite(ii& p) { return unite(p.first, p.second); }
    int size() const { return n; }
    int size(int x) { return -a[find(x)]; }
};

int main() {
	ll n, m;
	cin >> n >> m;
	
	vl p(n), x(m), y(m);
    UnionFind uf(n + 1);

    rep(i, n) cin >> p[i];
    rep(i, m) {
        cin >> x[i] >> y[i];
        uf.unite(x[i], y[i]);
    }

    ll ans = 0;
    rep(i, n) {
        if (uf.same(i + 1, p[i])) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 2944
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#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(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD = 1e9 + 7;
static const bool DEBUG = false;

signed main() {
	int N; cin >> N;
	int ans = 0;
	rep(i, 1, N+1)ans += i;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
        
    def unite(self, x, y, w):
        px = self.find(x)
        py = self.find(y)
        
        if px == py:
            return True
        
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        elif self.rank[px] < self.rank[py]:
            px, py = py, px
            x, y = y, x
            w *= -1

        self.par[py] = px
        self.weight[py] = self.weight[x] - self.weight[y] - w
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

t = WeightedUnionFind(N + 1)
for l, r, d in X:
    if t.same(l, r):
        if t.diff(l, r) != d:
            print('No')
            break
    else:
        t.unite(l, r, d)
else:
    print('Yes')



Measured memory_bytes: 122584
import java.io.*;
import java.util.*;
public class Main {

    private static void solver(InputReader sc, PrintWriter out) {
            int a=  sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int k = sc.nextInt();
            long sum=0;
            for(int i=0;i<k && i<a;i++) sum +=1;
            k -=a; k-=b;
            for(int i=0; i<k && i<c; i++) sum-=1;
            out.println(sum);
    }
    public static void main(String[] args) throws Exception {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solver(in,out);
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int[] readIntArray(int n){
            int arr[] = new int[n];
            for(int i=0;i<n;i++) arr[i] = nextInt();
            return arr;
        }
    }
}
class Pair{
    int x,y;
    Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}

Measured memory_bytes: 32960
// https://atcoder.jp/contests/abc155/tasks/abc155_e

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

#define DEBUG 0
#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#if DEBUG
  #define DUMP(a) REP(_i, a.size()) cout << a[_i] << (_i + 1 == a.size() ? "\n" : " ")
  #define DUMP2D(b) REP(_j, b.size()) DUMP(b[_j]); cout << endl
#else
  #define DUMP(a)
  #define DUMP2D(b)
#endif

const int N_MAX = 1'000'000;

string N;

int L;
vector<vector<int>> dp;


int main() {
  cin >> N;

  L = N.size();

  dp = vector<vector<int>>(2, vector<int>(2));
  auto cur = dp[0];
  auto nxt = dp[1];
  cur[0] = 0;
  cur[1] = 1;

  DUMP(cur);

  REP(i, L) {
    int d = N[i] - '0';
    REP(j, 2) {
      int k = d + j;
      if (k == 0) {
        nxt[j] = cur[0];
      } else if (k <= 9) {
        nxt[j] = min(k + cur[0], 10 - k + cur[1]);
      } else {
        nxt[j] = cur[1];
      }
    }
    swap(cur, nxt);
    DUMP(cur);
  }

  int ans = cur[0];
  cout << ans << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define int long long

signed main(){
    int n; string s;
    cin >> n >> s;
    
    int ans = 1;
    rep(i,n-1) if(s[i] != s[i+1]) ans++;
    
    cout << ans << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int n,k,ans=1;
int main()
{
	cin>>n>>k;
	for(int i=0; i<n; i++)
	{
		if(ans>k)
		ans+=k;
		else
		ans*=2;
	}
	cout<<ans;
}

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

//INSERT ABOVE HERE
signed main(){
  Int n,d;
  cin>>n>>d;
  Int l=2*d+1;
  cout<<(n+l-1)/l<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

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

// 多次元 vector 生成
template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> id(m), id_sort(m);
    REP(i, m) {
        int p, y;
        cin >> p >> y;
        id[i] = make_pair(p, y);
        id_sort[i] = make_pair(p, y);
    }

    map<pair<int, int>, pair<int, int>> ms;

    sort(ALL(id_sort));
    int cur_p = id_sort[0].first;
    int cur_n = 1;
    for (auto p : id_sort) {
        if (cur_p == p.first) {
            ms[p] = make_pair(cur_p, cur_n);
            cur_n++;
        } else {
            cur_p = p.first;
            cur_n = 1;
            ms[p] = make_pair(cur_p, cur_n);
            cur_n++;
        }
        // cout << p.first << " " << p.second << endl;
    }

    for (auto i : id) {
        auto p = ms[i];
        cout << std::setw(6) << std::setfill('0') << p.first;
        cout << std::setw(6) << std::setfill('0') << p.second << endl;
    }

    return 0;
}


Measured memory_bytes: 9344
"""
17D8101031C 杉山　祥吾 ID:keisei334 python
"""

n=int(input())

dic=set()

for i in range(n):
    Command, Key = input().split()
    if Command=="insert":
        dic.add(Key)
    else:
        if Key in dic:
            print("yes")
        else:
            print("no")

"""実行結果

"""



Measured memory_bytes: 30992
#include <stdio.h>

#define DATANUM 3

int judge(int*);

int main(void)
{
    int data[DATANUM] = {0};
    int i = 0;
    int ret = 0;

    for (i = 0; i < DATANUM; i++) {
        scanf("%d", &data[i]);
    }

    ret = judge(data);

    if (ret) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}

int judge(int *data)
{
    if ((data[2] >= data[0]) && (data[2] <= data[1])) {
        return 1;
    } else {
        return 0;
    }
}


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

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
#define rep2(i,a,b,c) for(i=a;i<=b;i+=c)
#define maxn 100000
#define ll long long

int anak[maxn+5],depth[maxn+5],par[maxn+5];
vector<int> jaj[maxn+5];

void butri(int nod){
	anak[nod]=1;
	int i,ke;
	rep(i,0,(int)jaj[nod].size()-1){
		ke=jaj[nod][i];
		if(ke==par[nod]){
			continue;
		}
		par[ke]=nod;
		depth[ke]=depth[nod]+1;
		butri(ke);
		anak[nod]+=anak[ke];
	}
}

int main(){
	int N,i;
	cin>>N;
	int lop=N-1,a,b;
	while(lop--){
		cin>>a>>b;
		jaj[a].pb(b);
		jaj[b].pb(a);
	}
	par[1]=1;
	butri(1);
	int nod,naik=(depth[N]-1)/2;
	nod=N;
	while(naik--){
		nod=par[nod];
	}
	b=anak[nod];
	a=N-b;
	if(a>b){
		cout<<"Fennec\n";
	}
	else{
		cout<<"Snuke\n";
	}
}


Measured memory_bytes: 14720
L,R= [int(i) for i in input().split()]
n=[]
for i in range(R-L+1):	
	for j in range(i+1,R-L+1):
		a = ((L+i)*(L+j))%2019
		if a == 0:
			print(0)
			exit()
		else: 
			n.append(((L+i)*(L+j))%2019)
print(min(n))

Measured memory_bytes: 6788
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
int main(){
    string S,T;
    string U;
    int flag = 0;
    cin >> S;
    cin >> T;
    U = S + S;
    for(int i = 0; i < S.size(); i++){
        for(int j = 0; j < S.size(); j++){
            if(U[i + j] != T[j]){
                flag = 0;
                break;
            }
            flag = 1;
        }
        if(flag){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main() {
  int n,k,x,y;
  cin >> n >> k >> x >> y;

  if(n<=k) cout << n*x << endl;
  else cout << k*x + (n-k)*y << endl;
}

Measured memory_bytes: 256
a,b = map(int,input().split())
ans = 0
if b-a <= 4:
    for x in range(a, b+1):
        ans ^= x
else:
    s = a%4
    t = b%4
    if s == 0:
        s = 4
    for x in range(a, a+4-s):
        ans ^= x
    for x in range(b-t, b+1):
        ans ^= x
print(ans)

Measured memory_bytes: 9200
#include <stdio.h>
#include <math.h>

int main() {
  int n, roop;
  double length[1000], theta[1000], sum = 0;
  length[1] = 1, theta[1] = atan(1 / length[1]);

  scanf("%d", &n);

  while (n != -1) {

    for (roop = 1; roop < n; roop++) {
      length[roop + 1] = sqrt(1 * 1 + length[roop] * length[roop]);
      theta[roop] = atan(1 / length[roop]);
      sum += theta[roop];
    }

    printf("%f\n", length[n] * cos(sum));
    printf("%f\n", length[n] * sin(sum));

    sum = 0;
    scanf("%d", &n);
  }

  return 0;
}

Measured memory_bytes: 704
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b;
  int c;
  cin>>c;
  if(c==1){
    cout<<"Hello"<<" "<<"World"<<"\n";
    return(0);
  }
  cin>>a>>b;
  cout<<a+b<<"\n";
  return(0);
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <list>
#include <utility>
#include <queue>
#include <memory>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std; 

int64_t
comb2(int64_t x) {
    return (x * (x - 1)) / 2;
}


int
main(int argc, char const *argv[])
{
    int64_t n;
    cin >> n;
    vector<string> ss(n);

    for (int64_t i = 0; i < n; ++i) {
	string s;
	cin >> s;
        list<char> chars;
	copy(s.begin(), s.end(), back_inserter(chars));
	chars.sort();
	ss[i] = "";
	copy(chars.begin(), chars.end(), back_inserter(ss[i]));
	// cerr << ss[i] << endl;
    }

    sort(ss.begin(),ss.end());

    int64_t sum = 0;
    int64_t sames = 1; 

    for (int64_t i = 1; i < n; ++i) {
	if (ss[i-1] == ss[i]) {
	    ++sames;
	} else {
	    sum += comb2(sames);
	    sames = 1;
	}
    }
    sum += comb2(sames);
    sames = 1;

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 7296