akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

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

    string A, B; cin >> A >> B;
    if(A.length() > B.length())
    {
        cout << "GREATER" << endl;
        return 0;
    }
    else if(A.length() < B.length())
    {
        cout << "LESS" << endl;
        return 0;
    }
    else
    {
        REP(i, (int)A.length()) 
        {
            if(A[i] > B[i])
            {
                cout << "GREATER" << endl;
                return 0;
            }
            if(A[i] < B[i])
            {
                cout << "LESS" << endl;
                return 0;
            }
        }
    }
    cout << "EQUAL" << endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, e, n) for (int i = e; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const ll inf=1000000000007;

int main() {
  int x,y,z,k;
  cin >> x >> y >> z >> k;
  vector<ll> a(x);
  vector<ll> b(y);
  vector<ll> c(z);
  rep(i,0,x) cin >> a[i];
  rep(i,0,y) cin >> b[i];
  rep(i,0,z) cin >> c[i];

  priority_queue<ll> abc;
  priority_queue<ll> ab;

  rep(i,0,x) rep(j,0,y){
    ll val=a[i]+b[j];
    ab.push(val);
  }

  sort(c.rbegin(), c.rend());
  ll e=min(x*y,k);

  rep(i,0,e){
    ll val1=ab.top(); ab.pop();
    rep(j,0,z){
      abc.push(val1+c[j]);
    }
  }

  rep(i,0,k){
    ll ans = abc.top(); abc.pop();
    cout << ans << endl;
  }
  return 0;
}

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

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


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int inf = 1001001001;

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


int main(){
  int k,ans = 0;
  cin >> k;
  
  for(int i = 1; i <= k; i++){
    for(int j = 1; j <= k; j++){
      for(int l = 1; l <= k; l++){
        int temp = gcd(i,j);
        int temp2 = gcd(temp,l);
        ans += temp2;
      }
    }
  }
  
  cout << ans << endl;
  
}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007;

int main(){
    
    int N,K;cin>>N>>K;
    vector<ll> S(N),sum(N-K+1),choice(N-K+1);
    for(int i=0;i<N;i++){
        cin>>S[i];
    }
    ll a=0;
    for(int i=0;i<K;i++){
        a+=S[i];
    }
    sum[0]=max(a,0LL);
    for(int i=1;i<N-K+1;i++){
        a=a-S[i-1]+S[i-1+K];
        sum[i]=max(a,0LL);
    }
    ll b=0;
    for(int i=K;i<N;i++){
        if(S[i]>0) b+=S[i];
    }
    choice[0]=b;
    for(int i=0;i<N-K;i++){
        if(S[i]>0) b+=S[i];
        if(S[i+K]>0) b-=S[i+K];
        choice[i+1]=b;
    }
    ll ans=0;
    for(int i=0;i<N-K+1;i++){
        ll c=sum[i]+choice[i];
        ans=max(ans,c);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
/*

    author : s@if

*/

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define 		NIL 			-1
#define         SAIF            main
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			1e9
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> new_data_set;

//*find_by_order(k)  gives the kth element;
//order_of_key(item)   gives the index(number of element strictly less than item) of item;


inline int in() {int x; scanf("%d", &x); return x; }
bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};    // King's move
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hx[]={-2,-2,-1,+1,+2,+2,-1,+1};    // Knight's move
int hy[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)3e3+9;

vector<int>adj[MAXN];
int A[MAXN], dp[MAXN];

void dfs(int curr, int prev)
{
    dp[curr] = 0;
    bool flag = false;
    for(int i=0; i<adj[curr].size(); i++)
    {
        int v = adj[curr][i];
        if(v!=prev){
            dfs(v, curr);
            if(dp[v]==0 && A[v]<A[curr]) flag = true;
        }
    }

    if(flag) dp[curr] = 1;
}

int SAIF()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout); */

    ios_base::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);

    int i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>n; For(i,1,n) cin>>A[i];

    for(i=1; i<n; i++)
    {
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(i=1; i<=n; i++)
    {
        dfs(i,-1);
        if(dp[i]==1) cout<<i<<" ";
    }
    cout<<endl;

    return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)


Measured memory_bytes: 4032
import numpy as np

