akhauriyash/Code-Regression huggingface dataset:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int A = in.nextInt();
            int B = in.nextInt();
            int Q = in.nextInt();

            long[] s = new long[A + 2];
            s[0] = (long) -1e11;
            s[A + 1] = (long) 1e11;
            for (int i = 0; i < A; i++) {
                s[i + 1] = in.nextLong();
            }
            long[] t = new long[B + 2];
            t[0] = (long) -1e11;
            t[B + 1] = (long) 1e11;
            for (int i = 0; i < B; i++) {
                t[i + 1] = in.nextLong();
            }

            for (int i = 0; i < Q; i++) {
                long x = in.nextLong();

                long[] s2 = search(s, x);
                long[] t2 = search(t, x);

                long ans = (Math.abs(Math.min(s2[0], t2[0]) - x));
                ans = Math.min(ans, Math.abs(Math.max(s2[1], t2[1]) - x));
                ans = Math.min(ans, Math.abs(s2[0] - x) * 2 + Math.abs(t2[1] - x));
                ans = Math.min(ans, Math.abs(s2[1] - x) * 2 + Math.abs(t2[0] - x));
                ans = Math.min(ans, Math.abs(t2[0] - x) * 2 + Math.abs(s2[1] - x));
                ans = Math.min(ans, Math.abs(t2[1] - x) * 2 + Math.abs(s2[0] - x));
                out.println(ans);
            }
        }

        private long[] search(long[] xs, long v) {
            int l = 0, r = xs.length - 1;
            while (l < r) {
                int index = (r + l) / 2;
                long temp = xs[index];
                if (index < r && v < temp) {
                    r = index;
                } else if (l < index && temp < v) {
                    l = index;
                } else if (temp == v) {
                    l = r = index;
                } else {
                    break;
                }
            }
            long[] ret = {xs[l], xs[r]};
//        if (v < ret[0]) {
//            ret[0] = (long)-1e11;
//        }
//        if (ret[1] < v) {
//            ret[1] = (long)1e11;
//        }
            return ret;
        }

    }
}



Measured memory_bytes: 95876
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n, a[N];
vector <pair<int,int> > v;
vector <pair<int,int> >::iterator it;
inline bool check(int k){
	v.clear();
	for(int i=1; i<=n; ++i){
		if(a[i]>a[i-1])v.insert(v.end(),make_pair(1,a[i]-a[i-1]));
		else if(a[i]<a[i-1]){
			int x=0,j; it=v.begin();
			for(j=0; j<v.size(); ++j, ++it){
				x+=v[j].second;
				if(x>=a[i]){
					v[j].second-=x-a[i];
					break;
				}
			}
			++it; if(it!=v.end())v.erase(it,v.end()); --it;
			for(j=v.size()-1; ~j; --j,--it){
				if(v[j].first==k)v[j].first=1;
				else{
					int tmp=v[j].first;
					if(v[j].second>1)v[j].second--,++it; else v.erase(it);
					v.insert(it,make_pair(tmp+1,1)); break;
				}
			}
			if(j==-1)return 0;
		}else{
			int j=v.size()-1; it=--v.end();
			for(; ~j; --j,--it){
				if(v[j].first==k)v[j].first=1;
				else{
					int tmp=v[j].first;
					if(v[j].second>1)v[j].second--,++it; else v.erase(it);
					v.insert(it,make_pair(tmp+1,1)); break;
				}
			}
			if(j==-1)return 0;
		}
	}
	return 1;
}
int main(){
	scanf("%d",&n); for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
	int l=1, r=n, tmp=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))tmp=r=mid;
		else l=mid+1;
	}
	printf("%d", tmp);
	return 0;
}

Measured memory_bytes: 3188
N = int(input())
P = [0]*N
for i in range(N):
	P[i] = int(input())

cnt = [0]*(N+1)
for i in range(N):
	cnt[P[i]] = cnt[P[i]-1] + 1

a = 0
for i in range(N):
	a = max(a, cnt[i+1])
print(N - a)
	


Measured memory_bytes: 18804
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

int main() {
    int H, N;
    cin >> H >> N;
    
    vector<pair<long long int, long long int> > AB(N+1);
    for(int n=1; n<=N; n++) {
        cin >> AB[n].first >> AB[n].second;
    }
    
    vector<long long int> memo(H+1, -1);
    memo[0]=0;
    for(int n=1; n<=N; n++) {
        for(int h=0; h<=H; h++) {
            if(h<AB[n].first) {
                if(memo[h]!=-1) {
                    memo[h] = min(memo[h], AB[n].second);
                } else {
                    memo[h] = AB[n].second;
                }
            } else {
                if(memo[h]!=-1) {
                    memo[h] = min(memo[h], memo[h-AB[n].first]+AB[n].second);
                } else {
                    memo[h] = memo[h-AB[n].first]+AB[n].second;
                }
            }
            // cout << memo[h] << " ";
        }
        // cout << endl;
    }

    cout << memo[H] << endl;


    return 0;
    
}

Measured memory_bytes: 384
#include <iostream>
#include <set>
#include <map>
using namespace std;

