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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}
int power(long long x, long long y, long long p) {
    long long res = 1;  // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1) res = (res * x) % p;

        // y must be even now
        y = y >> 1;  // y = y/2
        x = (x * x) % p;
    }
    return res;
}

long long modInverse(long long n, long long p) { return power(n, p - 2, p); }

long long nCrModPFermat(long long n, long long r, long long p) {
    if (r == 0) return 1;
    long long fac[n + 1];
    fac[0] = 1;
    for (long long i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

signed main() {
    long long n, m, a, b;
    cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < m; i++) {
        int as;
        cin >> as;
        sum += as;
    }
    if (n < sum) {
        cout << "-1" << endl;
        return 0;
    }
    cout << n - sum << endl;
}

Measured memory_bytes: 3656
object Main {
  def main(args: Array[String]): Unit = {
    import scala.io.StdIn.readLine
    val Array(datN) = readLine.split(" ").map(_.toInt)

    val rank =
      if (datN >= 400 && datN <= 599) 8
      else if (datN >= 600 && datN <= 799) 7
      else if (datN >= 800 && datN <= 999) 6
      else if (datN >= 1000 && datN <= 1199) 5
      else if (datN >= 1200 && datN <= 1399) 4
      else if (datN >= 1400 && datN <= 1599) 3
      else if (datN >= 1600 && datN <= 1799) 2
      else 1
    println(rank)
  }
}


Measured memory_bytes: 54596
n = str(input())
n = n[-1]
if n == '2' or n == '4' or n == '5' or n == '7' or n == '9':
    print('hon')
elif n == '0' or n == '1' or n == '6' or n == '8':
    print('pon')
else:
    print('bon')




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

using namespace std;
typedef long long ll;
ll A,B;
ll D;
int N;
ll h[100005];
int solve(ll n)
{
    ll sum=B*n;
    for(int i=0;i<N;i++)
    {
        if(h[i]>sum)
        {
            n-=(h[i]-sum)/D;
            if((h[i]-sum)%D)
                n--;
        }
    }
    if(n<0)
        return 0;
    else
        return 1;
}
int main()
{

    scanf("%d",&N);
    scanf("%lld%lld",&A,&B);
    D=A-B;
    for(int i=0;i<N;i++)
    {
        scanf("%lld",&h[i]);

    }
    ll l=1;
    ll r=1e9;
    ll mid=(l+r)/2;
    while(l<r)
    {
        int flag=solve(mid);
        if(flag)
            r=mid;
        else
            l=mid+1;
        mid=(l+r)/2;
    }

    printf("%lld",l);
}


Measured memory_bytes: 1024
/*  -*- coding: utf-8 -*-
 *
 * d.cc: D - Road to Millionaire
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 80;
const int D0 = 1000;

/* typedef */

typedef long long ll;

/* global variables */

int as[MAX_N];
ll dp[MAX_N + 1];

/* subroutines */

inline void setmax(ll &a, ll b) { if (a < b) a = b; }

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", as + i);

  dp[0] = D0;
  for (int i = 0; i < n; i++) {
    setmax(dp[i + 1], dp[i]);

    int mina = as[i];
    for (int j = i + 1; j < n; j++) {
      setmax(dp[j + 1], dp[i] % mina + (dp[i] / mina) * as[j]);
      mina = min(mina, as[j]);
    }
  }

  printf("%lld\n", dp[n]);
  return 0;
}


Measured memory_bytes: 3216
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int y = sc.nextInt();
			int x = sc.nextInt();
			if(x == 0 && y == 0)break;
			for ( int j = 0; j < x; j++ )System.out.print("#");
			 System.out.println("");
			for ( int i = 0; i < y - 2; i++ ){
	        	System.out.print("#");	
				for ( int j = 0; j < x -2; j++ ){
		        	System.out.print(".");		       
		    	}
				System.out.println("#");		       
			}
			for ( int j = 0; j < x; j++ )System.out.print("#");
			System.out.println("\n");	
			
		}
	}
}



Measured memory_bytes: 33160
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip> 
#include <bits/stdc++.h>
using namespace std;
double pi=3.14159265358979323846264338;
const int MOD=1000000007;

