akhauriyash/Code-Regression huggingface dataset:
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        input_inner!{$s, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($exp_input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                let start = std::time::Instant::now();
                let input = solve($exp_input);
                let end = start.elapsed();
                assert_eq!(input, $output, "{}.{:03}", end.as_secs(), end.subsec_millis());
                assert!(end.as_secs() <= 2, "expected_sec: {}sec, actual_sec: {}sec", 2, end.as_secs());
                assert!(end.as_secs() <= 1, "expected_sec: {}sec, actual_sec: {}sec", 1, end.as_secs());
                assert!(end.subsec_millis() <= 10, "expected_ms: {}ms, actual_ms: {}ms", 10, end.subsec_millis());
                assert!(end.subsec_millis() <= 2, "expected_ms: {}ms, actual_ms: {}ms", 2, end.subsec_millis());
            )*
        }
    };
}

test! {
r#"5"# => r#"3"#,
r#"2"# => r#"1"#,
r#"100"# => r#"50"#,
}

fn solve(src: &str) -> String {
    let mut src_iter = src.split_whitespace();
    input! {
        source = src_iter,
        n: usize,
    }

    let ans = (if n % 2 == 0 { 0 } else { 1 } + n) / 2;
    ans.to_string()
}

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

bool isprime(int n) {
    if(n < 2) {
        return false;
    }
    if(n == 2) {
        return true;
    }
    if(n%2 == 0) {
        return false;
    }
    for(int i = 3;i*i < n + 1;i += 2) {
        if(n%i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int N;
    scanf("%d", &N);
    int n = 0;
    for(int i = 1;n < N;i++) {
        if(isprime(10*i + 1)) {
            printf("%d ", 10*i + 1);
            n++;
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int64_t a,int64_t b){
    if(a==0||b==0){
        return 0;
    }
    if(a%b==0){
        return b;
    }else{
        return(gcd(b,a%b));
    }

}
int main(){
    int64_t x;
    int64_t y;
    cin >> x >> y;
    cout << x*y/gcd(x,y) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits>
#define MAX 100001
int altura[MAX], custoMinimo[MAX], k, n;
int custo(int atual)
{
    if(custoMinimo[atual] != -1)
        return custoMinimo[atual];
    int minimo = std::numeric_limits<int>::max();
    for(int i = 1; i <= k && atual - i >= 1; i++)
        minimo = std::min(minimo, custo(atual - i) + std::abs(altura[atual] - altura[atual - i]));
    return custoMinimo[atual] = minimo;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        custoMinimo[i] = -1;
        std::cin >> altura[i];
    }
    custoMinimo[1] = 0;
    std::cout << custo(n) << '\n';
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int ans=1e9;
	for(int i=0;i<s.size()-2;i++)
		ans=min(ans,abs(stoi(s.substr(i,3))-753));
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    ll dx = x2 - x1;
    ll dy = y2 - y1;

    ll x3 = x2 - dy;
    ll y3 = y2 + dx;
    ll x4 = x3 - dx;
    ll y4 = y3 - dy;

    cout << x3 << " " <<  y3 << " " << x4  << " " << y4 << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var H, N int
	fmt.Scan(&H)
	fmt.Scan(&N)
	a := make([]int, N)

	var r int
	for i := range a {
		fmt.Scan(&a[i])
		r += a[i]
	}
	var s string
	if r >= H {
		s = "Yes"
	} else {
		s = "No"
	}
	fmt.Printf("%s", s)
}


Measured memory_bytes: 5504
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let v :Vec<usize> = read_vec();
    if (v[0] + v[1]) % 2 == 0 {
        println!("{}", (v[0]+v[1])/2);
    } else {
        println!("IMPOSSIBLE");
    }
}


Measured memory_bytes: 4352
n = int(input())
a = list(map(int, input().split())) 
a = sorted(a)
flag_diff = True
for i in range(len(a) - 1):
    if a[i] == a[i+1]:
        flag_diff = False

if flag_diff is True:
    print("YES")
else:
    print("NO")

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b>c+d)
    cout << "Left" << endl;
  else if(a+b == c+d)
    cout << "Balanced" << endl;
  else
    cout << "Right" << endl;
}


Measured memory_bytes: 256
/* ***************************************
Author        :Scau.ion
Created Time  :2017/04/15 20:29:52 UTC+8
File Name     :ion.cpp
*************************************** */

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

#define LL long long
#define ULL unsigned long long
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<PII>
#define X first
#define Y second
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define IN freopen("in", "r", stdin);
#define OUT freopen("out", "w", stdout);

const int maxn=100010;

VI son[maxn];
VI ans;
int tar;
bool near[maxn];
int last;
bool vis[maxn];
bool vis2[maxn];

bool dfs1(int st)
{
    ans.PB(st);
    vis2[st]=1;
    if (st==tar) return 1;
    for (int j=0;j<son[st].size();++j)
    {
        if (vis2[son[st][j]]) continue;
        if (dfs1(son[st][j])) return 1;
    }
    ans.pop_back();
    return 0;
}

bool dfs2(int st)
{
    ans.PB(st);
    if (near[st]) --last;
    vis[st]=1;
    vis2[st]=1;
    bool flag=1;
    for (int j=0;j<son[st].size();++j)
    {
        if (vis[son[st][j]]==0)
        {
            flag=0;
            if (vis2[son[st][j]]==0&&dfs2(son[st][j])) return 1;
        }
    }
    if (flag==1&&last==0) return 1;
    if (near[st]) ++last;
    vis[st]=0;
    ans.pop_back();
    return 0;
}

int main()
{
    IOS;
    int n,m;
    cin>>n>>m;
    for (int j=1;j<=m;++j)
    {
        int u,v;
        cin>>u>>v;
        son[u].PB(v);
        son[v].PB(u);
    }
    VI ones;
    for (int j=1;j<=n;++j)
        if (son[j].size()==1) ones.PB(j);
    if (ones.size()>=2)
    {
        tar=ones[1];
        dfs1(ones[0]);
    }
    else
    {
        for (int j=1;j<=n;++j)
        {
            memset(near,0,sizeof near);
            memset(vis2,0,sizeof vis2);
            for (int k=0;k<son[j].size();++k)
                near[son[j][k]]=1;
            last=son[j].size();
            if (dfs2(j)) break;
        }
    }
    cout<<ans.size()<<endl;
    for (int j=0;j<ans.size();++j)
        cout<<ans[j]<<" ";
    cout<<endl;
    return 0;
}


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

int main(){
    int n;
    while(cin>>n , n){
        int table[n+1][n+1];
        
        for(int i=0; i<=n; i++){
            table[i][n]=0;
            table[n][i]=0;
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin>>table[i][j];
            }
        }
        

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
               table[i][n] += table[i][j];
            }
        }
        
        for(int j=0; j<=n; j++){
            for(int i=0; i<n; i++){
                table[n][j] += table[i][j];
            }
        }
        
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                printf("%5d",table[i][j]);
            }
            cout<<endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1192
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	string s;cin>>s;
	if(s=="A") cout<<"T"<<endl;
	if(s=="T") cout<<"A"<<endl;
	if(s=="C") cout<<"G"<<endl;
	if(s=="G") cout<<"C"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<long long,int> P;
