akhauriyash/Code-Regression huggingface dataset:
<?php
$n = intval(fgets(STDIN));
$str = trim(fgets(STDIN));
$Q = intval(fgets(STDIN));

$seg = new SegTree($n);
function op($a, $b){return $a | $b;}

for($i = 0; $i < $n; $i++){
  $seg->set($i, 1<<(ord($str[$i])-97));
}
while($Q--){
  list($q, $a, $b) = explode(" ", trim(fgets(STDIN)));
  if($q == "1"){
    $seg->set($a-1, 1<<(ord($b)-97));
  }else{
    $ret[] = popcount($seg->get($a-1, $b));
  }
}
echo implode("\n", $ret);


class SegTree{
  public $tree;
  public $bits;
  function __construct($n){
    $this->bits = max(1, ceil(log($n)/log(2)));
    for($i = 0; $i < $this->bits; ++$i){
      $this->tree[$i] = array_fill(0, 2**($this->bits-$i), 0);
    }
  }
  function set($i, $amount){
    $this->tree[0][$i] = $amount;
    for($j = 1, $J = $this->bits; $j < $J; ++$j){
      $this->tree[$j][$i>>$j] = op($this->tree[$j-1][$i>>$j<<1], $this->tree[$j-1][($i>>$j<<1) + 1]);
    }
  }
  function get($f, $t){
    $sum = 0;
    $tree = $this->tree;
    for($i = 0; $i < $this->bits ; ++$i){
      $treei = $tree[$i];
      $ff = $f>>$i+1<<$i+1;
      if($f!=$ff){
        $sum = op($sum, $treei[$f>>$i]);
        $f+=1<<$i;
      }
      $tt = $t>>$i+1<<$i+1;
      if($t!=$tt){
        $sum = op($sum, $treei[($t>>$i)-1]);
        $t-=1<<$i;
      }
      if($f==$t)break;
    }
    return $sum;
  }
}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array: ";
            echo implode(" ", addIndex($val))."\n";
        }else{
            echo "array:array\n";
            if(isCleanArray($val)){
                foreach($val as $row)echo implode(" ", addIndex($row))."\n";
            }else{
                foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row))."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
function addIndex($val){
    if(!isCleanArray($val)){
        $val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);
    }
    return $val;
}
function isCleanArray($array){
    $clean = true;
    $i = 0;
    foreach($array as $k => $v){
        if($k != $i++)$clean = false;
    }
    return $clean;
}
//ビットカウント-1の数を数える
function popcount($x){
    $con = 0;
    while ($x) {
        $x &= $x-1;
        ++$con;
    }
    return $con;
}


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

int main() {
  int X, A, B;
  cin >> X >> A >> B;
  string ans;
  if (B-A<=0) {
    ans = "delicious";
  }
  else if (B-A<=X) {
    ans = "safe";
  }
  else {
    ans = "dangerous";
  }
  cout << ans << endl;
}


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

int main()
{
    int n;
    cin>>n;
    int arr[n+5];
    for(int i=0;i<n;i++)cin>>arr[i];
   // set<int>s;
   int counter=0;
    for(int i=1;i<n;i++)
    {
        if(i+1<n)
        {
            if(arr[i]>arr[i-1]&&arr[i]<arr[i+1])counter++;
            else if(arr[i]<arr[i-1]&&arr[i]>arr[i+1])counter++;
        }
    }
    cout<<counter<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int A[20],n;

int ESearch(int m,int a){
  int res;
  if(a>=n) return 0;
  if(m==0) return 1;
  if(m==A[a]) return 1;

  res = ESearch(m,a+1) || ESearch(m-A[a],a+1);
  return res;

}

int main(){
  int q,i;

  scanf("%d",&n);
  for(i=0; i<n; i++)
  scanf("%d",&A[i]);

  scanf("%d",&q);
  int m;
  for(i=0; i<q; i++){
    scanf("%d",&m);
    if(ESearch(m,0)==1)printf("yes\n");
    else
      printf("no\n");
  }

  return 0;
}



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

using namespace std;
using VI = vector<int>;
using PII = pair<int,int>;
#define MP make_pair
#define FF first
#define SS second

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

int main(){
  int W, H;
  while(cin>>W>>H,W){
    vector<VI> xs(H, VI(W));
    for(int y=0;y<H;++y)
      for(int x=0;x<W;++x)
	cin >> xs[y][x];
    VI cs(4);
    for(int i=0;i<4;++i)
      cin >> cs[i];

    fill((int*)dist, (int*)dist+30*30*4, 1e9);
    // dist, dir, y, x
    using P = pair<int,pair<int,PII>>;
    priority_queue<P,vector<P>,greater<P>> pq;
    // y, x, dir
    dist[0][0][0] = 0;
    pq.push(MP(0,MP(0,MP(0,0))));
    while(!pq.empty()){
      P p = pq.top();
      pq.pop();
      int cost = p.FF;
      int dir = p.SS.FF;
      int y = p.SS.SS.FF;
      int x = p.SS.SS.SS;
      if(dist[y][x][dir] < cost) continue;
      for(int i=0;i<4;++i){
	int tdir = (dir + i) % 4;
	int tx = x + dx[tdir], ty = y + dy[tdir];
	int nc = cost + cs[i];
	if(0 <= ty && ty < H && 0 <= tx && tx < W
	   && dist[ty][tx][tdir] > nc){
	  pq.push(MP(nc, MP(tdir, MP(ty,tx))));
	  dist[ty][tx][tdir] = nc;
	}
      }

      if(xs[y][x] == 4) continue;
      if(xs[y][x] == 1) (++dir) %= 4;
      else if(xs[y][x] == 2) (dir+=2)%=4;
      else if(xs[y][x] == 3) (dir+=3)%=4;
      int tx = x + dx[dir], ty = y + dy[dir];
      if(0 <= ty && ty < H && 0 <= tx && tx < W
	 && dist[ty][tx][dir] > cost){
	pq.push(MP(cost, MP(dir, MP(ty,tx))));
	dist[ty][tx][dir] = cost;
      }
    }
    
    int ans = 1e9;
    for(int i=0;i<4;++i)
      ans = min(ans, dist[H-1][W-1][i]);
    cout << ans << endl;
  }

  return 0;
}

Measured memory_bytes: 3228
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
  cin>>s;

  int counter=0;
  if(s[0] == '1'){
  counter++;
  }
 if(s[1] == '1'){
  counter++;
  }
  if(s[2] == '1'){
  counter++;
  }
  
  cout<<counter;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] c = new int[4];
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if (s.equals("AC")) {
                c[0]++;
            } else if (s.equals("WA")) {
                c[1]++;
            } else if (s.equals("TLE")) {
                c[2]++;
            } else if (s.equals("RE")) {
                c[3]++;
            }
        }
        System.out.println("AC x " + c[0]);
        System.out.println("WA x " + c[1]);
        System.out.println("TLE x " + c[2]);
        System.out.println("RE x " + c[3]);
    }

}


