akhauriyash/Code-Regression huggingface dataset:
import sys
import re
import heapq

def value(t):
    global a, b, c
    return -(a[t[0]] + b[t[1]] + c[t[2]])

def main():
    global a, b, c
    x, y, z, k = map(int, re.split(r'\s+', sys.stdin.readline().strip()))
    #print(x, y, z, k)
    a = list(map(int, re.split(r'\s+', sys.stdin.readline().strip())))
    b = list(map(int, re.split(r'\s+', sys.stdin.readline().strip())))
    c = list(map(int, re.split(r'\s+', sys.stdin.readline().strip())))

    a.sort()
    b.sort()
    c.sort()

    done = set()
    q = list()
    t = (x - 1, y - 1, z - 1)
    q.append((value(t), t))

    for _ in range(k):
        val, t = heapq.heappop(q)
        print(-val)
        t0 = (t[0] - 1, t[1], t[2])
        t1 = (t[0], t[1] - 1, t[2])
        t2 = (t[0], t[1], t[2] - 1)
        if (t0 not in done) and (t[0] - 1 >= 0):
            heapq.heappush(q, (value(t0), t0))
            done.add(t0)
        if (t1 not in done) and (t[1] - 1 >= 0):
            heapq.heappush(q, (value(t1), t1))
            done.add(t1)
        if (t2 not in done) and (t[2] - 1 >= 0):
            heapq.heappush(q, (value(t2), t2))
            done.add(t2)
            
main()


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define FOR(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define REP(i,n) FOR(i,0,n)
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; }
using ll = long long;

int k;
vector<int> d;

int bfs() {
  deque<int> Q;
  REP(i,k) d[i] = INF;
  d[1] = 1;
  Q.push_back(1);
  while (Q.size()) {
    auto v = Q.front(); Q.pop_front();
    int nv = (v+1)%k;
    if (d[nv] == INF) {
      d[nv] = d[v] + 1; Q.push_back(nv);
    }
    nv = (v*10)%k;
    if (d[nv] > d[v]) {
      d[nv] = d[v]; Q.push_front(nv);
    }
  }
  return d[0];
}

