akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
using ll = long long; using ld = long double; const char nl = '\n';
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */

#include <bits/extc++.h>
namespace pbds =  __gnu_pbds;
template <typename key, typename val=pbds::null_type, typename comp=less<key>>
using ostree=pbds::tree<key,val,comp,pbds::rb_tree_tag,pbds::tree_order_statistics_node_update>;
using vi = vector< int >; using vll = vector< ll >;
#define all(x) std::begin(x), std::end(x)
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&);
string to_string(string const&s){return '"'+s+'"';}
string to_string(char const &c) {return to_string(string(1,c));}
string to_string(char const *c) {return to_string(string(c));}
string to_string(bool const &b) {return (b ? "1" : "0");}
template<typename... Args> string to_string(pair<Args...> const&p)
{return "("+to_string(p.first)+", "+to_string(p.second)+")";}
template <typename...Args, template<typename...> typename T> string to_string(T<Args...> const&S)
{string s = "{"; for(auto const& e: S)s+=" "+to_string(e);s+=" }"; return s;}
template<typename Tail> void debug_out(Tail t) {cerr<<" "<<to_string(t)<<" ]"<<endl;}
template<typename Head, typename... Tail> void debug_out(Head h, Tail... t)
{cerr << " " << to_string(h) << ","; debug_out(t...);}
#define pr(...) cerr<<"["<<(#__VA_ARGS__)<<"] : [", debug_out(__VA_ARGS__)
template <typename T> void dbr(T lb, T ub)
{cerr<<'{';for(auto it=lb; it!=ub; it++)cerr<<' '<<to_string(*it); cerr<<" }"<<endl;}
template<typename T, typename Comp=less<T>> bool smin(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(v, mem) ? mem = v, true : false;}
template<typename T, typename Comp=less<T>> bool smax(T &mem, T const&v, Comp const&cmp=Comp())
{return cmp(mem, v) ? mem = v, true : false;}
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */

int const C = 200100, N = C;
ll const mod = 7+(ll)1e9;
ll dp[C];
int n, a[N];

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

  fill(dp, dp+C, 0);
  cin >> n;
  for(int i=1; i<=n; i++) cin >> a[i];
  n = unique(a+1, a+1+n) - a-1;

  a[0] = 0; dp[0] = 1;
  for(int i=1; i<=n; i++) {
    int c = a[i];
    dp[c] += dp[ a[i-1] ];
    dp[c] %= mod;
  }

  cout << dp[ a[n] ] << nl;
}
/* -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- */



Measured memory_bytes: 2560
tollGates :: Int -> Int -> [Int] -> Int
tollGates n x as = min cost0 costN
    where
        gates = [if x `elem` as then 1 else 0 | x <- [0..n]]
        cost0 = sum . take x $ gates
        costN = sum . drop (x + 1) $ gates

main :: IO ()
main = problemBDo

problemBDo = do
    [n,_,x] <- map read . words <$> getLine
    as <- map read . words <$> getLine
    putStrLn . show $ tollGates n x as

Measured memory_bytes: 892
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }
void Taka() { cout << "Takahashi" << endl; }
void Aoki() { cout << "Aoki" << endl; }
void digit(int d) { cout << fixed << setprecision(d); }
void IOup() { cin.tie(0); ios::sync_with_stdio(false); }

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 << "Right" << endl;
	}
	else {
		cout << "Balanced" << endl;
	}

	return 0;
}

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

Measured memory_bytes: 256
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for paint_h in range(2**h): #すべての行の塗りつぶし方を2進数で列挙する
    for paint_w in range(2**w): #すべての列の塗りつぶし方を2進数で列挙する
        cnt=0
        for i in range(h): #すべてのi行目j列目の要素についてみる
            for j in range(w):
                if (paint_h>>i)&1==0 and (paint_w>>j)&1==0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
                    if board[i][j]=='#': #塗りつぶされないマスが黒マスであれば個数を+1する
                        cnt+=1
        if cnt==k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
            ans+=1
print(ans)

Measured memory_bytes: 9112
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n = ni()
    d, x = nm()
    a = [ni() for _ in range(n)]

    ans = 0
    for i in range(n):
        ans += (d - 1) // a[i] + 1

    print(ans + x)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
    string s,t;cin >> s >> t;
    int n = s.size(),m = t.size();
    vector<string> kouho;
    auto check = [&](int x){
        if(x + m > n)return;
        string ret;
        rep(i,x){
            if(s[i] == '?')ret += 'a';
            else ret += s[i];
        }
        for(int i = x;i < x+m;i++){
            //s[i],t[i-x]
            if(s[i] == '?'){
                ret += t[i-x];
            }
            else if(s[i] == t[i-x]){
                ret += s[i];
            }
            else return;
        }
        for(int i = x+m;i < n;i++){
            if(s[i] == '?')ret += 'a';
            else ret += s[i];
        }
        kouho.push_back(ret);

    };
    rep(i,n)check(i);
    
    if(kouho.size() == 0){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    sort(kouho.begin(),kouho.end());
    cout << kouho[0] << endl;   
    return 0;
}

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

typedef long long ll;

int n;
ll t;
ll a[100010];

ll rmax[100010];