def solve(a, b):
    if a == b: return 2 * (a-1)
    scoreT = a*b
    x = y = int(np.sqrt(scoreT)) - 2
    while True:
        if (x+1)*y < scoreT:
            x += 1
        else:
            break
        if x*(y+1) < scoreT:
            y += 1
        else:
            break
    if x == y:
        return (x-1) * 2
    else:
        return y * 2 - 1


for i in range(int(input())):
    a, b = map(int, input().split())
    print(solve(a, b))

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

int main(){
  int n,w=0,e=0;
  string s;
  cin >> n >> s;
  for(int i=0;i<n;i++)
    if(s.at(i)=='W') w++;
  e=n-w;
  int w2=0,e2=0,ans=n;
  for(int i=0;i<n;i++){
    if(s.at(i)=='W')
      w2++;
    else
      e2++;
    ans=min(ans,e-e2+w2-(s.at(i)=='W'?1:0));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3924
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    struct Position
    {
        internal int x, y;

        public Position(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public bool Equal(Position other)
        {
            if (x != other.x) return false;
            if (y != other.y) return false;
            return true;
        }
    }

    class Program
    {
        static readonly int[] moveX = new int[] { 0, +1, 0, -1 };
        static readonly int[] moveY = new int[] { -1, 0, +1, 0 };

        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            int d = int.Parse(Console.ReadLine());

            bool isStart = true;

            while (d-- > 0)
            {
                if (!isStart) sb.Append("\n");
                else isStart = false;

                int n = int.Parse(Console.ReadLine());

                char[][] map = new char[n][];

                map[0] = Enumerable.Repeat('#', n).ToArray();

                for (int i = 1; i < n; i++)
                {
                    map[i] = Enumerable.Repeat(' ', n).ToArray();
                }

                Position cur = new Position(0, n - 1);
                map[cur.y][cur.x] = '#';

                Position[] target = new Position[4];
                target[0] = new Position(0, 0);
                target[1] = new Position(n - 1, 0);
                target[2] = new Position(n - 1, n - 1);
                target[3] = new Position(2, n - 1);

                bool flg = true;

                while (flg)
                {
                    for (int i = 0; i < 4; i++)
                    {
                        int moveCount = 0;

                        while (!cur.Equal(target[i]))
                        {
                            cur.x += moveX[i];
                            cur.y += moveY[i];
                            moveCount++;

                            map[cur.y][cur.x] = '#';
                        }

                        if (moveCount <= 1)
                        {
                            flg = false;
                            break;
                        }
                    }

                    if (flg)
                    {
                        target[0] = new Position(target[0].x + 2, target[0].y + 2);
                        target[1] = new Position(target[1].x - 2, target[1].y + 2);
                        target[2] = new Position(target[2].x - 2, target[2].y - 2);
                        target[3] = new Position(target[3].x + 2, target[3].y - 2);
                    }
                }

                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        sb.Append(map[i][j]);
                    }
                    sb.Append("\n");
                }
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 9464
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int n, m;
    cin >> n >> m;
    int ikkai = 1900 * m + 100 * (n - m);
    int tim = pow(2, m);
    int ans = ikkai * tim;
    cout << ans;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define PB push_back
#define EB emplace_back
using LL = long long;
using PII = pair<int, int>;
#define F first
#define S second

int main() {
  int k, s;
  cin >> k >> s;
  int ans = 0;
  REPE(i, 0, k)
    REPE(j, 0, k) {
      int r = s - i - j;
      if (r >= 0 && r <= k)
        ans++;
    }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    print(n.count('2'))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;

#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; ++i)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; --i)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))

const int maxn=1e5+100;
int N,M,u[maxn],link[maxn];
int dlt[maxn];

int get_u(int x,int &ret)
{
    if (x==u[x]) return x;
    u[x]=get_u(u[x],ret);
    ret+=dlt[x];
    dlt[x]=ret;
    return u[x];
}

bool check(int x,int y,int d)
{
    int rx=0,ry=0;
    int a=get_u(x,rx),b=get_u(y,ry);
    if (a==b) return (dlt[y]-dlt[x]==d);
    if (link[a]<link[b]) swap(a,b),swap(x,y),d=-d;
    u[b]=a;
    link[a]+=(link[a]==link[b]);
    dlt[b]=dlt[x]-dlt[y]+d;
    return 1;
}

int main()
{
    for (; scanf("%d%d",&N,&M)!=EOF; )
    {
        bool flag=1;
        For(i,1,N) u[i]=i,link[i]=0,dlt[i]=0;
        For(i,1,M)
        {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            if (flag) flag=check(x,y,d);
        }
        if (flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>



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

  int n;
  cin>>n;
  cout<<n*n*n<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;

int sockets(int holes, int plug){
    return (holes * plug) - (plug-1);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a, b; // a = socket, b = required number.
	cin >> a >> b;

	int ans;
	// If there is more sockets than demand
	if (a > b) ans = b < 2 ? 0 : 1;
	else ans = b / a;

	while (sockets(a, ans) < b) {
		ans++;
	}

    // ==== Answer by prof https://atcoder.jp/contests/abc139/submissions?f.User=kmjp
    // int num = 0; // Initial, no need if theres only one plug
    // int cur = 1; // currently available plug
    // while(cur < b){ // cur needs to be more or equal to B
    //     num++;
    //     cur += a - 1; // add plug
    // }
    // cout << num << endl;
    // ====

	//cout << "Required number of power strips: \n";
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")
// -------------------</optimizations>--------------------
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define f first
#define s second
#define sz(x) ll(x.size())
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
 
typedef long long ll;
typedef long double ld; 
typedef pair<ll,ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
 
const ll mod = 1e9 + 7;
const int inf = 1e9 + 5;
const int N = 1005;
const int H = 20005;

int dp[H],a[N],b[N];

signed main(){
    fastio;
    int n,h,i,j,mx=-inf,ans=inf;
    cin>>h>>n;
    for(i=1;i<=n;++i){
        cin>>a[i]>>b[i];
        mx=max(mx,a[i]);
    }
    dp[0]=0;
    for(i=1;i<=h+mx;++i){
        dp[i]=inf;
    }
    for(i=1;i<=h+mx;++i){
        for(j=1;j<=n;++j){
            if(i>=a[j]){
                dp[i]=min(dp[i],b[j]+dp[i-a[j]]);
            }
        }
    }
    for(i=h;i<=h+mx;++i){
        ans=min(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 384
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()


int main() {
  double w, h, x, y;
  cin >> w >> h >> x >> y;
  double ans = w*h/2;
  int cnt = 0;
  if (x == w/2 && y == h/2) cnt = 1;
  printf("%.12lf %d\n", ans, cnt);
  return 0;
}

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

#define rep(i, k) for (ll(i) = 0; (i) < (k); ++(i))
#define rep3(i, k, n) for (ll(i) = (k); (i) < (n); ++(i))
#define mp(x, y) make_pair((x), (y))

using ll = long long;
using pll = pair<ll, ll>;

const ll MAX = (ll)1e18;
const int MOD = (int)1e9 + 7;

ll ryk[87] = {2, 1};

ll ans = 0;
int main() {
    rep3(i, 2, 87) { ryk[i] = ryk[i - 1] + ryk[i - 2]; }
    ll n;
    cin >> n;
    cout << ryk[n];
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc =  new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
       
    int[][] val = new int[N][3];
    int ax = 0, ay = 0, ah = 0;
    for(int i = 0; i < N; i++){
      val[i][0] = Integer.parseInt(sc.next());
      val[i][1] = Integer.parseInt(sc.next());
      val[i][2] = Integer.parseInt(sc.next());
      if(val[i][2] != 0){
        ax = val[i][0];
        ay = val[i][1];
        ah = val[i][2];
      }
    }
    
    for(int i = 0; i <= 100; i++){
      f:for(int j = 0; j <= 100; j++){
        int H = ah + Math.abs(ax-i) + Math.abs(ay-j);
        for(int k = 0; k < N; k++){
          int x = val[k][0], y = val[k][1], h = val[k][2];
          if(Math.max(H-Math.abs(x-i)-Math.abs(y-j), 0) == h){
            continue;
          }else{
            continue f;
          }
        }
        System.out.println(i+" "+j+" "+H);
        return;
      }
    }
  }
}

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

using ll = long long int;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

#define pi 3.14159265358979

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }




ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int ans = 0;
int N, M, Q;

template<typename T>
void showall(vector<T> v){
  rep(i, 0, v.size()){
    cout << v[i] << " ";
  }
  cout << endl;
}


void dfs(vector<ll> ls, vector<vector<ll>> way, int ){
  ll cur = ls.back();
  ls.pop_back();

  rep(i, 0, N){
    if(way[cur][i] != 0){

    }
  }

}

 
int main() {
  int X;
  cin >> X;
  bool flag = false;

  for (ll i = -120; i < 120; i++){
    for (ll j = -120; j < 120; j++){
      if(pow(i, 5) - pow(j, 5) == X) {
        cout << i << " " << j << endl;
        flag = true;
        break;
      }
    }
    if(flag) break;
  }
  
}

Measured memory_bytes: 4012
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define BR cout<<endl;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}

double expect(int x){
    double kitai,tem=0;
    for(int i=1;i<=x;i++){
        tem += i;
    }
    kitai = tem/x;
    cout << kitai << endl;
    return kitai;
    
}

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    
    int count = 0;
    int ans[100];
    rep(i,100)ans[i] = 0;

    for(int i = 0; i < 100 ; i++){
        if(a % (i + 1) == 0 and b % (i + 1) == 0){
            ans[i] = i + 1;
        }
    }

    sort(ans, ans + 100, greater<int>());

    cout << ans[k - 1] << endl;

    return 0;
}



Measured memory_bytes: 3576
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int N,K;
  cin >> N >> K;
  vector<pair<ll,int>> vec(N);
  for(int i=0;i<N;i++) cin >> vec[i].second >> vec[i].first;

  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());

  ll sum=0;
  map<int,int> mp;
  vector<ll> opt;
  for(int i=0;i<K;i++){
    if(mp[vec[i].second] == 0){
      mp[vec[i].second] = 1;
    }else{
      opt.push_back(vec[i].first);
    }
    sum+=vec[i].first;
  }

  int pos = opt.size()-1;
  ll sz = mp.size();
  ll ans = sum + sz*sz;
  for(int i=K;i<N;i++){
    if(sz == K) break;
    if(mp[vec[i].second]==1) continue;

    mp[vec[i].second] = 1;
    sz++;
    sum-=opt[pos];
    sum+=vec[i].first;
    pos--;

    ans=max(ans,sum+sz*sz);
  }
  cout << ans <<endl;
  return 0;
}


Measured memory_bytes: 5244
#![allow(non_snake_case, unused)]
use std::io::*;
use std::str::FromStr;
use std::collections::*;

fn main() {
    let cin = stdin();
    let mut sc = Scanner::new(cin.lock());

    let n: usize = sc.next();
    let m: usize = sc.next();
    
    let mut dsu = DSU::new(n);
    for i in 0..m {
	let a: usize = sc.next();
	let b: usize = sc.next();
	let a = a - 1;
	let b = b - 1;
	dsu.unite(a, b);
    }

    let mut ans = 0;
    for i in 0..n {
	ans = ans.max(dsu.get_size(i));
    }

    println!("{}", ans);
}

pub struct DSU {
    n: usize,
    rank: Vec<usize>,
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl DSU {
    pub fn new(n: usize) -> DSU {
	DSU {
	    n: n,
	    rank: vec![0; n],
	    size: vec![1; n],
	    parent: (0..n).collect()
	}
    }
    pub fn get_rep(&mut self, x: usize) -> usize {
	if self.parent[x] != x {
	    self.parent[x] = self.get_rep(self.parent[x]);
	}
	self.parent[x]
    }

    pub fn unite(&mut self, x: usize, y: usize) {
	let mut p1 = self.get_rep(x);
	let mut p2 = self.get_rep(y);
	if p1 != p2 {
	    if self.rank[p1] < self.rank[p2] {
		std::mem::swap(&mut p1, &mut p2);
	    }
	    if self.rank[p1] == self.rank[p2] {
		self.rank[p1] += 1;
	    }
	    self.parent[p2] = p1;
	    self.size[p1] += self.size[p2];
	}
    }

    pub fn get_size(&mut self, x: usize) -> usize {
	let rep = self.get_rep(x);
	self.size[rep]
    }

    pub fn is_same(&mut self, x: usize, y: usize) -> bool {
	self.get_rep(x) == self.get_rep(y)
    }
}


// Scanner
struct Scanner<R: std::io::Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
	Scanner { reader: reader }
    }

    fn read<T: FromStr> (&mut self) -> Option<T> {
	let token = self
	    .reader
	    .by_ref()
	    .bytes()
	    .map(|c| c.unwrap() as char)
	    .skip_while(|c| c.is_whitespace())
	    .take_while(|c| !c.is_whitespace())
	    .collect::<String>();
	if token.is_empty() {
	    None
	} else {
	    token.parse::<T>().ok()
	}
    }

    fn next<T: FromStr>(&mut self) -> T {
	if let Some(s) = self.read() {
	    s
	} else {
	    writeln!(stderr(), "Terminated with EOF").unwrap();
	    std::process::exit(0);
	}
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
	(0..n).map(|_| self.next()).collect()
    }

    fn char(&mut self) -> char {
	self.next::<String>().chars().next().unwrap()
    }
}


Measured memory_bytes: 6732
#!/usr/bin/env python3
import sys
from dataclasses import dataclass

def solve(N: int, a: "List[int]", b: "List[int]"):
    from collections import defaultdict, deque
    edges = defaultdict(list)
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)
    def f():
        visited = [None] * (N+1)
        que = deque([("f", 1), ("s", N)])
        while que:
            name, node = que.popleft()
            if visited[node]:
                continue
            visited[node] = name
            for n in edges[node]:
                if visited[n]:
                    continue
                que.append((name, n))
        return sum("f" == v for v in visited)
    return "Fennec" if f() > N // 2 else "Snuke"
            


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, a, b))

def test():
    import doctest
    doctest.testmod()

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


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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 1010;

LL n, m;

LL get1(LL n, LL m)
{
	LL res = 1e18;
	for (int i = 1; i < n; i ++ )
	{
		LL a = (n - i) / 2, b = n - i - a;
		LL area[] = {i * m, a * m, b * m};
		sort(area, area + 3);
		res = min(res, area[2] - area[0]);
	}
	return res;
}

LL get2(LL n, LL m)
{
	LL res = 1e18;
	for (int i = 1; i < n; i ++ )
	{
		LL a = m / 2, b = m - a, c = n - i;
		LL area[] = {i * m, a * c, b * c};
		sort(area, area + 3);
		res = min(res, area[2] - area[0]);
	}
	return res;
}

int main()
{
	cin >> n >> m;
	
	LL t1 = min(get1(n, m), get1(m, n));
	LL t2 = min(get2(n, m), get2(m, n));
	
	cout << min(t1, t2) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

int toid(int i,int j,vector<vector<int>> &id){
	if(i>j)
		swap(i, j);
	return id[i][j];
}

//深さ優先探索のテンプレ.デフォルトでは参照渡ししたsetに探索済みの頂点が格納される.
//graphは隣接リスト.vは探索開始地点.seenは空のセット
int dfs(vector<vector<int>> &graph, int v, vector<int> &dp,vector<int> &calc){
	if(dp[v] >= 0){
		if(calc[v] == 0)
			return -1;
		return dp[v];
	}
	dp[v] = 1;

	for (auto nxt:graph[v]){
		int temp = dfs(graph, nxt, dp, calc);
		if (temp == -1)
			return -1;
		dp[v] = max(dp[v], temp+1);
	}
	calc[v] = 1;
	return dp[v];
}

int main(){
	int n;
	cin >> n;
	vector<vector<int>> p(n, vector<int>(n - 1));
	vector<vector<int>> a(n, vector<int>(n - 1));
	rep(i,n){
		rep(j, n - 1){
			cin >> p[i][j];
			p[i][j]--;
		}
	}
	int v = 0;
	vector<vector<int>> id(n, vector<int>(n));
	rep(i, n)
	{
		rep(j,n){
			id[i][j] = v;
			v++;
		}
	}
	vector<vector<int>> graph(v);
	rep(i, n)
	{
		rep(j,n-1){
			a[i][j] = toid(i, p[i][j], id);
		}
		rep(j, n - 2)
		{
			graph[a[i][j]].push_back(a[i][j+1]);
		}
	}
	vector<int> dp(v, -1);
	vector<int> calc(v, 0);
	int ans = 0;
	rep(i,v){
		int temp = dfs(graph, i, dp, calc);
		if (temp == -1)
		{
			cout << -1 << endl;
			return 0;
		}
		ans = max(ans, temp);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 59136
n, m = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(m)]
w.sort(key=lambda x: x[1])
f = -float('inf')
ans = 0
for p, q in w:
    if p >= f:
        ans += 1
        f = q
print(ans)


Measured memory_bytes: 64600
INF = float("inf")

def Bellmanford(n, edges):
    dp = [INF] * n
    dp[0] = 0

    for i in range(n):  # たかだかn-1回ループ　n回目でまだ更新できたら負閉路がある
        for u, v, c in edges:
            if dp[u] != INF and dp[u] + c < dp[v]:
                dp[v] = dp[u] + c
                if i == n-1 and v == n-1:
                    return "inf"

    return -dp[n-1]


N, M = map(int, input().split())
E = []

for i in range(M):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1, -c))

ans = Bellmanford(N, E)

print(ans)

Measured memory_bytes: 9320
N = [int(i) for i in str(input())]
output = list()
num_op = 3

for i in range(2**num_op):
  ans = '{}'.format(str(N[0]))
  res = N[0]
  for j in range(num_op):
    if (i>>j) & 1:
      res += N[j+1]
      ans += '+{}'.format(str(N[j+1]))
    else:
      res -= N[j+1]
      ans += '-{}'.format(str(N[j+1]))
  if res == 7:
    print(ans+'=7')
    exit()
    

Measured memory_bytes: 3064
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

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

	map<int, lint> mod;
	for (int i = 0; i < N; i++) mod[A[i] % M]++;

	lint ans = mod[0] * (mod[0] + 1) / 2 - mod[0] * (mod[0] - 1) / 2;
	for (const auto &elem : mod) ans += elem.second * (elem.second - 1) / 2;

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 4608
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

int calc(int a,int b){
  if(b == 0) return 1;
  if(b%2 == 0){
    int d = calc(a,b/2);
    return (d*d)%MOD;
  }
  return (a*calc(a,b-1))%MOD;
}

int comb(int n,int r){
  int tmp = 1,ttmp = 1;
  for(int i = n;i >= n-r+1;i--) tmp = (tmp*i)%MOD;
  for(int i = 1;i <= r;i++) ttmp = (ttmp*i)%MOD;
  return (tmp*calc(ttmp,MOD-2))%MOD;
}

int powMod(int n, int p) {
  int res = 1;
  while (p) {
    if (p & 1) (res *= n) %= MOD;
    (n *= n) %= MOD;
    p >>= 1;
  }
  return res;
}
int invMod(int n) {
  return powMod(n, MOD - 2);
}

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

  cout << ((powMod(2, N)-(comb(N, A)+comb(N, B))-1+MOD)%MOD+MOD)%MOD << "\n";

  return 0;
}

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