int main() {
  cin >> k;
  d.resize(k);
  int ans = bfs();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
 vector<long long> memo(87,-1);
long long rucas(int x){
  if(x == 0 ){
    return 2;
  }
  if(x == 1){
    return 1;
  }
  if(memo[x] != -1) {
    return memo[x];
  }
  
 return  memo[x] = rucas(x-1) + rucas(x-2);
}

int main(){
  int N;
  cin >> N;
 cout <<  rucas(N) << endl;
}

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

using namespace std;

#define sp << " " <<
#define mod 1000000007

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

long long dice()
{
    uniform_int_distribution<long long> uid(1,2);//specify l and r.
    return uid(rng) ;
}

int read()
{
       int cc = getc(stdin);
       for (;cc < '0' || cc > '9';)  cc = getc(stdin);
       int ret = 0;
       for (;cc >= '0' && cc <= '9';)
       {
          ret = ret * 10 + cc - '0';
          cc = getc(stdin);
       }
      return ret;
}

inline void print(int n)
{
  if (n == 0)
  {
    putchar('0');
    putchar('\n');
  }
  else if (n == -1)
  {
    putchar('-');
    putchar('1');
    putchar('\n');
  }
  else
  {
    char buf[11];
    buf[10] = '\n';
    int i = 9;
    while (n)
    {
      buf[i--] = n % 10 + '0';
      n /= 10;
    }
    while (buf[i] != '\n')
      putchar(buf[++i]);
  }
}
*/

long double dp[301][301][301];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long double n;
    int x=0,y=0,z=0;
    cin >> n;
    int d;
    for(int i=0;i<n;i++)
    {
        cin >> d;
        if(d==1)
            x++;
        else if(d==2)
            y++;
        else
            z++;
    }
    dp[0][0][0]=0;
    for(int i=0;i<=300;i++)
    {
        for(int j=0;j<=300;j++)
        {
            for(int k=0;k<=300;k++)
            {
                if(i+j+k>300)
                    continue;
                if((i+j+k)>0)
                    dp[k][j][i]=(n/(long double)(i+j+k));
                if(k>0)
                    dp[k][j][i]+=(long double)k*dp[k-1][j][i]/(i+j+k);
                if(j>0)
                    dp[k][j][i]+=(long double)j*dp[k+1][j-1][i]/(i+j+k);
                if(i>0)
                    dp[k][j][i]+=(long double)i*dp[k][j+1][i-1]/(i+j+k);
            }
        }
    }
    cout << fixed <<  setprecision(13) << dp[x][y][z];
	return 0;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint operator-() const { return mint(-x); }

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

vector<int> G[100010];
mint dp[100010][2];

void dfs(int v, int p) {
    dp[v][0] = dp[v][1] = 1;
    for (auto nv: G[v]) {
        if (nv == p) continue;
        dfs(nv, v);
        dp[v][0] *= dp[nv][0] + dp[nv][1];
        dp[v][1] *= dp[nv][0];
    }
}

int main() {
    int N;
    cin >> N;
    rep(i, N - 1) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    dfs(0, -1);

    cout << (dp[0][0] + dp[0][1]).x << endl;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1000000007;  // 1e9+7
const int INF = 100100100;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int A, B;
  cin >> A >> B;
  int ans = 0;
  while (1 + (A - 1) * ans < B) {
    ans++;
  }
  cout << ans << '\n';
}

Measured memory_bytes: 256
N,K = map(int, input().split())
A = list(map(int,input().split()))

ls = [1]
s = {1}
cnt = 0
flag = 0
for i in range(K):
    t = A[ls[-1]-1]
    if t in s:
        nls = ls[ls.index(t):]
        flag = 1
        break
    else:
        ls.append(t)
        s.add(t)
        cnt += 1
        
if flag == 1:
    nokori = K-cnt-1
    amari = nokori % len(nls)
    print(nls[amari])
else:
    print(ls[-1])

Measured memory_bytes: 32380
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL
#define MAX 500001
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;

Node treeMinimum(Node x){
while(x->left!=NIL){
  x=x->left;
}
return x;
}

Node treeMaximum(Node x){
while(x->right!=NIL){
  x=x->right;
}
return x;
}

Node treeSearch(Node x, int k){
while ( x!=NIL && k!=x->key){
  if(k<x->key) x=x->left;
  else x=x->right;
}
return x;
}

Node treeSuccessor(Node x){
Node y;
if(x->right !=NIL) return treeMinimum(x->right);

y=x->parent;
while ( y !=NIL && x == y->right) {
  x=y;
  y=y->parent;
}
return y;

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
if(z->left == NIL || z->right ==NIL){
  y=z;
}
else y= treeSuccessor(z);

if(y->left != NIL) x=y->left;
else x=y->right;

if(x !=NIL) x->parent=y->parent;
if(y->parent==NIL) root=x;
else if(y==y->parent->left) y->parent->left=x;
else y->parent->right=x;

if(y!=z) z->key=y->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

while( x!=NIL){
  y=x;
  if(z->key<x->key) x=x->left;
  else x=x->right;
}
z->parent=y;
if(y==NIL)root=z;
else{
  if(z->key<y->key) y->left=z;
  else y->right=z;
}
}

void inorder(Node u){
if(u==NIL) return;
inorder(u->left);
printf(" %d",u->key);
inorder(u->right);
}
void preorder(Node u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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

int main() {
    int N;
    cin >> N;
    vector<int> X(N);
    for (int i = 0; i < N; i++)
    {
        cin >> X[i];
    }
    sort(X.begin(), X.end());
    int ans = 1000000;
    for (int i = X[0]; i <= X.back(); i++)
    {
        int temp = 0;
        for (int j = 0; j < N; j++)
        {
            temp += (X[j] - i) * (X[j] - i);
        }
        ans = min(ans, temp);
    }
    cout << ans << endl;
    
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

int main()
{
    string s;
    string a = "abcdefghijklmnopqrstuvwxyz";
    int fl[30] = {};
    cin >> s;
    rep(i,s.size()){
        rep(j,a.size()){
            //cou  << s[i] << " " << a[j] << endl;
            if(s[i] == a[j]){
                fl[j] = 1;
                break;
            }
        } 
    }
    rep(j,a.size()){
        if(fl[j] == 0){
            cout << a[j] << endl;
            return 0;
        }
    }
    cout << "None" << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
char s[11];
int main() {
    scanf("%s", s);
    int len = strlen(s);
    s[4] = '\0';
    if (strcmp(s, "YAKI") == 0) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    sort(all(vec));
    vector<pair<int,int> > count(0);
    count.push_back(pair<int,int> (vec[0],1));
    rep(i,N - 1){
        if (vec[i] == vec[i + 1]){
            int len_count = count.size();
            count[len_count - 1].second++;
        }
        else{
            count.push_back(pair<int,int> (vec[i + 1], 1));
        }
    }
    vector<int> chart(100002);
    int len_count = count.size();
    rep(i,len_count){
        chart[count[i].first] = count[i].second;
    }
    int ans = 0;
    rep(i,100002){
        if (i == 0){
            if (chart[i] + chart[i + 1] > ans) ans = chart[i] + chart[i + 1];
        }
        else{
            if (chart[i - 1] + chart[i] + chart[i + 1] > ans){
                ans = chart[i - 1] + chart[i] + chart[i + 1];
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1656
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

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

int main(void){
	int N;
	string s;
	int respon[1000];
	int dp[1000][8];
	cin >> N;
	cin >> s;
	REP(i, s.size()){
		if(s[i] == 'J') respon[i] = 1;
		else if(s[i] == 'O') respon[i] = 2;
		else respon[i] = 4;
	}
	REP(i, 1000){
		fill(dp[i], dp[i]+8, 0);
	}

	REP(i, 8){
		if((i & respon[0]) != 0 && (i & 1) != 0)
			dp[0][i] = 1;
	}

	FOR(i, 1, N){
		REP(j, 8){
			if((j & respon[i]) == 0) continue;
			REP(k, 8){
				if((j & k) == 0) continue;
				dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007;
			}
		}
	}

	int res = 0;
	REP(i, 8){
		res = (res + dp[N-1][i]) % 10007;
	}
	cout << res << endl;
}

Measured memory_bytes: 3204
#include <algorithm>
#include <iostream>

using namespace std;
/** Problem0117 : A reward for a Carpenter **/
const int INF = 100000;

int main()
{
	int d[21][21];
	int V, E;
	
	int s, g, plus, minus;
	char c;
	cin >> V >> E;
	
	for (int i=0; i<21; i++)
		for (int j=0; j<21; j++) d[i][j] = INF;
	
	for (int i=0; i<E; i++) {
		int a, b, dd, ddd;
		cin >> a >> c >> b >> c >> dd >> c >> ddd;
		d[a][b] = dd;
		d[b][a] = ddd;
	}
	
	cin >> s >> c >> g >> c >> plus >> c >> minus;
	
	for (int k=1; k<=V; k++)
		for (int i=1; i<=V; i++)
			for (int j=1; j<=V; j++)
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	cout << plus - (minus + d[s][g] + d[g][s]) << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#define MAX 100000
#define SENTINEL 2000000000

struct Card {
  char suit;
  int value;
};

struct Card L[MAX/2+2], R[MAX/2+2];

void merge(struct Card A[], int n, int left, int mid, int right) {
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i=0;i<n1;i++) L[i] = A[left + i];
  for(int i=0;i<n2;i++) R[i] = A[mid  + i];
  L[n1].value = R[n2].value = SENTINEL;
  i = j = 0;
  for(k=left; k<right; k++) {
    if(L[i].value <= R[j].value) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(struct Card A[], int n, int left, int right) {
  if(left+1 < right) {
    int mid = (left+right) / 2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid, right);
    merge(A,n,left,mid,right);
  }
}

int partition(struct Card A[], int n, int p, int r) {
  int i, j;
  struct Card t, x;
  x = A[r];
  i = p-1;
  for(j=p; j<r; j++) {
    if(A[j].value <= x.value) {
      i++;
      t=A[i]; A[i]=A[j]; A[j]=t;
    }
  }
  t=A[i+1]; A[i+1]=A[r]; A[r]=t;
  return i+1;
}

void quickSort(struct Card A[], int n, int p, int r) {
  int q;
  if(p<r) {
    q = partition(A,n,p,r);
    quickSort(A,n,p,q-1);
    quickSort(A,n,q+1,r);
  }
}

int main() {
  int n, i, v;
  struct Card A[MAX], B[MAX];
  char S[10];
  int stable = 1;

  scanf("%d", &n);

  for(i=0;i<n;i++) {
    scanf("%s %d",S,&v);
    A[i].suit =  B[i].suit  = S[0];
    A[i].value = B[i].value = v;
  }

  mergeSort(A,n,0,n);
  quickSort(B,n,0,n-1);

  for(i=0;i<n;i++) {
    // ????????????????????¨??????????????????????????????????????????
    if(A[i].suit != B[i].suit) stable = 0;
  }

  if(stable==1) printf("Stable\n");
  else printf("Not stable\n");
  for(i=0;i<n;i++) {
    printf("%c %d\n",B[i].suit,B[i].value);
  }

  return 0;
}



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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007


int main(){

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




  return 0;
}

Measured memory_bytes: 256
n=int(input())
t,a=[int(x) for x in input().split()]
h=[int(x) for x in input().split()]
ans=0
diffa=10**10
for i in range(n):
    diffi=abs(t-h[i]*0.006-a)
    if diffa>diffi:
        ans=i+1
        diffa=diffi
print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e9;

int main()
{
    int a, b, x;
    cin >> a >> b >> x;
    if(b >= x - a && x >= a)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}


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

int main () {
  int N;
  cin >> N;
  int64_t L1 = 2, L2 = 1, L = 0;

  if (N == 1) cout << L2 << endl;
  else {
    for (int i = 0; i < N - 1; i++) {
      L = L1 + L2;
      L1 = L2;
      L2 = L;
    }
    cout << L << endl;
  }
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let N: i32 = read();
    if N == 1 {
        println!("Hello World");
    } else {
        let A: i32 = read();
        let B: i32 = read();
        println!("{}", A+B);
    }
}


Measured memory_bytes: 4352
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char s[1<<19];
int sm[1<<19];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
        sm[i]=sm[i-1]+(s[i]=='#');
    int als=sm[n];
    for(int i=n,ss=0;i;--i){
        ss+=(s[i]=='.');
        als=min(als,ss+sm[i-1]);
    }
    printf("%d",als);
    return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <cstdlib>
#include <string>
#include <typeinfo>
using namespace std;
int main()
{
    string s, ms;
    cin >> s;
    ms = s.substr(5, 6);
    int m = stoi(ms);
    if (m > 4)
    {
        cout << "TBD" << endl;
    }
    else
    {
        cout << "Heisei" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<cstdlib>
#include<math.h>
#include<set>
#include<array>
using namespace std;

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



#define rep(n) for(int i=0;i<n;i++)
typedef pair<int, int> pii;

typedef long long ll;
typedef pair<ll, ll>pll;
const int MOD = 1000000007;
const int INF = 1 << 29;


struct iii {
	int f, s, t;
};

int main() {

	int n;

	cin >> n;
	vector<pair<int,pii>> s(n);
	rep(n) {
		int a, b;
		cin >> a >> b;
		s[i] = make_pair(i, make_pair(a, b));

	}
	double sum = 0;
	int cnt = 0;
	 do{
		for (int i = 0; i<n-1; i++) {
			sum += sqrt(pow(s[i].second.first - s[i + 1].second.first, 2) + pow(s[i].second.second - s[i + 1].second.second, 2));
			//cout << sum << endl;
		}
		//cout << ++cnt << endl;
	} while (next_permutation(s.begin(),s.end()));
	int um = 1;
	for (int i = 1; i <= n; i++) {
		um *= i;
	}
	printf("%.10f", sum / um);
	return 0;
}


Measured memory_bytes: 256
#include<bitset>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2005
using namespace std;
bitset<N*N>f;
int main(){
	int n,x,sum=0;
	scanf("%d",&n);
	f[0]=1;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		f|=(f<<x),sum+=x;
	}
	for(int i=(sum+1)/2;i<=sum;++i)
		if(f[i])  return printf("%d",i),0;
	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ld long double
#define int long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define ff first
#define ss second
#define rep(i,l,r) for(int i = (int)l;i<(int)r;i++)
#define td(v) v.begin(),v.end()
//#define M   1000000007 // 1e9 + 7
#define MAXN 200100
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int exp(int a,int b,int m){
	
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);

}

int cnt[MAXN];
int a[MAXN];
int n,m,k;
char s[15][1050];
int pre[15][1050];
int solve(vector<int> d){
	vector<int> cur(n,0);
	int res=0;
	for(int j=0;j<m;j++){
		int f=0;
		for(int it=0;it+1<(int)d.size();it++){
			int l = d[it];
			int r = d[it+1] -1;
			//
			int tem = pre[r][j] - (l==0 ? 0 : pre[l-1][j]);
			//
			if(tem>k){
				return 1e9;
			}
			
			if(tem+cur[it]>k){
				f = 1;
			}
			
		}
		if(f){
			res++;
			for(int it=0;it+1<(int)d.size();it++){
				int l = d[it];
				int r = d[it+1] -1;
				//
				int tem = pre[r][j] - (l==0 ? 0 : pre[l-1][j]);
				//
				if(tem>k){
					return 1e9;
				}
				
				cur[it] = tem;
			}
		}else{
			for(int it=0;it+1<(int)d.size();it++){
				int l = d[it];
				int r = d[it+1] -1;
				//
				int tem = pre[r][j] - (l==0 ? 0 : pre[l-1][j]);
				//
				if(tem>k){
					return 1e9;
				}
				
				cur[it]+= tem;
			}
			
			
		}
	}
	return res;
}

int32_t main(){
	fastio;
	cin>>n>>m>>k;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>s[i][j];
			pre[i][j]+=(s[i][j]=='1'?1:0);
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(i)pre[i][j]+=pre[i-1][j];
		}
	}
	int best = n - 1 + m - 1;
	if(n==1){
		vector<int> d;
		d.pb(0);
		d.pb(1);
		best = min(best,solve(d));
	}else{
		for(int i=0;i<(1<<(n-1));i++){
			int r1 = __builtin_popcount(i);
			// corto onde tem os bits;
			int r2 = 0;
			vector<int> d;
			d.pb(0);
			for(int j=0;j<n-1;j++){
				if((1<<j)&i){
					d.pb(j+1);
				}
			}
			d.pb(n);
				r2+=solve(d);
			
			best = min(best,r1+r2);
		}
	}
	cout<<best<<endl;
	
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();  //候補地点の数
    int T = sc.nextInt();  //基礎気温 ある地点の気温はT-H[]*0.006
    int A = sc.nextInt();  //理想とする気温
    int[] H = new int[N];  //候補地点ごとの高度
    int number = 0; //理想の候補地点の番号
    double x = 1000.0; //理想の差の絶対値
    for(int i = 0; i < N; i++)
      H[i] = sc.nextInt();
    
    for(int i = 0; i < N; i++){
      double xi = A - (T - H[i] * 0.006);
        if(xi < 0) xi = -xi;
      if(xi < x){ x = xi; number = i + 1;}     
    }
    System.out.println(number);
  }  
}


Measured memory_bytes: 22100
import sys
import re
import queue
import collections
import math
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
	S = s_input()
	if(S[len(S)-1]!='s'):
		print(S[0:len(S)]+'s')
	else:
		print(S[0:len(S)]+'es')

	return

if __name__ == '__main__':
	main()

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

#define int long long
#define fast_io(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(x) x.begin(),x.end()
#define us unordered_set
#define um unordered_map
#define ms multiset
#define mm multimap
#define pb push_back
#define pf push_front
#define ins insert
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define _max max_element
#define _min min_element
#define tc(T) int T; cin>>T; while(T--)
#define q(q) int q; cin>>q; while(q--)
#define pi 3.1415926535897932384626433832
const int pinf=((int)2e18);
const int ninf=((int)-2e18);
const int mod=1000000007;

using namespace std;

int power(int x,int n,int M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}

bool vowel(char c)
{
    return(c=='a' or c=='e' or c=='i' or c=='o' or c=='u' or c=='A' or c=='E' or c=='I' or c=='U' or c=='O');
}

int32_t main()
{
    fast_io();

    //FILE *fptr1=freopen("in.txt","r",stdin);
    //FILE *fptr2=freopen("out.txt","w",stdout);


    int n,x;
    cin>>n;
    bool f=0;
    vector <int> a(n);
    loop(i,0,n)
    {
        int x;
        cin>>x;
        if(x%2==0)
        {
            if(x%3!=0 and x%5!=0)
            {
                f=1;
                break;
            }
        }
    }

    if(f) cout<< "DENIED";
    else cout<< "APPROVED";


    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define N 300001
using namespace std;

typedef unsigned ui;
typedef long long ll;
typedef unsigned long long ul;

ui a[N]; ll l[N], r[N];

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0);
#ifdef _DEBUG
	ifstream cin("1.in");
#endif
	ui n; cin >> n;
	for (ui i = 0; i != 3 * n; ++i) cin >> a[i];
	priority_queue<ui, vector<ui>, greater<ui>> ql;
	priority_queue<ui, vector<ui>, less<ui>> qr;
	ul ls = 0;
	for (ui i = 0; i <= 2 * n; ++i) {
		ql.push(a[i]);
		ls += a[i];
		if (ql.size() > n) {
			ls -= ql.top();
			ql.pop();
		}
		l[i] = ls;
	}
	ul rs = 0;
	for (ui i = 3 * n - 1; i >= n; --i) {
		qr.push(a[i]);
		rs += a[i];
		if (qr.size() > n) {
			rs -= qr.top();
			qr.pop();
		}
		r[i] = rs;
	}
	ll ans = 1ll<<63;
	for (ui i = n - 1; i != 2 * n; ++i)
		if(l[i] > r[i]) 
			ans = max(ans, l[i] - r[i + 1]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5624
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>
#include <string.h>
#define rep(i,n) for (int i=0; i< (n); i++)
typedef long long ll;
using namespace std;

const int mod = 998244353;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

int main()
{
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<mint> q(s+1);
    mint ans = 0;
    rep(i,n)
    {
        q[0] += 1;
        vector<mint> q2(s+1);
        rep(j,s+1)
        {
            q2[j] += q[j];
            if(j+a[i] <= s) q2[j+a[i]] += q[j];
        }
        q = q2;
        ans += q[s];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
long long int lcm(long long int a,long long int b){
  long long int n;
  n=a*b/__gcd(a,b);
  return n;
}
using ll =long long int;
#define ci(a) cin>>a
#define co(a) cout<<a<<endl
#define gcd(a,b) __gcd(a,b)
#define vec vector<ll>
#define For(i,a,b) for(int i=a;i<b;i++)
#define rFor(i,a,b) for(int i=a;i>b;i--)
#define sort(a,b) sort(a.begin(),b.end())
//gcd 最大公約数
//lcm 最小公倍数
//double 少数（変数）
//string 文字列（変数）
//sqrt 平方根
//ceil 天井関数
//floor 床関数
//abs 絶対値
//pow 累乗
//cbrt  立方根
//hypot 平方和の平方根
//(string-'0') 文字列を数字に変換
//vector<vector<int>> data(a,vector<b>(b)) a×b行列
//for(int i=0;i<a;i++)
//for(int j=0;j<b;j++)
//cin>>data.at(i).at(j)  a×b行列の入力
//floor(log10(a)+1) aの10進法での桁数
//ceil(log10(a)) aの10進法での桁数

int main() {
  ll a;
  ci(a);
  vec b(a);
  For(i,0,a)
    ci(b[i]);
  ll c=b[0]+b[a-2];
  For(i,1,a-1)
    c+=min(b[i-1],b[i]);
  co(c);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long dp[101][100001];
long long a[101], b[101];
int main (){
	long long n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; ++i){
		cin >> a[i] >> b[i];
	}
	dp[n][0] = 0;
	dp[0][m] = 0;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			dp[i][j] = dp[i - 1][j];
			if(j >= a[i] && dp[i][j] < dp[i - 1][j - a[i]] + b[i]){
				dp[i][j] = dp[i - 1][j - a[i]] + b[i];
			}
		}
	}
	cout << dp[n][m];
	return 0;
}

Measured memory_bytes: 78336
// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <numeric>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

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

  long long sum = 0;
  for(int a=1; a<=K; ++a) {
    for(int b=1; b<=K; ++b) {
      for(int c=1; c<=K; ++c) {
        sum += std::gcd(a, std::gcd(b, c));
      }
    }
  }

  cout << sum << endl;
  return 0;
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	int ans=0;
	for(int i=1;i<=n;++i){
		int a; cin>>a;
		if(a&1&&i&1)++ans;
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 3644
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    _ <- B.getLine
    k <- fst . fromJust . B.readInt <$> B.getLine
    xs <- map (fst . fromJust . B.readInt) . B.words <$> B.getLine
    print $ sum $ map (\x -> min (x * 2) (abs (k - x) * 2)) xs


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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}


vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0)
      dfs2(x, curr, num);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != -1) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find algo with array
// Find()
int findpar(int curr, int arr[])
{
  while(arr[curr] != curr) curr = arr[curr];
  return curr;
}
// Union()
void Union(int b, int spa, int arr[])
{
  while(arr[b] != b)
  {
    int c = arr[b];
    arr[b] = spa;
    b = c;
  }
  arr[b] = spa;
}

// Main Code
int co[30];
int main()
{
  int n;
  cin>>n;
  int arr[n];
  int sum = 0;
  int minn = INT_MAX;
  rep(i, 0, n)
  {
    cin>>arr[i];
    sum += arr[i];
    if(arr[i]%10 != 0 && arr[i] <= minn)
      minn = arr[i];
  }
  if(sum%10 != 0)
    cout<<sum<<endl;
  else if(minn == INT_MAX)
    cout<<0<<endl;
  else
    cout<<(sum - minn)<<endl;
  return 0;
}


Measured memory_bytes: 12288
n = int(input())
cnt = 0
for i in range(int((100 + 4) / 4)):
    for j in range(int((100 + 7) / 7)):
        if i * 4 + j * 7 == n:
            cnt += 1
if cnt > 0:
    print("Yes")
else:
    print("No")


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

n,T = map(int, raw_input().split())
t = map(int, raw_input().split())
total_time = 0
stop_time = 0
for i in range(n):
    if(stop_time<=t[i]):
        total_time += T
    else:
        total_time += t[i]-t[i-1]
    stop_time = t[i]+T
        
print (total_time)



Measured memory_bytes: 20036
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;


ll s_lt(ll);

map<ll, ll> memo;
map<ll, ll> memo_lt;

ll s(ll n) {
  if (n == 0) {
    return 1;
  }
  if (memo.count(n)) {
    return memo[n];
  }
  ll &ret = memo[n];
  ll c = 1;
  while (c <= n) {
    c *= 2;
  }
  c /= 2;
  ll r = n - c;
  return ret = (s(c - 1) + s(r) + s_lt(n) + mod - s_lt(c - 1)) % mod;
}

ll s_lt(ll n) {
  if (n <= 1) {
    return 0;
  }
  if (memo_lt.count(n)) {
    return memo_lt[n];
  }
  ll &ret = memo_lt[n];
  ll c = 1;
  while (c <= n) {
    c *= 2;
  }
  c /= 2;
  ll r = n - c;
  ll sub = s_lt(c / 2 - 1);
  if (n >= c + c / 2) {
    return ret = (s_lt(c + c / 2 - 1) + s_lt(r) + mod - sub) % mod;
  }
  return ret = (s_lt(c - 1) + s_lt(r + c / 2) + s(r) + mod - sub) % mod;
}


int main(void) {
  ll n;
  cin >> n;
  cout << s(n) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
  long long a,b,k; cin>>a>>b>>k;
  if(a+b<=k) a=b=0;
  else if(a<k) b-=(k-a),a=0;
  else a-=k;
  printf("%lld %lld\n",a,b);
  return 0;
}
  

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

int main() {
    
    long long N,x,count = 0;
    
    vector<long long> a;
    
    cin >> N;
    cin >> x;
    
    for ( long long i = 0; i < N; i++ ) {
        long long y;
        cin >> y;
        a.push_back(y);
    }
    
    
    for ( long long i = 1; i < N; i++ ) {
        
        long long z = a[i] + a[i-1];
        
        if ( z > x ) {
            if ( a[i] >= z-x ) { a[i] -= z - x; }
            else { a[i] = 0; }
            
            count += z - x;
        }
        
    }
    
    cout << count << endl;
    
    return 0;
}

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

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

    vector<int64_t> divs(N+1);
    for(int i=1; i<=N; i++) for(int j=i; j<=N; j+=i) divs[j]++;
    int64_t ans = 0;
    for(int i=1; i<N; i++) ans += divs[i];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11172
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int n;
    cin >> n;
    map<int, int> m;
    REP(i, n) {
        int d;
        cin >> d;
        m[d]++;
    }

    cout << m.size() << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

int main() {
  double h, a;
  cin >> h >> a;
  cout << ceil(h / a) << endl;
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#define rep(i, a, b) for (int i = (a), _ = (b); i <= _; ++ i)
#define per(i, a, b) for (int i = (a), _ = (b); i >= _; -- i)
#define For(i, a, b) for (int i = (a), _ = (b); i < _; ++ i)
#define ri rd<int>
using namespace std;
const int maxN = 107;

template<class T> inline T rd() {
	bool f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = 0;
	T x = 0; for (; isdigit(c); c = getchar()) x = x * 10 + c - 48; return f ? x : -x;
}

int n;
int a[maxN];
int c[maxN];

inline void NIE() {puts("Impossible"); exit(0);}
inline void TAK() {puts("Possible"); exit(0);}

int main() {

	n = ri();
	rep (i, 1, n) a[i] = ri();
	sort(a+1, a+n+1);
	rep (i, 1, n) ++c[a[i]];

	int D = a[n];
	int d = D / 2 + (D & 1);

	if (a[1] < d) NIE();
	c[d] += (D % 2 == 0);
	if (c[d] > 2) NIE();
	For (i, d, D) if (c[i] < 2) NIE();
	TAK();

	return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define Fast_cin ios::sync_with_stdio(false), cin.tie(0);
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
using namespace std;

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

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

template <typename T>
struct hash_map_t {
    vector <T> v, val, nxt;
    vector <int> head;
    int mod, tot, lastv;
    T lastans;
    bool have_ans;

    hash_map_t (int md = 0) {
        head.clear(); v.clear(); val.clear(); nxt.clear(); tot = 0; mod = md;
        nxt.resize(1); v.resize(1); val.resize(1); head.resize(mod);
        have_ans = 0;
    }

    void clear() { *this = hash_map_t(mod); }

    bool count(int x) {
        int u = x % mod;
        for(register int i = head[u]; i; i = nxt[i]) {
            if(v[i] == x) {
                have_ans = 1;
                lastv = x;
                lastans = val[i];
                return 1;
            }
        }
        return 0;
    }

    void ins(int x, int y) {
        int u = x % mod;
        nxt.push_back(head[u]); head[u] = ++tot;
        v.push_back(x); val.push_back(y);
    }

    int qry(int x) {
        if(have_ans && lastv == x) return lastans;
        count(x);
        return lastans;
    }
};

const int N = 1e5 + 5;

char c[N];
int f[N][400], g[400], now[400], ans[N];
int n;

void gen_g() {
    now[101] = 1; int len = 101, cnt = 0;
    while(len) {
        g[++cnt] = now[1] & 1;
        for(register int i = len; i >= 1; i--) {
            if(now[i] & 1) now[i - 1] += 10;
            now[i] >>= 1;
        }
        while(len && !now[len]) --len;
    }
}

int main() {
    scanf("%s", c + 1); n = strlen(c + 1);
    for(register int i = 1; i <= n; i++) f[i][0] = i + (c[i] == 'L' ? -1 : 1);
    for(register int j = 1; j < 400; j++) {
        for(register int i = 1; i <= n; i++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    gen_g();
    for(register int i = 1; i <= n; i++) {
        int now = i;
        for(register int j = 0; j < 400; j++) {
            if(g[j]) {
                now = f[now][j];
            }
        }
        ++ans[now];
    }
    for(register int i = 1; i <= n; i++) print(ans[i], i == n ? '\n' : ' ');
    return 0;
}

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;
using ld = long double;
const int MOD = 1e9+7;


int main() {
    int k; cin >> k;
    int x = 7 % k;
    for(int i = 1; i <= k; i++){
        if(x == 0) {
            cout << i << endl;
            return 0;
        }
        x = (x * 10 + 7) % k;
    }
    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int N,i,j=0;
    int p[30];
    cin>>N;
    for(i=0;i<N;i++)
    {
        cin>>p[i];
    }
    sort(p,p+N);
    p[N-1]=p[N-1]/2;
    for(i=0;i<N;i++)
    {
        j=j+p[i];
    }
    cout<<j<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline char nc() {
	static char b[100000],*s=b,*t=b;
	return s==t&&(t=(s=b)+fread(b,1,100000,stdin),s==t)?-1:*s++;
}
inline void read(int &x) {
	char b = nc(); x = 0;
	for (; !isdigit(b); b = nc());
	for (; isdigit(b); b = nc()) x = x * 10 + b - '0';
}
const int N = 100005;
int f[N][17], n, d, q, x[N];
int solve(int l, int r) {
	int res = 0;
	for (int i = 16; ~i; --i)
		if (f[l][i] && f[l][i] < r)
			l = f[l][i], res += (1 << i);
	return res + 1;
}
int main() {
	read(n);
	for (int i = 1; i <= n; ++i) read(x[i]);
	read(d); read(q);
	for (int i = 1; i < n; ++i) {
		f[i][0] = upper_bound(&x[i+1], &x[n+1], x[i] + d) - 1 - x;
	}
	for (int j = 1; j < 17; ++j)
		for (int i = 1; i < n; ++i)
			f[i][j] = f[f[i][j-1]][j-1];
	for (int l, r; q--;) {
		read(l); read(r);
		if (l > r) swap(l, r);
		printf("%d\n", solve(l, r));
	}
	return 0;
}

Measured memory_bytes: 7936
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    
    vector<ll> b(n);
    iota(ALL(b), 0);
    sort(ALL(b), [&](int x,int y){
        return a[x] < a[y];
    });
    rep(i, n)cout << b[i]+1 << " ";
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=1e9+7;
const int size=1e5;
const int inf=1e9;
long calc(long a, long b){
	return a*a*a*a + a*a*a*b + a*a*b*b + a*b*b*b + b*b*b*b;
}
int main(){
	long X; cin>>X;
	for(int i = 1; i * i <= X; i++){
		if(X % i) continue;
		rep(j,0,10000){
			if(calc(j, j-i) == X / i){ cout<<j<<" "<<j-i<<endl; return 0; }
			if(calc(j, j-X/i) == i){ cout<<j<<" "<<j-X/i<<endl; return 0; }
		}
	}
}

Measured memory_bytes: 3636
void main() {
	auto s = rs;
	writeln(s[0], s.length-2, s[$-1]);
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

#define int long long

signed main() {
    string s;
    cin >> s;
    if(s[0]=='9'||s[1]=='9') cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  char b; cin >> b;
  char ans;
  switch(b){
    case 'A': ans = 'T'; break;
    case 'T': ans = 'A'; break;
    case 'G': ans = 'C'; break;
    case 'C': ans = 'G'; break;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main() {
	int n;
	char s[10005];

	scanf("%d", &n);
	scanf("%s", s);

	for(int i = 0; s[i] != '\0'; i++) {
		s[i] = 'A' + (s[i] - 'A' + n) % 26;
	}

	puts(s);

	return 0;
}

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

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> h(n);
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    sort(h.begin(),h.end());
    int res=2*1e9;
    for(int i=0;i<=n-k;i++){
        res=min(res,h[i+k-1]-h[i]);
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 768