ll INF = 1e18;
int main()
{
	cin >> n >> t;
	
	for(int i = 0;i < n;i++)
	{
		cin >> a[i];
	}

	for(int i = n - 1;i >= 0;i--)
	{
		rmax[i] = max(rmax[i + 1],a[i]);
	}

	int MAX = 0;
	int cou = 0;
	for(int i = n - 1;i >= 0;i--)
	{
		int dif = rmax[i] - a[i];
		//cout << dif << endl;
		if(MAX < dif)
		{
			MAX = dif;
			cou = 1;
		}
		else if(MAX == dif)
		{
			cou++;
		}
		//cout << cou << endl;
	}
	cout << cou << endl;
	return 0;



}


Measured memory_bytes: 1792
#include<cstdio>
#include<cmath>
using namespace std;
int a[1000005],sum[1000005];
int gcdd(int x,int y){
	int z;
	while(y){
		z=x;
		x=y;
		y=z%y;
	}
	return x;
}
int main(){
	int n,now,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	now=a[1];
	for(i=2;i<=n;i++){
		now=gcdd(now,a[i]);
	}
	if(now==1){
		int j;
		for(i=1;i<=n;i++){
			int x=a[i];
			for(j=2;j<=sqrt(a[i]);j++){
				int noww=0;
				while(x%j==0){
					noww++;
					x/=j;
				}
				if(sum[j]&&noww){
					printf("setwise coprime");
					return 0;
				}
				sum[j]+=noww;
			}
			if(x!=1){
				if(sum[x]){
					printf("setwise coprime");
					return 0;
				}
				sum[x]=1;
			}
		}
	}
	else{
		printf("not coprime");
		return 0;
	}
	printf("pairwise coprime");
	return 0;
}

Measured memory_bytes: 6360
import java.util.Scanner;
class Main{
    int h,m,s,S;
    public void solve(){
        Scanner sc = new Scanner(System.in);
        S = sc.nextInt();
        h = S / 3600;
        m = (S - h * 3600) / 60;
        s = S - (h * 3600 + m * 60);
        System.out.println(h + ":" + m + ":" + s);
    }
    public static void main(String[] args){
        new Main().solve();     
    }
 
}

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

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

  string Line = "";
  cin >> Line;

  int l, r;
  l = 0, r = N-1;
  int cnt = 0;
  bool f = true;
  while(l <= r && f){
    for(int i = l; i <= r; ++i){
      if(Line.at(i) == 'W') {
        l = i;
        break;
      }
      if(i == r){
        l = i;
        f = false;
      }
    }
    for(int i = r; i >= l; --i){
      if(Line.at(i) == 'R') {
        r = i;
        break;
      }
      if(i == l){
        r = i;
        f = false;
      }
    }
    if(l < r) {
      cnt++;
      l++; r--;
    }
  }

  cout << cnt << endl;  
}


Measured memory_bytes: 3728
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 4003, MOD = 998244353;
int k, n, C[N][N];

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

void sub(int & x, int y) {
	x -= y;
	if (x < 0) x += MOD;
}

int ways(int l, int s) {
	if (l == 0 || s < 0) return 0;
	return C[s + l - 1][l - 1];
}

int get(int l, int s, int p) {
	int res = 0;
	for (int i = 0; i <= p; i++) {
		if (i & 1)
			sub(res, (ll)C[p][i] * ways(l, s - 2 * i) % MOD);
		else
			add(res, (ll)C[p][i] * ways(l, s - 2 * i) % MOD);
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	C[0][0] = 1;
	for (int i = 1; i < N; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
		}
	}
	cin >> k >> n;
	for (int i = 2; i <= 2 * k; i++) {
		int pairs = 0, res = 0;
		for (int j = 1; j <= k; j++) {
			if (i - j > k) continue;
			if (i - j <= j) break;
			pairs++;
		}
		if (i & 1)
			add(res, get(k, n, pairs));
		else {
			add(res, get(k - 1, n, pairs));
			add(res, get(k - 1, n - 1, pairs));
		}
		cout << res << '\n';
	}
}


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

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

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

typedef tuple<int32,int32,int64> edge;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int32 n,m;
  cin >> n >> m;
  vector<edge> edges;
  REP(i,m){
    int32 a,b,c;
    cin >> a >> b >> c;
    --a;--b;
    edges.emplace_back(a,b,-c);
  }

  vector<int64> dist(n,llinf);
  dist[0] = 0;
  REP(i,n-1){
    for(auto [a,b,c] : edges){
      if(dist[a] != llinf && dist[b] > dist[a] + c){
        dist[b] = dist[a] + c;
      }
    }
  }
  REP(i,n-1){
    for(auto [a,b,c] : edges){
      if(dist[a] != llinf && dist[b] > dist[a] + c){
        dist[b] = -llinf;
      }
    }
  }
  if(dist[n-1] == -llinf){
    ANS("inf");
  }else{
    ANS(-dist[n-1]);
  }
  return 0;
}