static const int INF=1<<24;

int main(){
	string stmp1="qazwsxedcrfvtgb",stmp2="yhnujmikolp";
	int st[30];
	rep(i,stmp1.size()){
		st[stmp1[i]-'a']=1;
	}
	rep(i,stmp2.size()){
		st[stmp2[i]-'a']=0;
	}
	string s;
	while(cin>>s,s[0]!='#'){
		int res=0;
		int ju=st[s[0]-'a'];
		rep(i,s.size()){
			if(ju!=st[s[i]-'a']){
				ju=st[s[i]-'a'];
				res++;
			}
		}
		cout<<res<<endl;
	}
	return 0;
}

Measured memory_bytes: 1188
#include <stdio.h>
#include <string.h>
int main(void)
{
	char s[16];
	int len;
	int jouken = 0;
	int c=0;
	int roop;
	scanf("%s", s);
	len = strlen(s);
	
	if(s[0] == 'A') jouken += 1;
	
	for(roop = 2;roop < (len-1);roop++){
		if(s[roop] == 'C') c++;
	}
	if(c == 1) jouken += 1;
	
	c = 0;
	
	for(roop = 0;roop <= len;roop++){
		if((s[roop] >= 'A') && (s[roop] <= 'Z')) c++;
	}
	if(c == 2)jouken += 1;
	
	if(jouken == 3)printf("AC\n");
	if(jouken != 3)printf("WA\n");
	
	return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		double[] dp=new double[N+1];
		for(int i=0; i<=N; i++) {
			dp[i]=0;
		}
		dp[0]=1;
		double[] kakuritu=new double[N];
		for(int i=0; i<N; i++) {
			kakuritu[i]=sc.nextDouble();
		}
		for(int i=0; i<N; i++) {
			for(int j=i; j>=0; j--) {
				dp[j+1]+=dp[j]*kakuritu[i];
				dp[j]*=(1.000d-kakuritu[i]);
			}
		}
		double sum=0;
		for(int i=(N+1)/2; i<=N; i++) {
			sum+=dp[i];
		}
		System.out.println(sum);
	}
}

Measured memory_bytes: 37372
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
template <class T> using V = vector<T>;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
const long long INF = 1LL << 60;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
 
#define comuse Comuse()
 
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
 
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n;
  	ci(n);
  ll h,w;
  	ci(h>>w);
  ll ans=0;
  FOR(i,0,n){
    ll a,b;
    	ci(a>>b);
    if(h<=a&&w<=b){
      ans++;
    }
  }
  co(ans)
}

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

using namespace std;

long long int dp[3001][3001][2];