int getValue(int x){
	if(x <= 3)
		return x;
	else if(x == 4)
		return 5;
	else
		return x + 2;
	
		
}
int main() {
	long long n;
	while(cin >> n && n){
		int ans[100] = {0}, c = 0;
		while(n > 0){
			ans[c++] = getValue(n % 8);
			n /= 8;
		}
		for(int i = c - 1; i >= 0; --i)
			cout << ans[i];
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 1001
#define M 1001

char X[N];
char Y[M];
int dp[N][M];


int _max(a, b)
{
    return a > b ? a : b;
}

void init(int n, int m)
{
    int i, j;
    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= m; j++)
        {
            dp[i][j] = -1;
        }
    }
}

int LCS(int i, int j)
{
    if (dp[i][j] != -1)
    {
        return dp[i][j];
    }
    if (i == 0 || j == 0)
    {
        dp[i][j] = 0;
    }
    else if (X[i - 1] == Y[j - 1])
    {
        dp[i][j] = LCS(i - 1, j - 1) + 1;
    }
    else
    {
        dp[i][j] = _max(LCS(i, j - 1), LCS(i - 1, j));
    }
    return dp[i][j];
}


int main(void)
{
    int q;
    int lx, ly;
    int lcs;

    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        scanf("%s %s", X, Y);
        lx = strlen(X);
        ly = strlen(Y);
        init(lx, ly);
        lcs = LCS(lx, ly);
        printf("%d\n", lcs);
    }

    return 0;
}


Measured memory_bytes: 5696
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <set>
#include <queue>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <map>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace gnu_pbds;

#define F first
#define S second
#define ll long long
#define pb push_back
#define ppb pop_back
#define pii pair<int, int>
#define piii pair<int, pii>
#define __ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define watch(x) cout << (#x) << " is " << (x) << endl
//#define int long long
// #define ld long double


const int N = 1e5 + 20, mod = 1e9 + 7, inf = 2e9 + 9;
const ll INF = 1e18 + 20;

int n, k, a[N], b[N], c[N], dp[N][4];

signed main() { __
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    cin>>n;
    for(int i = 1; i <= n; i++) {
        cin>>a[i]>>b[i]>>c[i];
    }
    dp[1][1] = a[1];
    dp[1][2] = b[1];
    dp[1][3] = c[1];
    for(int i = 2; i <= n; i++) {
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + a[i];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + b[i];
        dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + c[i];
    }
    cout<<max(max(dp[n][1], dp[n][2]), dp[n][3]);
    return 0;
}


Measured memory_bytes: 2944
N = int(input())
for i in range(N):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    x2 -= x1; y2 -= y1
    x4 -= x3; y4 -= y3
    print("YES" if abs(x2*y4 - x4*y2) < 1e-10 else "NO")



Measured memory_bytes: 5612
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x)    // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    for (ll i = 0; i < 5; i++)
    {
        ll t;
        cin >> t;
        if (t == 0)
        {
            cout << i + 1 << endl;
            exit(0);
        }
    }
}

Measured memory_bytes: 3588
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
ll n,ch[100000],q,k,lo[100000];
vector<P> s[100000];
void dfs(ll x,ll y){
    for(auto xx:s[x]){
        if(ch[xx.first]==0){
            lo[xx.first]=y+xx.second;
            ch[xx.first]=1;
            dfs(xx.first,y+xx.second);
        }
    }
    return ;
}
int main(void){
    cin>>n;
    
    for(int i=0;i<n-1;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        s[a].push_back(P(b,c));
        s[b].push_back(P(a,c));
    }
    cin>>q>>k;
    k--;
    ch[k]=1;
    dfs(k,0);
    
    /*for(int i=0;i<5;i++){
        cout<<lo[i]<<"W"<<k<<endl;
    }*/
    
    for(int i=0;i<q;i++){
        ll a,b;
        cin>>a>>b;
        cout<<lo[a-1]+lo[b-1]<<endl;
    }
}


Measured memory_bytes: 13568
//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;
 
