akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
 
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);
 
ll rec(int n, ll x) {
	if (n == 0) {
		return 1;
	}
	
	ll len = (1LL << (n + 1)) - 3;
	ll num = (1LL << n) - 1;
 
	if (x == 1) {
		return 0;
	}
	else if (x <= len + 1) {
		return rec(n - 1, x - 1);
	}
	else if (x <= len + 2) {
		return num + 1;
	}
	else if(x <= (len + 1) * 2) {
		return num + 1 + rec(n - 1, x - len - 2);
	}
	else {
		return num * 2 + 1;
	}
}
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/
 
	int n;
    ll x;
	cin >> n >> x;
 
	out(rec(n, x));
 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define db(a) cout << a << endl
#define db2(a,b) cout << a << " " << b << endl
#define dbd(a) cout << #a << ": " << a << endl
#define dbd2(a,b) cout << #a << ": " << a << ", " << #b << ": " << b << endl 
#define dbp(a) cout << a.first << " " << a.second << endl
#define adb(a) for(auto _i:a) cout << _i << " "; cout << endl
#define adbp(a) for(auto _i:a) cout << _i.first << " " << _i.second << endl;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define mod 998244353
#define N 1000010
#define M 100010
using namespace std;

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

    long long a[n], i;
    map<long long, long long> mp;
    for(i=0;i<n;i++)
    {
        cin >> a[i];
        mp[a[i]]++;
    } 

    sort(a, a+n);
    long long ans = 0;
    bool chk[N] = {false};
    for(i=0;i<n;i++)
    {
        if(!chk[a[i]] && mp[a[i]] == 1) ans++;
        if(a[i] == 1) break;
        if(!chk[a[i]]) for(int j=a[i]; j<N; j+=a[i]) chk[j] = true;
    }

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

Measured memory_bytes: 18656
#include <bits/stdc++.h> 
#include <vector>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector <int> h(n),dp(n,INT_MAX);
	for(int i=0;i<n;i++) 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]));
	for(int i=3;i<n;i++){
		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];
	return 0;
}

Measured memory_bytes: 1024
var inputs = require('fs').readFileSync('/dev/stdin', 'utf8').split(" ");

a = ~~inputs[0];
b = ~~inputs[1];

if (a<b) {
    rel = "<";
} else if (a>b) {
    rel = ">";
} else {
    rel = "==";
}

console.log(`a ${rel} b`);



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

int a[300100];

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i < 3*n; i++)
		scanf("%d", a+i);
	sort(a, a + 3*n, greater<int>());
	long ans = 0;
	for(int i = 0; i < 2*n; i++)
		if(i % 2) ans += a[i];
	printf("%ld\n", ans);
}


Measured memory_bytes: 1408
from sys import stdin
import bisect

N = int(input())
L = list(map(int,stdin.readline().strip().split()))

L.sort()

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        idx = bisect.bisect_left(L,L[i]+L[j],j)
        ans += (idx-j-1)

print(ans)    


Measured memory_bytes: 3188
package main

import (
	"fmt"
)

func main() {
	var n int
	var m int
	fmt.Scan(&n)
	fmt.Scan(&m)
	var arr [50]int
	for i:=0;i < n; i++ {
		var x int
		fmt.Scan(&x)
		for j:=0; j < x; j++{
			var y int;
			fmt.Scan(&y);
			y--;
			arr[y]++;
		}
		
	}
	ans := 0;
	for i:=0; i<m;i++ {
		if arr[i] == n {
			ans++;
		}
	}
	fmt.Println(ans);

}


Measured memory_bytes: 1808
'use strict'
function otoshidama(stdin) {
  const inputs = stdin.split(' ')
  const n = inputs[0]
  const y = inputs[1]
  for (let i = 0;i <= n;i++) {
    const remain = y - 10000 * i
    if (remain === 0 && n === i) return console.log(n, 0, 0)
    for (let j = 0;j <= n - i;j++) {
      const sen = n - i - j
      const result = remain - 5000 * j - 1000 * sen
      if (result === 0) return console.log(i, j, sen)
    }
  }
  return console.log(-1, -1, -1)
}
otoshidama(require('fs').readFileSync(0, 'utf8'))

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

int n, m, k;

bool solve() {
    for(int row = 0; row <= n; ++row)
	for(int col = 0; col <= m; ++col)
	    if(row * m + col * n - 2 * row * col == k)
		return true;

    return false;
}

int main() {
    scanf("%d %d %d", &n, &m, &k);

    if(solve())
	printf("Yes\n");
    else
	printf("No\n");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K, x;
  int total = 0;
  
  cin >> N >> K;
  
  for (int i = 0; i < N; i++) {
    cin >> x;
    if (x < K - x)
      total += x;
    else
      total += K - x;
  }
  
  cout << total * 2 << endl;
}

Measured memory_bytes: 256
N,M = map(int,input().split(" "))
H = input().split(" ")
for i in range(N):
  H[i]=[int(H[i]),1]
for j in range(M):
  A,B = map(int,input().split(" "))
  if H[A-1][0]>H[B-1][0]:
    H[B-1][1]=0
  elif H[A-1][0]<H[B-1][0]:
    H[A-1][1]=0
  elif H[A-1][0]==H[B-1][0]:
    H[A-1][1]=0
    H[B-1][1]=0
compte=0
for k in range(N):
  if H[k][1]==1:
    compte+=1
print(compte)

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

                            #define FOR(i,a,b) for(int i = (a); i < (b); i++)
                            #define rep(i,n) FOR(i,0,n)
                            #define RFOR(i,b,a) for(int i = (b) - 1; i>= (a); i--)
                            #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 SZ(a) (int)a.size()
                            #define ALL(a) a.begin(), a.end()
                            #define PB push_back
                            #define MP make_pair
                            #define er erase
                            #define in insert
                            #define f first