int main() {
	int t;
	cin>>t;
	//int ans;
	for(int i=1;i<=179;i++){
		if((i*360)%t==0){
			cout<<i*360/t<<endl;
			return 0;
		}
		//else cout<<i*360/t<<" "<<i<<endl;
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#define N 12
using namespace std;
int main() {
	string ans;
	int s[30][50];
	int min;
	int n;
	int l;
	cin >> n;
    
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 30; j++) {
			s[j][i] = 0;
		}
	}

	for (int i = 0; i < n;i++) {
		cin >> ans;
		l = ans.length();
		for (int j = 0; j < l;j++) {
			s[('a' - ans[j])*-1][i] ++ ;
		}
	}
    
	for (int i = 0; i < 30;i++) {
		min = s[i][0];
		for (int j = 1; j < n; j++) {
			if (min > s[i][j]) {
				min = s[i][j];
			}
		}
		while (min > 0) {
			cout << (char)('a' + i);
			min--;
		}
	}
	cout << endl;


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int a[100000];
int b[100000];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  long long suma = 0, sumb = 0;
  vector<int>up;
  int cnt = 0, j = 0;
  map<int, int>used;
  cin >> n;

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

  for(int i = 0;i < n;i++){
	cin >> b[i];
	sumb += b[i];
	if(b[i] < a[i]) up.push_back(a[i] - b[i]);
  }

  sort(up.begin(), up.end());
  reverse(up.begin(), up.end());
  
  if(suma < sumb){
	cout << -1 << endl;
  }else{
	for(int i = 0;i < n;i++){
	  if(a[i] < b[i]){
		cnt ++;
		while(a[i] < b[i]){
		  used[j] ++;
		  if(a[i] + up[j] < b[i]){
			a[i] += up[j];
			j ++;
		  }else{
			up[j] -= (b[i] - a[i]);
			a[i] += (b[i] - a[i]);
		  }
		}
	  }
	}

	for(int i = 0;i < up.size();i++){
	  if(used[i] > 0) cnt++;
	}
	cout << cnt  << endl;
  }
			
  return 0;
}


Measured memory_bytes: 3836
#include <cstdio>
using namespace std;

int main(){
	int sum, count;
	int val, cou, n;
	
	sum = 0; count = 0; n = 0;
	while((scanf("%d,%d", &val, &cou)) != EOF){
		sum += val * cou;
		count += cou;
		n++;
	}
	
	printf("%d\n%d\n", sum, (count + n - 1) / n);
	
	return 0;
}

Measured memory_bytes: 1020
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[123456];
#define mod 109+7;
int main(){
	int x,a,b;
	while(~scanf("%d%d%d",&x,&a,&b)){
		if(a-b>=0) printf("delicious\n");
		else{
			if(b-a<=x){
				printf("safe\n");
			}
			else{
				printf("dangerous\n");
			}
		}
	}
		
	
	return 0;
} 

Measured memory_bytes: 128
a,b,c,k = map(int,input().split())
max_point = 0
if k - a  >= 0:
    max_point += a
else :
    max_point = k
if k - a - b  > 0:
    max_point += (a+b)-k
else :
    max_point = max_point      
print(max_point)

Measured memory_bytes: 9000
package main

import (
	"fmt"
	//"sort"
	//"strconv"
	//"strings"
	//"bufio"
	//"os"
	//"strconv"
	"math"
)

func main() {
	//input
	var n float64
	fmt.Scan(&n)
	f := int(n) % 2 
	if f == 0{
		fmt.Print(math.Trunc(n/2)/n)
	}else{
		fmt.Print((math.Trunc(n/2)+1)/n)
	}
}

Measured memory_bytes: 512
def main():
    S = input()
    result = 'Yes'
    for i in range(len(S)):
        if (i % 2 == 0 and S[i] == 'L') or (i % 2 == 1 and S[i] == 'R'):
            result = 'No'
            break
    print(result)


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

ll mod = 1000000007;

signed main()
{
    string s;
    cin >> s;
    int cnt = 0;
    rep(i, s.size() - 1)
    {
        if (s[i] != s[i + 1])
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

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

int main()
{
  long  n;
  long k;
  cin>>n;
  cin>>k;
  vector<long> nums(n);
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    nums[i]=x;
  }
    vector<long> dp(n,INT_MAX);
    dp[0]=0;
    dp[1]=abs(nums[0]-nums[1]);
    for(long i=2;i<n;i++)
    {  
  		for(long j=1;j<=k && (i-j)>=0 && (i-j)<n;j++)
          dp[i]=min(dp[i],dp[i-j]+abs(nums[i]-nums[i-j]));
    }
    cout<<dp[n-1]<<endl;
  return 0;
}

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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    int d1, d2;
    cin >> d1 >> d2;
    if (d1 == d2) {
      cnt++;
      if (cnt == 3) {
        cout << "Yes" << endl;
        return 0;
      }
    } else {
      cnt = 0;
    }
  }
  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <bitset>


using namespace std;
int main(){
	int N;
	cin >> N;
	if(N==1) cout<<"Hello World"<<endl;
	else{
		int A,B;
		cin >>A>>B;
		cout<<A+B<<endl;
	}
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        StringBuilder sb = new StringBuilder();

        if (a < b) {
            for (int i = 0;i<b;i++) {
                sb.append(a);
            }
        } else {
            for (int i = 0;i<a;i++) {
                sb.append(b);
            }
        }
        System.out.println(sb.toString());

    }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>
#define rep(i,j) for(int i{};i<j;i++)
using namespace std;int d[100001][13];void f(int i, int j, int k){(d[i+1][k%13]+=d[i][j])%=1000000007;}main(){string s;cin>>s;d[0][0]=1;rep(i,s.size())rep(j,13){if(s[i]=='?')rep(k,10)f(i,j,j*10+k);else f(i,j,j*10+s[i]-'0');}cout<<d[s.size()][5];}

