akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define LEN(x) (int)x.size()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
using namespace std;
typedef int64_t i64;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF = 0x3f3f3f3f;

signed main()
{
  int N, M;
  int odeg[55] {};

  cin >> N >> M;
  for (int i= 0; i < M; ++i) {
    int a ,b; cin >> a >> b;
    ++odeg[a], ++odeg[b];
  }

  for (int i= 1; i <= N; ++i) cout << odeg[i] << endl;

  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <tuple>
#include <algorithm>
#include <memory>
#include <numeric>
#include <queue>
#include <functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;

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

	ll N, M;
	cin >> N >> M;

	vector<ll> X(M);

	for (ll i = 0; i < M; ++i)
	{
		cin >> X[i];
	}

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

	vector<ll> d(M-1);

	for (ll i = 0; i < M-1; ++i)
	{
		d[i] = X[i + 1] - X[i];
	}

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

	ll s = 0;
	for (ll i = 0; i < M-N; ++i)
	{
		//cout << d[i] << endl;
		s += d[i];
	}


	cout << s << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;
 

int  A(int x){
    if(x>=0)return x;
    else return -x;
}

ll inv(ll x) {
	ll res = 1;
	ll k = N - 2;
	ll y = x%N;
	while (k) {
		if (k & 1)res = (res*y) % N;
		y = (y%N)*(y%N) % N;
		k /= 2;
	}
	return res;
}

unsigned long long popCount64bitB(unsigned long long x) 
{ 
    x = ((x & 0xaaaaaaaaaaaaaaaaUL) >> 1) 
      +  (x & 0x5555555555555555UL); 
    x = ((x & 0xccccccccccccccccUL) >> 2) 
      +  (x & 0x3333333333333333UL); 
    x = ((x & 0xf0f0f0f0f0f0f0f0UL) >> 4) 
      +  (x & 0x0f0f0f0f0f0f0f0fUL); 
    x = ((x & 0xff00ff00ff00ff00UL) >> 8) 
      +  (x & 0x00ff00ff00ff00ffUL); 
    x = ((x & 0xffff0000ffff0000UL) >> 16) 
      +  (x & 0x0000ffff0000ffffUL); 
    x = ((x & 0xffffffff00000000UL) >> 32) 
      +  (x & 0x00000000ffffffffUL); 
    return x; 
} 

bool g[13][13];

int main(void){
    ll n;
    cin>>n;
    ll ans = (ll)INF;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ans = min(ans,i+n/i-2);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int dp[2][103];
	int n;
	int bill[2][103];
	while(cin >> n , n){
		rep(i,2)rep(j,103)dp[i][j] = (1<<21);
		rep(i,2)rep(j,103)bill[i][j] = 0;
		rep(i,2)rep(j,n)cin >> bill[i][j];
		
		dp[0][0] = dp[1][0] = 0;
		
		rep(loop,n+1000){
			rep(i,n){
				rep(bit,2){
					if(bill[bit][i] == 1){
						if(bill[bit][i+1] == 1){
							dp[bit][i+1] = min(dp[bit][i+1],dp[bit][i]);
						}else{
							dp[bit^1][i] = min(dp[bit^1][i],dp[bit][i]+1);
							dp[bit^1][i+1] = min(dp[bit^1][i+1],dp[bit][i]+1);
							dp[bit^1][i+2] = min(dp[bit^1][i+2],dp[bit][i]+1);
						}
					}else if(bill[bit][i] == 2){
						dp[bit][i-1] = min(dp[bit][i-1],dp[bit][i]);
					}else if(bill[bit][i] == 0){
						dp[bit^1][i] = min(dp[bit^1][i],dp[bit][i]+1);
						dp[bit^1][i+1] = min(dp[bit^1][i+1],dp[bit][i]+1);
						dp[bit^1][i+2] = min(dp[bit^1][i+2],dp[bit][i]+1);
					}
				}
			}
		}
		rep(bit,2){
			if(bill[bit][n-1] != 2)dp[bit][n] = min(dp[bit][n-1],dp[bit][n]);
		}
		int ret = min(dp[0][n],dp[1][n]);
		if(ret != (1<<21) ){
			cout << ret << endl;
		}else{
				cout << "NA" << endl;
		}
	}
}

Measured memory_bytes: 864
import java.util.Scanner;
import java.util.HashSet;
import java.lang.String;
 
public class Main {
  
  public static void main (String[] arg) {
    Scanner sc = new Scanner(System.in);
    HashSet<Integer> pcolors = new HashSet<Integer>();
    pcolors.add(sc.nextInt());
    pcolors.add(sc.nextInt());
    pcolors.add(sc.nextInt());    
    sc.close();
    
    System.out.println(pcolors.size());
  }
}

Measured memory_bytes: 23764
S = input()
oddSet = set(['R', 'U', 'D'])
evenSet = set(['L', 'U', 'D'])
for idx, ch in enumerate(S):
	if(idx % 2 == 0):
		if(ch not in oddSet):
			print("No")
			exit(0)
	else:
		if(ch not in evenSet):
			print("No")
			exit(0)
print("Yes")

Measured memory_bytes: 3064
#include <stdio.h>
int main()
{   int n,k;
    scanf("%d%d",&n,&k);
    long long ans=1;
    for(int i=0;i<n;i++){
        if(i==0){
            ans*=k;
        }else{
            ans*=(k-1);
        }
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string.h>
#include <fstream>
#include<time.h>
#include <string>
#include <string.h>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <stack>
#include <map>
#include <queue>
#include<cctype>
#include <math.h>
#include <algorithm>
#define Size 1000
using namespace std;
int number[10];
int lef[10];
bool dfs(int num){
    if(num == 10){
        int lnum = 0, rnum = 0;
        for(int i = 0; i < 10; i ++){
            if((lef[i] == 1 && lnum > number[i])
               ||(lef[i] == 0 && rnum > number[i]))
               return false;
            else if(lef[i] == 1)
                lnum = number[i];
            else
                rnum = number[i];
        }
        return true;
    }
    lef[num] = 1;
    bool left = dfs(num + 1);
    lef[num] = 0;
    bool right = dfs(num + 1);
    return left || right;
}
int main()
{
    //ifstream in;
    //in.open("a.txt", ios::in);
    int n;
    cin>>n;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < 10; j ++){
            cin>>number[j];
        }
        if(dfs(0))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3072
#include<iostream>
using namespace std;
int x[12][12];
int T[12][12], V[12][12];
void compute(int X, int Y) {
	int dx[5] = { -1,0,0,0,1 }, dy[5] = { 0,-1,0,1,0 };
	for (int i = 0; i < 5; i++) { T[X + dx[i]][Y + dy[i]]++; T[X + dx[i]][Y + dy[i]] %= 2; }
}
int main() {
	int n; cin >> n;
	for (int h = 0; h < n; h++) {
		for (int i = 1; i <= 10; i++) {
			for (int j = 1; j <= 10; j++)cin >> x[i][j];
		}

		for (int i = 0; i < (1 << 10); i++) {
			int bit[11]; for (int j = 0; j < 10; j++)bit[j + 1] = (i / (1 << j)) % 2;
			for (int j = 0; j < 12; j++) {
				for (int k = 0; k < 12; k++) { T[j][k] = 0; V[j][k] = 0; }
			}

			for (int j = 1; j <= 10; j++) {
				if (bit[j] == 1) {
					compute(1, j);
					V[1][j] = 1;
				}
			}
			for (int j = 2; j <= 10; j++) {
				for (int k = 1; k <= 10; k++) {
					if (T[j - 1][k] != x[j - 1][k]) {
						compute(j, k);
						V[j][k] = 1;
					}
				}
			}
			bool OK = true; for (int k = 1; k <= 10; k++) { if (T[10][k] != x[10][k])OK = false; }
			if (OK == true) {
				for (int j = 1; j <= 10; j++) {
					for (int k = 1; k <= 10; k++) {
						if (k >= 2)cout << ' '; cout << V[j][k];
					}
					cout << endl;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  vll p(n);re(i, n)std::cin >> p[i];
  ll c = 0;
  re(i, n-2) if(p[i]==i+1) swap(p[i], p[i+1]), c++;
  if(p[n-1]==n||p[n-2]==n-1) c++;
  std::cout << c << '\n';
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 10000007;
const int inf = 1001001001;


int main(void) {
  int n;
  cin >> n;
  vi w(n);
  rep(i,n) cin >> w[i];
  int ans = inf;
  rep(i,n-1){
    int dai = 0;
    int syou = 0;
    rep(j,n){
      if(j>i) dai+=w[j];
      else syou+=w[j];
    }
    ans = min(ans,abs(dai-syou));
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))

l = sum(a)

sum_1 = 0
split = 0
for i, x in enumerate(a):
    sum_1 += x
    if sum_1 > (l / 2):
        split = i
        break

sum_2 = sum_1 - a[split]

ans = min(2 * sum_1 - l, l - 2 * sum_2)
print(ans)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define DVSORT(v) sort(v.begin(), v.end(),greater<int>())
#define SORT(v, n) sort(v, v+n)
#define DSORT(v,n) sort(v, v+n,greater<int>())
#define vi vector<int>
#define pb push_back
#define P pair<int,int>


template <class T> void chmin(T&a, const T&b) { a = min(a,b); }
template <class T> void chmax(T&a, const T&b) { a = max(a,b); }

const double EPS =1e-9;
const long INF =2147483647;//32bit 2*1e+9
const long MOD =1e+9+7;
#define PI 3.14159265258979

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

int main(void){
	int N,L;
	vector<string> ve;
	cin>>N>>L;
	string S;

	REP(i,N){
		cin>>S;
		ve.pb(S);
	}
	VSORT(ve);
	for(auto itr=ve.begin();itr!=ve.end();itr++) cout<<*itr;
	cout<<endl;
	
	return 0; 
}



Measured memory_bytes: 256
S = input()
ans = 'WA'
from string import ascii_lowercase
if S[0] == 'A' and S[2:-1].find('C') != -1:
    j = S.find('C')
    k = 0
    for i,s in enumerate(S):
        if i == 0 or j == i:continue
        if s in ascii_lowercase:
            k += 1
    if k == len(S) - 2:
        ans = 'AC'
print(ans)


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

int main(void) {

	int S,h,m,s;
	cin >> S;
	h = S / 3600; S %= 3600;
	m = S / 60; s = S % 60;

	cout << h << ":" << m << ":" << s << endl;

	return 0;
}



Measured memory_bytes: 3112
#include<bits/stdc++.h>
#include<string>
#include<cmath>

using namespace std;

#define ll long long int
#define loop(i, n) for (int i = 0; i < n; i++)
#define loops(i, s, n) for (int i = s; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
#define MOD 1000000007

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

    int h1,h2,m1,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    h1*=60;
    h1+=m1;
    h2*=60;
    h2+=m2;
    int ans = (h2-h1)-k;
    cout<<ans;
}

Measured memory_bytes: 3588
import sys
readline = sys.stdin.readline
write = sys.stdout.write

L = 50000
sq = int(L**.5)
p = [1]*(L+1)
p[0] = p[1] = 0
pn = []
for x in range(sq+1):
    if not p[x]:
        continue
    for y in range(x*x, L+1, x):
        p[y] = 0
    pn.append(x)
for x in range(sq+1, L+1):
    if not p[x]:
        continue
    pn.append(x)
pp = [0]*(L+1)
L0 = len(pn)
for i in range(L0):
    x = pn[i]
    for j in range(i+1):
        z = x + pn[j]
        if z > L:
            break
        pp[z] += 1

def solve():
    N = int(readline())
    if N == 0:
        return False
    write("%d\n" % pp[N])
    return True
while solve():
    ...


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

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

    int a[n] = {};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] % 2 != 0) {
            cout << 0 << endl;
            return 0;
        }
    }
    int ans = 0;
    while (true) {
        for (int i = 0; i < n; i++) {
            if (a[i] % 2 == 0) {
                a[i] /= 2;
            } else {
                cout << ans << endl;
                return 0;
            }
        }
        ans++;
    }
}


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

ll N,a,total,ans,t;
ll cumu[200001];
int main(){
  cin>>N;
  cumu[0]=0; REP(i,N){ cin>>a; cumu[i+1]=cumu[i]+a;}
  total = cumu[N];
  ans = total;
  for(int i=1;i<N;++i){
    t = total-cumu[i]*2;
    if(abs(t)<ans){ans=abs(t);}
    if(t<=0){break;}
  }
  cout << ans<<"\n";
}

Measured memory_bytes: 1792
X,Y = map(int,input().split())
e = 0
temp_X = X
if Y%2 != 0:
    print("No")
    quit()
else:
    while temp_X >= 0:
        i = (temp_X*2) + (e*4)
        if i == Y:
            print("Yes")
            quit()
        temp_X -= 1
        e += 1
print("No")

Measured memory_bytes: 9188
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
typedef vector< vi > vvi;
int main() {
	int n, x, sum, count=0;
	while(cin >> n >> x){
		if (n == 0 && x == 0) {
			break;
		}
		else {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (j > i) {
						for (int k = 1; k <= n; k++) {
							if (k > j) {
								sum = i + j + k;
								if (sum == x) {
									count++;
								}
							}
						}
					}
				}
			}
			cout << count << endl;
			count = 0;
		}
	}
}

Measured memory_bytes: 1160
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])
ans, num = 1, []