Measured memory_bytes: 3712
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(a,b) memset(a,b,sizeof(a))
#define msn(a,n,b) for(int i=0;i<=n;i++)a[i]=b
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define fi first
#define se second
using namespace std;
mt19937 rng_32(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef double db;
const int mod=1e9+7;
const int seed=233;
const double PI=acos(-1.0);
const double eps=1e-7;
const int inf=0x3f3f3f3f;
const int max_n=2005;
ll ceil(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?(x+y-1)/y:-x/y;}
ll floor(ll x,ll y){if(x==0)return 0;if(y<0)x=-x,y=-y;bool sign=x>0;x=abs(x);return sign?x/y:-(x+y-1)/y;}
namespace {
    inline int Add(int x,int y){return (x+=y)>=mod?x-mod:x;}
    inline int Sub(int x,int y){return (x-=y)<0?x+mod:x;}
    inline int Mul(int x,int y) {return 1ll*x*y%mod;}
    inline int Pow(int x,int y=mod-2){if(y==0)return 1;int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
}
/**********************head************************/
typedef pair<int,int>  P;
int n, a[max_n];
P p[max_n];
ll dp[max_n][max_n];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &p[i].fi), p[i].se = i;
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n + 1; i++) {
        for(int j = i; j <= n + 1; j++) dp[i][j] = -1;
    }
    for(int i = 1; i <= n + 1; i++) dp[i][i] = 0;
    for(int len = 0; len < n; len++) {
        for(int i = 1; i + len - 1 <= n; i++) {
            int j = i + len;
            if(dp[i][j] == -1) continue;
            if(j + 1 <= n + 1)dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1ll * p[len + 1].fi * abs(p[len + 1].se - j));
            if(i)dp[i - 1][j] = max(dp[i - 1][j], dp[i][j] + 1ll * p[len + 1].fi * abs(p[len + 1].se - i + 1));
        }
    }
    printf("%lld\n",dp[1][n + 1]);
    return 0;
}

Measured memory_bytes: 26424
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>

using namespace std;
//author_name:
//date://
//title:
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define eb emplace_back
#define mp make_pair
//ÒòÎªÇÓÅ³£¬ËùÒÔÌÓ±ÜÉúÃü£¬ÒÔ²»µÖ¿¹ÔÚ×îºÚ°µµÄ³ÁÂÙÖÐÉú³ö½¾°Á£¬ÒòÎª½¾°Á£¬ËùÒÔ²»Ñ¡ÔñÉú£¬ËùÒÔ¾Ü³â´Ö±ÉµÄÀÖ¹ÛÖ÷Òå¡£
//Ìì²ÅµÄ±¯¾çµØÓÚ±»Ð¡¶øÊæÊÊµÄÃûÍûËùÊø¸¿¡£
//It's human to lie. Most of the time we can't even be honest with ourselves.
typedef long long ll;
typedef pair<int,int> pii;

int a[100010],b[100010];
int n,x;
const int boun=2e5+10;
const int trans=1e5+1; 
int bit[boun+1];
int lim=-1;

inline int sum(int i){
	int res=0;
	while(i>0){
		res+=bit[i];
		i-=i&-i;
	}
	return res;
}

inline void add(int i,int val){
	while(i<=boun){
		bit[i]+=val;
		i+=i&-i;
	}
	return;
}

inline int check(int val){
	memset(bit,0,sizeof bit);
	ll tot=0;
	add(trans,1);
	for(int i=0;i<n;i++){
		b[i]=a[i]<val?-1:1;
		if(i) b[i]+=b[i-1];
		tot+=sum(b[i]+trans);
		add(b[i]+trans,1);
	}
	return tot>=(ll) n*(n+1)/4;
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		lim=max(lim,a[i]);
	}
	int low=0,high=lim+1,m;
	while(high-low>1){
		m=(low+high)>>1;
		if(check(m))
			low=m;
		else high=m;
	}
	printf("%d\n",low);
	return 0;
}

Measured memory_bytes: 1792
x1, y1, x2, y2 = map(int, raw_input().split())
vx = - x1 + x2
vy = - y1 + y2
ux = - vy
uy = vx
x3 = x2 + ux
y3 = y2 + uy
x4 = x3 - vx
y4 = y3 - vy

print x3, y3, x4, y4


Measured memory_bytes: 2568
#include <stdio.h>

