akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int mod = 1e9 + 7;
const int N = 200005;
const int K = 10;
int a[N], d[N];
vector < int > g[N];
map < pair < int, int >, int > mp;
int binpow(int x, int y){
    if (y == 0) return 1;
    if (y % 2) return x * binpow(x, y - 1) % mod;
    int z = binpow(x, y / 2);
    return z * z % mod;
}
int dfs(int v, int p = -1){
    int mx = 0;
    int s = 0;
    for (auto u: g[v]){
        if (u == p) continue;
        int x = dfs(u, v);
        s += x;
        mx = max(mx, x);
    }
   // cout << "v = " << v << endl;
    if (d[v] == 1) return a[v];
    int x = 2 * a[v] - s;
    int y = s - a[v];
   // cout << v << " " << x << " " << y << " " << mx << " " << s << " " << a[v] << endl;
    if (y > s - mx || y < 0 || x < 0){
        cout << "NO";
        exit(0);
    }
    if (p == -1){
        if (x == 0){
            cout << "YES";
        } else cout << "NO";
        exit(0);
    }
    return x;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        d[u]++;
        d[v]++;
    }
    if (n == 2){
        if (a[1] == a[2]){
            cout << "YES";
        } else{
            cout << "NO";
        }
        return 0;
    }
    for (int i = 1; i <= n; i++){
        if (d[i] != 1){
            dfs(i);
        }
    }
}


Measured memory_bytes: 15616
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define PI 3.141592653589793
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vll B(0);
  ll bsize = 0;
  for(int i = 0; i < N; i++){
    ll A;
    cin >> A;
    if(i == 0){
      B.push_back(A);
      bsize++;
    }
    else if(B.at(0) < A){
      B.at(0) = A;
    }
    else if(B.at(bsize-1) >= A){
      B.push_back(A);
      bsize++;
    }
    else{
      auto ite = lower_bound(B.rbegin(), B.rend(), A);
      ite--;
      *ite = A;
      /*
      int ok = bsize-1;
      int ng = 0;
      while(ok - ng > 1){
        int mid = (ok + ng) / 2;
        if(B.at(mid) < A) ok = mid;
        else ng = mid;
      }
      B.at(ok) = A;
      */
    }
  }
  cout << B.size() << endl;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,w,a,b;
    cin>>n>>w;
    vector<ll> dp(w+1,0);//dp(weight)=maximum value we can get with exactly this weight
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        for(ll x=w-a;x>=0;x--)
        {  // cout<<"\n"<<a+x<<" "<<dp[a+x]<<" status 22"<<endl;
           //     cout<<(b+dp[x])<<" status 1"<<endl;
            dp[a+x]=max(dp[a+x],b+dp[x]);
           // cout<<dp[a+x]<<endl;
        }
    }
    ll p=0;
   
    for(ll i=0;i<=w;i++)
    {
        p=max(p,dp[i]);
    }
    cout<<p<<endl;
    return 0;
}


Measured memory_bytes: 4048
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
template <class T> inline void dump(T &v){irep(i, v){cout<<(*i)<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;



int main() {
    
    int n;
    cin>>n;
    vi v(n);
    rep(i,n)cin>>v[i];
    int ans=0;
    rep(i,n){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(v[i]==v[j])continue;
                if(v[i]==v[k])continue;
                if(v[k]==v[j])continue;
                if(v[i]+v[j]>v[k]&&v[i]+v[k]>v[j]&&v[k]+v[j]>v[i]){
                    ans++;
                    // cout<<v[i]<<" "<<v[j]<<" "<<v[k]<<endl;
                    // cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
                    // cout<<endl;
                }
            }
        }
    }
    fin(ans);
}

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