if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        ans = ans * i % mod
    print(ans)
    exit()

for _ in range(k):
    if (len(mia) * len(pla) > 0 and abs(mia[-1]) <= pla[-1]) or len(mia) == 0:
        tmp = pla.pop()
    elif (len(mia) * len(pla) > 0 and abs(mia[-1]) > pla[-1]) or len(pla) == 0:
        tmp = mia.pop()
    num.append(tmp)

cnt = sum(i < 0 for i in num)
for i in num:
    ans = ans * i % mod

if cnt % 2 == 1:
    p, q, r, s = 1, 0, -1, 0
    if len(mia) > 0 and cnt != k:
        p, q = min(i for i in num if i >= 0), mia[-1]
    if len(pla) > 0:
        r, s = max(i for i in num if i < 0), pla[-1]
    if len(mia) > 0 or (len(pla) > 0 and cnt != k):
        if q * r >= p * s:
            ans *= q * pow(p, mod - 2, mod)
        if q * r < p * s:
            ans *= s * pow(r, mod - 2, mod)
    ans %= mod
print(ans)


Measured memory_bytes: 33244
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
typedef long long int ll;
typedef pair<int, int> P;
#define INF 1e9 + 7

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

    int n;
    cin >> n;
    ll a[n], b[n], c[n];
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n) cin >> c[i];
    
    sort(a, a+n);
    sort(b, b+n);
    sort(c, c+n);
    
    int vb[n], vc[n];
    
    //a -> b
    int idx = 0;
    rep(i,n){
        while(idx < n && a[idx] < b[i]){
            idx++;
        }
        
        vb[i] = idx;
    }
    //b -> c
    idx = 0;
    rep(i,n){
        while(idx < n && b[idx] < c[i]){
            idx++;
        }
        
        vc[i] = idx;
    }
    
    ll sum[n+1];
    sum[0] = 0;
    for(int i=1; i<n+1; i++){
        sum[i] = sum[i-1] + vb[i-1];
        // cout << sum[i] << endl;
    }
    
    ll ans = 0;
    rep(i,n){
        ans += sum[vc[i]];
    }
    
    cout << ans << endl;
    
    return 0;
}

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