long long int solve(long int a[], int i,int j,int t)
{
    if(i==j)
    {
        return 0;
    }
	else if(dp[i][j][t]!=-1)
	{
		return dp[i][j][t];
	}
    else if(t==1)
    {
        dp[i][j][t] = max(solve(a,i+1,j,0)+a[i], solve(a, i,j-1,0)+a[j-1]);
    }
    else
    {
        dp[i][j][t] = min(solve(a, i+1,j,1)-a[i],solve(a, i,j-1,1)-a[j-1]);
    }
    
    return dp[i][j][t];
}

int main()
{
    int n;
    cin>>n;
    long int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
	
    memset(dp, -1, sizeof(dp[0][0][0]) * 3001 * 3001 * 2);
				
    cout<<solve(a,0,n,1);

    return 0;
    

}

Measured memory_bytes: 141184
#include<bits/stdc++.h>
using namespace std;
long long n,t,q;
long long a[100001],b[100001],ans[100001];
bool v[100001],tecked[100001]={};
long long teckb(long long k){
	if(tecked[k]){
		return ans[k];
	}
	tecked[k]=true;
	if(k<=0){
		return ans[k]=b[k];
	}
	if(v[k-1]){
		return ans[k]=max(b[k],(b[k]+b[k-1])/2);
	}
	return ans[k]=max(b[k],teckb(k-1));
}
long long teck(long long k){
	//cout<<k<<'k';
	if(tecked[k]){
		//cout<<"tecked"<<endl;
		return ans[k];
	}
	tecked[k]=true;
	if(k>=n-1){
		//cout<<'b';
		return ans[k]=b[k];
	}
	if(!v[k+1]){
		//cout<<'a'<<b[k-1]<<b[k];
		return ans[k]=min(b[k],(b[k]+b[k+1])/2);
	}
	//cout<<'k';
	return ans[k]=min(b[k],teck(k+1));
}
int main(){
	int w;
	cin>>n>>t>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		cin>>w;
		if(w==1){
			b[i]=a[i]+t;
			v[i]=true;
		}else if(w==2){
			b[i]=a[i]-t;
			v[i]=false;
		}
		tecked[i]=false;
	}
	//for(int i=0;i<n;i++){
	//	cout<<i<<" a"<<a[i]<<" b"<<b[i]<<endl;
	//}
	for(int i=0;i<q;i++){
		cin>>w;
		w--;
		if(v[w]){
			cout<<teck(w)<<endl;
		}else{
			cout<<teckb(w)<<endl;
		}
	}
	//for(int i=0;i<n;i++){
	//	cout<<"i"<<i<<" a"<<a[i]<<" b"<<b[i]<<" ans"<<ans[i];
	//	if(v[i]){
	//		cout<<"left"<<endl;
	//	}else{
	//		cout<<"right"<<endl;
	//	}
	//}
}


Measured memory_bytes: 6292
#include <iostream>
#include <map>
#include <cstdlib>

using namespace std;
int num1=0, n, count=0, T[200000];
string str;
map<int, int> QS;

void print(){
    map<int, int>::iterator it;
    int ans=0;
    for(it=QS.begin();it!=QS.end();it++){
        pair<int, int> item=*it;
        //cout << item.first << " : " << item.second << endl;
        ans += item.second*(item.second-1)/2;
    }
    cout << ans << endl;
}

int main(){
    cin >> str;
    T[0]=0;
    QS[T[0]]++;
    int j=0;
    int p=1;
    for(int i=str.size()-1;i>=0;i--){
        int a = (str[i]-'0');
        if(j) p = (p*10)%2019;
        T[j+1] = (T[j]+a*p)%2019;
        QS[T[j+1]]++;
        j++;
    }
    print();
    return 0;
}

Measured memory_bytes: 4440
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define M 1000000007
#define sz(a) (ll)a.size()
#define pll pair<ll,ll>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define sep(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll f[10005],n;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    rep(i,1,101)
    {
        rep(j,1,101)
        {
            rep(k,1,101)
            {
                ll v=i*i+j*j+k*k+i*j+j*k+i*k;
                if(v<=n)
                    f[v]++;
            }
        }
    }
    rep(i,1,n+1)
        cout<<f[i]<<"\n";
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define hell 1000000007
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long int
#define pi 3.1415926536
using namespace std;

/*ll merge(vector<ll> &v,ll l,ll m,ll r)
{
	ll n1=m-l+1;
	ll n2=r-m;
	ll inv=0;
	vector<ll> a(n1),b(n2);
	for(ll i=0;i<n1;i++)
	a[i]=v[l+i];
	for(ll i=0;i<n2;i++)
	b[i]=v[m+1+i];
	ll i=0,j=0,k=l;
	while(i<n1&&j<n2)
	{
		if(a[i]<=b[j])
		{
			v[k]=a[i];
			i++;
		}
		else
		{   inv+=(m-i+1);
			v[k]=b[j];
			j++;
		}
		k++;
	}
	while(i<n1)
	{
		v[k]=a[i];
		i++;
		k++;
	}
	while(j<n2)
	{
		v[k]=b[j];
		j++;
		k++;
	}
	return inv;
}
ll mergesort(vector<ll> &v,ll l,ll r)
{  ll inv=0;
	if(l<r)
	{
		ll m=l+(r-l)/2;
		inv=mergesort(v,l,m);
		inv+=mergesort(v,m+1,r);
		inv+=merge(v,l,m,r);
	}
	return inv;
}*/