int main(void)
{
	int S,h,m,s;
	scanf("%d",&S);
	h = S / 3600;
	m = (S % 3600) / 60;
	s = S % 60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

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

int main() {
	int N, Q;
	cin >> N >> Q;
	string s;
	cin >> s;
	vector<int> ans(N, 0);
	rep(i, N - 1) {
		if (s[i] == 'A' && s[i + 1] == 'C') {
			ans[i + 1]++;
		}
	}
	
	rep(i,N){
		if(i>0){
			ans[i] += ans[i-1];
		}
	}
	
	rep(i,Q) {
		int l, r;
		cin >> l >> r;
		r--;
		l--;
		cout << ans[r] - ans[l] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1408
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>
#include <bitset>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

double EPS = 1e-10;

double add(double a, double b){
	if(abs(a + b) < EPS * (abs(a) + abs(b))){
		return 0;
	}
	return a + b;
}

struct Pd{
	double x, y;
	Pd(){}
	Pd(double x, double y) : x(x), y(y){}
	Pd operator + (Pd p){
		return Pd(add(x, p.x), add(y, p.y));
	}
	Pd operator - (Pd p){
		return Pd(add(x, -p.x), add(y, -p.y));
	}
	Pd operator * (double d){
		return Pd(x * d, y * d);
	}
	double dot(Pd p){
		return add(x * p.x, y * p.y);
	}
	double det(Pd p){
		return add(x * p.y, -y * p.x);
	}
	static double norm(Pd p){
		return p.x * p.x + p.y * p.y;
	}
};

pair<Pd, double> min_ball(vector<Pd> ps) {
    const int n = ps.size();
 
    //assert(n >= 1); // n < 1 の場合、エラーメッセージを出力して異常終了
    if (n == 1) {
        return {ps[0], 0.0};
    }

    using circle = pair<Pd, double>;
 
    auto make_circle_3 = [](Pd a, Pd b, Pd c) -> circle {
        double A = Pd::norm(b - c), B = Pd::norm(c - a), C = Pd::norm(a - b), S = Pd(b - a).det(c - a);
        Pd p = (a * A * (B + C - A) + b * B * (C + A - B) + c * C * (A + B - C)) * (1.0 / (4 * S * S));
        double r2 = Pd::norm(p - a);
        return {p, r2};
    };
 
    auto make_circle_2 = [](Pd a, Pd b) -> circle {
        Pd c = (a + b) * 0.5;
        double r2 = Pd::norm(a - c);
        return {c, r2};
    };
 
    auto in_circle = [](Pd a, circle c) -> bool {
        return Pd::norm(a - c.first) <= c.second + EPS;
    };

    circle c = make_circle_2(ps[0], ps[1]);

    for (int i = 2; i < n; ++i) {
        if (!in_circle(ps[i], c)) {
            c = make_circle_2(ps[0], ps[i]);
            for (int j = 1; j < i; ++j) {
                if (!in_circle(ps[j], c)) {
                    c = make_circle_2(ps[i], ps[j]);
                    for (int k = 0; k < j; ++k) {
                        if (!in_circle(ps[k], c)) {
                            c = make_circle_3(ps[i], ps[j], ps[k]);
                        }
                    }
                }
            }
        }
    }
    return c;
}

int main(){
	int N;
	cin >> N;
	vector<Pd> v;
	for(int i = 0; i < N; i++){
		Pd p = Pd();
		cin >> p.x >> p.y;
		v.push_back(p);
	}
	printf("%.15f\n", sqrt(min_ball(v).second));
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
public class Main {
	final Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		new Main();
	}
	Main(){
		new AOJ1266();
	}
	
	class AOJ1266{
		int N;
		final double EPS=1.0e-8;
		AOJ1266(){
			while(true){
				N=sc.nextInt();
				if(N==0)	break;
				solve();
			}
		}
		class Point3D{
			double x,y,z;
			Point3D(double x,double y,double z){
				this.x=x;	this.y=y;	this.z=z;
			}
		}
		double dot3D(Point3D a,Point3D b){
			return a.x*b.x + a.y*b.y + a.z*b.z;
		}
		double norm3D(Point3D a){
			return a.x*a.x + a.y*a.y + a.z*a.z;
		}
		double abs3D(Point3D a){
			return Math.sqrt(norm3D(a));
		}
		double angleR3D(Point3D a,Point3D b){
			return Math.acos(dot3D(a,b) / (abs3D(a)*abs3D(b)));
		}
		void solve(){
			Point3D[] stars=new Point3D[N];
			for(int i=0; i<N; ++i)	stars[i]=new Point3D(sc.nextDouble(), sc.nextDouble(), sc.nextDouble());
			int M=sc.nextInt();
			Point3D[] scopes=new Point3D[M];
			double[] vs=new double[M];
			for(int i=0; i<M; ++i){
				scopes[i] = new Point3D(sc.nextDouble(), sc.nextDouble(), sc.nextDouble());
				vs[i]=sc.nextDouble();
			}
			HashSet<Integer> ans=new HashSet<Integer>();
			for(int i=0; i<M; ++i){
				for(int j=0; j<N; ++j){
					if(vs[i]+EPS > angleR3D(scopes[i], stars[j]))	ans.add(j);
				}
			}
			System.out.println(ans.size());
		}
	}
}

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

#define ll long long
#define F first
#define S second

const int mod = 1000000007;
const int M = 100005;



int main() {
	int T = 1;
	// cin>>T;
	while(T--)
	{
		int n;	cin>>n;
		int W;	cin>>W;
	
		vector<int> wt(n+1);
		vector<int> val(n+1);
		
		ll dp[n+1][W+1];
		
		for(int i=1; i<=n; i++)	cin>>wt[i]>>val[i];
		
		for(int i=0; i<=n; i++)
		{
			for(int j=0; j<=W; j++)
			{
				if(i==0 || j==0)
					dp[i][j] = 0;
				if(i>0 && j>0)
				{
					dp[i][j] = dp[i-1][j];
					if(j-wt[i]>=0)	dp[i][j] = max(dp[i][j] , dp[i-1][j-wt[i]]+val[i]);
				}
				
			}
		}
		cout<<dp[n][W];
	}
	return 0;
}

Measured memory_bytes: 79104
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){

    int N;
    cin >> N;
    ll T[N], A[N];
    REP(i,N) cin >> T[i] >> A[i];

    ll t=1, a=1;

    REP(i,N){
        ll n1,n2;
        if(t%T[i] != 0) n1 = t/T[i]+1;
        else n1 = t/T[i];
        if(a%A[i] != 0) n2 = a/A[i]+1;
        else n2 = a/A[i];
        ll n = max(n1,n2);
        t = n*T[i]; a = n*A[i];
    }

    cout << t+a << endl;

    return 0;
}

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

int main()
{
	int a,b,c,d,sum=0;
	string s;

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(string S){
	ll cnt = 0;
	vector<ll> res(S.length());
	rep(i, S.length()) {
		cnt++;
		if (S[i] == 'R' && S[i+1] == 'L') {
			res[i] += cnt/2+cnt%2;
			res[i+1] += cnt/2;
			cnt = 0;
		}
		if (i == S.length()-1 || (S[i] == 'L' && S[i+1] == 'R')) {
			res[i-cnt+1] += cnt/2+cnt%2;
			res[i-cnt] += cnt/2;
			cnt = 0;
		}
	}
	rep(i, S.length()-1) {
		cout << res[i] << " ";
	}
	cout << res[S.length()-1] << endl;
}

int main(){	
	string S;
	cin >> S;
	solve(S);
	return 0;
}



Measured memory_bytes: 1408
N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for i in range(N)]

ans = - (10**7)*N
for i in range(1, 2**10):
    tmp = 0
    for j in range(N):
        count = 0
        for k in range(10):
            if F[j][k] == 1 and (i >> k) % 2 == 1:
                count += 1
        tmp += P[j][count]

    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewScanner(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	r.Buffer(make([]byte, 0), 1000000001*3)
	r.Scan()
	s := r.Text()

	counts := make([]int, len(s))
	tmp := 0
	for i := len(s) - 1; i >= 0; i-- {
		if string(s[i]) == ">" {
			tmp++
		} else {
			tmp = 0
		}
		counts[i] = tmp
	}

	total := 0
	tmp = 0
	last := ""
	for i, l := range s {
		if string(l) == "<" {
			if last == ">" {
				tmp = 0
			}
			total += tmp
			// fmt.Print(tmp, "<")
			tmp++
			last = "<"
		} else {
			if !((last == "<") && (tmp > counts[i])) {
				tmp = counts[i]
			}
			total += tmp
			// fmt.Print(tmp, ">")
			tmp--
			last = ">"
		}
	}
	total += tmp
	// fmt.Print(tmp)
	fmt.Fprint(w, total)
}


Measured memory_bytes: 7460
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC return 0;
using namespace std;
long long a, b, x, n, res;
int main() {
    DAU
    cin >> a >> b >> n;
    x = min(b - 1, n);
    res = (a * x) / b;
    cout << res;
    PLEC
}


Measured memory_bytes: 3640
//AtCoder ABC076 C - Dubious Document 2
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

int main() {
    string Sd,T;
    cin>>Sd>>T;
    auto check_func = [&](ll p){
        bool ret = true;
        for(ll i=0;i<T.size();++i){
            auto sp=p+i;
            if(Sd[sp]=='?'||Sd[sp]==T[i]){
            } else {
                ret=false;
                break;
            }
        }
        return ret;
    };
    string ans=Sd;
    for(ll p=Sd.size()-T.size();p>=0;--p){
        if (check_func(p)){
            ans.replace(p,T.size(),T);
            for (auto&& s:ans){
                if (s=='?') {s='a';}
            }
            cout<<ans<<endl;
            return 0; //終わり
        }
    }
    cout<<"UNRESTORABLE"<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int r = scan.nextInt();
		if(n >= 10) System.out.println(r);
		else System.out.println(r+100*(10-n));
	}

}


Measured memory_bytes: 21972
#include <iostream>
#include <vector>
using namespace std;
const int MAX_NK = 410;
const int INF = 1 << 20;
struct edge{
  int to;
  int cap;
  int cost;
  int rev;
  edge(){};
  edge(int to, int cap, int cost, int rev):to(to),cap(cap),cost(cost),rev(rev){
  }
};

int V;
vector<edge> G[MAX_NK];
int dist[MAX_NK];
int prevv[MAX_NK];
int preve[MAX_NK];

void add_edge(int from, int to, int cap, int cost){
  G[from].push_back(edge(to, cap, cost, G[to].size()));
  G[to].push_back(edge(from, 0, -cost, G[from].size() -1));
}

int min_cost_flow(int s, int t, int f, int K){
  int res = 0;
  int use_cost = 0;
  
  while (f > 0){
    fill(dist, dist + V, INF);
    dist[s] = 0;
    bool update = true;
    while (update){
      update = false;
      for (int v = 0; v < V; v++){
	if (dist[v] == INF)continue;
	for (int i = 0; i < G[v].size(); i++){
	  edge &e = G[v][i];
	  if (e.cap > 0 and dist[e.to] > dist[v] + e.cost){
	    dist[e.to] = dist[v] + e.cost;
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    update = true;
	  }
	}
      }
    }

    //cout << dist[t] << " " << (K - use_cost) << endl;
    if (dist[t] >= INF || (K - use_cost) < dist[t]){
      return f;
    }
    
    int d = f;
    for (int v = t; v != s; v = prevv[v]){
      d = min(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * dist[t];
    
    for (int v = t; v != s; v = prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
      use_cost += e.cost;
    }
  }
  
  return f;
}

int A,B,K;
vector<string> RA,RB;
int main(){
  cin >> A >> B >> K;
  V = A + B + 2;
  string tmp;

  for (int i = 0; i < A; i++){
    cin >> tmp;
    RA.push_back(tmp);
  }
  for (int i = 0; i < B; i++){
    cin >> tmp;
    RB.push_back(tmp);
  }

  for (int i = 0; i < A; i++){
    for (int j = 0; j < B; j++){
      int AB = RA[i][j] - '0';
      int BA = RB[j][i] - '0';

      if ((AB & BA) == 1){//1 1
	add_edge(i + 1, A + 1 + j, 1, 2);
	//cout << i << " " << j << " " << 2 << endl;
      }else if ((AB ^ BA) == 1){//0 1 1 0
	add_edge(i + 1, A + 1 + j, 1, 1);
	//cout << i << " " << j << " " << 1 << endl;	
      }else{//0 0
	add_edge(i + 1, A + 1 + j, 1, 0);
	//cout << i << " " << j << " " << 0 << endl;		
      }
    }
  }
  for (int i = 0; i < A; i++){//src A
    add_edge(0, i + 1, 1, 0);
  }
  for (int j = 0; j < B; j++){//B tar
    add_edge(A + 1 + j, A + B + 1, 1, 0);
  }
 
  //  cout << "hoge" << endl;

  int res = min_cost_flow(0, A + B + 1, (A + B), K);
  
  cout << (A + B - res) << endl;  
}

Measured memory_bytes: 2856
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  set<char> s;
  char a;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    s.insert(a);
  }
  if(s.size()==3) cout<<"Three";
  else cout<<"Four";
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <string>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int mod = 1000000007;

vector<int> e[maxn];
int n;
int fa[maxn];
void dfs(int x,int y){
  fa[x] = y;
  for(int i=0;i<e[x].size();i++){
    int v = e[x][i];
    if(v==y)continue;
    dfs(v, x);
  }
}
int mx;
void dfs2(int x, int y, int d){
  mx = max(mx, d);
  for(int i=0;i<e[x].size();i++){
    int v = e[x][i];
    if(v==y)continue;
    dfs2(v, x, d+1);
  }
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  cin>>n;
  int s,t;
  cin>>s>>t;
  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs(t, 0);
  vector<int>path;
  int cur = s;
  while(cur){
    path.push_back(cur);
    cur = fa[cur];
  }
  int node = (path.size() - 2)/2;
  mx = 0;
  dfs2(path[node], fa[path[node]], 1);
  int all = path.size() - node  - 1 + mx;
  cout<<all - 2<<endl;
  return 0;
}

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

typedef long long ll;
const int inf = 1e9;

int n;

int main(){
	cin>>n;
	vector<string> vec(n);
	vector<int> ans(4, 0);
	for(int i = 0; i < n; ++i)cin>>vec[i];
	for(int i = 0; i < n; ++i){
		if(vec[i]=="AC")ans[0]++;
		if(vec[i]=="WA")ans[1]++;
		if(vec[i]=="TLE")ans[2]++;
		if(vec[i]=="RE")ans[3]++;
	}
	for(int i = 0; i < 4; ++i){
		if(i == 0)cout<<"AC x "<<ans[0]<<endl;
		if(i == 1)cout<<"WA x "<<ans[1]<<endl;
		if(i == 2)cout<<"TLE x "<<ans[2]<<endl;
		if(i == 3)cout<<"RE x "<<ans[3]<<endl;
	}
	
	return 0;
}


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

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

  if( c == 'a' || c=='i' || c=='u' || c=='e' || c=='o'){
    cout << "vowel" <<endl;
  }else{
  cout << "consonant"<< endl;
  }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST_INPUT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long

using namespace std;

const int mod = 1e9 + 7;


void add_self(int& a, int b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	}
}

int mul(int a, int b) {
	return (ll) a * b % mod;
}

int n;

struct matrix {
	vector<vector<int>> t;

	matrix() {
		t.resize(n, vector<int>(n));
	}

	matrix operator* (const matrix& b) {
		matrix c = {};
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				for (int k=0; k<n; k++) {
					add_self(c.t[i][k], mul(t[i][j], b.t[j][k]));
				}
			}
		}
		return c;
	}
};