Measured memory_bytes: 5504
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <map>
#include <vector>
#include <string>
#include <vector>
#include <cassert>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cmath>
#include <stack>
#include <list>
#include <cctype>
#include <queue>
#include <algorithm>
#include <memory>
#include <memory.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, P> P2;
typedef pair<int, pair<P, P> > PPP;
const int INF = 1 << 30;
const double EPS = 1e-10;
const double PI = 3.14159;

P bridge[50];

int main(){
	int n;
	while(cin >> n && n){
		for(int i = 0; i < n; i++){
			cin >> bridge[i].second >> bridge[i].first;
		}
		sort(bridge, bridge + n);
		int sum = 0;
		int p = 0;
		while(p < n && sum + bridge[p].second <= bridge[p].first){
			sum += bridge[p].second;
			p++;
		}
		if(p == n) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 592
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
    vector<int>a(1000001);
    int k;
    cin>>k;
    for(int i=1;i<=1000001;i++){
        a[k]++;
        if(a[k]>1){
            cout<<i<<endl;
            break;
        }else{
            if(k%2==0)k=k/2;
            else k=3*k+1;
        }
    }
    return 0;
}

Measured memory_bytes: 6984
#include <cmath>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int solve(ll n)
{
	if(n < 10)
		return n;
	
	ll n0 = n;
	int ndig = 0;
	ll p10 = 1;
	while(10 <= n)
	{
		n /= 10;
		++ndig;
		p10 *= 10;
	}
	int res1 = 9*ndig + n-1;
	int res2 = n + solve(n0-p10*n);
	return max(res1,res2);
}

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

	ll n;
	cin >> n;

	int ans = solve(n);
	
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int flg[101],i,x,f;
	for(i=1;i<=100;i++)	flg[i]=0;
	for(i=0;i<12;i++)	{
		scanf("%d",&x);
		flg[x]++;
	}
	f=1;
	for(i=1;i<=100;i++)	{
		if(flg[i]%4!=0)	{
			f=0;
			break;
		}
	}
	if(f==1)	printf("yes\n");
	else printf("no\n");
	return 0;
}


Measured memory_bytes: 2140
Module Module1

    Sub Main()
        Dim input As String = Console.ReadLine()
        'Dim input As String = "575"
        If (input.Substring(0, 1).Equals(input.Substring(2, 1))) Then
            Console.WriteLine("Yes")
        Else 
      		Console.WriteLine("No")
        End If
    End Sub
End Module

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

int main() {
    int INF = 9999999;
    string s;
    cin >> s;
    int N = s.size();
    vector<int> a(N, 0);
    for (int i = 0; i < N; i++) {
        int d = (1 << (int)(s[i]-'a'));
        if (i == 0) a[0] = d;
        else a[i] = a[i-1]^d;
    }
    vector<int> opt(N+1, INF);
    opt[0] = 0;
    vector<int> dp(1 << 26, INF);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        int m = INF;
        m = min(m, dp[a[i-1]]);
        for (int k = 0; k < 26; k++) {
            m = min(m, dp[a[i-1]^(1 << k)]);
        }
        opt[i] = m+1;
        dp[a[i-1]] = min(dp[a[i-1]], m+1);
    }
    cout << opt[N] << endl;
    return 0;
}


Measured memory_bytes: 264324
n, m = map(int, input().split())
broken = [0 for _ in range(n)]
for _ in range(m):
    broken[int(input())] = 1
mod = 1000000007
dp = [0 for _ in range(n+2)]
dp[n] = 1
for i in range(n)[::-1]:
    if(broken[i]):
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod
print(dp[0])

Measured memory_bytes: 7832
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const ll INF = 1LL << 60;

ll D, G;
vector<ll> p, c;
ll ans = INF;

void dfs(int cnt, vector<ll> v) {
    if (cnt == D) {
        // スコア計算
        // 対象の問題の高い順から計算していく

        // ボーナス取得する問題をセット
        ll score = 0;
        ll question_cnt = 0;
        rep(i, v.size()) {
            if (v[i] == 0) continue;
            score += (i + 1) * 100 * p[i] + c[i];
            question_cnt += p[i];
        }
        // cout << score << " " << question_cnt << endl;

        if (G <= score) {
            ans = min(ans, question_cnt);
            return;
        }

        // 残りは高い問題から埋めていく
        for (int i = D - 1; i >= 0; i--) {
            if (v[i] == 1) continue; 
            // if (p[i] == 1) continue;
            for (int j = p[i] - 1; j >= 0; j--) {
                score += (i + 1) * 100;
                question_cnt++; 

                if (G <= score) {
                    ans = min(ans, question_cnt);
                    return;
                }
            }
        }

        return;
    }

    for (int i = 0; i < 2; i++) {
        v[cnt] = i;
        dfs(cnt + 1, v);
    }
}