Measured memory_bytes: 58532
#include<bits/stdc++.h>
using namespace std;
string s;
char a[5005][5005];
int b,d[10005],total=0,dx[8]= {1,1,-1,-1,0,0,1,-1},dy[8]= {1,-1,1,-1,1,-1,0,0};
int sum=0;
int n,m;
const double pi=3.141593;
int main()
{
    long long  k,i,j;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            cin>>a[i][j];
        }
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i][j]=='#')
                cout<<a[i][j];
            else
            {
                int c=0;
                for(k=0; k<8; k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='#')
                        c++;
                }
                cout<<c;
            }
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>
#include <numeric>

using namespace std;

using ll = long long;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;

        if (a < b || d < b) {
            cout << "No" << endl;
            continue;
        }

        if (a > c) {
            a = a - b * ((a - c + b - 1) / b);

            if (a < 0) {
                cout << "No" << endl;
                continue;
            }
        } 

        a += d;

        ll e = d - b;

        if (e == 0) {
            cout << "Yes" << endl;
            continue;
        }

        ll t = (-b + (b + e - 1) / e * e) % (d - b);
        ll s = __gcd(t, e);

        ll ng_l = c + b + 1;
        ll ng_r = min(2 * b - 1, c + d);

        if (ng_r - ng_l + 1 <= 0) {
            cout << "Yes" << endl;
            continue;
        }
        
        if (ng_r - ng_l + 1 >= s) {
            cout << "No" << endl;
            continue;
        }

        if (ng_l % s <= ng_r % s) {
            if (ng_l % s <= a % s && a % s <= ng_r % s) {
                cout << "No" << endl;
                continue;
            }
        } else {
            if (ng_l % s <= a % s || a % s <= ng_r % s) {
                cout << "No" << endl;
                continue;
            }
        }

        cout << "Yes" << endl;
    }
}



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

int main()
{
    int n;
    cin >> n;
    int a[n];
    int cnt = 0;
    int minj;

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

    for(int i = 0; i < n; i++){
        minj = i;
        for(int j = i; j < n; j++){
            if(a[j] < a[minj]){
                minj = j;
            }    
        }
        if(a[i] > a[minj])
            cnt++;
        int tmp = a[i];
        a[i] = a[minj];
        a[minj] = tmp;
    }
    
    for(int i = 0; i < n; i++){
        if(i < n - 1){
            cout << a[i] << ' ';
        }else{
            cout << a[i] << endl;
        }
    }
    cout << cnt << endl;
}


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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int n, a[50][26], m[26];
string s;