int main(void){
	int x, a, b;

	cin >> x >> a >> b;
	if(a>=b){
		cout << "delicious" << endl;
	}else if(x < b-a){
		cout << "dangerous" << endl;
	}else{
		cout << "safe" << endl;
	}
}


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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#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 REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数


//ライブラリ挿入


int main(){
    int N;
    cin >> N;
    vector<ll> A(N+1);
    REP(i,N) cin >> A[i+1];
    ll ans=0;
    map<ll,int> A1,A2;
    REP2(i,2,N+1){
        A2[i-A[i]]++;
    }
    REP2(i,1,N+1){
        ans+=A2[A[i]+i];
        if(A2[i-A[i]]>0) A2[i-A[i]]--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 27360
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
using namespace std;
// type alias
typedef long long LL;
typedef vector < int > VI;
typedef unordered_map < int, int > MAPII;
typedef unordered_set < int > SETI;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// minmax
#define SMAX(a,b) a = max(a,b)
#define SMIN(a,b) a = min(a,b)
// debug cerr
#define TRACE false
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }

/*
 
 8/9/2018
 
 22:45-22:49 analysis
 22:50-23:02 AC
 
 Editorials:
  - https://img.atcoder.jp/abc070/editorial.pdf
  - https://youtu.be/v4aQTNiWS2A?t=2517
 
 */

// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG x.cpp && ./a.out
const int MAX_N=1e5+1;
int N,K;
LL A[MAX_N];
vector<pair<LL,int>> E[MAX_N];
LL D[MAX_N];

void dfs(int u, int pre, LL d) {
  D[u]=d;
  FORR(p,E[u]) {
    LL w; int v; tie(w,v)=p;
    if(v==pre) continue;
    dfs(v,u,d+w);
  }
}

void solve() {
  //D[K]=0;
  //FORR(p,E[K]) dfs(p.second,K,p.first);
  dfs(K,-1,0);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  
  cin>>N;
  REP(i,N-1) {
    int u,v; LL w; cin>>u>>v>>w;
    --u,--v;
    E[u].emplace_back(w,v);
    E[v].emplace_back(w,u);
  }
  int Q; cin>>Q>>K; --K;
  solve();
  REP(_,Q) {
    int u,v; cin>>u>>v;
    --u,--v;
    cout<<D[u]+D[v]<<endl;
  }
  return 0;
}


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

int main(void){
    // Your code here!
    ll n,k;
    cin>>n>>k;
    ld ans=0.;
    rep(0,i,n){
        ld tmp=1./n;
        ll now=(i+1);
        while(now<k){
            now*=2;
            tmp/=2;
        }
        ans+=tmp;
    }
    cout<< fixed << setprecision(14)<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try(Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			PriorityQueue<Integer> q = new PriorityQueue<>();
			int ans = 0;
			for(int i = 0 ; i < n ; i++) {
				int now = sc.nextInt();
				q.add(now);
				if(now == q.peek()) {
					ans++;
				}
			}

			System.out.println(ans);
		}

	}

}


