akhauriyash/Code-Regression huggingface dataset:
// arc082.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
// 22:00~13, 13~27
// 448ms
// 意識したこと：組み込みのソフトでも使用できるように

#include <iostream>
#include <fstream>
#include <time.h>

//#define _DEBUG (true)
#define _DEBUG (false)

# define ELEM_MAX_SIZE (100000)

unsigned int a[ELEM_MAX_SIZE];
unsigned int N = 0;
unsigned int result = 0;

// a[n]=value の時、counter[value]をインクリメントする。
unsigned int counter[ELEM_MAX_SIZE + 1];

void input() {
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		std::cin >> a[i];
	}
}


void solve() {
	for (int i = 0; i < N; i++) {
		counter[a[i]]++;
		if(a[i] != 0) counter[a[i]-1]++;
		if(a[i] != ELEM_MAX_SIZE) counter[a[i]+1]++;
	}

	// get max value in counter
	for (int i = 0; i < ELEM_MAX_SIZE + 1; i++) {
		if (result < counter[i]) {
			result = counter[i];
		}
	}
}

void output() {
	std::cout << result << std::endl;
}

int main()
{
#if(_DEBUG)
	// 標準入力をファイルに変更
	std::ifstream in("input.txt");
	std::cin.rdbuf(in.rdbuf());

	// 処理時間計測用
	clock_t start, end;
	start = clock();
#endif

	// 入力部
	input();

	// 処理部
	solve();

	// 出力部
	output();

#if(_DEBUG)
	// 処理時間を表示
	end = clock();
	std::cout << "処理時間：" << (double)(end - start) << "[ms]";
	getchar();
#endif
}

Measured memory_bytes: 1024
<?php
fscanf(STDIN, "%d", $n);

$count = 0;
for ($i = 0; $i < $n; $i++) {
    fscanf(STDIN, "%d", $num);

    if (is_prime($num)) {
        $count += 1;
    }
}

echo "$count\n";

function is_prime($num)
{
    $last = floor(sqrt($num));

    for ($d = 2; $d <= $last; $d++) {
        if (0 == $num % $d) {
            return false;
        }
    }

    return true;
}

Measured memory_bytes: 6616
#include <iostream>
#include <utility>

using namespace std;

void output(int n, int element[])
{
	for (int i = 0; i < n - 1; i++)
		cout << element[i] << " ";
	cout << element[n - 1] << endl;
}

int bubble_sort(int n, int element[])
{
	int swap_count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = n - 1; i < j; j--) {
			if (element[j] < element[j - 1])
				swap(element[j], element[j - 1]), swap_count++;
		}
	}
	return swap_count;
}

int main()
{
	int n, element[100];

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> element[i];
	}
	int swap_count = bubble_sort(n, element);
	output(n, element);
	cout << swap_count << endl;
	return 0;
}

Measured memory_bytes: 1164
package main
import . "fmt"
func main() {
  var a,b,c,d int
  Scan(&a,&b,&c,&d)
  if a > d || c > b {
    Println(0)
  } else {
    Println(min(b,d)-max(a,c))
  }
}
func min(m int,n int) int {
  if m < n {
    return m
  } else {
    return n
  }
}
func max(m int,n int) int {
  return m+n-min(m,n)
}


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

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

    vector<int64_t> h(N);
    for(int i=0;i<N;i++) {
        cin >> h[i];
    }

    sort(h.begin(), h.end());
    cout << N-distance(h.begin(), lower_bound(h.begin(), h.end(), K)) << "\n";
    return 0;
}


Measured memory_bytes: 1024
#import<ios>
int D,c,a;char s[9];main(){for(;c+21&&scanf("%s",s);a+=D/64)c=*s-69,D=c==9?D*8&448|63-D/8&56|D&7:c==14?511-D*8&448|D/8&56|D&7:!c?511-D*64&448|D&56|D/64&7:c==18?D*64&448|D&56|7-D/64&7:c==13?D&448|D*8&56|7-D/8&7:c==7?D&448|63-D*8&56|D/8&7:(a&&printf("%d\n",a),a=0,83);}

Measured memory_bytes: 0
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;

ll n, a[114514], b[114514];

int main(){
  cin >> n;
  for(int i=0;i<=n;i++) cin >> a[i];
  for(int i=0;i<n;i++) cin >> b[i];
  
  ll ans = 0;
  for(int i=0;i<=n;i++){
    ll x = min(a[i], b[i]);
    ans += x;
    b[i] -= x;
    if (i<n){
	  x = min(a[i+1], b[i]);
      ans += x;
      a[i+1] -= x;
    }
  }
  cout << ans << endl;
  return 0;
}
  
  

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int main()
{
    ll x,y;
    scanf("%lld%lld",&x,&y);
    for(ll i=62;i>=0;i--){
        ll k=(ll)pow(2,i);
        ll ans=y/k;
        if(ans>=x){
            printf("%lld\n",i+1);
            return 0;
        }
    }
    printf("0\n");
}


Measured memory_bytes: 384
#include <iostream>

auto Pow(std::uint64_t base, std::size_t i) {
    auto result = std::uint64_t(1);

    while (i > 0) {
        if (i % 2 == 0) {
            base *= base;
            i /= 2;
        } else {
            result *= base;
            i--;
        }
    }

    return result;
}

