akhauriyash/Code-Regression huggingface dataset:
using System;
using static System.Console;
using static System.Math;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var input = ReadLine().Split();
        int a = int.Parse(input[0]);
        int b = int.Parse(input[1]);
        if (a + b == 15) WriteLine("+");
        else if (a * b == 15) WriteLine("*");
        else WriteLine("x");
    }
}

Measured memory_bytes: 13140
//2019.5.19 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
inline int read() {
    res s=0,ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline LL Read() {
    RG LL s=0;
    res ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s;
}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=2e5+10;
const int kcz=1e9+7;
namespace MAIN {
    int n,a[N],dp[N];
    inline void add(res &x,const res &y){
        x+=y,x>=kcz?x-=kcz:1;
    }
    inline int Add(const res &x,const res &y){
        return x+y>=kcz?x+y-kcz:x+y;
    }
    inline int mul(const res &x,const res &y){
        return int(1LL*x*y%kcz);
    }
    int las[N];
    inline void MAIN(){
        n=read();
        for(res i=1;i<=n;i++)a[i]=read();
        dp[1]=1,las[a[1]]=1;
        for(res i=2;i<=n;i++)dp[i]=Add(dp[i-1],las[a[i]]<i-1?dp[las[a[i]]]:0),las[a[i]]=i;
        printf("%d\n",dp[n]);
    }
}
int main() {
//    srand((unsigned)time(NULL));
//    freopen("graph.in","r",stdin);
//    freopen("graph.out","w",stdout);
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 2560
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func gets() string {
	sc.Scan()
	return sc.Text()
}

func toInt(value string) int {
	num, _ := strconv.Atoi(value)
	return num
}

func splitWithInt(value string) []int {
	vals := strings.Split(value, " ")
	nums := make([]int, len(vals))
	for index, elem := range vals {
		nums[index] = toInt(elem)
	}
	return nums
}

func main() {
	var t int
	in := toInt(gets())
	h := in / 3600
	t = in % 3600
	m := t / 60
	s := t % 60
	fmt.Printf("%v:%v:%v\n", h, m, s)
}



Measured memory_bytes: 1120
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i=0; i<N; i++){
        int di;
        cin >> vec.at(i);
    }

    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());

    int count = 0;
    for (int i=0; i<N-1; i++){
        if(vec.at(i)-vec.at(i+1) != 0){
            count += 1;
        }
    }
    cout << count + 1 << endl;
}

Measured memory_bytes: 256
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    s = list(str(input().rstrip('\n')))
    k = int(input().rstrip('\n'))
    ts = s[k-1]
    for i in range(n):
        if s[i] != ts:
            s[i] = "*"
    print("".join(s))


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38384
s = input()
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])

if a + b + c + d  == 7:
  print(str(a)+"+"+str(b)+"+"+str(c)+"+"+str(d)+"=7")
elif a + b + c - d == 7:
  print(str(a)+"+"+str(b)+"+"+str(c)+"-"+str(d)+"=7")
elif a + b - c + d == 7:
  print(str(a)+"+"+str(b)+"-"+str(c)+"+"+str(d)+"=7")
elif a - b + c + d == 7:
  print(str(a)+"-"+str(b)+"+"+str(c)+"+"+str(d)+"=7")
elif a + b - c - d == 7:
  print(str(a)+"+"+str(b)+"-"+str(c)+"-"+str(d)+"=7")
elif a - b + c - d == 7:
  print(str(a)+"-"+str(b)+"+"+str(c)+"-"+str(d)+"=7")
elif a - b - c + d == 7:
  print(str(a)+"-"+str(b)+"-"+str(c)+"+"+str(d)+"=7")
elif a - b - c - d == 7:
  print(str(a)+"-"+str(b)+"-"+str(c)+"-"+str(d)+"=7")

Measured memory_bytes: 38256
#include <iostream>

using namespace std;