/*ll factorize(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            if((n/i)!=i)
            res.push_back(n/i);
        }
    }
    
    return (ll)res.size();
}*/

void solve()
{ll n,k,ans,z,d=0,q,l=INT_MIN,mini=0,prev;
   cin>>n;
   vector<double> v;
   d=1;
   double a,b;
   for(ll i=0;i<n;i++)
   { cin>>a;
   	v.pb(a);
   }
   sort(v.rbegin(),v.rend());
   while(n>1)
   {
   	  b=(v[n-1]+v[n-2])/2;
   	  v.pop_back();
   	  v.pop_back();
   	  v.push_back(b);
   	  n=n-1;
   }
   
   cout<<fixed<<setprecision(9)<<v[0];
}

int main()
{
  fast
ll t=1;

while(t--)
{solve();
 //cout<<ma<<endl;
}
return 0;}

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

int main(){
    string S, T;
    int q;
    cin >> S;
    cin >> T;
    cin >> q;
    vector<int> a(q);
    vector<int> b(q);
    vector<int> c(q);
    vector<int> d(q);
    for(int i = 0; i < q; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> S_sum(S.size() + 1);
    vector<int> T_sum(T.size() + 1);
    S_sum[0] = 0, T_sum[0] = 0;
    int current_sum = 0;
    for(int i = 1; i <= S.size(); i++){
        current_sum += S[i - 1] == 'A' ? 1 : 2;
        S_sum[i] = current_sum;
    }
    current_sum = 0;
    for(int i = 1; i <= T.size(); i++){
        current_sum += T[i - 1] == 'A' ? 1 : 2;
        T_sum[i] = current_sum;
    }
    for(int i = 0; i < q; i++){
        int s_point = S_sum[b[i]] - S_sum[a[i] - 1];
        int t_point = T_sum[d[i]] - T_sum[c[i] - 1];
        if(s_point % 3 == t_point % 3) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}


Measured memory_bytes: 3200
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)

typedef long long ll;

int main() {
    int n, a, b;
    while (scanf("%d%d%d", &n, &a, &b) != EOF)  {
        printf("%d %d\n", min(a, b), a + b - n > 0 ? a + b - n : 0 );
    }
    return 0;
}


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

void Main() {
	long long X, money = 100, cnt = 0;
	
	cin >> X;
	while (true) {
		if (money >= X) {
			break;
		}
		money = money * 1.01;
		cnt++;
	}
	cout << cnt << endl;
}

int main() {
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n) {
        string s;
        cin >> s;
        mp[s]++;
    }
    for (string s : {"AC", "WA", "TLE", "RE"}) {
        cout << s << " x " << mp[s] << endl;
    }
    
}


Measured memory_bytes: 3628
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from cmath import phase, rect
from math import acos
def resolve():
    n, k = map(int, input().split())
    ZC = [None] * n
    for i in range(n):
        x, y, c = map(int, input().split())
        ZC[i] = (complex(x, y), c)

    def check(t):
        # i-th circle : Z[i][0] centered with radius t / Z[i][1]
        circle = [(z, t / c) for z, c in ZC]
        candidate = [c for c, r in circle]
        for c1, r1 in circle:
            for c2, r2 in circle:
                if c1 == c2:
                    continue
                d = abs(c2 - c1)
                alpha = phase(c2 - c1)
                s = (r1**2 + d**2 - r2**2) / (2 * r1 * d)
                if abs(s) >= 1:
                    continue
                theta = acos(s)
                candidate.append(c1 + rect(r1, alpha + theta))
                candidate.append(c1 + rect(r1, alpha - theta))

        return any(sum(abs(z - c) <= r + 0.00001 for c, r in circle) >= k for z in candidate)

    l = 0
    r = 1 << 30
    for _ in range(100):
        m = (l + r) / 2
        if check(m):
            r = m
        else:
            l = m

    print(m)
resolve()

