akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;

ll dp[52];

int main(){
    int n; cin >> n;
    vector<string> s(2);
    rep(i,2) cin >> s[i];
    int pos;
    if(s[0][0] != s[1][0]){
        dp[0] = 6;
        dp[1] = 6;
        pos = 2;
    }else{
        dp[0] = 3;
        pos = 1;
    }
    for(int i = pos; i < n; i++){
        if(s[0][i-1] != s[1][i-1]){
            if(s[0][i] != s[1][i]){
                //yoko -> yoko 
                dp[i] = dp[i-1] * 3;
                dp[i] %= mod;
                dp[i+1] = dp[i];
                i++;
            }else{
                //yoko -> tate
                dp[i] = dp[i-1];
            }
        }else{
            if(s[0][i] != s[1][i]){
                //tate -> yoko
                dp[i] = dp[i-1] * 2;
                dp[i] %= mod;
                dp[i+1] = dp[i];
                i++;
            }else{
                //tate -> tate
                dp[i] = dp[i-1] * 2;
                dp[i] %= mod;
            }
        }
    }
    /*
    for(auto elem : dp){
        cout << elem << endl;;
    }
    cout << endl;
    */
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
const ll MOD = 1000000007;

map<ll, vector<pair<ll,ll>>> M;

int main() {
	ll N, X, D, A, B, S = 0, T = 0, AM;
	cin >> N >> X >> D;
	if (D < 0) {
		X += (N - 1) * D;
		D = -D;
	}
	if (D == 0) {
		if (X == 0)cout << 1 << endl;
		else cout << N + 1 << endl;
		return 0;
	}
	D *= 2;
	for (ll i = 0;i <= N;i++) {
		A = X * 2 * i;
		AM = (A % D + D) % D;
		S += i;T = S - i;
		if (M.count(AM) == 0) {
			M.insert({ AM, {} });
		}
		M[AM].push_back({ -(A - AM) / D - T,-(A - AM) / D - (i * N - S) });
	}

	ll sp;
	ll ans = 0, nr, fr;
	for (auto x : M) {
		sp = x.second.size();
		sort(all(x.second));
		reverse(all(x.second));
		tie(nr, fr) = x.second[0];
		for (ll i = 1;i < sp;i++) {
			auto p = x.second[i];
			if (fr < p.second)continue;
			if (p.first < fr) {
				ans += nr - fr + 1;
				nr = p.first;
				fr = p.second;
			}
			else {
				fr = p.second;
			}
		}
		ans += nr - fr + 1;
	}
	cout << ans << endl;
}

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

int main() {
    vector<int> dg(5, 0);

    for(int i = 0; i < 3; i += 1) {
        int a, b; cin >> a >> b;
        dg[a] += 1;
        dg[b] += 1;
    }
    
    int maxx = 0;

    for(int i = 1; i <= 4; i += 1) {
        maxx = max(maxx, dg[i]);
    }

    if(maxx == 2) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

Measured memory_bytes: 256
str1 = gets.split
N,K = str1[0].to_i, str1[1].to_i

S = gets.chomp

if S[K-1] == "A"
  S[K-1] = "a"
elsif S[K-1] == "B"
  S[K-1] = "b"
else
  S[K-1] = "c"
end

puts S

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

int main() {
  int N, A;
  cin >> N >> A;

  if (N < 500 && A - N >= 0){
    cout << "Yes" << endl;
  }
  else if (N >= 500 && A - N % 500 >= 0){
    cout << "Yes" << endl;
  }
  else  {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
a, b, c, x = map(int,[input() for i in range(4)])
ans = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)


Measured memory_bytes: 2940
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, x, ans;

int main()
{
	in >> N;
	std::vector<LL>a(N);
	rep(i, N)
	{
		in >> a[i];
		x ^= a[i];
	}
	for (LL k = 32; k >= 0; --k)
	{
		if (x&(1 << k))
		{
			rep(i, N)
			{
				if ((a[i] ^ (a[i] - 1)) == (1LL << (k + 1)) - 1)
				{
					x ^= (a[i] ^ (a[i] - 1));
					++ans;
					break;
				}
			}
		}
	}
	out << (x == 0 ? ans : -1) << std::endl;
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>

using namespace std ;
int main()
{
    int a,b;
     cin>>a>>b;

        int max=-9999999;

        if(a+b>=max){
            max=a+b;
        }
        if(a-b>=max){
            max=a-b;
        }
        if(a*b>=max){
            max=a*b;
        }
        cout<<max<<endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,Y,x=0,y=0,z=0;
	cin>>n>>Y;
	Y/=1000;
	if(n>Y||n*10<Y){
		cout<<-1<<" "<<-1<<" "<<-1;
		return 0;
	}
	Y-=n;
	for(z=n;Y!=0&&z>0;z--){
		if(Y%9==0){
			Y-=9;
			x++;
		}
		else{
			Y-=4;
			y++;
		}
	}
	if(Y==0){
		cout<<x<<" "<<y<<" "<<z;
		return 0;
	}
	cout<<-1<<" "<<-1<<" "<<-1;
	return 0;
}


Measured memory_bytes: 256
A, B, M = map(int, input().split())
a = input().split()
b = input().split()
low = int(min(a)) + int(min(b))

p = []
for i in range(M):
    s = input().split()
    p.append(int(a[int(s[0])-1])+int(b[int(s[1])-1])-int(s[2]))
p.append(low)
print(min(p))

Measured memory_bytes: 20948
#include<cstdio>
using namespace std;
const int N = 1000000;
int IsPrime[N];
int main(){

  IsPrime[0] = 1;
  IsPrime[1] = 1;
  for(int i=2; i<=N;i++){
    if(IsPrime[i]==0){
      for(int j=2*i; j<=N; j+=i)
        IsPrime[j] = 1;
      }
  }
  int max;
  while(~scanf("%d",&max)){
    int count=0;
    for(int i=1; i<max+1; i++)
      if(IsPrime[i]==0) count++;
    printf("%d\n",count);
  }
}


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

int main(){
    int a,b,c,ans;
    cin>>a>>b>>c;
    if(a>=b&&a>=c) ans=b+c;
    else if(b>=a&&b>=c) ans=a+c;
    else ans=b+a;
    cout<<ans<<endl;
    return 0; 
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int N;
    int i;
    int v;
    int j;
    int k;
    scanf("%d",&N);
    int A[N];
    
    
    for(i=0; i<N; i++){
        scanf("%d",&A[i]);
    }
    for(i=0; i<N; i++){
        v = A[i];
        j = i-1;
        while( j>= 0 && A[j] > v){
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        for(k=0; k<N; k++){
            printf("%d",A[k]);
            if(k<N-1) printf(" ");
        }
        printf("\n");
    }
    
    
    
    return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

static const long long FAR = (1LL << 31);
static const int N = 100;

int n, m;
bool visited[N];
long long d[N][N];


void floyd(){
	for (int k = 0; k < n; ++k) {
		for (int l = 0; l < n; ++l) {
			if (d[l][k] == FAR) continue;
			for (int r = 0; r < n; ++r) {
				if (d[k][r] == FAR) continue;
				d[l][r] = min(d[l][r], d[l][k] + d[k][r]);
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) d[i][j] = (i!=j)?FAR:0;
	}

	for (int i = 0; i < m; ++i) {
		int u, v, e; cin >> u >> v >> e;
		d[u][v] = e;
	}

	floyd();
	
	bool negitive = false;
	for (int i = 0; i < n; ++i){
		if (d[i][i] < 0) negitive = true;
	}

	if (negitive) cout << "NEGATIVE CYCLE" << endl;
	else{
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (j != 0) cout << " ";

				if (d[i][j] == FAR) cout << "INF";
				else cout << d[i][j];
			}
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3132
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<double, double> Pdd;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;

const ll mod = 1e9+7;
const int INF = 2e9;
const double epsilon = 1e-7;
const double PI = 3.1415926535;

int p[20000];
int a[20000];
int b[20000];
int main(void){
    int n; cin >> n; for(int i = 0;i < n;i++){int a; cin >> a; a--; p[a] = i;}
    a[0] = 1; b[0] = 1000000000;
    for(int i = 1;i < n;i++){
        if(p[i] - p[i-1] > 0){
            a[i] = a[i-1] + 1 + p[i] - p[i-1];
            b[i] = b[i-1] - 1;
        }else{
            a[i] = a[i-1] + 1;
            b[i] = b[i-1] - 1 + p[i] - p[i-1];
        }
    }
    printf("%d", a[0]); for(int i = 1;i < n;i++)printf(" %d", a[i]);
    printf("\n");
    printf("%d", b[0]); for(int i = 1;i < n;i++)printf(" %d", b[i]);
    printf("\n");
 	return 0;
}


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

int main(){
  float x, y;
  float O = 100;
  scanf("%f", &x);
  scanf("%f", &y);
    float A = x * y;
  A = (double)(int)A;
  cout << A * 1000 / 1000<< endl;
  return 0;
}


Measured memory_bytes: 3848
a,b,k = map(int,input().split())

aa = list(range(a,min(a+k,b)))
bb = list(range(max(b-k+1,a),b+1))
aa.extend(bb)
c = set(aa)
d = list(c)
d = sorted(d)
for i in range(len(d)):
    print(d[i])

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

bool bs(int* array, int n, int x) {
	int left, right, mid;
	left = 0;
	right = n;
	mid = (left + right) / 2;
	while (array[mid] != x && left < right) {
		if (array[mid] < x) {
			left = mid + 1;
		} else {
			right = mid;
		}
		mid = (left + right) / 2;
	}
	return array[mid] == x;
}

int main(void) {
	int n;
	scanf("%d", &n);
	int* array = new int[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &array[i]);
	}
	int q, x;
	scanf("%d", &q);
	while (q--) {
		scanf("%d", &x);
		if (bs(array, n, x))
			printf("1\n");
		else
			printf("0\n");
	}
}


Measured memory_bytes: 3520
N=int(input())
L=[]
for i in range(N):
    l=list(input())
    L.append(l)
    
#print(L)
F=0
ans=0
for i in range(N):
    F=0
    for a in range(N):
        if F==1:
            break
        for b in range(N):
            if L[a][(b+i)%N]!=L[b][(a+i)%N]:
                F=1
                break
    if F==0:
        ans+=N
        #print(i)
print(ans)

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

#define MOD 998244353
long long power(long long x, long long y) 
{ 
    long long res = 1;     // Initialize result 
   
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % MOD; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % MOD;  // Change x to x^2 
    } 
    return res; 
}


int main() {
    // oh hi mark
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,m,v, p ; cin >> n >> m >> v >> p;
    int a[n];
    for(int i = 0; i< n; i++) cin >> a[i];
    long long c[n];
    sort(a, a+n);
    for(int i = 0; i < n; i++) {
        if(i == 0) {
            c[i] = a[i]; 
        }
        else {
            c[i] = c[i-1] + a[i];
        }

    }

    

    int pth = a[n-p];
    
    long long left = 0;
    long long right = (p-1) * m;
    long long gap = n - p;
    for(int i = 0; i < n; i++) {
        left += m;
        long long dis = m*v;
        dis -= left;
        dis -= right;

        int ind = upper_bound(a, a+n, a[i]+m) - a;
        if(ind <= n-p) continue;

        long long sum = c[n-p] - c[i];
        long long safe = (long long)(a[i] + m) * (n-p - i);
        
        

        long long canabsorb = safe - sum;

        long long extra = dis - canabsorb;
        
        if(extra  <= 0) {
            cout << n-i << endl;
            break;
        }
        gap--;
    }
    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define SET(a, b) memset(a, b, sizeof(a))
#define eps 1e-6
#define PI atan(1) * 4
#define mod 1000000007
using namespace std;
ll num[100005];
ll x, y, z;
bool ok (ll a) {
	ll s = 0;
	for (ll i = 1; i <= x; i++) {
		ll t = num[i] - z * a;
		if (t <= 0) continue;
		s += (t / (y - z)) + (t % (y - z) > 0);
		if (s > a) break;
	}
	return (s <= a);
}
int main () {
	ll a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q;
	scanf("%lld %lld %lld", &x, &y, &z);
	for (i = 1; i <= x; i++) {
		scanf("%lld", &num[i]);
	}
	d = 0; e = 1e9;
	while (d <= e) {
		f = (d + e) / 2;
		if (ok(f)) e = f - 1;
		else d = f + 1;
	}
	printf("%lld\n", d);
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>


int main()
{
  int cnt;
  int a,b,c;
  int i;

  cnt = scanf("%d %d %d", &a, &b, &c);

  if (a < b) {
    if ((a <= c) &&
        (c <= b)) {
      printf("Yes");
      return 0;
    } else {
      printf("No");
      return 0;
    }
  }

  if ((b <= c) &&
      (c <= a)) {
    printf("Yes");
    return 0;
  } else {
    printf("No");
    return 0;
  }

  return 0;
}


Measured memory_bytes: 128
#  --*-coding:utf-8-*--

def f(T, X, S, k):
    if k == len(T):
        return 1 if S == X else 0

    return f(T, X, S, k+1) + f(T, X, S^T[k], k+1)
        

    

def main():
    N, M = map(int, input().split())

    T = [0]*N
    for i in range(M):
        L = list(map(int, input().split()))
        for sw in L[1:]:
            T[sw-1] |= (1 << i)

    X = 0
    P = map(int, input().split())
    for i, p in enumerate(P):
        X |= ((1<<i) if p == 1 else 0)



    print(f(T, X, 0, 0))


if __name__ == '__main__':
    main()



Measured memory_bytes: 3064
//include,namespace
 #include<bits/stdc++.h>
 #include<iostream> 
 #include <queue>
 #include <vector>
 #include <string>
 using namespace std;
//REPmacro
 #define all(x) (x).begin(),(x).end()             //ソート
 #define FOR(i,x,n)for(int i=(x);i<(n);i++)
 #define FOR_R(i,x,n) for(int i=(n-1);i>=(x);i--)
 #define REP(i, n) FOR(i, 0, n)
 #define REP_R(i, n) FOR_R(i, 0, n)
//long long(define)
 using ll = long long;
 typedef long long ll;
 typedef long long int64;
 typedef long long lint;
 typedef long long lli;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
////////////////いろいろあるよ//////////////////////////////////
int main(){
	ll a; cin >> a;
    int m; cin >> m;
    ll data[m];
    REP(i,m){
    	int piyo=0; cin >> piyo;
        a-=piyo;
        if(a<0){cout << -1 << endl; return 0;}
    }
    
  cout << a << endl;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define ARRS ((ll)(1e5+100))
#define pb push_back

bool p[6005][6005];

int main(){
   ll a,b,c,d,e,f;
   cin>>a>>b>>c>>d>>e>>f;
   p[0][0]=1;
   for(int i=0; i<=f; i++){
      for(int j=0; j<=f; j++){
         if(p[i][j]){
            p[i+100*a][j]=1;
            p[i+100*b][j]=1;
            p[i][j+c]=1;
            p[i][j+d]=1;
         }
      }
   }
   pair<ll,ll> pas={a*100,0};
   for(int i=1; i<=f; i++){
      for(int j=0; j<=f; j++){
         if(p[i][j]&&i+j<=f&&j*100<=e*i&&1.0*j/(i+j)>1.0*pas.sc/(pas.fr+pas.sc)){
            pas={i,j};
         }
      }
   }
   cout<<pas.fr+pas.sc<<" "<<pas.sc<<endl;
   
   return 0;
}


Measured memory_bytes: 24832
#include<stdio.h>

int main(void)
{
   int a, b;
   
   scanf("%d %d",&a ,&b);

   if(a < b) printf("a < b\n");
   else if(a > b) printf("a > b\n");
   else if(a == b) printf("a == b\n");

    return 0;
}

Measured memory_bytes: 580
#pragma region

#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define _rep3(i, begin, end) for (register int i = (begin); i < (end); i++)
#define _irep3(i, begin, end) for (register int i = (end)-1; i >= (begin); i--)
#define _rep2(i, n) _rep3(i, 0, n)
#define _irep2(i, n) _irep3(i, 0, n)
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__, _rep3, _rep2, )(__VA_ARGS__)
#define irep(...) _overload3(__VA_ARGS__, _irep3, _irep2, )(__VA_ARGS__)
#define out(x) cout << (x) << '\n';
#define debug(x) cerr << #x << " = " << (x) << " (line: " << __LINE__ << ") " << endl;
typedef long long ll;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "vec[ ";
  rep(i, vec.size()) i == 0 ? os << vec[i] : os << ", " << vec[i];
  os << " ]";
  return os;
}

#pragma endregion

#define MOD 1000000007
#define INF 2147483647

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);

  ll N;
  cin >> N;
  vector<ll> h(N);
  cin >> h;

  vector<ll> dp(N);
  dp[0] = 0;
  dp[1] = abs(h[0] - h[1]);
  rep(i, 1, N - 1) {
    dp[i + 1] = min(abs(h[i - 1] - h[i + 1]) + dp[i - 1], abs(h[i] - h[i + 1]) + dp[i]);
  }
  out(dp[N - 1]);
}


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

using namespace std;

int main(){
  bool x = true;
  int N;
  cin >> N;
  int A[N];

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

  for(int j = 0;j < N;j++){
    if(A[j] % 2){
      //偶数
    }
    else{
      if((A[j] % 3)){
        //３で割れない
        if((A[j] % 5)){
          //３、５で割れない
          x = false;
        }
      }
    }
  }


  if(x)
    cout << "APPROVED";
  else
    cout << "DENIED";
  return 0;
}


Measured memory_bytes: 256
class Bar
	def initialize(a)
		@h = a[0]
		@p = a[1]
		@q = a[2]
	end

	attr_accessor :h
	attr_accessor :p
	attr_accessor :q
end

loop do
	n, m, a = gets.split.map(&:to_i)
	if n == 0 && m == 0 && a == 0 then
		break
	end

	b = []

	m.times do
		b.push Bar.new(gets.split.map(&:to_i))
	end

	b.sort!{|a0, b0| b0.h <=> a0.h }

	m.times do |i|
		if b[i].p == a then
			a = b[i].q
		elsif b[i].q == a then
			a = b[i].p
		end
	end

	puts a
end

Measured memory_bytes: 6120
#include  <functional>
#include  <algorithm>
#include  <exception>
#include  <stdexcept>
#include  <streambuf>
#include  <iterator>
#include  <string.h>
#include  <stdlib.h>
#include  <typeinfo>
#include  <valarray>
#include  <iostream>
#include  <sstream>
#include  <istream>
#include  <stdio.h>
#include  <climits>
#include  <clocale>
#include  <complex>
#include  <csetjmp>
#include  <csignal>
#include  <cstdarg>
#include  <cstddef>
#include  <ctype.h>
#include  <cassert>
#include  <cstdlib>
#include  <utility>
#include  <cstring>
#include  <numeric>
#include  <ostream>
#include  <cwctype>
#include  <fstream>
#include  <iomanip>
#include  <math.h>
#include  <bitset>
#include  <cctype>
#include  <string>
#include  <vector>
#include  <limits>
#include  <locale>
#include  <memory>
#include  <cerrno>
#include  <time.h>
#include  <iosfwd>
#include  <cfloat>
#include  <cstdio>
#include  <cwchar>
#include  <cmath>
#include  <ctime>
#include  <deque>
#include  <queue>
#include  <stack>
#include  <list>
#include  <ios>
#include  <map>
#include  <set>
#include  <new>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=100005;
bool m[maxn];
int n,ans,minn;
int a[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==i)
        {
            if(a[i-1]==i-1 && i!=1 && !m[i-1])
            {
                m[i-1]=m[i]=1;
                minn++;
                //cout<<i<<endl;
            }
            ans++;
        }
    }
    cout<<ans-minn<<endl;
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<" "<<x<<"\n";
#define lli long long int
long long int mod= 1000000007,modd=998244353;
int32_t main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);  cout.tie(0);
   lli i,l,r,d,ans=0;
   cin>>l>>r>>d;
   for(i=l;i<=r;i++)
     if(i%d==0) ans++;
   cout<<ans<<"\n";
   return 0;
}//main


Measured memory_bytes: 3656
def main():
    n, m, v, p = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-1:]
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return True

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    print(n-b_search(0, n-1, value))


main()


Measured memory_bytes: 16340
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {


    public static void main(String[] args) {


        Scanner scan = new Scanner(System.in);
String X=scan.next();
String T="A";
       if (X.equals("a")){T="a";}
        if (X.equals("q")){T="a";}
        if (X.equals("w")){T="a";}
        if (X.equals("e")){T="a";}
        if (X.equals("r")){T="a";}
        if (X.equals("t")){T="a";}
        if (X.equals("y")){T="a";}
        if (X.equals("u")){T="a";}
        if (X.equals("i")){T="a";}
        if (X.equals("o")){T="a";}
        if (X.equals("p")){T="a";}
        if (X.equals("s")){T="a";}
        if (X.equals("d")){T="a";}
        if (X.equals("f")){T="a";}
        if (X.equals("g")){T="a";}
        if (X.equals("h")){T="a";}
        if (X.equals("j")){T="a";}
        if (X.equals("k")){T="a";}
        if (X.equals("l")){T="a";}
        if (X.equals("z")){T="a";}
        if (X.equals("x")){T="a";}
        if (X.equals("c")){T="a";}
        if (X.equals("v")){T="a";}
        if (X.equals("b")){T="a";}
        if (X.equals("n")){T="a";}
        if (X.equals("m")){T="a";}
       System.out.println(T);


    }
    }




Measured memory_bytes: 26892
def resolve():
    S = str(input())
    n = S.count('N')
    s = S.count('S')
    w = S.count('W')
    e = S.count('E')
    if n > 0 and s == 0:
        print('No')
        return
    if n == 0 and s > 0:
        print('No')
        return
    if w > 0 and e == 0:
        print('No')
        return
    if w == 0 and e > 0:
        print('No')
        return
    print('Yes')

    return


resolve()

Measured memory_bytes: 3064
// atcoder/agc036/A/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; for (auto& i: v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { for (auto& i: v) is >> i; return is; }
template<typename T> ostream& operator << (ostream& os, set<T> s) { os << "#{"; for (auto& i: s) os << i << ","; os << "}"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; for (auto& i: m) os << i << ","; os << "}"; return os; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

using lli = long long int;
using ull = unsigned long long;
using point = complex<double>;
using str = string;
template<typename T> using vec = vector<T>;

constexpr array<int, 8> di({0, 1, -1, 0, 1, -1, 1, -1});
constexpr array<int, 8> dj({1, 0, 0, -1, 1, -1, -1, 1});
constexpr lli mod = 1e9 + 7;

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.setf(ios_base::fixed);
  cout.precision(15);

  lli s;
  while (cin >> s) {
    lli n = ceil(sqrt(s));
    lli m = n * n - s;
    lli a = m;
    lli b = 1;
    for (lli i = 1; i * i <= m; ++i) {
      if (m % i == 0) {
        a = m / i;
        b = i;
      }
    }
    cout << 0 << ' ' << 0 << ' ' << n << ' ' << a << ' ' << b << ' ' << n << endl;
    // assert(abs(n * n - a * b) == s);
  }

  return 0;
}


Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dl double long
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rrep(i, m, n) for(ll i = (ll)(m); i > (ll)(n); --i)
const ll MOD = 1000000007;
const double pi = 3.14159265358979323846;

int main(void){
    int n, a[200000];
    ll k;
    cin >> n >> k;
    bool *b = new bool[n];
    rep(i, 0, n){
        cin >> a[i];
        b[i] = false;
    }
    int count = 0, now = 0;
    while(!b[now]){
        b[now] = true;
        now = a[now]-1;
        count++;
        if(count == k){
            cout << now+1 << endl;
            return 0;
        }
    }
    int lstart = now;
    now = 0;
    int ccount = 0;
    while(now != lstart){
        now = a[now]-1;
        ccount++;
    }
    int lcount = count - ccount;
    k -= ccount;
    k %= lcount;
    now = lstart;
    for(int i = 0; i < k; ++i){
        now = a[now]-1; 
    }
    cout << now+1 << endl;
    return 0;
}

Measured memory_bytes: 4612
def dfs(s,n):
    if int(s)>n:
        return 0
    ans=1000000
    if(s.count('7')>0 and s.count('5')>0 and s.count('3')>0):
        ans=1
    else:
        ans=0
    for c in '357':
        ans+=dfs(s+c,n);
    return ans
    
    
n=int(input())
print(dfs('0',n))
        
    
    
        


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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)
// while (getline(cin, S)) {}