Measured memory_bytes: 85960
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	LL w, h, x, y; cin >> w >> h >> x >> y;

	double area = (double)(w*h)*0.5;
	cout << fixed << setprecision(12) << area<<" ";


	if (2 * x == w && 2 * y == h) {
		cout << 1 << endl;
	}
	else {
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A;
  int N;
  int sho;
  int sabun;
 cin >> N >> A;
  sho = N/500;
  sabun = N - sho*500;
  if (sabun <= A) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
/* به نام یزدان */
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 3000 + 5;
long double p[MAX_N], dp[MAX_N][MAX_N];
int n;

void read_input() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> p[i];
}

void solve() {
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= n; j++) {
			dp[i][j] = (1 - p[i]) * dp[i - 1][j];
			if (j)
				dp[i][j] += p[i] * dp[i - 1][j - 1];
		}
}

void print_output() {
	long double ans = 0;
	for (int i = (n + 1) / 2; i <= n; i++)
		ans += dp[n][i];
	cout << fixed << setprecision(13);
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	read_input();
	solve();
	print_output();
}


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

typedef long long int ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
const ll mod = 1000000007;
const ll INF = 10010010010010010;

int main() {
    int n; cin >> n;
    double ans;
    if (n%2) ans = (double) (n/2+1) / (double) n;
    else ans = 0.5;
    cout << setprecision(15) << ans << endl;
    return 0;
}


Measured memory_bytes: 3764
while 1:
	N, Q = map(int,raw_input().split())
	if (N, Q) == (0,0):
		break
	era = dict()
	for i in range(N):	
		inputs = raw_input().split(" ")
		ename = inputs[0]
		eyear, wyear =map(int,inputs[1:])
		start = wyear - eyear + 1
		if start in era:
			if era[start][1] < wyear:
				era[start][1] = wyear
		else :
			era[start] = [ename, wyear]
	era_list = sorted(era)
	for i in range(Q):
		q = int(raw_input())
		for start in era_list:
			if q <= era[start][1]:
				result = "Unknown" if q < start else "%s %d" % (era[start][0], q - start+1)
				break
		else :
			result = "Unknown"
		print result