int main(){
	int a, b;
	cin >> a >> b;

	if(a > 0 && a < 10){
		if(b > 0 && b < 10)
			cout << a * b;
		else
			cout << "-1";
	}else{
		cout << "-1";
	}
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

int main(){
  long long int N, D;
  scanf("%lld%lld", &N, &D);
  
  std::cerr << "Answer:" << std::endl;
  std::cout << (N+2*D)/(2*D+1) << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long       ll;
#define MOD ((int)1e9+7)
#define N ((int)2e5+123)
void reads(string& x){ char kk[N]; scanf("%s",kk); x = kk;}

int ans, n;
string s;
void solve(){
    reads(s);
    n = (s[2] == s[3] && s[4] == s[5]);
    if(n)printf("Yes\n");
    else printf("No\n");
}

int main(){
    ios_base::sync_with_stdio(0);
    int t = 1; //scanf("%d",&t);
    for(int caso=1;caso<=t;caso++){
        solve();
    }
}

Measured memory_bytes: 3732
// In the name of God //
 
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pii pair <int, int>
using namespace std;
const ll mod = 998244353;

ll calc(vector<pii> &a) {
    int n = a.size();
    set<int> free;
    ll ans = 0;
    sort(rall(a));
    for (int i = 1; i <= n; i++)    free.insert(i);
    for (auto p : a) {
        auto it = free.upper_bound(p.second);
        if(it != free.begin()) {
            ans += p.first;
            --it;
            free.erase(it);
        }
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> pos, neg;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int k, l ,r;
        cin >> k >> l >> r;
        if(l > r) {
            ans += r;
            pos.push_back({l - r, k});
        }
        else {
            ans += l;
            neg.push_back({r - l, n - k});
        }
    }
    cout << ans + calc(pos) + calc(neg) << "\n";
}

int main()  {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int tt;
    cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    } 
}                               

Measured memory_bytes: 9628
N = int(input())
a1 = list(map(int,input().split()))
ai = [0]
ai.extend(a1)
ai.append(0)
summ = 0;
array = []
#print (ai)

for i in range(N+1):
	summ += abs(ai[i] - ai[i+1]);

for i in range(N):
	array.append(summ);

for i in range(1,N+1):
	array[i-1] -= ( abs(ai[i] - ai[i-1]) + abs(ai[i]-ai[i+1]) )
	array[i-1] += abs( ai[i-1] - ai[i+1] )

for i in range(N):
	print (array[i])


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

int main() {
	int n, m;
	cin >> n >> m;
	int j = 1, d[3] = { 1 }, p = 1e9 + 7;
	for (int i = 0; i <= m; i++) {
		int a = n + 1;
		if (i < m)
			scanf("%d", &a);
		for (; j < a; j++)
			(d[j % 3] = d[(j + 1) % 3] + d[(j + 2) % 3]) %= p;
		d[a % 3] = 0;
		j = a + 1;
	}
	cout << d[n % 3] << endl;
	return 0;
}


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

int main()
{
	int n;
	int a[3];
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[0] >> a[1] >> a[2];
		sort(a,a+3);
		if(a[2] * a[2] == (a[0] * a[0] + a[1] * a[1])){
			cout << "YES" <<endl;
		}else{
			cout << "NO" <<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1168
import bisect
import math
#----エラトステネスの篩--------
def get_primenumber(number):
    prime_list = []
    #2からnumberまでの数字をsearch_listに入れる
    search_list = list(range(2,number+1))
    while True:
      #search_listの先頭の値が√nの値を超えたら処理終了
      if search_list[0] > math.sqrt(number):
        #prime_listにsearch_listを結合
        prime_list.extend(search_list)
        break
      else:
        #search_listの先頭をprime_listに入れる
        head_num = search_list[0]
        prime_list.append(head_num)
        #search_listの先頭をpopする
        search_list.pop(0)
        #head_numの倍数を取り除く
        search_list = [num for num in search_list if num % head_num != 0]
    return prime_list

l = get_primenumber(100100)
a = int(input())
t = l[bisect.bisect_right(l,a)]
T =  l[bisect.bisect_left(l,a)]

if T == a:
    print(a)
else:
    print(t)

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

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

  int D = 0,ans = 1;
  vector<int> L(N);
  for(int i=0;i<N;i++){
    cin>>L.at(i);
    D += L.at(i);
    if(D <= X){
      ans++;
    }else{
      break;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 384
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
use std::cmp::{max,min};
fn main(){
    input!{
        n:usize,
        mut an:[usize;n],
    }
    an.sort();
    let mid = n /2;
    let under = an[mid-1];
    let top = an[mid];
    let ans = if top == under  {
        0
    } else {
        top-under
    };
    println!("{}",ans);
}


fn is_prime(x:i64) -> bool {
    if x == 2 {return true;}
    if x < 2 || x % 2 == 0 {return false;}
    let mut j = 3;
    while j <= (x as f64).sqrt() as i64 {
        if x % j == 0 {
            return false;
        }
        j += 2;
    }
    true
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void)
{

  int n, a, b, max;
  int min = 0;

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

  max = a < b ? a : b;
  if (a + b > n)
  {
    min = (a + b) - n;
  }

  printf("%d %d\n", max, min);

  return 0;
}

Measured memory_bytes: 128
import java.util.*;

public class Main {
    public static void main(String args[]) {
     
    Scanner sc = new Scanner(System.in);
    
   long s = sc.nextLong();
    long ans=0;
    ans +=s/500*1000;
    s%=500;
    ans+=s/5*5;
    System.out.println(ans);

        
    }
    static boolean util(String s){
        if(s.length()<6)
        return false;
        
        if(s.charAt(2)!=s.charAt(3) ||s.charAt(4)!=s.charAt(5))
        return false;
        else
        return true;
    }
}

Measured memory_bytes: 25300
#pragma warning(disable:4996)
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define pb push_back
#define mp make_pair
#define fill(x,y) memset(x,y,sizeof(x))
#define even(x) x % 2 == 0
#define odd(x) x % 2 != 0

const ll INF_LL = (1ll << 60);
const int INF_INT = (int)1e9;
const ll MOD_CONST = (ll)(1e9 + 7);

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(void)
{
	cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20);

	int N; cin >> N;
	bool equal = true;
	ll ans = 0;
	ll mb = INT64_MAX;
	REP(i, N) {
		ll a, b; cin >> a >> b;
		if (a != b) equal = false;
		ans += a;
		if (a > b) chmin(mb, b);
	}
	if (equal)
		cout << 0 << endl;
	else
		cout << ans - mb << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<tuple>
using namespace std;
tuple<int,int,char,long long,string>a[1<<17];
main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        int A,b;char c;long long d;string e;
        cin>>A>>b>>c>>d>>e;
        a[i]=make_tuple(A,b,c,d,e);
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        cout<<get<0>(a[i])<<" "<<get<1>(a[i])<<" "<<get<2>(a[i])<<" "<<get<3>(a[i])<<" "<<get<4>(a[i])<<endl;
    }
}


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

#include <atcoder/all>

// #LIB#

using namespace std;
using namespace atcoder;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#ifdef ONLINE_JUDGE
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');
#endif

int main() {
  ll n, m;
  cin >> n >> m;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  const int mf0 = n * m, mf1 = n * m + 1;
  mf_graph<ll> mf(n * m + 2);
  rep(i, n) rep(j, m) {
    if (s[i][j] == '#') continue;
    auto v = i * m + j;
    if ((i + j) % 2 == 0) {
      mf.add_edge(mf0, v, 1);
    } else {
      mf.add_edge(v, mf1, 1);
    }
  }
  rep(i, n) rep(j, m) {
    if ((i + j) % 2 != 0 || s[i][j] == '#') continue;
    const ll dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
    rep(k, 4) {
      auto i2 = i + dx[k], j2 = j + dy[k];
      if (0 <= i2 && i2 < n && 0 <= j2 && j2 < m && s[i2][j2] == '.') {
        mf.add_edge(i * m + j, i2 * m + j2, 1);
      }
    }
  }
  cout << mf.flow(mf0, mf1) << endl;
  itr(e, mf.edges()) {
    if (e.from == mf0 || e.to == mf1 || e.flow == 0) continue;
    int i0 = e.from / m, j0 = e.from % m;
    int i1 = e.to / m, j1 = e.to % m;
    if (i0 == i1 + 1) {
      s[i1][j1] = 'v';
      s[i0][j0] = '^';
    } else if (j0 == j1 + 1) {
      s[i1][j1] = '>';
      s[i0][j0] = '<';
    } else if (i0 == i1 - 1) {
      s[i0][j0] = 'v';
      s[i1][j1] = '^';
    } else {
      s[i0][j0] = '>';
      s[i1][j1] = '<';
    }
  }
  itr(x, s) cout << x << endl;
}


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

template<typename T>
void read(T &n){
    n = 0;
    T f = 1;
    char c = getchar();
    while(!isdigit(c) && c != '-') c = getchar();
    if(c == '-') f = -1, c = getchar();
    while(isdigit(c)) n = n*10+c-'0', c = getchar();
    n *= f;
}
template<typename T>
void write(T n){
    if(n < 0) putchar('-'), n = -n;
    if(n > 9) write(n/10);
    putchar(n%10+'0');
}

int n, q;
ll m, x, P, d[MAX];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        read(d[i]);
    }
    while(q--){
        read(m), read(x), read(P);
        ll s1 = 0, s2 = x;
        for(int i = 1; i <= n; i++){
            if(d[i]%P == 0) s1 += ((m-1)/n+(i-1<(m-1)%n));
            else s2 += ((m-1)/n+(i-1<(m-1)%n))*(d[i]%P);
        }
        s2 = s2/P-x/P;
        write(m-1-s1-s2), puts("");
    }

    return 0;
}

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

typedef pair<int,int> P;

int nextInt() {
  int x; scanf("%d", &x); return x;
}

const int MAX_N = 100000 + 10;

map<P, vector<int> > g;
vector<P> es[MAX_N];

struct State {
  int pos;
  int pc;
  int cost; 
  State(int a, int b, int c) : pos(a), pc(b), cost(c) {}
};

struct L {
  int p, q, c;
  L (int p, int q, int c) : p(p), q(q), c(c) {}
  bool operator<(const L& o) const {
    return p < o.p;
  }
};

int main() {
  int N = nextInt();
  int M = nextInt();

  vector<L> vl;
  for (int i = 0; i < M; i++) {
    int p = nextInt() - 1;
    int q = nextInt() - 1;
    int c = nextInt();
    es[p].emplace_back(q, c);
    es[q].emplace_back(p, c);
    g[P(p,c)].push_back(q);
    g[P(q,c)].push_back(p);
  }

  int ans = -1;
  map<P, int> memo; // 0なら存在しないノード、最小値は 1 
  deque<State> pq;
  pq.emplace_back(0, 0, 1); // 今いる駅, 最後に使った会社, コスト
  memo[P(0,0)] = 1;
  while (!pq.empty()) {
    const State state = pq.front();
    pq.pop_front();
    // const int cost = memo[P(state.pos, state.pc)];
    // if (state.cost != cost) continue;
    const int cost = state.cost;
    if (state.pos == N - 1 && state.pc == -1) {
      ans = cost - 1;
      break;
    }


    if (state.pc != -1) for (int next_pos : g[P(state.pos, state.pc)]) {
      P e(next_pos, state.pc);
      int next_cost = cost;
      auto f = memo.find(e);
      if (f == memo.end() || f->second > next_cost) {
        memo[e] = next_cost;
        if (state.pc == e.second) 
          pq.emplace_front(e.first, e.second, next_cost);
        else
          pq.emplace_back(e.first, e.second, next_cost);
      }
    }

    if (state.pc == -1) {
      for (P e : es[state.pos]) {
        int next_cost = cost + 1;
        auto f = memo.find(e);
        if (f == memo.end() || f->second > next_cost) {
          memo[e] = next_cost;
          if (state.pc == e.second) 
            pq.emplace_front(e.first, e.second, next_cost);
          else
            pq.emplace_back(e.first, e.second, next_cost);
        }
      }
    }
    else
    {
      int next_pos = state.pos;
      int next_pc = -1;
      P e(next_pos, next_pc);
      int next_cost = cost ;
      auto f = memo.find(e);
      if (f == memo.end() || f->second > next_cost) {
        memo[e] = next_cost;
        if (state.pc == e.second) 
          pq.emplace_front(e.first, e.second, next_cost);
        else
          pq.emplace_back(e.first, e.second, next_cost);
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 77952
n,s,t,b;
double P[16][9];
main(){
	int i;
	for(;scanf("%d%s%s%s",&n,&s,&t,&b)*n;){
		memset(P,0,sizeof(P));
		P[n][s-'A']=1;
		for(;n--;){
			for(i=0;i<9;i++){
				P[n][i/3>0&&i-3!=b-'A'?i-3:i]+=P[n+1][i]/4;
				P[n][i/3<2&&i+3!=b-'A'?i+3:i]+=P[n+1][i]/4;
				P[n][i%3>0&&i-1!=b-'A'?i-1:i]+=P[n+1][i]/4;
				P[n][i%3<2&&i+1!=b-'A'?i+1:i]+=P[n+1][i]/4;
			}
		}
		printf("%f\n",P[0][t-'A']);
	}
}

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

int main() {
	char b;
	cin >> b;

	map<char, char> base = {
		{'A', 'T'},
		{'T', 'A'},
		{'C', 'G'},
		{'G', 'C'}
	};
	cout << base[b] << endl;
}

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

typedef long long ll;
const long long LINF = 1LL << 60;
const long long LMINF = 1LL << 63;
const int INF = 1 << 30;

#define REP(i,n) for(int i = 0;i < n;++i)
#define REPS(i,x) for(int i = 1;i <= (int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i >= 0;i--)
#define RREPS(i,x) for(int i=((int)(x));i > 0;i--)
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << ": " << x << "\n"

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(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    if(n == 1 || n == 2 || n == 4){
        cout << 4 << endl;
        return 0;
    }
    int cnt = 0;
    while(1){
        if(n == 4){
            cout << cnt + 4 << endl;
            break;
        }
        if(n % 2 == 0){
            n = n / 2;
        }else{
            n = n * 3 + 1;
        }
        cnt++;
    }

    return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cstdio>

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int main(){
    int N;
    
    while (1) {
        scanf("%d", &N);
        if (N == 0)
            break;
        vector< pair<int, int> > v;
        rep(i, N){
            int takara, bridge;
            scanf("%d%d", &takara, &bridge);
            v.push_back(make_pair(bridge, takara));
        }

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

        int amount = 0;
        int success = 1;
        rep(i, N){
            amount += v[i].second;
            if ( amount > v[i].first ){
                success = 0;
                break;
            }
        }

        printf(success ? "Yes\n" : "No\n");
    }
}

Measured memory_bytes: 3132
#include <iostream>

using namespace std;

int cost[1000][1000];
int mincost[1000];
char used[1000];
int V;



int prim(void)
{
    int i;
    int res;
    int u, v;
    
    for (i = 0; i < V; i++){
        mincost[i] = 1000000000;
        used[i] = 0;
    }
    
    mincost[0] = 0;
    res = 0;
    
    while (1){
        v = -1;
        for (u = 0; u < V; u++){
            if (!used[u] && (v == -1 || mincost[u] < mincost[v])){
                v = u;
            }
        }
        
        if (v == -1){
            break;
        }
        used[v] = 1;
        res += mincost[v];
        
        for (u = 0; u < V; u++){
            mincost[u] = min(mincost[u], cost[v][u]);
        }
    }
    return (res);
}

int main(void)
{
    int num, from, to, dist;
    int ans;
    int i, j;
    
    while (1){
        scanf("%d", &V);
        if (V == 0){
            break;
        }
        scanf("%d", &num);
        
        for (i = 0; i < V; i++){
            for (j = 0; j < V; j++){
                cost[i][j] = 1000000000;
            }
        }
        
        for (i = 0; i < num; i++){
            scanf("%d,%d,%d", &from, &to, &dist);
            cost[from][to] = cost[to][from] = (dist / 100) - 1;
        }
        ans = prim();
        printf("%d\n", ans);
    }
    return (0);
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
using namespace std;


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

int main(){
    long long N;
    long long mod= 1000000007;
    cin >> N;
    long long ans = 0;
    if(N == 1){
        cout << 0 << endl;
        return 0;
    }
    long long tmp =1;
    for(int i=0; i < N; ++i){
        tmp *= 8;
        tmp %= mod;
    }
    //ans += tmp;
    //ans %= mod;

    long long tmp2 = 1;
    for(int i=0; i < N; ++i){
        tmp2 *= 9;
        tmp2 %= mod;
    }

    long long tmp3=1;
    for(int i=0; i < N; ++i){
        tmp3 *= 10;
        tmp3 %= mod;
    }

    ans = tmp3-((2*tmp2)%mod)+tmp;
    if(ans < 0){
        ans += mod;
    }

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

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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> cnt(10001,0);
  for(int a=1;a<101;a++){
    for(int b=1;b<101;b++){
      for(int c=1;c<101;c++){
        if(a*a+b*b+c*c+a*b+b*c+c*a<=10000){
          cnt[a*a+b*b+c*c+a*b+b*c+c*a]++;
        }
      }
    }
  }
  for(int i=1;i<n+1;i++){
    cout << cnt[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] as = new int[n];
		int count4 = 0;
		int countOdd = 0;
		
		for(int i=0; i<as.length; i++) {
			as[i] = sc.nextInt();
			if(as[i]%4 == 0) {
				count4 += 1;
			}else if(as[i]%2 != 0) {
				countOdd += 1;
			}
		}
		sc.close();
		
		if(n != count4+countOdd) {
			if(count4 >= countOdd) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}else {
			if(count4 >= countOdd-1) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}
		

	}

}


Measured memory_bytes: 50332
#include<iostream>
#include<string>
#include<map>
using namespace std;int main(){string s,m,l;for(map<string,int>d;cin>>s;l=s.size()>l.size()?s:l)m=++d[s]>d[m]?s:m;cout<<m<<" "<<l<<endl;return 0;}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;
 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;
 
int main ()
{
  prep();
  long long n;
  cin >> n;
  if (n%2 == 1){
      cout << 0;
  }else{
      long long sum = 0;
      long long fives = 0;
      long long poww = 10;
      for (int i=1; i<19; i++){
          long long val = n/poww;
          long long poww2 = 5;
          for (int i=1; i<27; i++){
              long long val2 = val/poww2;
              sum += val2/2+val2%2; 
              poww2 *= 5;
          }
          sum += val; 
          poww *= 10;
      }
     
      // in n count all ones divisible by 10 and 5 except 10's
      cout << sum;
  }   
  return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
static const int MAX = 100000;

vector<int> G[MAX];
list<int> out;
bool V[MAX];
int N;

void dfs(int u) {
  V[u] = true;
  for ( int i = 0; i < G[u].size(); i++ ) {
    int v = G[u][i];
    if ( !V[v] ) dfs(v);
  }
  out.push_front(u);
}

int main() {
  int s, t, M;

  cin >> N >> M;

  for ( int i = 0; i < N; i++ ) V[i] = false;

  for ( int i = 0; i < M; i++ ) {
    cin >> s >> t;
    G[s].push_back(t);
  }

  for ( int i = 0; i < N; i++ )
    if ( !V[i] ) dfs(i);

  for ( list<int>::iterator it = out.begin(); it != out.end(); it++ )
    cout << *it << endl;

  return 0;
}


Measured memory_bytes: 6200
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,m;
    cin>>n;
    ll a[n+2];
    ll cnt[100005]={0};
    ll sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        cnt[a[i]]++;
    }
    cin>>m;
    while(m-->0){
        ll x,y;
        cin>>x>>y;
        sum+=(y-x)*cnt[x];
        cout<<sum<<endl;
        cnt[y]+=cnt[x];
        cnt[x]=0;
    }
}


Measured memory_bytes: 5180
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  string s;
  cin >> s;
  bool ok = false;
  if(s[0] == s[1] && s[1] == s[2]) ok = true;
  if(s[1] == s[2] && s[2] == s[3]) ok = true;


  if(ok) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

using namespace std;

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


int main() {
    int a, b; cin >> a >> b;
    if(a > 9 || b > 9){
        cout << -1;
    }else{
        cout << a*b;
    }
}

Measured memory_bytes: 256
import math

N, K = map(int, input().split())
mod = 10**9 + 7
ans = 0

for i in range(K, N + 2):
    a = N - i + 1
    n_max = i * (2 * a + i - 1) // 2
    n_min = i * (i - 1) // 2
    ans += n_max - n_min + 1
    ans %= mod

print(ans)


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

typedef long long ll;
const ll MOD=1e9+7ll;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll g=exgcd(b,a%b,x,y);
	ll temp=x;
	x=y;
	y=temp-(a/b)*y;
	return g;
}

ll  inverse(ll a,ll m)
{
	ll x,y;
	int g=exgcd(a,m,x,y);
    
	return (x%m+m)%m;
}

ll C(ll n,ll m,ll p)
{
	ll ans=1;
	
	for(ll i=1;i<=m;i++)
	{
		ans=ans*(n-m+i)%p;
		ans=ans*inverse(i,p)%p;
	}
   return ans;
}

long long binarypow(long long a,long long b,long long m)
{
	long long mul;
	if(b==0) return 1;
	if(b%2==0)
	{
		mul=binarypow(a,b/2,m)%m;
		return mul*mul%m;
	}
	else
	{
		mul=binarypow(a,b-1,m)%m;
		return a*mul%m;
	}
}


int main()
{
	ll ans,sum=0;
	ll n,a,b;
	cin>>n>>a>>b;
	
    ans=C(n,a,MOD)+C(n,b,MOD);
    sum=((binarypow(2ll,n,MOD)-1ll-ans)%MOD+MOD)%MOD;
//ans=((pow(2ll,n)-C(n,a)-C(n,b)-1ll)%MOD+MOD)%MOD;


	cout<<sum<<endl;

   return 0;
}

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

using namespace std;

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

  vector<int> l(n);
  for (int& val : l) cin >> val;
  
  sort(l.begin(), l.end());
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1, jj = i + 1; j < n; ++j) {
      while (jj < n && l[i] + l[j] > l[jj]) ++jj;
      ans += jj - j - 1;
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main() {
  int N;
  int AC = 0;
  int RE = 0;
  int WA = 0;
  int TLE = 0;
  cin >> N;
  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    if (s == "AC") AC+=1;
    if (s == "RE") RE+=1;
    if (s == "WA") WA+=1;
    if (s == "TLE") TLE+=1;
  }
  cout << "AC x " << AC << endl;
  cout << "WA x " << WA << endl;
  cout << "TLE x " << TLE << endl;
  cout << "RE x " << RE << endl;
}

Measured memory_bytes: 3628
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define p pair<int,int>
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
using namespace std;
int POW(int x,int y){return int(pow(double(x),double(y)));}

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

	int m=0;
	int a=0;
	FOR(i,1,n){
		if(s[i]=='W'){
			m++;
		}
	}
	a=m;
	FOR(i,1,n){
		if(s[i-1]==s[i]){
			if(s[i]=='E'){
				m++;
			}else{
				m--;
			}
		}
		a=max(a,m);
	}
	cout<<n-1-a<<endl;

}


Measured memory_bytes: 900
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <set>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

typedef long long ll;
typedef long long int llt;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < 6;i++){
        if(s[i]=='1')
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
def A():
    n, x, t = map(int, input().split())
    print(t * ((n+x-1)//x))

def B():
    n = list(input())
    s = 0
    for e in n:
        s += int(e)
    print("Yes" if s % 9 == 0 else "No")

def C():
    int(input())
    a = list(map(int, input().split()))
    l = 0
    ans = 0
    for e in a:
        if e < l: ans += l - e
        l = max(l, e)
    print(ans)

A()


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

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

    sort(a.begin(),a.end(),greater<int>());
    int alice=0,bob=0;
    for ( int i = 0 ; i < n ; i++){
        if (i%2 == 0) alice += a[i];
        else bob += a[i];
    }
    int ans = alice - bob;
    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
s = input()

b = [0 if si == 'o' else 1 for si in s]

for i in range(4):
    sw = [i & 1] + [(i >> 1) & 1] + [0] * (N - 2)

    for k in range(2, N):
        sw[k] = b[k - 1] ^ sw[k - 1] ^ sw[k - 2]

    if b[N - 1] != (sw[N - 2] ^ sw[N - 1] ^ sw[0]):
        continue
    if b[0] != (sw[N - 1] ^ sw[0] ^ sw[1]):
        continue

    ans = ['W' if si else 'S' for si in sw]
    print(''.join(ans))
    quit()

print(-1)

Measured memory_bytes: 6364
#include"bits/stdc++.h"
using namespace std;

int main() {
	string SA, SB, SC;
	cin >> SA >> SB >> SC;
	char judge = 'a';
	reverse(SA.begin(), SA.end());
	reverse(SB.begin(), SB.end());
	reverse(SC.begin(), SC.end());
	while (true) {
		if (judge == 'a') {
			if (SA.size() == 0) {
				puts("A");
				return 0;
			}
			judge = SA[SA.size() - 1];
			SA.pop_back();
		}
		else if (judge == 'b') {
			if (SB.size() == 0) {
				puts("B");
				return 0;
			}
			judge = SB[SB.size() - 1];
			SB.pop_back();
		}
		else {
			if (SC.size() == 0) {
				puts("C");
				return 0;
			}
			judge = SC[SC.size() - 1];
			SC.pop_back();
		}
	}
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = RInt();
            int[] mountains = RArInt();

            int res = 0;
            for (int i = 0; i < mountains.Length; i++)
            {
                bool flg = false;
                for (int j = 0; j < i; j++)
                {
                    if (mountains[i] < mountains[j])
                    {
                        flg = true;
                        break;
                    }
                }
                if(!flg)res++;
            }
            Console.WriteLine(res);
        }
        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RArSt(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RArInt(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RArLong(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RArDouble(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }
}


Measured memory_bytes: 13140
#pragma warning disable

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Numerics;
using System.Collections;
using System.Timers;

static class MainClass
{
    public static void Main(string[] args)
    {
        var s = Console.ReadLine();
        Console.WriteLine(s.Substring(0,4) + " " + s.Substring(4));
    }

    #region ライブラリ

    #region 文字列処理

    public static int ToInt32(this string str)
    {
        
return int.Parse(str);
    }
    public static List<string> SplittedStringToList(this string str)
    {
        return str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
            .ToList();
    }
    public static List<int> SplittedStringToInt32List(this string str)
    {
        return str.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToList();
    }
    #endregion
    #region DeepClone
    public static T DeepClone<T>(this T src)
    {
        using (var memoryStream = new MemoryStream())
        {
            var binaryFormatter
              = new BinaryFormatter();
            binaryFormatter.Serialize(memoryStream, src);
            memoryStream.Seek(0, SeekOrigin.Begin);
            return (T)binaryFormatter.Deserialize(memoryStream);
        }
    }
    #endregion

    public static int Gcd(int a,int b)
    {
        if (b == 0)
            return a;
        return Gcd(b, a % b);
    }
    #endregion
}


Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(void){
    int n;
    cin >> n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];

    map<int, int> p;
    for(int i=1;i<=n;i++){
        p[i-a[i]]++;
    }
    long long ans = 0;
    for(int i=1;i<=n;i++){
        p[i-a[i]]--;
        ans += p[a[i]+i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 20592
#include<iostream>
#include<cstring>
#define N 2019
using namespace std;
int has[N];
int main()
{
	int L, R; cin >> L >> R;
	
	memset(has,0,sizeof has);
	for(int a = L, ctr = 0; a <= R && ctr < 2019; a++,ctr++)
		has[a%2019]++;
		
	int ans = ((L%2019)*(R%2019))%2019;
	for(int a = 0; a < 2019; a++)
		for(int b = 0; b < 2019; b++)
			if((a==b && has[a] >= 2)||(a != b && has[a] >= 1 && has[b] >= 1))
				ans = min(ans,(a*b)%2019);
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main (int argc, char * const argv[]) {
    // insert code here...
    double a, b, c, d, e, f, x, y;
	while(cin >> a >> b >> c >> d >> e >> f ){
		x=(c*e-b*f)/(a*e-b*d);
		y=(c*d-a*f)/(b*d-a*e);
		
		x*=1000;y*=1000;
		if(x<0){
			x-=0.5;
		}else{
			x+=0.5;
		}
		if(y<0){
			y-=0.5;
		}else{
			y+=0.5;
		}
		int xi = (int)x;
		int yi = (int)y;
		x = (double)xi;
		y = (double)yi;
		x/=1000;y/=1000;
		
		printf("%.3f %.3f\n", x, y);
	} 
	return 0;
}

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

#define PI 6.28318530717958623200

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

	double R;

	cin >> R;

	cout << fixed;
	cout.precision(16);
	
	cout << R*PI << '\n';
	return 0;
}

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

char color[50][50];
int H, W;

bool judge(int t, int y) {
    bool judgement = false;
    if(t - 1 >= 0 && color[t - 1][y] == '#') judgement = true;
    if(y - 1 >= 0 && color[t][y - 1] == '#') judgement = true;
    if(t + 1 < H && color[t + 1][y] == '#') judgement = true;
    if(y + 1 < W && color[t][y + 1] == '#') judgement = true;
    return judgement;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            cin >> color[i][j];
        }
    }

    string ans = "Yes";
    for(int i = 0; i < H; ++i) {
        for(int j = 0; j < W; ++j) {
            if(color[i][j] == '#') {
                if(!judge(i, j)) {
                    ans = "No";
                    break;
                }
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

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; }

vector<int> v, w;

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

	int n;
	cin >> n;

	vector<int> v(n), w(n);
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	int hn = min(n, 520);
	int max_l = 101010;
	vector<vector<int>> dp(hn + 1, vector<int>(max_l, 0));

	for(int i = 1; i <= hn; i++){
		if(i > 1) dp[i] = dp[i/2];
		for(int j = max_l - 1; j >= w[i]; j--){
			chmax(dp[i][j], dp[i][j - w[i]] + v[i]);
		}
	}

	int q;
	cin >> q;

	while(q-- > 0){
		int p, l;
		cin >> p >> l;

		vector<pii> a;
		while(p > hn){
			a.push_back({v[p], w[p]});
			p /= 2;
		}

		int k = a.size();
		int ans = 0;
		for(int f = 0; f < (1 << k); f++){
			int sv = 0, sw = l;
			rep(i, k){
				if((f >> i) & 1){
					sv += a[i].first;
					sw -= a[i].second;
				}
			}

			if(sw >= 0) chmax(ans, sv + dp[p][sw]);
		}

		cout << ans << endl;
	}
}


Measured memory_bytes: 212008
#include <cstdio>

//N is array size
int A[1000 + 10], N;

void trace(int A[], int N);
void insertionSort(int A[], int N);

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) { scanf("%d", &A[i]); }

  insertionSort(A, N);

  return 0;
}

//display Array
void trace(int A[], int N) {

  for (int i = 0; i < N; ++i) {
    if (i) { printf(" "); }
    printf("%d", A[i]);
  }

  printf("\n");
}

void insertionSort(int A[], int N) {
  for (int i = 0; i < N; ++i) {
    int j = i - 1;
    int v = A[i];

    while (j >= 0 && v < A[j]) {
      A[j + 1] = A[j];
      j--;
    }

    A[j + 1] = v;
    trace(A, N);
  }
}

Measured memory_bytes: 1032
import sys
n = int(input())
a_dict = {}
max_val = 1
max_key_list = []
for s in sys.stdin:
  s = s.rstrip()
  if s not in a_dict:
    a_dict[s] = 1
    if max_val == 1:
      max_key_list.append(s)
  else:
    a_dict[s] += 1
    if a_dict[s] > max_val:
      max_val = a_dict[s]
      max_key_list = [s]
    elif a_dict[s] == max_val:
      max_key_list.append(s)
max_key_list.sort()
for s in max_key_list:
  print(s)

Measured memory_bytes: 33416
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>
#include<queue>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

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

	long double a, b, x;
	cin >> a >> b >> x;

	long double PI = 3.14159265358979323846;
	long double ans;
	if (2 * x <= a * a * b) {
		ans = (long double)atan(a * b * b / 2 / x) *180/ PI;
	}
	else {
		ans= (long double)atan((2*a*a*b-2*x)/a/a/a) *180/ PI;
	}

	printf("%.10Lf\n", ans);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define max(a, b)	(((a) > (b)) ? (a) : (b))		/* ２個の値の最大値 */
#define min(a, b)	(((a) < (b)) ? (a) : (b))		/* ２個の値の最小値 */
#define ENTER		printf("\n")					/* 改行プリント */
int DBG = 1;										/* デバッグプリント 提出時は0 */
/* main *************************************************************/
int main()
{
	int		a,b,c,i,j,k,n,m,x,y,ans = 0;
	char	str[256];
	
	scanf("%s", str);

	if (str[0]=='S') {
		strcpy(str,"Cloudy");
	} else if (str[0] == 'C') {
		strcpy(str,"Rainy");
	} else {
		strcpy(str,"Sunny");
	}
		
	printf("%s\n",str);


	return 0;
}


Measured memory_bytes: 128
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    s = S()
    for i, si in enumerate(s):
        if i % 2:
            if si == "R":
                print("No")
                return
        else:
            if si == "L":
                print("No")
                return
    print("Yes")
    return

# C


def C():
    n, k, q = LI()
    d = [0] * n
    for _ in range(q):
        a = II() - 1
        d[a] += 1
    for a in d:
        if k - (q - a) > 0:
            print("Yes")
        else:
            print("No")
    return

# D


def D():
    n, = LI()
    a = LI()
    q = []
    for ai in a:
        heappush(q, ai)
    for _ in range(m):
        heappush(q, heappop(q) / 2)
    ans = 0
    while q:
        ans += int(heappop(q))
    print(ans)
    return

# E


def E():
    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    A()


Measured memory_bytes: 39152
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int x=c-a,y=d-b;
	rep(i,y)cout<<"U";
	rep(i,x)cout<<"R";
	rep(i,y)cout<<"D";
	rep(i,x)cout<<"L";
	cout<<"L";
	rep(i,y+1)cout<<"U";
	rep(i,x+1)cout<<"R";
	cout<<"DR";
	rep(i,y+1)cout<<"D";
	rep(i,x+1)cout<<"L";
	cout<<"U"<<endl;
}










Measured memory_bytes: 256
#include<stdio.h>
 
int main(void){
	int N;

	scanf("%d",&N);

	if(N<=111)
		printf("111\n");
	else if(N<=222)
		printf("222\n");
	else if(N<=333)
		printf("333\n");
	else if(N<=444)
		printf("444\n");
	else if(N<=555)
		printf("555\n");
	else if(N<=666)
		printf("666\n");
	else if(N<=777)
		printf("777\n");
	else if(N<=888)
		printf("888\n");
	else if(N<=999)
		printf("999\n");

	return 0;
	}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep0(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<string, int, int> TU;

int main()
{
    int A,B;
    cin >> A >> B;
    cout << A/(double)B;
}


Measured memory_bytes: 3788
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
	int n;
	cin>>n;
	string s[100];
	for(int i=0;i<n;i++)cin>>s[i];
	int m;
	cin>>m;
	string t[100];
	for(int i=0;i<m;i++)cin>>t[i];
	int c;
	int d=0;
	for(int i=0;i<n;i++){
		c=0;
		for(int j=0;j<n;j++){
			if(s[i]==s[j])c++;
		}
		for(int j=0;j<m;j++){
			if(s[i]==t[j])c--;
		}
		if(d<c)d=c;
	}
	cout<<d<<endl;
	return 0;
}


Measured memory_bytes: 256