Measured memory_bytes: 48860
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vi a2 = a;
    sort(a2.begin(),a2.end());
    int count = 0;
    rep(i,n){
        if(a[i] != a2[i])count++;
    }
    if(count <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

ab.sort()

for i in ab:
    if m >= i[1]:
        res += i[0]* i[1]
        m -= i[1]
    else:
        res += i[0] * m
        m = 0
    if m == 0:
        break

print(res)

Measured memory_bytes: 27756
#include<stdio.h>

#define MAX 500000

void maxHeapify(int*,int,int);
void buildMaxHeap(int*,int);

int main(){
  int A[MAX],i,h;

  scanf("%d",&h);
  for(i = 1; i <= h; i++){
    scanf("%d",&A[i]);
  }

  buildMaxHeap(A,h);

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

void buildMaxHeap(int *A,int H){
  int i;
  
  for(i = H/2; i >= 1; i--){
    maxHeapify(A,i,H);
  }
}

void maxHeapify(int* A,int i,int H){

  int largest,l,r,x;

  l = 2 * i;
  r = 2 * i + 1;
 
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;

  if(r <= H && A[r] > A[largest]) largest = r;

  if(largest != i){
    x = A[i];
    A[i] = A[largest];
    A[largest] = x;
    maxHeapify(A,largest,H);
  }
}

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

int A[500005];
int n;

void swap(int i, int j){
    int tmp = A[j];
    A[j] = A[i];
    A[i] = tmp;
}

void maxHeapify(int i){
    int maxi = A[i];
    int maxi_id = i;
    if(2*i<=n){
        int lvalue = A[2*i];
        if(lvalue>maxi){
            maxi = lvalue;
            maxi_id = 2*i;
        }
    }
    if((2*i+1)<=n){
        int rvalue = A[2*i+1];
        if(rvalue>maxi){
            maxi = rvalue;
            maxi_id = 2*i+1;
        }
    }
    if(maxi_id != i){
        swap(i,maxi_id);
        maxHeapify(maxi_id);
    }
}

void buildMaxHeap(){
    int H = n/2;
    for(int i=H;i>=1;--i){
        maxHeapify(i);
    }
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&A[i]);
    }
    buildMaxHeap();
    for(int i=1;i<=n;++i){
        printf(" %d",A[i]);
    }
    printf("\n");
    return 0;
}



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

typedef long long ll;

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

    int n; cin >> n;
    for(int i=1;i<=n;i++){
        bool check = false;
        int x = i;
        if(x%3==0){
            cout << ' ' << i;
            continue;
        }
        while(x){
            if(x%10==3){
                cout << ' ' << i;
                check = true;
                if(check) break;
            }
            if(check) break;
            else x /= 10;
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3208
w,h,n = map(int,input().split())
x_start = 0
x_end = w
y_start = 0
y_end = h 
array = []
for i in range(n):
    x,y,a=map(int,input().split())
    if a == 1:
        x_start = max(x,x_start)
    elif a == 2:
        x_end = min(x,x_end)
    elif a == 3:
        y_start = max(y,y_start)
    elif a == 4:
        y_end = min(y,y_end)
x_len = x_end-x_start
y_len = y_end-y_start
if x_len <= 0 or y_len <= 0:
    print(0)
else:
    print(x_len * y_len)

Measured memory_bytes: 3064
ABCD = input()

a = ABCD[0]
f = int(a)

def recur(total,formula,i):
  #=3回足せば
  if i == 4:
    #合計が7であれば
    if total == 7:
      print(formula+"=7")
      exit()
  #ABCD[0]に対してABCD[1~3]まで3回足し算or引き算を実行する
  #足し算引き算の再帰実行に応じて+-の演算子を持っておく
  else:
    recur(total + int(ABCD[i]),formula + "+" + ABCD[i],i + 1),
    recur(total - int(ABCD[i]),formula + "-" + ABCD[i],i + 1)
  
recur(f,a,1)


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

int main()
{
    int x;
    for (int i = 0; i < 10000; i++)
    {
        cin >> x;
        cout << "Case " << i + 1 << ": " << x << endl;
        if (x == 0)
        {
            break;
        }
    }
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, c;
    cin >> n >> c;
    vector<vector<int>> d(c+1, vector<int>(c+1));
    for(int i = 1; i <= c; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            cin >> d[i][j];
        }
    }
    vector<vector<int>> vc(n, vector<int>(n));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> vc[i][j];
        }
    }

    vector<int> r0(c+1);
    vector<int> r1(c+1);
    vector<int> r2(c+1);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int before = vc[i][j];
            int r = i + j;
            if(r % 3 == 0) 
            {
                r0[before]++;
            }
            if(r % 3 == 1) 
            {
                r1[before]++;
            }
            if(r % 3 == 2) 
            {
                r2[before]++;
            }
        }
    }
    int ans = 1e10;
    for(int i = 1; i <= c; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            for(int k = 1; k <= c; k++)
            {
                if(i == j || j == k || i == k) continue;
                int tmpans = 0;
                for(int p = 1; p <= c; p++)
                {
                    tmpans += r0[p] * d[p][i] + r1[p] * d[p][j] + r2[p] * d[p][k];
                }
                ans = min(ans, tmpans);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define local
//if you find any bug in my code, please tell me.
set<int> k;
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
    int n,x;
    cin>>n;
    while(n--)
    {
        scanf("%d",&x);
        k.insert(x);
    }
    if(k.size()&1) cout<<k.size()<<endl;
    else cout<<k.size()-1<<endl;
    return 0;
}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int T = 1e5 + 10;
const ll MOD = 1e9 + 7;

int vis[T];
int v[T];
ll ans[T];
ll f[T];
int n;

ll expo(ll base, ll e) {
    ll ans = 1;
    while(e) {
        if(e&1) ans = (ans * base) % MOD;
        base = (base * base) % MOD;
        e >>= 1;
    }
    return ans;
}

ll fat(ll x) {
    if(~f[x]) return f[x];
    return f[x] = (x * fat(x-1))%MOD;
}

ll choose(ll n, ll x) {
    ll div = (fat(x) * fat(n-x))%MOD;
    return (fat(n)*expo(div,MOD-2))%MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    memset(f,-1,sizeof f);
    f[0] = 1; f[1] = 1;

    cin >> n;
    n++;
    ans[1] = n-1;
    for(int i = 2; i <= n; i++) ans[i] = choose(n,i);

    int a,b;

    for(int i = 1; i <= n+1; i++) {
        cin >> v[i];
        if(vis[v[i]]) a = vis[v[i]], b = i;
        vis[v[i]] = i;
    }

    a--;
    b = n-b;
    for(int i = 1; i <=a+b; i++) ans[i+1] = (ans[i+1] - choose(a+b,i) + MOD) % MOD;
    for(int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}



Measured memory_bytes: 5120
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int w[100000];

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

  int d = a - b;

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

  int l = 0, r = 1000000000;

  while (l <= r) {
    int m = (l + r) / 2;
    long long s = 0;
    for (int i = 0; i < n; i++) {
      if (w[i] > (long long)b * m) {
        s += (w[i] - (long long)b * m + d - 1) / d;
      }
    }
    if (s <= m) {
      r = m - 1;
    } else {
      l = m + 1;
    }
  }
  printf("%d\n", l);
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> cnt(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        cnt[a]++; cnt[b]++;
    }
    bool ans = true;
    rep(i, n) {
        if (cnt[i]%2 != 0) {
            ans = false;
            break;
        }
    }
    cout << (ans ? "YES" : "NO") << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  ll r, d, x; cin >> r >>d >>x;
  rep(i,10) {
    x = r*x-d;
    cout << x << endl;
  }

  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func COM(n, k int64) int64 {
	r := int64(1)
	for i := int64(0); i < k; i++ {
		r = ModMul(r, n-i)
		r = ModDiv(r, i+1)
	}

	return r
}

const (
	MOD = 1000000000 + 7
)

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

type Q struct {
	value int
	index int
	A, B  int
}

type QS []*Q

func (p QS) Len() int           { return len(p) }
func (p QS) Less(i, j int) bool { return p[i].value > p[j].value }
func (pq QS) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *QS) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Q)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *QS) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func FactoredPrimeNumber(num int) map[int]int {
	m := map[int]int{}
	return factor(m, num, 2)
}