//                            #define s second



                            typedef  long long LL;
                            typedef vector<int> VI;
                            typedef vector<LL > VL;
                            typedef vector<vector<int > > VVI;
                            typedef vector<vector<LL>> VVL;
                            typedef vector <vector<pair<int, int >> >VVPI;
                            typedef vector<vector<pair<LL, LL >> >VVPL;
                            typedef vector<pair<LL, LL >> PL;
                            typedef vector<PL> VPL;
                            typedef pair<int, int> PII;
                            typedef vector<PII> VPI;

                            const double PI = acos(-1.0);
                            const int INF = 1e9;
                            const LL LINF = (LL)1e18;

                            const double EPS = 1e-7;
                            const int MAS =  3 *1e5 + 10;
                            const int mod = 998244353;
                            const int MOD =1e9+7;
                            const int LOG= 19;
                            const int ar = 1e5 +100;
                            const int MAX = 1e6 + 1e2;
                            LL dp[3005][3005];
                        int main() {
                            ios_base::sync_with_stdio(false);
                            cin.tie(NULL);
                            int n;
                            cin >> n;
                            VI a(n);
                            rep(i,n)cin >> a[i];
                            RFOR(l,n,0)
                            FOR(r,l,n)
                            {
                                if(l == r)dp[l][r] = a[l];
                                else dp[l][r] = max(a[l] - dp[l + 1][r],a[r] - dp[l][r-1]);
                            }
                            cout << dp[0][n-1];


                        }

















































Measured memory_bytes: 70016
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,a,b;
	cin>>n>>a>>b;
	long long x1,x2;
	cin>>x1>>x2;
	long long ans=0;
	for(int i=3;i<=n;i++)
	{
		ans+=min((x2-x1)*a,b);
		x1=x2;
		cin>>x2;
	}
	ans+=min((x2-x1)*a,b);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<stack>
#include<queue>
#include<string>
#include<iostream>
#include<tuple>
#include<utility>
#include<set>
#include<queue>
#include<iomanip>
#include<iterator>
//#include<chrono>
//cout<<setprecision(12)
//fixed
//#include<random>
using namespace std;
typedef long long int llint;
typedef long double lldo;
const llint big=1e15+100000;
const int mod=1e9+7;
const lldo eps=1e-9;
const long double pai=3.141592653589793238462643;
#define mt make_tuple
#define mp make_pair
#define fir first
#define sec second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define res resize
#define ins insert
#define era erase
#define dme(in) cout<<in<<endl;return 0
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
int main(void){
	int i,n,d,j=0;cin>>n>>d;
	llint ans=0;
	vector<tuple<llint,llint,llint>> a(n);
	for(i=0;i<n;i++){cin>>get<1>(a[i])>>get<2>(a[i])>>get<0>(a[i]);}
	sort(a.begin(),a.end());
	multiset<llint>x;
	multiset<llint>y;
	for(i=0;i<n;i++){
		x.ins(get<1>(a[i]));
		y.ins(get<2>(a[i]));
		for(;j<n;j++){
			if(get<0>(a[j])>=get<0>(a[i])-d){break;}
			x.era(x.lower_bound(get<1>(a[j])));
			y.era(y.lower_bound(get<2>(a[j])));
		}
		maxeq(ans,((*prev(x.end()))-(*x.begin()))*((*prev(y.end()))-(*y.begin())));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 26196
#include<bits/stdc++.h>
            #define ll long long
            #define f   first
            #define s   second
            #define pb          push_back
            #define mod        1000000007
            #define mod1       1000000009
            #define hell        998244353
            #define inf         1000000000000000000LL
            #define pi          3.14159265358979323
            //#define N           100005 
            const int N=1000005;
            using namespace std;
            ll n,k,sum,q,res,m,val,ans;
            ll x,y;
            double p;
            ll xx[]={1,0,-1,0};
            ll yy[]={0,1,0,-1};
            void solve()    
            {   ll a,b,c;
                cin>>n;
                vector<ll> v(n);
                for(int i=0;i<n;i++) cin>>v[i];
                ll suf[n];
                suf[n-1]=v[n-1];
                for(int i=n-2;i>=0;i--) suf[i]=(suf[i+1]+v[i])%mod;
                ll ans=0;
                for(int i=0;i<n-1;i++)
                {
                    ll res=(v[i]*suf[i+1])%mod;
                    ans+=res;
                    ans%=mod;
                }
                cout<<ans;

                
                
            }
            int main()  
            {   ios_base::sync_with_stdio(false);
                cin.tie(0);cout.tie(0);
                ll t=1;
                
                //cin>>t;
                 for(ll i=1;i<=t;i++)
                    solve();
                
            }            


Measured memory_bytes: 6360
N = int(input())
ans = []
char = ["a"]


def dfs(idx, c):
    if idx == N:
        ans.append("".join(char))
    else:
        for i in range(c+2):
            nc = chr(ord("a")+i)
            char.append(nc)
            dfs(idx+1, max(i, c))
            char.pop()

dfs(1, 0)
for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 61092
import java.util.*;
import java.lang.*;
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();
		for( int i=0; i<1; i++ ){
			if( A==B && B!=C ){
				System.out.println("Yes");
				break;
			}
			if( A!=B && B==C ){
				System.out.println("Yes");
				break;
			}
			if( A==C && B!=C ){
				System.out.println("Yes");
				break;
			}
			if( i==0 ){
				System.out.println("No");
			}
		}
	}
}

Measured memory_bytes: 22228
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace().map(|s| s.parse().unwrap());
    let (n, m): (usize, usize) = (iter.next().unwrap(), iter.next().unwrap());
    
    let mut cities: Vec<i32> = vec![0; n];

    for _ in 0..m {
        let mut buf2 = String::new();
        std::io::stdin().read_line(&mut buf2).unwrap();
        let mut iter2 = buf2.split_whitespace().map(|s| s.parse().unwrap());
        let (a, b): (usize, usize) = (iter2.next().unwrap(), iter2.next().unwrap());
        cities[a - 1] += 1;
        cities[b - 1] += 1;
    }

    for i in cities.iter() {
        println!("{}", i);
    }
}


