akhauriyash/Code-Regression huggingface dataset:
import math
stage = int(input())
while True:
    ans = [0 for n in range(stage)]
    for n in range(stage):
        if n == 0:
            try:
                ans[0] += 1
                ans[1] += 1
                ans[2] += 1
            except:
                pass
        else:
            if n - 3 < 0:
                ans[n] = ans[n] + sum(ans[:n])
            else:
                ans[n] = sum(ans[n-3:n])
    print(math.ceil(ans[-1] / 3650))
    stage = int(input())
    if stage ==0:
        break

Measured memory_bytes: 7652
#include <bits/stdc++.h>
using namespace std;
// x^y≡x^(y%(p-1))mod p
// but there is a condition that x needs to be coprime to p
///assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
typedef long long int ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
#define  pb push_back
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define tests() int test_cases ; cin >> test_cases ; while(test_cases--)
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define MAXN 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define sp " "
#define MS(x,y) fill_n(*x, sizeof x / sizeof **x, y);
#define mem(x,y) memset(x,y,sizeof(x));
#define INF 1000000000000000000
ll power(ll x, ll y,ll p) 
{ 
    ll res = 1;     // Initialize result 
    x = x % p;
    if (y==0)return 1;
    if(x==0)return 0;   
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p;    
        y = y>>1; // y = y/2 
        x = (x*x) % p;  // Change x to x^2 
    } 
    return res; 
}
int gcd(int a, int b) { if (a == 0)return b;return gcd(b % a, a);} 