////////////////いろいろあるよ//////////////////////////////////
int main(){
	int N,K;
  	cin >> N >> K;
  	int sunukes[N];
  
  	REP(i,N)sunukes[i] = 0;
  
  	REP(i,N){
      	int a;
    	cin >> a;
      
      	REP(j,a){
        	int piyo;
          	cin >> piyo;
          	sunukes[piyo - 1]++;
        }
    }
    int ans = 0;
  	REP(i,N){if(sunukes[i]==0)ans++;}
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
//#define INF (1LL<<31)-1
//#define MOD 998244353
#define MOD 1000000007

int main(){
    ll n;
    cin>>n;
    ll ans=0;
    rep(i,1,n+1){
        if((i%3)&&(i%5))ans+=i;
    }
    cout<<ans;
    
}

Measured memory_bytes: 3636
use proconio::input;
use std::io::{stdout, BufWriter, Write};

fn main() {
    input! {
        x: usize,
        y: usize,
    }
    let out = stdout();
    let mut out = BufWriter::new(out.lock());

    for i in 0..x + 1 {
        if i * 2 + (x - i) * 4 == y {
            writeln!(out, "{}", "Yes");
            return;
        }
    }
    writeln!(out, "{}", "No");
}

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

#define debug(x) cout << #x << ": " << (x) << endl
#define For(i, j, k) for (int i = j; i <= k; ++ i)
#define Forr(i, j, k) for (int i = j; i >= k; -- i)

using namespace std;

inline void File() {
	freopen("D.in", "r", stdin);
	freopen("D.out", "w", stdout);
}

const int N = 2e5 + 10, mod = 1e9 + 7;
int fac[N], inv[N], n, m, a, b;

inline int qpow(int a, int b) {
	static int res;
	for (res = 1; b; b >>= 1, a = 1ll * a * a % mod)
		if (b & 1) res = 1ll * res * a % mod;
	return res;
}

inline void Init(int n) {
	fac[0] = 1; For(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	Forr(i, n - 1, 0) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

inline int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

inline int add(int a, int b) { return a + b > mod ? a + b - mod : a + b; }

int main() {
	 Init(N - 5);
	
	cin >> n >> m >> a >> b;

	int ans = 0, x = n - a, y = b + 1;

	for (; x > 0 && y <= m; -- x, ++ y) 
		ans = add(ans, 1ll * C(x + y - 2, x - 1) * C(n + m - x - y, n - x) % mod);

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


Measured memory_bytes: 1792
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

using ll = long long;
using P = pair<int, int>;

bool memo[100001];

int main()
{
    int N;
    cin >> N;
    int a[100001];
    for(int i = 1; i <= N; ++i) cin >> a[i];
    int index = 1;
    int cnt = 1;
    memo[1] = true;

    while(true){
        if(memo[a[index]] == true){
            cnt = -1;
            break;
        }
        if(a[index] == 2)
            break;
        memo[a[index]] = true;
        index = a[index];
        cnt++;
    }
    cout << cnt << endl;

    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (ll i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll h[100005],dp[100005];
ll N;	

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N;
	FOR(i,0,N)	cin>>h[i];
	
	dp[0]=0;
	FOR(i,1,N)	dp[i]=INF;
	
	FOR(i,1,N){
		chmin(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
		if(i>1)	chmin(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
	}
	
	cout<<dp[N-1]<<endl;

    return 0;
}




Measured memory_bytes: 1792
#include<iostream>

using namespace std;

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

	int num = 1;
	for (int i = 0; i < N; i++) {
		if (num * 2 < num + K) {
			num = num * 2;
		}
		else {
			num = num + K;
		}
	}

	cout << num << endl;

}
	


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
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;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    int mx = 1000010;
    vector<int> b(mx);
    rep(i,n) {
        if (b[a[i]] != 0) {
            b[a[i]]++;
        } else {
            for (int j = a[i]; j <= mx; j+=a[i]) {
                b[j]++;
            }
        }
    }
    int ans = 0;
    rep(i,n) {
        if (b[a[i]] == 1) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8012
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    s=chomp(readline())
    n=length(s)
    move=[0 for i in 1:n]
    res=0
    for i in n:-1:1
        if s[i]=='L'
            res=0
        else
            res+=1
            move[i]=res
        end
    end
    for i in 1:n
        if s[i]=='R'
            res=0
        else
            res-=1
            move[i]=res
        end
    end
    ans=[0 for i in 1:n]
    for i in 1:n
        ans[i+move[i]+move[i]%2*-1]+=1
    end
    println(join(ans," "))
end
main()

Measured memory_bytes: 166824
#include <bits/stdc++.h>
#define ll long long
#define MAXN 101
#define MAXW 100001

using namespace std;

ll mat[MAXN][MAXW];
vector<int> weights(MAXN);
vector<ll> value(MAXN);

int main() {
	int n, W;
	cin >> n >> W;
	for(int i = 1; i <= n; i++)
		cin >> weights[i] >> value[i];

	for(int i = 1; i <= W; i++) {
		for(int j = 1; j <= n; j++) {
			if(i < weights[j])
                mat[j][i] = mat[j - 1][i];
			else
				mat[j][i] = max(mat[j - 1][i], value[j] + mat[j - 1][i - weights[j]]);
		}
	}

	cout << mat[n][W];
}


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

int calc(int x) {
  if (x % 2 == 0) return x/2;
  else return 3*x + 1;
}

int main(int argc, char const *argv[]) {
  int s;
  std::cin >> s;
  
  vector<int> v;
  v.push_back(0);
  v.push_back(s);
  int next = s;
  
  while (true) {
    next = calc(next);
    auto ret = find(v.begin(), v.end(), next);
    if (ret == v.end()) {
      v.push_back(next);
    } else {
      // std::cout << distance(v.begin(), ret) << '\n';
      auto ret_next = find(ret+1, v.end(), next);
      std::cout << distance(v.begin(), ret_next) << '\n';

      exit(0);
    }
  }

}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
char a[105][105];
bool b[105][105];
int m,n;
int dire[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y)
{
    b[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int x1=x+dire[i][0];
        int y1=y+dire[i][1];
        if(x1>=0 && x1<m && y1>=0 && y1<n && !b[x1][y1] &&a[x1][y1]==a[x][y])
        {
            dfs(x1,y1);
        }
    }
}
int main()
{
    int ans;
    while(1)
    {
        scanf("%d%d",&m,&n);
        if(m==0||n==0)
            return 0;
        ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                b[i][j]=false;
            }
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(!b[i][j])
                {
                    dfs(i,j);
                    ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 1848
N=int(input())
import sys
input=sys.stdin.readline
S=input()
C_stack=[]
D=[0]*(N+1)
M=[0]*(N+1)
DM=[0]*(N+1)
m=0
for i in range(1,N+1):
  if S[i-1]=="D":
    D[i]=D[i-1]+1
  else:
    D[i]=D[i-1]
  if S[i-1]=="C":
    C_stack.append(i)
  if S[i-1]=="M":
    DM[i]=DM[i-1]+D[i-1]
    M[i]=M[i-1]+1
  else:
    DM[i]=DM[i-1]
    M[i]=M[i-1]

Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  for c in C_stack:
    ans+=DM[c]-DM[max(0,c-k)]-D[max(0,c-k)]*(M[c]-M[max(0,c-k)])
  print(ans)
    

Measured memory_bytes: 118252
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 55, M = N * N;

struct Edge{
    int a, b;
}e[M];

int n, m;

int p[N];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < m; i ++)  scanf("%d%d", &e[i].a, &e[i].b);
    
    int res = 0;
    for(int k = 0; k < m; k ++)
    {
        for(int i = 1; i <= n; i ++)  p[i] = i;
        
        int cnt = 0;
        for(int i = 0; i < m; i ++)
        {
            if(i == k)  continue;
            
            int a = e[i].a, b = e[i].b;
            int pa = find(a),  pb = find(b);
            if(pa != pb)
            {
                p[pa] = pb;
                cnt ++;
            }
        }
        if(cnt < n - 1)  res ++;
    }
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define bg begin()
#define en end()

using namespace std;

typedef long long ll;

int ans, N;
int p[100005];

int main() {
  scanf("%d", &N);
  rep(i, 1, N+1) scanf("%d", &p[i]);
  
  rep (i, 1, N) {
    
    if (p[i] == i && p[i+1] == i+1) {
      swap(p[i], p[i+1]);
      ans++;
    }
  }
      rep(i, 1, N+1) {
      if (p[i] == i) ans++;
    }
  printf("%d\n", ans);

}

Measured memory_bytes: 640
/*PM　問題１１*/
#include <stdio.h>
int main()
{


	int x = 0;
	int y = 0;
	int temp = 0;

	while (1)
	{
		scanf("%d %d", &x, &y);

		if (x > y)
		{
			if (x == 0 && y == 0) break;
			temp = x;
			x = y;
			y = temp;
			printf("%d %d\n", x, y);
		}
		else
		{
			if (x == 0 && y == 0) break;
			printf("%d %d\n", x, y);
		}
	}

	return 0;
}



Measured memory_bytes: 2040
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using static System.Math;
using System.Linq;
using static System.Array;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            //var N = long.Parse(Console.ReadLine());
            Solve();

        }
        static void Solve()
        {
            //var A = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            var N = long.Parse(Console.ReadLine());
            //var S = Console.ReadLine();


            Console.WriteLine(N == 1?0:1);
        }
    }

    
}


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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

const long long MOD = 1000000007;
const int MAX_N = 100000;
int n;
vi g[MAX_N];
ll memo[MAX_N][2];
bool vis[MAX_N][2];

// c = 0: white
ll dfs(int u, int p, int c)
{
  if (vis[u][c]) return memo[u][c];

  ll res = 1;
  for (int v : g[u]) {
    if (v == p) continue;
    ll temp = dfs(v,u,1-c);
    if (c == 0)
      temp = (temp + dfs(v,u,0)) % MOD;
    res = (res * temp) % MOD;
  }

  vis[u][c] = true;
  return memo[u][c] = res;
}

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  cin >> n;
  forn(i,n-1) {
    int x,y;
    cin >> x >> y;
    x--,y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }

  cout << (dfs(0,-1,0) + dfs(0,-1,1)) % MOD << endl;

  return 0;
}


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

using namespace std;

typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define sz size()

const double EPS = 1e-10;
const int INF = 100000000;

int main(){
    int l[10]={},r[10]={};
    double a,b;
    while(cin>>a>>b){
        if(a>=1.1)l[0]++;
        else if(a>=0.6)l[1]++;
        else if(a>=0.2)l[2]++;
        else l[3]++;

        if(b>=1.1)r[0]++;
        else if(b>=0.6)r[1]++;
        else if(b>=0.2)r[2]++;
        else r[3]++;

    }

    
    rep(i,4){
        cout<<l[i]<<" "<<r[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1224
#問題文
#整数aと、英小文字からなる文字列sが入力されます。
#aが3200以上ならsと出力し、a が3200未満なら red と出力するプログラムを書いてください。
#
#制約
#2800≤a<5000
#sは長さ1以上10以下の文字列である。
#sの各文字は英小文字である。

a = int(input())
s = input()

if(a<3200): print('red')
else: print(s)


Measured memory_bytes: 2940
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define int long long

void solve() {
	int h, w; cin >> h >> w;
    rep(i, h) {
        rep(j, w) {
            string s; cin >> s;
            if(s == "snuke") {
                cout << (char)('A' + j)<< i + 1 << endl;
            }
        }
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

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

int main(){
    int N, x[100], y[100], h[100];
    int xout, yout, hout;
    int xtemp, ytemp , htemp;

    cin >> N;
    for (int i=0; i < N; i++){
        cin >> x[i] >> y [i] >> h[i];
        if(h[i] > 0 ){
            xtemp = x[i];
            ytemp = y[i];
            htemp = h[i];
        }
    }

int hhantei;
int htop, xtop, ytop;
bool flag;
for(int i = 0; i <= 100 ; i++){
    for(int j = 0 ; j <= 100 ; j ++){
        flag = true;
        hhantei = htemp + abs(i - xtemp) + abs(j - ytemp);
        hhantei = max(hhantei, 0);
        for(int k = 0 ; k < N ; k ++){
            if(h[k] != max(hhantei - abs(i - x[k]) - abs(j - y[k]),0)){
                flag = false;
            }
        }
        if(flag == true){
            xtop = i;
            ytop = j;
            htop = hhantei;
        }
    }
}


    cout << xtop << ' ' << ytop << ' ' << htop << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1007;
int n,ans,vis[N];
vector<pii > q;
struct node
{
    int x,y;
}a[N];
void judge()
{
    int cnt=0;
    for(int i=0; i<q.size(); i++)
    {
        int x1=a[q[i].second].x - a[q[i].first].x;
        int y1=a[q[i].second].y - a[q[i].first].y;
        for(int j=0; j<q.size(); j++)
        {
            if(i!=j)
            {
                int x2=a[q[j].second].x - a[q[j].first].x;
                int y2=a[q[j].second].y - a[q[j].first].y;
                if(x2*y1 == x1*y2) cnt++;
            }
        }
    }
    ans=max(ans, cnt);
}
void dfs(int pos)
{
    if(pos==n+1)
    {
        judge();
        return ;
    }
    if(vis[pos]) dfs(pos+1);
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(vis[i] || i==pos) continue;
            q.push_back(make_pair(pos, i));
            vis[i]=vis[pos]=1;
            dfs(pos+1);
            q.pop_back();
            vis[i]=vis[pos]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
    dfs(1);
    printf("%d\n",ans/2);
    return 0;
}



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

 int main(){
  string O,E;
  cin >> O >> E;
  E.push_back(' ');
  string S;
  for(int i = 0;i<O.size();i++){
    S.push_back(O[i]);
    S.push_back(E[i]);
  }
   cout << S << endl;

 }


Measured memory_bytes: 256
# import sys
# import math #sqrt
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import permutations #順列生成
# import collections # deque
# from operator import itemgetter
# from fractions import Fraction

mod = int(1e9+7)
INF = 1<<29
lINF = 1<<35

def readInt():
    return list(map(int,input().split()))

def main():
    n = int(input())
    x = int(n**0.5)**2
    print(x)
    return

if __name__=='__main__':
    main()

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

const int MAX_N = 100010;
const int INF = 1001001001;

int dp[MAX_N];

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < MAX_N; i++)
        dp[i] = INF;

    dp[0] = 0;

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j *= 6)
            dp[i] = min(dp[i], dp[i - j] + 1);
        for (int j = 1; j <= i; j *= 9)
            dp[i] = min(dp[i], dp[i - j] + 1);
    }
    cout << dp[N] << endl;
    return 0;
}

Measured memory_bytes: 640
from heapq import heappush, heappop

N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [1 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if self.r[px] < self.r[py]:
            self.r[py] += self.r[px]
            self.p[px] = py
        else:
            self.r[px] += self.r[py]
            self.p[py] = px

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.r[self.find(x)]


# Mが奇数ならば構築不可
# Mが偶数ならば適当に木を構築し、深さの大きい頂点を端点とする辺から向きを決めていく
utf = UnionFindTree(N)
T = [{} for _ in range(N + 1)]
for a, b in zip(A, B):
    if not utf.same(a, b):
        T[a][b] = 1
        T[b][a] = 1
        utf.union(a, b)
INF = 10**9


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


r = dijkstra(T, 1)
p = [0, 1] + [
    min(T[i], key=lambda j: r[j])
    for i in range(2, N + 1)
]
dp = [0 for _ in range(N + 1)]
for a, b in zip(A, B):
    if b not in T[a]:
        dp[a] += 1
for i in sorted(
        range(1, N + 1),
        key=lambda j: r[j],
        reverse=True
):
    dp[i] += sum(
        (dp[j] + 1) % 2
        for j in T[i]
        if j != p[i]
    )
ans = (
    -1 if M % 2 == 1 else
    '\n'.join(
        '{} {}'.format(a, b)
        if b not in T[a] or (
            dp[a] % 2 == 1 and p[a] == b or
            dp[b] % 2 == 0 and p[b] == a
        ) else
        '{} {}'.format(b, a)
        for a, b in zip(A, B)
    )
)

print(ans)


Measured memory_bytes: 58064
n = int(input())

ans = 0
for i in range(1, n+1):
    w = 0
    if i % 2 == 0:
        continue
    for j in range(1, i+1):
        if i % j == 0:
            w += 1
    if w == 8:
        ans += 1

print(ans)

Measured memory_bytes: 2940
#include <iostream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <numeric>
#include <cmath>
#include <cctype>

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,x); REP(i,sizeof(a)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

#define umap unordered_map
//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}


int main(){
  ll N,M; cin>>N>>M;
  ll cumu=0,a;
  map<ll,ll> mp;
  vector<ll> v;
  
  REP(i,N+1){
    if(i==0){
      cumu = 0;
    }else{
      cin >> a;
    }
    cumu += a;
    cumu %= M;
    ++mp[cumu];
    if(mp[cumu]==2){ v.push_back(cumu); }
  }
  ll ans = 0;
  for(ll amari:v){
    ll x = mp[amari];
    ans += x*(x-1)/2;
  }
  cout << ans <<"\n";
  
}

Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr ll MOD = 1e9+7;

ll pw(ll base, ll exp) {
	ll res = 1;
	while (exp) {
		if (exp & 1) (res *= base) %= MOD;
		exp >>= 1, (base *= base) %= MOD;
	}
	return res;
}

ll inv(ll x) { return pw(x, MOD - 2); }

ll A[100001], P[100001];

int main() {
    if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0);

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

    for (int i = 0; i < N; ++i) (P[i+1] = inv(i+1)+P[i]) %= MOD;

    ll ans = 0;
    for (int i = 0; i < N; ++i) (ans += A[i]*(P[i+1]+P[N-i] - 1) % MOD) %= MOD;
    for (int i = 0; i < N; ++i) (ans *= (i+1)) %= MOD;
    cout << ans;
}

Measured memory_bytes: 5152
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define begin fuck
#define end cao

const int N=123;

long long v[N], t[N];
long long begin[N], end[N];
int n;
int main(void) {
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>t[i];
	}
	memset(begin, 0x3f, sizeof begin);
	memset(end, 0x3f, sizeof end);
	for (int i=1; i<=n; i++) {
		cin>>v[i];
		begin[i]=min(begin[i], v[i]);
		end[i]=min(end[i], v[i]);
	}
	end[0]=0;
	begin[n+1]=0;
	for (int i=n; i; i--) {
		end[i]=min(end[i], begin[i+1]);
		begin[i]=min(begin[i], end[i]+t[i]);
	}
	double ans=0;
	for (int i=1; i<=n; i++) {
		begin[i]=min(end[i-1], begin[i]);
		end[i]=min(end[i], begin[i]+t[i]);
	}
	for (int i=1; i<=n; i++) {
	//	debug(begin[i]); debug(end[i]); debug(v[i]); debug(t[i]);
		double high=(begin[i]+end[i]+t[i])*0.5;
	//	debug(high);
		double x=high-begin[i];
		double s1=(begin[i]+high)*x*0.5;
		double s2=(end[i]+high)*(t[i]-x)*0.5;
		double s=s1+s2;
	//	debug(s);
		if (high>v[i]) {
			double x1=v[i]-begin[i];
			double x2=end[i]+t[i]-v[i];
		//	debug(x1); debug(x2);
			double di=x2-x1;
			double gao=high-v[i];
		//	debug(di); debug(gao);
		//	debug(di*gao*0.5);
			s-=di*gao*0.5;
		}
		ans+=s;
	}
			
	printf("%.10lf", ans);
		
	return 0;
	
}

Measured memory_bytes: 256
n,k,q = map(int,input().split())
a = [0]*q
for i in range(q):
    a[i] = int(input())

points = [0]*n
for i in range(q):
    points[a[i]-1] += 1

for i in range(n):
    if k-q+points[i] > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 51544
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define co(n) cout<<n<<endl
using namespace std;

int main(){
  int a,b,c=0,d=0,e,n,m,x,y;
  cin>>n>>x>>a;
  double inf=2e200;
  double xx[n],yy[n];
  rep(i,0,n){
    cin>>xx[i];
    yy[i]=abs(x-xx[i]*0.006-a);
  }
  c++;
  rep(i,0,n){
    if(inf>yy[i]){
      inf=yy[i];
      a=i+1;
    }
  }
  co(a);
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define fastread ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll mod=1000000007;

using namespace std;

int main(){



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

    map<ll,ll> mp;

    ll sum=0;
    ll cnt=0;
    for(int i=0;i<n;i++){
    	sum+=arr[i];
    	if(sum==0)
    		cnt++;
    	cnt+=mp[sum];
    	mp[sum]++;
    }

    cout<<cnt;

  return 0;
}



Measured memory_bytes: 14336
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
const ll mod=1e9+7;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    vector<pair<int,int>>v;
    for(int i=0;i<s.length();i++){
        int cnt1=0;
        int cnt2=0;
        while(s[i]=='R'){cnt1++;i++;}
        while(s[i]=='L'){cnt2++;i++;}
        if((cnt1+cnt2)%2==0){v.push_back({(cnt1+cnt2)/2,(cnt1+cnt2)/2});i--;continue;}
        if(cnt1>=cnt2){
            if((cnt1-1)%2==0)v.push_back({1+(cnt1+cnt2)/2,(cnt1+cnt2)/2});
            else{v.push_back({(cnt1+cnt2)/2,1+(cnt1+cnt2)/2});}
        }
        else{
            if((cnt2-1)%2==0)v.push_back({(cnt1+cnt2)/2,1+(cnt1+cnt2)/2});
            else{v.push_back({1+(cnt1+cnt2)/2,(cnt1+cnt2)/2});}
        }
        i--;
    }
    vector<int>res;
    int cnt=0;
    for(int i=0;i<s.length()-1;i++){
        if((s[i]=='R')&&(s[i+1]=='L')){
            res.push_back(v[cnt].first);
            res.push_back(v[cnt].second);
            cnt++;
            i++;
        }
        else{
            res.push_back(0);
        }
    }

    for(int i=0;i<s.length();i++){
        cout<<res[i]<<" ";
    }
    return 0;
    }


Measured memory_bytes: 1480
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())


int n;
int k;
int a[100];

bool dp[100001][2];


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

	
	cin >> n >> k;
	rep(i, n)cin >> a[i];

	rep(i,k+1) rep(j,2){
		bool ret = false;
		rep(x,n) {
			if (i >= a[x] && !dp[i-a[x]][j^1]) {
				ret = true;
				break;
			}
		}
		dp[i][j] = ret;
	}


	cout << (dp[k][0] ? "First" : "Second") << endl;



	return 0;
}


Measured memory_bytes: 512
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		solver();
	}

	void solver() {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		int K = sc.nextInt();
		int T = sc.nextInt();
		ArrayList<Long> a = new ArrayList<>();
		for (int i = 0; i < T; i++) {
			a.add((sc.nextLong() << 32 | i));
		}

		Collections.sort(a);
		int ans = 0;
		int pre = -1;
		for (int i = 0; i < K; i++) {
			Collections.sort(a);
			if ((int)(a.get(a.size() - 1)-0) == pre) {
				if (a.size() > 1) {
					long v = a.get(a.size() - 2);
					a.remove(a.size() - 2);
					pre = (int) v;
					int val = (int) ((v >>> 32) - 1);
					if (val != 0) {
						a.add((long) val << 32 | pre);
					}
				} else {
					ans++;
					long v = a.get(a.size() - 1);
					a.remove(a.size() - 1);
					long val = (v >>> 32) - 1;
					if (val != 0) {
						a.add(val << 32 | pre);
					}
				}
			} else {
				long v = a.get(a.size() - 1);
				a.remove(a.size() - 1);
				pre = (int) v;
				long val = (v >>> 32) - 1;
				if (val != 0) {
					a.add(val << 32 | pre);
				}
			}
		}
		pw.println(ans);
		pw.close();

	}
	
	void tr(Object...objects){System.out.println(Arrays.deepToString(objects));}
}


Measured memory_bytes: 14672
n = gets.to_i
datas = gets.split(" ").map{|nn|nn.to_i}
datas << 0
datas.unshift(0)

base = 0
for i in 0..n
  base += (datas[i+1] - datas[i]).abs
end

for i in 1..n
  ans = base - (datas[i+1] - datas[i]).abs - (datas[i] - datas[i-1]).abs + (datas[i+1] - datas[i-1]).abs
  puts ans.to_s
end

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

int main(void)
{
	double v, y, t;
	int n;
	
	while (scanf("%lf", &v) != EOF){
		t = v / 9.8;
		y = 4.9 * (t * t);
		
		for (n = 0; 5 * n - 5 < y; n++);
		
		printf("%d\n", n);
	}
	
	return (0);
}

Measured memory_bytes: 628
using System;

public class hello
{
    public const int MOD = 10000;
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var k = int.Parse(line[1]);
        var p = new int[n + 1];
        for (int i = 0; i < k; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            var a = int.Parse(line[0]);
            var b = int.Parse(line[1]);
            p[a] = b;
        }
        var dp = new int[n + 2, 4, 4];
        setInit(dp, p);
        getAns(dp, p, n);
        print(dp, n);
    }
    static void print (int[,,] dp , int n)
    {
        var ans = 0;
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
            {
                ans += dp[n + 1, i, j];
                ans %= MOD;
            }
        Console.WriteLine(ans);
    }
    static void getAns(int[,,] dp, int[] p, int n)
    {
        for (int i = 4; i < n + 2; i++)
        {
            dp[i, 1, 1] = (dp[i - 1, 2, 1] + dp[i - 1, 3, 1]) % MOD;
            dp[i, 1, 2] = (dp[i - 1, 1, 1] + dp[i - 1, 2, 1] + dp[i - 1, 3, 1]) % MOD;
            dp[i, 1, 3] = dp[i, 1, 2];
            dp[i, 2, 1] = (dp[i - 1, 1, 2] + dp[i - 1, 2, 2] + dp[i - 1, 3, 2]) % MOD;
            dp[i, 2, 2] = (dp[i - 1, 1, 2] + dp[i - 1, 3, 2]) % MOD;
            dp[i, 2, 3] = dp[i, 2, 1];
            dp[i, 3, 1] = (dp[i - 1, 1, 3] + dp[i - 1, 2, 3] + dp[i - 1, 3, 3]) % MOD;
            dp[i, 3, 2] = dp[i, 3, 1];
            dp[i, 3, 3] = (dp[i - 1, 1, 3] + dp[i - 1, 2, 3]) % MOD;
            var a = p[i - 1];
            if (a != 0)
            {
                for (int j = 1; j <= 3; j++)
                    for (int k = 1; k <= 3; k++)
                        if (a != k) dp[i, j, k] = 0;
            }
        }
    }
    static void setInit(int[,,] dp, int[] p)
    {
        var a1 = p[1];
        var a2 = p[2];
        if (a1 != 0 && a2 != 0) { dp[3, a1, a2] = 1; return; }
        if (a1 != 0)
        { for (int i = 1; i <= 3; i++) dp[3, a1, i] = 1; return; }
        if (a2 != 0)
        { for (int i = 1; i <= 3; i++) dp[3, i, a2] = 1; return; }
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                dp[3, i, j] = 1;
    }
}