void solve() {
	ll k;
	cin >> n >> k;
	vector<vector<int>> can(n, vector<int>(n));
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			cin >> can[i][j];
		}
	}

	matrix ans = {};
	for (int i=0; i<n; i++) {
		ans.t[i][i] = 1;
	}
	matrix m = {};
	m.t = can;

	while (k) {
		if (k % 2) {
			ans = ans * m;
		}
		m = m * m;
		k /= 2;
	}

	int res = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			add_self(res, ans.t[i][j]);
		}
	}

	cout << res << endl;

	// vector<int> dp(n, 1);
	// for (int step=0; step<k; step++) {
	// 	vector<int> dp2(n);
	// 	for (int u=0; u<n; u++) {
	// 		for (int v=0; v<n; v++) {
	// 			if (can[u][v]) {
	// 				add_self(dp2[v], dp[u]);
	// 			}
	// 		}
	// 	}
	// 	dp = dp2;
	// }

	// int ans = 0;
	// for (int i=0; i<n; i++) {
	// 	add_self(ans, dp[i]);
	// }

	// cout << ans << endl;
}

int main() {
    FAST_INPUT;

    solve();

    return 0;
}


Measured memory_bytes: 3688
#include <stdio.h>
struct dice{
    int d[6], tmp[6];
};
struct dice dice1;
void init(int n[6]){
    int i;
    for (i=0;i<6;i++){
        dice1.d[i]=n[i];
    }
}
void throwdice(char c){
    int i;
    for(i=0;i<6;i++){
        dice1.tmp[i]=dice1.d[i];
    }
    if(c=='N'){
        dice1.d[0]=dice1.tmp[1];
        dice1.d[1]=dice1.tmp[5];
        dice1.d[2]=dice1.tmp[2];
        dice1.d[3]=dice1.tmp[3];
        dice1.d[4]=dice1.tmp[0];
        dice1.d[5]=dice1.tmp[4];
    }
    else if(c=='E'){
        dice1.d[0]=dice1.tmp[3];
        dice1.d[1]=dice1.tmp[1];
        dice1.d[2]=dice1.tmp[0];
        dice1.d[3]=dice1.tmp[5];
        dice1.d[4]=dice1.tmp[4];
        dice1.d[5]=dice1.tmp[2];
    }
    else if(c=='W'){
        dice1.d[0]=dice1.tmp[2];
        dice1.d[1]=dice1.tmp[1];
        dice1.d[2]=dice1.tmp[5];
        dice1.d[3]=dice1.tmp[0];
        dice1.d[4]=dice1.tmp[4];
        dice1.d[5]=dice1.tmp[3];
    }
    else if(c=='S'){
        dice1.d[0]=dice1.tmp[4];
        dice1.d[1]=dice1.tmp[0];
        dice1.d[2]=dice1.tmp[2];
        dice1.d[3]=dice1.tmp[3];
        dice1.d[4]=dice1.tmp[5];
        dice1.d[5]=dice1.tmp[1];
    }
    else if(c=='R'){
        dice1.d[0]=dice1.tmp[0];
        dice1.d[1]=dice1.tmp[3];
        dice1.d[2]=dice1.tmp[1];
        dice1.d[3]=dice1.tmp[4];
        dice1.d[4]=dice1.tmp[2];
        dice1.d[5]=dice1.tmp[5];
    }
}
int main()
{
    int q;
    int n[6];
    int i,j;
    char t[110];
    int ts;
    for(i=0;i<6;i++){
        scanf("%d",&n[i]);
    }
    init(n);
    scanf("%s",&t);
    ts=strlen(t);
    for(i=0;i<ts;i++){
        throwdice(t[i]);    
    }
    printf("%d\n",dice1.d[0]);
    return 0;
}