Measured memory_bytes: 4352
#define _CRT_SECURE_NO_WARNINGS

#pragma comment(linker, "/STACK:250000000")

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <complex>
#include <functional>
#include <numeric>
#include <random>
#include <cstring>
#include <ctime>
#include <cassert>

#define y1 klfjvkldfngldf

using namespace std;

typedef long long LL;

const int MOD = (int)1e9 + 7;

vector<pair<int, int> > C[300];
int dp[301][301][301];

bool check(int r, int g, int b)
{
	int p = min(r, g);
	p = min(p, b);
	for (auto &c : C[p])
	{
		int cnt =	(p <= r && r < c.first) + 
					(p <= g && g < c.first) + 
					(p <= b && b < c.first);
		if (cnt != c.second)
			return 0;
	}
	return 1;
}

void add(int & x, int y)
{
	x += y;
	if (x >= MOD)
		x -= MOD;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int L, R, x;
		cin >> L >> R >> x;
		L--;
		C[L].push_back({ R, x });
	}

	dp[n][n][n] = 1;
	for (int r = n; r >= 1; --r)
	{
		for (int g = n; g >= 1; --g)
		{
			for (int b = n; b >= 1; --b)
			{
				int p = min(r, g);
				p = min(p, b);

				if (check(p - 1, g, b))
					add(dp[p - 1][g][b], dp[r][g][b]);
				if (check(r, p - 1, b))
					add(dp[r][p - 1][b], dp[r][g][b]);
				if (check(r, g, p - 1))
					add(dp[r][g][p - 1], dp[r][g][b]);
			}
		}
	}

	int res = 0;
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j <= n; ++j)
		{
			add(res, dp[0][i][j]);
			add(res, dp[i][0][j]);
			add(res, dp[i][j][0]);
		}
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 106752
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from collections import defaultdict

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    d1 = defaultdict(int)
    sum1 = 0
    for i in range(N):
        v = next(it)
        sum1 += v
        d1[v] += 1

    Q = next(it)
    ans = []
    for bi, ci in zip(it, it):
        cnt = d1[bi]
        sum1 += (ci-bi)*cnt
        d1[bi] = 0
        d1[ci] += cnt
        ans.append(sum1)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 101936
#include <bits/stdc++.h>
using namespace std;
#define maxn 2010
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
#define fi first
#define pi pair<int, int>
#define se second
#define mp make_pair
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
int n, m;
vi eg[maxn];
int dep[maxn];
int u[maxn], v[maxn], fa[maxn];
deque<int> tr[maxn];
int cnt[maxn];
int bg[maxn];
void dfs(int a) {
	for (auto v : eg[a]) {
		if (v == fa[a]) continue;
		dep[v] = dep[a] + 1, fa[v] = a;
		dfs(v);
	}
}
deque<int> gt(int a, int b) {
	deque<int> r, e;
	while (a != b) {
		if (dep[a] >= dep[b])
			r.pb(a), a = fa[a];
		else e.pb(-b), b = fa[b];
	}
	for (auto x : e)
		r.pb(x);
	return r;
}
vi ss[maxn];
int tp[maxn];
int pre[maxn];
int gp(int a) {
	if (pre[a] == a) return a;
	int nf = gp(pre[a]);
	tp[a] ^= tp[pre[a]], pre[a] = nf;
	return nf;
}
int fl[maxn];
int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		eg[u].pb(v), eg[v].pb(u);
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u[i], &v[i]), 
		tr[i] = gt(u[i], v[i]);
		for (auto s : tr[i]) {
			cnt[abs(s)]++;
			if (s < 0) ss[-s].pb(-i);
			else ss[s].pb(i);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += min(cnt[i], 2);
	cout << ans << endl;
	for (int i = 1; i <= m; i++)
		pre[i] = i;
	for (int i = 2; i <= n; i++) {
		if (ss[i].size() < 2) continue;
		memset(fl, 0, sizeof(fl));
		int nf = 0;
		for (auto v : ss[i]) {
			int ng = gp(abs(v));
			int ut = tp[abs(v)] ^ (v < 0);
			ut++;
			if (fl[ng] && fl[ng] != ut) nf = 1;
			fl[ng] = ut;
		}
		if (nf) continue;
		else {
			l1:int x1 = rand() % ss[i].size(), x2 = rand() % ss[i].size();
			if (x1 == x2) goto l1;
			int tt = ss[i][x1], mm = ss[i][x2];
			int nr = (tt < 0) ^ (mm < 0) ^ 1;
			tt = abs(tt), mm = abs(mm);
			int ufa = gp(tt), vfa = gp(mm);
			pre[ufa] = vfa, 
			tp[ufa] = tp[tt] ^ tp[mm] ^ nr;
		}
	}
	for (int i = 1; i <= m; i++) {
		gp(i);
		if (tp[i] == 1) swap(u[i], v[i]);
		printf("%d %d\n", u[i], v[i]);
	}

 	return 0;
}


Measured memory_bytes: 12800
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 