int main() {
	cin >> n;
	rep(i,n) {
		cin >> s;
		rep(j,s.length()) a[i][s[j]-'a']++;
	}
	
	fill(m,m+26,1145141919);
	rep(i,n) rep(j,26) chmin(m[j], a[i][j]);
	string al = "abcdefghijklmnopqrstuvwxyz";
	rep(i,26) rep(j,m[i]) cout << al[i];
	cout << ln;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
#define rnt re int
#define re register
#define pb push_back
#define I inline int
#define V inline void
#define B inline bool
#define isnum(ch) ('0'<=ch&&ch<='9')
#define FOR(i,a,b) for(rnt i=a;i<=b;i++)
#define gc (_op==_ed&&(_ed=(_op=_buf)+fread(_buf,1,100000,stdin),_op==_ed)?EOF:*_op++)
char _buf[100000],*_op(_buf),*_ed(_buf);
I getint(){
	rnt _s=0;re char _ch=gc;
	while(!isnum(_ch))_ch=gc;
	while(isnum(_ch))_s=_s*10+_ch-48,_ch=gc;
	return _s;
}
const int N=2e5+10;
int n,a[N];
struct node{
	int p,w;
	B operator<(const node&u)const{
		return p==u.p?w<u.w:p<u.p;
	}
};
vector<node>dp[N],tmp;
I max(const int&x,const int&y){return x>y?x:y;}
node mk(rnt x,rnt y){return (node){max(0,x),y};}
V input(){n=getint();FOR(i,1,n)a[i]=getint();}
V init(){n=unique(a,a+n+2)-a-1,dp[0].pb(mk(0,0));}
V work(){
	rnt minn,d;
	FOR(i,1,n){
		tmp.clear(),d=a[i]-a[i-1],minn=N;
		if(d>0)for(node x:dp[i-1])
			tmp.pb(mk(0,x.w+2)),tmp.pb(mk(x.p,x.w+1)),tmp.pb(mk(x.p+d,x.w));
		else for(node x:dp[i-1])
			tmp.pb(mk(0,x.w+2)),tmp.pb(mk(x.p+d,x.w+1)),tmp.pb(mk(x.p,x.w));
		sort(tmp.begin(),tmp.end());
		for(node x:tmp)if(minn>x.w&&x.p<=a[i])
			dp[i].pb(mk(x.p,x.w)),minn=x.w;
	}
	minn=N;
	for(node x:dp[n])if(x.w<minn)minn=x.w;
	cout<<minn;
}
int main(){
	input();
	init();
	work();
	return 0;
}

Measured memory_bytes: 15232
#include <iostream>
using namespace std;
#define ll long long int

int F(ll a, ll b){
    ll x,cnt=0;
    x = max(a,b);
    while(x>0){
        x /= 10;
        cnt++;
    }
    return cnt;
}

int main(){
    ll n; int ans=11; cin >> n;
    for (int i=1; i <= (n<=100001 ? n : 100001); i++){
        if (n%i==0) ans = min(ans,F(i,n/i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>

using namespace std;

int main(){
    int64_t N, x;
    cin >> N >> x;

    vector<int64_t> a(N);
    for(auto& c : a){
        cin >> c;
    }

    int64_t ans = 0;
    for(int i = 1; i < N; ++i){
        if(a[i-1] >= x){
            ans += (a[i-1] - x);
            a[i-1] = x;
        }
        if(a[i-1] + a[i] >= x){
            ans += (a[i-1] + a[i]) - x;
            a[i] = x - a[i-1];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
fun main(args: Array<String>) {
    readInputLine()
    val s = readInputLine().toCharArray().toMutableList()
    
    val left = mutableListOf<Char>()
    
    var max = 0
    
    while (s.isNotEmpty()) {
        left.add(s.removeAt(0))
        
        val intersect = left.intersect(s).size
        
        if (intersect > max) {
            max = intersect
        }
    }
    
    println(max)
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 38008
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
 
 
public class Main{
	
	//@paste
	/*
	public static long mod_pow(long a, long e, long m){
	    if(e == 0){
	        return 1;
	    }else if(e % 2 == 0){
	        long ret = mod_pow(a, e / 2, m);
	        return (ret * ret) % m;
	    }else{
	        return (mod_pow(a, e - 1, m) * a) % m;
	    }
	}
	public static long mod_inv(long a, long p){
	    return mod_pow(a, p-2, p);
	}
	*/
	
	public static long mod_inv(long a, long m){
		//System.err.println(a + " : " + m);
	    return (a == 1 ? 1 : (1 - m*mod_inv(m%a, a)) / a + m);
	}
	
	
	//@paste
	public static long chinese_remainder(long[] as, long[] ms){
		long prod = 1;
		for(long m : ms){
			prod *= m;
		}
		
		long ret = 0;
		for(int i = 0; i < ms.length; i++){
			final long M = prod / ms[i];
			final long inv = mod_inv(M, ms[i]);
			
			long a = as[i] - as[i] / prod * prod;
			if(a < 0){
				a += prod;
			}
			
			ret = (ret + M * inv * as[i] % prod) % prod;
		}
		
		return ret;
	}
	
    public static void main(String[] args){
    	final Scanner sc = new Scanner(System.in);
    	
    	final int n = sc.nextInt();
    	
    	long[] as = new long[]{0, 0};
    	long[] ms = new long[]{1158991, 1386811};
    	
    	for(int tt = 0; tt < n; tt++){
    		final int ops = sc.nextInt();
    		final long val = sc.nextLong();
    		
    		for(int i = 0; i < as.length; i++){
    			switch(ops){
    			case 1: // +
    				as[i] += val;
    				as[i] %= ms[i];
    				break;
    			case 2: // -
    				as[i] += ms[i];
    				as[i] -= val;
    				as[i] %= ms[i];
    				break;
    			case 3: // *
    				as[i] *= val;
    				as[i] %= ms[i];
    				break;
    			case 4: // /
    				as[i] *= mod_inv((ms[i] + val) % ms[i], ms[i]);
    				as[i] %= ms[i];
    				break;
    			}
    		}
    	}
    	
    	//System.out.println(Arrays.toString(as));
    	long mul = 1;
    	for(long m : ms){
    		mul *= m;
    	}
    	
    	long ret =  chinese_remainder(as, ms);
    	while(ret < Integer.MIN_VALUE){
    		ret += mul;
    	}
    	while(ret > Integer.MAX_VALUE){
    		ret -= mul;
    	}
    	System.out.println(ret);
    	
    	sc.close();
    }
     
}

Measured memory_bytes: 95444
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    string s;
    cin>>s;
    int q;
    cin>>q;
    int yo=0;
    deque<char>dq;
    for(auto ch:s)
    {
        dq.pb(ch);
    }
    while(q--)
    {
        int typ;
        cin>>typ;
        if(typ==1)
        {
            yo=1-yo;
        }
        else
        {
            int p;
            char ch;
            cin>>p>>ch;
            if(p==1)
            {
                if(yo==0)
                {
                    dq.push_front(ch);
                }
                else
                {
                    dq.pb(ch);
                }
            }
            else if(p==2)
            {
                if(yo==0)
                {
                    dq.pb(ch);
                }
                else
                {
                    dq.push_front(ch);
                }

            }
        }
    }
   vector<char>ses;
   while(!dq.empty())
   {
       char nw=dq.front();
       dq.pop_front();
       ses.pb(nw);
   }
   if(yo)reverse(ses.begin(),ses.end());
   for(auto x:ses)
   {
       cout<<x;
   }
   cout<<endl;
    return 0;

}














Measured memory_bytes: 1360
#include<stdio.h>
int main(){
	int n,i,a,M=1e9+7,b[100010]={};
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a);
		b[a]++;
	}
	a=1;
	if(n%2)b[0]++;
		for(i=0;i<n;i++){//printf("%d %d %d\n",i,i%2==n%2?0:2,b[i]);
		if((i%2==n%2?0:2)-b[i])break;
		if(i%2)a=(a*2)%M;
	}
	printf("%d\n",i-n?0:a);
	return 0;
}

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

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

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

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

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

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

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

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


ld getP(int cnt){
  if(cnt == 0) return 1.00000000000;
  else return 1/pow(2,cnt);
}

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

    ld n,k;
    cin >> n >> k;
    ld sum = 0;
    FOR(i,1,n+1){
      int cnt = 0;
      int temp = i;
      while(temp < k){
        temp *= 2;
        cnt++;
      }
      sum += getP(cnt);
    }
    std::cout << std::fixed;
    std::cout << std::setprecision(10);
    cout << sum/n << endl;


    return 0;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void){
  ll k,a,b,ans;
  
  cin >> k >> a >> b;
  
  if (b-a>=2 && k>=a+1){
    ans=a+(b-a)*((k-a+1)/2)+(k-a+1)%2;
  }else{
    ans=k+1;
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
def z_algorithm(s):
    n = len(s)
    prefix = [0] * n
    j = 0
    ret = 0
    for i in range(1, n):
        if i + prefix[i - j] < j + prefix[j]:
            prefix[i] = prefix[i - j]
        else:
            k = max(0, j + prefix[j] - i)
            while i + k < n and s[k] == s[i + k]:
                k += 1
            prefix[i] = k
            ret = max(ret, min(i, k))
            j = i
    return ret


n = int(input())
s = input()
print(max(z_algorithm(s[i:]) for i in range(n - 1)))


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

int main()
{
	int n;
	long long ll = 0;
	cin >> n;
	vector <int> b(n - 1);
	vector <int> a(n);
	for (int i = 0; i < n - 1; i++)
	{
		cin >> b[i];
	}
	a[0] = b[0];
	a[1] = b[0];
	for (int i = 1; i < n - 1; i++)
	{
		if (b[i] >= a[i])
		{
			a[i + 1] = b[i];
		}
		else
		{
			a[i] = b[i];
			a[i + 1] = b[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		ll += a[i];
	}
	cout << ll;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct dice {
    int front, right, bottom;
    dice(){
        front = 2;
        right = 3;
        bottom = 6;
    }
    void b() {
        int tmp = front;
        front = bottom;
        bottom = 7 - tmp;
    }
    void f() {
        int tmp = bottom;
        bottom = front;
        front = 7 - tmp;
    }
    void l() {
        int tmp = right;
        right = bottom;
        bottom = 7 - tmp;
    }
    void r() {
        int tmp = bottom;
        bottom = right;
        right = 7 - tmp;
    }
};

int main(){
    int H, W;
    cin >> H >> W;

    vector<string> IN(H);
    rep(i, H) cin >> IN[i];

    vector<vector<int>> S(H, vector<int>(W));
    rep(i, H)rep(j, W) {
        if (IN[i][j] != '#') S[i][j] = IN[i][j] - '0';
        else IN[i][j] = -1;
    }

    queue<pair<P, dice>> q;
    dice di;
    q.emplace(P(0, 0), di);
    vector<vector<bool>> used(H, vector<bool>(W));
    used[0][0] = true;
    bool ans = false;
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int i = p.first.first, j = p.first.second;
        dice d = p.second;
        if (i == H-1 && j == W-1) {
            ans = true;
            break;
        }
        if (i+1 < H && !used[i+1][j] && d.front == S[i+1][j]) {
            dice nd(d); nd.f();
            q.emplace(P(i+1, j), nd);
            used[i+1][j] = true;
        }
        if (j+1 < W && !used[i][j+1] && d.right == S[i][j+1]) {
            dice nd(d); nd.r();
            q.emplace(P(i, j+1), nd);
            used[i][j+1] = true;
        }
        if (i-1 >= 0 && !used[i-1][j]) {
            dice nd(d); nd.b();
            if (nd.bottom == S[i-1][j]) {
                q.emplace(P(i-1, j), nd);
                used[i-1][j] = true;
            }
        }
        if (j-1 >= 0 && !used[i][j-1]) {
            dice nd(d); nd.l();
            if (nd.bottom == S[i][j-1]) {
                q.emplace(P(i, j-1), nd);
                used[i][j-1] = true;
            }
        }
    }

    if (ans) puts("YES");
    else puts("NO");
}



Measured memory_bytes: 3256
require 'prime'
require 'set'
require 'tsort'
include Math
ALP = ('a'..'z').to_a
INF = 0xffffffffffffffff
def max(a,b);              a > b ? a : b                              end
def min(a,b);              a < b ?  a : b                             end
def swap(a,b);             a, b = b, a                                end
def gif;                   gets.to_i                                  end
def gff;                   gets.to_f                                  end
def gsf;                   gets.chomp                                 end
def gi;                    gets.split.map(&:to_i)                     end
def gf;                    gets.split.map(&:to_f)                     end
def gs;                    gets.chomp.split.map(&:to_s)               end
def gc;                    gets.chomp.split('')                       end
def pr(num);               num.prime_division                         end
def pr?(num);              Prime.prime?(num)                          end
def digit(num);            num.to_s.length                            end
def array(s,ini=nil);      Array.new(s){ini}                          end
def darray(s1,s2,ini=nil); Array.new(s1){Array.new(s2){ini}}          end
def rep(num);              num.times{|i|yield(i)}                     end
def repl(st,en,n=1);       st.step(en,n){|i|yield(i)}                 end


set = Set.new
n = gif
rep n do
  num = gif
  if set.include? num
    set.delete num
  else
    set << num
  end
end

puts set.size


Measured memory_bytes: 8828
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;
map<char, int> M;
ll a[5];

int main() {
  INCANT;
  cin >> N;
  string S;
  rep(i, N) {
    cin >> S;
    M[S[0]]++;
  }
  a[0] = M['M'];
  a[1] = M['A'];
  a[2] = M['R'];
  a[3] = M['C'];
  a[4] = M['H'];
  ll res=0ll;
  rep(i, 3) {
    for (int j=i+1; j<4; j++) {
      for (int k = j+1; k<5; k++) {
        res+=a[i]*a[j]*a[k];
      }
    }
  }
  
  cout << res << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0);
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int main() {
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    int n;
    cin >> n;
    int x = ceil(((1.0 * n) / 1.08));
    if ((int)(1.08 * x) == n)
        cout << x << endl;
    else
        cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			char[] c = sc.next().toCharArray();
			int count = 0;
			int n = c.length;
			for(int i=0;i<n/2;i++){
				if((c[i]=='i' && c[n-1-i]!='i') || (c[i]=='w' && c[n-1-i]!='w')
						|| (c[i]=='(' && c[n-1-i]!=')') || (c[i]==')' && c[n-1-i]!='(')) count++;
			}
			if(n%2==1 && c[n/2]!='w' && c[n/2]!='i') count++;
			System.out.println(count);
		}
	}	
}

Measured memory_bytes: 17284
#include<stdio.h>

int N;
int A[101][101];

int hantei(int x,int y){
  int i;
  int flag=0;

  for(i=2;i<=N;i++){
    if(A[x][i]==y){
      flag=1;
    }
  }

  if(flag==1){
    return 1;
  }
  else if(flag==0){
    return 0;
  }
}

int main (){
  int i,j,k;

  scanf("%d",&N);

  for(i=1;i<=N;i++){
    j=1;
    scanf("%d %d",&A[i][1],&k);
    for(j=2;j<k+2;j++){
      scanf("%d",&A[i][j]);
    }
  }

  for(i=1;i<=N;i++){
    for(j=1;j<=N;j++){    
      if(j==N){
	printf("%d\n",hantei(i,j));
      }
      else {
	printf("%d ",hantei(i,j));
      }
    }
    
  }

  return 0;
}

Measured memory_bytes: 632
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d,ans=0;
  cin >> a>>b>>c>>d;
  if(a>=b){
    ans+=b;
  }else{
    ans+=a;
  }
  if(c>=d){
    ans+=d;
  }else{
    ans+=c;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
	int N;
	bool flag = false ;

	cin >> N;
	for (int i = 0; i < N; i++) {
		string c;
		cin >> c;
		if (c == "Y")
		{
			flag = true;
			break;
		}
	}

	if (flag == 1) {
		cout << "Four" << endl;
	}
	else {
		cout << "Three" << endl;
	}

}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int c = 0;

		for(int i = 1; i <= n; i++)
			if((int)Math.log10((double)i) % 2 == 0)
				c++;

		System.out.println(c);
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  string S;
  cin >> S;
  //S の先頭から 3 文字目と末尾から 2 文字目の間（両端含む）に大文字の C がちょうど 1 個含まれる。
  int count = 0;
  int index;
  
  for (int i = 2; i < S.size() - 1; i++) {
    if(S[i] == 'C'){
      count++;
      index = i;
    }
  }
  
  int up_count = 0;
    
  for (int i = 1; i < S.size(); i++) {
    if(i != index){
      if(S[i] >= 'A' && S[i] <= 'Z'){
		up_count++;
      }
    }
  }
  
  
  if(S[0] == 'A' && count == 1 && up_count == 0){
   cout << "AC" << endl;
  }else{
   cout << "WA" << endl;
  }
 
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
#define scan(a,n) for(long int index=0;index<n;index++) cin>>a[index];
#define print(a,n) for(long int index=0;index<n;index++) cout<<a[index]<<" ";cout<<endl;
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ss second
#define ff first
#define vli vector<long long int>
#define vlli vector<pair<long long int,long long int>>
#define vsi vector<string>
#define vci vector<char>
 
 
 
int main() {
   #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    fast;
   ll a,b,c,k;
   cin>>a>>b>>c>>k;
   ll cc=0;
   while(a>=b){
    b*=2;
    cc++;
   }
   while(b>=c){
    c*=2;
    cc++;
   }
  if(cc<=k) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
return 0;
    
 }  

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

char ch[100005];

int main()
{
    int a,b,c,d,e,x,y,z,n;

    scanf("%s",ch);

    n=strlen(ch);

    x=e=0;

    for(a=0;a<n;a++)
    {
        if(ch[a]=='g')
        {
           e++;
        }
        else
        {
            e--;
        }
    }

    cout<<e/2<<endl;

    return 0;
}


Measured memory_bytes: 384
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;

  vll as(n);
  map<ll, set<ll>> mp;
  rep(i, n) {
    cin >> as[i];
    mp[as[i]].insert(i);
  }

  auto chk = [&](ll x, ll a) {
    if (mp.count(x) == 0) return true;
    if (x == a && mp[x].size() == 1) return true;
    return false;
  };

  ll ans = 0;
  rep(i, n) {
    bool ok = true;
    for (ll j = 1; j * j <= as[i]; j++) {
      if(as[i] % j == 0){
        ok &= chk(j, as[i]);
        ok &= chk(as[i]/j, as[i]);
        if (!ok) break;
      }
    }
    if (ok) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 32716
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main() {
    cin>>N;
    vec a(N);
    rep(i,N) cin>>a[i];
    ll sum = 0;
    rep(i,N) sum += a[i];
    bitset<ll(4e+6 + 1)> bs(1);
    rep(i,N) bs = bs | (bs<<a[i]);
    reps(i, (sum + 1)/2, sum + 1){
        if(bs[i]) {
            cout<<i<<endl;
            return 0;
        }
    }
}

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

int main(){
    int r,c;
    int L[101][101];

    for(int i=0;i<101;i++){
        for(int j=0;j<101;j++){
            L[i][j]=0;
        }
    }

    cin >> r >> c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> L[i][j];
        }
    }

    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            L[i][c] += L[i][j];
            L[r][j] += L[i][j];
            L[r][c] += L[i][j];
        }
    }

    

    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            if(j != 0)cout << " ";
            cout << L[i][j];
        }
        cout << endl;
    }

    return 0;

}


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

using namespace std;

int main()
{
    int n,m,c,i,j,a[101],b[101],count=0;
    cin>>n>>m>>c;
    for(i=0; i<m; i++)
    {
        cin>>b[i];
    }
    for(i=0; i<n; i++)
    {
        int sum=0;
        for(j=0; j<m; j++)
        {
            cin>>a[j];
            sum+=a[j]*b[j];
        }
        if(sum+c>0)
        {
            count++;
        }

    }
    cout<<count;
    return 0;
}


Measured memory_bytes: 3604
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <utility>
#include <vector>

#define MAX_N (100000)
#define MAX_Q (100000)
#define INF (1000000000)

using namespace std;

int main(int argc, char *argv[]) {
  // read inputs
  long N, Q, as[MAX_N], xs[MAX_Q];
  scanf("%ld %ld", &N, &Q);
  for (long i = 0; i < N; i++) {
    scanf("%ld", &as[i]);
  }
  for (long q = 0; q < Q; q++) {
    scanf("%ld", &xs[q]);
  }

  // calculate accumulated sums
  long acc_as[MAX_N] = {}, acc_oe_as[MAX_N] = {};
  acc_as[0] = as[0];
  acc_as[1] = as[0] + as[1];
  acc_oe_as[0] = as[0];
  acc_oe_as[1] = as[1];
  for (long i = 2; i < N; i++) {
    acc_as[i] = acc_as[i - 1] + as[i];
    acc_oe_as[i] = acc_oe_as[i - 2] + as[i];
  }

  // solve
  for (long q = 0; q < Q; q++) {
    const long x = xs[q];

    // find ab and ae where
    // aoki-kun takes [ab, ae) and takahashi-kun takes [ae, N)
    long ab, ae;

    // find w where [x +- w] is the range of values of the block [b, e)
    long le = -1, ri = INF;
    while (ri - le > 1) {
      const long m = (le + ri) / 2;
      const long b = lower_bound(as, as + N, x - m) - as;
      const long e = upper_bound(as, as + N, x + m) - as;
      // printf("le = %ld, ri = %ld, m = %ld, e - b = %ld, N - e = %ld\n", le, ri,
      //        m, e - b, N - e);

      if (e - b == N - e - 1 || e - b == N - e) {
        ri = m;
        le = m - 1;
        ab = b;
        ae = e;
      } else if (e - b < N - e - 1) {
        le = m;
      } else if (e - b > N - e + 1) {
        ri = m;
      } else {
        // the hard case (e - b == N - e + 1)
        if (e > 0 && abs(as[b] - x) == abs(as[e - 1] - x)) {
          ri = m;
          le = m - 1;
          ab = b;
          ae = e - 1;
        } else {
          ri = m;
        }
      }
    }
    // printf("q = %ld, ab = %ld, ae = %ld, x = %ld, ri = %ld\n", q, ab, ae, x,
    //        ri);
    long ans;
    if (ae - ab == 0) {
      ans = acc_oe_as[N - 1];
    } else {
      ans = acc_as[N - 1] - acc_as[ae - 1];
      if (ae - ab == N - ae && ab - 1 >= 0) {
        ans += acc_oe_as[ab - 1];
      } else if (ae - ab == N - ae - 1 && ab - 2 >= 0) {
        ans += acc_oe_as[ab - 2];
      }
    }
    printf("%ld\n", ans);
  }

  return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>
unsigned n, a[9], b[9], r;
void rec(unsigned x, int d) {
	if (d == 32) { r = x; return; }
	for (int i = 0; i < 2; i++) {
		unsigned res = 0;
		for (int j = 0; j < 9; j++) b[j] = a[j] ^ (x + (i << d));
		for (int j = 0; j < 8; j++) res += b[j];
		if ((res & (1 << d)) == (b[8] & (1 << d))) rec(x + (i << d), d + 1);
	}
}
int main() {
	scanf("%u", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 9; j++) scanf("%x", a + j);
		rec(0, 0);
		printf("%x\n", r);
	}
}

Measured memory_bytes: 2740
using System;

namespace ConsoleApplication24
{
    class Dice
    {
        string[] D;
 
        public Dice(string[] DArray)
        {
            D = DArray;
        }
 
        public string DiceRoll(string roll)
        {
            for (int i = 0; i < roll.Length; ++i)
            {
                string D0 = D[0];
                string D1 = D[1];
                string D2 = D[2];
                string D3 = D[3];
                string D4 = D[4];
                string D5 = D[5];
 
                switch (roll[i])
                {
                    case 'E':
                        D[0] = D3;
                        D[2] = D0;
                        D[3] = D5;
                        D[5] = D2;
 
                        break;
 
                    case 'N':
                        D[0] = D1;
                        D[1] = D5;
                        D[4] = D0;
                        D[5] = D4;
 
                        break;
 
                    case 'S':
                        D[0] = D4;
                        D[1] = D0;
                        D[4] = D5;
                        D[5] = D1;
                        break;
 
                    case 'W':
                        D[0] = D2;
                        D[2] = D5;
                        D[3] = D0;
                        D[5] = D3;
                        break;
                }
            }
            return D[0];
        }
    }
 
 
    class Program
    {
        static void Main()
        {
            string[] DiceArray = Console.ReadLine().Split(' ');
            string str = Console.ReadLine();
 
            Dice DClass = new Dice(DiceArray);
 
            string top = DClass.DiceRoll(str);
 
            Console.WriteLine(top);
        }
    }
}


Measured memory_bytes: 7772
N,K = [int(x) for x in input().split()]
ps = [int(x) for x in input().split()]
best_val = 0
past_val = None
for i in range(K-1, N):
    if past_val is None:
        past_val = (sum(ps[i + 1 - K:i + 1]) + K) / 2
    else:
        past_val += (ps[i] - ps[i - K]) / 2
    val = past_val 
    if best_val < val:
        best_val = val 
print(best_val)

Measured memory_bytes: 24676
#include<iostream>//入出力関連ヘッダ(stdio.hとは別)
using namespace std;//名称をローカルのように扱うことができる(被りを防げる)
#define MAX 100000
typedef long long llong;//long long型は64ビット以上の整数型

int n, k;//n→荷物の個数、k→分ける個数
llong T[MAX];

//最大積載量Pのk台のトラックで何個の荷物を積めるか？
int check(llong P){
	int i = 0;
	for(int j = 0;j<k;j++){
		llong s = 0;
		while(s + T[i] <= P){//入力した数字が最大積載量Pを上回るかの判断
			s += T[i];
			i++;
			if(i == n) return n;
		}
	}
	return i;
}

int solve(){
	llong left = 0;
	llong right = 100000*10000;//荷物の個数×1個当たりの最重量
	llong mid;
	while(right - left > 1){
		mid = (left + right)/2;
		int v = check(mid);//mid == Pを決めて何個詰めるかチェック
		if(v >= n)right = mid;//最大値の方を真ん中へ
		else left = mid;//最小値の方を真ん中へ
	}
	return right;
}

//cinはcharacter inputで、標準入力である.
//coutも同様、標準出力.
main() {
	cin >> n >> k;//nとkの値を入力
	for(int i = 0;i<n;i++) cin >> T[i];//リストに突っ込む
	llong ans = solve();
	cout << ans << endl;//結果表示
}


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

typedef long long ll;
const int MAXN = 100010;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch=='-') f=-1;
	for(; isdigit(ch); ch = getchar()) x = (x*10)+(ch^48);
	return x * f;
}