Measured memory_bytes: 2096
#include<cstdio>
#include<vector>
const long long mod = 1e9+7;
std::vector<int>g[5005];
long long count[5005];
int vis[5005];
long long f[5005][5005][2];
long long keep[5005][2];

void modAdd(long long&a,long long b){
    a += b;
    if(a>=mod) a -= mod;
}

void dp(int u){
    vis[u] = 1;
    f[u][1][0] = 1;
    for(int t = 0; t < (int)g[u].size(); t++){
        int v = g[u][t];
        if(vis[v]==0){
            dp(v);
            for(int i = 1; i <= vis[u]; i++){
                keep[i][0] = f[u][i][0], keep[i][1] = f[u][i][1];
                f[u][i][0] = f[u][i][1] = 0;
            }
            for(int i = 1; i <= vis[v]; i++){
                for(int j = 1; j <= vis[u]; j++){
                    //remove edge
                    f[u][j][1] += f[v][i][0]*keep[j][0]%mod*count[i]%mod; if(f[u][j][1]>=mod) f[u][j][1] -= mod;
                    f[u][j][0] += f[v][i][0]*keep[j][1]%mod*count[i]%mod; if(f[u][j][0]>=mod) f[u][j][0] -= mod;
                    f[u][j][0] += f[v][i][1]*keep[j][0]%mod*count[i]%mod; if(f[u][j][0]>=mod) f[u][j][0] -= mod;
                    f[u][j][1] += f[v][i][1]*keep[j][1]%mod*count[i]%mod; if(f[u][j][1]>=mod) f[u][j][1] -= mod;
                    //haven't remove
                    f[u][i+j][0] += f[v][i][0]*keep[j][0]%mod; if(f[u][i+j][0]>=mod) f[u][i+j][0] -= mod;
                    f[u][i+j][1] += f[v][i][0]*keep[j][1]%mod; if(f[u][i+j][1]>=mod) f[u][i+j][1] -= mod;
                    f[u][i+j][1] += f[v][i][1]*keep[j][0]%mod; if(f[u][i+j][1]>=mod) f[u][i+j][1] -= mod;
                    f[u][i+j][0] += f[v][i][1]*keep[j][1]%mod; if(f[u][i+j][0]>=mod) f[u][i+j][0] -= mod;
                }
            }
            vis[u] += vis[v];
        }
    }
}