using namespace std;

int main()
{

	string S;
	cin >> S;

	int year = atoi(S.substr(0, 4).c_str());
	int month = atoi(S.substr(5, 2).c_str());

	bool isHeisei = false;

	if (year < 2019) {
		isHeisei = true;
	} else if (year == 2019) {
		if (month <= 4) {
			isHeisei = true;
		}
	}

	if (isHeisei) {
		cout << "Heisei" << endl;
	} else {
		cout << "TBD" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) ll(i.size())
#define FOR(i, j, k, in) for (ll i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (ll i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif

template<class T> inline bool cmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool cmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MOD=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll MAXN=1e5+5;
const ll MAXLG=__lg(MAXN)+2;

ll n,k,a[MAXN];
bool dp[MAXN];
/********** Good Luck :) **********/
int main()
{
    IOS();
    cin >> k >> n;
    REP (i,k) {
        cin >> a[i];
    }

    dp[0] = 0;
    REP1 (i,n) {
        dp[i] = 0;
        REP (j,k) {
            if (i - a[j] >= 0) {
                dp[i] |= !dp[i-a[j]];
            }
        }
    }

    cout << (dp[n] ? "First" : "Second") << endl;
    return 0;
}


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

using namespace std;

int main(void){
	string str;

	getline(cin, str);

	for(int i=0;i<str.size();i++){
		if(str[i] >= 97 && str[i] <= 122){
			str[i] -= 32;
		}
	}

	cout << str << endl;
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
 #define int long long
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
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;};



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

  int n, k;
  cin >> n >> k;
  double res = 0;
  REP(i, 1, n + 1) {
    double now = 1.0;
    int tmp = i;
    while(tmp < k) {
      tmp *= 2;
      now /= 2;
    }
    res += now / n;
  }
  fcout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;


int main(){
  int n;
  scanf ("%d",&n);
  while(n){
    int k;
    vector<int> p(n);
    for(int t=0;t<n;t++){
      scanf ("%d",&p[t]);
    }
    sort(p.begin(),p.end());
    k=p[1]-p[0];
    for(int t=1;t<n-1;t++){
      if(k>(p[t+1]-p[t])){
        k=(p[t+1]-p[t]);
      }
    }
    printf("%d\n",k);
    scanf ("%d",&n);
  }
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
long double  cur[200005];
long double best,ans;
/*
int dp[20005][100][5];
string s;
int n,k;
int Rec(int index,int zeros,bool flag){
    if(zeros > k)   return 0;
    if(index == n)
        return zeros == k;
    if(dp[index][zeros][flag] + 1)    return dp[index][zeros][flag];
    int Res  =0;
    int Limit = flag?9:s[index];
    for(int i =0; i<=Limit; i++){
        Res+=Rec(index+1,zeros + (i!=0),!flag && i == s[index]?0:1);
    }
    return dp[index][zeros][flag] = Res;
}
*/
main()
{

    int n,k;
    cin>>n>>k;
    for(int i =0 ; i<n; i++){
        int x;
        cin>>x;
        ans = 0.0;
        for(long double j =1; j<=x; j++){
            ans+=j * (1/(x*1.0));
        }
        cur[i] = ans;
    }
    long double ans = 0.0;
    for(int i=0; i<k; i++){
        ans+=cur[i];
    }
    best = ans;
    for(int i =k; i<n; i++){
        ans-=cur[i-k];
        ans+=cur[i];
        best = max(best,ans);
    }
    cout<<fixed<<setprecision(10)<<best<<endl;





    return 0;
}


Measured memory_bytes: 3328
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=15;
const int maxm=15;
int cost[maxn],val[maxn][maxm],und[maxm];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>cost[i];
        for(int j=1;j<=m;j++)
            cin>>val[i][j];
    }
    int mask=(1<<n)-1,ans=INF;
    for(int sub=mask;sub;sub=(sub-1)&mask)
    {
        memset(und,0,sizeof(und));
        int spend=0;
        for(int i=0;i<n;i++)
            if(sub&(1<<i))
            {
                for(int j=1;j<=m;j++)
                    und[j]+=val[i+1][j];
                spend+=cost[i+1];
            }
        bool check=true;
        for(int i=1;i<=m;i++)
            if(und[i]<x)
            {
                check=false;
                break;
            }
        if(check) ans=min(ans,spend);
    }
    cout<<(ans==INF?-1:ans)<<'\n';
    return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
//#define ll long long
int n;
int t[200000];

int main(){
cin>>n;
rep(i,n)cin>>t[i];
int ans=0;

int cnt=0;
rep(i,n){
	if(t[i]==i+1){//should erase
		cnt++;
	}
	else{
		if(cnt>0){
			if(cnt==1)ans++;
			else ans+=cnt/2+cnt%2;
			cnt=0;
		}
	}
}

if(cnt==1)ans++;
if(cnt>1)ans+=cnt/2+cnt%2;

cout<<ans<<endl;
 
	return 0;
}

Measured memory_bytes: 640
import collections
N = int(input().strip())
Alst = []
for _ in range(N):
    u,k,*varray = map(int,input().strip().split(" "))
    Alst.append(varray)
D = [-1 for _ in range(N)]
D[0] = 0
Q = collections.deque()
Q.append(0)
while len(Q) > 0:
    cur = Q.popleft()
    for dst in range(N):
            if (dst+1 in Alst[cur]) and (D[dst] == -1):
                D[dst] = D[cur] + 1
                Q.append(dst)
for v in range(N):
    print(v+1,D[v])


Measured memory_bytes: 6028
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));

        }

        public void Solve(ConsoleInput cin)
        {
            var NY = cin.ReadIntArray(2);
            var isOk = false;
            var sen = 0;
            var gosen = 0;
            var man = 0;

            for (int i = 0; i <= NY[0]; i++)
            {
                
                for (int k = 0; k <= NY[0]-i; k++)
                {
                    var money = 10000 * i + 5000 * k + 1000 * (NY[0] - (i + k));
                    
                    if (money == NY[1])
                    {
                        sen = NY[0] - (i + k);
                        gosen = k;
                        man = i;
                        isOk = true;
                        break;
                    }
                }

                if (isOk) break;

            }

            if (isOk)
            {
                Console.WriteLine($"{man} {gosen} {sen}");
            }
            else
            {
                Console.WriteLine($"{-1} {-1} {-1}");
            }
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>

//Some constants don't work
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
#ifndef INT_MIN
#define INT_MIN -2147483648
#endif
//short hand tricks
typedef long long ll;

using namespace std;

int main(int argc, char * argv[]) {
    ios_base::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    //only care about first and last intger in term
    vector<ll> v(N+1,0);
    for(int i=1; i<=N; i++) {
        cin >> v[i];
        if(i>K) {
            if(v[i]>v[i-K]) {
                cout << "Yes\n";
            } else {
                cout << "No\n";
            }
        }
    }
    return 0;
}


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

int main() {
  string c1j, c2j;
  cin >> c1j >> c2j;
  
  if (c1j[0] == c2j[2] && c1j[1] == c2j[1] && c1j[2] == c2j[0])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}  

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

int main(){
    string s;
    cin>>s;

    if(s=="A")cout<<"T"<<endl;
    else if(s=="C")cout<<"G"<<endl;
    else if(s=="G")cout<<"C"<<endl;
    else if(s=="T")cout<<"A"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s1, s2, s3, input;
  cin >> input;
  s1 = input / 100;
  s2 = input % 100 / 10;
  s3 = input % 100 % 10 / 1;
  cout << s1 + s2 + s3 << endl;
}

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

int n;
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	int a[n];
	REP(i, 0, n) cin >> a[i];
	sort(a, a + n);
	cout << a[n - 1] - a[0];
}