int n, a[MAXN], b[MAXN];
ll sum, t, s, pre[MAXN], Pre[MAXN];
ll c[MAXN];

int main() {

	int i;

	n = read();
	for(i = 1; i <= n; i++) sum += (a[i] = read());
	if(n == 1) {
		printf("YES\n");
		return 0;
	}
	s = ((ll)(1+n)*n)>>1;
	if(sum % s) {
		printf("NO\n");
		return 0;
	}
	t = sum/s;
	b[1] = a[1]-a[n];
	for(i = 2; i <= n; i++) b[i] = a[i]-a[i-1];
	for(i = 1; i <= n; i++) {
		if((t-b[i])%n != 0) {
			printf("NO\n");
			return 0;
		}
		c[i] = (t-b[i])/n;
		if(c[i] < 0) {
			printf("NO\n");
			return 0;
		}
	}
	for(i = 1; i <= n; i++) pre[i] = pre[i-1]+c[i];
	for(i = 1; i <= n; i++) Pre[i] = Pre[i-1]+c[i]*i;
	for(i = 1; i <= n; i++) {
		ll r = pre[i]*(i+1)-Pre[i];
		r = r+(pre[n]-pre[i])*(n+i+1)-(Pre[n]-Pre[i]);
		if(r != a[i]) {
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
	return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define ll long long
#define ljc 1000000007
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
inline ll fast_pow(ll a,ll b,ll p){
	ll t=1;
	while (b){
		if (b&1ll) t=t*a%p;
		b>>=1ll;a=a*a%p;
	}
	return t;
}
ll n,A,B,dp[5050][2],g[5050][2],h[5050];
inline void add(ll &a,const ll &b){a=(a+b)%ljc;}
signed main(){
	n=read(),A=read(),B=read();
	if (A<B) swap(A,B);
	if (B==1||A==1){
		printf("%lld\n",fast_pow(2,n,ljc));
		return 0;
	}
	g[0][0]=g[0][1]=h[0]=1;
	for (int i=1;i<=A;i++){
		for (int j=1;j<=i;j++) add(g[i][0],g[i-j][1]);
		for (int j=B;j<=i;j++) add(g[i][1],g[i-j][0]);
		h[i]=(g[i][0]+g[i][1])%ljc;
	}
	dp[0][0]=dp[0][1]=1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=i&&j<B;j++){
			add(dp[i][1],dp[i-j][0]);
		}
		for (int j=1;j<=i&&j<A;j++){
			if (i==j) add(dp[i][0],h[j-1]);
			else if (i!=n) add(dp[i][0],(j>1?h[j-2]:1)*dp[i-j][1]%ljc);
//			if (i==n) add(dp[i][1],(j>1?h[j-2]:0)*dp[i-j][1]%ljc);
			else add(dp[i][0],h[j-1]*dp[i-j][1]%ljc);
		}
	}
	printf("%lld\n",(fast_pow(2,n,ljc)-dp[n][0]-dp[n][1]+ljc+ljc)%ljc);
	return 0;
}



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

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
    int n; cin >> n;
    bool f = true;
    if(n%2 == 1) f = false;
    char c[n];
    rep(i, n) cin >> c[i];
    for(int i=0; i<n/2; i++){
        if(c[i] != c[n/2 + i]) f=false;
    }
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}


    


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;