int main(){
    count[0] = 1;
    for(int i = 1; i <= 5000; i++){
        if(i%2) count[i] = 0;
        else count[i] = count[i-2]*(long long)(i-1)%mod;
    } 
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n-1; i++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dp(1);
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans += f[1][i][0]*count[i]%mod;
        if(ans>=mod) ans -= mod;
        ans -= f[1][i][1]*count[i]%mod;
        if(ans<0) ans += mod;
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 160496
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
#define llMAX 9223372036854775807
#define llMIN -9223372036854775808
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,k,x,y;

int main(){
  ll ans=0;
  string s;
  cin >> s;
  int flag=0;
  if (s[2]==s[3])flag++;
  if (s[4]==s[5])flag++;
  if (flag==2){
    cout<<"Yes"<<endl;
    return 0;
  }else{
    cout<<"No"<<endl;
    return 0;
  }
  return 0;
}


/*


#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
#define llMAX 9223372036854775807
#define llMIN -9223372036854775808
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll x;

int main(){
  ll ans=0;
  cin >> x;
  ll x500=x/500;
  ll x5=(x-x500*500)/5;
  ans=x500*1000+x5+5;
  cout<<ans<<endl;
  return 0;
}
*/

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

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl ;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;

const int OO = (int) 2e9;
const double eps = 1e-9;

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
//	freopen("in.txt", "rt", stdin);
//	freopen("out.txt", "wt", stdout);
#endif
	int n, x, cnt = 0;
	cin >> n;
	for (int i = 0 ;i < n; i++) {
		cin >> x;
		if (x & 1)
			cnt++;
	}
	(cnt & 1) ? puts("NO") : puts("YES");
	return 0;
}