func factor(result map[int]int, num, pnum int) map[int]int {
	if pnum*pnum > num {
		if num != 1 {
			result[num] += 1
		}
		return result
	}

	if num%pnum == 0 {
		num /= pnum
		result[pnum]++
	} else {
		pnum++
	}
	return factor(result, num, pnum)
}

func GCD(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int64) int64 {
	return a * b / GCD(a, b)
}

func main() {
	var L string
	fmt.Scanf("%s\n", &L)
	R := []rune(L)
	l := len(R)
	ans := int64(0)
	cnt := 0
	for idx, r := range R {
		n := string(r)
		if n == "0" {
			continue
		}
		t := ModPow(3, int64(l-idx-1))
		o := ModPow(2, int64(cnt))
		cnt++
		ans = ModAdd(ans, ModMul(t, o))
	}
	ans = ModAdd(ans, ModPow(2, int64(cnt)))
	fmt.Println(ans)
}

func Reverse(runes []rune) []rune {
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}


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

bool can(string s1, string s2, int pos){
	for(int j = pos; j < pos + s2.size() && j < s1.size(); j++){
		if(s1[j] != '?' && s2[j-pos] != '?' && s1[j] != s2[j-pos]){
			return 0;
		}
	}
	return 1;
}
bool ok[3][3][2020];
string s[3];

int get_it(int a, int b, int c){
	int ans = s[a].size() + s[b].size() + s[c].size();
	for(int pos1 = 0; pos1 <= s[a].size(); pos1++){
		for(int pos2 = 0; pos2 <= s[b].size() || pos1 + pos2 <= s[a].size(); pos2++){
			if(ok[a][b][pos1] && (pos2 >= s[b].size() || ok[b][c][pos2]) && (pos1 + pos2 >= s[a].size() || ok[a][c][pos1 + pos2])){
				ans = min(ans, max({pos1 + pos2 + (int)s[c].size(), pos1 + (int)s[b].size(), (int)s[a].size()}));
			}
		}
	}
	return ans;
}

int main(){
	cin >> s[0] >> s[1] >> s[2];
	rep(i, 3){
		rep(j, 3){
			rep(pos, s[j].size()){
				ok[j][i][pos] = can(s[j], s[i], pos);
			}
			ok[j][i][s[j].size()] = 1;
		}
	}
	cout << min({get_it(0, 1, 2), get_it(0, 2, 1), get_it(1, 0, 2), 
                 get_it(1, 2, 0), get_it(2, 0, 1), get_it(2, 1, 0)}) << endl;
	return 0;
}

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