def flatten():
    MOD = 10**9+7
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    najwieksza = max(A)
    najmniejszy_dzielnik = [None] * (najwieksza + 1)
    for i in reversed(range(2, najwieksza + 1)):
        for j in range(0, najwieksza + 1, i):
            najmniejszy_dzielnik[j] = i
    najwieksze_wykladniki = [0] * (najwieksza + 1)
    for liczba in A:
        dzielnik = 1
        wykladnik = 0
        while liczba != 1:
            d = najmniejszy_dzielnik[liczba]
            if d == dzielnik:
                wykladnik += 1
            else:
                if najwieksze_wykladniki[dzielnik] < wykladnik:
                    najwieksze_wykladniki[dzielnik] = wykladnik
                dzielnik = d
                wykladnik = 1
                
            liczba //= d
            
        if najwieksze_wykladniki[dzielnik] < wykladnik:
            najwieksze_wykladniki[dzielnik] = wykladnik
    
    nww = 1
    for dzielnik, wykladnik in enumerate(najwieksze_wykladniki):
        nww = nww * pow(dzielnik, wykladnik, MOD) % MOD
    
    suma = 0
    for liczba in A:
        suma += nww * pow(liczba, MOD - 2, MOD)
        suma %= MOD
    print(suma)
        

flatten()

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

int w[100];
int main() {
	int m, n;
	while (scanf("%d%d", &m, &n), m) {
		int ans = 0;
		rep(i, n) {
			scanf("%d", &w[i]);
			ans = max(ans, w[i]);
		}
		for (;; ans++) {
			int j = 0, k = 0;
			bool flag = true;
			rep(i, n) {
				j += w[i];
				if (j > ans) {
					k++; j = w[i];
					if (k >= m) {
						flag = false;
						break;
					}
				}
			}
			if (flag) {
				printf("%d\n", ans);
				break;
			}
		}
	}
}

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

#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

int ctoi(char c) { return int(c - '0'); }

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

    string str;
    int k;
    cin >> str >> k;

    int n = str.size();
    vector<vll> dp0(n + 1, vll(k + 2, 0)), dp1(n + 1, vll(k + 2, 0));
    dp0[0][0] = 1;

    rep(i, 0, n) {
        rep(j, 0, k + 1) {
            if (str[i] == '0') {
                dp0[i + 1][j] += dp0[i][j];
                dp1[i + 1][j] += dp1[i][j];
                dp1[i + 1][j + 1] += 9 * dp1[i][j];
            } else {
                dp0[i + 1][j + 1] += dp0[i][j];
                dp1[i + 1][j] += dp0[i][j];
                dp1[i + 1][j + 1] += (ctoi(str[i]) - 1) * dp0[i][j];
                dp1[i + 1][j] += dp1[i][j];
                dp1[i + 1][j + 1] += 9 * dp1[i][j];
            }
        }
    }

    cout << dp0[n][k] + dp1[n][k] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
using namespace std;
//cout <<  << endl;
typedef long long int ll;
typedef double ld;

vector<pair<ll,ll>> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}

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

#define MAX_N 100010
bool x[MAX_N];
ll num[MAX_N];

ll fibl[MAX_N]={0};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}

ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    
    return p;
}

ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}

int main(){
    string s;
    cin >> s;
    for (ll i=1;i<=s.size();i++){
        if (i%2==0){
            if (s[i-1]=='L' || s[i-1]=='U' || s[i-1]=='D'){
                continue;
            }
        }else{
            if (s[i-1]== 'R'|| s[i-1]=='U' || s[i-1]=='D'){
                continue;
            }
        }
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdio.h>
#define test ll t; cin>>t; while(t--)
#define FOR(p,n) for(ll i=p;i<(ll)n;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define MAX 1000005
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define endl '\n'
#define vs vector<string>
#define mii map<int,int>
#define msi map<string,int>
#define vpii vector< pair<int, int > >
#define vpsi vector< pair< string ,int > >
#define forci(p,q) for(int i=p;i<q;i++)
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b) {a %= mod;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % mod;  a = a * a % mod;  b >>= 1; }  return res%mod; }
ll modmul(ll x, ll y){return (x*y)%mod;}
ll modadd(ll x, ll y){return (x+y)%mod;}
ll modsub(ll x, ll y){return (x-y+mod)%mod;}
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[r],mod-2)))%mod; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
inline long long toint(const std::string &s) {std::stringstream ss; ss << s; long long x; ss >> x; return x;}
inline std::string tostring(long long number) {std::stringstream ss; ss << number; return ss.str();}
inline std::string tobin(long long x) {return std::bitset<63>(x).to_string();}
/*bool prime[MAX];
ull sieve(){memset(prime,true,sizeof(prime));for(ull p=2;p*p<MAX;p++){if(prime[p]==true){for(ull i=2*p;i<MAX;i+=p){prime[i]=false;}}}prime[0]=0;prime[1]=0;
}
int inv[1000001]={0};
void findinverse(){inv[1] = 1;for(int i = 2; i <=1e6 ; ++i)	inv[i] = (mod - (mod/i) * inv[mod%i] % mod) % mod;}
*/
using namespace std;
int solve()
{
	int a,b;
	cin>>a>>b;
	cout<<a*b<<endl;	
	return 0;
}
signed main()
{
	fastio;
//	test
	{
		solve();
	}
}




Measured memory_bytes: 3640
#include<bits/stdc++.h>
//g++ -std=c++11 

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7

int main(){
	ll A, B;
	cin >> A >> B;
	if(A == B) {
		cout << 0 << endl;
	} else {
		if((A+B)%2 == 1) {
			cout << "IMPOSSIBLE" << endl;
		} else {
			cout << (A+B)/2 << endl;
		}
	}
}



Measured memory_bytes: 3596
#include <stdio.h>
#define N 100000
#define NIL -1

struct Node{
  int parent;
  int left;
  int right;
};
struct Node T[25];
int C[25];
int H[25];

void getDepth(int, int);
int getHeight(int);