// #include <cstdio>
// int a;
// scanf("%d", &a);
// printf("%d\n", a);
//
// for (int i=0; i<n; ++i)
// 	scanf("%d", &a[i]);
//
// char c;
// scanf(" %c", &c);
//
// cout << "\n";

// cout <<fixed <<setprecision(10)

// priority_queue<int> q;
// priority_queue<int, vector<int>, less<int>> q; // Default: vector, less
// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

//
// Notes
//
// When specified less than N, try full scan.
// RE: empty vector
// Check Qs
// long/int
// xor -> count each bit
// Check values
// 	1,000,000 -> Loop
// 	100,000	-> vector(int:400KB, long:800KB) 

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

/*
ll	myPow(ll x, ll n) {
	if (0==n)
		return 1;
	if (0==n%2)
		return myPow(x*x%MOD, n/2);
	else
		return x*myPow(x, n-1)%MOD;
}
*/
ll	myPow(ll x, ll n) {
	ll r=1;
	while(n>0)
		if (0==n%2) {
			x *=x;
			x %=MOD;
			n /=2;
		} else {
			r *=x;
			r %=MOD;
			n--;
		}
	return r;
}

#define	Rep0(i, n)	for (auto i=0; i<n; i++)
#define	Rep1(i, n)	for (auto i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	ll N, H, W;
	cin >>N >>H >>W;
	ll S=0;
	Rep0(i, N) {
		ll A, B;
		cin >>A >>B;
		if ((A>=H)&&(B>=W))
			S++;
	}
	cout <<S <<endl;
	return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>