Measured memory_bytes: 256
import numpy as np
N = int(input())
V = np.array([int(v) for v in input().split()])
Vs = np.sort(V)
v = (Vs[0] + Vs[1]) / 2.0
for i in range(2, len(Vs - 1)):
    v = (v + Vs[i]) / 2.0
print(v)


Measured memory_bytes: 12408
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

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

  int n;
  cin >> n;
  int cnt = 0;
  for(int i = 1; i <= n; i += 2) cnt++;
	cout << (ld) cnt / n;
}

Measured memory_bytes: 256
c=0
while True:
    n=input()
    if n==0:
        break
    c+=1
    x0, y0=map(int,raw_input().split())
    prev_x, prev_y=x0, y0
    tmp=0
    for i in range(n-1):
        x,y=map(int,raw_input().split())
        tmp+=prev_x*y - prev_y*x
        prev_x, prev_y=x, y
    tmp+=prev_x*y0 - prev_y*x0
    print c, 0.5*abs(tmp)
    skip=raw_input()
    
   

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

int main() {
  
  int N; cin >> N; vector<int> vec(N);
  
  for (int i = 0; i < N; i++) cin >> vec.at(i);
  
  sort(vec.begin(), vec.end());
  
  cout << vec.back() - vec.front() << endl;
  
}

Measured memory_bytes: 256
import math


def solve(stns, n, idx, dp):
    for i in range(n):
        for j in range(1, 3):
            j = i + j # step i + 1, i + 2
            if j < n:
                # min(existing min, new path using i)
                dp[j] = min(dp[j], dp[i] + abs(stns[i] - stns[j]))
    return dp[n-1]

def take_input():
    n = int(input())
    stns = [int(x) for x in input().split()]
    dp = [math.inf for i in range(n)]
    dp[0] = 0
    res = solve(stns, n, 0, dp)
    print(res)

take_input()

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

#define Int register int
#define MAXN 100005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,a[MAXN],f[MAXN],deg[MAXN];
struct edge{
	int v,nxt;
}e[MAXN << 1];
int top = 1,head[MAXN];
void Add_Edge (int u,int v){
	e[++ top] = edge {v,head[u]};head[u] = top;
	e[++ top] = edge {u,head[v]};head[v] = top;
}

bool dfs (int u,int fa){
	if (deg[u] == 1) return f[u] = a[u],1;
	f[u] = 2 * a[u];int Maxn = 0;
	for (Int i = head[u];i;i = e[i].nxt){
		int v = e[i].v;
		if (v == fa) continue;
		if (!dfs (v,u)) return 0;
		f[u] -= f[v],Maxn = max (Maxn,f[v]);
	}
	if (0 <= f[u] && f[u] <= a[u] && Maxn <= a[u]) return 1;
	else return 0;
}

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (a[i]);
	for (Int i = 2,u,v;i <= n;++ i) read (u,v),Add_Edge (u,v),deg[u] ++,deg[v] ++;
	if (n == 2) return puts (a[1] == a[2] ? "YES" : "NO"),0;
	for (Int i = 1;i <= n;++ i) if (deg[i] > 1) return puts (dfs (i,0) && !f[i] ? "YES" : "NO"),0;
	return 0;
} 

Measured memory_bytes: 13344
from itertools import product
import numpy as np
from sys import maxsize

n = int(input())
f = np.array([[int(i) for i in input().split()] for _ in range(n)])
p = np.array([[int(i) for i in input().split()] for _ in range(n)])

res = -maxsize
for arr in product(range(2), repeat=10):
    if sum(arr) == 0:
        continue
    a = np.array(arr)
    profit = 0
    for i in range(n):
        profit += p[i][np.sum(a*f[i])]
    if profit > res:
        res = profit

print(res)


Measured memory_bytes: 14432
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, k;
  cin >> n >> k;
  int g = 0;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    g = __gcd(x, g);
    mx = max(x, mx);
  }
  if (k > mx) {
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }
  string ans;
  if (g == 1) {
    if (k <= mx) ans = "POSSIBLE";
    else ans = "IMPOSSIBLE";
  } else {
    if (k % g == 0) ans = "POSSIBLE";
    else ans = "IMPOSSIBLE";
  }
  cout << ans << endl;
  return 0;	
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int main(int argc, char *argv[]) {
	int X;
	cin >> X;
	
	int ans = 1;
	for (int i = 2; i < sqrt(X); i++)
		for (int j = i * i; j <= X; j *= i)
			ans = max(ans, j);

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

Measured memory_bytes: 256