int main() {
    auto s = std::string();
    std::cin >> s;

    auto sum = std::uint64_t(0);
    for (auto i = std::size_t(0); i < s.size(); ++i) {
        const auto num = static_cast<std::uint64_t>(s[i] - '0');

        auto pow_2 = Pow(2, i);
        auto pow_10 = Pow(10, s.size() - 1 - i);

        sum += num * pow_10 * pow_2;

        while (pow_10 > 0) {
            pow_10 /= 10;

            sum += num * pow_10 * pow_2;

            pow_2 *= 2;
        }
    }
    std::cout << sum << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int tmp,num;
  float even;
  scanf("%d",&tmp);
  if(tmp%2 == 0)
    even = 0.5;
  else{
    num = (tmp+1)/2.0;
    even = (float)num/tmp;
  }
  printf("%f",even);
  return 0;
}
  

Measured memory_bytes: 128
Q, H, S, D = map(int, input().split())
N = int(input())

if N%2:
    if D < 2*min(Q*4, H*2, S):
        # 2L サイズの容量あたり単価が一番安いときは、N//2本買う
        # 残りは1Lになるので、0.25L,0.5L,1Lのなかから最も容量あたり単価が安いものを買う
        print(N//2*D+min(Q*4, H*2, S))
    else:
        # 0.25L,0.5L,1Lのなかから最も容量あたり単価が安いものを買う
        print(N*min(Q*4, H*2, S))
else:
    #0.25L,0.5L,1L,2Lのなかから最も容量あたり単価が安いものを買う
    print(N*min(Q*8, H*4, S*2, D)//2)

Measured memory_bytes: 3064
def search(data, key):
    cnt = 0
    left, right = -1, len(data)

    while right - left > 1:
        mid = (left + right) // 2
        cnt += 1
        if data[mid] == key: break
        elif data[mid] > key:
            right = mid
        else:
            left = mid

    return cnt

def solve():
    N = int(input())
    if N == 0: return -1
    data = [int(input()) for i in range(N)]
    k = int(input())
    return search(data, k)

while True:
    ans = solve()
    if ans == -1: break
    print(ans)


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

using namespace std;
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
typedef vector<ll> vll;
typedef vector<int> vi;
const ll N = 2e6 + 10;
const int M = 1e9 + 7;
const double eps = 1e-9;

int main() {
    int x, y;
    cin >> x >> y;
    for (int i = 0; i <= x; ++i) {
        if (2 * i + 4 * (x - i) == y)
            return cout << "Yes" << endl, 0;
    }
    cout << "No" << endl;
}



Measured memory_bytes: 3644
from math import ceil
from heapq import heappush, heappop, heapify

n, m = map(int, input().split())
a = list((map(lambda x:int(x) * -1, input().split())))
heapify(a)

for _ in range(m):
    price = heappop(a)
    heappush(a, price / 2)
print(sum(ceil(_) for _ in a) * -1)


Measured memory_bytes: 14380
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();
        
        System.out.println(Character.toString(a.charAt(0)) + b.charAt(1) + c.charAt(2));
    }
}


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

typedef pair<int, int> pii;

const int mod = 1000*1000*1000+7;

int N;
vector<pii> P, seg;
vector<int> X;
map<int, int> dx;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4*N, -1e9);
    }
    void upd(int idx, int val, int l, int r, int n) {
        if(idx < l || r < idx) return;
        if(l == r) {
            tree[n] = val;
            return;
        }
        int m = (l + r)>>1;
        upd(idx, val, l, m, 2*n);
        upd(idx, val, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e9;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit1, bit2;

int dp[200010], psum[200010];

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

    P.resize(N);
    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);

        X.push_back(P[i].second);
    }

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

    sort(X.begin(), X.end());
    for(int i = 0; i < N; i++) dx[X[i]] = i;

    bit1.init();
    bit2.init();
    for(int i = 0; i < N; i++) {
        bit1.upd(i, P[i].second, 0, N - 1, 1);
        bit2.upd(i, -P[i].second, 0, N - 1, 1);
    }

    seg.resize(N);
    for(int i = 0; i < N; i++) {
        seg[i].first = dx[ -bit2.quer(i, N - 1, 0, N - 1, 1) ];
        seg[i].second = dx[ bit1.quer(0, i, 0, N - 1, 1) ];
    }

    seg.push_back(pii(N, N));
    dp[N] = 1;
    psum[N] = 1;
    int pos = N;

    for(int i = N - 1; i >= 0; i--) {
        while(seg[i].second + 1 < seg[pos].first) pos--;

        dp[i] = psum[i + 1] + mod - psum[pos + 1];
        dp[i] %= mod;
        psum[i] = dp[i] + psum[i + 1];
        psum[i] %= mod;
    }

    int ans = 0;
    for(int i = 0; i < N; i++) if(seg[i].first == 0) {
        ans += dp[i];
        ans %= mod;
    }

    printf("%d", ans);
}


Measured memory_bytes: 22772
#include<iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <queue>

using namespace std;

long long maxPoint(long long N,long long M,long long r1,long long r2,long long r3,vector<long long>X,vector<long long>Y,vector<long long>Z){
    long long* maxPoints = new long long[N+1];
    for (int i = 1;i<= N;i++){
        for (int j = i;j>0;j--){
            if (j ==i){
                maxPoints[j] = maxPoints[j-1]+ r1 * X[i-1]+ r2 * Y[i-1]+ r3 *Z[i-1];
            }else{
                maxPoints[j] = max(maxPoints[j],maxPoints[j-1]+ r1 * X[i-1]+ r2 * Y[i-1]+ r3 *Z[i-1]);
            }
        }
    }
    return maxPoints[M];
}