Measured memory_bytes: 15892
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,z;
    int a,b,c;
    cin>>x>>y>>z;
    if(x>=1&&x<=100&&y>=1&&y<=100&&z>=1&&z<=100)
    {
        a=x;
        b=y;
        c=z;
        x=c;
        y=a;
        z=b;
        cout<<x<<" "<<y<<" "<<z<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int N;
cin >> N;
int ans;
ans = 800*N - 200*(N/15);
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int main() {
    ll n,a;
    ll x[60];
    std::cin >> n>>a;
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }
    ll dp[60][2610][60];
    Fill(dp,0);

    for (int i = 0; i < n; i++) {
          dp[i][0][0] = 1;
        for (int j = 0; j <= 50*n; j++) {
            for (int c = 1; c <= n; c++) {
//                std::cout << i<<" "<<j <<" "<<c << std::endl;
              	dp[i+1][j][c] = max(dp[i+1][j][c],dp[i][j][c]);

              	dp[i+1][j + x[i]][c] += dp[i][j][c-1] + dp[i][j + x[i]][c];
            }
        }
    }
    ll result = 0;
    for (int i = 1; i <= n; i++) {
        result += dp[n][i*a][i];
    }
    std::cout << result << std::endl;
}


Measured memory_bytes: 73600
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<cstdlib>
#include<algorithm>