int main()
{
  int n, i, j, k, x, y, id, left, right, root;


  scanf("%d",&n);
  for( i=0 ; i<n ; i++ ){
    T[i].parent = NIL;
  }
  for( i=0 ; i<n ; i++ ){
    scanf("%d %d %d",&id,&left,&right);
    T[id].left = left;
    T[id].right = right;

    T[left].parent = id;

    T[right].parent = id;
  }

  for( i=0 ; i<n ; i++ )
    if(T[i].parent==NIL) root = i;

  getDepth(root,0);
  getHeight(root);

  for( i=0 ; i<n ; i++ ){
    printf("node %d: parent = %d, sibling = ",i,T[i].parent);
    
    j=i;
    while(1){
      if(T[i].parent==NIL) {
	printf("%d",T[i].parent);
	break;
      }
      if(T[T[i].parent].left==j) {
	printf("%d",T[T[i].parent].right);
	break;
      }
      if(T[T[i].parent].right==j){
	printf("%d",T[T[i].parent].left);
	break;
      }
      j++;
    }
        
    printf(", degree = ");
    if(T[i].left==NIL && T[i].right==NIL) printf("0");
    else if(T[i].left==NIL && T[i].right!=NIL)printf("1");
    else if(T[i].left!=NIL && T[i].right==NIL)printf("1");
    else printf("2");

    printf(", depth = %d,",C[i]);

    printf(" height = %d,",H[i]);
    
    if(T[i].parent==NIL)
      printf(" root\n");
    else if(T[i].left==NIL && T[i].right==NIL)
      printf(" leaf\n");
    else
      printf(" internal node\n");
  }

  return 0;
}
void getDepth(int r, int d)
{
  if(r==NIL) return;
  C[r] = d;


  getDepth(T[r].right,d+1);

  getDepth(T[r].left,d+1);
}

int getHeight(int r)
{
  int x=0, y=0;

  if(T[r].right!=NIL)
    x = getHeight(T[r].right)+1;
  if(T[r].left!=NIL)
    y = getHeight(T[r].left)+1;
  if(x>y) H[r] = x;
  else H[r] = y;
  return H[r];
}

Measured memory_bytes: 616
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const ll INF = 1e9;
inline ll read(){
	ll X = 0,w = 0 ;
	char ch = 0;
	while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
	return w ? -X : X;
}
const ll mod=1e9+7;
void add(ll &a,ll b)
{
	a+=b;
	a%=mod;
}
ll P[205];
ll dp[10005][205];
int main()
{
	ll n,k;
	cin>>n>>k;
	P[0]=1;
	for(ll i=0;i<=n;i++)
	{
		P[i+1]=P[i]*(k+1)%mod;
	}
	ll ans=0;
	dp[0][n]=1;
	for(ll i=n-1;i>=0;i--)
	{
		for(ll y=0;y<=n*n;y++)
		{
			if(!dp[y][i+1])
			{
				continue;
			}
			for(ll x=0;x<=k;x++)
			{
				if(x<=i+1 and i-x+1<=y)
				{
					ll p=(x+y)/(i+1);
					add(ans,P[i]*p%mod*dp[y][i+1]%mod);
					add(dp[y+p][i],dp[y][i+1]);
				}
				else
				{
					add(dp[y][i],dp[y][i+1]);
				}
			}
		}
	}
	cout<<(k*(k+1)/2*P[n-1]%mod*n%mod+mod-ans)%mod;
	return 0;
}

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

int main(){
  int k; cin >> k;
  ll res = 0;
  for(int i=1; i<=k; ++i){
    for(int j=1; j<=k; ++j){
      for(int l=1; l<=k; ++l){
        res += gcd(gcd(i, j), l);
      }
    }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3632
import sys
input = sys.stdin.readline

def main():
    X, Y, A, B, C = map( int, input().split())
    P = list( map( int, input().split()))
    Q = list( map( int, input().split()))
    R = list( map( int, input().split()))
    P.sort( reverse = True)
    Q.sort( reverse = True)
    R.sort( reverse = True)
    ANS = P[:X] + Q[:Y]
    ANS.sort()
    for i in range( min(X+Y, C)):
        if ANS[i] < R[i]:
            ANS[i] = R[i]
        else:
            break
    print( sum(ANS))
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 93804
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

class Dis{
  public:
  vector<ll> rank,p;
  
  Dis(int s){
    rank.resize(s,0);
    p.resize(s,0);
    rep(i,s) makeSet(i);
  }
  
  void makeSet(int x){
    p[x]=x;
    rank[x]=0;
  }
  
  bool same(int x,int y){
    return findSet(x)==findSet(y);
  }
  
  void unite(int x,int y){
    link(findSet(x),findSet(y));
  }
  
  void link(int x,int y){
    if(rank[x]>rank[y]) p[y]=x;
    else{
      p[x]=y;
      if(rank[x]==rank[y]) rank[y]++;
    }
  }
  
  int findSet(int x){
    if(x != p[x]) p[x]=findSet(p[x]);
    return p[x];
  }
};
  
class Edge{
  public: int source,target,cost;
  Edge(int source=0, int target=0, int cost=0):
  source(source),target(target),cost(cost){}
  bool operator < (const Edge &e) const{
    return cost<e.cost;
  }
};
  
int kruskal(int N,vector<Edge> edges){
  int totalCost=0;
  sort(ALL(edges));
  
  Dis dset=Dis(N+1);
  
  int source,target;
  rep(i,edges.size()){
    Edge e=edges[i];
    if(!dset.same(e.source,e.target)){
      totalCost+=e.cost;
      dset.unite(e.source,e.target);
    }
  }
  return totalCost;
} 

int main() {
  int N,M,cost;
  int source,target;
  cin>>N>>M;
  
  vector<Edge> edges;
  rep(i,M){
    cin>>source>>target>>cost;
    edges.push_back(Edge(source,target,cost));
  }
  
  cout<<kruskal(N,edges)<<endl;
  
  return 0;
}


Measured memory_bytes: 5428
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
        if (A*B*C%2==0){
            System.out.println(0);
        } else {
            System.out.println(Math.min(A*B, Math.min(B*C,A*C)));
        }
    }
}