int main()
{
        // 整数の入力
    long long N,M,xi,yi,zi;
    cin >> N>> M;
    vector<long long> X,Y,Z;
    long long* maxPoints = new long long[N+1];
    maxPoints[0] = 0;
    for (int i = 1;i<= N;i++){
        cin >> xi >> yi >> zi;
        X.push_back(xi);
        Y.push_back(yi);
        Z.push_back(zi);
    }
    long long real_max =maxPoint(N,M,1,1,1,X,Y,Z);
    long long temp = maxPoint(N,M,1,1,-1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }
    temp = maxPoint(N,M,1,-1,1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    temp = maxPoint(N,M,1,-1,-1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    temp = maxPoint(N,M,-1,1,1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    temp = maxPoint(N,M,-1,1,-1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    temp = maxPoint(N,M,-1,-1,1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    temp = maxPoint(N,M,-1,-1,-1,X,Y,Z);
    if (real_max < temp){
        real_max = temp;
    }

    cout << real_max << endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


ll v[55];

int main(){
    int n, k;
    cin >> n >> k;
    rep(i, n) cin >> v[i];

    int m = min(n, k);

    ll ans = 0;

    rep(i, m+1){ // i個取り出す時を考える
        rep(l, i+1){
            vector<ll> tmp;
            rep(j, l) tmp.push_back(v[j]);
            int r = i - l;
            // cout << l << " " << r << endl;
            for(int j = n-1; j >= n - r; j--) tmp.push_back(v[j]);
            // rep(j, tmp.size()) cout << tmp[j] << " ";
            // cout << endl;

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

            int res = k - (l+r);
            ll s = 0;
            rep(j, tmp.size()){
                if (tmp[j] < 0 && res > 0){
                    res--;
                }
                else s += tmp[j];
            }
            ans = max(s, ans);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>


using std::cout;
using std::cin;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


ll gcd(ll a, ll b) {
    while (b != 0) {
        auto tmp = a;
        a = b;
        b = tmp % a;
    }
    return a;
}

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




void oneCase () {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int x = 0;
    int best = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'I') {
            ++x;
        } else {
            --x;
        }
        best = max(best, x);
    }
    cout << best << "\n";

}





int main() {
    int t = 1;
//    cin >> t;
    while (t > 0) {
        oneCase();
        --t;
    }

    return 0;
}

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

short pref[5005][5005];
short suf[5005][5005];

int main() {
    //ifstream cin("f.iun");
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for (int x, i = 1; i <= n; ++ i) {
        cin >> x;
        if (x < k) {
            v.push_back(x);
        }
    }
    n = v.size();
    for (int i = 0; i < k; ++ i) {
        pref[0][i] = 1;
    }
    for (int i = 1; i <= n; ++ i) {
        int val = v[i - 1];
        for (int j = k - val - 1; j >= 0; -- j) {
            if (pref[i - 1][j] - (j ? pref[i - 1][j - 1] : 0)) {
                pref[i][j + val] = 1;
            }
        }
        for (int j = 0; j < k; ++ j) {
            if (pref[i - 1][j] - (j ? pref[i - 1][j - 1] : 0)) {
                pref[i][j] = 1;
            }
            if (j) {
                pref[i][j] += pref[i][j - 1];
            }
        }
    }
    for (int i = 0; i < k; ++ i) {
        suf[n + 1][i] = 1;
    }
    for (int i = n; i >= 1; -- i) {
        int val = v[i - 1];
        for (int j = k - val - 1; j >= 0; -- j) {
            if (suf[i + 1][j] - (j ? suf[i + 1][j - 1] : 0)) {
                suf[i][j + val] = 1;
            }
        }
        for (int j = 0; j < k; ++ j) {
            if (suf[i + 1][j] - (j ? suf[i + 1][j - 1] : 0)) {
                suf[i][j] = 1;
            }
            if (j) {
                suf[i][j] += suf[i][j - 1];
            }
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; ++ i) {
        bool ok = false;
        for (int j = 0; j < k; ++ j) {
            if ((j == 0 && pref[i - 1][j]) || (j != 0 && pref[i - 1][j] - pref[i - 1][j - 1])) {
                int min_sum_right = max(k - v[i - 1] - j, 0);
                int max_sum_right = k - 1 - j;
                if ((min_sum_right == 0 && suf[i + 1][max_sum_right]) || (min_sum_right != 0 && suf[i + 1][max_sum_right] - suf[i + 1][min_sum_right - 1])) {
                    ok = true;
                    break;
                }
            }
        }
        if (!ok) {
            ++ cnt;
        }
    }

    cout << cnt << "\n";


    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int N = nextLong();
  ll D = nextLong();
  int ans = 0;
  REP(i, N) {
    ll x = nextLong();
    ll y = nextLong();
    if (D*D >= x*x + y*y) ans++;
  }
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

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

typedef long long ll;

const ll MOD = 1000000007;

ll modPow(ll a, ll n) {
  ll x = 1;
  for (ll i = 1; i <= n; i++) {
    x = x * a % MOD;
  }
  return x;
}

int main() {
  ll N;
  cin >> N;
  ll ans = modPow(10, N) - modPow(9, N) - modPow(9, N) + modPow(8, N);
  ans %= MOD;
  ans = (ans + MOD) % MOD;
  cout << ans << endl;
}


Measured memory_bytes: 3592
import scala.math.BigInt

object Main extends App {
  
  val sc = new java.util.Scanner(System.in)
  val n = sc.nextInt()
  val mod = BigInt(math.pow(10, 9).toLong + 7)
  val all = BigInt(10).pow(n)
  val no = BigInt(9).pow(n) + BigInt(9).pow(n) - BigInt(8).pow(n)
  val ans = (all - no) % mod
  println(ans)
}

Measured memory_bytes: 100712
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> H(N);
    REP(i, N) { cin >> H.at(i); }
    sort(ALL(H), greater<ll>());

    ll ans = 0;
    FOR(i, K, N) { ans += H[i]; }

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


Measured memory_bytes: 1792
"""

(N-1)(N+1) = N^2 - 1
(N-2)(N+2) = N^2 - 4

A,Bが等しいときは、上の式に基づいて2*(A-1)人小さい人を作れる

A,Bが等しくないときは、同じように作るとすると

(A-x)*(B+x) = AB + (A-B)x - x^2
なので、(A-B)x - x^2 < 0 → (A-B) < x
よって、A < B ならば、A-1…1まですべて使用可能。
A>Bならば、 A- (A-B+1) … 1まで使用可能

どちらか片方が高橋君より小さいことは必須→A,B中片方は範囲外の数字で全て無駄なく使ってしまう
残りは使える個数に制限があるけど、できるだけ使ってしまうのでこれで最適かな
→だめだった！！！！

=====けんちょんさんのブログ参照=========

A,Bから小さい方から同じ数だけ使っていくのが最適なのは自明
高橋君のA,Bを除いてA,BからNこずつ取ってくるとする。
最大値を最小化するには、大きい方からx番目と小さい方からx番目をマッチングする
→真ん中らへんに最大値が来るはず
最大値を無理やり求めてあげる→最大値がtA*tBを超えない最大のNを2分探索!!
"""
def kth(m,k):
    if m >= k:
        return m+1
    else:
        return m

def wantmax(m,A,B): #mコとった時の最大値計算(真ん中らへんを探索)

    ret = 0

    for i in range(-10,10):

        now = m // 2 + i
        
        if 0 < now <= m:

            ret = max( ret , kth(now,A) * kth(m-now+1,B) )

    return ret
        
            

Q = int(input())

for loop in range(Q):

    A,B = map(int,input().split())

    l = 0
    r = A*B

    while r -l != 1:
        m = (r+l) // 2

        ret = wantmax(m,A,B)
        #print (m,ret)

        if ret >= A*B:
            r = m
        else:
            l = m

    print (l)

Measured memory_bytes: 47468
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
//#define ll __int64
#define ll long long
const int INF=1000000007;
int n;
vector<P>G[111111];//to,dist
ll d[111111];
bool visit[111111];
int q,k,a,b;


void dfs(int now){
	
	rep(i,G[now].size()){
		int next=G[now][i].first;
		int w=G[now][i].second;

		if(visit[next])continue;//訪問済みなら打ち切り

		visit[next]=1;
		d[next]=d[now]+w;
		dfs(next);
	}

}

int main(){
int n;
cin>>n;
int a,b,c;
rep(i,n-1){
	cin>>a>>b>>c;
	a--;
	b--;

	G[a].pb(mp(b,c));
	G[b].pb(mp(a,c));
}



cin>>q>>k;
k--;
visit[k]=1;

dfs(k);

//rep(i,n)cout<<d[i]<<" ";cout<<endl;

rep(i,q){
	cin>>a>>b;
	a--;b--;
	cout<<d[a]+d[b]<<endl;
}


	return 0;
}


/*#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
//#define ll long long
int n,m,r;
int G[500][500];
int d[500][500];
vector<int>visit;
int ans;
 
const int INF=1000000000;
 
int main(){
cin>>n>>m>>r;
 
int a,b,c;
rep(i,r){
	cin>>a;
	a--;
	visit.push_back(a);
}
 
rep(i,n){
	rep(j,n)d[i][j]=(i==j)?0:INF;
}
 
rep(i,m){
	cin>>a>>b>>c;
	a--;b--;
	G[a][b]=G[b][a]=c;
	d[a][b]=d[b][a]=c;
}
 
rep(k,n){
	rep(i,n){
		rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}
}
 
ans=INF;
do{
	int tmp=0;
	for(int i=1;i<r;i++)tmp+=d[visit[i-1]][visit[i]];
	ans=min(ans,tmp);
}while(next_permutation(visit.begin(),visit.end()));
 
cout<<ans<<endl;
 
 
	return 0;
}*/

Measured memory_bytes: 13056
n = int(input())
s = [list( input().split() ) for i in range(n)]
c = [0, 0, 0, 0]

for i in range(n):
  if s[i] == ['AC']:
    c[0] += 1
  if s[i] == ['WA']:
    c[1] += 1
  if s[i] == ['TLE']:
    c[2] += 1
  if s[i] == ['RE']:
    c[3] += 1
    
print('AC x', c[0])
print('WA x', c[1])
print('TLE x', c[2])
print('RE x', c[3])

Measured memory_bytes: 91096
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
          fozubaoyou    no BUGs alive
*/
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

bool isPrime(int x) {
    if (x == 2) return true;
    if (x < 2 || x%2 == 0) return false;
    int i = 3;
    while (i <= (int)sqrt(double(x))) {
        if (x%i == 0) return false;
        i++;}
    return true;
}

int main(){
    int n, r = 0; cin >> n;
    REP(i, n) {
        int x; cin >> x;
        if (isPrime(x)) r++;}
    cout << r << endl;
}

Measured memory_bytes: 3100
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
#define p(s) std::cout << s ;
#define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}

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;
}
int main() {
    ll n;
    cin >> n;
    vector<pair<ll,ll> >v;
    rep(i, 0, n) {
        ll x, l; cin >> x >> l;
        v.push_back(make_pair(x+l, x-l));
    }
    sort(v.begin(), v.end());
    ll mn = -INF; 
    ll ans = 0;
    rep(i, 0, n) {
        ll r = v[i].first;
        ll l = v[i].second;
        if (mn <= l) {
            mn = r;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2420
#if __has_include("D:/dhiraj/Programming/debug.h")
    #include "D:/dhiraj/Programming/debug.h"
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 11
#endif

// Loops --------------------------------------------------------------------

#define loop(i,s,e)         for(ll i=(s); i<(e); i++)
#define rloop(i,s,e)        for(ll i=(s); i>=(e); i--)
#define iter(it,var)        for(auto it=var.begin(); it!=var.end(); it++)
#define riter(it,var)       for(auto it=var.rbegin(); it!=var.rend(); it++)

// Extra --------------------------------------------------------------------

#define ull                 unsigned long long int
#define ll                  long long int
#define ld                  long double
#define endl                '\n'
#define all(x)              x.begin(),x.end()
#define rall(x)             x.rbegin(),x.rend()

// Template -----------------------------------------------------------------

template <typename T> 
inline bool inrange(T a, T l, T r) {
    if(l>r) swap(l,r);
    return (a>=l and a<=r);
}
template <typename T, typename U> 
inline bool exist(T val, U &any) {
    return (any.find(val) != any.end());
}
// multiple input
template <typename T> 
inline void inp(T &any) {
    cin >> any;
}
template <typename T, typename... U> 
inline void inp(T &a, U &...b) {
    cin >> a; inp(b...);
}
// scan vector
template <typename T> 
inline istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// scan pair
template <typename T, typename U> 
inline istream &operator>>(istream &in, pair<T,U> &a) {
    in >> a.first >> a.second; 
    return in;
}

// Solve --------------------------------------------------------------------

void solve(ll &T)
{
    ll n, k;
    std::cin>>n>>k;

    vector<bool> vis(n);
    while(k--)
    {
        ll d;
        std::cin>>d;
        while(d--) {
            ll x;
            std::cin>>x;
            vis[x-1] = true;
        }
    }
    std::cout<<count(all(vis),false)<<endl;
}

// Main ---------------------------------------------------------------------

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt","r",stdin);
        freopen("D:/dhiraj/Programming/o1.txt","w",stdout);
    #endif

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

    int t = 1;
    loop(i,1,t+1)
    {
        cerr<<"Case #"<<i<<"\n";
        solve(i);
    }
    return 0;
}

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

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

	int h, w, a=0;
	cin >> h >> w;
	for(int i=0; i<h; ++i) {
		string s;
		cin >> s;
		for(char c : s)
			a+=c=='#';
	}
	cout << (a==h+w-1?"Possible":"Impossible");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF=1000000000;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    ll h[n],d=0;
    for (int i = 0; i < n;i++){
        cin>>h[i];
    }
    if(n>1){
        for (int i = n - 1; i > 0;i--){
            if(h[i]>=h[i-1]){

            }else if(h[i]+1==h[i-1]){
                h[i - 1]--;
            }else{
                cout << "No" << endl;
                break;
            }
            if(i==1){
                cout << "Yes" << endl;
            }
        }
    }else{
        cout << "Yes" << endl;
    }
    
    return 0;
}

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

int main() {
  int N, M; cin >> N >> M;
  vector<int> cost(N);
  for(int i = 0; i < N; ++i)
    cin >> cost[i];
  vector<int> score(N, 0);
  while(M--) {
    int x; cin >> x;
    for(int i = 0; i < N; ++i) {
      if(cost[i] <= x) {
        score[i]++;
        break;
      }
    }
  }
  int argmax = find(score.begin(), score.end(), *max_element(score.begin(), score.end())) - score.begin();
  cout << argmax + 1 << endl;
}

Measured memory_bytes: 1200
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#define LOG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long i64;
inline int rd(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5, P = 998244353, W = int(((long long)1e18)%P);
int n, ans; void fix(int &x) { x<P?0:x-=P; }
struct G
{
    int sg[N], w[N], t; vector<int> e[N]; void add(int x, int y) { if(x > y) swap(x, y); e[x].push_back(y); }
    int SG(int x)
    {
        if(~sg[x]) return sg[x]; sg[x] = 0; map<int, bool> h;
        for(int y:e[x]) h[SG(y)] = 1; while(h.count(sg[x])) ++sg[x]; return sg[x];
    }
    void sol()
    {
        memset(sg+1, -1, sizeof(int)*n);
        for(int i = 1; i <= n; ++i) sg[i] = SG(i);
        for(int i = 1, v = 1; i <= n; ++i) v = (i64)v*W%P, t = max(sg[i], t), fix(w[sg[i]]+=v);
    }
}g[3];
int main()
{
    n = rd(); for(int k = 0; k < 3; g[k].sol(), ++k) for(int m = rd(), x, y; m--; ) x = rd(), y = rd(), g[k].add(x, y);
    for(int i = 0; i <= g[0].t; ++i) for(int j = 0; j <= g[1].t; ++j) fix(ans+=(i64)g[0].w[i]*g[1].w[j]%P*g[2].w[i^j]%P);
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 16748
/*
    ٭٭UWW٭٭OWO٭٭
    Auto-generated by VS Code's Code Snippet
    «I'm just a starter-coder»
    ▶zyck2002◀
    ٭٭UWW٭٭OWO٭٭
*/

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

#define fup(i,l,h) for (int i = l; i < h; i++)

// Debug tool, f = open input file, D = debug mode
//#define f
//#define debug

// Main function
int main()
{
    #ifdef f
    freopen("a.inp","r",stdin);
    #endif
    int a, b;
    cin >> a >> b;
    if (a >= 13) cout << b;
    else if (a >= 6 && a <= 12) cout << b/2;
    else cout << 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        final Scanner scan = new Scanner(System.in);
        long K = scan.nextLong();
        final long A = scan.nextLong();
        final long B = scan.nextLong();

        if (B - A <= 2L) {
            System.out.println(K + 1L);
            return;
        }

        long biscuit = 1L;
        long jpy = 0L;

        while (K > 0L) {
            if (jpy > 0L) {
                jpy--;
                biscuit += B;
                K--;
                continue;
            }

            if (biscuit >= A && K >= 2L) {
                biscuit -= A;
                jpy++;
                K--;
                continue;
            }

            biscuit++;
            K--;
        }
        System.out.println(biscuit);
    }
}

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

int main(){
  int N,D;cin>>N>>D;
  vector<vector<int>>X(N,vector<int>(D));
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++){
      cin>>X[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int norm=0;
      for(int k=0;k<D;k++){
        int a=abs(X[i][k]-X[j][k]);
        norm+=a*a;
      }
      bool flag= false;
      for(int k=0;k<=norm;k++){
        if(k*k==norm) flag=true;
      }
      if(flag) ans++;
    }
  }
  cout<<ans<<endl;
}

      


Measured memory_bytes: 3580
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }

int main() {
    long long int N,K;
    scanf("%lld %lld",&N,&K);
    if(N%K >= K-N%K){
        printf("%lld",K-N%K);
    }
    else{
        printf("%lld",N%K);
    }

}

int A(){
    int A,B,C;
    scanf("%d %d %d",&A,&B,&C);
    printf("%d %d %d",C,A,B);
    return 0;
}

int B(){
    int M, N;
    scanf("%d %d", &N, &M);
    int A[N];
    int SUM = 0;
    for (int i = 0; i < N; ++i) {
        scanf("%d", &A[i]);
        SUM += A[i];
    }
    qsort(A, sizeof(A) / sizeof(A[0]), sizeof(int), downint);

    if (A[M-1] >= 1.0*SUM / (4 * M)) {
        printf("Yes");
        return 0;
    } else {
        printf("No");
        return 0;
    }
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    string s;
    cin>>s;
    int n = stoi(s);
    
    int t = 0;
    rep(i,s.size()){
        t+=s[i]-'0';
    }
    if(n%t==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

A,B,X = inpl()
if A <= X <= A+B:
	print('YES')
else:
	print('NO')


Measured memory_bytes: 4204
<?php
$a = intval(trim(fgets(STDIN)));
$b = intval(trim(fgets(STDIN)));
$c = intval(trim(fgets(STDIN)));
$d = intval(trim(fgets(STDIN)));
$ans = min($a, $b) + min($c, $d);
print("$ans\n");
?>

Measured memory_bytes: 4728
import java.util.*;

class Main{

  public static void main(String args[]){

    Scanner s=new Scanner(System.in);
    long N=s.nextLong();
    String ans="";
	for(;0<N;){
      char c=(char)((N-1)%26+97);
      ans=String.valueOf(c)+ans;
      N=(N-1)/26;
    }
    System.out.println(ans);

  }  
}

Measured memory_bytes: 39108
#include <stdio.h>
int main(void){
	int a[12]={0,1,3,1,2,1,2,1,1,2,1,2,1},x,y;
	scanf("%d%d",&x,&y);
	a[x]==a[y] ? printf("Yes") : printf("No");
	return 0;
}

Measured memory_bytes: 128
process.stdin.resume();
process.stdin.setEncoding('utf8');
 
// inputに入力データ全体が入る
function Main(input) {
  // 1行目がline1, 2行目がline2, …に入る
  var arg   = input.split("\n");
  var line0 = arg[0].split(" ");
  var line1 = arg[1].split(" ");
  //var line2 = tmp[2].split(" ");
  //var line3 = tmp[3].split(" ");

  var input1 = (line0[0]);
  var input2 = (line1[0]);
  //var input3 = Number(line0[2]);
  var a = input1;
  var b = input2;
  //var c = input3;

  var ans = "No";

  //console.log( line0 +" "+ a +" "+ b +" "+ "");
  
  for(var i=0; i<a.length; i++){
    var first = a[0];
    //console.log("before a = " +  a);

    var tmp =  a.slice(1, a.length);
    //a.push(first);
    //console.log("tmp = " + tmp);
    a = tmp + first;
    //console.log("after a = " + a)
    
    if(a === b) ans = "Yes"
  }


  console.log(ans);

  


}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
#include<bits/stdc++.h>
using namespace std;
#if defined __has_include
# if __has_include(<bits/debug_aamir.h>)
#  define dbg(...) DEBUG(#__VA_ARGS__, __VA_ARGS__);
#  include<bits/debug_aamir.h>
# else
#  define dbg(...)
# endif
#endif

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pll;
#define sz(x) int(x.size())
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define rep(i, begin, end) for(__typeof(end) i=begin; i<end; i++)
#define per(i, begin, end) for(__typeof(end) i=begin; i>=end; i--)
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
constexpr int INF = 1e9 + 1;
constexpr ll LLINF = 1e18 + 1;


template<typename T>
T gcd(T a, T b){	return b ? gcd(b, a%b): a; }
template<typename T>
T lcm(T a, T b){	return a/gcd(a, b) * b;		}


int main()
{
	fastio;
	int n;
	cin >> n;
	vi h(n), dist(n, INF);
	rep(i, 0, n)	cin >> h[i];
	dist[0]=0;
	rep(i, 0, n){
		for(int j=1; j<3 && i+j<n; j++){
			dist[j+i] = min(dist[j+i], dist[i]+abs(h[j+i]-h[i]));
		}
	}
	printf("%d\n", dist[n-1]);
}



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

using namespace std;

int main(void) {
    while (1) {
        int n;
        cin >> n;
        if (n == 0) break;

        int len[n + 1];
        for (int i = 1; i <= n; ++i) {
            string w;
            cin >> w;
            len[i] = w.length();
        }

        int cumulativesum[n + 1];
        cumulativesum[1] = len[1];
        for (int i = 2; i <= n; ++i) {
            cumulativesum[i] = cumulativesum[i - 1] + len[i];
        }

        bool cnt5 = false, cnt12 = false, cnt17 = false, cnt24 = false, cnt31 = false;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
//            for (int j = 1; j <= n; ++j) {
//                printf("%d ", cumulativesum[j]);
//            }
//            printf("\n");
            for (int j = i; j <= n; ++j) {
                if (cumulativesum[j] == 5) cnt5 = true;
                if (cumulativesum[j] == 12) cnt12 = true;
                if (cumulativesum[j] == 17) cnt17 = true;
                if (cumulativesum[j] == 24) cnt24 = true;
                if (cumulativesum[j] == 31) cnt31 = true;

                if (cnt5 && cnt12 && cnt17 && cnt24 && cnt31) ans = i;
            }
            if (ans != 0) break;
            for (int j = 1; j <= n; ++j) {
                cumulativesum[j] -= len[i];
            }
            cnt5 = false, cnt12 = false, cnt17 = false, cnt24 = false, cnt31 = false;
        }

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


Measured memory_bytes: 3156
#include <cstdio>
#include <cmath>
#include <algorithm>

typedef double r64;
const r64 PI = acos(-1);
const r64 C1 = 5 * (PI - 4);
const r64 C2 = 10 * (PI - 2);
const int Inf = 0x3f3f3f3f;
const int MN = 200005;

int sx, sy, tx, ty, N, K, px[MN], py[MN], p[MN];
r64 Ans;

int f[MN];

int main() {
	scanf("%d%d%d%d%d", &sx, &sy, &tx, &ty, &N);
	Ans = 100ll * (abs(tx - sx) + abs(ty - sy));
	if (sx > tx) std::swap(sx, tx), std::swap(sy, ty);
	int rev = sy > ty;
	if (rev) std::swap(sy, ty);
	for (int i = 1, x, y; i <= N; ++i) {
		scanf("%d%d", &x, &y);
		if (x < sx || tx < x || y < sy || ty < y) continue;
		if (rev) y = -y;
		px[++K] = x, py[K] = y, p[K] = K;
	}
	std::sort(p + 1, p + K + 1, [](int i, int j) { return px[i] < px[j]; });
	int num = 0;
	f[0] = -Inf;
	for (int i = 1; i <= K; ++i) f[i] = Inf;
	for (int i = 1; i <= K; ++i) {
		int v = py[p[i]];
		int j = std::lower_bound(f, f + K + 1, v) - f;
		if (num < j) num = j;
		f[j] = v;
	}
	if (num == std::min(tx - sx, ty - sy) + 1) Ans += (num - 1) * C1 + C2;
	else Ans += num * C1;
	printf("%.15lf\n", Ans);
	return 0;
}

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

int main() {
    string s, t; cin >> s >> t;
    int res = 0;
    for (int i = 0; i < 3; i++) {
        if (s[i] == t[i]) res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 764
from bisect import bisect_left
A, B, Q = map(int, input().split())
S = [-10**11] + [int(input()) for _ in range(A)] + [10**11]
T = [-10**11] + [int(input()) for _ in range(B)] + [10**11]
X = [int(input()) for _ in range(Q)]

S1 = [0]*A
T1 = [0]*B
for i, s in enumerate(S[1:-1]):
    x = bisect_left(T, s)
    S1[i] = (s, min(abs(s - T[x-1]), abs(T[x] - s)))
for i, t in enumerate(T[1:-1]):
    x = bisect_left(S, t)
    T1[i] = (t, min(abs(t - S[x-1]), abs(S[x] - t)))
ST = S1 + T1
ST.sort()
ST = [(-10**11, 10**11)] + ST + [(10**11, 10**11)]
bist, dist = map(list, zip(*ST))
for d in X:
    x = bisect_left(bist, d)
    print(min(abs(d - bist[x-1]) + dist[x-1], abs(bist[x] - d) + dist[x]))


Measured memory_bytes: 130880
N,K=map(int, input().split())
L=[]
for i in range(N):
    a,b=map(int, input().split())
    L.append((a,b))

L=sorted(L)
count=0

for i in range(N):
    t=L[i]
    a,b=t
    count+=b
    if count>=K:
        print(a)
        break



Measured memory_bytes: 17816
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

int main() {
	double x, h;
	while(cin >> x >> h, x) {
		double ans =  x*x + 2*x*sqrt(h*h+x*x/4);
		printf("%.6f\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1236
#include<bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define N 100012
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define pb push_back
#define fs first
#define sc second
#define sz(x) ((int)((x).size()))
#define oo 1000000123
#define mod 1000000007

using namespace std;

int n, q, m, v[50], dp[50][50];

struct Quad{
    int a, b, c, d;
} quad[100];

int cont(){
    int r = 0;
    for(int i = 0; i < q; ++i){
        if(v[quad[i].b] - v[quad[i].a] == quad[i].c) r += quad[i].d;
    }
    return r;
}

int f(int idx, int last){
    if(idx > n){
        return cont();
    }
    int r = -oo;
    for(int i = last; i <= m; ++i){
        v[idx] = i;
        r = max(r, f(idx + 1, i));
    }
    return r;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> q;
    for(int i = 0; i < q; ++i) cin >> quad[i].a >> quad[i].b >> quad[i].c >> quad[i].d;
    cout << f(1, 1) << '\n';
    return 0;
}


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

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

    long long x, y;
    cin >> x >> y;

    long long num = x;
    long long ans = 1;
    while(true){
        num *= 2;
        if(num <= y);
        else break;
        ans++;
    }
    

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

/*
   AtCoder contest code
   coder : yoichidon
 */

public class Main {
    public static String longer(String x, String y){
        if(x.length() > y.length()) return x;
        else return y;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int zero=0, one=0, two=0, three=0;
        for(int n=0; n<N; n++){
            int a = sc.nextInt();
            switch(a){
                case 0 :
                    zero++;
                    break;
                case 1 :
                    one++;
                    break;
                case 2 :
                    two++;
                    break;
                default:
                    three++;
            }
        }

        double[][][] dp = new double[N+1][N+1][N+1];
        //dp[i][j][k] : when there are 'i' dishes with one sushi
        //                             'j' dishes with two sushi
        //                         and 'k' dishes with three sushi
        dp[0][0][0]=0;


        for(int k=0; k<=three; k++){
            if(k==0){
                for(int j=0; j<=two+three; j++){
                    if(j==0){
                        for(int i=0; i<=N; i++){

                            if(i==0) dp[i][j][k] = 0;
                            else dp[i][j][k] = (N + i*dp[i-1][j][k])/i;
                        }
                    }
                    else {
                        for(int i=0; i<=N; i++){
                            if(i+j+k>N) break;
                            if(i==0) dp[i][j][k] = (N + j*dp[i+1][j-1][k])/j;
                            else dp[i][j][k] = (N + i*dp[i-1][j][k] + j*dp[i+1][j-1][k])/(i+j);
                        }
                    }
                }
            }else{
                for(int j=0; j<=two+three; j++){
                    if(j==0){
                        for(int i=0; i<=N; i++){
                            if(i+j+k>N) break;
                            if(i==0) dp[i][j][k] = (N + k*dp[i][j+1][k-1])/(k);
                            else dp[i][j][k] = (N + i*dp[i-1][j][k] + k*dp[i][j+1][k-1])/(i+k);
                        }
                    }
                    else {
                        for(int i=0; i<=N; i++){
                            if(i+j+k>N) break;
                            if(i==0) dp[i][j][k] = (N + j*dp[i+1][j-1][k] + k*dp[i][j+1][k-1])/(j+k);
                            else dp[i][j][k] = (N + i*dp[i-1][j][k] + j*dp[i+1][j-1][k] + k*dp[i][j+1][k-1])/(i+j+k);
                        }
                    }
                }
            }
        }
        
        System.out.println(dp[one][two][three]);
    }
}


Measured memory_bytes: 309712
import numpy as np
from collections import defaultdict


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


def main():
    N, M, K = [int(x) for x in input().split()]

    uf = UnionFind(N)
    fcount = defaultdict(int)
    for _ in range(M):
        A, B = [int(x) for x in input().split()]
        uf.union(A-1, B-1)
        fcount[A-1]+=1
        fcount[B-1]+=1

    import collections
    bcount = defaultdict(int)
    for _ in range(K):
        C, D = [int(x) for x in input().split()]
        C-=1
        D-=1
        if uf.is_same(C, D):
            bcount[C]+=1
            bcount[D]+=1

    groups = collections.defaultdict(set)
    for i in range(N):
        groups[uf.find(i)].add(i)

    counts = []
    for i in range(N):
        friends = groups[uf.find(i)]
        cnt = len(friends)-1-fcount[i]-bcount[i]
        counts.append(cnt)
    print(" ".join(map(str, counts)))


if __name__ == '__main__':
    main()

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

vector<int> G[10];
int d[10]={};
int n, m;
int ans = 0;

void dfs(int now){
  d[now] = 1;
  int cnt = 1;
  for(int i=0; i<n; i++){
    cnt *= d[i];
  }
  ans += cnt;
  for(int i=0; i<G[now].size(); i++){
    int next = G[now][i];
    if(d[next]==0) dfs(next);
  }
  d[now] = 0;
}
 
int main(){
  cin >> n >> m;
  for(int i=0; i<m; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  dfs(0);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n=input()
a=raw_input()
count=0
for r in range(n):
	b=raw_input()
	lb=len(b)
	flag=0
	for s in range(lb):
		for i in range(lb-(s+1)*(len(a)-1)):
			if b[i:i+(s+1)*len(a):s+1]==a:
				count+=1
				flag=1
				break
		if flag==1:break
print count
	

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

int main(void){
    int n, m;
    cin >> n >> m;
    int l[100000];
    int r[100000];
    int rmin;
    int lmax;

    for(int i = 0; i < m; i++){
        cin >> l[i] >> r[i];
    }
    rmin = r[0];
    for(int i = 1; i < m; i++){
        if(rmin > r[i]){
            rmin = r[i];
        }
    }

    lmax = l[0];
    for(int i = 1; i < m; i++){
        if(lmax < l[i]){
            lmax = l[i];
        }
    }
    cout << max(rmin - lmax + 1, 0) << endl;
}

Measured memory_bytes: 1024
NK = input()
N, K = int(NK.split(" ")[0]), int(NK.split(" ")[1])

p = input()
lists = []
for i in range(N):
  lists.append(int(p.split(" ")[i]))

lists.sort()

price = 0
for j in range(K):
  price += lists[j]
  
print(price)

Measured memory_bytes: 9120
#include <iostream>

int main(void) {
    int N = 0;
    std::cin >> N;
    std::string string;
    std::cin >> string;
    int count = 0;
    for (auto i = 0; i < string.length(); i++) {
        if (string[i] == 'A' && string[i+1] == 'B' && string[i+2] == 'C') {
            count++;
        }
    }
    std::cout << count << std::endl;
    return 0;
}

Measured memory_bytes: 256