Measured memory_bytes: 256
n,x,y=map(int,input().split())
ans=[0]*n
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[int(min(j-i,abs(x-i)+abs(y-j)+1))]+=1
for i in range(1,n):
    print(ans[i])

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

int main() {
  
  long long int N;
  cin >> N;
  long long int b, c, d, e;
  long long int count = 0;
  
  long long int A[N];
  for(long long int i = 0; i < N; i++){
    cin >> A[i];
  }
  
  for(long long int i = 0; i < N - 1; i++){
    c = A[i];
    d = A[i + 1];
    if(c > d){
      e = c - d;
      count = count + e;
      A[i + 1] = A[i + 1] + e;
    }
  }
  
  cout << count;
  
  return 0;
}


Measured memory_bytes: 5156
import java.awt.*;
import java.awt.geom.*;
import java.io.*;
import java.util.*;
class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int m = sc.nextInt();
			if(m == 0) break;
			int[] xm = new int[m];
			int[] ym = new int[m];
			for(int i = 0; i < m; i++) {
				xm[i] = sc.nextInt();
				ym[i] = sc.nextInt();
			}
			
			int n = sc.nextInt();
			int[] xn = new int[n];
			int[] yn = new int[n];
			for(int i = 0; i < n; i++) {
				xn[i] = sc.nextInt();
				yn[i] = sc.nextInt();
			}
			CON:for(int i = 0; i < n; i++) {
				int mox = xn[i] - xm[0];
				int moy = yn[i] - ym[0];
				for(int j = 0; j < m; j++) {
					boolean ok = false;
					for(int k = 0; k < n; k++) {
						if(xn[k] == xm[j]+mox && yn[k] == ym[j]+moy) {
							ok = true;
							break;
						}
					}
					if(!ok) continue CON;
				}
				
				System.out.println(mox + " " + moy);
				break;
				
			}
			
			
		}
	}


}

Measured memory_bytes: 29720