int main(){
    int n;
    cin>>n;
    vector<vector<int> > ac(n,vector<int>(3,0) );
    for(int i=0;i<n;i++){
	cin>>ac[i][0]>>ac[i][1]>>ac[i][2];
    }
    int ans = 0;
    vector<vector<int> > dp(n+1,vector<int>(3,0) );
    for(int i=1;i<=n;i++){
	for(int j=0;j<3;j++){
	    for(int k=1;k<=2;k++){
		dp[i][j] = max(dp[i][j], dp[i-1][(j+k)%3] + ac[i-1][j] );
		ans = max(ans,dp[i][j]);
	    }
	}
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a<=0&&b>=0){
		puts("Zero");
	}
	else if(b<0){
		if((a&1)==(b&1)) puts("Negative");
		else puts("Positive");
	}
	else{
		puts("Positive");
	}
	return 0;
}

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

using namespace std;

#define all(v)				((v).begin()), ((v).end())
#define allr(v)				((v).rbegin()), ((v).rend())
#define sz(v)				((int)((v).size()))
#define rep(i, v)		for(int i=0;i<sz(v);++i)
#define lp(i, n)		for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)	for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)	for(int i=(j);i>=(int)(n);--i)
#define ll long long
#define pb					push_back
#define fIO ios_base::sync_with_stdio(0);cin.tie(0);