Measured memory_bytes: 4480
d=[11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381]
c=""
for i in range(int(input())):
    c+=str(d[i])+" "
print(c)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int a,b;
        a=sc.nextInt();
        b=sc.nextInt();
        if(a<b){
            System.out.println("a < b");
        }else if(a>b){
            System.out.println("a > b");
        }else{
            System.out.println("a == b");
        }
    }
}

Measured memory_bytes: 17156
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = na()

a.sort()
cu = [0] * (n + 1)
for i in range(n):
    cu[i + 1] = cu[i] + a[i]

ans = 1
for i in range(n - 2, -1, -1):
    if cu[i + 1] * 2 >= a[i + 1]:
        ans += 1
    else:
        break

print(ans)

Measured memory_bytes: 14404
import java.util.Scanner;

public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = S / 3600;
		S %= 3600;
		int m = S / 60;
		int s = S % 60;
		System.out.println(h+":"+m+":"+s);
	}
}

Measured memory_bytes: 26204
N,A,B,C,D=map(int,input().split())
A-=1
B-=1
C-=1
D-=1
S=input()
l=[0]*N
r=[0]*N
stack=[A]
dx=[1,2]
while(stack):
    x=stack.pop()
    l[x]=1
    for d in dx:
        X=x+d
        if X<0 or N<=X or l[X]==1 or S[X]=="#" or X>C:
            continue
        stack.append(X)
stack=[B]
dx=[1,2]
while(stack):
    x=stack.pop()
    r[x]=1
    for d in dx:
        X=x+d
        if X<0 or N<=X or r[X]==1 or S[X]=="#" or X>D:
            continue
        stack.append(X)
if C>D:
    t=False
    for i in range(N-3):
        if S[i:i+3]=="..." and l[i]==1 and r[i+1]==1:
            t=True
            break
    if t:
        if l[C]==1 and r[D]==1:
            print("Yes")
            quit()
    print("No")
else:
    if l[C]==1 and r[D]==1:
        print("Yes")
    else:
        print("No")


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

int main()
{
	int a, b, c, x;
	cin >> a >> b >> c;
	if (a > b)
	{
		x = a;
		a = b;
		b = x;
	}
	if (b > c)
	{
		x = b;
		b = c;
		c = x;
	}
	if (a > b) 
	{
		x = a;
		a = b;
		b = x;
	}

	cout << a << " " << b << " " << c << endl;

	return 0;
}


Measured memory_bytes: 3088
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		long[] a = new long[n];
		for (int i = 0;i < n;i++) {
			a[i] = Integer.parseInt(sc.next()) - i - 1;
		}
		Arrays.sort(a);
		long ans = 0;
		for (int i = 0;i < n;i++) {
			ans += Math.abs(a[i] - a[n / 2]);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 59692
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main(){
	int N;
	cin >> N; 
	int P = 0; int Q = 0; int R = 0; int S = 0; // 終わりA，はじめB，両方，内部 
	for(int i = 0; i < N; i++){
		string s; cin >> s; 
		for(int j = 0; j < s.size() - 1; j++){
			if(s[j] == 'A' && s[j+1] == 'B') S++; 
		}
		int L = s.size(); 
		if(s[0] == 'B' && s[L-1] == 'A') R ++; 
		else if(s[0] == 'B') Q ++; 
		else if(s[L-1] == 'A') P ++; 
	}
	if(P == 0 && Q == 0 && R == 0) cout << S << endl; 
	else if(P == 0 && Q == 0 && R > 0) cout << S + R - 1 << endl; 
	else cout << min(P, Q) + R + S << endl; 
}

Measured memory_bytes: 256
function Main(input) {
    var ans = 1;
    input = input.split("\n");
    for (var i = 0; i < input[0].length; i++) {
        if (input[0][i] != '1') {
            ans = input[0][i];
            break;
        }
    }
    if (i >= input[1]) ans = 1;
    console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 21064
x = int(input())

cad = x

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1
    
while True:
    
    flag = is_prime(cad)
    if flag:
        print(cad)
        break
    cad += 1
    

Measured memory_bytes: 2940
#include<iostream>
#include<map>
#include<utility>
using namespace std;
typedef pair<int,int> P;
map<P,int> d;
int w[100],v[100];
int n,W;

int dp(int i,int j){
	P p=make_pair(i,j);
	if(d.count(p)) return d[p];
	long long res;
	if(i==n) res=0;
	else if(j<w[i]) res=dp(i+1,j);
	else res=max(dp(i+1,j),dp(i+1,j-w[i])+v[i]);
	return d[p]=res;
}

int main(){
	cin >> n >> W;
	for(int i=0;i<n;i++){
		cin >> w[i] >> v[i];
	}
	cout << dp(0,W) << endl;
}


Measured memory_bytes: 6400
import java.util.Arrays;
import java.util.Scanner;
class Main{


	static char[][] map;

	static long[][] c;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] d = new int[n];
		for(int i = 0;i < n;i++){
			a[i] = sc.nextInt();
			d[i] = a[i];
 		}
		
		Arrays.sort(d);
		int max = d[n-1];
		int judge = 0;
		if(d[n-1] == d[n-2]){
			judge = 1;
		}
		
		if(judge == 1){
			for(int i = 0;i < n;i++){
				System.out.println(max);
	 		}
		}else{
			for(int i = 0;i < n;i++){
				if(a[i] == max){
					System.out.println(d[n-2]);
				}else{
					System.out.println(max);

				}
	 		}
		}

		
		
	}
	


	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}