ll modinv(ll a,ll p){return power(a,p-2,p);}
vll adj[MAXN];
int solve(){
    ll n,m;
    cin>>n>>m;
    vll h(n+1);
    f(i,0,n){
        cin>>h[i+1];
    }
    f(i,0,m){
        ll a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ll cnt =0;
    fo(i,1,n){
        bool ans = true;
        for(auto x: adj[i]){
            if (h[x]>=h[i])
            {
                ans = false;
            }
        }
        if (ans)
        {
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);



    
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif

    

    // tests(){solve();}
    solve();
    return 0;
}/*#ifndef ONLINE_JUDGE
    #endif*/

    // make_pair make_tuple  tuple<int,int,int> continue resize insert

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n; cin >> n;
	vl a(n), b(n);
	FOR(i,0,n) cin >> a[i] >> b[i];
	sort(all(a)), sort(all(b));
	
	if (n%2 == 1) {
		ll lo = a[n/2], hi = b[n/2];
		cout << hi-lo+1 << endl;
	} else {
		ll lo = a[n/2-1]+a[n/2];
		ll hi = b[n/2-1]+b[n/2];
		cout << hi-lo+1 << endl;
	}
}



Measured memory_bytes: 6364
#include <cstdio>
#include <cstring>
#include <bitset>
#include <cctype>
#include <algorithm>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
int q, a, b, c, d, k;
int resA(int i) { return a-i/(k+1)*k-i%(k+1); }
int resB(int i) { return b-i/(k+1); }
bool valid(int mid) {  return resB(mid) <= 1ll*resA(mid)*k; }
int main()
{
    q = read();
    while(q--)
    {
        a = read(), b = read(), c = read(), d = read(), k = (max(a, b)-1)/(min(a, b)+1)+1;
        int l = 0, r = a+b+1;
        while(l <= r)
        {
            int mid = (l+r)>>1;
            if(valid(mid)) l = mid+1;
            else r = mid-1;
        }
        r = l+resB(l)-resA(l)*k+1;
        for(int i = c; i <= min(d, l); ++i) putchar(i%(k+1)?'A':'B');
        for(int i = max(c, l+1); i <= d; ++i) putchar((i-r)%(k+1)?'B':'A');
        puts("");
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
const int inf=8938103643641919514ll;
const int mod=1000000007ll;
const int dd[]={0,-1,0,1,0};
using namespace std;
int a,b,c,d;
int p[200000];
signed main(){
	cin>>a;
	for(int i=0;i<a;i++)
		cin>>p[i];
	sort(p,p+a);
	cout<<p[a-1]-p[0]<<endl;
}

Measured memory_bytes: 256
#d,t,s=map(int,input().split())
s=str(input())
t=str(input())
cans=10000
for i in range(len(s)-len(t)+1):
  ans=0
  for j in range(len(t)):
    if s[i]!=t[j]:
      ans+=1
    i+=1
  cans=min(ans,cans)
print(cans)

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

#define rep(i,n) for(int i=0; i<n ; ++i)
#define REP(i,a,b) for(int i=a; i<b; ++i)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

//プロトタイプ宣言
void faster(void);
ll gcd(auto , auto);
ll get_digent(auto);
ll POW(auto , auto);
ll vec_max(auto & , string);
ll vec_min(auto & , string);

int main(){
  faster();
  ll n,k;
  cin >> n >> k;
  cout << (n - 1 + k - 1 - 1)/(k - 1) << endl;
}





























//以下、ライブラリ

//同期解除
void faster(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
}

//ユークリッドの互除法
ll gcd(auto a, auto b) {
  return (b ? gcd(b, a%b) : a);
} 

//桁数取得
ll get_digent(auto x){
  string s;
  s = to_string(x);
  ll digent = s.size();
  return digent;
} 

//べき乗計算
ll POW(auto x, auto y){
  if(y==0) return 1;
  if(y%2 == 1){
    ll temp = POW(x,y-1);
    return (temp*x);
  }
  else{
    ll temp = POW(x,y/2);
    return temp*temp;
  }
} 

//配列内の最大要素の添え字取得or要素取得
ll vec_max(auto &v, string s){
  auto itr = max_element(v.begin(),v.end());
  ll element = *itr;
  ll place = itr - v.begin();
  if(s == "element") return element;
  else if(s == "place") return place;
  else return -1;
}

//配列内の最小要素の添え字取得or要素取得
ll vec_min(auto &v, string s){
  auto itr = min_element(v.begin(),v.end());
  ll element = *itr;
  ll place = itr - v.begin();
  if(s == "element") return element;
  else if(s == "place") return place;
  else return -1;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<int,int>;

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

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

    int n;
    cin >> n;

    int cnt = 0;
    int two = 0;
    rep(i, n){
        int a;
        cin >> a;
        if(a % 4 == 0) {
            cnt++;
        }else if(a % 2 == 0) {
            two++;
        }
    }

    if(two >= 2) {
        n -= two;
    }else{
        n -= 1;
    }

    if(n - cnt <= cnt){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }


    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef struct{
    string s;
    int a;
    int num;
}node;
node st[107];
bool cmp(node a,node b){
    if(a.s!=b.s)
        return a.s<b.s;
    return a.a>b.a;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>st[i].s;
        cin>>st[i].a;
        st[i].num=i;
    }
    sort(st+1,st+1+n,cmp);
    for(int i=1;i<=n;++i){
        cout<<st[i].num<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double D;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef long double ld;

#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d %d",&x,&y)
#define rl(x) scanf("%lld",&x)
#define rl2(x,y) scanf("%lld %lld",&x,&y)
#define wd(x) printf("%d" ,x)
#define wd2(x,y) printf("%d %d",x,y)
#define wl(x) printf("%lld",x)
#define wl2(x,y) printf("%lld %lld",x,y)
#define PC(x) putchar(x)
#define GC() getchar()
#define NL printf("\n")
#define SP printf(" ")
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define F first
#define S second
#define MP make_pair
#define PB push_back

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fr(i,s,e) for(int i=s;i<e;i++)
#define frl(i,s,e) for(ll i=s;i<e;i++)
#define frr(i,s,e) for(int i=s-1;i>=e;i--)
#define frv(i,a) for(int i = 0;i<(int)a.size();i++)
#define frvr(i,a) for(int i = a.size()-1;i>=0;i--)
#define tr(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end();i++)

#define inf 10000000000000
#define mod 1000000007
#define maxn 100009
#define maxr 100009
int main(){
	//sstd::ios::sync_with_stdio(false); cin.tie(NULL);
	ll x,y;
	rl2(x,y);
	ll ans=0;
	if(x==1)
		ans+=300000;
	else if(x==2)
		ans+=200000;
	else if(x==3)
		ans+=100000;
	else
		ans=ans;
	if(y==1)
		ans+=300000;
	else if(y==2)
		ans+=200000;
	else if(y==3)
		ans+=100000;
	else
		ans=ans;
	if(x==1&&y==1)
		ans+=400000;
	wl(ans);
	NL;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    int n;
    string s;
    cin >> n >> s;
    int cnt=0;
    int ans=0;
    rep(i,n){
        if(s[i] == 'I')cnt++;
        else if(s[i] == 'D')cnt--;
        ans = max(ans,cnt);
    }
 
    cout << ans << endl;
}

Measured memory_bytes: 256
def is_kaibun(kaibun):
    for i in range(len(kaibun)//2):
        if kaibun[i] != kaibun[-i-1]:
            return False
    return True

S = input()
N = len(S)

sta = (N - 1) // 2
end = (N + 3) //2

if is_kaibun(S):
    if is_kaibun(S[0:sta]):
        if is_kaibun(S[end - 1:]):
            print("Yes")
        else:
            print("No")
    else:
        print("No")
else:
    print("No") 

Measured memory_bytes: 3060
n,a,b = gets.chomp.split.map(&:to_i)
MOD = 10 ** 9 + 7
require 'openssl'
def combination_mod(n,k,mod)
  if n < k || (n < 0 || k < 0)
    0
  elsif k == 0 || k == n
    1
  else
    k = n - k if k > n - k
    x = (n-k+1..n).inject{|res,i| res * i % mod}
    y = (1..k).inject{|res,i| res * i % mod}
    inv_y = OpenSSL::BN.new(y).mod_inverse(mod)
    x * inv_y % mod
  end
end

def mod_pow(base,n,mod)
  res = 1
  if n <= 0
    res = 1
  elsif n % 2 == 0
    res = mod_pow(base,n/2,mod) ** 2
  else
    res = base * mod_pow(base,n-1,mod)
  end
  res % mod
end

puts (mod_pow(2,n,MOD) - 1 - combination_mod(n,a,MOD) - combination_mod(n,b,MOD)) % MOD

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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N;
  cin>>N;
  ll dp[101][5][5][5] = {0};
  dp[0][0][0][0] = 1;
  for (int n = 0; n < N; ++n) {
    for (int i = 0; i < 5; ++i) {
      for (int j = 0; j < 5; ++j) {
        for (int k = 0; k < 5; ++k) {
          for (int l = 1; l < 5; ++l) {
              if (i == 1 && j == 2 && l == 3) continue;
              if (i == 1 && k == 2 && l == 3) continue;
              if (j == 1 && k == 2 && l == 3) continue;
              if (j == 2 && k == 1 && l == 3) continue;
              if (j == 1 && k == 3 && l == 2) continue;
              dp[n+1][j][k][l] += dp[n][i][j][k];
              dp[n+1][j][k][l] %= MOD;
          }
        }
      }
    }
  }
  ll ans(0);
  for(int j(0);j<4;j++){
    for(int k(0);k<4;k++){
      for(int l(0);l<4;l++){
        ans += dp[N][j+1][k+1][l+1];
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 384
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner stdIn=new Scanner(System.in);
		int n=stdIn.nextInt(),a,max=0,min=1000,i;
		for(i=0;i<n;i++) {
			a=stdIn.nextInt();
			if(a>max) max=a;
			if(min>a) min=a;
		}
		System.out.print(max-min);
	}
}

Measured memory_bytes: 21844
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <forward_list>
#include <random>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 100005;

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

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    LL n, m;
    cin >> n >> m;
    
    if( n == 1 || m == 1 ) {
        if( n == m ) cout << 1;
        else if( n == 1 ) cout << m - 2;
        else cout << n - 2;
        cout << endl;
        return 0;

    }

    cout << n * m - ( n * 2 + m * 2 - 4 ) << endl;
    return 0;
}



Measured memory_bytes: 256
n,m=map(int, input().split())
ab=[list(map(int,input().split())) for i in range(m)]

from pprint import pprint

l=[[False for _ in range(n)] for _ in range(n)]
v=[True for _ in range(n)]
for a,b in ab:
    l[b-1][a-1], l[a-1][b-1]=True,True
def dfs(x,t,v,j,m,n):
    j+=1
    if j<n+m:
        v[x]=False
        for i in range(1,n):
            if v[i]:
                if t[x][i]:
                    dfs(i,t,v,j,m,n)
import copy

ans=0
for i in range(m):
    j=0
    t=copy.deepcopy(l)
    t[ab[i][1]-1][ab[i][0]-1],t[ab[i][0]-1][ab[i][1]-1]=False,False
    v=[True for _ in range(n)]
    dfs(0, t, v, j, m,n)
        
    z=False
    for x in v:
        if x:
            z=True
    if z:
        ans+=1
print(ans)

Measured memory_bytes: 3828
#include<stdio.h>
#include<math.h>

int main(void)
{
	long long int n, s[1000];
	double sum, ans;
	while (1)
	{
		sum = 0;
		ans = 0;
		scanf("%lli", &n);
		if (n == 0)break;
		for (int i = 0; i < n; i++)
		{
			scanf("%lli", &s[i]);
			sum = sum + s[i];
		}
		for (int j = 0; j < n; j++)
		{
			ans = ans + (s[j] - sum / n)*(s[j] - sum / n);
			s[j] = 0;
		}
		printf("%f\n", sqrt(ans / n));
	}
	return 0;
}

Measured memory_bytes: 1068
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


A, B = map(int, input().split())
def gcd(a,b):
    if b > a:
        return gcd(b,a)
    if b == 0:
        return a
    return gcd(a%b, b)

print(A*B//gcd(A,B))

Measured memory_bytes: 15636
# ALDS1_2_D - Shell Sort
def insertion_sort(g: int) -> None:
    global cnt
    for i in range(g, N):
        x = A[i]
        j = i - g
        while j >= 0 and A[j] > x:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = x


def main():
    global N, A, cnt
    N, *A = map(int, open(0).read().split())
    # shell sort
    G, x = [1], 1  # gap
    while 3 * x + 1 < N:
        x = 3 * x + 1
        G += [x]
    cnt = 0
    for g in G[::-1]:
        insertion_sort(g)
    print(len(G))
    print(*G[::-1])
    print(cnt)
    print(*A, sep="\n")


if __name__ == "__main__":
    main()


Measured memory_bytes: 120772
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, c[510], s[510], f[510];
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		cin >> c[i] >> s[i] >> f[i];
	}
	for (int i = 0; i < n; i++) {
		int b = 0;
		for (int j = i; j < n - 1; j++) {
			if (b < s[j]) {
				b = s[j];
			} else if (b % f[j] == 0) {
			} else {
				b = b + f[j] - b % f[j];
			}
			b += c[j];
		}
		cout << b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define MOD 998244353
#define INF 40000000000000000
int dx8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy8[8] = {1, 1, 1, 0, -1, -1, -1, 0};
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, -1, 0, 1};
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
signed main() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    N--;
    for(int n = 0; n <= N; n++) {
        int m = N - n;
        int min = A + C * n - D * m;
        int max = A + D * n - C * m;
        if(min <= B && B <= max) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}


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

bool isPrime(int a){
	if(a == 1) return false;
	else if(a == 2) return true;
	else if(a % 2 == 0) return false;

	for(int i=3; i*i<=a; i+=2){
		if(a % i == 0) return false;
	}

	return true;
}

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

	int count = 0;
	int num;
	for(int i=0; i<n; i++){
		cin >> num;
		if(isPrime(num)) count++;
	}

	cout << count << endl;
}


Measured memory_bytes: 3116
import scala.collection.mutable
import scala.io.StdIn.{readInt, readLine}

case class Node(left: Option[Int], right: Option[Int])

object Main extends App {
  import Solver.solve

  val n     = readInt()
  val lines = Iterator.fill(n)(readLine())

  val (xs, ys, zs) = solve(lines, n)

  println("Preorder")
  println(xs.mkString(" ", " ", ""))
  println("Inorder")
  println(ys.mkString(" ", " ", ""))
  println("Postorder")
  println(zs.mkString(" ", " ", ""))
}

object Solver {
  def solve(
      lines: Iterator[String],
      n: Int
  ): (List[Int], List[Int], List[Int]) = {

    val (nodes, rootId) = {
      val nodes      = mutable.Map.empty[Int, Node]
      val allNodeIds = mutable.Set(0 until n: _*)

      for {
        line <- lines
        Array(id, l, r) = line.split(' ').map { _.toInt }
      } {
        val left = if (l != -1) {
          allNodeIds -= l
          Some(l)
        } else None

        val right = if (r != -1) {
          allNodeIds -= r
          Some(r)
        } else None

        nodes(id) = Node(left, right)
      }

      val rootId = allNodeIds.head
      (nodes.toMap, rootId)
    }

    def preOrder(start: Int): List[Int] = {
      def loop(id: Int, zs: List[Int]): List[Int] = {
        val Node(left, right) = nodes(id)

        val list1 = id :: zs
        val list2 = left.fold(list1) { loop(_, list1) }
        val list3 = right.fold(list2) { loop(_, list2) }
        list3
      }
      val xs = loop(start, Nil)
      xs.reverse
    }

    def inOrder(start: Int): List[Int] = {
      def loop(id: Int, zs: List[Int]): List[Int] = {
        val Node(left, right) = nodes(id)

        val list1 = left.fold(zs) { loop(_, zs) }
        val list2 = id :: list1
        val list3 = right.fold(list2) { loop(_, list2) }
        list3
      }
      val xs = loop(start, Nil)
      xs.reverse
    }

    def postOrder(start: Int): List[Int] = {
      def loop(id: Int, zs: List[Int]): List[Int] = {
        val Node(left, right) = nodes(id)

        val list1 = left.fold(zs) { loop(_, zs) }
        val list2 = right.fold(list1) { loop(_, list1) }
        val list3 = id :: list2
        list3
      }
      val xs = loop(start, Nil)
      xs.reverse
    }

    val xs = preOrder(rootId)
    val ys = inOrder(rootId)
    val zs = postOrder(rootId)

    (xs, ys, zs)
  }
}



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

int main() {
	int a; //年齢
	int b; //金額,偶数

	cin >> a >> b;

	if (a >= 13) {
		cout << b << endl;
	}
	else if (6 <= a && a <= 12) {
		cout << (b / 2) << endl;
	}
	else {
		cout << 0 << endl;
	}
}

Measured memory_bytes: 3152
#include <iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<array>
#include<functional>
#include<iomanip>
#include<ios>
using namespace std;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)

typedef int value_type; /* ソートするキーの型 */

value_type med3(value_type x, value_type y, value_type z)
/* x, y, z の中間値を返す */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}

void quicksort(value_type a[], int left, int right,value_type index[])
/* クイックソート
 * a     : ソートする配列 
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 * index: index配列
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            tmp = index[i]; index[i] = index[j]; index[j] = tmp;
            i++; j--;
        }
        quicksort(a, left, i - 1,index);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right,index); /* 分割した右を再帰的にソート */
    }
}

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

    int c[N];
    int t[N];
    int mincost=1001;
    for(int i=0;i<N;i++){
        cin>>c[i] >> t[i];
        if(T>=t[i]){
            if(mincost>c[i]){
                mincost=c[i];
            }
        }
    }
    if(mincost==1001){
        cout << "TLE";
    }else{
        cout << mincost;
    }



  
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
#define mod 1000000007
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define forr(c, n) for (int i = c; i < n; i++)
#define forli(n) for (lli i = 0; i < n; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())

//FUNCTONS
lli llipower(lli x, lli y)
{
    lli res = 1;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x);
        y = y >> 1;
        x = (x * x);
    }
    return res;
}
lli llipowerp(lli x, lli y, lli p)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli gcd(lli a, lli b)
{
    if (!a)
        return b;
    return gcd(b % a, a);
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
void printvec(vector<T> inp)
{
    for (int i = 0; i < inp.size(); i++)
    {
        cout << inp[i] << " ";
    }
    cout << endl;
}
template <typename T>
T ceildiv(T x, T y) { return 1 + ((x - 1) / y); }
lli modInverse(lli a, lli m)
{
    lli g = gcd(a, m);
    if (g != 1)
        return -1;
    else
        return llipowerp(a, m - 2, m);
}

int main()
{
    lli n;
    cin>>n;
    lli maxh=n/500;
    cout<<maxh*1000 + ((n%500)/5)*5   <<endl;
}


Measured memory_bytes: 256
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)

	X := getInt()
	ans := 0
	a := float64(100)
	for {
		a = math.Trunc(a * 1.01)
		ans++
		if int(a) >= X {
			break
		}
	}
	out(ans)
}