int main() {
    cin >> D >> G;
    p.resize(D);
    c.resize(D);
    rep(i, D) cin >> p[i] >> c[i];

    vector<ll> tmp(D, 0);
    dfs(0, tmp);

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int freq[100000];
    int a;
    int maxm=0;
    int result=0;
    for (int i=0;i<100000;i++){
        freq[i]=0;
    }
    for (int i=0;i<n;i++){
        cin>>a;
        freq[a]++;
    }
    for (int i=1;i<100000-1;i++){
        maxm=freq[i]+freq[i-1]+freq[i+1];
        if (maxm>=result){
            result=maxm;
        }
    }
    cout<<result<<endl;
    return 0;
}


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

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

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

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

  int sum_v = 0;
  int sum_c = 0;
  for(int i = 0; i < n; i++) {
    if (v[i] > c[i]) {
      sum_v = sum_v + v[i];
      sum_c = sum_c + c[i];
    }
  }

  cout << sum_v - sum_c << "\n";
  return 0;
}


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

int main() {

	string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZA";

	int N = 0;
	cin >> N;

	string str;
	cin >> str;

	for (int i = 0; i < str.size(); i++) {
		str[i] = *(find(alphabet.begin(), alphabet.end(), str[i]) + N);
	}

	cout << str << endl;
}

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

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	int x, y;
	cin >> x >> y;
	x--;
	y--;
	vector<vector<int>> d(n, vector<int>(n, 0));
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			if (abs(i - x) + abs(j-y) + 1 < j - i) {
				d[i][j] = abs(i - x) + abs(j - y) + 1;
			}
			else {
				d[i][j] = j - i;
			}
		}
	}

	vector<int> ans(n, 0);
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			ans[d[i][j]]++;
		}
	}

	for (int i = 1; i < n; i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 16000
#include<stdio.h>
#include<string.h> 
int main()
{
	int N;
	scanf("%d", &N);
	char S[N];
	char T[N];
	
	scanf("%s %s", S, T);
	
	int r;
	
	for(r=0; r<N; r++){
		printf("%c%c", S[r], T[r]);
	}

	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef bitset<705> bs;

// dp[i] is number of colorings with sum equal to i
ll dp[300 * 300 + 5];
const int MOD = 998244353;

ll modpow(ll b, ll e, ll m) {
  ll r = 1;
  while(e) {
    if(e%2) {
      r*=b;
      r%=m;
    }
    b*=b;
    b%=m;
    e/=2;
  }
  return r;
}

ll compensate(vector<int>& v) {
  memset(dp, 0, sizeof(dp));
  dp[0] = 1;
  int tot = 0;
  for(int out: v) {
    for(int i = 90000; i >= out; i--) {
      dp[i] += dp[i-out];
      dp[i] %= MOD;
    }
    tot += out;
  }
  return 3 * dp[tot/2];
}

void solve() {
  int n;
  cin >> n;
  dp[0] = 1;
  ll total = 1;
  int sum = 0;
  vector<int> v;
  for(int i = 0; i < n; i++) {
    total *= 3;
    total %= MOD;
    int t;
    cin >> t;
    v.push_back(t);
    sum += t;
    for(int x = 300 * 300; x >= 0; x--) {
      dp[x] = 2 * dp[x];
      if(x >= t) dp[x] += dp[x-t];
      dp[x] %= MOD;
    }
  }
  ll ret = total;
  for(int i = (sum+1)/2; i <= sum; i++) {
    ret += 3 * (MOD - dp[i]);
    ret %= MOD;
  }
  if(sum%2 == 0) {
    ret += compensate(v);
    ret %= MOD;
  }
  cout << ret << "\n";
}

void casesolve() {
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  // casesolve();
}


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

using namespace std;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int x = 0, maxVal = x;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == 'D')
            x--;
        if(s[i] == 'I')
            x++;
        maxVal = max(maxVal, x);
    }
    cout << maxVal;
    return 0;
}

Measured memory_bytes: 256
while True:
    try:
        a,b,c,d,e,f=map(int,input().split())
        print("{0:.3f} {1:.3f}".format((c*e-b*f)/(a*e-b*d)+1e-10,(a*f-c*d)/(a*e-b*d)+1e-10))
    except:break


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

int main() {
  int N;
  cin >> N;
  
  vector <int> B(N);
  
  for(int i = 0; i < N;i++)
    cin >> B.at(i);
  
  int j = 0;
  int count = 0;
  bool finish = false;
  for (int i = 0; i < N; i++){
    if (B.at(j) == 2) {
      count ++;
      finish = true;
      break;
    }
    else {
      count++;
      j = B.at(j)-1;
    }
  } 
  if (finish) cout << count << endl;
  else cout << "-1" << endl;  
}

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