class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   end- otherpair.end;
	}








}






Measured memory_bytes: 94056
#include <iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include <set>
#include <cassert>
#include<cmath>
#include<climits>
#include<iomanip>
using namespace std;
#define MOD 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
const long long INF = 1LL << 60;


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

class UnionFind {
	vector<int> data;
public:
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

int find(vector<long long> &arr, long long obj) {
	if (arr[arr.size() - 1] < obj)return arr.size()-1;
	if (arr[0] > obj)return -1;

	int min = 0; int max = arr.size() - 1;
	for (int i = 0; i < arr.size(); i++) {
		if (arr[min+(max-min) / 2] > obj) {
			max = min + (max - min) / 2;
		}
		else {
			min = min + (max - min) / 2;
		}
		if (max - min == 1) {
			return min;
		}
	}


}

//約数求める //約数
void divisor(ll n,vector<ll> &ret) {
	for (ll i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ret.push_back(i);
			if (i * i != n) ret.push_back(n / i);
		}
	}
	sort(ret.begin(), ret.end());
	
}
//階乗
long long factorial(long long n, long long mod) {
	long long ret = 1;
	for (long long i = 1; i <= n; i++) {
		ret = (ret * i) % mod;
	}
	return ret;
}
//モジュラ逆数
long long inv_mod(long long n, long long mod) {
	long long a = n % mod, b = mod - 2, ret = 1;
	while (b > 0) {
		if (b & 1) ret = (ret * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ret;
}

long long nPr(long long n, long long r, long long mod) {
	long long ret = 1;
	for (long long i = n; i >= n - r + 1; i--) {
		ret = ret * (i % mod) % mod;
	}
	return ret;
}

long long nCr(long long n, long long r, long long mod) {
	return nPr(n, r, mod) * inv_mod(factorial(r, mod), mod) % mod;
}

ll gcd(ll m, ll n){
	if (n == 0)return m;
	return gcd(n, m%n);
}//gcd



ll dp[3010][3010];
int main() {
	string s, t;
	cin >> s >> t;
	
	rep(i, s.size()) {
		rep(j, t.size()) {
			if (s[i] == t[j]) {
				
				chmax(dp[i + 1][j + 1], dp[i][j]+1);
			}
			else {
				chmax(dp[i + 1][j + 1], dp[i][j + 1]);
				chmax(dp[i + 1][j + 1], dp[i + 1][j]);
			}
		}
		
	}
	string ans;
	int x = s.size(); int y = t.size();
	ll l = dp[s.size()][t.size()];
	
	while (true) {
		if (l == 0)break;
		if (l == dp[x - 1][y]) {
			x--;
		}
		else if (l == dp[x][y - 1]) {
			y--;
		}
		else {
			x--; y--; l--;
			ans.push_back(s[x]);
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans;





	return 0;
}


Measured memory_bytes: 70784
fn main() {
    use std::io;

    let mut input = String::new();
    let _ = io::stdin().read_line(&mut input);
    let strings = input.trim().split_whitespace().collect::<Vec<_>>();

    let (afirst, atail) = strings[0].split_at(1);
    let (bfirst, btail) = strings[1].split_at(1);
    let (cfirst, _) = strings[2].split_at(1);

    let alast = atail.to_string().pop().unwrap_or(afirst.clone().to_string().pop().unwrap());
    let blast = btail.to_string().pop().unwrap_or(bfirst.clone().to_string().pop().unwrap());

    if alast.to_string() == bfirst.to_string() && blast.to_string() == cfirst.to_string() {
        println!("YES");
    } else {
        println!("NO");
    }

}

Measured memory_bytes: 4352
import java.util.Scanner;
 
class Main {
 
    public static void main(String[] args) {
        // TODO ?????????????????????????????????????????????
        Scanner sc = new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        if(a<b&&b<c) System.out.println("Yes");
        else System.out.println("No");
 
    }
 
}


Measured memory_bytes: 26216
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int main() {
	int map[3][3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}
	int a[3], b[3];
	for (int i = 0; i < 3; i++) {
		int ans = 200;
		for (int j = 0; j < 3; j++) {
			a[i] = min(ans, map[i][j]);
			ans = a[i];
		}
	}

	for (int i = 0; i < 3; i++) {
		b[i] = map[0][i] - a[0];
	}

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (a[i] + b[j] != map[i][j]) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second

string s;

signed main(){
	int n;
	cin>>n;
	int a[n];
	r(i,n)cin>>a[i];
	int s=0,x=0;
	r(i,n){
		if(a[i]>=x)s++;
		x=max(a[i],x);
	}
	cout<<s<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define f first
#define s second
#define nax (int)1e5+2
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define newline cout<<"\n"
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n" 
#define INF (int)1e5
using namespace std;


int main(){
	int n,x;
	cin>>n>>x;
	vector<int> v(n+1);
	v[0] = 0;
	int ans = 1;
	for(int i =1;i<=n;i++){
		cin>>v[i];
		v[i] = v[i-1]+v[i];
		if(v[i] <= x)
			ans = i;
	}
	
	cout<<ans+1;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

vector<ll> pf(ll n){
	vector<ll> v;
	for(ll i=2;i*i<=n;i++){
		while(n%i==0LL){
			v.push_back(i);
			n/=i;
		}
	}

	if(n!=1LL) v.push_back(n);

	return v;
}

int main(void){
	          ll i,j;

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

	          ll N,P;
	          cin >> N >> P;

	          vector<ll> u=pf(P);
	          ll n=u.size();

	          map<ll,ll> mp;

	          for(i=0;i<n;i++){
	        	  mp[u[i]]++;
	          }

	          ll ans=1LL;
	          foreach(mp,itr){
	        	  if((*itr).second>=N){
	        		  for(j=1;j<=(*itr).second/N;j++){
	        			  ans*=(*itr).first;
	        		  }

	        	  }
	          }

	          cout << ans << endl;

	          return 0;
}


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

int N,cnt;

void solve(long long now,int check){
    if(now > N) return;
    if(check == 0b111) cnt++;
    solve(now*10+3,check | 0b001);
    solve(now*10+5,check | 0b010);
    solve(now*10+7,check | 0b100);
}

int main(){
    cin>>N;
    cnt = 0;
    solve(0,0b000);
    cout<<cnt<<endl;

    return 0;
}

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

int main(){
  int n , h ;
  int ans = 0;
  int saidai = 0 ;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> h ;
    if(saidai<=h) {
      ans++;
      saidai = h;
    }
  }
    
  cout << ans << endl;
}



Measured memory_bytes: 3628
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a,b,c,x,ans=0;
  cin >> a >> b >> c >> x;
  FOR(i,0,a+1) {
    FOR(j,0,b+1) {
      FOR(k,0,c+1) {
        if(500 * i + 100 * j + 50 * k == x) ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define all(v) v.begin(), v.end()
#define repi(i, n, init) for (ll i = init; i <= (n); i++)
#define repd(i, n, init) for (ll i = (n); i >= init; i--)
#define repm(i, m) for (auto i = m.begin(); i != m.end(); i++)
#define repb(bit, n, init) for (ll bit = init; bit < (1 << n); ++bit)

int main()
{
    ll n;
    cin >> n;
    repi(i, n, 1)
    {
        if (i % 3 == 0)
        {
            cout << " " << i;
        }
        else if (i % 10 == 3 || (i / 10) % 10 == 3)
        {
            cout << " " << i;
        }
        else
        {
            ll tmp = i;
            while (tmp /= 10)
            {
                if (tmp % 10 == 3)
                {
                    cout << " " << i;
                    break;
                }
            }
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3104
def solve(x):
    cnt = 1
    while x > 0:
        x %= bin(x).count('1')
        cnt += 1
    return cnt

n = int(input())
x = input()
one = sum(map(int, list(x)))
num = int(x, 2)

up = num%(one+1)
if one == 1:
    down = 0
else:
    down = num%(one-1)

for i in range(n):
    if x[i] == '1':
        if one == 1:
            print(0)
            continue
        s = (down - pow(2, n-i-1, one-1))%(one-1)
    else:
        s = (up + pow(2, n-i-1, one+1))%(one+1)
    print(solve(s))

Measured memory_bytes: 10588
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using T = tuple<string,int,int>;

int main(){
  ll a,b,n; cin >> a >> b >> n;
  ll ans = 0;
  if(n < b){
    ans = (a*n)/b;
  }else{
    ans = (a*(b-1))/b;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
X, N = map(int, input().split())
judge = 102*[1]
if N==0:
	print(X)
	exit()

P = list(map(int, input().split()))
for i in range(N):
	judge[P[i]] = 0

upcnt = 0
while judge[X+upcnt]==0:
	upcnt+=1

downcnt = 0
while judge[X-downcnt]==0:
	downcnt+=1

if upcnt < downcnt:
	print(X+upcnt)
else:
	print(X-downcnt)




Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
int E[50][50],F[50][50],mem[31][51][6],used[31][51][6];
int D,c,X,W;

int dfs(int d,int cost,int x){
  if(D==d)return 0;
  if(used[d][cost][x]) return mem[d][cost][x];
  used[d][cost][x]=1;
  
  int res=dfs(d+1,cost,x);  

  for(int i=0;i<c;i++){
    int ncost=cost+F[i][d];
    if(ncost>W)continue;
    if(!E[i][d]||ncost>W)continue;
    res=max(res,dfs(d+1,ncost,x)+E[i][d]);
    
    if(x>=X)continue;
    int ee=E[i][d],cc=cost+F[i][d];
    for(int j=i+1;j<c;j++){
      ee+=E[j][d],cc+=F[j][d];
      if(!E[j][d]||cc>W)break;
      res=max(res,dfs(d+1,cc,x+1)+ee);
    }
    
    ee=E[i][d],cc=cost+F[i][d];
    for(int j=i-1;j>=0;j--){
      ee+=E[j][d],cc+=F[j][d];
      if(!E[j][d]||cc>W)break;
      res=max(res,dfs(d+1,cc,x+1)+ee); 
    }
  }
  return mem[d][cost][x]=res;
}

int main(){
  while(1){
    cin>>c>>D>>W>>X;
    if(!c&&!D&&!W&&!X) break;
    memset(used,0,sizeof(used)), memset(mem,0,sizeof(mem));
    for(int i=0;i<c;i++)for(int j=0;j<D;j++) cin>>E[i][j];
    for(int i=0;i<c;i++)for(int j=0;j<D;j++) cin>>F[i][j];
    cout << dfs(0,0,0)<<endl;
  }
  return 0;
}

Measured memory_bytes: 1252
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip>
using namespace std;
#define int long long

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

    int n; cin >> n;
    vector<int> yakusu(10000001,2);
    yakusu.at(1) = 1;
    for(int i = 2;i <= 5000000;i ++){
        for(int j = 2;;j ++){
            if(i * j >= 10000001) break;
            yakusu.at(i * j) ++;
        }
    }    

    int ans = 0;

    for(int i = 0;i < n+1;i ++) ans += i * yakusu.at(i);

    cout << ans << endl;
}

Measured memory_bytes: 81320
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main(){
  int n,k;
  cin >> n >> k;
  if (n % k == 0){
    cout << "0\n";
  }
  else{
    cout << "1\n";
  }
  return 0;
}

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

using namespace std;

#define LL long long
#define reg register
#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a )
#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a )
#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a )
#define debug(x) cerr<<#x<<" = "<<x<<endl;

template<class T>inline bool Max(T &a,T b) {
	return a<b?a=b,1:0;
}
template<class T>inline bool Min(T &a,T b) {
	return a>b?a=b,1:0;
}

inline int Read(void) {
	int res=0,flag=1;
	char c;
	while(c=getchar(),c<48||c>57)if(c=='-')flag=0;
	do res=(res<<1)+(res<<3)+(c^48);
	while(c=getchar(),c>=48&&c<=57);
	return flag?res:-res;
}

const int N=2e3+5,M=1e6+5,mod=1e9+7;
const int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};

int n,m,dp[N][N],S[N],T[N];

int dfs(int x,int y){
	if(~dp[x][y])return dp[x][y];
	if(x==0||y==0)return 1;
	int res=0;
	if(S[x]==T[y])res=dfs(x-1,y-1);
	res=(res+dfs(x-1,y)+dfs(x,y-1)-dfs(x-1,y-1))%mod;
	res=(res+mod)%mod;
	dp[x][y]=res;
	return dp[x][y];
}

int main(void) {
	memset(dp,-1,sizeof dp);
	n=Read(),m=Read();
	rep(i,1,n)S[i]=Read();
	rep(i,1,m)T[i]=Read();
	printf("%d",dfs(n,m));
	return 0;
}

Measured memory_bytes: 16256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 18 + 2 ;
int n ;
ll dp[N][N] , ans ;
string s ;

inline int get (int mask) {
	memset(dp , 0 , sizeof dp) ;
	string a = "" , b = "" ;

	for (int i = 0 ; i < n ; i ++) {
		if (mask >> i & 1) a += s[i] ;
		else b += s[i] ;
	}

	dp[0][0] = 1 ;
	for (int i = 0 ; i <= _sz(a) ; i ++) {
		for (int j = 0 ; j <= _sz(b) ; j ++) {
			if (i < _sz(a) && s[2 * n - i - j - 1] == a[i]) dp[i + 1][j] += dp[i][j] ;
			if (j < _sz(b) && s[2 * n - i - j - 1] == b[j]) dp[i][j + 1] += dp[i][j] ;
		}
	}

	return dp[_sz(a)][_sz(b)] ;
}

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

	cin >> n ;
	cin >> s ;

	for (int mask = 0 ; mask < (1 << n) ; mask ++) ans += get(mask) ;

	cout << ans << '\n' ;
}

Measured memory_bytes: 256
#!/usr/bin/env python2

import sys

input = iter(sys.stdin.readlines()).next

def main():
   S = input().strip()
   T = input().strip()
   print('Yes' if T[:-1] == S else 'No')

   return 0

if __name__ == '__main__':
   sys.setrecursionlimit(10000)
   main()


Measured memory_bytes: 85056
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

const int MAXN = 1000*1000 + 7;
const int SS = 1<<20;
const int INF = 1000*1000*1000 + 7;


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

	int T;
	//cin >> T;
	T = 1;
	while(T--)
	{
		long long a, b, c, d;
		cin >> a >> b >> c >> d;
		cout << max({a*c, a*d, b*c, b*d}) << '\n';
	}
	return 0;
}


Measured memory_bytes: 3652