Measured memory_bytes: 1756
#include<stdio.h>
int main(void)
{
	int n,m;
	scanf("%d %d",&n,&m);
	if(n%3==0||m%3==0) printf("Possible\n");
	else if((n+m)%3==0) printf("Possible\n");
	else if((n+m)%3!=0) printf("Impossible\n");
	return 0;
}	

Measured memory_bytes: 128
use std::io;
use std::cmp;

// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

// read wods on a line
pub fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

// read type t on a line
pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// sort slice
pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort();
}
// sort slice by reverse order
pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort_by(|x, y| y.cmp(x));
}

pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::min(a, b);
}

pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::max(a, b);
}

fn main() {

    let v = read_t_in_line::<i32>();
    if (v[0] - v[1]).abs() < (v[0] - v[2]).abs() {
        println!("A");
    }
    else{
        println!("B");
    }
    
}


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

using namespace std;

void dfs(int N, int pos, int lim, vector<int> &v) {
    if(N == 0) {
        cout << v[0];
        for(int i = 1; i < pos; ++i) {
            cout << ' ' << v[i];
        }
        cout << endl;
        return;
    }

    for(int i = min(lim,N); i >= 1; --i) {
        v[pos] = i;
        dfs(N-i, pos+1, i, v);
    }
}