#include <string>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;

#define rep(i, n) for(int i = 0; i < n ; i++ )
#define For(i, a, b) for(int i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const int MAX_N = 8;

int main(void){
    int N, A, B, C;
    int l[MAX_N];
    int answer = 1e9;

    cin >> N >> A >> B >> C;

    rep(i, N){
        cin >> l[i];
    }

    int upper = 1;
    rep(i, N) upper *= 4;

    rep(i, upper){
        int a = A;
        int b = B;
        int c = C;
        int tmp = i;
        bool cnt[3] = {false, false, false};
        int cost = -30;

        rep(j, N){
            if (tmp % 4 == 0) {a -= l[j]; cost += 10; cnt[0] = true;}
            else if(tmp % 4 == 1) {b -= l[j]; cost += 10; cnt[1] = true;}
            else if(tmp % 4 == 2) {c -= l[j]; cost += 10; cnt[2] = true;}
            tmp /= 4;
        }

        if (cnt[0] && cnt[1] && cnt[2]){
            cost += abs(a) + abs(b) + abs(c);
            answer = min(cost, answer);
        }
    }

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 256
// ABC052 B - Increment Decrement
#include <stdio.h>

int main(void) {
    int N;
    char S[101];
    // input
    scanf("%d", &N);
    scanf("%s", S);

    int x = 0;
    int result = 0;
    int i = 0;
    while (S[i] != '\0') {
        if (S[i] == 'I') {
            x++;
        } else {
            x--;
        }
        if (x > result) {
            result = x;
        }
        i++;
    }

    printf("%d\n", result);
}

Measured memory_bytes: 128
import numpy as np

N = int(input())
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))

