akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
enum{
  NOT_VISITED, VISITED, MAYBE_LOOP, INCOMPLETE, CHECKING, DONE
};
int main()
{
	int N; //町の数
	ll K; //テレポートを使用する回数
	cin >> N >> K;
	//vector<int> A(N); //テレポートの転送先
	vector<vector<int> > A(N, vector<int>(2, 0)); //テレポートの転送先
	for(int i = 0; i < N; i++) {
		cin >> A[i][0];
	}

  int current_location = NOT_VISITED;
	int destination = NOT_VISITED;
	int loop_check = INCOMPLETE;
  int loop_count = 0;

	while(K > 0) {
    current_location = destination;
    //メモした町を再度訪れたとき
    if(A[destination][1] == MAYBE_LOOP && loop_check == CHECKING){
      K %= loop_count;
      loop_check = DONE;
    }
    //ループしていることに気づいたとき，その時点の町をメモしループカウント開始
		else if(A[destination][1] == VISITED && loop_check == INCOMPLETE){
			loop_check = CHECKING;
      A[destination][1] = MAYBE_LOOP;
		}
		else{
			A[current_location][1] = VISITED; //町を訪れたら記録する
		}
    if(loop_check == CHECKING) loop_count++;
		if(K > 0) {
			destination = A[current_location][0] - 1; //テレポート先を指定
			K--; //テレポートを使用
		}
	}
	cout << destination + 1 << endl;
}


Measured memory_bytes: 14316
import math


N, K = map(lambda x: int(x), input().split())
sum = 0

if(N < K):
    edited_N = N
else:
    edited_N = K - 1

for i in range(1, edited_N + 1):
    num = math.ceil(math.log(K/i, 2))
    sum += 0.5 ** num


sum = sum * (1 / N)
if(N >= K):
    sum += (N - edited_N) / N
print(sum)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define all(x) (x).begin(), (x).end()
#define endl '\n'
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  string s;
  cin >> s;
  ll n = s.size();

  ll ans = 0;
  for (ll i = 1; i < n; i++) {
    if (s[i] != s[i - 1]) ans++;
  }
  cout << ans << endl;
}

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

int main()
{
	string s,t,u;
	cin>>s>>t;
	int a,b;
	cin>>a>>b;
	cin>>u;
	if(s==u) cout<<a-1<<" "<<b<<endl;
	else if(u==t) cout<<a<<" "<<b-1<<endl;
	else cout<<a<<" "<<b<<endl;
	return 0;
}


Measured memory_bytes: 256
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#define test ll t; cin>>t; while(t--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define MAX 1000005
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define endl '\n'
#define vs vector<string>
#define mii map<int,int>
#define msi map<string,int>
#define vpii vector< pair<int, int > >
#define vpsi vector< pair< string ,int > >
#define forci(p,q) for(int i=p;i<q;i++)
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b) {a %= mod;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % mod;  a = a * a % mod;  b >>= 1; }  return res%mod; }
ll modmul(ll x, ll y){return (x*y)%mod;}
ll modadd(ll x, ll y){return (x+y)%mod;}
ll modsub(ll x, ll y){return (x-y+mod)%mod;}
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<1000007;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[r],mod-2)))%mod; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
inline long long toint(const std::string &s) {std::stringstream ss; ss << s; long long x; ss >> x; return x;}
inline std::string tostring(long long number) {std::stringstream ss; ss << number; return ss.str();}
inline std::string tobin(long long x) {return std::bitset<63>(x).to_string();}
/*bool prime[MAX];
ull sieve(){memset(prime,true,sizeof(prime));for(ull p=2;p*p<MAX;p++){if(prime[p]==true){for(ull i=2*p;i<MAX;i+=p){prime[i]=false;}}}prime[0]=0;prime[1]=0;
}*/
/*int inv[1000001]={0};
void findinverse(){inv[1] = 1;for(int i = 2; i <=1e6 ; ++i)	inv[i] = (mod - (mod/i) * inv[mod%i] % mod) % mod;}
*/
using namespace std;
int solve()
{
	int a,b,c;
	cin>>a>>b>>c;
	int ans=min(a-b,c);
	cout<<c-ans<<endl;
	return 0;
}
signed main()
{
	fastio;
//	test
		solve();
}







Measured memory_bytes: 3624
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <set>
#include <complex>
#include <functional>
#include <utility>
#include <iterator>

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define dprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define dprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

int main() {
  int a, b;
  cin >> a >> b;
  int ans = a - b * 2;
  if(ans < 0) {
    ans = 0;
  }
  cout << ans << '\n';
  return 0;
}


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