#define endl "\n"

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h1, h2, m1, m2, k;
    int h, m;

    cin >> h1 >> m1 >> h2 >> m2 >> k;

    if (m1 <= m2)
        m = m2 - m1;
    else {
        m = m2 + 60 - m1;
        if (h2 != 0)
            h2--;
        else
            h2 = h2 + 24 - 1;
    }
    h = (h2 >= h1) ? h2 - h1 : h2 + 24 - h1;
    // m = m2 + (60 - m1);
    // if (m >= 60) {
    //     h++;
    //     m -= 60;
    // }
    
    int ans = h * 60 + m - k;
    if (ans > 0)
        cout << ans << endl;
    else
        cout << 0 << endl;
     

    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <stdio.h>

using namespace std;

//typedefリスト
typedef long long llint;
typedef vector<long long int> vint;
typedef vector< vector<int> > vvint;
typedef vector<string> vstr;


int main(void) {
	int N;
	cin >> N;
	vstr S(N);
	vint P(N);
	map<string, int> mp;
	vector<pair<string, int>> p(N);
	for (int i = 0; i < N; i++) {
		cin >> S[i] >> P[i];
		p[i] = make_pair(S[i], P[i]);
	}
	sort(S.begin(), S.end());
	for (int i = 0; i < N; i++) {
		int ma = -1;
		for (int j = 0; j < N; j++) {
			if (S[i] == p[j].first) {
				ma = max(ma, p[j].second);
			}
		}
		for (int j = 0; j < N; j++) {
			if (ma == p[j].second&&S[i] == p[j].first) {
				cout << j + 1 << endl;
				p[j].second -= 101;
			}
		}
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

vector<int> GetPrimes(ll x) {
  vector<int> primes;
  for (int p = 2; p * p <= x; ++p) {
    while (x % p == 0) {
      primes.push_back(p);
      x /= p;
    }
  }
  if (x != 1) primes.push_back(x);
  return primes;
}

int main() {
  int X;
  cin >> X;
  while (true) {
    if (GetPrimes(X).size() == 1) {
      cout << X << endl;
      return 0;
    }
    ++X;
  }
  return 0;
}


Measured memory_bytes: 256
import math

PI = math.pi

a, b, h, m = map(int, input().split())

rad = 2 * PI * abs(h / 12.0 + m / 60.0 / 12.0 - m / 60.0)

ans = math.sqrt(a * a + b * b - 2 * a * b * math.cos(rad))

print(ans)


Measured memory_bytes: 9496
#!/usr/bin/env python3

n, c = list(map(int, input().split()))

x, v = [], []
for i in range(n):
    a, b = list(map(int, input().split()))
    x.append(a)
    v.append(b)

cw = [0]*(n+1)
ccw = [0]*(n+1)
for i in range(n):
    cw[i+1] = cw[i]+v[i]
    ccw[i+1] = ccw[i]+v[-i-1]


for i in range(1, n+1):
    cw[i] -= x[i-1]
    ccw[i] -= c-x[-i]


maxcw = [0]*(n+1)
maxccw = [0]*(n+1)
for i in range(1, n+1):
    maxcw[i] = max(maxcw[i-1], cw[i])
    maxccw[i] = max(maxccw[i-1], ccw[i])

ans = max(0, maxcw[-1], maxccw[-1])

for i in range(1, n+1):
    ans = max(ans, cw[i] + maxccw[-i-1] - x[i-1])
    ans = max(ans, ccw[i] + maxcw[-i-1]-(c-x[-i]))

print(ans)


Measured memory_bytes: 29552
using System;
using System.Collections.Generic;//list用
using System.Text;//StringBuilder用
using System.Collections;
using System.Linq;
class Program
{
    static List<int> s=new List<int>();
      static List<int> t=new List<int>();
    static decimal result;
static int N,G,S,B;
    static void Main()
    {
Read1();
result=180*(N-2);
   Console.WriteLine(result.ToString());

      
    }

    static void Read1()
    {
        string tmp = Console.ReadLine();
        N = int.Parse(tmp);
    }

    static void Read2()
    {
      
}
}

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

int main(){
  int N ;
  double D ; 
  cin >> N >> D ; 
 // vector<double> A(N) ;  
  int cnt=0;
  
  for(int i = 0 ; i < N ; i++){
    double B , C ; 
    cin >> B >> C ; 
    
    if(B*B + C*C <= D*D){
      cnt++ ; 
    }
  }

  cout << cnt << endl ; 
  
}

Measured memory_bytes: 3784
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;

template <class _T> static _T tp_abs(const _T& a) {
	//	usage:  tp_abs<type name>(a);
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void getint(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
static void getstring(char* buff) {
	if (scanf(" %s", buff) < 0) {
		printf("getstr error!\n");
	}
}

static void Disco2020C();

#if 1
int main()
{
	Disco2020C();
	fflush(stdout);
	return 0;
}
#endif

static int Disco2020C_dfs(
	std::vector<std::string>& grid,
	int startH, int startW,
	int H, int W,
	std::vector<std::vector<int>>& blkGrid,
	int blockNo)
{
	int berry = 0;
	std::vector<std::pair<int, int>> bPos(2, std::pair<int, int>(0, 0));

	for (int h = startH; h < H; h++) {
		for (int w = startW; w < W; w++) {
			if (grid[h][w] == '#') {
				bPos[berry].first = h;
				bPos[berry].second = w;
				berry++;
			}
			if (berry >= 2) break;
		}
		if (berry >= 2) break;
	}

	int sh1, sh2, sw1, sw2;
	int eh1, eh2, ew1, ew2;
	sh1 = sh2 = sw1 = sw2 = eh1 = eh2 = ew1 = ew2 = 0;

	if (berry == 1) {
		for (int h = startH; h < H; h++) {
			for (int w = startW; w < W; w++) {
				blkGrid[h][w] = blockNo;
			}
		}
		blockNo++;
	}
	else if (bPos[0].first == bPos[1].first) {
		sh1 = sh2 = startH;
		eh1 = eh2 = H;
		sw1 = startW;
		sw2 = tp_max(bPos[0].second, bPos[1].second);
		ew1 = sw2;
		ew2 = W;

	}
	else {
		sh1 = startH;
		sh2 = tp_max(bPos[0].first, bPos[1].first);
		eh1 = sh2;
		eh2 = H;
		sw1 = sw2 = startW;
		ew1 = ew2 = W;
	}
	
	if(berry >= 2) {
		blockNo = Disco2020C_dfs(grid, sh1, sw1, eh1, ew1, blkGrid, blockNo);
		blockNo = Disco2020C_dfs(grid, sh2, sw2, eh2, ew2, blkGrid, blockNo);
	}

	return blockNo;
}

static void Disco2020C()
{
	int H, W, K;
	getint(H, W, K);

	std::vector<std::string> grid(H);
	for (int i = 0; i < H; i++) {
		std::cin >> grid[i];
	}

	std::vector<std::vector<int>> blkGrid(H, std::vector<int>(W, 0));

	Disco2020C_dfs(grid, 0, 0, H, W, blkGrid, 1);

	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			printf("%d ", blkGrid[h][w]);
		}
		putchar('\n');
	}
}

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

string s;

void solve()
{
	const int n = s.length();
	int ans = n-1;
	set<char> ch(s.begin(), s.end());
	for(char c : ch){
		int p=-1;
		int cur = 0;
		for(int i=0;i<n;++i)if(s[i]==c){
			cur=max(cur, i-p-1);
			p = i;
		}
		cur=max(cur, n-p-1);
		ans=min(ans, cur);
	}
	cout<<ans<<'\n';
}

int main()
{
	cin >> s;
	solve();
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
template <class X> void print(X x) { cout << x << endl; }
#define in(A, n)                                                                                                       \
    rep(i, n) {                                                                                                        \
        cin >> f;                                                                                                      \
        A.push_back(f);                                                                                                \
    }

void print(vl x) {
    for(ll i : x) {
        cout << i << " ";
    }
    cout << endl;
}
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, n, t, r, k, w, l, ans, i, j, u, v, m;
ll codeforces = 1;
string S, T;
vector<vl> g(MAX_N);
vl A, B;
void input() { cin >> n; }
void solve() {
    a = 0;
    rep(i, n) {
        cin >> x >> y;
        if(x == y)
            a++;
        else
            a = 0;
        if(a == 3)
            ans = 1;
    }

    if(ans)
        print("Yes");
    else
        print("No");
}
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    while(codeforces--) {
        solve();
    }
}

Measured memory_bytes: 15052
#include <bits/stdc++.h>
#define pb push_back
#define SZ(x) ((int)(x.size()))
#define FOR(i,s,n) for (ll i = (s); (i) < (n); ++i)
#define FORD(i,s,l) for (ll i = (s); (i) >= l; --i)
#define F first
#define S second
#define TC int __tc; cin >> __tc; FOR(case_num,1,__tc+1)
#define TEST(x,i) ((x)&(1ll<<(i)))
#define SET(x,i) ((x)|(1ll<<(i)))
#define FLIP(x,i) ((x)^(1ll<<(i)))
#define CLEAR(x,i) ((x)&~(1ll<<(i)))

const double pi = 4 * atan(1);
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 200005;

int arr[105];
ll dp[55][55][55*55];

int n;
int a;

ll solve(int idx, int cnt, int s){
	if (idx == n) {
		return (cnt != 0 && s%cnt==0 && s/cnt==a);
	}
	if (dp[idx][cnt][s] != -1) {
		return dp[idx][cnt][s];
	}
	return dp[idx][cnt][s] = solve(idx+1,cnt+1,s+arr[idx]) + solve(idx+1,cnt,s);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> a;
	memset(dp,-1,sizeof dp);
	
	FOR(i,0,n){
		cin >> arr[i];
	}
	cout << solve(0,0,0) << "\n";
}


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

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; }
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using ll = long long;
using pint = pair<int, int>; 
using pll  = pair<ll, ll>;
using vint = vector<int>; 
using vll  = vector<ll>;
using vstr = vector<string>;

//　定数, 変数 *********************************************
const ll MOD=1e9+7;
const ll INF=1ll<<60;

int x;
// *********************************************************
int main(){

    cin >> x ;

    if(x==0){cout<<"1"<<endl;}
    else cout<<"0"<<endl;





    return 0;
}

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

using namespace std;
typedef long long ll;
//ループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//コンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define D()
//定数
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int a, b, k;
    cin >> k >> a >> b;
    if(a/k != b/k) cout << "OK";
    else if(a%k==0) cout << "OK";
    else cout << "NG";
}