Measured memory_bytes: 9544
import java.util.Scanner;

class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    int remainder = N % 2;
    int quotient = N / 2;

    if (remainder == 0) {
      System.out.println("0.5000000000");
    } else {
      double probability = (quotient + 1.0) / N;
      System.out.println(probability);
    }
  }
}


Measured memory_bytes: 21844
n=int(input())
A=list(map(int,input().split()))
c=0
for i in range(0,n):
    minj=i
    for j in range(i,n):
        if A[j]<A[minj]:
            minj=j
    if i != minj:
        c+=1
    A[i],A[minj]=A[minj],A[i]
print(" ".join(map(str,A)))
print(c)


Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std;
#define MAX 500
#define INF (1<<26)
typedef pair<int,int> P;
typedef pair<int,P> PP;
struct edge{int to,cost;};
vector<edge> G[MAX];
vector<int> K;
int d[MAX];
int D[MAX][MAX];
int J[MAX],E[MAX];
int n,m,l,s,t;

void dijkstra(int si){
  fill(d,d+MAX,INF);
  d[K[si]]=0;
  priority_queue< P,vector<P>,greater<P> > Q;
  Q.push(P(0,K[si]));
  while(!Q.empty()){
    P p=Q.top();Q.pop();
    int cost=p.first,pos=p.second;
    if(cost>d[pos])continue;
    for(int i=0;i<(int)G[pos].size();i++){
      edge e=G[pos][i];
      if(cost+e.cost<d[e.to]){
        d[e.to]=cost+e.cost;
        Q.push(P(d[e.to],e.to));
      }
    }
  }
  for(int i=0;i<=l;i++)
    D[si][i]=d[K[i]];
}

int dist[17][(1<<16)];
int solve(){
  int ans=0;
  fill(dist[0],dist[17],INF);
  priority_queue< PP,vector<PP>,greater<PP> > Q;
  Q.push(PP(0,P(l,0)));
  dist[l][0]=0;
  while(!Q.empty()){
    PP pp=Q.top();Q.pop();
    P p=pp.second;
    int cost=pp.first,pos=p.first,bit=p.second;
    if(cost<=t&&pos==l)
      ans=max(ans, __builtin_popcount(bit));
    for(int i=0;i<=l;i++){
      int nbit=bit;
      int ncost=cost+D[pos][i];
      if(i<l)nbit|=(1<<i),ncost+=E[i];
      if(ncost<dist[i][nbit]){
        dist[i][nbit]=ncost;
        Q.push(PP(ncost,P(i,nbit))); 
      }
    }
  }
  return ans;
}

void init(){
  K.clear();
  for(int i=0;i<MAX;i++)G[i].clear();
}