A1_cum_left = np.cumsum(A1)
A2_cun_right = np.cumsum(A2[::-1])

ans = 0
for i in range(N):
    ans = max(ans, A1_cum_left[i] + A2_cun_right[N-i-1])

print(ans)


Measured memory_bytes: 13796
//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>
#include <cstdint>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef unsigned long long		SQWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
/* 最大公約数 */
ll gcd(ll a, ll b) 
{
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

	if (IsOdd(K)) {
		cout << (K / 2) * ((K + 1) / 2) << endl;
	} else {
		cout << (K / 2) * (K / 2) << endl;
	}

	return 0;
}


Measured memory_bytes: 256
/*
	Name:
	Author: xiaruize
	Date:
*/

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

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define ll long long
#define form(i,j,n) for(int i=int(j);i<=int(n);i++)
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pis pair<int,string>
#define sec second

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

int f[20][20];
int num[200000];
int main()
{
 	ios::sync_with_stdio(false);
	cin.tie(0);
 	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n;
	n=read();
	int x;
	form(i,1,n)
	{
		x=i;
		while(x>=10)
		{
			x/=10;
		}
		num[i]=x;
		f[x][i%10]++;
	}
	int ans=0;
	form(i,1,n)
	{
		ans+=f[i%10][num[i]];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#![allow(unused_imports)]
use std::io;
use std::cmp;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::collections::HashSet;
use std::f64::consts::PI;
use std::str::FromStr;
use std::cmp::Reverse;

#[allow(dead_code)]
type Error = Box<dyn std::error::Error>;

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).ok();
    buf
}