int main() {
    while(true) {
        int N;
        cin >> N;
        if(!N) break;

        vector<int> arr(N, 0);
        dfs(N, 0, N, arr);
    }
    return 0;
}

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

int main() {
    int N, P;
    cin >> N >> P;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    
    vector<vector<long long>> dp(N + 1, vector<long long>(2, 0));
    dp[0][0] = 1;
    rep(i, N) rep(j, 2) {
        dp[i + 1][j] += dp[i][j];
        dp[i + 1][(j + A[i]) % 2] += dp[i][j];
    }
    cout << dp[N][P] << endl;
    return 0;
}

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

int main(void) {
	int A, B;
	scanf("%d %d", &A, &B);
	string S;
	cin >> S;
	string ans = "Yes";
	for (int i = 0; i < A; i++) {
		if (S[i] == '-') {
			ans = "No";
		}
	}
	if (S[A] != '-') ans = "No";
	for (int i = A + 1; i < A + B + 1; i++) {
		if (S[i] == '-') {
			ans = "No";
		}
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 3680
# 93 C - Switches
N,M = map(int,input().split())
K = []
S = []
for _ in range(M):
    s = list(map(int,input().split())) 
    K.append(s[0])
    # 0-indexed
    s = [i-1 for i in s]
    S.append(s[1:])
P = list(map(int,input().split()))

ans = 0
for i in range(1<<N):
    swiches = [0]*N
    for j in range(N):
        mask = 1<<j
        # j 番目のスイッチが on のとき
        if i & mask != 0:
            swiches[j] = 1
        # j 番目のスイッチが off のとき
        else:
            continue

    # on の電球をカウント
    cnt_light = 0
    for m in range(M):
        cnt_swich = 0
        for s in S[m]:
            if swiches[s] == 1:
                cnt_swich += 1
        if cnt_swich%2 == P[m]:
            cnt_light += 1
    if cnt_light == M:
        ans += 1
print(ans)

Measured memory_bytes: 74164
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <set>
#include <utility>
using namespace std;

int main() {
  string s; cin >> s;
  for (int i = 0; i < s.length(); i++) {
    if ((i+1) % 2 == 1)
      cout << s[i];
  }
  cout << endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<set>
#include<queue>
#include<vector>
#include<cstdio>
#include<map>
#include<iomanip>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  if(b>=a)
    cout<<a;
  else
    cout<<a-1;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// // 整数の入力
		// int a = sc.nextInt();
		// // スペース区切りの整数の入力
		// int b = sc.nextInt();
		// int c = sc.nextInt();
		// // 文字列の入力
		// String s = sc.next();
		// // 出力
    // System.out.println((a+b+c) + " " + s);
    int N = sc.nextInt();
    System.out.println(N / 3);
	}
}

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

int main(){
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll ans = 0;
  ll r,g,b;
  r = count(s.begin(),s.end(),'R');
  g = count(s.begin(),s.end(),'G');
  b = count(s.begin(),s.end(),'B');
  ans = r*g*b;
  for(int i=0;i<n-2;i++){
    for(int j=i+1;j<n-1;j++){
      if( 2*j-i > n-1 ) continue;
      if( s.at(i) != s.at(j) && s.at(i) != s.at(2*j-i) && s.at(j) != s.at(2*j-i) ) ans--;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll fac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    ll n,m;cin >> n >>m;
    vl v(n);
    rep(i,n)cin >> v[i];
    sort(all(v));
    ll count=0;
    vector<pl> c(m);
    rep(i,m)cin >> c[i].se >> c[i].fi;
    sort(all(c));
    reverse(all(c));
    ll x=0;
    while(x<m&&count<n){
        if(v[count]<c[x].fi)v[count]=c[x].fi;
        else break;
        count++;
        c[x].se--;
        if(c[x].se==0)x++;
    }
    ll ans=0;
    rep(i,n)ans+=v[i];
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    string S, T;
    cin >> S >> T;
    int ret = 0;
    FOR(i, 0, 3)
        if (S[i] == T[i])
            ret++;
    cout << ret << endl;
    return 0;
};


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

int main()
{
    int N, M, K, A, ans = 0;
    cin >> N >> M;
    vector<int> ANS(M, 0);

    for (int i = 0; i < N; ++i)
    {
        cin >> K;
        for (int k = 0; k < K; ++k)
        {
            cin >> A;
            ANS[A - 1]++;
        }
    }
    for (int i = 0; i < M; ++i)
        if (ANS[i] == N)
            ans++;
    cout << ans << endl;
}

Measured memory_bytes: 256
class UnionFind():
    # https://qiita.com/hukuhuku11111a1/items/1bbf67d90630552eb512
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return

N, M = [int(_) for _ in input().split()]
ab = [[int(_) for _ in input().split()] for _ in range(M)]

result = 0

for a1, b1 in ab:
    uf = UnionFind(N + 1)
    for a, b in ab:
        if (a, b) == (a1, b1):
            continue
        uf.union(a, b)
    rs = set([])
    for i in range(1, N + 1):
        rs.add(uf.find(i))
    if len(rs) > 1:
        result += 1

print(result)
    



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll k;string s;cin>>k>>s;
  print((s.length()<=k)?s:(s.substr(0,k)+"..."));
  return 0;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    while(true){
        int n,s,ans=0;
        cin>>n>>s;
        if(n==0) break;
        rep(i,pow(2,10)){
            int x=0,y=0,p=i;
            rep(j,10){
                if(p%2) x++,y+=j;
                p=p/2;
            }
            if(x==n&&y==s) ans++;
        }
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 3100
#include <stdio.h>

int main(int argc, char const *argv[])
{
	int h, m, s;

	while (scanf("%d %d %d", &h, &m, &s), ~h){
		int v = (2 * 3600) - (h * 3600 + m * 60 + s);
		printf("%02d:%02d:%02d\n", v / 3600, v % 3600 / 60, v % 3600 % 60);
		v *= 3;
		printf("%02d:%02d:%02d\n", v / 3600, v % 3600 / 60, v % 3600 % 60);
	}
	return (0);
}

Measured memory_bytes: 612
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//clock_t start=clock();clock_t end=clock();cout<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
typedef pair<double,double> pdd;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll mod5=1000000009;
ll inf=1LL<<60;
double pi=3.141592653589793238462643383279L;
double eps=1e-9;
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
#define srep(itr,st) for(auto itr=st.begin();itr!=st.end();itr++)
#define mrep(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll popcount(ll n){
    ll ret=0;
    ll u=n;
    while(u>0){
        ret+=u%2;
        u/=2;
        
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    cout<<n*(n+1)/2<<endl;
    
}










Measured memory_bytes: 256
#include <cstdio>
 
int main(void)
{
    int X, Y;
    scanf("%d%d", &X, &Y);
 
    int b2 = Y - 2 * X;
    if(b2 < 0 || b2 % 2) 
        printf("No");
    else {
        int a = X - b2 / 2;
        if(a < 0) printf("No");
        else printf("Yes");
    }
}

Measured memory_bytes: 1736
#include <stdio.h>

int main(){
  int n, u, k, v, c, list[100][100], s[100], d[100], p[100];
  int i, j, min, min_v;

  for (i = 0; i < 100; i++) {
    d[i] = 999999;
    s[i] = -1;
    for (j = 0; j < 100; j++) {
      list[i][j] = 999999;
    }
  }

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d %d", &u, &k);
    for (j = 0; j < k; j++) {
      scanf("%d %d", &v, &c);
      list[u][v] = c;
    }
  }

  d[0] = 0;

  for (j = 0; j < n; j++){
    min = 1000000;
    for (i = 0; i < n; i++) {
      if (min > d[i] && s[i] != 1) {
        min = d[i];
        min_v = i;
      }
    }

    s[min_v] = 1;
    for (i = 0; i < n; i++) {
      if (d[min_v]+list[min_v][i]<d[i] && s[i]!=1){
        d[i] = d[min_v] + list[min_v][i];
        p[min_v] = i;
      }
    }
  }

  for (i = 0; i < n; i++) {
    printf("%d %d\n", i, d[i]);
  }

  return 0;
}



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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(A*N, B) << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize "trapv"
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1000000007;
#define pb push_back
#define fs first
#define sc second
#define forn(i,k,n) for(int i = k; i < n; ++i)
#define nfor(i,n,k) for(int i = n; i >= k; --i)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vvpii vector<vector<pait<int,int>>>
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define dbgarr(V,n) forn(i,0,n) cout << V[i] << " "; cout << endl;
#define dbgarrrev(V,n) nfor(i,n,0) cout << V[i] << " "; cout << endl;
#define dbgmaze(V) for(auto x: V) {for(auto y : x) cout << y <<  " ";cout << endl;}
#define dbg2d(V,n,m) forn(i,0,n) {forn(j,0,m) cout << V[i][j] <<  " ";cout << endl;}
#define N 100005
int H[N];
int dp[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin >> n;
	forn(i,0,n) cin >> H[i];
	dp[0] = 0; dp[1] = abs(H[1] - H[0]);
	dp[2] = min(abs(H[2] - H[0]), dp[1] + abs(H[2] - H[1]));
	forn(i,3,n) dp[i] = min(dp[i - 2] + abs(H[i] - H[i - 2]), dp[i - 1] + abs(H[i] - H[i - 1]));
	cout << dp[n - 1] << endl;
    return 0;
}


Measured memory_bytes: 4420
#include<stdio.h>
int main(void)
{
	int a, b, x;
	while(1){
		scanf("%d %d", &a, &b);
		if(a==0 && b==0){
			break;
		}
		if(a>b){
			x=a;
			a=b;
			b=x;
		}
		printf("%d %d\n", a,b);
	}
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
#include <deque>
#include <utility>
#include <cmath>
#include <limits>

using std::cout;
using std::cin;
using pair = std::pair<int, int>;	// height, shortest distance

void p_d(std::deque<pair> d){
	for (const pair &p : d){
		cout << "(" << p.first << ", " << p.second << ") "; 
	}
	cout << '\n';
	return;
}

int main(){
	int n, k, height, diff, minDiff;

	cin >> n;
  	k = 2;
	std::deque<pair> nums;
	cin >> height;
	nums.push_back(std::make_pair(height, 0));
	for (int i = 0; i < n - 1; ++i){
		cin >> height;
		
		minDiff = std::numeric_limits<int>::max();
		for (pair &p : nums){
			diff = p.second + std::abs(p.first - height);
			if (diff < minDiff) minDiff = diff;
		}
		//p_d(nums);
		nums.push_back(std::make_pair(height, minDiff));
		if (nums.size() == k + 1){
			nums.pop_front();
		}
	}
	cout << nums.at(nums.size() - 1).second << '\n';

	return 0;
}

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        char s = in.nc();
        if(s>='a'&&s<='z') out.println("a");
        else out.println("A");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32856
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include <numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

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

  sort(a.begin(), a.end());
  a[n] = k + a[0]; 
  int max_diff = 0;
  for(int i = 0; i < n; ++i){
  	max_diff = max(max_diff, a[i + 1] - a[i]);
  }
  cout << k - max_diff << endl;

  return 0;
}


Measured memory_bytes: 1024
s,a,b=[set(map(int,input().split()))for j in[0]*3];c=1;N=M=0;k=x=max(a)
while k:A=k in a;B=k in b;N+=A;M+=B;c*=[M*N-x+k,N,M,1][A*2+B];c%=10**9+7;k-=1
print(c)

Measured memory_bytes: 3188
#include <stdio.h>

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

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

  int n0 = N % 10;
  int n1 = ((N % 100) - n0) / 10;
  int n2 = ((N % 1000) - n1 - n0) / 100;

  if (7 == n0 || 7 == n1 || 7 == n2) {
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;
}


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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            while (true)
            {
                int n = int.Parse(Console.ReadLine());

                if (n == 0) break;

                int count = 0;

                while (n != 1)
                {
                    if (n % 2 == 0)
                    {
                        n /= 2;
                    }
                    else
                    {
                        n = n * 3 + 1;
                    }
                    count++;
                }
                sb.AppendLine(count.ToString());
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string S;
    cin >> S;
    if (S[0] != S[1] and S[1] != S[2] and S[0] != S[2]) {
        cout << "Yes" << endl;;
    }
    else {
        cout << "No" << endl;
    }
}

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


int bubbleSort(int A[],int N){
 int sw=0;
 bool flag=1;
 for(int i=0;flag;i++){
  flag=0;
  for(int j=N-1;j>=i+1;j--){
   if(A[j]<A[j-1]){
   swap(A[j],A[j-1]);
   flag=1;
   sw++;
   }
  }
 }
 return sw;
 }
 
 int main(){
 int A[100],N,sw;
 cin >>N;
 for(int i=0;i<N;i++) cin>>A[i];
 
 sw=bubbleSort(A,N);
 
 for(int i=0;i<N;i++){
  if(i)cout<<" ";
  cout<<A[i];
 }
 cout<<endl;
 cout<<sw<<endl;
 
 return 0;
}

Measured memory_bytes: 3108