int main(){
  int a,b,c;
  while(1){
    cin>>n>>m>>l>>s>>t;
    if(n==0&&m==0&&l==0&&s==0&&t==0)break;
    s--;
    init();
    for(int i=0;i<m;i++){
      scanf("%d %d %d",&a,&b,&c);
      a--,b--;
      G[a].push_back((edge){b,c});
      G[b].push_back((edge){a,c});
    }
    for(int i=0;i<l;i++){
      scanf("%d %d",&J[i],&E[i]);
      J[i]--;
      K.push_back(J[i]);
    }
    K.push_back(s);
    for(int i=0;i<=l;i++)dijkstra(i);
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 17628
#include <iostream>
#include <string>
#include <stdlib.h>
#include <cstdlib>
using namespace std;


int main(){
	long long X;	// now
	long long K;	// times
	long long D;	// distance
	long long min_x = 0;
	cin >> X >> K >> D;
	
	long long times = abs(X)/ D;
	if(times > 0){
		if(times <= K){
		} else {
			times = K;
		}
		K -= times;
		if(X >= 0){
			X = X - times * D;
		} else {
			X = X + times * D;
		}
	}
	if((K % 2)==0){
		min_x = X;
	} else {
		if(X >= 0){
			min_x = X - D;
		} else {
			min_x = X + D;
		}
	}
	
	cout << abs(min_x);
	return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
 
const int N=100010;
struct node{
	int a,b;
	bool operator<(const node q)const{
		return a>q.a;
	}
}s[N];
int n;
long long sum=0;
 
long long gcd(long long x,long long y){
	if(y==0) return x;
	return gcd(y,x%y);
}
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		sum+=x;
		s[i].a=max(x,y);s[i].b=y;
	}
	sort(s+1,s+1+n);
	long long as=0;
	int k=0;
	while(1){
		k++;
		as+=s[k].a;
		if(as>=sum) break;
	}
	long long ansx=1,ansy=1;
	for(int i=1;i<=n;i++){
		long long now=sum-(as-s[min(i,k)].a);
		if(now<=s[i].b && now*ansy<1ll*s[i].b*ansx) ansx=now,ansy=s[i].b;
	}
	ansx=ansy-ansx+(n-k)*ansy;
	ansy*=n;
	printf("%lld %lld",ansx/gcd(ansx,ansy),ansy/gcd(ansx,ansy));
}

Measured memory_bytes: 1024
s=int(input())
a=(s-s%1000)+(s%1000-s%100)
b=s%100
if 100<=a<=1200 and 1<=b<=12:
  print('AMBIGUOUS')
elif 100<=a<=1200 and b>12:
  print('MMYY')
elif a>1200 and 1<=b<=12:
  print('YYMM')
elif a==100 and b==0:
  print('MMYY')
elif a==0 and b==1:
  print('YYMM')
else:
  print('NA')

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

int main(){
    ll N;
    cin >> N;
    double v[N];
    rep(i,N) cin >> v[i];
    sort(v,v+N);

    double r = 0.0;
    for(ll i=1;i<N;i++){
        r = (v[i-1] + v[i])/2.0;
        v[i] = r;
    }
    cout << r << endl;
    return 0;
}

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

using namespace std;
using i64 = long long int;
using ui64 = unsigned long long int;
using vi = vector<int>;
using vvi = vector<vi>;

////////////////////////////////

vvi mul(vvi a, vvi b, int m){
    assert(a[0].size() == b.size());
    vvi c(a.size(), vi(b[0].size()));
    for(int i=0;i<(int)a.size();i++){
        for(int j=0;j<(int)b[0].size();j++){
            for(int k=0;k<(int)b.size();k++){
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= m;
            }
        }
    }
    return c;
}

void E(vvi &a){
    a.assign(a.size(), vi(a[0].size(), 0));
    for(int i=0;i<(int)a.size();i++)a[i][i] = 1;
}

vvi rp(const vvi &a, int n, const int &m){
    vvi r(a.size(), vi(a.size()));
    if(!n){
        E(r);
        return r;
    }
    r = rp(a, n >> 1, m);
    r = mul(r, r, m);
    if(n&1){
        return mul(a, r, m);
    }
    return r;
}

int main(){
    int n, m, a, b, c, t;
    while(cin >> n >> m >> a >> b >> c >> t, n|m|a|b|c|t){
        vvi d(n, vi(n, 0));
        for(int i=1;i<n-1;i++){
            d[i][i-1] = a;
            d[i][i] = b;
            d[i][i+1] = c;
        }
        d[0][0] = b;d[0][1] = c;d[n-1][n-2] = a;d[n-1][n-1] = b;
        
        vi e(n);
        for(auto&& x:e)cin >> x;
        vvi A = rp(d, t, m);
        
        vi ret(n, 0);
        for(int i=0; i<n; i++)
            for(int j=0;j<n;j++){
                ret[i] += A[i][j] * e[j];
                ret[i] %= m;
            }
        for(int i=0;i<n;i++)cout << ret[i] << (i==n-1 ? "\n" : " ");
    }
}


Measured memory_bytes: 3380
#include <iostream>
#include <string>
#include <typeinfo>
#include <sstream>
using namespace std;
int main()
{
    int n;
	cin>>n;
	string a,b;
	while(n--){
		int s,keta=0;
		cin>>a>>b;
		int ai[85]={},bi[85]={},sum[85]={};
		int as,bs;
		char c;
		as=a.size();
		bs=b.size();
		if(as>80||bs>80){
			cout<<"overflow"<<endl;
		}else{
			for(int i=0;i<as;i++){c=a[as-i-1];ai[i]=c-'0';}
			for(int i=0;i<bs;i++){c=b[bs-i-1];bi[i]=c-'0';}
			for(int i=0;i<=max(as,bs);i++){
				s=ai[i]+bi[i]+sum[i];
				if(s)keta=i;
				if(s>9){
					sum[i]=s%10;
					sum[i+1]++;
				}else{
					sum[i]=s;
				}
			}
			if(sum[80]){
				cout<<"overflow"<<endl;
			}else{
				for(int i=keta;i>=0;i--){
					cout<<sum[i];
				}
				cout<<endl;
			}

		}
	}
    return 0;
}

Measured memory_bytes: 1208
def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    return C0 * C1 <= 0 and D0 * D1 <= 0

def contains(P, Q):
    v = []
    for q in Q:
        for i in range(4):
            v.append(cross3(P[i-1], P[i], q))
        if all(e <= 0 for e in v) or all(e >= 0 for e in v):
            return 1
    return 0

def check(Pi, Pj):
    if contains(Pi, Pj) or contains(Pj, Pi):
        return 1
    for i in range(4):
        for j in range(4):
            if is_intersection(Pi[i-1], Pi[i], Pj[j-1], Pj[j]):
                return 1
    return 0

def solve():
    M = readline(1)[0]
    *p, = range(M)
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            p[py] = px
        else:
            p[px] = py

    P = []
    for i in range(M):
        xa, ya, xb, yb, xc, yc, xd, yd = readline(8)
        P.append(((xa, ya), (xb, yb), (xc, yc), (xd, yd)))
    for i in range(M):
        for j in range(i+1, M):
            if check(P[i], P[j]):
                unite(i, j)
    res = 0
    for i in range(M):
        if i == root(i):
            res += 1
    return res


*r, = map(int, open(0).read().split())
it = iter(r)

def readline(v):
    r = []
    for i in range(v):
        r.append(next(it))
    return r

while 1:
    N = readline(1)[0]
    if N == 0:
        break
    for i in range(N):
        print(solve())


Measured memory_bytes: 5872
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
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; }

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main(int argc, char const *argv[]) {
  int n;
  ll m;
  cin >> n >> m;
  for(ll i=m/n+1; i>=1; i--){
    if(m%i==0 && m/n>=i){
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0;i < n;i++)cin >> a[i];

  for(int i = 0;i < n;i++){
    if(a[i] % 2 == 1){
      cout << "first" << endl;
      return 0;
    }
  }

  cout << "second" << endl;
}

Measured memory_bytes: 640
def main():
        

    N = int(input())
    A_s = list(map(int, input().split()))

    all_xor = A_s[0]

    for i in range(1, N):
        all_xor = (all_xor ^ A_s[i])

    ans_list = []

    for i in range(N):
        ans = (all_xor ^ A_s[i])
        ans_list.append(ans)

    print(' '.join(map(str, ans_list)))


if __name__ == '__main__':
    main()


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

int main()
{
    int n,w;
    cin >> n >> w;
    int a[n][2];
    for(int i=0;i<n;i++)
     cin >> a[i][0] >> a[i][1];
    vector<vector<long long>> kp(n+1,vector<long long>(w+1,0));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(j+1<a[i][0])
             kp[i+1][j+1]=kp[i][j+1];
            else
            {
                kp[i+1][j+1]=max(a[i][1]+kp[i][j+1-a[i][0]],kp[i][j+1]);
            }
        }
    }
    cout << kp[n][w];
    return 0;
}