struct Scanner {
    buff: Vec<String>,
    pos: usize,
}

#[allow(dead_code)]
impl Scanner {
    pub fn new() -> Self {
        Scanner {
            buff: Vec::new(),
            pos: 0,
        }
    }

    pub fn next<T: FromStr>(&mut self) -> T {
        while self.buff.len() <= self.pos {
            self.pos = 0;
            self.buff = read_line().split_whitespace().map(|s| s.to_owned()).collect();
        }

        let result = self.buff[self.pos].parse::<T>();
        self.pos += 1;
        result.ok().unwrap()
    }

    pub fn next_line(&mut self) -> String {
        let result  = read_line().trim().to_owned();
        self.buff.clear();
        self.pos = 0;

        result
    }

    pub fn next_vec<T: FromStr>(&mut self) -> Vec<T> {
        self.buff.clear();
        self.pos = 0;
        read_line().trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect()
    }
    
    pub fn next_line_chars(&mut self) -> Vec<char> {
        let result  = read_line().trim().chars().collect();
        self.buff.clear();
        self.pos = 0;

        result
    }
}


fn main() {
    let mut sc = Scanner::new();
    let m: usize = sc.next();
    let mut ans = 0;
    let mut sum = 0;
    for _i in 0..m {
        let d:u64 = sc.next();
        let c:u64 = sc.next();
        sum += d*c;
        ans += c;
        if sum > 0 {
            let tmp = (sum+8)/9 -1;
            ans += tmp;
            sum -= tmp*9;
        }
    }
    println!("{}", ans-1);
}