int main(){
    
    // double h, l;
    // cin>>h>>l;
    // double ans = ((l*l) - (h*h))/(2.0*h);
    // cout<<fixed<<setprecision(13)<<ans<<endl;
    // return 0;
    int n;
    cin>>n;
    if(n < 10)
        cout<<(n)<<endl;
    if(n >= 10 && n < 100)
        cout<<9<<endl;
    if(n >= 100 && n < 1000)
        cout<<(9 + (n-100+1))<<endl;
    if(n >= 1000 && n < 10000)
        cout<<(999-100+10)<<endl;
    if(n >= 10000 && n < 100000)
        cout<<((999-100+10)+(n-10000+1))<<endl;
    if(n >= 100000)
        cout<<((999-100+10)+(99999-10000+1))<<endl;
    return 0;
}

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

int main(){
    int a;
    cin >> a ;
    int s_1 , s_2 , s_3;
    s_1 = (a-(a%100))/100;
    s_2 = (a - 100* s_1 - (a - 100* s_1)%10)/10;
    s_3 = (a - 100* s_1)%10;
    cout << s_1+s_2+s_3;
}

Measured memory_bytes: 3580
// AOJ 2069: Greedy, Greedy.
// 2017.11.5 bal4u@uu

#include <stdio.h>
#include <string.h>
#define TM 0
#if TM
#include <time.h>
#endif

int c[52], n;
int dp[2001];

int calcGreedy(int lim)
{
	int v, p, i, k, s;
	for (v = lim; v >= 0; v--) {
		p = v;
		for (s = 0, i = n - 1; i >= 0; i--) if (c[i] <= p) {
			k = p/c[i];
			s += k;
			p -= c[i]*k;
		}
		if (s != dp[v]) return 0;
	}
	return 1;
}

void calcDP(int lim)
{
	int i, j, k;
	memset(dp, 0, sizeof(dp));
	for (i = 0; i < n; i++) for (j = 0; (k = j + c[i]) <= lim; j++) {
		if (!dp[k] || dp[k] > dp[j] + 1) dp[k] = dp[j] + 1;
	}
}

char buf[302], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int cno = 0, i, lim;
#if TM
	clock_t start, end;
	start = clock();
#endif
	while (fgets(p=buf, 300, stdin) && *p != '0') {
		printf("Case #%d: ", ++cno);
		n = getint(), p++;
		c[0] = getint(), p++;
		if (c[0] != 1) { puts("Cannot pay some amount"); continue; }
		if (n == 1) { puts("OK"); continue; }
		for (i = 1; i < n; i++) c[i] = getint(), p++;
		lim = c[n-1] + c[n-2];
		calcDP(lim);
		if (calcGreedy(lim)) puts("OK");
		else puts("Cannot use greedy algorithm");
	}
#if TM
	end = clock();
	printf("time %lf\n", (double)(end-start)/CLOCKS_PER_SEC);
#endif
	return 0;
}

Measured memory_bytes: 1744
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<deque>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

using namespace std;

#define DBG cerr << '!' << endl;
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

ll ans[1000];

int main()
{
	ll n;cin >> n;
	vector<ll> c;
	vector<ll> s;
	vector<ll> f;
	
	REP(i,n-1)
	{
		ll A,B,C;cin >> A >> B >> C;
		c.PB(A);s.PB(B);f.PB(C);
	}
	
	REP(i,n)
	{
		ll ret = 0;
		for(int j = i;j < n-1;j++)
		{
			ll mati = max(s[j],((ret+f[j]-1)/f[j])*f[j]);
			ret = mati + c[j];
		}
		ans[i] = ret;
	}
	
	REP(i,n)
	{
		cout << ans[i] << endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 256
N = int(input())
ans = 0
for i in range(1,N+1):
    if i % 2 == 0:
      continue
    count = 0
    for j in range(1,i+1):
        if i % j == 0:
            count += 1
    if count == 8:
        ans += 1
print(ans)

Measured memory_bytes: 2940
def manhattan(cor_1, cor_2)
  x = cor_1[0] - cor_2[0]
  y = cor_1[1] - cor_2[1]
  x *= -1 if x < 0
  y *= -1 if y < 0
  x + y
end

def chebyshev_distance_1(cor_1, cor_2)
  patern_1 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])
  patern_2 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])*(-1)
  patern_3 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])
  patern_4 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])*(-1)
  patern_1
end

def chebyshev_distance_2(cor_1, cor_2)
  patern_1 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])
  patern_2 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])*(-1)
  patern_3 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])
  patern_4 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])*(-1)
  patern_2
end

def chebyshev_distance_3(cor_1, cor_2)
  patern_1 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])
  patern_2 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])*(-1)
  patern_3 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])
  patern_4 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])*(-1)
  patern_3