Measured memory_bytes: 82988
//{{{
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(...) repN((__VA_ARGS__,rep3,rep2,loop,~))(__VA_ARGS__)
#define loop(n) rep2(_loop_,n)
#define rep2(i,n) rep3(i,0,n)
#define rep3(i,begin,end) for(int i=(int)(begin),i##_end=(int)(end);i<i##_end;++i)
#define repN(a) repX a
#define repX(a0,a1,a2,x,...) x
const int MOD = 1e9+7;
//}}}

int A[2][100];
int main(){
	int N;
	cin >> N;
	rep(i, 2) rep(j, N) cin >> A[i][j];
	int ans=0;
	rep(i,N){
		int sum=0;
		rep(j,0,i+1) sum+=A[0][j];
		rep(j,i,N) sum+=A[1][j];
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
n = gets.to_i
as = gets.split.map(&:to_i)
bs = gets.split.map(&:to_i)

ans = 0
bs.each_with_index do |b, i|
  2.times do |j|
    d = as[i + j] <= b ? as[i + j] : b
    as[i + j] -= d
    ans += d
    b -= d
  end
end

puts ans


Measured memory_bytes: 15388
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	final static long MOD = 1000000007;
	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();

		String[] Ws = W.split(" ");

		long[] A = new long[Ws.length];
		for (int i = 0; i < Ws.length; i++) {
			A[i] = Long.parseLong(Ws[i]);
		}

		System.out.println(A[2]+" "+A[0]+" "+A[1]);

	}
}


Measured memory_bytes: 21204
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main(){
    long N;string S;
    cin>>N>>S;
    vector<int> we(N);
    vector<int> ea(N);
    long ans=1e9;
    
    if(S[0]=='W'){
        we[0]++;
    }else{
        ea[0]++;
    }
    for(long i = 1; i < N; i++)
    {
        we[i]=we[i-1];
        ea[i]=ea[i-1];
        if(S[i]=='W'){
            we[i]++;
        }else{
            ea[i]++;
        }
    }
    
    for(int i=0;i<N;++i){
        long tmp=0;
        tmp=(ea[N-1]-ea[i])+we[i];

    if(i==0)tmp-=we[i];
    ans=min(ans,tmp);

    }

    cout<<ans<<endl;

}


Measured memory_bytes: 3076
/**
  * @brief atcoder
  * @author yao
  */
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#include <queue>
#define ft first
#define sd second
#ifdef DBG
#   define dbg_pri(x...) fprintf(stderr,x)
#else
#   define dbg_pri(x...) 0
#   define NDEBUG
#endif //DBG
#include <cassert>

typedef unsigned int uint;
typedef long long int lli;
typedef unsigned long long int ulli;

#define N 262144

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;++i) scanf("%d", &a[i]);
    std::sort(a,a+n,std::greater<int>());
    lli ans = 0;
    std::priority_queue<std::pair<int,int>> pq;
    pq.push({a[0],a[0]});
    for(int i=1;i<n;++i)
    {
        int u=pq.top().ft,v=pq.top().sd;
        pq.pop();
        ans += u;
        pq.push({a[i],u});
        pq.push({a[i],v});
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 5576
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

///////////////////////////





int main() {

	string s;
	cin >> s;
	if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) { cout << "Yes"; }
	else if (s[0] == s[2] && s[2] != s[3] && s[1] == s[3]) { cout << "Yes"; }
	else if (s[0] == s[3] && s[3] != s[2] && s[1] == s[2]) { cout << "Yes"; }
	else { cout << "No"; }
	system("PAUSE");


}


Measured memory_bytes: 504
#include<bits/stdc++.h>
#define ll long long int
#define loop(i,a,b) for(ll i=a;i<b;i++)
using namespace std;
int main()
{
	ll n;
	cin>>n;
	ll arr[n],cost[n] = {0};
	loop(i,0,n) cin>>arr[i];
	cost[1] = abs(arr[1]-arr[0]);
	loop(i,2,n)
	{
		cost[i] = min(cost[i-1]+abs(arr[i]-arr[i-1]),cost[i-2]+abs(arr[i]-arr[i-2]));
	}
	cout<<cost[n-1];
	return 0;
}

Measured memory_bytes: 1792
N,*S = map(int,open(0).read().split())

p = [[False for i in range(100*100+1)]  for j in range(N+1)]

p[0][0] = True

for i in range(N):
    for j in range(100*N+1):
      #S0~Si, point sum is j
      if p[i][j] == True:
        # incorrect
        p[i+1][j] = True
        # correct
        p[i+1][j+S[i]] = True 

for i in range(100*N, -1, -1):
  if p[N][i] == True and i % 10 != 0:
    print(i)
    exit()

print(0)


Measured memory_bytes: 17284
fn main() {
  let nums = read_nums();
  let a = nums[0];
  let b = nums[1];
  let t = nums[2];
  println!("{}", t / a * b);
}

fn read_line() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim().to_string()
}

fn read_nums() -> Vec<i32> {
    read_line()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect()
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
//#define sort(vec) sort(vec.begin(),vec.end())
#define reverse(vec) reverse(vec.begin(),vec.end())
#define unsort(vec); sort(vec);reverse(vec);
#define int long long
#define inf 1000000007

int gcd(int x,int y){
	if(y==0) return x;
	else return gcd(y,x%y);
}

int lcm(int x,int y){
	return x/gcd(x,y)*y;
}

signed main(){
	int n;
	cin>>n;
	int a[n],b[n],c[n],dp[n][3];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	dp[0][0]=a[0],dp[0][1]=b[0],dp[0][2]=c[0];
	for(int i=1;i<n;i++){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]})<<endl;
}

Measured memory_bytes: 4992