int main() {

    int N;
    scanf("%d", &N);

    vector<int> a;
    for(int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        a.push_back(num);
    }

    std::sort(a.begin(), a.end(), std::greater<int>());
    
    int alice, bob = 0;
    for(int i = 0; i < N; i++) {
        if(i % 2 == 0) {
            alice += a.at(i);
        }
        else {
            bob += a.at(i);
        }
    }
    printf("%d\n", alice - bob);

    return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> x(n), y(n), h(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> h[i];
    for (int cx = 0; cx <= 100; cx++) for (int cy = 0; cy <= 100; cy++) {
        set<int> se;
        for (int i = 0; i < n; i++) if (h[i]) {
            se.emplace(h[i] + abs(x[i] - cx) + abs(y[i] - cy));
        }
        if (se.size() > 1) continue;
        [&](int ch) {
            for (int i = 0; i < n; i++) if (!h[i]) {
                if (ch - abs(x[i] - cx) - abs(y[i] - cy) > 0) return ;
            }
            cout << cx << " " << cy << " " << ch << endl;
        }(*se.begin());
    }
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1302>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

int m,n;
map<string,int> mp;
int rec(vector<string>& obj){
    if(obj.size() <= 1) return 0;
    int ret = m;
    string s; for(auto v:obj) s += v;
    if(mp.count(s)) return mp[s];
    vector<string> l,r;
    for(int i = 0; i < m;i++){
        l.clear(); r.clear();
        for(int j = 0; j < obj.size(); j++){
            if(obj[j][i] == '0') l.push_back(obj[j]);
            else r.push_back(obj[j]);
        }
        if(l.empty() || r.empty()) continue;
        ret = min(ret,1 + max(rec(l),rec(r)));
    }
    mp[s] = ret;
    return ret;
}
int solve(){
    mp.clear();
    int res = 0;
    vector<string> obj(n);
    for(auto& in:obj) cin >> in;
    res = rec(obj);
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> m >> n,m|n){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 6712
//
//  main.cpp
//
 
#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
 
template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
	return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
	auto inner = make_vec_nd(init, rest...);
	return vector<decltype(inner)>(size, inner);
}

#define rep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrep(i,a,b) for(ll i=(a)-1;i>=(b);i--)

int main() {
	ll N;
	cin >> N;
	vector<ll> As(N);
	rep(i,0,N) {
		ll A;
		cin >> As[i];
	}
	sort(As.begin(), As.end());
	ll ans = 0;
	if (N % 2 == 0) {
		rep(i,0,N-1) {
			ll coef = 2 * min(i+1, N-1-i);
			if (i == N/2-1) {
				coef--;
			}
			ans += (As[i+1]-As[i]) * coef;
		}
	} else {
		rep(i,0,N-1) {
			ll coef = 2 * min(i+1, N-1-i);
			if (i == N/2-1 || i == N/2) {
				coef--;
			}
			ans += (As[i+1]-As[i]) * coef;
		}
		ans += max(As[N/2]-As[N/2-1], As[N/2+1]-As[N/2]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;

const int MX = 1<<19;
const int MM = 1000000007;

int D[MX];

int main()
{
	int N;
	scanf("%d", &N);
	int mn = 1e9, mx = 0;
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
		mn = min(mn, D[i]);
		mx = max(mx, D[i]);
	}
	if( mn == mx ){
		if( mn > N/2 && mn != N-1 ) return !printf("No\n");
		else printf("Yes\n");
	}
	else if( mn + 1 == mx ){
		int c = 0;
		for(int i = 1; i <= N; i++){
			if( D[i] == mn ) c++;
		}
		if( N-c <= 1 ) printf("No\n");
		else if( c+1 <= mx && mx <= c+(N-c)/2) printf("Yes\n");
		else printf("No\n");
	}
	else{
		printf("No\n");
	}
}


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

// 約数のリストを返す
std::vector<int> divisorList(int n) {
	std::vector<int> result;
	for(int i = 1; i * i <= n; i++) {
		if(n % i == 0) {
			result.emplace_back(i);
			if(i * i != n) {
				result.emplace_back(n / i);
			}
		}
	}
	return result;
}


int main() {
	int N, M;
	std::cin >> N >> M;

	int answer = 1;
	auto divList = divisorList(M);
	std::sort(divList.begin(), divList.end());
	for(const auto div : divList) {
		if(div >= N) {
			answer = M / div;
			break;
		}
	}

	std::cout << answer << std::endl;

	return 0;
}

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


#define INF (1<<31)-1
#define LINF (1LL<<63)-1LL
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n,p;
    cin>>n>>p;

    ll dp[n][2]={};

    vector<int> a(n);
    int piv = (p+1)%2;

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

    if(a[0]%2==0){
        if(p == 1){
            dp[0][1]=2;
        }else{
            dp[0][0]=2;
        }
    }else{
            dp[0][0]=1;
            dp[0][1]=1;
    }

    rep1(i,1,n){
        if(a[i]%2 == 0){
            dp[i][0] = dp[i-1][0]*2;
            dp[i][1] = dp[i-1][1]*2;
        }else{
            dp[i][0] = dp[i-1][1]+dp[i-1][0];
            dp[i][1] = dp[i-1][0]+dp[i-1][1];
        }
    }

    cout<<dp[n-1][0]<<endl;

    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000

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

    int x, y;
    cin >> x >> y;
    rep(i, x + 1) {
        int turu = i;
        int kame = x - i;
        if (turu * 2 + kame * 4 == y) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<iostream>
    using namespace std;
     
    int main(){
      string str;
      cin>>str;
      int w= str.size()-1;
      if(str[w]=='2'  || str[w]=='4' || str[w]=='5'  || str[w]=='7'  || str[w]=='9'){
        cout<<"hon"<<endl;
      }else if(str[w]=='0'  || str[w]=='1'  || str[w]=='6'  || str[w]=='8'){
        cout<<"pon"<<endl;
      }else{
        cout<<"bon"<<endl;
      }
    }

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

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

using namespace std;


int main() {
    string k = "keyence";
    string s; cin >> s;
    string ans = "YES";
    int p = 0;

    bool d = false;
    bool d2 = false;
    int count = 0;
    int n = s.length();
    int left;

    while(1){
        if(s[p] == k[count]){
            count ++;
            if (count == 7) break;
            p ++;
        }else{
            left = 7-count;
            for(int i = n-left; i < n; i ++){
                if(s[i] != k[count]) ans = "NO";
                count ++;
            }
            break;
        }
    }

    cout << ans;


    return 0;
}











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

int main() {
  int qq;
  scanf("%d", &qq);
  while (qq--) {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    if (a > b)
      swap(a, b);
    long long low = 0, high = 2e9;
    while (low + 1 < high) {
      long long mid = (low + high) / 2;
      long long x, y;
      if (mid % 2 == 0)
        x = mid / 2, y = mid / 2 + 1;
      else
        x = y = mid / 2 + 1;
      if (x * y < a * b)
        low = mid;
      else
        high = mid;
    }
    printf("%lld\n", low - (a != b));
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    long int n,m,k,a[200001],b[200001],suma[200001] = {},sumb[200001] = {},sum = 0,i,j;
    scanf("%ld %ld %ld",&n,&m,&k);
    for(i = 0 ; i < n ; i++)
    {
        scanf("%ld",&a[i]);
        if(i == 0)
        {
            suma[i] == 0;
        }
        
            suma[i + 1] = suma[i] + a[i];
        
        
    }
    for(i = 0 ; i < m ; i++)
    {
        scanf("%ld",&b[i]);
        if(i == 0)
        {
            sumb[i] == 0;
        }
        
            sumb[i + 1] = sumb[i] + b[i];
        
        
    }
    
    int daihyou = m;
    for(i = 0 ; i <= n ; i++)
    {
        if(suma[i] > k)
        {
            break;
        }
        j = daihyou;
        while(j >= 0)
        {
            if(suma[i] + sumb[j] <= k)
            {
                if(sum < i + j)
                {
                    sum = i + j;
                }
                daihyou = j;
                
                break;
            }
            j--;
        }
    }
    printf("%ld\n",sum);
    return 0;
}

Measured memory_bytes: 7960
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 0; i < n; ++i)
#define rep3(i, a, b) for (ll i = a; i < b; ++i)
#define rep4(i, a, b, c) for (ll i = a; i < b; i += c)
#define erep(n) for (ll i = 0; i <= n; ++i)
#define erep2(i, n) for (ll i = 0; i <= n; ++i)
#define erep3(i, a, b) for (ll i = a; i <= b; ++i)
#define erep4(i, a, b, c) for (ll i = a; i <= b; i += c)
#define rrep(i, a, b) for (ll i = a; i > b; --i)
#define rrep2(i, a, b, c) for (ll i = a; i > b; i -= c)
#define errep(i, a, b) for (ll i = a; i >= b; --i)
#define errep2(i, a, b, c) for (ll i = a; i >= b; i -= c)
#define print(a) cout << a << endl;
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
#define cin(x) cin >> x;
const ll MOD = 1000000007;
const double PI = 3.14159265358979323846264338327950;
inline int newline() { putchar('\n'); return 0; }

int main() {
    int x, y;
    cin(x); cin(y);

    if (y < 2 * x) {
        print("No");
        return 0;
    }

    ll a = 4 * x - y;
    if (a < 0 || a % 2 != 0) {
        print("No");
    } else {
        print("Yes");
    }
    return 0;
}

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

int main()
{
	ll n,m;
	cin>>n;
	ll a[n+1]={0},b;
	for(ll i=2;i<=n;++i){
		cin>>b;
		a[b]++;
	}
	for(ll i=1;i<=n;++i){
		cout<<a[i]<<endl;
	}
}

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

int main()
{
    int h, a;
    cin >> h >> a;
    if (h % a == 0)
        cout << h / a << endl;
    else
        cout << h / a + 1 << endl;
    return 0;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << "\n";
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define endl "\n"
// gcj print用
#define Case(x) printf("Case #%d: ", x);

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
};

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

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

void print() {
  cout << endl;
}

template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}

template <class T>
void print(vector<T> &vec, ll k){
   ll n = vec.size();
   k = min(k, n);
   rep(i, 0, k-1) cout << vec[i] << " ";
   cout << vec[k-1] << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
  for (auto& vec : df) {
    print(vec);
  }
}

template<class T, class U>
void print(pair<T,U> &p){
  cout << p.first << " " << p.second << "\n";
}

int t[13] = {-1, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};

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

  int x, y;
  cin >> x >> y;
  if (t[x] == t[y]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
};


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i = 0; i < 10; i++){
			int tmp = sc.nextInt();
			list.add(tmp);
		}
		
		Collections.sort(list);
		Collections.reverse(list);
		
		for(int i = 0; i < 3; i++){
			int tmp = list.get(i);
			System.out.println(tmp);
		}
	}
}

Measured memory_bytes: 17176
#include <iostream>
#include <algorithm>
#include <cstdint>

int64_t const MOD = 1e9+7;
enum {
 // one char
 kA = 0, kC = 1, kG = 2, kT = 3,
 // 3 char NG patterns
 kAGC = 9, kGAC = 0x21, kACG = 6,
 // 4 char NG patterns
 kA_GC = 9, kAG_C = 0x21,
 // mask for 4 char NG patterns
 kX_XX = 0xcf, kXX_X = 0xf3,
 kMask = 0x3f
};

int const MAXPAT = 64;
int const MAXN = 100;
int N;
int64_t dp[MAXN+1][MAXPAT];

int main() {
  std::cin >> N;
  for(int i = 3; i <= N; ++i) std::fill(dp[i], dp[i]+MAXPAT, (int64_t)0);
  // N=3
  std::fill(dp[3], dp[3]+MAXPAT, 1);
  dp[3][kAGC] = dp[3][kGAC] = dp[3][kACG] = 0;
  // N>=4
  for(int i = 4; i <= N; ++i) {
    // for A,T
    for(int p = 0; p < MAXPAT; ++p) {
      int np = (p<<2)&kMask;
      (dp[i][np+kA] += dp[i-1][p]) %= MOD;
      (dp[i][np+kT] += dp[i-1][p]) %= MOD;
    }
    // for G
    for(int p = 0; p < MAXPAT; ++p) {
      int np = (p<<2)&kMask;
      if(np+kG == kACG) continue;
      (dp[i][np+kG] += dp[i-1][p]) %= MOD;
    }
    // for C
    for(int p = 0; p < MAXPAT; ++p) {
      int np = (p<<2) + kC;
      if((np&kX_XX) == kA_GC) continue;
      if((np&kXX_X) == kAG_C) continue;
      np &= kMask;
      if(np == kAGC || np == kGAC) continue;
      (dp[i][np] += dp[i-1][p]) %= MOD;
    }
  }
  int64_t ans = 0;
  for(int p = 0; p < MAXPAT; ++p) (ans += dp[N][p]) %= MOD;
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main ( )
{
int x,a,b;
scanf("%d%d%d",&x,&a,&b);
if(-a+b<=0)cout<<"delicious\n";
else if (-a + b <= x ) printf ( "safe\n") ;
else printf ( "dangerous \n" ) ;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
//typedef pair<double, P> T;

const ll mod = 1000000007;
const ll INF = 100000010000;

ll N, M, a[100010], g[100010], b[100010];

ll ans;

ll gcd(ll x, ll y)
{
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2 == 1)
	{
		return x * pow_mod(x, y - 1) % mod;
	}
	else
	{
		ll half = pow_mod(x, y / 2);
		return half * half % mod;
	}
}

ll div_mod(ll x)
{
	return pow_mod(x, mod - 2);
}

/*ll sum_bit(ll i)
{
	ll s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add_bit(ll i, ll x)
{
	while (i <= 2 * N + 10)
	{
		bit[i] += x;
		i += i & -i;
	}
}*/

void init()
{
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
		a[i] /= 2;
		b[i] = a[i];
	}
	
}

void output()
{
	cout << ans << endl;
}



void solve()
{
	ans = 1;
	for (int i = 0; i < N; i++)
	{
		ans = ans * a[i] / gcd(ans, a[i]);
		while (b[i] % 2 == 0)
		{
			g[i]++;
			b[i] /= 2;
		}
	}
	ans = M / ans;
	ans = (ans + 1) / 2;
	bool jud = true;
	for (int i = 1; i < N; i++)
	{
		if (g[i - 1] != g[i])
		{
			jud = false;
		}
	}
	if (!jud)
	{
		ans = 0;
	}
}

int main()
{
	init();
	
	solve();

	

	output();
	ll N;
	cin >> N;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define COUT(x) cout << (x) << endl
using namespace std;
typedef pair<int,int> P;
typedef long long int ll;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
    int a, p; cin >> a >> p;
    COUT((a * 3 + p) / 2);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int N, K;
  cin >> N >> K;
  
  int L;
  L = K - 1;
  
  string S;
  
  int i;
  for (i = 0; i < N; i++){
    cin >> S;
    
  }
  
  if (S.at(L) == 'A'){
    
    S.at(L) = 'a' ;
  }
    
  else if (S.at(L) == 'B'){
    
    S.at(L) = 'b' ;
  }
    
  else if (S.at(L) == 'C'){
    
    S.at(L) = 'c' ;
    
  }
    
    
  cout << S << endl;
  
  
}


  


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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/e.in", "r", stdin);
//  freopen("../IO/f.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

int64_t calc(vector<int> &A, int thresh) {
  int64_t sm = 0;
  for (int a : A) {
    if (a <= thresh) continue;
    sm += (a + thresh - 1) / thresh - 1;
  }
  return sm;
}


void solve(std::istream &in, std::ostream &out) {
  int n, k;
  in >> n >> k;
  vector<int> A(n);
  for (int &i : A) in >> i;
  if (!k) {
    out << *max_element(A.begin(), A.end()) << '\n';
    return;
  }
  int hi = *max_element(A.begin(), A.end()) + 1;
  int lo = 0;
  while (hi - lo > 1) {
    int m = hi + lo >> 1;
    if (calc(A, m) <= k) {
      hi = m;
    } else {
      lo = m;
    }
  }
  out << hi << '\n';
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  for (int i = 0; i < N; i++) cin >> h[i];

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

  int ans = 1 << 30;
  for (int i = 0; i + K - 1 < N; i++) {
    ans = min(ans, h[i + K - 1] - h[i]);
  }

  cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>//pair
#include<cmath>//abs,sqrt
#include<cstring>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int INF=1e+9;
const ll INFLL=1e+17;
int main(){
  int n,Y;cin>>n>>Y;
  Y/=1000;
  int x=-1,y=-1,z=-1;
  rep(i,n+1){
    rep(j,n+1){
      if(9*i+4*j==Y-n&&n-i-j>=0){
	x=i;y=j;z=n-i-j;
	break;
      }
    }
  }
  cout<<x<<" "<<y<<" "<<z<<"\n";

  

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        int n = sc.nextInt();
        int answer = 0;
        for (int i = 0; i < n; i++) {
            int b = sc.nextInt();
            answer = answer + b - 1;
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 27364
def solve():
  N, K, C = map(int, input().split())
  workable = [i for i, s in enumerate(input()) if s=="o"]
  if len(workable) == K:
    return workable
    
  latest = set()
  prev = workable[-1]+C+1
  for x in reversed(workable):
    if prev - x > C:
      latest.add(x)
      prev = x
      if len(latest) > K:
        return []
  must = []
  prev = -C-1
  for x in workable:
    if x - prev > C:
      if x in latest:
        must.append(x)
      prev = x
  return must

for i in solve():
  print(i+1)

Measured memory_bytes: 12580
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define VIEW(x) do {cerr << #x << ": "; for(auto i : x) cerr << i << " "; cerr << endl;} while(0)
#define ALL(x) (x).begin(),(x).end()
template<class T>bool umax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}
template<class T>bool umin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}

template<typename A,size_t N,typename T> void FILL(A (&array)[N],const T &val){fill((T*)array,(T*)(array+N),val);}
template<typename T> void FILL(vector<T> &v, const T &x) {fill(v.begin(), v.end(), x);}
template<typename T> void FILL(vector<vector<T>> &v, const T &x) {for(auto &i:v)fill(i.begin(), i.end(), x);}

int main() {
  ll n; cin >> n;
  ll ans = 0;
  for(ll a = 1; a <= n; a++) {
    ll b_max = n / a;
    ans += b_max + ((n%a) == 0 ?  - 1 : 0);
  }
  cout << ans << endl; 
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define loop(i,a,b) for(int i=a; i<b; i++)
#define INF 10000000000099ll
#define mod 1000000007
#define prDouble(x) cout<<fixed<<setprecision(10)<<x

ll solve(vector<int>& v, int n, int k)
{
    ll dp[n+2][k+2];
    for(int i=0; i<=k; i++)
        dp[1][i]= (i>v[1]) ? 0 : 1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<=k; j++){
            if(j==0)
                dp[i][j]= dp[i-1][j];
            else dp[i][j]= (mod + dp[i][j-1] + dp[i-1][j] - ((j-v[i]-1 >=0) ? dp[i-1][j-v[i]-1] : 0))%mod;
        }
    }
    return dp[n][k]%mod;
}

int main()
{
    #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
    FASTIO;
    int n,k;
    cin>>n>>k;
    vector<int> v(n+1);
    loop(i,1,n+1) cin>>v[i];
    cout<<solve(v, n, k);
    return 0;
}



Measured memory_bytes: 81628
n = int(input())
word = []
for _ in range(n):
    a = int(input())
    l = [list(map(int,list(input().split()))) for _ in range(a)]
    word.append(l)

ans = 0
for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i>>j) & 1 == 1 and flag == 0:
            for k,v in word[j]:
                if i>>(k-1) & 1 != v:
                    flag = 1
                    break

    if flag == 0:
        ans = max(ans,bin(i).count('1'))

print(ans)


Measured memory_bytes: 3064
import math
n = int(input())

num_li = []
for i in range(10):
    num_li.append(6**i)
    num_li.append(9**i)
num_li.sort(reverse=True)

dp = [10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    for j in num_li:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)

print(dp[n])    

Measured memory_bytes: 3864
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    ll n; cin >> n;
    string s; cin >> s;
    ll r=0, b=0;
    rep(i,n){
        if(s[i] == 'R') r++;
        else b++;
    }
    if(r > b) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
int n,h[100005];
int count;
int max=0;
int now;
int count3;
scanf("%d",&n);
for(count=0;count<n;count++){
    scanf("%d",&h[count]);
}
now=0;
for(count=0;count<n-1;count++){
    if(h[count]>=h[count+1]){now++;}
    else{
        if(now>=max){max=now;}
        now=0;

    }
    //printf("now=%d\n",now);
}
if(now>=max){max=now;}
printf("%d",max);

}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main() {
	int A,B,C,D;
	cin >> A>>B>>C>>D;
	if(A+B < C+D) {
		cout << "Right" << endl;
	}
	else if(A+B==C+D) {
		cout << "Balanced" << endl;
	}
	else {
		cout << "Left" << endl;
	}
}


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

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

    int m;
    cin >> m;
    vector<int> w(m);
    for(int i=0; i<m; i++) cin >> w[i];

    int count=0;

    for(int i=0; i<m; i++) {
        if(find(v.begin(), v.end(), w[i]) != v.end()){
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3112
#include <iostream>
#include <vector>

#define SENTINEL 1000000001

using namespace std;

int cnt = 0;

void merge(vector<int> &A, int left, int mid, int right)
{
	int n1 = mid - left;
	int n2 = right - mid;
	vector<int> L(n1 + 1), R(n2 + 1);
	for (int i = 0; i < n1; i++)
	{
		L[i] = A[left + i];
	}
	for (int i = 0; i < n2; i++)
	{
		R[i] = A[mid + i];
	}
	L[n1] = SENTINEL;
	R[n2] = SENTINEL;
	int i = 0;
	int j = 0;
	for (int k = left; k < right; k++)
	{
		if (L[i] <= R[j])
		{
			A[k] = L[i];
			i++;
		}
		else
		{
			A[k] = R[j];
			j++;
		}
		cnt++;
	}
}

void mergeSort(vector<int> &A, int left, int right)
{
	if (left + 1 < right)
	{
		int mid = (left + right) / 2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> S(n);
	for (int i = 0; i < n; i++)
	{
		cin >> S[i];
	}
	mergeSort(S, 0, n);
	for (int i = 0; i < n; i++)
	{
		cout << S[i];
		if (i == S.size() - 1)
		{
		    cout << endl;
		}
		else
		{
		    cout << " ";
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 6800
//submitted by Himj
  #include<bits/stdc++.h>
  #define ll long long
  #define mod 1000000007
  #define pb push_back
  #define fi first
  #define se second
  #define fr(i,s,e) for(i=s;i<e;i++)
  #define ms(arr,val) memset(arr,val,sizeof(arr))
  using namespace std;

  const int mxn=2e5+1;

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

    int t=1;
    //cin>>t;
      while(t--){
        ll k,a,b,cur=1;
        cin>>k>>a>>b;
        if(b-a>2)
        {
          ll temp=min(a-cur,k);
          k-=temp;
          cur+=temp;
          temp=k/2;
          cur+=temp*(b-a);
          if(k%2)
            cur++;
        }
        else
          cur+=k;
        cout<<cur;
        
         
      }
    return 0;
    }



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

#define N 15

int main() {
	static int aa[N], xx[N][N - 1], yy[N][N - 1];
	static char honest[N];
	int n, i, j, b, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		for (j = 0; j < aa[i]; j++)
			scanf("%d%d", &xx[i][j], &yy[i][j]), xx[i][j]--;
	}
	ans = -1;
	for (b = 0; b < 1 << n; b++) {
		int k;

		memset(honest, 0, n * sizeof *honest);
		for (i = 0; i < n; i++)
			if (b & 1 << i)
				honest[i] = 1;
		k = 0;
		for (i = 0; i < n; i++)
			if (honest[i]) {
				k++;
				for (j = 0; j < aa[i]; j++)
					if (honest[xx[i][j]] != yy[i][j])
						goto bad;
			}
		if (ans < k)
			ans = k;
bad:
		;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include<string>
#include<utility>
#include<iterator>
#include<regex>
#include<math.h>

#define lli long long
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(lli i=0;i<j;i++)
#define rep1(i,j) for(lli i=1;i<=j;i++)
#define rep0d(i,j) for(lli i=j-1;i>=0;i--)
#define MAX 1000000007
typedef struct tree Tree;

using namespace std;

bool cmpf(pair<lli, lli> left, pair<lli, lli> right) {
	return left.first < right.first;
}
bool cmp(pair<lli, lli> left, pair<lli, lli> right) {
	if (left.first != right.first)return left.first < right.first;
	else return left.second < right.second;
}
int main() {
	lli d, g,ans=MAX;
	cin >> d >> g;
	vector<lli> p(d), c(d);
	vector<lli> sum(d);
	rep0(i, d) {
		cin >> p[i] >> c[i];
		sum[i]=p[i]*(i + 1) * 100 + c[i];
	}
	for (unsigned lli i=0; i < (1 << d); i++) {
		unsigned lli num = 1;
		lli tmp = 0, ans_tmp = 0;
		rep0(j,d) {
			if ((num & i) > 0) {
				tmp += sum[j];
				ans_tmp += p[j];
			}
			num <<= 1;
		}
		i=~i;
		lli ans_min = MAX;
		num = 1;
		rep0(j, d) {
			if ((num & i) > 0&&(g-tmp)<p[j]*(j+1)*100) {
				ans_min = min(ans_min, (g - tmp + (j + 1) * 100 - 1) / ((j + 1) * 100));
			}
			num <<= 1;
		}
		if (g <= tmp)ans_min = 0;
		i=~i;
		ans = min(ans, ans_tmp + ans_min);
	}
	cout << ans;
}


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

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans = INF, tmp;
int N;
vi A;

void solve(){
    for(int m = -100; m <= 100; ++m){
        tmp = 0;
        rep(i, N) tmp += (m-A[i])*(m-A[i]);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
}

int main(){
    cin >> N;
    A.resize(N);

    rep(i, N) cin >> A[i];

    solve();
}


Measured memory_bytes: 256
///in the name of Allah the most beneficent the most merciful.
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 998244353
//#define mod2 20071027
//#define MOD 998244353
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define base 139
//#define mod 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case %lld: ", ++c)
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
const ll N=300010, M=1000005;
ll n,k, a[N], res;
int main()
{
    in1(n);
    for(int i=0;i<n;i++)
    {
        in1(a[i]);
        if(i>0)
        {
            ll t = min(a[i], a[i-1]);
            res+=t;
            a[i]-=t;
        }
        if((a[i]/2)>0)
        {
            ll t = a[i]/2;
            res+=t;
            a[i]-=(2*t);
        }
    }
    printf("%lld\n",res);
    return 0;
}
/*

*/


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


int main() {
  int N,Y;
  int resx=-1,resy=-1,resz=-1;
  cin >> N >> Y;
  for(int x=0;x<=N;x++){
      for(int y=0;y<=N-x;y++){
        int sum=1000*x+5000*y+10000*(N-x-y);
        if (sum==Y){
          resx=x;
          resy=y;
          resz=N-x-y;
        }
      }
  }
  cout<<resz<<" "<<resy<<" "<<resx<<endl;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

for i in range(N-M+1):
  for j in range(N-M+1):
    flag = True
    for k in range(M):
      for l in range(M):
        if A[i+k][j+l] != B[k][l]:
          flag = False
    if flag:
      print('Yes')
      exit()
print('No')

Measured memory_bytes: 40048
N = int(input())
A = list(map(int, input().split()))



for i in range(N-1):
    #print(i, max, N, A[i], A[i+1])
    if A[i] - A[i+1] >=2:
        print('No')
        break
    
    if A[i] - A[i+1] ==1 and i >=2 and A[i-1] >= A[i]:
        print("No")
        break
    
    if i ==0 or A[i] > A[i-1]:
        A[i] -=1
        
else:
    print('Yes')

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

using namespace std;

#define MAX 2010
typedef long long ll;
const ll MOD = (1e9) + 7;

ll dp[MAX][MAX];

ll extgcd(ll a, ll b, ll &x, ll &y)
{
    ll d = a;
    if (b != 0) {
	d = extgcd(b, a % b, y, x);
	y -= (a / b) * x;
    } else {
	x = 1; y = 0;
    }
    return d;
}

ll mod_inverse(ll a, ll m)
{
    ll x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

int main()
{
    ll N, D, X;
    ll sum[MAX];
    while (cin >> N >> D >> X, N) {
        ll res = 0, comb = 1;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 1; i <= min(N, D); i++) {                        
            comb *= (D - i + 1) % MOD;
            comb %= MOD;
            comb *= mod_inverse(i, MOD);
            comb %= MOD;
            
            memset(sum, 0, sizeof(sum));
            for (int j = 0; j <= N; j++) {
                sum[j] += dp[i-1][j];                
                if (j > 0) sum[j] += sum[j-1];
                sum[j] %= MOD;
            }

            for (int j = 0; j <= N; j++) {
                if (j > 0) dp[i][j] = sum[j-1];
                if (j - X >= 0) {
                    dp[i][j] += (-sum[j-X] + MOD) % MOD;
                }
                dp[i][j] %= MOD;
            }                
            res += dp[i][N] * comb;
            res %= MOD;
        }
        cout << res << endl;
    }
    return 0;
}

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

using namespace std;

int main(int argc, const char *argv[]) {
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  int t = (a != b) + (b != c) + (c != a);
  t = t ? t : 1;
  printf("%d\n", t);
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

ll N, A[212345];

int main() {

	cin >> N;
	rep(i, N) cin >> A[i];

	map<ll, ll> B;
	rep(i, N) B[A[i]]++;

	ll pre = 0;

	for (auto b : B) {
		pre += b.second * (b.second - 1) / 2;
	}

	rep(i, N) {
		cout << pre - B[A[i]] * (B[A[i]] - 1) / 2 + (B[A[i]] - 1) * (B[A[i]] - 2) / 2 << endl;
	}

	return 0;
}


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

using namespace std;
#define ll long long
vector<vector<pair<ll, int>>> vert((int) 2e3 + 1, vector<pair<ll, int>>(0));
ll dp[(int) 2e3 + 1][(int) 7e3 + 1];
bool noWay[(int) 2e3 + 1][(int) 7e3 + 1];
vector<vector<int>> g(1e5+1, vector<int>(0));
vector<bool> was(1e5+1, false);
vector<int> topsort(0);
vector<int> grandi(1e5+1);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<pair<int, ll>> type(0);
    string s;
    cin>>s;
    ll last=-1;
    for(int i=0;i<s.size();i++){
        if(s[i]-'<'!=last){
            type.push_back({s[i]-'<',1});
        }
        else{
            type[type.size()-1].second++;
        }
        last=s[i]-'<';
    }
    last=-1;
    ll ans=0;
    for(int i=0;i<type.size();i++){
        if(type[i].first==0){
            ans+=(type[i].second-1)*type[i].second/2;
            last=type[i].second-1;
        }
        else{
            ans+=(type[i].second+1)*type[i].second/2;
            if(type[i].second<=last){
                ans+=last-type[i].second+1;
            }
        }
    }
    if(type[type.size()-1].first==0) ans+=type[type.size()-1].second;
    cout<<ans;
}

Measured memory_bytes: 9492
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace OOJ_ITP_1_3_B
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            while (true)
            {
                int num = int.Parse(Console.ReadLine());
                if (num == 0)
                    break;
                Console.WriteLine("Case {0}: {1}", ++count, num);
            }
        }
    }
}



Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int f[100005];
int main()
{
 	ll sum=0;
 	int i,n,r;
 	cin>>n>>r;
 	for(i=1;i<=n;i++)
 	{
 		cin>>f[i];
	 }
    sort(f+1,f+n+1);
    for(i=n;i>n-r;i--)
    {
    	sum+=f[i];
	}
	cout<<sum;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  rep(i, N) cin >> A[i];
  map<ll, int, greater<ll> > mp;
  rep(i, N) {
    if(!mp.count(A[i])) mp[A[i]] = 1;
    else mp[A[i]]++;
  }
  int ans = 0;
  for(auto a: mp) {
    ll tmp = a.first;
    ll pair = (ll)pow(2, ceil(log2(tmp))) - tmp;
    if(pair == 0) {
      if(mp[tmp] > 0) {
        int cnt = mp[tmp] / 2;
        mp[tmp] -= 2 * cnt;
        ans += cnt;
      }
    } else {
      if(mp[tmp] > 0 && mp.count(pair) && mp[pair] > 0) {
        int cnt = min(mp[tmp], mp[pair]);
        mp[tmp] -= cnt;
        mp[pair] -= cnt;
        ans += cnt;
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 14336
// https://atcoder.jp/contests/dp/tasks/dp_a
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define ll long long
#define rep(i, s, n) for (ll i = s; i < n; ++i)
#define dump(x) cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define MOD 1000000007

using namespace std;

int solve(int n, vector<int> h) {
    int ans = 0;
    vector<int> dp(n, 0);
    rep(i, 1, n) {
        if (i == 1) {
            dp[i] = abs(h[i] - h[i - 1]);
        } else {
            dp[i] = min(abs(h[i] - h[i - 1]) + dp[i - 1],
                        abs(h[i] - h[i - 2]) + dp[i - 2]);
        }
    }

    return dp[n - 1];
}

int main() {
    int n, hi;

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    vector<int> h;

    rep(i, 0, n) {
        cin >> hi;
        h.push_back(hi);
    }

    int ans = solve(n, h);
    cout << ans << endl;
}


Measured memory_bytes: 4476
#include<bits/stdc++.h>
using namespace std;
int cnt[300001];
int main()
{
    int n;
    cin>>n;
    int a[300001];
    for(int i=0;i<n-1;i++)
    {
        cin>>a[i];
        cnt[a[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 5188
n,u,v = map(int,input().split())

import queue

dist_t = [0] * n
dist_a = [0] * n

elb_t = [0] * n
elb_a = [0] * n

ab = [[] for j in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

u -= 1
v -= 1

q = queue.Queue()

q.put(u)
elb_t[u] = 1
dist_t[u] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_t[idx] != 1:
            if dist_t[idx] != 0:
                dist_t[idx] = min(dist_t[idx], dist_t[tmp] + 1)
            else:
                dist_t[idx] = dist_t[tmp] + 1
            elb_t[idx] = 1
            q.put(idx)

q = queue.Queue()

q.put(v)
elb_a[v] = 1
dist_a[v] = 0

while not q.empty():
    tmp = q.get()
    for i in range(len(ab[tmp])):
        idx = ab[tmp][i]
        if elb_a[idx] != 1:
            dist_a[idx] = dist_a[tmp] + 1
            elb_a[idx] = 1
            q.put(idx)

ans = 0

for i in range(n):
    if dist_a[i] > dist_t[i]:
        ans = max(ans,dist_a[i]-1)

print(ans)

Measured memory_bytes: 82844