end

def chebyshev_distance_4(cor_1, cor_2)
  patern_1 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])
  patern_2 = (cor_1[0] - cor_2[0]) + (cor_1[1] - cor_2[1])*(-1)
  patern_3 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])
  patern_4 = (cor_1[0] - cor_2[0])*(-1) + (cor_1[1] - cor_2[1])*(-1)
  patern_4
end

N = gets.to_i

coordinates = []



N.times do
  coordinates << gets.split(' ').map(&:to_i)
end

patern_1_array = coordinates.map{ |coordinate| chebyshev_distance_1(coordinate, [0,0])}
patern_2_array = coordinates.map{ |coordinate| chebyshev_distance_2(coordinate, [0,0])}
patern_3_array = coordinates.map{ |coordinate| chebyshev_distance_3(coordinate, [0,0])}
patern_4_array = coordinates.map{ |coordinate| chebyshev_distance_4(coordinate, [0,0])}

ans_1 = patern_1_array.max - patern_1_array.min
ans_2 = patern_2_array.max - patern_2_array.min
ans_3 = patern_3_array.max - patern_3_array.min
ans_4 = patern_4_array.max - patern_4_array.min


puts [ans_1, ans_2, ans_3, ans_4].max


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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	string s; cin >> s;
	bool m = regex_match(s, regex("^A?KIHA?BA?RA?$"));
	cout << (m ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


#main
if __name__ == '__main__':
    solve()


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

def get_ans():
    n, k = map(int, raw_input().split())
    src = []
    for i in range(n):
        src.append(map(int, raw_input().split()))
    src.sort(key=lambda x:x[0]) # 0番目の要素でソート

    cnt = 0
    for a, b in src:
        cnt = cnt + b
        if cnt >= k:
            return a
            break
    return src[n-1][1]

if __name__ == '__main__':
    print get_ans()


Measured memory_bytes: 24436
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <math.h>

using namespace std;
struct adsf
{
    int x, y;
} p[10];
int fact(int n)
{
    if (n == 1)
        return 1;
    return fact(n - 1) * n;
}
double dis(int x, int y, int x1, int y1)
{
    return sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
}
int vis[10], n, path[10];
double ans;
void dfs(int pos)
{
    if (pos == n + 1)
    {
        for (int i = 2; i <= n; i++)
        {

            ans += dis(p[path[i]].x, p[path[i]].y, p[path[i - 1]].x, p[path[i - 1]].y);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            path[pos] = i;
            vis[i] = 1;
            dfs(pos + 1);
            vis[i] = 0;
        }
    }
}
int main()
{
    cin >> n;
    ans = 0;
    for (int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;
    dfs(1);
    printf("%.6f\n", ans / fact(n));
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<map>
 
using namespace std;

const long long MAX = 200001;  //nCk　の最大のn 
const long long MOD = 998244353; //prime

long long fac[MAX],finv[MAX],inv[MAX];


 
long long i,j,k,N,M2,K,ans,n;

long long power(long long X,long long P,long long M)
{
  long long s;
  
  if(P==0)
  {
    return 1;
  }
  else if(P%2==0)
  {
    s=power(X,P/2,M);
    s*=s;
    s%=M;
    return s;
  }
  else
  {
    s=power(X,P-1,M)*X;
    s%=M;
    return s;
  }
}

void COMint()
{
  fac[0]=1;
  finv[0]=1;
  fac[1]=1;
  finv[1]=1;
  inv[1]=1;
  for(i=2;i<MAX;i++)
  {
    fac[i]=fac[i-1]*i%MOD;  ///n!の計算
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD; ///n^{-1}の計算
    finv[i]=finv[i-1]*inv[i]%MOD;//n!^{-1}の計算
  }
  
  
}
 
long long comb(long long X,long long Y)
{
  if(X<Y) return 0;
  else if(X<0||Y<0) return 0;
  return fac[X]*(finv[Y]*finv[X-Y]%MOD)%MOD;
}


 
int main()
{
  cin>>N>>M2>>K;
  
  COMint();
 
  ans=(M2*power(M2-1,N-1,MOD))%MOD;
  for(i=1;i<=K;i++)
  {
    n=(M2*power(M2-1,N-i-1,MOD))%MOD;
 
    n=(n*comb(N-1,i))%MOD;
    ans+=n;
    ans%=MOD;
 
  }
  
  cout<<ans;
  
  
  
}

Measured memory_bytes: 8292
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
int main()
{
	ll n;
	cin >> n;
	ll h[n], dp[n];
	for(ll i = 0; i < n; i++) cin >> h[i];

	dp[n - 1] = 0;
	dp[n - 2] = abs(h[n - 2] - h[n - 1]);
	for(ll i = n - 3; i >= 0; i--)
	{
		dp[i] = min(dp[i + 1] + abs(h[i] - h[i + 1]), dp[i + 2] + abs(h[i] - h[i + 2]));
	}
	cout << dp[0];
}

Measured memory_bytes: 1792