using namespace std;

int mymax(int a, int b, int c){
    if(a > b && a > c) return a;
    else if(b > c) return b;
    else return c;
}

int main(){
    int N;
    cin >> N;
    vector<int> L(N);
    for(int i=0; i<N; i++){
        cin >> L[i];
    }
    sort(L.begin(), L.end());
    int ans = 0;

    for(int i=0; i<N-2; i++){
        for(int j=i+1; j<N-1; j++){
            int sum = L[i] + L[j];
            ans += (int) (lower_bound(L.begin(), L.end(), sum) - L.begin()) - j -1;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PI 				acos(-1)
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define MOD				1000000007
#define MOD1			998244353
#define EPS				1e-9
#define fore(i, b, e)	for(int i = b; i < e; i++)
#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
using namespace __gnu_pbds;

typedef long long 		ll;
typedef unsigned long long 		ull;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int tam = 100010;int ara[100010], arb[100010];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//freopen("qwe.txt", "r", stdin);
	//freopen("asd.txt", "w", stdout);
	int n;
	cin>>n;
	string dir = "DULR";
	int ar[31];
	ll d[31];
	d[0] = 1;
	fore(i, 1, 31)
		d[i] = d[i -1] * 2;
	bool bo = false;
	pair<int,int> que[n];
	fore(i, 0, n) cin>>que[i].f>>que[i].s;
	fore(i, 0, n-1)
	{
		if((abs(que[i].f + que[i].s) % 2) != (abs(que[i+1].f + que[i+1].s) % 2))
		{
			cout<<"-1\n";
			return 0;
		}
	}
	bo = ((que[0].f + que[0].s) % 2) == 0;
	cout<<31 + bo<<'\n';
	if(bo) cout<<1<<' ';
	fore(i, 0, 31)
	{
		if(i > 0) cout<<' ';
		cout<<d[i];
	}
	cout<<'\n';
	fore(i, 0, n)
	{
		ll a = que[i].f, b = que[i].s;
		ll su = abs(a) + abs(b);
		string res = "";
		if(bo)
		{
			res += "L";
			su+= (a < 0 ? -1 : 1);
			a++;
		}
		int sen = 1;
		for(int i = 30; i > -1; i--)
		{
			ar[i] = sen;
			if(d[i] > su)
				sen = abs(sen-1);
			su = abs(su - d[i]);
		}
		ll va = 0;
		fore(i, 0, 31)
		{
			if(ar[i])
				va += d[i];
			else
				va -= d[i];
		}
		//cout<<va<<'\n';
		ll ax = abs(a);
		fore(i, 0, 31)
		{
			if(ax & d[i])
			{
				ax += (ar[i] ? -1 : 1) * d[i];
				ar[i] += 2;
			}
		}
		fore(i, 0, 31)
		{
			if(b < 0)
			{
			if((ar[i] < 2))
			{
				ar[i] = abs(ar[i] - 1);
			}	
		}
			if( a < 0)
			{
				if(ar[i] > 1)
				{
					if(ar[i] == 2)
						ar[i] = 3;
					else
						ar[i] = 2;
				}
			}
		}
		fore(i, 0, 31)
			res += dir[ar[i]];
			cout<<res<<'\n';
			ll x = 0, y = 0;

	}
	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?) ARRAY OUT OF BOUNDSS2

Measured memory_bytes: 256