Measured memory_bytes: 2116
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=105;
struct edge{
	int to,next;
}e[N*2];
int n,d[N][N],v[N];
int head[N],tot;
ll ans1,ans2;
void add(int x,int y){
	e[++tot]=(edge){y,head[x]};
	head[x]=tot;
}
void dfs(int x,int fa,int d){
	int s=0;
	for (int i=head[x];i;i=e[i].next)
		if (e[i].to!=fa)
			++s,dfs(e[i].to,x,d+1);
	v[d]=max(v[d],s);
}
int main(){
	scanf("%d",&n);
	For(i,1,n) For(j,1,n)
		d[i][j]=(i==j?0:1<<28);
	For(i,1,n-1){
		int x,y;
		scanf("%d%d",&x,&y);
		d[x][y]=d[y][x]=1;
		add(x,y); add(y,x);
	}
	For(k,1,n) For(i,1,n) For(j,1,n)
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	ans1=ans2=1ll<<60;
	For(i,1,n){
		int mx=0;
		For(j,1,n) mx=max(mx,d[i][j]+1);
		memset(v,0,sizeof(v));
		dfs(i,0,1);
		ll val=1;
		For(j,1,n)
			if (v[j]) val*=v[j];
			else break;
		if (mx<ans1) ans1=mx,ans2=val;
		else if (mx==ans1&&val<ans2)
			ans2=val;
	}
	For(i,1,n) For(j,i+1,n) if (d[i][j]==1){
		int mx=0;
		For(k,1,n) mx=max(mx,min(d[i][k],d[j][k])+1);
		memset(v,0,sizeof(v));
		dfs(i,j,1); dfs(j,i,1);
		ll val=2;
		For(j,1,n)
			if (v[j]) val*=v[j];
			else break;
		if (mx<ans1) ans1=mx,ans2=val;
		else if (mx==ans1&&val<ans2)
			ans2=val;
	}
	printf("%lld %lld\n",ans1,ans2);
}

Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define files(name) name!=""?freopen(name".in","r",stdin),freopen(name".out","w",stdout):0
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define elif else if
#define mp make_pair
#define pb push_back
#define fir first
#define sec second