int main() {
    string S;
    cin >> S;
    int N = S.size();
    long long ans = 0;

    for(int bit = 0; bit < (1<<N-1); bit++){
        long long tmp = 0;
        for(int i = 0; i < N-1; i++){
            tmp = tmp * 10 + (S[i] - '0');
            if( (bit>>i) & 1){
                ans += tmp;
                tmp = 0;
            }
        }
        tmp = tmp * 10 + (S[N-1] - '0');
        ans += tmp;
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath> 
#include <cctype>

using namespace std;

int main() {
    int N;
    int count_p = 0;
    int count_w = 0;
    int count_g = 0;
    int count_y = 0;
    cin >> N;
    char s[N];
    for (int i = 0; i < N; i++) {
        cin >> s[i];
    }

    for (int i = 0; i < N; i++) {
        if (s[i] == 'P') {
            count_p++;
        } else if (s[i] == 'W') {
            count_w++;
        } else if (s[i] == 'G') {
            count_g++;
        } else if (s[i] == 'Y') {
            count_y++;
        }
    }

    if ((count_p >= 1) && (count_w >= 1) && (count_g >= 1)  && (count_y >= 1)) {
        cout << "Four" << endl;
    } else {
        cout << "Three" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define forn(i, s, t) for (int i = s ; i < (int)t ; i++)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pf2(x,y) printf("%d %d\n",x,y)
#define pf(x) printf("%d\n",x)
#define each(x) for(auto it:x)  cout<<it<<endl;
#define pi pair<int,int>
#define pb push_back
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y) 
#define pf(x) printf("%d\n",x)
#define pf2(x,y) printf("%d %d\n",x,y)
#define mem(a,x) memset(a,x,sizeof(a))
#define copy(b,a) memcpy(a,b,sizeof(a))
#define SZ(x) (int)x.size()
#define VI vector<int> 
#define VII vector<pair<int,int>> 
#define PI pair<int,int>
using namespace std;
typedef long long ll;
ll mul(ll x,ll y,ll p){ll t=x*y-ll((long double)x*y/p)*p;return t<0?t+p:t;}
ll add(ll x,ll y,ll p){x+=y;if(x>=p) x-=p;if(x<0) x+=p;return x;}
ll qpow(ll x,ll y,ll p){ll ans=1;for(x%=p;y;y>>=1,x=x*x%p)if(y&1) ans=ans*x%p;return ans;}
ll inv(ll x,ll p){return x<=1?1:(p-p/x)*inv(p%x,p)%p;}
ll sqrt2(ll x){ll l=1,r=2e9;while(l<r){ll mid=(l+r+1)>>1;if(mid*mid<=x) l=mid;else r=mid-1;}return l;}
ll sqrt3(ll x){ll y=(ll)(powl((long double)x,1.0/3.0)+0.5);while(y*y*y<x) y++;while(y*y*y>x) y--;return y;}
ll comb(ll n,ll m,ll p){if(m>n||n<0) return 0;if(m>n-m) m=n-m;ll ans=1;for(int i=1;i<=m;i++)ans=ans*n%p,ans=ans*inv(i,p),n--;return ans;}
ll comb(ll n,ll m){if(m>n||n<0) return 0;if(m>n-m) m=n-m;ll ans=1;for(int i=1;i<=m;i++)ans=ans*n,ans/=i,n--;return ans;}
ll ceil(ll x,ll y){return (x+y-1)/y;}
int lowerbit(int x) {return x&-x;}
int HighBit(int x){for(int i=30;i>=0;i--)if(x>>i&1) return i;}
const int maxn=1e5+5;
int X,Y,A,B,C,p[maxn],q[maxn],r[maxn];
ll ans;
int main(){
	sc2(X,Y),sc2(A,B),sc(C);
	forn(i,0,A) sc(p[i]);
	forn(i,0,B) sc(q[i]);
	forn(i,0,C) sc(r[i]);
	sort(p,p+A,greater<int>());
	sort(q,q+B,greater<int>());
	sort(r,r+C,greater<int>());
	int id_p=X-1,id_q=Y-1;
	ll cost=0;
	forn(i,0,X)
		cost+=p[i];
	forn(i,0,Y)
		cost+=q[i];
	ans=cost;
	for(int i=1;i<=min(C,X+Y);i++){
		cost+=r[i-1];
		if(id_q<0 || (id_p>=0 && p[id_p]<=q[id_q])) cost-=p[id_p--];
		else cost-=q[id_q--];
		ans=max(ans,cost);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1536
int main()
{
    int n,a[200],i,cnt=-1,flag=1;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    while (flag) {
        cnt++;
        for(i=0;i<n;i++){
            if(a[i]%2==1){
                flag=0;
            }
            a[i] /= 2;
        }
    }
    printf("%d\n",cnt);
}

Measured memory_bytes: 128
#include <stdio.h>

int main() {
  int n,m,i,j,cnt=0;
  scanf("%d",&n);
  int a[n];
  for(i=0; i<n; i++) scanf("%d",&a[i]);
  scanf("%d",&m);
  for(i=0; i<m; i++) {
    int x;
    scanf("%d",&x);
    for(j=0; j<n; j++) {
      if(a[j]==x) {
	cnt++;
	break;
      }
    }
  }
  printf("%d\n",cnt);
  return 0;
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000011
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
 
int main(){
  int n,d;
  cin>>n>>d;
  cout<<(n+2*d)/(2*d+1)<<endl;
 
 
}

Measured memory_bytes: 256
from itertools import combinations
h, w, k = map(int,input().split())
c = [list(input()) for _ in range(h)]

def cnt(i, j):
    res = 0
    for s in combinations(range(h),i):
        for t in combinations(range(w), j):
            count = 0
            for u in range(h):
                for v in range(w):
                    if u in s:continue
                    if v in t:continue
                    if c[u][v] == '#':
                        count += 1
            if count == k:res += 1
    return res    

ans = 0
for i in range(h + 1):
    for j in range(w + 1):
        ans += cnt(i, j)
print(ans)

Measured memory_bytes: 9180
#include <iostream>
#include <math.h>
#include <algorithm>
#include <queue>
#include <map>
#include <list>
#include <set>
//#include <bits/stdc++.h>


using namespace std;

#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
typedef long long ll;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    vector<vector<pair<int,int>>> road(n);
    FOR(i, 0, n) { cin >> h[i]; }

    FOR(i, 0, m) {
        int a, b;
        cin >> a >> b;
        road[a-1].push_back(make_pair(a-1,b-1)); 
        road[b-1].push_back(make_pair(b-1,a-1)); 
    }

    int ans = 0;
    FOR(i, 0, n) {
        bool flag = true;
        FOR(j, 0, road[i].size()) {
            if(h[i] <= h[road[i][j].second]) {
                flag = false;
                break;
            }
        }
        if(flag) { ans++; }
    }
    cout <<  ans << endl;
    return 0;
}

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

MOD = 10**9 + 7
def inv(a):
	b = MOD
	u = 1
	v = 0
	while b > 0:
		t = a // b
		a -= t*b
		a,b = b,a
		u -= t*v
		u,v = v,u
	u %= MOD
	return u

def gcd(a,b):
	if a > b:
		a,b = b,a
	while b % a > 0:
		tmp = b % a
		b = a
		a = tmp
	return a

lcm = 1
for a in A:
	lcm = lcm * a // gcd(lcm, a)

L = lcm % MOD
ans = 0
for a in A:
	ans = (ans + L * inv(a)) % MOD
print(ans)

Measured memory_bytes: 42460
#####################################################
# 組み合わせを10**9+7で割った余り、を高速に求めるアルゴリズム
# https://drken1215.hatenablog.com/entry/2018/06/08/210000
# https://qiita.com/derodero24/items/91b6468e66923a87f39f
# 全然理解できていない
MOD = 10**9 + 7


def comb(n, r):
    if (r < 0 and r > n):
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

N = 10**6
# 元テーブル
g1 = [1, 1]
# 逆元テーブル
g2 = [1, 1]
# 逆元テーブル計算用テーブル
inverse = [0, 1]

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)


#####################################################

X, Y = map(int, input().split())

# X+Yが3の倍数のマスしか通りえない
if not (X + Y) % 3:

    # (1,2)移動をn回、(2,1)移動をm回したとする
    # n+2m = X, 2n+m = Y
    # → n+m = (X+Y)/3
    # n = (2n+m)-(n+m) = X - (X+Y)/3 = (-X+2Y)/3
    # mも同様
    n = (2 * Y - X) // 3
    m = (2 * X - Y) // 3

    if n >= 0 and m >= 0:
        print(comb(n + m, n))
    else:
        print(0)

# X+Yが3の倍数でない場合
else:
    print(0)


Measured memory_bytes: 127924
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

bool solve(){
  ll n;cin>>n;
  vector<vector<ld>>dp(n+1,vector<ld>(n+1,0));
  dp[0][0]=1;
  rep(i,n){
    ld p;cin>>p;
    rep(j,n){
      dp[i+1][j+1]+=dp[i][j]*p;
      dp[i+1][j]+=dp[i][j]*(1-p);
    }
  }
  ld ans=0;
  rep(i,n+1)if(i>n-i)ans+=dp[n][i];
  cout<<ans<<endl;

  return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


Measured memory_bytes: 141056
h,w,k = map(int,input().split())
s = []
for i in range(0,h):
    s.append(str(input()))
ans = 0
for bit_h in range(1 << h):
    for bit_w in range(1 << w):
        kuro = 0
        for tate in range(h):
            for yoko in range(w):
                if bit_h & (1 << tate) or bit_w & (1 << yoko):
                    kuro = kuro
                else:
                    if (s[tate])[yoko] == '#':
                        kuro += 1
        if kuro == k:
            ans += 1
print(ans)


Measured memory_bytes: 9108
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var dg = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
        var d = dg[0];
        var g = dg[1] / 100;
        var ps = new int[d];
        var cs = new int[d];
        for (int i = 0; i < d; i++)
        {
            var pc = Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray();
            ps[i] = pc[0];
            cs[i] = pc[1] / 100;
        }

        var totals = E.Range(0, d).Select(i => (i + 1) * ps[i] + cs[i]).ToArray();
        var full = ps.Sum();
        var dp = new int[1 + full];
        for (int i = 0; i < d; i++)
        {
            for (int j = full; j >= ps[i]; j--)
            {
                dp[j] = Math.Max(dp[j], dp[j - ps[i]] + totals[i]);
            }
            for (int j = ps[i]; j > 0; j--)
            {
                var p = Math.Min(ps[i] - 1, j);
                for (int k = 0; k < p; k++)
                {
                    int kk = k + 1;
                    dp[j] = Math.Max(dp[j], dp[j - kk] + (i + 1) * kk);
                }
            }
        }
        Console.WriteLine(dp.TakeWhile(x => x < g).Count());
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  double A,B;
  cin>>A>>B;
  if(A<=(10*B*0.08)&&(10*B*0.08)<A+1){
    cout<<10*B<<endl;
  }
  else if (A<=(10*B+1)*0.08&&(10*B+1)*0.08<A+1){
    cout<<(10*B+1)<<endl;
  }
  else if (A<=(10*B+2)*0.08&&(10*B+2)*0.08<A+1){
    cout<<(10*B+2)<<endl;
  }
  else if (A<=(10*B+3)*0.08&&(10*B+3)*0.08<A+1){
    cout<<(10*B+3)<<endl;
  }
  else if (A<=(10*B+4)*0.08&&(10*B+4)*0.08<A+1){
    cout<<(10*B+4)<<endl;
  }
  else if (A<=(10*B+5)*0.08&&(10*B+5)*0.08<A+1){
    cout<<(10*B+5)<<endl;
  }
  else if (A<=(10*B+6)*0.08&&(10*B+6)*0.08<A+1){
    cout<<(10*B+6)<<endl;
  }
  else if (A<=(10*B+7)*0.08&&(10*B+7)*0.08<A+1){
    cout<<(10*B+7)<<endl;
  }
  else if (A<=(10*B+8)*0.08&&(10*B+8)*0.08<A+1){
    cout<<(10*B+8)<<endl;
  }
  else if (A<=(10*B+9)*0.08&&(10*B+9)*0.08<A+1){
    cout<<(10*B+9)<<endl;
  }
  else{
    cout<<"-1"<<endl;
  }
}

Measured memory_bytes: 256
import math

def euclid(a, b):
    if a == b:
        return a
    elif b > a:
        return euclid(b, a)
    else:
        while b > 0:
            temp = a % b
            a = b
            b = temp
        return a


def get_e(x):
    l = []
    i = 2
    m = math.floor(math.sqrt(x))
    while i <= m and i <= x:
        if x % i == 0:
            x = x // i
            l += [i]
        else:
            i += 1
    if x != 1:
        l += [x]
    return l


def calc(A, B):
    gcd = euclid(A, B)
    if gcd == 1:
        return 1
    else:
        return 1 + len(set(get_e(gcd)))


(A, B) = tuple([int(s) for s in input().split(' ')])
print(calc(A, B))

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

struct Town { int x, y; };
double length(const Town& a, const Town& b) {
  int dx = (b.x - a.x);
  int dy = (b.y - a.y);
  return sqrt(dx * dx + dy * dy);
}

int main() {
  int N; cin >> N;
  Town town[10];
  for (int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    town[i] = Town{ x, y };
  }
  
  vector<int> p;
  for (int i = 0; i < N; ++i) { p.push_back(i); }
  
  double sum = 0;
  int n = 0;
  do {
    for (int i = 1; i < N; ++i) { 
      double len = length(town[p[i - 1]], town[p[i]]);
      sum += len;
    }
    n++;
  } while (next_permutation(p.begin(), p.end()));
  
  printf("%f\n", (double)sum / n);
}
  



Measured memory_bytes: 256
import sys
N, M = list(map(int, input().split()))
S = set()
B = [False] * (N + 1)
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1:
        S.add(b)
    elif b == N:
        B[a] = True
for s in S:
    if B[s]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')


Measured memory_bytes: 18960
n = int(input())
count = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]

for i in range(n):
  b, f, r, v = map(int, input().split())
  count[b-1][f-1][r-1] += v

for i in range(4):
  if i != 0:
      print("#"*20)
  for j in range(3):
      for k in range(10):
        print(" %d"%(count[i][j][k]), end="")
      print()
    
   


Measured memory_bytes: 5624
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n, m;
    cin >> n >> m;
    atcoder::dsu ds(n);
    REP(_,m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        ds.merge(a,b);
    }
    set<int> st;
    REP(i,n) {
        st.insert(ds.leader(i));
    }
    OUT(st.size()-1)

    return 0;
}

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

int main()
{
  int n{};
  for(int i = 0; i < 4; ++i){
    char c; std::cin >> c;
    if(c == '+')
      ++n;
    else
      --n;
  }
  std::cout << n << std::endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.nextLine();
		String T = sc.nextLine();
		int ans = 0;
		
		for(int i = 0; i < S.length(); i++) {
			if(S.charAt(i)!=T.charAt(i)) ans++;
		}
		System.out.println(ans);
	}

}


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

int saiki(int n, int s, int i, int *result){
    if(n <= 0){
        if(s == 0){
            *result += 1;
        }
    }else{
        for(int j=i;j<10;j++){
            saiki(n-1,s-j,j+1,result);
        }
    }
}
int main(){
    int n, s;
    int result;
    cin >> n >> s;
    while(n || s){
        result = 0;
        saiki(n, s, 0, &result);
        cout << result << endl;
        cin >> n >> s;
    }
    return 0;
}

Measured memory_bytes: 0
N = int(input())
A = list(map(int, input().split()))
d = dict()
for i in range(N):
    if d.get(A[i]) is None:
        d[A[i]] = 1
    else:
        d[A[i]] += 1
ans = 0
for key, value in d.items():
    if key <= value:
        ans += value - key
    else:
        ans += value
print(ans)




Measured memory_bytes: 21844
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()


show_flg=False
show_flg=True
ans=0


h1,m1,h2,m2,k=LI()

x=h2*60+m2-h1*60-m1
ans=x-k

print(ans)






Measured memory_bytes: 78208
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  long long int ans=0;
  int mod = 1000000007;
  cin >> N;
  vector<long long int> list(N);
  for (int i=0;i<N;i++) {
    cin >> list.at(i);
  }
  vector<long long int> num1(60,0);
  for (int i=0;i<60;i++) {
    for (int j=0;j<N;j++) {
      //if (((long long int)1<<i)&list.at(j)) num1.at(i)++;
      num1.at(i)+=((long long int)1)&(list.at(j)>>i);
    }
  }
  long long int ks=1;
  for (int i=0;i<60;i++) {
    ans = (ans + (ks*num1.at(i)%mod*(N-num1.at(i)%mod))%mod)%mod;
    ks = (ks*2)%mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2560
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: "List[int]", A: "List[int]"):
    t, a = 1, 1
    for i in range(N):
        if T[i] == A[i]:
            tmp = max(t, a)
            t = tmp
            a = tmp
        elif t <= a / A[i] * T[i]:
            a = ((a - 1) // A[i] + 1) * A[i]
            t = (a // A[i]) * T[i]
        else:
            t = ((t - 1) // T[i] + 1) * T[i]
            a = (t // T[i]) * A[i]
        #print(T[i], A[i], t, a)
    ret = a + t
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = [int()] * (N)  # type: "List[int]" 
    A = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        T[i] = int(next(tokens))
        A[i] = int(next(tokens))
    solve(N, T, A)

if __name__ == '__main__':
    main()


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

using namespace std;

typedef long long ll;
struct P{double x, y;};

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

	int n;
	cin >> n;

	string s;
	cin >> s;

	if(n % 2 == 1){
		cout << "No" << endl;
	}else{
		rep(i, n/2){
			if(s[i] != s[i + n/2]){
				cout << "No" << endl;
				return 0;
			}
		}
		cout << "Yes" << endl;
	}
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;
using static AtCoderTemplate.MyLibrary;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main (string[] args)
        {
            string[] str;

            int[, ] A = new int[3, 3];

            for (int i = 0; i < 3; i++)
            {
                str = Console.ReadLine ().Split (' ');
                A[i, 0] = int.Parse (str[0]);
                A[i, 1] = int.Parse (str[1]);
                A[i, 2] = int.Parse (str[2]);
            }
            str = Console.ReadLine ().Split (' ');
            int N = int.Parse (str[0]);

            for (int i = 0; i < N; i++)
            {
                str = Console.ReadLine ().Split (' ');
                int b = int.Parse (str[0]);

                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 3; k++)
                    {
                        if (A[j, k] == b)
                        {
                            A[j, k] = 0;
                            break;
                        }
                    }
                }
            }

            for (int i = 0; i < 3; i++)
            {
                if (A[i, 0] + A[i, 1] + A[i, 2] == 0 || A[0, i] + A[1, i] + A[2, i] == 0)
                {
                    Console.Write ("Yes");
                    return;
                }
            }

            if (A[0, 0] + A[1, 1] + A[2, 2] == 0 || A[0, 2] + A[1, 1] + A[2, 0] == 0)
            {
                Console.Write ("Yes");
                return;
            }
            Console.Write ("No");
        }
    }

    class MyLibrary
    {
        public static int GCD (int a, int b)
        {
            if (a % b == 0) return b;
            return GCD (b, a % b);
        }
    }
}

Measured memory_bytes: 27468
n = int(input())
s_original = [int(input()) for _ in range(n)]

S = sorted(s_original)
SUM = sum(S)
ANS = []

if SUM%10 != 0:
    ANS.append(SUM)

for i in range(n):
    ans = SUM - S[i]
    if ans%10 != 0:
        ANS.append(SUM - S[i])

if ANS == []:
    print(0)
else:
    print(max(ANS))

Measured memory_bytes: 3064
#include "stdio.h"
#include <stdlib.h>

typedef struct {
    int flag;
    int check[100];
    long long int v;
} bigint;

void clear_A(int*A){
  for (size_t i = 0; i < 100; i++) {
    A[i]=0;
  }
}

void  dainyuu_A(int*A,int*B) {
  for (size_t i = 0; i < 100; i++) {
    A[i]=B[i];
  }
}

int main(int argc, char const *argv[]) {
  int N,W,i,j;
  scanf("%d%d", &N,&W);
  bigint A[W+1];
  long long int V[N];
  int w[N];
  long long int ans=0;
  for (i = 0; i < N; i++) {scanf("%d%lld", &w[i],&V[i]);}

  for (i = 0; i <= W; i++) {A[i].flag=0;A[i].v=0;clear_A(A[i].check);}

  for (i = 0; i <= W; i++) {
    for (j = 0; j < N; j++) {
      if (i==w[j] && A[i].v < V[j]) {
        A[i].flag=1;
        A[i].v=V[j];
        clear_A(A[i].check);
        A[i].check[j]=1;
      }
      if (i-w[j]>0 && A[i-w[j]].flag==1 && A[i].v<A[i-w[j]].v+V[j] && A[i-w[j]].check[j]==0) {
        A[i].flag=1;
        A[i].v=A[i-w[j]].v+V[j];
        dainyuu_A(A[i].check,A[i-w[j]].check);
        A[i].check[j]=1;
      }
    }
  }

  for (i = 0; i <= W; i++) {if (A[i].v>ans) {ans=A[i].v;}}
  printf("%lld", ans);
  return 0;
}


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

int main() {
	int N;
	cin >> N;
	deque<int> A(N + 2);
	rep(i, 0, N) cin >> A[i];

	A.push_front(0);  A.push_back(0);
	ll sum = 0;
	rep(i, 0, N + 1) sum += abs(A[i] - A[i + 1]);
	rep(i, 1, N + 1) {
		cout << sum + abs(A[i - 1] - A[i + 1]) - abs(A[i - 1] - A[i]) - abs(A[i] - A[i + 1]) << endl;
	}

	return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#include <string>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) (a)=max(a, b)
#define chmin(a, b) (a)=min(a, b)
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/


 
int main(void) {
  ll i, j, k;
  
  string s;
  cin >> s;
  ll Q;
  cin >> Q;
  ll r=0;
  deque<char> q;
  
  for(i=0; i<s.size(); i++) q.push_back(s[i]);
  
  for(ll _=0; _<Q; _++) {
    ll t;
    cin >> t;
    if(t==1) {
      r=1-r;
    }else {
      ll f; char c; cin >> f >> c;
      if(f%2==r%2) q.push_back(c);
      else q.push_front(c);
    }
  }
  
  if(r==0) {
    for(i=0; i<q.size(); i++) cout << q[i];
    pt("");
  }else {
    for(i=(ll)q.size()-1; i>=0; i--) cout << q[i];
    pt("");
  }
  
}
 
 


Measured memory_bytes: 896
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<string>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,K=200005,mod=1000000007;
const long long llinf=9223372036854775807ll;
//int & long long
long long h,n,a[10005],b[10005],dp[20005],ans;
int main()
{
	ans=inf;
	cin>>h>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for(int i=1;i<20005;i++)
		dp[i]=inf;
	for(int i=1;i<20005;i++)
	{
		for(int j=1;j<=n;j++)
			if(a[j]<=i)
				dp[i]=min(dp[i],dp[i-a[j]]+b[j]);
		if(i>=h)
			ans=min(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main() {
	int n;
	while (cin >> n&& n!=0) {
		int f[21][21] = {};

		for (int i = 0; i<n; i++) {
			int x, y;
			cin >> x >> y;
			f[y][x] = 1;
		}

		int x = 10, y = 10;
		int cnt = 0;

		int m;
		cin >> m;
		for (int i = 0; i<m; i++) {
			char dir;
			int step;
			cin >> dir >> step;
			while (step--) {
				if (dir == 'N') { y++; }
				else if (dir == 'S') { y--; }
				else if (dir == 'E') { x++; }
				else { x--; }

				if (f[y][x]) {
					f[y][x] = 0;
					cnt++;
				}
			}
		}

		if (cnt == n) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}

	return 0;
}


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

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

int main() {
	string S;
	cin >> S;
	
	int n = S.size();
	if (n == 2 && S[0] == S[1]) {
		puts("1 2");
		exit(0);
	}
	
	for_(i,0,n-2) {
		if (S[i] == S[i+1] || S[i] == S[i+2]) {
			cout << i+1 << " " << i + 3 << endl;
			exit(0);
		}
	}
	
	puts("-1 -1");
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		
		int[] teishutu = new int[31]; 
		
		for(int i = 0;i < 28 ;i++){
			int a = scan.nextInt();
			
			teishutu[a] = 1;
		}
		
		for(int i = 1;i < 31;i++){
			if(teishutu[i] == 0){
				System.out.println(i);
			}
		}
		
	}
}

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

int main(void) {

  int Fi[64];
  int n;

  std::cin >> n;
  
  Fi[0] = 1;
  Fi[1] = 1;
  for(int i = 2; i <= n; ++i) {
    Fi[i] = Fi[i - 1] + Fi[i - 2];
  }

  std::cout << Fi[n] << std::endl;

  return 0;
}

Measured memory_bytes: 1164
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;


namespace StartFinish
{
 
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int[] hw = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();


                if (hw[0] == 0 && hw[1] == 0)
                {
                    break;
                }
                for(int i = 0; i < hw[0]; i++)
                {
                    if (i == 0||i==hw[0]-1)
                    {
                        for(int j = 0; j < hw[1]; j++)
                        {
                            Console.Write("#");
                        }
                    }else
                    {
                        for(int j = 0; j < hw[1]; j++)
                        {
                            if (j == 0||j==hw[1]-1)
                            {
                                Console.Write("#");
                            }else
                            {
                                Console.Write(".");
                            }
                        }
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
              
            }
        }
    }
}

Measured memory_bytes: 9292
#include <bits/stdc++.h>
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define per(a, b, c) for(int a = (b); a >= (c); -- a)
using namespace std;
template <class T> void rd(T &x){
  x = 0; int f = 1; char ch = getchar();
  while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}

typedef long long ll;
const int mod = 1e6 + 3;
const int maxn = 2e6 + 10;
ll fac[maxn], fin[maxn];
int x, d, n;

ll power(ll x, ll n){
  ll y = 1;
  for(; n; n >>= 1, x = x * x % mod)
    if(n & 1) y = y * x % mod;
  return y;
}

#define inv(x) power(x, mod - 2)

void init(int n){
  fac[0] = 1; rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
  fin[n] = inv(fac[n]);
  per(i, n, 1) fin[i - 1] = fin[i] * i % mod;
}

void work(){
  rd(x), rd(d), rd(n);
  if(d == 0){
    printf("%lld\n", power(x, n));
    return ;
  }
  if(x == 0){
    printf("%lld\n", fac[n] * power(d, n) % mod);
    return ;
  }
  ll t = (ll) x * inv(d) % mod;
  if(n >= mod || t + n - 1 >= mod) return (void) (puts("0"));
  printf("%lld\n", fac[t + n - 1] * fin[t - 1] % mod * power(d, n) % mod);
}

int main(){
  init(mod - 1);
  int q; rd(q);
  while(q --) work();
  return 0;
}



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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; ++i)
        cin >> a[i];

    int count = 0;
    while(1){
        for(int i=0; i<n; ++i){
            if(a[i]&1){
                cout << count;
                return 0;
            }
            a[i] /= 2;
        }
        count++;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits>

int main(){
  long a,b,c,d;
  std::cin >> a >> b >> c >> d;
  long temp = std::max(std::max(a*d,a*c),std::max(b*d,b*c));
  if(a*b<=0 || c*d<=0){
    temp = std::max((long)0,temp);
  }
  std::cout << temp << std::endl;
  return 0;
}

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

int div2(long long num) {
    if (num % 2 == 1) {
        return 0;
    } else {
        return div2(num / 2) + 1;
    }
}
int main() {
    long long N;
    cin >> N;
    vector<long long> a(N);
    for (long long i = 0; i < N; i++) {
        cin >> a[i];
    }
    long long ans = 0;
    for (long long i = 0; i < N; i++) {
        ans += div2(a[i]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
#define ii for(int i=1;i<=n;++i)
#define ji for(int j=1;j<=n;++j)
#define jj for(int j=1;j<=m;++j)
#define ij for(int i=1;i<=m;++i)
#define sz(x) ((ll)x.size())
#define all(x) x.begin(),x.end()
#define alll(x) x+1,x+1+n
#define asd cout<<"ok"<<endl;
#define endl '\n'

int a[22];
int main()
{
    int l;
    cin >> l;
    if(l&(1<<19))
    {
        int m = 0;
        vector<pair<int,int>> ans;
        int cur = 0;
        for(int i=19;i>=0;--i)
        {
            if(l&(1<<i))
            {
                if(i != 19) ans.push_back({i+1, cur});
                cur = cur + (1<<i);
            }
        }
        cout << 20 << " " << ans.size() + 38 << endl;
        for(int i=1;i<=19;++i)
        {
            cout << i << " " << i+1 << " " << 0 << endl;
            cout << i << " " << i+1 << " " << (1<<(i-1)) << endl;
        }
        for(auto p : ans) cout << p.first << " " << 20 << " " << p.second << endl;
    }
    else
    {
        int m = 0;
        vector<pair<int,int>> ans;
        int cur = 0;
        for(int i=0;i<=19;++i)
        {
            if(l&(1<<i))
            {
                ++m;
                ans.push_back({i+1, cur});
                cur = cur + (1<<i);
            }
        }
        cout << 20 << " " << m + 36 << endl;
        for(int i=1;i<=18;++i)
        {
            cout << i << " " << i+1 << " " << 0 << endl;
            cout << i << " " << i+1 << " " << (1<<(i-1)) << endl;
        }
        for(auto p : ans) cout << p.first << " " << 20 << " " << p.second << endl;
    }
}


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

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

using namespace std;
using lint=long long;

int main(){
	int n;
	lint k; scanf("%d%lld",&n,&k);
	vector<int> to(n);
	rep(u,n) scanf("%d",&to[u]), to[u]--;

	static int dbl[60][200000];
	rep(u,n) dbl[0][u]=to[u];
	rep(t,59) rep(u,n) dbl[t+1][u]=dbl[t][dbl[t][u]];

	int pos=0;
	rep(t,60) if(k>>t&1) pos=dbl[t][pos];
	printf("%d\n",pos+1);

	return 0;
}


Measured memory_bytes: 51044
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vvi vector< vector<int> >
#define vi vector<int>
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define shosu(X) fixed << setprecision(X)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
 
int main(){
  int n, l;
  cin >> n >> l;
  int sum = 0;
  REP(i, n) sum += (l+i);
  int sa = 0;
  int ans = 0;
  REP(i, n){
    if(i == 0 || abs(l+i) < sa){
      ans = sum - (l+i);
      sa = abs(l+i);
    }
  }
  cout << ans << endl;
}

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

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;
#define REP(i, n) for(ll i = 0LL; i < (ll)(n); i++)
#define REPR(i, n) for(ll i = n-1; i >= 0LL; i--)
#define FOR(i, n, m) for(ll i = n; i < (ll)(m); i++)
#define PRINT(x) cout << x << endl
#define ALL(v) v.begin(), v.end()
#define INF (ll)1e18
#define INFD 1e18
#define PI 3.14159265358979
#define MOD 1000000007
#define vl vector<ll>
#define Mat(T) vector<vector<T>>

vector<ll> dx = {-1, 1, 0, 0};
vector<ll> dy = {0, 0, 1, -1};

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main()
{
	ll N, K;
	cin >> N >> K;

	vector<ll> A(N);
	REP(i, N) cin >> A[i];
	REP(i, N) A[i]--;

	ll cnt = 0;
	ll now = 0;
	vector<ll> dp(N, -1);
	dp[0] = 0;
	while(1) {
		if (dp[A[now]] == -1) {
			cnt++;
			dp[A[now]] = cnt;
			now = A[now];
		} else {
			break;
		}
	}
	// PRINT(cnt);
	// PRINT(A[now]);
	// REP(i, N) {
	// 	cout << dp[i] << " ";
	// }
	// cout << endl;
	ll tmp = cnt - dp[A[now]];
	if (cnt >= K) {
		REP(i, N) {
			if (dp[i] == K) {
				PRINT(i+1);
				return 0;
			}
		}
	} else {
		K -= dp[A[now]];
		// PRINT(K);
		K %= tmp+1;
		// PRINT(K);
		REP(i, N) {
			if (dp[i] == K + dp[A[now]]) {
				PRINT(i+1);
				return 0;
			}
		}
	}

	return 0;
}


Measured memory_bytes: 6428
#include <vector>
#include <cstdio>
using namespace std;
int main(){
	int N,Q;
	long long q;
	scanf("%d%d",&N,&Q);
	vector<long long>v(N);
	for(int i=0;i<N;i++)scanf("%lld",&v[i]);
	for(;Q--;){
		scanf("%lld",&q);
		long long s=0,r=0;
		int start=0,stop=0;
		for(;;){
			for(;stop<N&&s+v[stop]<=q;stop++)s+=v[stop];
			for(;start<N&&s>q;start++)s-=v[start];
			if(start==N)break;
			r+=stop-start;
			if(start<N)s-=v[start++];
		}
		printf("%lld\n",r);
	}
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;   
#define ll long long
#define ull unsigned long long
// #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> 
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define inf 9e18
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// Comment this out for interactice problem
// #define endl '\n'
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output

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

    ll n;
    cin>>n;
    ll a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    sort(a, a+n);
    reverse(a, a+n);

    if(n==1){
        cout<<0;
    }
    else if(n==2){
        cout<<a[0];
    }
    else{
        ll ans=a[0];
        vector<ll> v;
        for (int i = 1; i < n; ++i)
        {
            v.push_back(a[i]);
            v.push_back(a[i]);
        }
        for (int i = 0; i < n-2; ++i)
        {
            ans+=v[i];
        }
        cout<<ans;
    }

    return 0;
}

Measured memory_bytes: 8988
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


bool check(string s) {
    if (s.length % 2) {
        return false;
    }
    while (!s.empty) {
        if (s[0 .. 2] != "hi") {
            return false;
        }
        s.popFront();
        s.popFront();
    }
    return true;
}

void main() {
    string s;
    scan(s);
    yes(check(s));
}



void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x > arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x < arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
 string s;
    
    while(cin>>s){
        int i=0;
        int c=0;
        if(s[0]=='0')break;
        for(int i=0;i<s.size();i++)c+=s[i]-'0';
         cout <<c<<endl;
    }
}


Measured memory_bytes: 3188
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
int dp[1000000];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  dp[0] = 1;
  long long ans = 0;
  long long s = 1;
  rep(i, N-1) {
    dp[i+1] = (s - (i-1>=0?dp[i-1]:0) + MOD) % MOD;
    s = (s + dp[i+1]) % MOD;
    int g = (1LL*(N-1)*(N-1)+(N-max(2, N-i-1)+1)) % MOD;
    ans = (1LL*dp[i]*g + ans) % MOD;
  }
  ans = (ans + 1LL * dp[N-1] * N) % MOD;
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 4224
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int v = sc.nextInt();
		int b = sc.nextInt();
		int w = sc.nextInt();
		int t = sc.nextInt();
		if (w >= v || Math.abs(a - b) / (double)(v - w) > t) {
		    System.out.println("NO");
		} else {
		    System.out.println("YES");
		}
	}
}


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

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if (e-a <= k) {
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
}


Measured memory_bytes: 256