const ll oo = 1e8;
const double pi = 3.1415926535897;


const double EPS = (1e-7);
int dcmp(double x, double y) {	return fabs(x-y) <= EPS ? 0 : x < y ? -1 : 1;	}


typedef vector<int>                vi;
typedef vector<pair<int,int>>      vii;
typedef vector<ll>                 vll;
typedef vector<double>             vd;
typedef vector< vi >               vvi;
typedef vector< vd >               vvd;
typedef vector<string>             vs;

/**
    * PLEASEEE READDD PROBLEEEM CARFULLY ****
    * Always check for OVERFLOW ll vs int
    * Always check for array bounds
    * Check for function return
    * READ OUTPUT SECTION AGAIN!!!
**/

struct edge{
    int from, to, w;

    edge(){}
    edge(int x, int y, int we): from(x), to(y), w(we){}

    bool operator < (const edge &rhs) const{
        return w > rhs.w;
    }

};

int main(){
    fIO

    ll n;
    cin >> n;

    ll ans = 0;
    if(n & 1) return cout << 0, 0;
    n /= 2LL;
    for(ll i = 5LL; n / i >= 1; i *= 5LL) {
        ans += n / i;
    }
    cout << ans;

}







Measured memory_bytes: 256
/*
	RAone00
	Rohit sharma
	*/

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

	typedef long long ll;
	typedef long double ld;
	typedef pair < ll, ll > pll;
	typedef vector < vector < ll > > matrix;
	typedef vector < ll > vll;

	#define pb push_back
	#define debug(x) cout << (#x) << " is " << (x) << endl
	#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

	const ll mod = 1e9 + 7;
	const ll inf = LLONG_MAX;
	const ll N = 1e5 + 10;

	
	int main() {
	    fast_io();
	    int a;
	    cin >> a;
	 	ll sum = 0;
	    for (int i = 1; i <= a; ++i) {
	    	if ((i % 3 == 0) || (i % 5 == 0)) continue;
	    	else sum += i;
	    }
	    cout << sum << "\n";
	    return 0;
	}

 

Measured memory_bytes: 3636
#include <iostream>
#include <cstring>
#include <cstdio>
#include<algorithm>
#include <queue>
#include <cmath>
#include <limits>
#include <map>
#include <iomanip>
using namespace std;
int main(){
  double n;
  cin >> n;
  double a = (n / 3) * (n / 3) * (n / 3);
  cout << fixed << setprecision(10) << a << endl;

  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    if n & 1:
        print(0)
        return
    a5 = 5
    a2 = 0
    ans = 0
    a = n
    while n:
        a2 += n // 2
        n = n // 2
    while a:
        ans += a // 10
        a //= 5
    print(min(a2, ans))
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 40816