Measured memory_bytes: 3608
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include<tuple>
#include<string.h>
#include<iomanip>
#include<stack>
#include<queue>

using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define ALLOF(c) (c).begin(), (c).end()
#define Pa pair<ll,ll>
const ll mod=10e9+7;
const ll INF=10e12;
const ll inf=-1;
ll ABS(ll a){return max(a,-a);}

int main(void){
    ll N,D;
    cin>>N>>D;
    ll X=2*D+1;
    ll ans=N/X;
    if(N%X) ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
//abc066_c.cpp
//Sat Jun  9 19:58:34 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;

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

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

	ll ans = 1;

	if (n%2==0){
		for (int i=1;i<n;i++){
			if (num[i] != 2){
				ans = 0;
				break;
			}else{
				ans = (ans * 2)%1000000007;
			}
			i++;
		}
	}else {
		if (num[0] == 1){
			for (int i=2;i<n;i++){
				if (num[i] != 2){
					ans = 0;
					break;
				}else{
					ans = (ans *2)%1000000007;
				}
				i++;
			}
		}else{
			ans = 0;
		}
	}

	cout << ans << endl;
}

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<double> a(n);
    REP(i,0,n) cin>>a[i];
    double ans=0.0;
    REP(i,0,n) ans+=(1.0/a[i]);
    cout << fixed << setprecision(10) << 1.0/ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int N;
    cin >> N;
    int a;
    int ans=0;
    int num=1;
    for(int i=0;i<N;i++){
        cin >> a;
        if(a!=num){
            ans++;
        }else{
            num++;
        }
    }

    if(ans==N) ans=-1;

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main()
{
    int h, w;
    scanf("%d%d", &h, &w);
    char a[100][101];
    int x[100] = {};
    int y[100] = {};
    int i, j, k, l;

    for (i=0; i<h; i++)
    {
        scanf("%s", a[i]);
    }

    for (i=0; i<h; i++)
    {
        int cnt = 0;
        for (j=0; j<w; j++)
        {
            if (a[i][j] == '.') cnt ++;
        }
        if (cnt == w) {
            y[i] = 1;
        }
    }

    for (i=0; i<w; i++)
    {
        int cnt = 0;
        for (j=0; j<h; j++)
        {
            if (a[j][i] == '.') cnt ++;
        }
        if (cnt == h) {
            x[i] = 1;
        }
    }

    for (i=0; i<h; i++)
    {
        if (y[i]) continue;
        for (j=0; j<w; j++)
        {
            if (x[j]) continue;
            printf("%c", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}




Measured memory_bytes: 128
#include <iostream>
using namespace std;
#include <utility>
using P = pair<int,int>;
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#include<algorithm>
int main(){
    int N,count = 0;
    cin >> N;
    int e=0,s=0;
    vector<P> p(N);
    rep(i,N){
        cin >> p[i].second >> p[i].first;
    }
    sort(p.begin(),p.end());
    e = p[0].first;
    s = p[0].second;
    count++;
    for(int i=1;i<N;i++){
        if(e < p[i].second){
            count++;
            e = p[i].first;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>
using namespace std;

int main()
{
	const string w[] = { "apple", "peach" };
	const string t[] = { "_ALE_", "_PEH_" };
//	cut here before submit 
//	freopen("testcase.applepeach", "r", stdin);
	string str = "";
	int i;

	while (getline (cin, str ) ){
		if (str.empty() ){
			break;
		} // end if
		vector <int> dot;
		vector <int> camma;
		int i;
//		str = ' ' + str + ' ';

		while ( str.find ('.') != string::npos ){
			dot.push_back ((int)str.find('.') );
			str.replace (str.find('.'), 1, " " );
		} // end while
		while ( str.find (',') != string::npos ){
			camma.push_back ((int)str.find(',') );
			str.replace (str.find (','), 1, " " );
		} // end while

		while (str.find(w[0]) != string::npos ){
			str = str.replace (str.find(w[0]), w[0].length(),t[0] );
		} // end while

		while (str.find(w[1]) != string::npos ){
			str = str.replace (str.find(w[1]), w[1].length(),t[1] );
		} // end while

		while (str.find(t[0]) != string::npos ){
			str = str.replace (str.find(t[0]), t[0].length(),w[1] );
		} // end while

		while (str.find(t[1]) != string::npos ){
			str = str.replace (str.find(t[1]), t[1].length(),w[0] );
		} // end while

		if (!dot.empty() ){
			for (i = 0; i < dot.size(); ++i){
				str = str.replace (dot[i], 1, "." );
			} // end for
		} // end if
		if (!camma.empty() ){
			for (i = 0; i < camma.size(); ++i){
				str = str.replace (camma[i], 1, "," );
			} // end for
		} // end if

//		cout << str.substr(1, str.length() - 2) << endl;	
		cout << str << endl;
	} // end loop
		
	return 0;
}

Measured memory_bytes: 0
/*
 * If you're not willing to make sacrifices yourself, you'll never be
 * able to change anything. In order to overcome monsters, you must
 * be willing to abandon your own humanity.
 * ~ Arlert
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;

typedef long long int LL;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define si(n) scanf("%d", &n)
#define dout(n) printf("%d\n", n)
#define sll(n) scanf("%lld", &n)
#define lldout(n) printf("%lld\n", n)

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

#define fast_io                     \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)

#define endl '\n'

int main() {
  fast_io;
  int n;
  cin >> n;
  int c = 0;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (a == i + 1)
      c++;
    else {
      ans += (c + 1) / 2;
      c = 0;
    }
  }
  ans += (c + 1) / 2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }

P f(int n){
    string s = to_string(n);
    return P(s.front() - '0',s.back() - '0');
}

//ミョ(-ω- ?)
int main() {
    int n;
    cin >> n;
    map<P,int> mp;
    for(int i = 1;i <= n;i++){
        P p = f(i);
        mp[p]++;
    }
    ll res = 0;
    for(int i = 1;i <= n;i++){
        P q = make_pair(f(i).second , f(i).first);
        res += mp[q];
    }
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 3636
N = gets.chomp.to_i
S = gets.chomp.chars

cnt = 0
(0..999).each do |n|
  s = "%03d" % n
  i = S.find_index(s[0])
  next if i == nil
  j = S[i+1..-1].find_index(s[1])
  next if j == nil
  k = S[i+j+2..-1].find_index(s[2])
  next if k == nil
  cnt += 1
end

puts cnt

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

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

static const ll INF = 1e15;

static const ll mod = 1e9 + 7;

int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> vs(n);
	rep(i, n) cin >> vs[i];
	sort(vs.begin(), vs.end());
	ll sum = 0;
	rep(i, k) {
		sum += vs[i];
	}
	cout << sum << endl;
	return 0;
}
	

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

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

    cout << (n - 2) / (k - 1) + 1 << endl;
    return 0;
}


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

int main(){
	long a, b, n;
	scanf("%ld%ld%ld", &a, &b, &n);
	long x = n;
	if(b - 1 < n) x = b - 1;
	printf("%ld\n", a * (x % b) / b);
}


Measured memory_bytes: 3788
# coding: utf-8
H = int(raw_input())
A = map(int,raw_input().split())

for i in range(H):
    parent_key = ""
    left_key = ""
    right_key = ""
    ans = ""
    if i == 0:
        if 2*(i+1) - 1 < H:
            left_key = "left key = " + str(A[2*(i+1)-1])  +", "
        if 2*(i+1) < H:
            right_key= "right key = " + str(A[2*(i+1)]) + ", "
    else:
        parent_key = "parent key = " + str(A[(i+1)/2-1]) + ", "
        if 2*(i+1) - 1 < H:
            left_key = "left key = " + str(A[2*(i+1)-1])  +", "
        if 2*(i+1) < H:
            right_key= "right key = " + str(A[2*(i+1)]) + ", "
    ans = "node " +str(i + 1) + ": key = "+ str(A[i]) + ", " +\
        parent_key + left_key + right_key
    print ans

Measured memory_bytes: 4248
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int MOD =1e9+7;
using ll=long long;
using Graph = vector<vector<int>>;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> cost(n);
    rep(i,n) cin >> cost[i];
    sort(cost.begin(),cost.end());
    int ans = 0;
    rep(i,k){
        ans += cost[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#define MOD 1000000007
#define pb push_back
using namespace std;

int dp[100100];
vector<int> stones;

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

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		stones.pb(x);
	}

	for (int i = 0; i <= k; i++) {
		for (int stone : stones) {
			if (i - stone >= 0)
				if(dp[i - stone] == 0) dp[i] = 1;
		}
	}

	if (dp[k]) cout << "First";
	else cout << "Second";
	return 0;
}

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  string s; cin >> s;
  int r = 0, b = 0;
  for (auto i : s) if (i == '0') r++; else b++;
  cout << min(r, b) * 2 << '\n';
  return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;


int main() {

    cin.tie(0); ios::sync_with_stdio(false);
    
    ll N, K;
    vector<ll> tree;

    cin >> N >> K;
    tree.resize(N, 0);

    for (ll i = 0; i < N; ++i)
        cin >> tree[i];

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

    ll res = 10000000000;
    for(ll i=0; i+K-1<N; i+=1)
        res=min(res, tree[i+K-1]-tree[i]);

    cout<<res<<endl;

    return 0;
}


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

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

    int x, ans = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        if ((x * 2) >= (K - x) * 2)
        {
            ans += (K - x) * 2;
        }
        else
        {
            ans += x * 2;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256