using namespace std;
#define int long long

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;

const int arr=2e5+10;
const int ar=2e3+10;
const ld pi=acos(-1);
const ld eps=1e-10;
const ll md=1e9+7;

///---program start---///

#define arr (int)(1e7+10)

int bpow(int a,int n)
{
    int res=1;
    while (n){
        if (n&1){
            res=res*a%md;
        }
        n/=2;
        a=a*a%md;
    }
    return res;
}

void inc(int& a,int b)
{
    a+=b;
    if (a>=md){
        a-=md;
    }
}

int f[arr];
int rf[arr];

int C(int n,int k)
{
    return f[n]*rf[k]%md*rf[n-k]%md;
}

int H(int n,int m)
{
    return C(n+m,n);
}

int dp[ar][ar];

main()
{
    #ifdef Barik
        files("barik");
        freopen("debug.txt","w",stderr);
    #endif

    f[0]=1;
    for (int i=1;i<arr;i++){
        f[i]=f[i-1]*i%md;
    }
    rf[arr-1]=bpow(f[arr-1],md-2);
    for (int i=arr-2;i>=0;i--){
        rf[i]=rf[i+1]*(i+1)%md;
    }

    int n,k;
    cin>>n>>k;
    if (k==1){
        cout<<1<<"\n";
        return 0;
    }
    dp[0][0]=1;
    for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++){
            if (i!=0){
                inc(dp[i][j],dp[i-1][j]);
            }
            if (i<j){
                inc(dp[i][j],dp[i][j-1]*H(k-2,(j-i-1)*(k-1)+i*(k))%md);
            }
//            cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        }
    }
    int ans=dp[n][n]*f[n]%md;
    cout<<ans<<"\n";
}


Measured memory_bytes: 188032
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define test int t;cin>>t;while(t--)
#define REP(i,n) for (int i = 1; i <= n; i++)
#define MOD 1000000007
#define ll long long
#define int ll
#define pb push_back
#define ii pair<int,int>
#define llll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<ii>
#define vllll vector<llll>
#define ff first
#define ss second
#define INF 1000000000
#define HINF 1000000000000000
#define mem(a,b) memset(a,b,sizeof(a))
#define deb(x) cout<<#x<<'='<<x<<endl
const double pi = 3.14159265358979323846;

ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int C(int n,int k)
{
	int ans=1;
	if(k>n-k)
	k=n-k;
	for(int i=1;i<=k;i++)
	ans*=(n-i+1),ans/=i;
	return ans;
}

void solve()
{

	int i=0,j=0,k=0,m,n,p,sum=0,cnt=0;
	cin>>n;
	if(n%1000==0)
	cout<<0;
	else cout<<((n/1000)+1)*1000-n;
}
int32_t main() {
    fast
    //freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w+", stdout);
    //test
    {
        
        solve();
		
		      
    }
    return 0;
}
  

