akhauriyash/Code-Regression huggingface dataset:
#include<iostream>

using namespace std;

int N, Y;

int main() {
    cin >> N >> Y;
    Y /= 1000;
    int a = Y - N;
    int b = 5 * N - Y;
    bool ng = true;
    if (a % 4 == (4 - b % 4) % 4) {
        int mn = max(( - b + 4) / 5, 0);
        //cout << mn << endl;
        int x = mn / 4 * 4 + a % 4;
        x = mn > x ? x + 4 : x;
        if (x <= a / 9) {
            ng = false;
            cout << x << " " << (a - 9 * x) / 4 << " " << (b + 5 * x) / 4 << endl;
        }
    }
    if (ng) cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please


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


	string S, T;
	cin >> S >> T;


	T.pop_back();

	if (S == T) co("Yes");
	else co("No");


	Would you please return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>
#include <string>
#include <math.h>
using namespace std;
int main()
{
    int t;
    int x[4]={0};
    cin>>t;
    while(t--)
    {
        char y[5];
        cin>>y;
        if(y[0]=='A')
            x[0]++;
        else if(y[0]=='W')
            x[1]++;
        else if(y[0]=='T')
            x[2]++;
        else
            x[3]++;
    }
    cout<<"AC x "<<x[0]<<endl;
    cout<<"WA x "<<x[1]<<endl;
    cout<<"TLE x "<<x[2]<<endl;
    cout<<"RE x "<<x[3]<<endl;
	return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
  double a,b,h,m,x,y,t,s,res;
  cin >> a >> b >> h >> m;
  t=(h+m/60)*acos(-1.0)/6;
  s=m*acos(-1.0)/30;
  x=a*cos(t)-b*cos(s);
  y=a*sin(t)-b*sin(s);
  res=sqrt(x*x+y*y);
  cout << setprecision(15) << res << endl;
  return 0;
}

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

// https://qiita.com/drken/items/cce6fc5c579051e64fab
struct WeightedUnionFind{
    vector<int> par;
    vector<int> rank;
    vector<int> diff;

    WeightedUnionFind(int n){
        init(n);
    }

    void init(int n){
        par.resize(n); rank.resize(n, 0); diff.resize(n, 0);
        for(int i = 0; i < n; i++)  par[i] = i;
    }

    int root(int x){
        if(par[x] == x){
            return x;
        }else{
            int r = root(par[x]);
            diff[x] += diff[par[x]];
            return par[x] = r;
        }
    }

    // 単ノードの重み取得
    int weight(int x){
        root(x);
        return diff[x];
    }

    int dif(int x, int y){
        return weight(y) - weight(x);
    }

    bool isSame(int x, int y){
        return root(x) == root(y);
    }

    // weight(y) - weight(x) = w となるように merge
    bool merge(int x, int y, int w){
        // x が y の親になることを考えると、更新の起点はdiff[y]で、
        // diff[y] を w + weight(x) - weight(y) にすればよい
        w += weight(x); w -= weight(y);

        x = root(x); y = root(y);
        if(x == y)  return false;
        if(rank[x] < rank[y])   swap(x, y), w = -w;
        if(rank[x] == rank[y])  rank[x]++;
        par[y] = x;
        diff[y] = w;
        return true;
    }
};

int main(){
    int n, q;
    cin >> n >> q;
    WeightedUnionFind uf(n);
    while(q-- > 0){
        int a, b, c, d;
        cin >> a >> b >> c;
        if(a == 0){
            cin >> d;
            uf.merge(b, c, d);
        }else{
            if(uf.isSame(b, c)) cout << uf.dif(b, c) << endl;
            else                cout << "?" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3888
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1111111111;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;

	if (s[2] == s[3] && s[4] == s[5]) cout << "Yes" << "\n";
	else cout << "No" << "\n";

	return 0;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/11/22  Problem: 011_arc_b / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N;

LL ans = 0LL;

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

	VL a(N, 0);
	VL sum(N + 1, 0);
	FOR(i, 0, N) {
		cin >> a[i];
	}
	SORT(a);
	FOR(i, 0, N) {
		sum[i + 1] = sum[i] + a[i];
	}
	ans = 1;
	int f = 1;
	FORR(i, N - 2, -1) {
		if (a[i + 1] <= 2 * sum[i + 1] && f)ans++;
		else f = 0;
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
#define rep(i, j, n) for(int i = (j); i < (n); ++i)
#define rrep(i, j, n) for(int i = (n) - 1; (j) <= i; --i)
constexpr ll MOD = 1000000007;
constexpr ll INF = 1LL << 60;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	string s; cin >> s;
	int n = s.size();
	cout << string(n, 'x') << endl;
	return 0;
}


Measured memory_bytes: 3640
import sys
sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

N = int(input())
G = [[i] + list(map(int, input().split())) for i in range(N)]

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)


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

int main() {
  int N,a;
  cin>>N;
  map<int, int> s;
  for(int i=1; i<N+1; i++){
    cin>>a;
    s[a] = i;
  }
  for(int i=1; i<N+1; i++){
    if(i==1) cout<<s[i];
    else cout<<" "<<s[i];
  }
  cout<<endl;
}

Measured memory_bytes: 8188
if __name__ == '__main__':
    N = int(input())
    string = {}
    ret = 0
    for n in range(N):
        cur_char = ''.join(sorted(input()))
        if cur_char in string:
            ret += string[cur_char]
        string[cur_char] = string.get(cur_char, 0) + 1
    print(ret)

Measured memory_bytes: 17852
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(100000)

class Node():
    def __init__(self, ID=None, parent=-1, left=-1, right=-1):
        self.id = ID
        self.parent = parent
        self.left = left
        self.right = right

def preParse(u):
    if u == -1:
        return
    print(" " + str(u), end="")
    preParse(T[u].left)
    preParse(T[u].right)
    
def inParse(u):
    if u == -1:
        return
    inParse(T[u].left)
    print(" " + str(u), end="")
    inParse(T[u].right)
    
def postParse(u):
    if u == -1:
        return
    postParse(T[u].left)
    postParse(T[u].right)
    print(" " + str(u), end="")
    
    
if __name__ == '__main__':

    n = int(input())
    T = [Node() for i in range(n)]

    for _ in range(n):
        ID, left, right = list(map(int, input().split(" ")))
        T[ID].id = ID
        T[ID].left = left
        T[ID].right = right
        if left != -1:
            T[left].parent = ID
        if right != -1:
            T[right].parent = ID
    
    for node in T:
        if node.parent==-1:
            r = node.id
    
    print("Preorder")
    preParse(r)
    print()
        
    print("Inorder")
    inParse(r)
    print()
    
    print("Postorder")
    postParse(r)
    print()
    


Measured memory_bytes: 5628
#include<stdio.h>
char m[9*10];
int bomb(int p){
	if(m[p]=='1'){
		m[p]--;
		bomb(p+1)&&bomb(p+2)&&bomb(p+3);
		bomb(p-1)&&bomb(p-2)&&bomb(p-3);
		bomb(p+9)&&bomb(p+18)&&bomb(p+27);
		bomb(p-9)&&bomb(p-18)&&bomb(p-27);
	}
	return m[p]=='0';
}
int main(){
	int N=0,n,x,y;
	scanf("%d",&n);
	while(n--){
		fread(m+7,1,9*8+2,stdin);
		scanf("%d%d",&x,&y);
		bomb(y*9+x-1);
		printf("Data %d:%s",++N,m+8);
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

unsigned int gcd(unsigned int, unsigned int);

int main(){
        unsigned int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", gcd(x,y));
        return 0;
}

unsigned int gcd(unsigned int x, unsigned int y){
        unsigned int tmp, i;
        
        if(x == y)return x;
        if(y > x){
                tmp = y;
                y = x;
                x = tmp;
        }

        tmp = x % y;

        for(i = tmp; i > 0 ; i--){
                if((y % i) == 0 && (tmp % i) == 0)return i;
        }

}



Measured memory_bytes: 2144
def factorize(n):
    a = []
    f = 2
    while f * f <= n:
        if n % f == 0:
            a.append((f, n//f))
        f += 1
    if not len(a):
        a.append((1, n))
    return a

n = int(input())
factor = factorize(n)

ans = int(1e13)
for fa in factor:
    a, b = fa
    ans = min(ans, a + b - 2)
print(ans)

Measured memory_bytes: 39024
#include <iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;


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

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

	int n;
	cin >> n;

	vector<long long> a(n + 1), b(n);
	for (int i = 0; i < n + 1; ++i)
		cin >> a[i];
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}

	ll ans = 0;//合計値
	for (int i = 0; i < n; ++i) {
		//まずは左を全力で倒す
		auto left = min(a[i], b[i]);//左に残ってる数と自分の戦力，小さい数が倒せる数
		ans += left;
		a[i] -= left;
		b[i] -= left;

		//残った戦力で右を倒す
		auto right = min(a[i + 1], b[i]);
		ans += right;
		a[i + 1] -= right;
		b[i] -= right;

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

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		String[] piledStudentList = sc.nextLine().split(" ");
		sc.close();
		
		int[] visitArr = new int[n];
		for(int i = 0; i < n; i++) {
			int piledStudents = Integer.parseInt(piledStudentList[i]);
			visitArr[piledStudents - 1] = i;
		}
		
		for(int i = 0; i < n; i++) {
			System.out.print(visitArr[i] + 1);
			if(i < n -1) {
				System.out.print(" ");
			}
		}
		System.out.println("\n");
	}
}


Measured memory_bytes: 57184
#include<stdio.h>
int main(void){
    int a,b,n,cnt,temp,i;
    scanf("%d %d %d",&a,&b,&n);
    cnt=0;
    if(a<b){
        temp=b;
        b=a;
        a=temp;
    }
    for(i=a;i!=0;i--){
        if(a%i==0&&b%i==0){
            cnt++;
            if(cnt==n){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=505,mod=998244353;
ll base1=1,base2=0,p[N];
int n,m,tot,vis[N],head[N],nex[N<<1],to[N<<1];
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}
vector<ll>res[3];
void solve(int flag)
{
    tot=0;memset(head,0,sizeof(head));
    memset(vis,false,sizeof(vis));
    m=100000;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        //u=v=1;while(u==v) u=rand()*rand()%n+1,v=rand()*rand()%n+1;
        add(u,v);add(v,u);
    }
    priority_queue<int>q[2];
    int x=0,tim=0;
    for(int i=1;i<=n;i++) q[x].push(i);
    vector<ll>f;
    while(!q[x].empty())
    {
        tim++;
        ll ans=0;
        while(!q[x].empty())
        {
            while(!q[x].empty()&&vis[q[x].top()]==tim) q[x].pop();
            if(q[x].empty()) break;
            int u=q[x].top();q[x].pop();
            vis[u]=1e9;
            ans=(ans+p[u])%mod;
            for(int i=head[u];i;i=nex[i])
            {
                int v=to[i];
                if(vis[v]<tim)
                {
                    vis[v]=tim;
                    q[x^1].push(v);
                }
            }
        }
        x^=1;
        f.push_back(ans);
    }
    res[flag]=f;
}
bool vis1[M][M],vis2[M];
ll solve()
{
    memset(vis2,0,sizeof(vis2));
    ll ans=0;
    for(int i=0;i<res[1].size();i++)
    {
        int mx=0;
        while(mx<res[2].size()&&vis1[i][mx]||vis2[mx]) mx++;
        if(mx<res[2].size())
        {
            vis1[i][mx]=vis2[mx]=true;
            ans=(ans+res[1][i]*res[2][mx])%mod;
        }
    }
    return ans;
}
int main()
{
    srand(time(0));
    p[0]=1;
    for(int i=1;i<N;i++) p[i]=1000000000000000000ll%mod*p[i-1]%mod;
    scanf("%d",&n);
    solve(0);solve(1);solve(2);
    assert(res[0].size()<M);
    assert(res[1].size()<M);
    assert(res[2].size()<M);
    ll ans=0;
    for(int i=0;i<res[0].size();i++)
        ans=(ans+res[0][i]*solve())%mod;
    printf("%lld\n",ans);
}


Measured memory_bytes: 4336
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

void foreach_permutation(int n, std::function<void(int *)> f) {
    int indexes[n];
    for (int i = 0; i < n; i++) indexes[i] = i+1;
    do {
        f(indexes);
    } while (std::next_permutation(indexes, indexes + n));
}

int main() {
  string S;
  cin >> S;

  for(int i=0;i<S.length();i++){
      cout << 'x';
  }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[(" << __LINE__ << ") " << #x << "]: " << (x) << endl;

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

    string s;
    cin >> s;

    if (s.back() == 's') cout << s << "es\n";
    else cout << s << "s\n";
}


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

int main(){
  long long n, k;
  cin >> n >> k;
  vector<double> vec;
  for(long long i=0; i<n; i++){
    double num;
    cin >> num;
    num = num / 2.0 + 0.5;
    vec.push_back(num);
  }
  double sum = 0;
  vector<double> sumvec;
  for(long long i=0; i<k; i++){
    sum += vec[i];
  }
  sumvec.push_back(sum);
  for(long long i=k; i<n; i++){
    sum -= vec[i-k];
    sum += vec[i];
    sumvec.push_back(sum);
  }
  cout << std::setprecision(10) << *std::max_element(sumvec.begin(), sumvec.end()) << endl;
}
    
  
  

Measured memory_bytes: 4848
#include <stdio.h>
#include <stdlib.h>

struct Node{
    int key;
    struct Node *right;
    struct Node *left;
    struct Node *parent;
};
struct Node *root;

void inorder(struct Node *);
void preorder(struct Node *);
void insert(int);

int main(){
    int n,x;
    char com[20];

    scanf("%d", &n);

    for (int i = 0; i < n; i++ ){
        scanf("%s", com);
        if(com[0] == 'i'){
            scanf("%d",&x);
            insert(x);
        } 
        else if(com[0] == 'p'){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        } 
    }

    return 0;
}

void inorder(struct Node *A){
    if(A == NULL)return;
    inorder(A->left);
    printf(" %d",A->key);
    inorder(A->right);
}

void preorder(struct Node *A){
    if(A == NULL)return;
    printf(" %d",A->key);
    preorder(A->left);
    preorder(A->right);
}

void insert(int key){
    struct Node *y = NULL;
    struct Node *x = root;
    struct Node *z = malloc(sizeof(struct Node));
    z->key = key;
    z->left = z->right = z->parent = NULL;

    while(x != NULL){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }
        else{
            x = x->right;
        }
    }

    z->parent = y;

    if(y == NULL){
        root = z;
    }
    else if(z->key < y->key){
        y->left = z;
    }
    else{
        y->right = z;
    }
}


Measured memory_bytes: 25172
public class Hello {
    public static void Main(){
        // 1行に複数の入力値がある場合の例
        string [] inputs = System.Console.ReadLine().Split(' ');
        int a = int.Parse(inputs[0]);
        int b = int.Parse(inputs[1]);
        int c = (a * b);
        int d = (a + b) * 2;
        System.Console.WriteLine(c + " " + d);
    }
}



Measured memory_bytes: 9100
n, k = gets.rstrip.split(' ').map(&:to_f)

ans = 0.0
(1..[n, k].min).each do | i |
  # (Math.log(n) / Math.log(i*2)).ceil 回連続で勝たないとだめ
  ans += (1/n) * (1/2.0) ** (Math.log(k/i) / Math.log(2.0)).ceil
end

if n > k
  ans += (n-k)/n
end

p ans

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

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[N],b[N];
int F[N],f[N][33];
int vis[33];
int main(){
	ios::sync_with_stdio(false);
	cin>>a+1>>b+1;
	int L=strlen(a+1),R=strlen(b+1);
	for(int i=0;i<26;i++)f[L+1][i]=-1;
	for(int i=1;i<=L;i++)if(!F[a[i]-'a'])F[a[i]-'a']=i;
	for(int i=L;i>=1;i--){
		vis[a[i]-'a']=1;
		for(int j=0;j<26;j++){
			f[i][j]=f[i+1][j];
		}
		f[i][a[i]-'a']=i;
	}
	int now=0;
	LL ans=0;
	for(int i=1;i<=R;i++){
		if(!vis[b[i]-'a'])return cout<<-1,0;
		if(f[now+1][b[i]-'a']!=-1){
			ans+=f[now+1][b[i]-'a']-now;
			now=f[now+1][b[i]-'a'];
		}else{
			ans+=L-now;
			ans+=F[b[i]-'a'];
			now=F[b[i]-'a'];
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 16768
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <cmath>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vector<T>>;

#define REP(i, s, e) for (ll i = s; i < e; ++i)
static const ld PI = 3.14159265358979323846L;

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

    // long short hour minute
    int A, B, H, M; cin >> A >> B >> H >> M;

    ld radianLong = PI / 30 * M;
    ld radianShort = PI / 6 * H + PI / 6 / 60 * M;

    ld ly = sinl(radianLong) * B, lx = cosl(radianLong) * B;
    ld sy = sinl(radianShort) * A, sx = cosl(radianShort) * A;

    ld vx = lx - sx, vy = ly - sy;
    ld l = sqrtl(vx * vx + vy * vy);

    cout << fixed << setprecision(15) << l << endl;

    return 0;
}


Measured memory_bytes: 4168
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<ll,ll>;
#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second
#define int ll
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define mkp make_pair
#define INF (ll)(1e17)
#define MOD (ll)(998244353)

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	//I won't misunderstand the problem statement anymore.
	int n; cin>>n;
	vector<bool> v;
	For(i,0,n-1){
		int a,b; cin>>a>>b;
		v.eb(a==b);
	}
	For(i,2,n-1){
		if(v[i] && v[i-1] && v[i-2]){
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
	return 0;
}























Measured memory_bytes: 3684
#include <iostream>
using namespace std;
 
#define MAX_W 100
#define MAX_H 100
char farm[MAX_W][MAX_H];
int W, H;
const int direction[4][2] = {
	{ -1, 0 },
	{ 1, 0 },
	{ 0, -1 },
	{ 0, 1 },
};
 
void dfs(const int& x, const int& y, const char tree)
{
	farm[x][y] = 'x';
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + direction[i][0];
		int ny = y + direction[i][1];
		if (nx >= 0 && nx < W && ny >= 0 && ny < H && farm[nx][ny] == tree)
		{
			dfs(nx, ny, tree);
		}
	}
}
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
 
	while (cin >> H >> W, W > 0)
	{
		int res = 0;
		int x, y;
		for (y = 0; y < H; ++y)
		{
			for (x = 0; x < W; ++x)
			{
				cin >> farm[x][y];
			}
		}
 
		for (y = 0; y < H; ++y)
		{
			for (x = 0; x < W; ++x)
			{
				if (farm[x][y] != 'x')
				{
					dfs(x, y, farm[x][y]);
					++res;
				}
			}
		}
		cout << res << endl;
	}
 
	return 0;
}


Measured memory_bytes: 3896
#include <iostream>

using namespace std;

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

  for(int i=0; i<k*2-1; i++){
    if( -1000000 <= x - k + 1 + i && x - k + 1 + i <= 1000000 ){
      cout << x - k + 1 + i << " ";
    }
  }
  cout << endl;

  return 0;
}


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

typedef long long ll;

int main()
{
    int N;
    cin >> N;
    if (N % 1000 == 0)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << 1000 - N % 1000 << endl;
    }
}

Measured memory_bytes: 3644
/*
  B - NarrowRectanglesEasy
  <http://abc056.contest.atcoder.jp/tasks/abc056_b>
*/

#include <stdio.h>

int main(int argc, char const *argv[]) {

  int W, a, b;

  scanf("%d %d %d", &W, &a, &b);

  if( a < b ){
    if( a+W < b ){
      printf("%d", b - (a+W));
    }else{
      printf("%d", 0);
    }
  }else{
    if( b+W < a ){
      printf("%d", a-(b+W));
    }else{
      printf("%d", 0);
    }
  }

  return 0;
}


Measured memory_bytes: 128
// Wed Aug 12 20:03:03 IST 2020   
#include <bits/stdc++.h>        
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define forn(ii,a,b)       for(int64 ii = (int)a ; ii < (int)b  ; ii++ )
#define debug(x)           cerr << #x << " " << x << " -- \n"
#define I__O               ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define int64              long long   
#define all(x)             (x).begin(),(x).end() 
#define ff                 first
#define ss                 second
#define pppp               pair <int,int> 
#define precise(x)         cout << fixed << setprecision(12) << x << '\n'; 
using namespace std ;    
// policy based   
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set ; 
 
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
const double pi = 3.141592653589793238;
const int N = 1e5+7; 
const int INF = 2e9;

struct compare{
    bool operator()(vector <int64> A, vector <int64> B){
        if(A[0] == B[0])
            return A[1] < B[1];
        return A[0] < B[0];
    }
};      
  
int64 grid[3007][3007];
int64 dp[3007][3007][4];
int R,C;
int64 solve(int row, int col, int times){
    if(row == R-1 && col == C-1)
        return (times < 3 ? grid[R-1][C-1] : 0);
    int64 &x = dp[row][col][times];
    if(x > -1)
        return x;
    // cout << row << ' ' << col << ' ' << times << '\n';
    int64 mex = 0LL;
    if(row+1 < R && times < 3)
        mex = max(mex,grid[row][col] + solve(row+1, col, 0));
    if(col+1 < C && times < 3 )
        mex = max(mex,grid[row][col] + solve(row,col+1, times+1));
    if(col+1 < C)
        mex = max(mex,solve(row,col+1, times)); 
    if(row+1 < R)
        mex = max(mex,solve(row+1, col, 0));
    x = mex;
    return x;
}
int tests(){  
    int K;
    cin >> R >> C >> K;
    forn(i,0,K){
        int r,c,v;
        cin>> r >> c >> v;
        grid[r-1][c-1] = (int64)v; 
    }
    forn(i,0,3007)
        forn(j,0,3007)
            forn(k,0,4)
                dp[i][j][k] = -1;

    cout << solve(0,0,0) << '\n';
    return 0;
}   
int main(){
    I__O ;      
    int cases = 1 ;  
    // cin >> cases ;
    while(cases--)
        tests(); 
    return 0 ; 
 
}


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

using namespace std;
int n,m;
int h[1003];
int sum[1003];
int ans1,ans2;
int main(){
	cin >> n >> m;
	for(int i = 0;i < n;i++)cin >> h[i];
	for(int i = 0;i < m;i++){
		int k;
		cin >> k;
		for(int j = 0;j < n;j++){
			if(h[j] <= k){
				sum[j]++;
				if(sum[j] > ans1){
					ans1 = sum[j];
					ans2 = j+1;
				}
				break;
			}
		}
	}
	cout << ans2 << endl;
	return 0;
}


Measured memory_bytes: 1168
#define _USE_MATH_DEFINES
#include<cstdio>
#include<math.h>
using namespace std;

struct Point {
	double x, y;
};

void koch(int n, Point a, Point b) {
	if (n == 0)return;
	Point s, t, u;
	double th = M_PI*60.0 / 180.0;

	s.x = (2.0*a.x + 1.0*b.x) / 3.0;
	s.y = (2.0*a.y + 1.0*b.y) / 3.0;
	t.x = (1.0*a.x + 2.0*b.x) / 3.0;
	t.y = (1.0*a.y + 2.0*b.y) / 3.0;
	u.x = (t.x - s.x)*cos(th) - (t.y - s.y)*sin(th) + s.x;
	u.y = (t.x - s.x)*sin(th) + (t.y - s.y)*cos(th) + s.y;

	koch(n - 1, a, s);
	printf("%.8f %.8f\n", s.x, s.y);
	koch(n - 1, s, u);
	printf("%.8f %.8f\n", u.x, u.y);
	koch(n - 1, u, t);
	printf("%.8f %.8f\n", t.x, t.y);
	koch(n - 1, t, b);
}

int main(void) {
	Point a, b;
	int n;

	scanf("%d", &n);

	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;

	printf("%.8f %.8f\n", a.x, a.y);
	koch(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);
	return 0;
}

Measured memory_bytes: 1068
N, W = [int(i) for i in input().split()]
w, v = [0]*N, [0]*N
 
for i in range(N):
  w[i], v[i] = [int(_) for _ in input().split()]
  
dp = [[0] * (W+1) for _ in range(N+1)]
# dp[i][j] i番目までの荷物で重さがjを超えないように選んだときの価値の最大値
for i in range(N):
  for j in range(W+1):
    if j < w[i]:# i番目の荷物の重さw[i]がjを超えているので，入れる可能性がない
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])# 入れ場合と入れない場合を比較
      
print(dp[N][W])

Measured memory_bytes: 120300
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> Pll;
typedef pair<P,P> PP;
#define rep(i,a,n) for(int i = a;i < n;i++)
#define LINF (ll)1e17
#define INF 1e9
#define MOD 1e9+7
#define sMOD 1e5
#define fs first
#define sc second


signed main(){
	
	ll n,a,b;
	cin >> n;
	vector<P> vec;
	
	rep(i,0,n){
		cin >> a >> b;
		vec.push_back(P(a,b));
	}
	
	sort(vec.begin(),vec.end());
	
	cout << vec[n-1].fs + vec[n-1].sc << endl;
	return 0;

}

Measured memory_bytes: 2420
from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())
ans=0
query=[]
for _ in range(Q):
    query.append(list(map(int,input().split())))

for co in combinations_with_replacement(range(1,M+1),N):
    co = sorted(co)
    t=0
    for a,b,c,d in query:
        if co[b-1]-co[a-1]==c:
            t+=d
    ans = max(ans,t)
print(ans)


Measured memory_bytes: 9200
// Aizu 0580: Fish
// 2017.10.25 bal4u@uu
// ???????????????????????±?????¨?????????????¨????

#include <stdio.h>
#include <stdlib.h>

#define MAX  52
#define MAX2 104

typedef struct { int x1, y1, d1, x2, y2, d2; } PP;
PP p[MAX];
int x[MAX2], y[MAX2], d[MAX2], sz;

int cmp(int *a, int *b) { return *a - *b; }

int main()
{
	int n, k, i, xx, yy, dd, c;
	long long ans;

	scanf("%d%d", &n, &k);
	for (sz = 0, i = 0; i < n; i++) {
		scanf("%d%d%d%d%d%d", &p[i].x1, &p[i].y1, &p[i].d1, &p[i].x2, &p[i].y2, &p[i].d2);
		x[sz] = p[i].x1, x[sz+1] = p[i].x2;
		y[sz] = p[i].y1, y[sz+1] = p[i].y2;
		d[sz] = p[i].d1, d[sz+1] = p[i].d2;
		sz += 2;
	}
	qsort(x, sz, sizeof(int), cmp);
	qsort(y, sz, sizeof(int), cmp);
	qsort(d, sz, sizeof(int), cmp);

	ans = 0;
	for (xx = 1; xx < sz; xx++) for (yy = 1; yy < sz; yy++) for (dd = 1; dd < sz; dd++) {
		c = 0;
		for (i = 0; i < n; i++) {
          if (p[i].x1 <= x[xx-1] && x[xx] <= p[i].x2 &&
              p[i].y1 <= y[yy-1] && y[yy] <= p[i].y2 &&
              p[i].d1 <= d[dd-1] && d[dd] <= p[i].d2) c++;
        }
        if (c >= k) ans += (long long)(x[xx]-x[xx-1]) * (y[yy]-y[yy-1]) * (d[dd]-d[dd-1]);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1808
class SegTreeSum:
    '''
    0-indexedで実装していることに注意
    '''

    def __init__(self, V):
        self.sz = len(V)
        N = 1
        while N < self.sz:
            N *= 2

        self.N = N
        self.node = [0] * (2 * self.N - 1)
        
        for i in range(self.sz):
            self.node[i + self.N - 1] = V[i]
        
        for i in range(self.N - 2, 0, -1):
            # 親から子ノードへアクセスする
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]
    
    def add(self,i,x):
        i += (self.N - 1)
        self.node[i] += x

        while i > 0:
            i = (i - 1) // 2
            self.node[i] = self.node[2*i+1] + self.node[2*i+2]

    def getsum(self,a,b,k=0,l=0,r=-1):
        if r < 0:
            r = self.N
        
        if b <= l or a >= r:
            return 0
        
        if a <= l and b >= r:
            return self.node[k]

        vl = self.getsum(a,b, 2*k+1, l, (l+r)//2)
        vr = self.getsum(a,b, 2*k+2, (l+r)//2, r)
        return vl + vr

def main():
    n,q = map(int, input().split())
    V = [0] * n
    seg = SegTreeSum(V)
    for _ in range(q):
        com, x, y = map(int, input().split())
        x -= 1
        if com:
            print(seg.getsum(x,y))
        else:
            seg.add(x,y)

if __name__ == "__main__":
    main()



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

long long n;
std::vector<std::pair<int,int>> tasks; 

void input()
{
    std::cin>>n;
    tasks.resize(n);
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        tasks.push_back(std::make_pair(b,a));
    }
}


int main()
{
    input();
    std::sort(tasks.begin(),tasks.end());
    bool res = true;    //時間内に仕事ができるかどうか
    long long sum = 0;  //仕事にかかってきた時間の総和
    for(auto i:tasks){
        sum += i.second;
        if(sum>i.first){
            res = false;break;
        }
    }
    std::cout<<(res?"Yes":"No")<<std::endl;
}


Measured memory_bytes: 4736
import sys
x,y=map(int,input().split())
if (x+y)%3!=0:
    print(0)
    sys.exit()
dx=x-(x+y)//3
dy=y-(x+y)//3
if dx<0 or dy<0:
    print(0)
    sys.exit()
fact=[1]*(dx+dy+1)
MOD=10**9+7
def inv_mod(a):
  return pow(a,MOD-2,MOD)

for i in range(1,dx+dy+1):
  fact[i] = (i*fact[i-1])%MOD
fact_inv = [1] * (dx+dy+1)
fact_inv[-1] = inv_mod(fact[-1])
for i in range(dx+dy,0,-1):
  fact_inv[i-1] = (i*fact_inv[i])%MOD

def comb(n,k):
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x
print(comb(dx+dy,dx))

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

int H, W;
string C[100];

int main(){
    cin >> H >> W;
    for(int i = 0; i < H; i++) cin >> C[i];
    for(int i = 0; i < H; i++) cout << C[i] << endl << C[i] << endl;

    return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
LRD = [tuple(map(int,input().split())) for i in range(M)]

class WeightedUnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self.weight = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            pa = self.root(self.parent[a])
            self.weight[a] += self.weight[self.parent[a]]
            self.parent[a] = pa
            return pa
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b,w):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self.weight[ra] = w - self.weight[a] + self.weight[b]
        else:
            self.parent[rb] = ra
            self.weight[rb] = -w - self.weight[b] + self.weight[a]
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def diff(self,a,b):
        return self.weight[a] - self.weight[b]

uf = WeightedUnionFind(N)
for l,r,d in LRD:
    l,r = l-1,r-1
    if uf.is_same(l,r):
        if uf.diff(l,r) != d:
            print('No')
            exit()
    else:
        uf.unite(l,r,d)
print('Yes')

Measured memory_bytes: 40812
import java.util.Scanner;
class Main {
  public static void main(String[] args) {
        int price = 700;
        Scanner scan = new Scanner(System.in);
        String order = scan.next();
        char[] chars = order.toCharArray();

        for (char ch : chars) {
            if (ch == 'o') {
                price += 100;
            }
        }
        System.out.println(price);
    }
}

Measured memory_bytes: 22608
n = int(input())
a = [int(i) for i in input().split()]

a = [0] + a + [0]
sum_a = 0
for i in range(len(a)-1):
    sum_a += abs(a[i+1] - a[i] )
    
for i in range(n):
    print(sum_a + abs(a[i+2]-a[i]) - abs(a[i+1]- a[i])  -abs(a[i+2]-a[i+1]))

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; ll k; cin>>n>>k;
    map<int,ll> Map;
    rep(i,n){
        int a,b; cin>>a>>b;
        Map[a]+=b;
    }
    for(auto e:Map){
        if (e.se>=k){
            cout<<e.fi<<endl;
            return 0;
        }
        k-=e.se;
    }
    return 0;
}


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

typedef long long ll;
typedef vector<ll> vl;

const ll INF = (ll)9e18;
int N;
vl S;
vector<vl> dp;

ll rec(int l, int r) {
	if (dp[l][r] != (ll)-1)
		return dp[l][r];
	if (l == r)
		return (ll)0;
	ll min_val = INF;
	for (int i = l; i < r; ++i) {
		ll val = rec(l, i) + rec(i + 1, r) + (S[r] - S[l - 1]);
		min_val = min(val, min_val);
	}
	return dp[l][r] = min_val;
}

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

	cin >> N;
	S.resize(N + 1, (ll)0);
	for (int i = 1; i <= N; ++i) {
		cin >> S[i];
		S[i] += S[i - 1];
	}

	dp.resize(N + 1, vl(N + 1, (ll)-1));
	ll ans = rec(1, N);

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


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

int main() {
	int R, C;
	cin >> R >> C;
	vector<vector<int>> matrix(R + 1, vector<int>(C + 1));
	rep(i, R)
	{
		rep(j, C)
		{
			cin >> matrix.at(i).at(j);
			matrix.at(i).at(C) += matrix.at(i).at(j);
			matrix.at(R).at(j) += matrix.at(i).at(j);
			matrix.at(R).at(C) += matrix.at(i).at(j);
		}
	}
	rep(i, R + 1)
	{
		rep(j, C)
			cout << matrix.at(i).at(j) << ' ';
		cout << matrix.at(i).at(C) << endl;
	}
}



Measured memory_bytes: 3148
/**
*    created: 05.07.2020 17:21:48
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#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(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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;}
const long double pi = acos(-1.0);
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

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

    int a, b;
    cin >> a >> b;
    cout << (a-1) * (b-1) << endl;
    return 0;
}

Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main(){
	int n;
	int i,j,k;
	int a,b,c;
	while(cin>>n){
		if(!n)break;
		a=0;
		for(i=n+1;i<=2*n;i++){
			for(j=2;j<i && j<500;j++){
				if(i%j==0)break;
			}
			if(j==500 || j==i)a++;
		}
		cout<<a<<endl;
	}
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin >> n >> k;
vector<int> high(n);
for(int i = 0; i < n; i++){
cin >>  high.at(i);
}
sort(high.begin(), high.end());
int answer = 1000000000;
for(int i; i < n - k +1; i++){
int gap;
gap = high.at(k + i - 1) - high.at(i);
if( gap < answer){
answer = gap;
}
}
cout << answer <<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using P = pair< int,int>;
using node = tuple<int,int,int>;
const int MAX_N = (1 << 21) - 1;
const int inf = numeric_limits<int>::max();

int n;
P etree[MAX_N];
P otree[MAX_N];
vector< P > v;

void init(int k,int l,int r){
  if(r - l == 1){
    etree[k] = P(inf,-1);
    otree[k] = P(inf,-1);
  }else{
    int chl = k*2+1;
    int chr = k*2+2;
    etree[k] = P(inf,-1);
    otree[k] = P(inf,-1);
    init(chl, l, (l+r)/2);
    init(chr, (l+r)/2, r);
  }
}

void update(int t,int i,int x,int k,int l, int r){
  if(l <= i && i < r){
    if(r - l == 1){
      if(t == 0)
        etree[k] = P(x,2*l);
      else
        otree[k] = P(x,2*l+1);
    }else{
      int chl = k*2+1;
      int chr = k*2+2;
      update(t,i,x,chl,l,(l+r)/2);
      update(t,i,x,chr,(l+r)/2,r);
      if(t == 0)
        etree[k] = min(etree[chl],etree[chr]);
      else
        otree[k] = min(otree[chl],otree[chr]);
    }
  }
}

P find(int t,int a,int b,int k,int l,int r){
  if(r <= a || b <= l)return P(inf,-1);
  else if(a <= l && r <= b)
    return t == 0 ? etree[k] : otree[k];
  else{
    int chl = k*2+1;
    int chr = k*2+2;
    P vl = find(t,a,b,chl,l,(l+r)/2);
    P vr = find(t,a,b,chr,(l+r)/2,r);
    return min(vl,vr);
  }
}

void rec(int l,int r){
  cout << l << " " << r << endl;
  if(r - l <= 0)return;
  P res = find(l%2,l/2,r/2,0,0,n);
  int idx = res.second;
  P res2 = find((idx+1)%2,(idx+1)/2,(r+1)/2,0,0,n);
  int idx2 = res2.second;
  rec(l,idx);
  rec(idx+1,idx2);
  rec(idx2+1,r);
  v.push_back(P(res.first,res2.first));
}

int main(void){
  cin >> n;
  init(0,0,n);
  for(int i = 0;i < n;++i){
    int a;
    cin >> a;
    update(i%2,i/2,a,0,0,n);
  }
  priority_queue< node,vector<node>,greater<node> > que;
  bool flag = false;
  que.push(node(find(0,0,n/2,0,0,n).first,
                0,n));
  while(!que.empty()){
    int m,l,r;
    tie(m,l,r) = que.top();
    que.pop();
    if(flag)cout << " ";
    flag = true;
    P res = find(l%2,l/2,r/2,0,0,n);
    int idx = res.second;
    P res2 = find((idx+1)%2,(idx+1)/2,(r+1)/2,0,0,n);
    int idx2 = res2.second;
    cout << res.first << " " << res2.first;
    if(idx - l > 0)
      que.push(node(find(l%2,l/2,idx/2,0,0,n).first,
                    l,idx));
    if(idx2 - (idx+1) > 0)
      que.push(node(find((idx+1)%2,(idx+1)/2,idx2/2,0,0,n).first,
                    idx+1,idx2));
    if(r - (idx2+1) > 0)
      que.push(node(find((idx2+1)%2,(idx2+1)/2,r/2,0,0,n).first,
                    idx2+1,r));
  }
  return 0;
}


Measured memory_bytes: 14332
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
 
#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
 
__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
 
signed main() {
  int a, b;
  cin >> a >> b;
  if(a > 8 || b > 8) {
    cout << ":(" << endl;
    
  }else {
    cout << "Yay!" << endl;
    
  }
}

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

using namespace std;

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

    long int N,Q,B,C,sum=0;
    cin>>N;

    long int arr[N]={},freq[100001]={};

    for(long int i=0;i<N;i++){
        cin>>arr[i];
        freq[arr[i]]++;
        sum+=arr[i];
    }

    cin>>Q;
    for(long int i=0;i<Q;i++){
        cin>>B>>C;
        sum-=(freq[B]*B);//cout<<freq[B]<<" before\n";
        sum+=(freq[B]*C);
        cout<<sum<<"\n";
        freq[C]+=freq[B];
        freq[B]=0;
    }


    return 0;
}


Measured memory_bytes: 5168
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
 
##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力
 
# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと
 
##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順
 
# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順
 
##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
inf = float('inf')
mod = 1000000007
 
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
    N = inputInt()
    csf = []
    for _ in range(N-1):
        c,s,f = inputMap()
        csf.append((c,s,f))
        
    ans = []
    for i in range(N-1):
        c,s,f = csf[i]
        tmp = s+c
        for j in range(i+1,N-1):
            c,s,f = csf[j]
            #print("{} {}".format(tmp,s))
            if tmp < s:
                tmp = tmp + (s-tmp) + c
            else:
                if (tmp-s)%f == 0:
                    tmp = tmp + c
                else:
                    tmp = tmp + ((-(-(tmp-s) // f))*f + s)-tmp + c
        print(tmp)
        
    print(0)
    
     
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y
         
if __name__ == "__main__":
	main()


Measured memory_bytes: 40048
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return ~n & 1; }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

string S;
string op = "+-*/";

set<int> parse(int l, int r) { // [l, r)
  set<int> res;
  int depth = 0;
  for (int i = l; i < r; i++) {
    depth += (S[i] == '(') - (S[i] == ')');
    if (depth) continue;
    if (op.find(S[i]) == string::npos) continue;
    set<int> a = parse(l, i), b = parse(i + 1, r);
    for (auto &x : a)
      for (auto &y : b) {
        if (S[i] == '+') res.emplace(x + y);
        if (S[i] == '-') res.emplace(x - y);
        if (S[i] == '*') res.emplace(x * y);
        if (S[i] == '/' && y) res.emplace(x / y);
      }
  }
  if (res.size()) return res;
  if (S[l] == '(' && S[r - 1] == ')') return parse(l + 1, r - 1);
  int x = 0;
  while (l < r) x = x * 10 + S[l++] - '0';
  return {x};
}

main {
  while (cin >> S, S != "#") cout << parse(0, S.size()).size() << endl;
}



Measured memory_bytes: 3040