akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
const int INF = numeric_limits<int>::max();
const ll INFL = numeric_limits<ll>::max();
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

ll factorial(ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

bool fn_is_prime(ll n) {
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return n != 1;
}

bool isOK(int index, int key, vector<ll>& a) {
    if (a[index] >= key) return true;
    else return false;
}

int binary_search(int key, vector<ll>& a) {
    int ng = -1;
    int ok = a.size();

    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key, a)) ok = mid;
        else ng = mid;
    }
    return ok;
}

struct UnionFind {
    vector<int> r;

    UnionFind(int N) {
        r = vector<int>(N, -1);
    }

    int root(int x) {
        if (r[x] < 0) return x;
        return r[x] = root(r[x]);
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (r[x] > r[y]) swap(x, y);
        r[x] += r[y];
        r[y] = x;
        return true;
    }

    int size(int x) {
        return -r[root(x)];
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }
};

ll calc(ll a, ll b, ll p) {
    if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = calc(a, b/2, p);
        return (d * d) % p;
    } else {
        return (a * calc(a, b-1, p)) % p;
    }
}
     
int main()
{
    int n, m; cin >> n >> m;
    priority_queue<ll> q;
    rep(i,n) {
        ll a; cin >> a;
        q.push(a);
    }

    ll tmp;
    rep(i,m) {
        tmp = q.top();
        q.pop();
        q.push(tmp/2);
    }
    ll ans = 0;

    while (!q.empty()) {
        tmp = q.top();
        q.pop();
        ans += tmp;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4308
import random

class dice:
    def __init__(self, t, S, E):
        self.dice = list(map(int, input().split()))
        self.t = t
        self.S = S
        self.E = E
        self.now_dice()
    
    def roll(self, order):
        if order == 'E':
            self.t, self.E = self.W, self.t
        elif order == 'N':
            self.t, self.S = self.S, self.g
        elif order == 'S':
            self.t, self.S = self.N, self.t
        elif order == 'W':
            self.t, self.E = self.E, self.g
        self.now_dice()
    
    def now_dice(self):
        self.N = 7 - self.S
        self.g = 7 - self.t
        self.W = 7 - self.E
        self.now = [self.t, self.S, self.E, self.N, self.W, self.g]
        return self.now

if __name__ == '__main__':
    num = int(input())
    dice_1 = dice(1, 2, 3)
    direc = ['N', 'E', 'W', 'S']
    x = 0
    for _ in range(num-1):
        dice_2 = dice(1, 2, 3)
        for __ in range(1200):
            random.shuffle(direc)
            dice_2.roll(direc[0])
            if [dice_1.dice[dice_1.now[v]-1] for v in range(6)] == [dice_2.dice[dice_2.now[v]-1] for v in range(6)]:
                x += 1
                break
    if x >= 1:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 8196
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

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

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int h, w;
    cin >> h >> w;
    string s[h];
    for( int i = 0; i < h; ++i ) cin >> s[i];
    for( int i = 0; i < w + 2; ++i ) cout << '#';
    cout << endl;
    for( int i = 0; i < h; ++i ) {
        cout << '#' << s[i] << '#' << endl;
    }
    for( int i = 0; i < w + 2; ++i ) cout << '#';
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <cmath>

using namespace std;
const int maxn=100000+5;
typedef long long ll;
struct point{int x,y,id;};
point p[maxn];
int n;
struct edge{int from,to,cost;};
vector<edge> pool;
int myabs(int x){return x<0?-x:x;}
bool cmppp(edge a,edge b){
	return a.cost<b.cost;
}
bool cmp1(point a,point b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
bool cmp2(point a,point b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
struct ge{int to,cost;};
struct cmpp{
	bool operator()(edge a,edge b){
		return a.cost>b.cost;
	}
};
vector<ge> g[maxn];
int f[maxn],rnk[maxn];
int getf(int x){
	return f[x]==x?f[x]:f[x]=getf(f[x]);
}
void merge(int u,int v)
{
	int fu=getf(u),fv=getf(v);
	if(fu==fv) return;
	else{
		if(rnk[fu]>rnk[fv]){
			rnk[fu]+=rnk[fv];rnk[fv]=0;
			f[fv]=fu;
		}else{
			rnk[fv]+=rnk[fu];rnk[fu]=0;
			f[fu]=fv;
		}
	}
}
vector<edge> egs;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {p[i].id=i;scanf("%d%d",&p[i].x,&p[i].y);}
	sort(p+1,p+1+n,cmp1);
	for(int i=1;i<n;i++){
		egs.push_back((edge){p[i].id,p[i+1].id,min(myabs(p[i].x-p[i+1].x),myabs(p[i].y-p[i+1].y))});
	}
	sort(p+1,p+1+n,cmp2);
	for(int i=1;i<n;i++){
		egs.push_back((edge){p[i].id,p[i+1].id,min(myabs(p[i].x-p[i+1].x),myabs(p[i].y-p[i+1].y))});
	}
	bool has=true;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++) rnk[i]=1;
	ll ans=0;
	sort(egs.begin(),egs.end(),cmppp);
	int lev=n-1;
	for(int i=0;i<egs.size();i++)
	{
		edge now=egs[i];
		if(getf(now.from)!=getf(now.to))
		{lev--;merge(now.from,now.to);ans+=now.cost;}
		if(lev==0) break;
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 8436
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

map<pair<long long, long long>, long long> map_res;

long long Get(long long a, long long b) {
	if (a == b) {
		return 1;
	}

	if (map_res.find(mp(a, b)) != map_res.end()) {
		return map_res[mp(a, b)];
	}
	
	long long res = 0;
	if (a % 2 == 0) {
		res = 2 * Get(a / 2, b / 2);
	} else {
	    res = Get(a / 2, b / 2) + Get((a + 1) / 2, b / 2);
	}

	if (((b - 1) & b) + 1 < a) {
		--res;
   	}

   	return map_res[mp(a, b)] = res;
}

int main () {
    ios_base::sync_with_stdio(0);
//	freopen("input.txt", "rt", stdin);
//	freopen("output.txt", "wt", stdout);

	long long a, b;
	cin >> a >> b;

	cout << Get(a, b) << endl;

	return 0;
}


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

using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<int> a(N);
	for (auto& x : a) {
		cin >> x;
	}

	set<int> s;
	int t = 0;
	for (auto x : a) {
		if (x < 3200) {
			s.insert(x / 400);
		}
		else {
			++t;
		}
	}

	cout << max<int>(1, s.size()) << " " << s.size() + t << endl;
}


Measured memory_bytes: 256
#include<iostream>

int gcd(int a,int b){
    int c=1;
    if(a<b){
        c=a;a=b;b=c;
    }
    while(c!=0){
        c=a%b;
        a=b;
        b=c;
    }
   return a;
}


int main(){
    
    int k,x=0;
    std::cin>>k;
    for(int s=1;s<=k;s++)
        for(int t=1;t<=k;t++)
            for(int u=1;u<=k;u++){
                x=x+gcd(gcd(s,t),u);
            }
    std::cout<<x<<std::endl;
}



Measured memory_bytes: 3600
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"
#include "map"
#include "algorithm"
#include "functional"
#include "set"
#include "numeric"
#include "unordered_map"

using namespace std;

const long long int MOD = 1000000007;

int N, M, K, H, W, L, R;

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

	cin >> N >> M;
	if (N <= 0 && M >= 0) {
		cout << "Zero" << endl;
		return 0;
	}
	if (M < 0 && (M - N) % 2 == 0) {
		cout << "Negative\n";
		return 0;
	}
	cout << "Positive\n";
	return 0;
}


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

int main()
{
    ll N, K;
    vector<ll> H;
    ll ans = 0;
    cin >> N >> K;
    for (int i = 0; i < N; ++i)
    {
        ll temp;
        cin >> temp;
        H.push_back(temp);
    }
    sort(H.begin(), H.end());
    for (int i = 0; i < N - K; ++i)
    {
        ans += H[i];
    }
    cout << ans << endl;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i,N) cin >> L[i];
    sort(L.begin(),L.end());
    ll ans=0;
    rep(i,N){
        rep2(j,i+1,N){
            ans+=lower_bound(L.begin()+j+1,L.end(),L[i]+L[j])-upper_bound(L.begin()+j+1,L.end(),abs(L[i]-L[j]));
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
a=[input() for i in range(N)]
a=[int(i) for i in a]
a=[0]+a

flg=[0]*(N+1)
count=0
i=1

while count<N:
    if i==2:
        print(count)
        quit()
    i=a[i]
    count+=1

print('-1')
quit()


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int w, h;
int mi;

void f(int field[][21], pair<int, int> cur, pair<int, int> dst, int depth) {
    if (depth > 10) return;
    for (int i = cur.fi; i >= 0; i--) {
        if (i == dst.fi and cur.se == dst.se) {
            mi = min(mi, depth);
            return;
        }
        if (i == 0) break;
        if (field[i - 1][cur.se] == 1) {
            if (i == cur.fi) {
                break;
            }
            else {               
                field[i - 1][cur.se] = 0;
                f(field, {i, cur.se}, dst, depth + 1);
                field[i - 1][cur.se] = 1;
                break;
            }
        }
    }
    for (int i = cur.fi; i < h; i++) {
        if (i == dst.fi and cur.se == dst.se) {
            mi = min(mi, depth);
            return;
        }
        if (i == h - 1) break;
        if (field[i + 1][cur.se] == 1) {
            if (i == cur.fi) {
                break;
            }
            else {               
                field[i + 1][cur.se] = 0;
                f(field, {i, cur.se}, dst, depth + 1);
                field[i + 1][cur.se] = 1;
                break;
            }
        }
    }
    for (int i = cur.se; i >= 0; i--) {
        if (cur.fi == dst.fi and i == dst.se) {
            mi = min(mi, depth);
            return;
        }
        if (i == 0) break;
        if (field[cur.fi][i - 1] == 1) {
            if (i == cur.se) {
                break;
            }
            else {                
                field[cur.fi][i - 1] = 0;
                f(field, {cur.fi, i}, dst, depth + 1);
                field[cur.fi][i - 1] = 1;
                break;
            }
        }
    }
    for (int i = cur.se; i < w; i++) {
        if (cur.fi == dst.fi and i == dst.se) {
            mi = min(mi, depth);
            return;
        }
        if (i == w - 1) break;
        if (field[cur.fi][i + 1] == 1) {
            if (i == cur.se) {
                break;
            }
            else {                
                field[cur.fi][i + 1] = 0;
                f(field, {cur.fi, i}, dst, depth + 1);
                field[cur.fi][i + 1] = 1;
                break;
            }
        }
    }
}

int main() {
    vector<int> res;
    while (true) {
        cin >> w >> h;
        if (w == 0) break;
        int field[21][21] = {};
        pair<int, int> s, g;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> field[i][j];
                if (field[i][j] == 2) {
                    s = {i, j};
                    field[i][j] = 0;
                }
                if (field[i][j] == 3) {
                    g = {i, j};
                    field[i][j] = 0;
                }
            }
        }
        mi = inf;
        f(field, s, g, 1);
        res.push_back(mi == inf ? -1 : mi);
    }
    for (int i = 0; i < (int)res.size(); i++) {
        dump(res[i]);
    }
    return 0;
}



Measured memory_bytes: 3004
#include<bits/stdc++.h>
using namespace std;
int main(){
	int k; string s;
	cin>>k>>s;
	if(s.size()<=k) cout<<s;
	else{
		for(int i=0;i<k;i++) cout<<s[i];
		cout<<"...";
	}
	return 0;
}

Measured memory_bytes: 3624
import math

EPS = 1e-10

def eq(a, b):
  return (abs(a-b) < EPS)

def eqv(a, b):
  return (eq(a.real, b.real) and eq(a.imag, b.imag))

def cross(a, b):
  return a.real * b.imag - a.imag * b.real

def is_intersected_ls(a1, a2, b1, b2):
  return (cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS) and \
         (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS)

def intersection_l(a1, a2, b1, b2):
  a = a2 - a1
  b = b2 - b1
  return a1 + a * cross(b, b1-a1) / cross(b, a)

while True:
  n = int(input())
  if n==0:
    break
  lines = []
  for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    lines.append((complex(x1, y1), complex(x2, y2)))

  ans = 2
  for i in range(1, n):
    cross_point = []
    for j in range(0, i):
      l1, l2 = lines[i], lines[j]
      if is_intersected_ls(l1[0], l1[1], l2[0], l2[1]):
        p = intersection_l(l1[0], l1[1], l2[0], l2[1])
        if -100+EPS<=p.real<=100-EPS and -100+EPS<=p.imag<=100-EPS:
          cross_point.append(p)
    cnt = min(len(cross_point), 1)
    for i in range(1, len(cross_point)):
      flag = 0
      for j in range(0, i):
        if eqv(cross_point[i], cross_point[j]):
          flag = 1
      if not flag:
        cnt+=1
    ans += 1+cnt
  
  print(ans)


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

int main(){
	int a, b, c, x, y, sum;
	cin >> a >> b >> c >> x >> y;
	sum = a * x + b * y;
	if(sum > max(x, y) * c * 2) sum = max(x, y) * c * 2;
	if(x > y) {
		if((x-y)*a + y *c * 2 < sum) sum = (x-y) * a + y * c * 2;
	}else{
		if((y-x)*b + x *c * 2 < sum) sum = (y-x)* b + x * c * 2;
	}
	cout << sum;
	return 0;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
vector<int> g[100005];
vector<int> wt[100005];
long long int dist[100005], par[100005];
bool vis[100005];
void dijsktra(int r,int N){
	priority_queue<pair<long long int, int> > q;
	for (int i = 1; i <= N; i++) dist[i] = 1e18, vis[i] = false, par[i] = i;
	dist[r] = 0;
	q.push(mp(0, r));
	while (q.size()){
		pair<int, int> t = q.top();
		q.pop();
		if (vis[t.second]) continue;
		int root = t.second;
		vis[root] = true;
		for (int i = 0; i < g[root].size(); i++){
			int x = g[root][i];
			int w = wt[root][i];
			if (dist[x] > dist[root] + w){
				dist[x] = dist[root] + w;
				par[x] = root;
				q.push(mp(-dist[x], x));
			}
		}
	}
}
int main()
{
	int u,v,a,b,n,i,w,q,s;
	scanf("%d",&n);
	for(i=0;i<n-1;i++)
	scanf("%d %d %d",&u,&v,&w),g[u].push_back(v),g[v].push_back(u),wt[u].push_back(w),wt[v].push_back(w);
	scanf("%d %d",&q,&s);
	dijsktra(s,n);
	while(q--)
	{
		scanf("%d %d",&u,&v);
		printf("%lld\n",dist[u]+dist[v]);
	}
}

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

int main() {
  long long n,a,b,c,sum,p;
  cin>>n>>a>>b;
  c=a+b;
  sum=(n/c)*a;
  p=n%c;
  if(p<=a)sum=sum+p;
  else if(p>a)sum=sum+a;
  cout<<sum<<endl;
  
  return 0;
  
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> s(N);
  while (cin >> N) ++s[N-1];
  for (auto x: s) cout << (Q-x < K ? "Yes" : "No") << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(ll i = (begin); i < (end); i++)
#define rep(i, n) FOR(i, 0, n)
using ll = long long;
using namespace std;
#define all(x) (x).begin(),(x).end()
using pii = pair<int, int>; using vi = vector<int>; using vl = vector<ll>;

signed main() {
    int n;
    cin >> n;
    vi h(n);
    rep(i, n) cin>>h[i];
    vi dp(n);
    dp[1] = abs(h[1] - h[0]);
    rep(i,n-2) {
        dp[i+2] = min(
            dp[i] + abs(h[i+2] - h[i]),
            dp[i+1] + abs(h[i+2] - h[i+1]));
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <assert.h>
#include <vector>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <unordered_set>
using namespace std;
constexpr int64_t MOD = 1e9 + 7;
constexpr int64_t INF = 1e6 + 1;

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

  int32_t N;
  cin >> N;
  int64_t res = 0;
  int64_t cur_max = 0;
  for (int i = 0; i < N; i++) {
    int64_t v;
    cin >> v;
    if (v < cur_max) {
      res += cur_max - v;
    }
    cur_max = max(cur_max, v);
  }

  cout << res << endl;
  
  return 0;
}


Measured memory_bytes: 3592
#include <stdio.h>

int main(void) {
    int team[100][2] = {{0}};
    int array[31] = {0};
    int i = 0, j, k, n, count;

    while(scanf("%d,%d",&team[i][0],&team[i][1]) ,team[i][0] != 0 ) {
        i++;
    }
    n = i;
    for(--i; i >= 0; i--) {
        array[team[i][1]] = 1;
    }
    while(scanf("%d",&k) != EOF) {
        count = 0;
        for(i = 0; i < n; i++ ) {
            if(team[i][0] == k ) {
                j = team[i][1];
                break;
            }
        }
        for(i = 31; i > j; i--) {
            if(array[i]) {
                count++;
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

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

int main() {
  int ans=0;
  vector<int> vec(5);
  rep(i,5){
    cin>>vec[i];
    ans+=(vec[i]+9)/10*10;
  }
  int cnt=ans;
  rep(i,5){
    if(vec[i]%10!=0)cnt=min(cnt,ans-10+vec[i]%10);
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 3608
/*ヽ｀、ヽ｀｀、ヽ｀ヽ｀、、ヽ ｀ヽ 、ヽ｀｀ヽヽ｀ヽ、ヽ｀
ヽ｀、ヽ｀｀、ヽ 、｀｀、 ｀、ヽ｀ 、｀ ヽ｀ヽ、ヽ ｀、ヽ｀｀、
ヽ、｀｀、｀、ヽ｀｀、 、ヽヽ｀、｀、、ヽヽ、｀｀、 、 ヽ｀、
ヽ｀｀、 ヽ｀ヽ｀、、ヽ ｀ヽ 、 ヽ｀｀｀｀ヽヽヽ｀、、ヽ｀、、ヽ*/
#include <bits/stdc++.h> 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long   ll;
typedef long double ld;
typedef complex< ld > cd;
 
typedef pair<int, int> pi;
typedef pair<ll, ll>   pl;
typedef pair<ld, ld>   pd;
 
typedef vector< int > vi;
typedef vector< ld >  vd;
typedef vector< ll >  vl;
typedef vector< pi >  vpi;
typedef vector< pl >  vpl;
typedef vector< cd >  vcd;
 
#define l00p(i, a, b) for (int i=a; i<(b); i++)
#define loop(i, a)    for (int i=0; i<(a); i++)
#define rep1(i, a, b) for (int i = (b)-1; i >= a; i--)
#define rep(i, a)     for (int i = (a)-1; i >= 0; i--)
#define trav(a, x)    for (auto& a : x)
#define uid(a, b)     uniform_int_distribution<int>(a, b)(rng)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f  first
#define s  second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
//#define MOD 998244353
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ld pii=3.14159265359; 
const int MOD = 1000000007;
const char nl = '\n';
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	  int n;
 	 cin >> n;
 	 vector<int> v(n);
 	 for(int i=0;i<n;i++){
 	   cin>>v[i];
	  }
	  sort(v.begin(),v.end());
	  double ans=v[0];
	  for(int i=0;i<n-1;i++){
	    ans=(ans+(double)v[i+1])/(double)2;
	  }
	  cout<<ans<<endl;
		return 0;
}
// read the question correctly (ll vs int)
// template by bqi343

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

int64_t M = 998244353;
vector<int64_t> fac(200001);		//n! (mod M)
vector<int64_t> ifac(200001);		//k!^{M-2} (mod M)

int64_t mpow(int64_t x, int64_t n)
{
	int64_t ans = 1;
	while (n != 0) {
		if (n & 1) {
			ans = ans * x % M;
		}
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}

int64_t comb(int64_t n, int64_t k)
{
	if (n == 0 && k == 0) {
		return 1;
	} else if (n < k || n < 0) {
		return 0;
	}
	int64_t temp = ifac.at(k) * ifac.at(n - k) % M;
	return temp * fac.at(n) % M;
}

int main()
{
	int n, m, k;
	cin >> n >> m >> k;

	fac.at(0) = 1;
	ifac.at(0) = 1;
	for (int64_t i = 0; i < n; i++) {
		fac.at(i + 1) = fac.at(i) * (i + 1) % M;
		ifac.at(i + 1) = ifac.at(i) * mpow(i + 1, M - 2) % M;
	}

	int64_t ans = 0;
	for (int i = 0; i <= k; i++) {
		int64_t temp = m;
		temp = temp * comb(n - 1, i) % M;
		temp = temp * mpow(m - 1, n - 1 - i) % M;
		ans = (ans + temp) % M;
	}

	cout << ans << endl;
}


Measured memory_bytes: 6316
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int a = int(sqrt(2 * n)), b = a + 1;
	if (a*b/2 != n)
	{
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	cout << b << endl;
	vector<int> last(a);
	for (int i = 0, p = 1; i < b; i++)
	{
		cout << a;
		for (int j1 = 0; j1 < i; j1++)
		{
			cout << " " << last[j1]++;
		}
		for (int j2 = i; j2 < a; j2++)
		{
			cout << " " << p;
			last[j2] = p++;
		}
		cout << endl;
	}
		
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
int main() {
    int n, r, s[13] = {}, h[13] = {}, c[13] = {}, d[13] = {};
    char m;
    scanf("%d%*c", &n);
    while (n--) {
        scanf("%c %d%*c", &m, &r);
        if (m == 'S') s[r-1] = 1;
        else if (m == 'H') h[r-1] = 1;
        else if (m == 'C') c[r-1] = 1;
        else d[r-1] = 1;
    }
    for (int i = 0; i < 13; i++) if (!s[i]) printf("%c %d\n", 'S', i+1);
    for (int i = 0; i < 13; i++) if (!h[i]) printf("%c %d\n", 'H', i+1);
    for (int i = 0; i < 13; i++) if (!c[i]) printf("%c %d\n", 'C', i+1);
    for (int i = 0; i < 13; i++) if (!d[i]) printf("%c %d\n", 'D', i+1);
    return 0;
}

Measured memory_bytes: 3176
N = int(input())
A = 0#末尾がA
B = 0#先頭がB
BA = 0#先頭がB かつ 末尾がA
AB = 0#ABの数

for i in range(N):
    s = input()
    AB += s.count("AB")
    if s[0] == "B":
        B += 1
    if s[-1] == "A":
        A += 1
    if s[0] == "B" and s[-1] == "A":
        BA += 1
        B -= 1
        A -= 1
ans = 0
ans += AB

if min(A,B) > 0:
    ans += BA + 1
    A -= 1
    B -= 1
    ans += min(A,B)
else:
    ans += max(BA + min(1, max(A,B)) -1,0)
print(ans)
    
#if BA > max(A,B) - min(A,B):
#    ans += (BA - (max(A,B) - min(A,B))) / 2
#print(A,B,BA,AB)

Measured memory_bytes: 44264
#include <stdio.h>

int count = 0;

void dfs(int ver, int v[][10], int seen[], int n, int m){
	int end = 1;
	for(int i=0; i < n; i++) {
		if(!seen[i] && i != ver)
			end = 0;
	}
	if(end) {
		count++;
		return;
	}

	seen[ver] = 1;
	for(int i=0; v[ver][i]; i++) {
		if(seen[v[ver][i]-1])
			continue;
		dfs(v[ver][i]-1, v, seen, n, m);
	}
	seen[ver] = 0;
}

int main(void){
	int n, m, a, b, idx[10] = {0};
	int v[10][10] = {{0}};
	int seen[8] = {0};

	scanf("%d%d", &n, &m);
	for(int i=0; i < m; i++) {
		scanf("%d%d", &a, &b);
		a--; b--;
		v[a][idx[a]++] = b+1;
		v[b][idx[b]++] = a+1;
	}

	dfs(0, v, seen, n, m);
	printf("%d", count);

	return 0;
}


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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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){
    string s; cin >> s;
    int K; cin >> K;
    REP(i,s.size()){
        if(s[i] == 'a') continue;
        if(26-(s[i]-'a') <= K){
            K -= 26 - (s[i]-'a');
            s[i] = 'a';
        }
    }
    if(K > 0) s[s.size()-1] = (s[s.size()-1]-'a' + K%26)%26 + 'a';
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 512
import java.io.InputStream;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.IntStream;

public class Main {

  static Set<Long> squareNumber = new HashSet<>();

  static {
    int max = 40 * 40 * 10;
    for (int i = 0; i < max; i++) {
      long pow = i * i;
      squareNumber.add(pow);
      if (pow > max) {
        break;
      }
    }
  }

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }


  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int n = Integer.parseInt(sc.next());
    int d = Integer.parseInt(sc.next());
    sc.nextLine();
    List<Point> points = new ArrayList<>();
    int result = 0;
    for (int i = 0; i < n; i++) {
      Point pointN = Point.of(d, sc.nextLine());
      result += points.stream().filter(p -> p.isIntegerDistance(pointN)).count();
      points.add(pointN);
    }
    pw.println(result);
  }

  static class Point {

    int d;
    int x[];

    Point(int d, int[] x) {
      this.d = d;
      this.x = x;
    }

    static Point of(int d, String line) {
      return new Point(d,
        Arrays.stream(line.split(" ", -1)).map(Integer::parseInt).mapToInt(Integer::intValue)
          .toArray());
    }

    boolean isIntegerDistance(Point other) {
      long powDistance = (int) IntStream.range(0, d)
        .mapToLong(i -> (this.x[i] - other.x[i]) * (this.x[i] - other.x[i])).sum();
      return squareNumber.contains(powDistance);
    }
  }
}


Measured memory_bytes: 28880
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

typedef long long ll;

ll a, n;
ll ans;
const ll INF = (ll)1e13;

ll mult(ll x, ll y)
{
	if ((double)x * y > 2 * INF) return INF;
	return min(INF, x * y);
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	cin >> n >> a;
	ans = n;
	for (int k = 2; k <= 40; k++)
	{
		ll x = 2;
		while(true)
		{
			ll y = 1;
			for (int i = 0; i < k; i++)
				y = mult(y, x);
			if (y >= n) break;
			x++;
		}
		x--;
		ll res = a * (k - 1) + k * x;
		ll z = 1;
		for (int i = 0; i < k; i++)
			z *= x;
		for (int i = 0; z < n; i++)
		{
			res++;
			z /= x;
			z *= x + 1;
		}
		ans = min(ans, res);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 384
const N,M=map(x->parse(Int,x),split(readline()))
const A=[Int[] for _=1:N]
const B=[Int[] for _=1:N]
const C=[Int[] for _=1:N]
const vis=[false for _=1:N]
if M%2==1
	println(-1)
	exit()
end
for s=readlines()
	a,b=map(x->parse(Int,x),split(s))
	push!(A[a],b)
	push!(A[b],a)
	push!(B[a],length(A[b]))
	push!(B[b],length(A[a]))
	push!(C[a],-1)
	push!(C[b],-1)
end
@inbounds function dfs(u,p)
	vis[u]=true
	cnt=0
	par=-1
	for i=1:length(A[u])
		v=A[u][i]
		if !vis[v]
			dfs(v,u)
		end
		if v!=p&&C[u][i]!=0
			if C[u][i]==-1
				C[u][i]=1
				C[v][B[u][i]]=0
			end
			cnt+=1
		end
		if v==p
			par=i
		end
	end
	if cnt%2==1
		C[u][par]=1
		C[p][B[u][par]]=0
	end
end
dfs(1,0)
for u=1:N
	for i=1:length(A[u])
		if C[u][i]==1
			println("$u $(A[u][i])")
		end
	end
end


Measured memory_bytes: 204080
n = int(input())
if n < 2:
    print(0)
    exit()

if n % 2 != 0:
    print(0)
    exit()

ans = 0
a = 10
for i in range(10**18):
    if 10*5**i > n:
        break
    ans += n//(10*5**i)
print(ans)


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

vector<string> v(12);
const int mov[] = {-1, 0, 1, 0, -1};

void visit(int x, int y) {
    if (x < 0 || 12 <= x || y < 0 || 12 <= y || v[y][x] == '0') {
        return ;
    }
    v[y][x] = '0';
    for (int i = 0; i < 4; ++ i) {
        visit(x + mov[i], y + mov[i+1]);
    }
}

int main() {
    while (1) {
        for (int i = 0; i < 12; ++ i) {
            cin >> v[i];
            if (cin.eof()) return 0;
        }

        int ans = 0;
        for (int y = 0; y < 12; ++ y) {
            for (int x = 0; x < 12; ++ x) {
                if (v[y][x] == '0') continue;
                visit(x, y);
                ++ ans;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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

def main():
    N, M = map(int, input().split())
    keys = []
    for i in range(M):
        a, b = map(int, input().split())
        s = 0
        C = list(map(int, input().split()))
        for c in C:
            c -= 1
            s |= 1 << c
        keys.append([s,a])

    dp = [float('inf')] * (1 << N)

    dp[0] = 0
    for s in range(1 << N):
        for i in range(M):
            t = s | keys[i][0]
            cost = dp[s] + keys[i][1]
            dp[t] = min(dp[t],cost)
    
    if dp[-1] == float('inf'):
        print(-1)
    else:
        print(dp[-1])
            
main()

Measured memory_bytes: 42716
#include<iostream>
#include<cstdint>
using namespace std;
 
int main() {
  uint64_t a, b;
  
  cin >> a >> b;
  
  if( (a & 1 != 0) && (b & 1 != 0) ) {
    cout << "Odd";
  } else {
    cout << "Even";
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  int d;
  cin>>d;

  vector<ll> p(26);
  rep(i,26) {
    cin>>p[i];
  }


  vector<vector<ll>> q(d,vector<ll>(26));
  rep(i,d) {
    rep(j,26) {
      cin>>q[i][j];
    }
  }

  ll pre=0;
  vector<int> r(26,0);
  rep(i,d-5){
    ll ans=-INF;
    ll memo;
    rep(j,26){
      ll sum=pre;
      auto last=r;
      sum+=q[i][j];
      last[j]=i+1;
      rep(k,26){
        sum-=3*p[k]*(i+1-last[k]);
      }
      if(sum>ans) {
        memo=j;
        chmax(ans,sum);
      }
    }
    cout << memo+1 << endl;
    pre=ans;
    r[memo]=i+1;
  }

  ll answer=-INF;
  ll A,B,C,D,E;
  vector<int> zen(5);
  rep(i,26){
    rep(j,26){
      rep(k,26){
        rep(l,26){
          rep(m,26){
            zen[0]=i;
            zen[1]=j;
            zen[2]=k;
            zen[3]=l;
            zen[4]=m;

            ll sum=0;
            auto last=r;
            rep(n,5){
              sum+=q[d-5+n][zen[n]];
              last[zen[n]]=d-5+n+1;
              rep(o,26){
                sum-=p[o]*(d-5+n+1-last[o]);
              }
            }

            if(sum>answer) {
              A=zen[0];
              B=zen[1];
              C=zen[2];
              D=zen[3];
              E=zen[4];
            }
            chmax(answer,sum);

          }
        }
      }
    }
  }

  cout << A+1 << endl;
  cout << B+1 << endl;
  cout << C+1 << endl;
  cout << D+1 << endl;
  cout << E+1 << endl;
  
}

Measured memory_bytes: 3740
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] lines = br.readLine().split(" ");
        for (int i = n - 1; i >= 0; i--) {
            System.out.print(lines[i]);
            if (i != 0) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
}

Measured memory_bytes: 24244
# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion
class union_find:
    def __init__(self, n):
        self.n = n
        self.rank = [0]*n
        self.parent = [int(j) for j in range(n)]
    
    def union(self,i,j):
        i = self.find(i)
        j = self.find(j)
        if self.rank[i] == self.rank[j]:
            self.parent[i] = j
            self.rank[j] += 1

        elif self.rank[i] > self.rank[j]:
            self.parent[j] = i
        else:
            self.parent[i] = j

    def find(self, i):
        temp = i
        if self.parent[temp] != temp:
            self.parent[temp] = self.find(self.parent[temp])
        return self.parent[temp]
from math import log2, ceil
from collections import deque
def main():
# Enter your code here. Read input from STDIN. Print output to STDOUT
    # for t in range(int(input())):
        
        n = int(input())
        # n,k  =[int(j) for j in input().split()]
        s = input()
        i=0
        j = n-1
        ans = 0
        while(i<j):
            if(s[i]=='R' and s[j]=='W'):
                i+=1
                j-=1
            elif(s[i]=='W' and s[j]=='R'):
                ans+=1
                i+=1
                j-=1
            elif((s[i]=='R' and s[j]=='R')):
                i+=1
            else:
                j-=1
        print(ans)
        


        # n,k,z  =[int(j) for j in input().split()]
        



if __name__ == "__main__":
    main()

Measured memory_bytes: 69368
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using namespace std;

void SolveA()
{
	int X, A, B;
	scanf("%d", &X);
	scanf("%d", &A);
	scanf("%d", &B);

	int fsum = X - A;
	int dnum = fsum % B;

	printf("%d\n", dnum);
}

int main()
{
	SolveA();
}

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

using namespace std;

int gcd_inner(int a, int b){
    if(a==0) return b;
    return gcd_inner(b %a, a);

}

int gcd(vector<int> v){
    int gcd = v[0];
    for (int i : v) {
        gcd = gcd_inner(i, gcd);
    }
    return gcd;
}

int main() {
    int n, x;
    cin >> n;
    cin >> x;
    vector<int> cities;

    for(int i=0;i<n;i++){
        int city;
        cin >> city;
        if(city > x) cities.push_back(city-x);
        if(city < x) cities.push_back(x-city);
    }
    cout << gcd(cities);
    return 0;
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
long long Ans;
inline void dfs(long long x,long long y,long long z,int r){
	if(!r){
		Ans=max(Ans,x+y+z);
		return;
	}dfs(x*2,y,z,r-1),dfs(x,y*2,z,r-1),dfs(x,y,z*2,r-1);
}
int main(){
	long long a,b,c,k;
	cin>>a>>b>>c>>k;
	dfs(a,b,c,k);
	cout<<Ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=0
c=a.reverse()
d=0
for i in range(n-1):
  if a[i]-a[i+1]==-1:
    a[i+1]=a[i+1]-1
  elif a[i]-a[i+1]<=-2:
    b+=1
  else:
    d=d
    
if b==0:
  print("Yes")
else:
  print("No")


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

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi std::vector<int>
#define vvi std::vector<std::vector<int> >
#define vpi std::vector<pi >
#define pi std::pair<int,int>
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (int var = (from); var <= ((int)(to)); var++)
#define DOWNTO(var, from, to) for (int var = (from); var >= ((int)(to)); var--)
#define FOR(var, to)		  UPTO(var, 0, (to)-1)
#define DOWN(var, from)	   DOWNTO(var, (from)-1, 0)

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) std::cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) std::cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

static const int MOD = 1000000007;
static const int INF = ((1<<30)-1);
static const s64 LINF = ((1LL << 62)-1);

struct Comb {
	std::vector<std::vector<s64> > a;
	Comb(int n) { // O(n^2)
		a.resize(n+1);
		FOR(i,n+1) {
			a[i].resize(i+1, 1);
			UPTO(j,1,i-1) a[i][j] = a[i-1][j] + a[i-1][j];
		}
	}
	s64 ncr(int n, int r) {
		assert(n >= 0);
		assert(n <= (int)a.size());
		assert(r >= 0);
		assert(r <= n);
		return a[n][r];
	}
};

#define gc(c) (c)=getchar()
int ri() {
	int c,s=0,r=0;
	for(;;){gc(c);if(c=='-'){s=1;break;}if(c>='0'&&c<='9'){r=c-'0';break;}}
	for(;;){gc(c);if(c<'0'||c>'9')break;r*=10;r+=c-'0';}
	if(s)r=-r;
	return r;
}
s64 rs64() {
	s64 r = 0;
	int c,s = 0;
	for(;;){gc(c);if(c=='-'){s=1;break;}if(c>='0'&&c<='9'){r=c-'0';break;}}
	for(;;){gc(c);if(c<'0'||c>'9')break;r*=10;r+=c-'0';}
	if(s)r=-r;
	return r;
}

int int_less(const void *a, const void *b) {
	return (*(const int*)a - *(const int*)b);
}
int int_greater(const void *a, const void *b) {
	return (*(const int*)b - *(const int*)a);
}
std::string operator*(const std::string &s, int n){ std::string res; FOR(i,n) res += s; return res; }

template<class T> std::ostream& operator<<(std::ostream& os, std::vector<T> a) { for (auto i : a) os << i << " "; return os; }
template<class T> std::ostream& operator<<(std::ostream& os, std::set<T> a) { for (auto i : a) os << i << " "; return os; }
template<class A, class B> std::ostream& operator<<(std::ostream&os, std::pair<A,B> a) { os << a.fi << "," << a.se; return os; }


int main() {
	int n = ri();
	int a[n];
	INPUT(a);
	int ans = 0;
	FOR(i,n) {
		bool res = true;
		FOR(j,i) if (a[j] > a[i]) res = false;
		if (res) ans++;
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define fio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
// #define double long double
// #define mp make_pair
// #define pb push_back
// Upper case English alphabet to lower case ch |= ' ';
// Lower case English alphabet to upper case ch &= '_’ ;
//__builtin_popcount(x)

int INF=(int)1e9+7,t=-1,till=0;
int gcd(int a, int b) { return b!=0 ? gcd(b, a % b) : a; }
// int digits(int n){return floor(log10(n))+1 ;}
// bool ispoweroftwo (int x) { return x && (!(x&(x-1))); }
//vector<int> vis,parent,ti,tout,dis;
vector<vector<int> > adj;
map<int,int> vis;
// vector<int> row={-1,1,0,0};
// vector<int> col={0,0,-1,1};
// vector<int> dp;
// void dfs(int v){
//     vis[v]=1;
//     for(int x:adj[v]){
//         if(vis[x]==0){
//             cnt++;
//             dfs(x);
//         }
//     }
// }

signed main(){
    fio;
    int n;
    cin>>n;
    vector<double> v(n+1);
    for(int i=1;i<=n;i++) cin>>v[i];
    double ans=0;
    double dp[n+1][n+1];
    dp[0][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++) dp[i][j]=0;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j) dp[i][j]=dp[i-1][j-1]*v[i];
            dp[i][j]+=dp[i-1][j]*(1-v[i]);
            if(i==n && j>n/2) ans+=dp[i][j];
        }
    }

    cout<<fixed<<setprecision(9)<<ans<<endl;

    

    

}


Measured memory_bytes: 70656
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <istream>
#include <set>
#include <queue>
#define rep0(i,n) for (long long int i = 0; i <= (n); ++i)
#define rep1(i,n) for (long long int i = 1; i <= (n); ++i)
#define REP(a,b) for (long long int i = a; i <= (b); ++i) 
#define ps push_back 
#define MOD 1000000007
using namespace std;
typedef long long ll;
int main() {
	int five = 0;
	int seven = 0;
	REP(0, 2) {
		int a;
		cin >> a;
		if (a == 5)
			five++;
		else if (a == 7)
			seven++;
	}
	if (five == 2 && seven == 1) {
		cout << "YES" << endl;
	}
	else
		cout << "NO" << endl;
	return 0;
}

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

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

    int k;
    cin >> k;

    int cou = 0;
    for(int i = 0; i < k; i++){
        if(a < b){
            break;
        }

        b *= 2;
        cou++;
    }

    if(cou != k){
        for(int i = cou; i < k; i++){
            if(b < c){
                break;
            }
            c *= 2;
        }
    }

    if(a < b && b < c){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
#define precout(val) cout << std::fixed << std::setprecision(20) << val;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };

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

  string s,t; cin >> s >> t;
  if(s == t.substr(0, t.size() - 1)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    string S; cin >> S;
    map<char, set<int>> M;
    rep(i,S.size()) {
        M[S[i]].insert(i);
    }

    for (auto x : M) {
        char c = x.first;
        auto j = begin(M[c]);
        int prev = *j;
        for (++j; j != end(M[c]); j++) {
            if (*j - prev <= 2) {
                cout << prev + 1 << " " << *j + 1 << endl;
                return 0;
            }
            prev = *j;
        }
    }
    cout << "-1 -1" << endl;
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	int X;
	cin >> X;
	for (int k = 1; ; ++ k) {
		if (k*X % 360 == 0) {
			cout << k << endl;
			return 0;
		}
	}
}


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

typedef long long ll;

const ll INTEG = pow(10,9) + 7;

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

  map<char,int> m;
  for(char i:s){
    m[i]++;
  }
  bool flag = false;
  if(m.size() == 2){
    for(auto i:m){
      flag = i.second == 2;
      if(!flag) break;
    }
  }

  cout << (flag?"Yes":"No") << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

void insertionSort(int* input, int N);

int main()
{
	int N = 0;
	scanf("%d", &N);
	int input[1000];

	for (int i = 0; i < N; ++i)
		scanf("%d", &input[i]);

	for (int i = 0; i < N; ++i)
	{
		printf("%d", input[i]);
		if (i != N-1)
			printf(" ");
	}
	printf("\n");

	insertionSort(input, N);
	

	return 0;
}

void insertionSort(int* input, int N)
{
	for (int i = 1; i < N; ++i)
	{
		int index		= i - 1;
		int curValue	= input[i];
		
		while ((index >= 0) && (input[index] > curValue))
		{
			input[index+1] = input[index];
			index--;
		}
		input[index+1] = curValue;
		for (int i = 0; i < N; ++i)
		{
			printf("%d", input[i]);
			if (i != N - 1)
				printf(" ");
		}
		printf("\n");
	}
}

Measured memory_bytes: 1036