Measured memory_bytes: 3644
#include <iostream>

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

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

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

//repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const long long INFL = __LONG_LONG_MAX__ / 10;
const int INFI = __INT_MAX__ / 10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

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

uint64_t popcnt(uint64_t n)
{
    uint64_t c = 0;
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333);
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f);
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff);
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff);
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff);
    return (c);
}

int N;
const int LimitN = 100000;
string S;

int main()
{
    ios::sync_with_stdio(false);

    cin >> N >> S;

    char old = '$';

    int ans = 0;
    REP(i, N)
    {
        if (S[i] != old)
        {
            ans++;
            old = S[i];
        }
    }

    cout << ans << endl;

    // cout
    // << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =4e5+100;
const int MOD = 1e9+7;
int f[N],g[N];
int fpow(int x,int p){
    int rs=1;
    while(p){
        if(p&1) rs=1LL*rs*x%MOD;
        x=1LL*x*x%MOD; p>>=1;
    }
    return rs;
}
int C(int n,int m){
    return 1LL*f[n]*g[m]%MOD*g[n-m]%MOD;
}

int n,k,ans;
int main(){
    f[0]=g[0]=1;
    for(int i=1;i<N;++i) f[i]=1LL*f[i-1]*i%MOD;
    g[N-1]=fpow(f[N-1],MOD-2);
    for(int i=N-2;i>=1;--i) g[i]=1LL*g[i+1]*(i+1)%MOD;
    scanf("%d %d",&n,&k); k=min(n-1,k);
    for(int i=0;i<=k;++i){
        ans=(ans+1LL*C(n,i)*C(n-1,n-i-1))%MOD;
    }
    printf("%d\n",ans);
}


Measured memory_bytes: 3328
H,W,M = map(int,input().split())
h = [0] * (H+1)
w = [0] * (W+1)
hw = []
for i in range(M):
    hin,win = map(int,input().split())
    hw.append((hin,win))
    h[hin] += 1
    w[win] += 1
maxh = max(h)
maxw = max(w)
hlis = set()
for i in range(H+1):
    if h[i] == maxh:
        hlis.add(i)
wlis = set()
for i in range(W+1):
    if w[i] == maxw:
        wlis.add(i)
#print(hlis,wlis)
cnt = 0
for i in hw:
    if i[0] in hlis and i[1] in wlis:
        cnt += 1
if cnt == len(hlis) * len(wlis):
    print(maxh+maxw-1)
else:
    print(maxh+maxw)


Measured memory_bytes: 166636
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

ll dp[85];

int main() {
    int n; cin >> n;
    vint a(n);
    rep(i,n) cin >> a[i];
    dp[0] = 1000;
    REP(i,n+1) {
        chmax(dp[i],dp[i-1]);
        for (int j = 1; j < i; j++) {
            ll n_stock = dp[j]/a[j-1];
            chmax(dp[i],n_stock*a[i-1]+dp[j]%a[j-1]);
        }
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n;
	double a[110],sum = 0;
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> a[i];
		sum += 1.0 / a[i];
	}
	printf("%.9lf\n",1.0 / sum);
}

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
template<class T>
inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}
template<class T>
inline bool chmin(T &a, T b) {if(a > b) {a = b;return true;}return false;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;

//----------------------------------------------------------

int N;
ll A[10005];

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

int64_t mul(int64_t a, int64_t b){
    return ((a % MOD) * (b % MOD)) % MOD;
}

int64_t power(int64_t x, int64_t y){
    if   (y == 0) return 1;
    else if (y == 1) return x % MOD;
    else if (y % 2 == 0) {int64_t tmp = power(x, y/2);return mul(tmp,tmp) % MOD;}
    else {int64_t tmp = power(x, y/2);return mul(mul(tmp,tmp),x) % MOD;}
}

int64_t division(int64_t a, int64_t b){
    return mul(a, power(b, MOD-2));
}

int main(){
    cin >> N;
    FOR(i,1,N+1)cin >> A[i];
    int64_t ans=0;
    sort(A+1,A+N+1,greater<>());
    map< int64_t, int > g = prime_factor(A[1]);
    FOR(i,2,N+1)
    {
        map< int64_t, int > b = prime_factor(A[i]);
        for(auto it = b.begin();it!=b.end();it++)
        {
            chmax(g[(*it).first],(*it).second);
        }
    }
    int64_t total=1;
    for(auto it=g.begin();it!=g.end();it++)
    {
        int64_t a1=1;
        REP(i,(*it).second)
        {
            a1=mul(a1,(*it).first);
        }
        total = mul(total,a1);
    }
    FOR(i,1,N+1)
    {
        ans+=division(total,A[i]);
    }
    cout << (ans%MOD) << endl;
    return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll k,t;
    cin >> k >> t;
    vector<int> a(t);
    int i,j;
    for(i=0;i<t;i++)cin >> a.at(i);
    sort(a.begin(),a.end());

    ll sum=0;
    ll ans=0;
    for(i=0;i<t-1;i++){
        sum+=a.at(i);
    }
    if(sum+1>=a.at(t-1))ans=0;
    else ans = a.at(t-1) - sum -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256