akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int n, t, q;
vector<int> east, west;
pair<int, int> ad[100000 + 5];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> t >> q;
    rep(i, n) {
        cin >> ad[i].fi >> ad[i].se;
        if (ad[i].se == 1) east.pb(ad[i].fi);
        else west.pb(ad[i].fi);
    }
    rep(i, q) {
        int x;
        cin >> x;
        x--;
        int a = ad[x].fi;
        int d = ad[x].se;
        if (d == 1) {
            auto itr_w = lower_bound(all(west), a);
            int dist_w = distance(west.begin(), itr_w);
            if (dist_w == west.size()) {
                cout << a + t << endl;
                continue;
            }
            auto itr_e = lower_bound(all(east), *itr_w);
            itr_e--;
            cout << min(a + t, (*itr_e + *itr_w) / 2LL) << endl;
        }
        else {
            auto itr_e = lower_bound(all(east), a);
            int dist_e = distance(east.begin(), itr_e);
            if (dist_e == 0) {
                cout << a - t << endl;
                continue;
            }
            itr_e--;
            auto itr_w = lower_bound(all(west), *itr_e);
            cout << max(a - t, (*itr_e + *itr_w) / 2LL) << endl;
        }
    }

}

Measured memory_bytes: 5376
#include <iostream>
#include <cstring>
#include <limits.h>
using namespace std;
typedef long long ll;

ll inf = 1000000007;

int main(void){
    ll n, c[200020];
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    c[0]=0;
    ll dp[200020], color[200020];
    fill(color, color + 200001, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (c[i] == c[i - 1]) dp[i] = dp[i - 1];
        else dp[i] = color[c[i]] + dp[i - 1];
        if (c[i] != c[i - 1]) color[c[i]] += dp[i - 1];
        dp[i] %= inf;
        color[c[i]] %= inf;
        //cout << dp[i] << " " << color[1] << " " << color[2] <<" " << color[5] << endl;
    }
    
    cout << dp[n] % inf << endl;
    
    //for (int i = 1; i <= n; i++) cout << c[i] << " ";
    
    
}


Measured memory_bytes: 4992
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(void){
  long n;
  scanf("%ld",&n);
  for(long i=sqrt(n);i>=1;i--){
    
    if(n%i==0){
      printf("%ld",i+n/i-2);
      return 0;
    }
  }
  
}

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

long long solve(const string &S) {
    int N = S.size();
    vector<long long> val(2019, 0);
    long long fac = 1;
    long long cur = 0;
    val[cur]++;
    for (int i = 0; i < N; ++i) {
        long long add = S[N-1-i] - '0';
        cur = (cur + fac * add) % 2019;
        fac = (fac * 10) % 2019;
        val[cur]++;
    }
    long long res = 0;
    for (int i = 0; i < val.size(); ++i) {
        res += val[i] * (val[i] - 1) / 2;
    }
    return res;
}

int main() {
    string S;
    cin >> S;
    cout << solve(S) << endl;
}

Measured memory_bytes: 3760
#include <iostream>
#include<vector>
 
int main(){
    int N;
    std::cin>>N;
    std::vector<int> K(N),P(N);
    for(int i=0;i<N;++i){
        std::cin>>K[i]>>P[i];
    }
    for(int j=0;j<N;++j){
        if(K[j]%P[j]==0)std::cout<<P[j]<<std::endl;
        else std::cout<<K[j]%P[j]<<std::endl;
    }
    return 0;
}

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


int main(int argc, char** argv) {

    int n,x;
    cin>>n>>x;
    int f=abs(n-x)+1;
    if (n>0)
    {
            cout<<"Positive";
    }
    else
    {
        if (x>0)
            cout<<"Zero";
        else
        { if (f%2==0)
        cout<<"Positive";
        else cout<<"Negative";}
    }





    return 0;
}

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

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

    vector<vector<int>> graph(N);
    for (int i = 0; i < M; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    int colors[N];
    for (int i = 0; i < N; i++)
        colors[i] = -1;

    int color = 0;
    for (int i = 0; i < N; i++)
    {
        if (colors[i] != -1)
            continue;
        color++;
        colors[i] = color;

        queue<int> que;
        que.push(i); 
        while (!que.empty())
        {
            int node = que.front();
            // cout << "while " << i <<' '<<node << endl;
            que.pop();
            for (auto next_node: graph[node])
            {
                if (colors[next_node] != -1)
                    continue;
                // cout << node << endl;
                colors[next_node] = color;
                que.push(next_node);
            }
        }
    }
    cout << color << endl;
	// std::ios::sync_with_stdio(false);
   	return 0;
}

Measured memory_bytes: 6904
// 2011/05/24 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int q;
		cin >> q;
		if(q==-1)
			break;

		double x = (double)q/2.0;
		while(true){
			double err = x*x*x-(double)q;
			if(err<0.0)
				err *= -1.0;
			if(err<0.00001*(double)q)
				break;

			x = x-err/(3.0*x*x);
		}

		cout.precision(6);
		cout << fixed << x << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pll = pair<ll, ll>;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define Rep(i, m, n) for(ll i = m; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x, y, z) max((x), max((y), (z)))
#define tmin(x, y, z) min((x), min((y), (z)))
#define MINUS(a) memset(a, 0xff, sizeof(a))
#define ZERO(a) memset(a, 0, sizeof(a))
const ll INF = 1LL << 60;
const ll MM = 1000000000; const ll MOD = MM + 7; const ll MMM=9223372036854775807;//2^63 -1
#define ADD(a,b) a = (a + ll(b)) % MOD
#define MUL(a,b) a = (a * ll(b)) % MOD
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true;} return false;}
template<typename A, size_t N, typename T> void FILL(A (&array)[N], const T &val){ fill( (T*)array, (T*)(array+N), val );}
using Graph = vector<vector<ll>>;
ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
ll ddx[8] = {1, 1, 0, -1, -1, -1, 0, 1}, ddy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//cout << fixed << setprecision(10);


int main(){
    string s; cin >> s;
    ll ans = 0;
    rep(i, s.size()) ans += s[i] - '0';
    if(ans % 9 == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3652
fun main() {
    val k = nextInt()
    val n = nextInt()
    nextLine()
    val a = nextIntList()
    var max = k - a[n-1] + a[0]
    for (i in 0 until n-1) {
        val d = a[i+1] - a[i]
        if (d > max) max = d
    }
    println(k - max)
}

val scanner = java.util.Scanner(System.`in`)
fun next(): String = scanner.next()
fun nextInt() = scanner.nextInt()
fun nextLong() = scanner.nextLong()
fun nextLine() = scanner.nextLine()
fun nextList() = scanner.nextLine().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun printYesNo(isYes: Boolean) = println(if (isYes) "Yes" else "No")

fun main(args: Array<String>) = main()

Measured memory_bytes: 83756
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
//typedef vector<unsigned int>vec;
typedef vector<ll>vec;
typedef vector<vec> mat;
typedef vector<vector<int>> Graph;

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, s, t;
    cin >> N >> M;
    vector<vector<int>> to(N);
    REP(i,M){
        int a, b;
        cin >> a >> b;
        --a, --b;
        to[a].push_back(b);
    }
    cin >> s >> t;
    --s, --t;
    vector<vector<int>> dist(N,vector<int>(3,INF));
    queue<pair<int, int>> q;
    q.emplace(s, 0);
    dist[s][0] = 0;
    while(!q.empty()){
        int v = q.front().first;
        int l = q.front().second;
        q.pop();
        for(auto nv : to[v]){
            int nl = (l + 1) % 3;
            if(dist[nv][nl] != INF) continue;
            dist[nv][nl] = dist[v][l] + 1;
            q.emplace(nv, nl);
        }
    }
    int ans = dist[t][0];
    if(ans == INF) ans = -1;
    else ans /= 3;
    cout << ans << endl;
}

Measured memory_bytes: 11264
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (1 << 20)

vector<int> a[MAXN];
int n, m;
int v[MAXN];
int cnt[MAXN];

void dfs(int cur, int col) {
	if (v[cur]) {
		return;
	}
	v[cur] = col;
	for (auto&e : a[cur]) {
		dfs(e, col);
	}
}

int main() {
	cout << fixed << setprecision(12);	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		a[v1].push_back(v2);
		a[v2].push_back(v1);
	}
	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (!v[i]) {
			dfs(i, ++c);
		}
	}
	for (int i = 1; i <= n; i++) {
		cnt[v[i]]++;
	}
	int ret = 0;
	for (int i = 1; i <= c; i++) {
		ret = max(ret, cnt[i]);
	}
	cout << ret << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

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

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

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



Measured memory_bytes: 41392
#include<stdio.h>
#include<stdlib.h>
int main(void){

  int N=0;
  scanf("%d",&N);
  char S[30001]={};
  scanf("%s",S);
  int pin=0,count=0,i=0,j=0;
  int digit[3];
  
  for(int pin=0;pin<1000;pin++){
    digit[2] = pin%10;
    digit[1] =(pin/10)%10;
    digit[0] = pin/100;
    
    
    for(i=0,j=0;i<N && j<3 ;i++){
    	if(S[i] == '0' + digit[j]){
          j++;
        }
      if(j==3){
      	count++;
      }
    }
  }
  
  printf("%d",count);
  fflush(stdout);


 return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <fstream>
#include <iomanip>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  ll i = 0;
  for (auto x : v) {os << " [" << i++ << "]" << x; if (i % 10 == 0) os << std::endl;}
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp) {os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  std::string S;
  std::cin >> S;

  ll ans = 700;
  for (auto c : S) {
    ans += c == 'o' ? 100 : 0;
  }

  print(ans);
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin >> a >> b;
    sort (a.begin(),a.end());
    sort (b.begin(),b.end());
    reverse(b.begin(),b.end());
    cout << ((a<b)?("Yes"):("No"));
    return 0;
}


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

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

    int A[n], B[n], C[n];
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];
    for (int i = 0; i < n; i++) cin >> C[i];

    sort(A, A+n);
    sort(C, C+n);

    long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (lower_bound(A, A+n, B[i]) - A) * (C + n - upper_bound(C, C + n, B[i]));
    }

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

Measured memory_bytes: 1408
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <stdlib.h>
#include <functional>
#define ll long long
#define llu unsigned long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e5 + 10;
int n, m;
ll cost[N];
bool vis[N];
vector<pair<ll, int>> vec;
vector<vector<pair<ll, int>>> L;
vector<int> vt;
int P[N];

int _find(int x) {
	return P[x] = (P[x] != x ? _find(P[x]) : x);
}

void merge(int x, int y) {
	P[_find(y)] = _find(x);
}

int newidx(int x) {
	return lower_bound(vt.begin(), vt.end(), x) - vt.begin();
}

int main()
{
	int i, j, k, x, y;
	scanf("%d%d", &n, &m);

	for (i = 0; i < n; ++i) {
		scanf("%lld", &cost[i]);
		P[i] = i;
		vec.push_back({ cost[i], i });
	}

	sort(vec.begin(), vec.end());
	
	for (i = 0; i < m; ++i) {
		scanf("%d%d", &x, &y);
		merge(x, y);
	}
	if (m == n - 1) {
		printf("0\n");
		return 0;
	}
	
	for (i = 0; i < n; ++i) {
		vt.push_back(_find(i));
	}

	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());

	L.resize(vt.size());
	for (i = 0; i < n; ++i) {
		L[newidx(_find(i))].push_back({ cost[i], i });
	}

	for (i = 0; i < L.size(); ++i) sort(L[i].begin(), L[i].end());

	ll sum = 0;
	int cnt = L.size();

	if (n < 2 * (L.size() - 1)) {
		printf("Impossible\n");
		return 0;
	}

	for (i = 0; i < L.size(); ++i) {
		vis[L[i][0].second] = true;
		sum += L[i][0].first;
	}

	int lim = 2*L.size() - 2;

	for (i = 0; i < vec.size(); ++i) {
		if (!vis[vec[i].second]) {
			if (cnt == lim) break;
			sum += vec[i].first;
			cnt++;
		}
	}
	
	printf("%lld\n", sum);

}

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

// 1,000,000


int main() {
	int a;
	cin >> a;
	if (a < 100) {
		cout << "0" << endl;
		return 0;
	}
	int d = int(a / 100.0);
	int n = a % 100;
	for (int i = 0; i < d; ++i) {
		if (n <= 0) {
			break;
		}
		if (n >= 5) {
			n -= 5;
			continue;
		}
		if (n >= 4) {
			n -= 4;
			continue;
		}
		if (n >= 3) {
			n -= 3;
			continue;
		}
		if (n >= 2) {
			n -= 2;
			continue;
		}
		if (n >= 1) {
			n -= 1;
			continue;
		}
	}
	if (n <= 0) {
		cout << 1 << endl;
	}
	else {
		cout << 0 << endl;
	}
}

Measured memory_bytes: 256
# Aizu Problem 00159: The Best Body
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n = int(input())
    if n == 0:
        break
    best = 999999999999999999
    near = float('Inf')
    for _ in range(n):
        no, h, w = [int(__) for __ in input().split()]
        h /= 100
        bmi = w / h**2
        diff = abs(bmi - 22)
        if abs(diff - near) < 1e-8:
            near = abs(bmi - 22)
            best = min(best, no)
        elif diff < near:
            near = diff
            best = no
    print(best)
        

Measured memory_bytes: 7744
n, k = map(int, input().split())

def cmb(s, t, r):
    x = 1
    y = 1
    for i in range(t):
        x = (x*(s-i))%r
        y = (y*(i+1))%r
 
    y_inverse = pow(y, r-2, r)
    return (x*y_inverse)%r

mod = 10 ** 9 + 7

for i in range(1,k+1):
    div = cmb(k-1, i-1,mod)
    red = n + 1 - k - i 
    if red < 0:
        print(0)
        continue
    pat = cmb(i+red,red,mod)
    ans = (div * pat) % mod
    print(ans)

Measured memory_bytes: 3316
(defmacro for ((var from to) &body body)
  `(do ((,var ,from (1+ ,var)))
       ((> ,var ,to))
     ,@body))

(defun valid-p (n y)
  (for (a 0 n)
    (for (b 0 (- n a))
      (let* ((c (- n a b))
             (sum (+ (* a 10000)
                     (* b 5000)
                     (* c 1000))))
        (when (= y sum)
          (return-from valid-p (values a b c))))))
  (values -1 -1 -1))

(defun main ()
  (let ((n (read))
        (y (read)))
    (multiple-value-bind (a b c)
        (valid-p n y)
      (format t "~A ~A ~A~%" a b c))))

#-swank (main)


Measured memory_bytes: 15720
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);
parse_tuple!(A, B, C, D);

// ===

fn main() {
    let (a, b, c, d): (i32, i32, i32, i32) = read();
    let from = max(a, c);
    let to = min(b, d);
    let duration = max(to - from, 0);

    println!("{}", duration);
}


Measured memory_bytes: 4352
// template.cpp

// Defines.
//#define DEBUG
#define NUMBER_OF_DIGITS 12

// Includes.
#include <bits/stdc++.h>

#ifdef DEBUG
#include <chrono>
#endif

// Usings.
using namespace std;

// Main function.
int main()
{
#ifdef DEBUG
	chrono::system_clock::time_point start, end;
	
	start = chrono::system_clock::now();
#endif
	
	// settings.
	ios::sync_with_stdio(false);
	
	cout << fixed;
	cout << setprecision(NUMBER_OF_DIGITS);
	
	// logic.
	int n;
	cin >> n;
	
	vector<tuple<double, double>> cities;
	for (int i = 0; i < n; i++)
	{
		double x, y;
		cin >> x >> y;
		cities.push_back(make_tuple(x, y));
	}
	
	vector<int> order;
	for (int i = 0; i < n; i++)
	{
		order.push_back(i);
	}
	
	double total = 0.0;
	int counter = 0;
	do
	{
		double distance = 0.0;
		for (int i = 0; i < (n - 1); i++)
		{
			distance += pow(
				(pow((get<0>(cities[order[i]]) - get<0>(cities[order[i + 1]])), 2.0) + pow((get<1>(cities[order[i]]) - get<1>(cities[order[i + 1]])), 2.0)),
				0.5);
		}
		
		total += distance;
		counter++;
	}
	while (next_permutation(order.begin(), order.end()));
	
	cout << (total / (double)counter) << endl;

#ifdef DEBUG
	end = chrono::system_clock::now();
	
	double elapsed = chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
	cout << elapsed << "[ms]" << endl;
#endif
	
	return 0;
}


Measured memory_bytes: 4280
#define loop(i,j,k) for(long long i = j;i < k;i++)

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;

class stat {
public:
    int64_t p,q,d;
    bool operator< (const stat& e) const {
        if(this->p == e.p) return this->q < e.q;
        return this->p < e.p;
    }
};

int main(void) {
    int n,a[50];
    cin >> n;
    int maxn = INT32_MIN,minn = INT32_MAX,maxi = -1,mini = -1;
    loop(i,0,n) {
        cin >> a[i];
        if(maxn < a[i]) {
            maxn = a[i];
            maxi = i;
        }
        if(minn > a[i]) {
            minn = a[i];
            mini = i;
        }
    }
    cout << 2 * n - 1 << endl;
    if(abs(maxn) > abs(minn)) {
        loop(i,0,n) {
            cout << maxi + 1 << " " << i + 1 << endl;
            a[i] += maxn;
        }
        loop(i,0,n - 1) {
            cout << i + 1 << " " << i + 2 << endl;
            a[i+1] += a[i];
        }
    }
    else {
        loop(i,0,n) {
            cout << mini + 1 << " " << i + 1 << endl;
            a[i] += minn;
        }
        loop(i,0,n - 1) {
            cout << n - i << " " << (n - i) - 1 << endl;
            a[(n - i) - 2] += a[(n - i) - 1];
        }
    }
}


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

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
//priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

llint h,w;

void solve(){
  while(1){
    cin >> h >> w;
    if(h==0 && w==0)break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        if(i%2==j%2)cout << '#';
        else cout << '.';
      }
      cout << endl;
    }
    cout << endl;
  }
}

int main() {
  solve();
  return 0;
}



Measured memory_bytes: 3096
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    int a, p; cin>>a>>p;
    cout<<(3*a+p)/2<<endl;
    return 0;
}

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

D = int(input())
A = []
m1 = 0
m2 = 0
f = False
for i in range(D):
    tmp = int(input())
    if tmp > m1:
        m2 = m1
        m1 = tmp
        f = False
    elif tmp == m1: f = True
    elif tmp > m2:
        m2 = tmp
    A.append(tmp)

for a in A:
    if f or a != m1:
        print(m1)
    else:
        print(m2)

Measured memory_bytes: 12524
/*
        _            _                  _            _       _     _         _   _          _          _             _        
       / /\         / /\               / /\         / /\    / /\  /\ \      /\_\/\_\ _     /\ \       /\ \     _    /\ \      
      / /  \       / /  \             / /  \       / / /   / / /  \ \ \    / / / / //\_\   \ \ \     /  \ \   /\_\ /  \ \     
     / / /\ \__   / / /\ \           / / /\ \__   / /_/   / / /   /\ \_\  /\ \/ \ \/ / /   /\ \_\   / /\ \ \_/ / // /\ \_\    
    / / /\ \___\ / / /\ \ \         / / /\ \___\ / /\ \__/ / /   / /\/_/ /  \____\__/ /   / /\/_/  / / /\ \___/ // / /\/_/    
    \ \ \ \/___// / /  \ \ \        \ \ \ \/___// /\ \___\/ /   / / /   / /\/________/   / / /    / / /  \/____// / / ______  
     \ \ \     / / /___/ /\ \        \ \ \     / / /\/___/ /   / / /   / / /\/_// / /   / / /    / / /    / / // / / /\_____\ 
 _    \ \ \   / / /_____/ /\ \   _    \ \ \   / / /   / / /   / / /   / / /    / / /   / / /    / / /    / / // / /  \/____ / 
/_/\__/ / /  / /_________/\ \ \ /_/\__/ / /  / / /   / / /___/ / /__ / / /    / / /___/ / /__  / / /    / / // / /_____/ / /  
\ \/___/ /  / / /_       __\ \_\\ \/___/ /  / / /   / / //\__\/_/___\\/_/    / / //\__\/_/___\/ / /    / / // / /______\/ /   
 \_____\/   \_\___\     /____/_/ \_____\/   \/_/    \/_/ \/_________/        \/_/ \/_________/\/_/     \/_/ \/___________/    
                                                                                                                              
*/
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, n) for(int i = 0;i < (n);++i)

#define endl '\n'
#define pb emplace_back
#define mkp make_pair
#define p_q priority_queue
#define INF 1000000000
#define PI 3.1415926
#define coutdb cout << fixed << setprecision(10)

const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};
const long long MOD = 1e9+7;

typedef long long ll;
// #define int long long

template <typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

int wcnt[200010]={0}, bcnt[200010]={0};

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

  int n; string s; cin >> n >> s;
  for(int i = n-1; i >= 0; i--){
    if(s[i] == '.') wcnt[i+1] = wcnt[i+2]+1;
    else wcnt[i+1] = wcnt[i+2];
  }
  REP(i, n){
    if(s[i] == '#') bcnt[i+1] = bcnt[i]+1;
    else bcnt[i+1] = bcnt[i];
  }
  int ans = INF;
  for(int i = 0; i <= n; i++){
    ans = min(ans, bcnt[n-i]+wcnt[n-i+1]);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2196
// AOJ 2814: Energy Drink
// 2018.1.4 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 0x50505050
#define MAX 200002

typedef struct { int a, b; char f; } T;
T t[MAX]; int n;
int dp[MAX];

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int cmp(T *a, T *b) { if (a->a - b->a) return a->a - b->a; return b->b - a->b; }

int bsch(int x, int r)
{
	int m, l = 0;

    while (l < r) {
        m = (l + r) >> 1;
        if (dp[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int main()
{
	int i, a, b, r, sz;

	n = in();
	sz = 0;
	for (i = 0; i < n; i++) {
		a = in(), b = in();
		t[sz].a = a, t[sz++].b = b;
		t[sz].a = b, t[sz].b = a, t[sz++].f = 1;
	}
	n <<= 1; qsort(t, n, sizeof(T), cmp);

	memset(dp, INF, sizeof(dp));
	r = 1;
	for (i = 0; i < n; i++) {
		b = t[i].b, a = bsch(b, r);
		if ((a & 1) == t[i].f) {
			dp[a] = b;
			if (a >= r) r = a + 1;
		}
	}
	printf("%d\n", bsch(INF, n));
	return 0;
}



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

int main(){
  int a,b,c; cin>>a>>b>>c;
  int k; cin>>k;
  int d,i=0;
  d=max(max(a,b),c);
  int e=d;
  while(i<k){
    d*=2;
    i++;
  }
  int ans=d+a+b+c-e;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
// E - Cell Distance
#include <bits/stdc++.h>

using namespace std;

#define	MOD	1000000007

int main(int argc, char *argv[])
{
	long long n, m, k;
	cin >> n >> m >> k;

	long long r = 0, t = 1;
	for (long long i = 0; i < n; i++) r = (r + (1 + i) * i / 2 * m % MOD * m % MOD) % MOD;
	for (long long i = 0; i < m; i++) r = (r + (1 + i) * i / 2 * n % MOD * n % MOD) % MOD;
	for (long long i = 2; i <= n * m - 2; i++) r = r * i % MOD;
	for (long long i = 2; i <= k - 2; i++) t = t * i % MOD;
	for (long long i = 2; i <= (n * m - k); i++) t = t * i % MOD;
	for (long long x = MOD - 2; x > 0; t = t * t % MOD, x >>= 1)
		if (x & 1) r = r * t % MOD;
	cout << r << endl;

	return 0;
}


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

int main(){
  int N,A,count;
  int count_min=9999;
  cin >> N;

  for(int i=0;i<N;i++){
    count=0;
    cin >> A;
    while(A%2==0){
      A=A/2;
      count++;
    }
    if(count<count_min){
      count_min=count;
    }
  }
  cout << count_min << endl;
}


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

using namespace std;

int main(){
    int N,M,num = 0;

    vector<int> L,R;

    cin >> N >> M;

    for(int i = 0; i < M; i++){
        int a;
        cin >> a;
        L.push_back(a);
        cin >> a;
        R.push_back(a);
    }

    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    if (R[0] - L[M-1] >= 0)num = R[0] - L[M-1] + 1;
    else num = 0;

    cout << num << endl;

    return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

ll N;

void dfs(ll mult, ll val, bool th, bool fi, bool sev, ll &ans){
  if(val > N)
    return;

  if(th && fi && sev) ans++;

  dfs(10*mult, val + 3*mult, true || th, false || fi, false || sev, ans);
  dfs(10*mult, val + 5*mult, false || th, true || fi, false || sev, ans);
  dfs(10*mult, val + 7*mult, false || th, false || fi, true || sev, ans);

  return;
}

int main(){
  cin >> N;

  ll ans = 0;

  dfs(1, 0, false, false, false, ans);

  cout << ans << "\n";
  
  return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
const ll INF = 10010010010001;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    s = s+'R';
    int ans[100010] = {0};
    int m = -1;
    for(int i=0;i<n;i++){
        if(s[i]=='R' && s[i+1]=='L'){
            ans[i] += (i-m)-(i-m)/2;
            ans[i+1] += (i-m)/2;
            m = i;
        }
        else if(s[i]=='L' && s[i+1]=='R'){
            ans[m] += (i-m)/2;
            ans[m+1] += (i-m)-(i-m)/2;
            m = i;
        }
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << ' ';
    }
    cout << endl;
}


Measured memory_bytes: 1020
#https://qiita.com/drken/items/996d80bcae64649a6580 3-3. 二部グラフ判定
from collections import deque

# 頂点数と辺数
N, M = map(int, input().split())

# グラフ入力受取
G = [[] for _ in range(N)]
deg = [0]*N # 各頂点の出次数
for i in range(M):
    a, b = map(int, input().split())
    G[b].append(a) # 逆向きに辺を張る
    deg[a]+=1 # 出次数

# シンクたちをキューに挿入する
que = deque()
for i in range(N):
    if deg[i] == 0:
        que.append(i)

# 探索開始
order = []
while len(que)!=0:
    # キューから頂点を取り出す
    v = que.popleft()
    order.append(v)

    # v へと伸びている頂点たちを探索する
    for nv in G[v]:
        # 辺 (nv, v) を削除する
        deg[nv]-=1

        # それによって nv が新たにシンクになったらキューに挿入
        if deg[nv] == 0:
            que.append(nv)

# 答えをひっくり返す
order.reverse()
for i in order:
    print(i)


Measured memory_bytes: 9240
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>pii;
typedef vector<int>vi;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<"\n"
#define dd(x) cout<<#x<<"="<<x<<" "
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define lowbit(a) ((a)&-(a))
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=2e6+5;
const int mod = 1e9 + 7;
int f[N],invf[N];
int qpow(int x,int n){
	int res = 1;
	while(n){
		if(n&1)res = (ll)res*x%mod;
		x = (ll)x*x%mod;
		n >>= 1;
	}
	return res;
}
void init(){
	f[0] = invf[0] = 1;
	rep(i , 1 ,N)
		f[i] = (ll)f[i-1]*i%mod,invf[i] = qpow(f[i],mod - 2);
}
vi g[N];
int n,big[N],dp[N];
void dfs(int u,int p){
	big[u] = dp[u] = 1;
	for(auto v:g[u]){
		if(v == p)continue;
		dfs(v,u);
		big[u] += big[v];
		dp[u] = (ll)dp[u]*dp[v]%mod;
		dp[u] = (ll)dp[u]*invf[big[v]]%mod;
	}
	dp[u] = (ll)dp[u]*(f[big[u] - 1])%mod;
}
int ans[N];
void dfs1(int u,int p){
	if(u!= 1){
		ans[u] = (ll)ans[p]*invf[n - big[u]]%mod;
		ans[u] = (ll)ans[u]*f[n - big[u] - 1]%mod;
		ans[u] = (ll)ans[u]*f[big[u]]%mod;
		ans[u] = (ll)ans[u]*qpow(dp[u],mod - 2)%mod;
		dp[u] = (ll)dp[u]*(invf[big[u] - 1])%mod;
		ans[u] = (ll)ans[u]*dp[u]%mod;
	}
	for(auto v:g[u]){
		if(v == p)continue;
		dfs1(v,u);
	}
}
int main()
{
	init();
	cin>>n;
	int u,v;
	rep(i , 1 , n ){
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,0);
	ans[1] = dp[1];
	dfs1(1,0);
	rep(i , 1 , n + 1)
		cout<<ans[i]<<"\n";
	return 0;
}



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

using namespace std;

typedef long long ll;

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

	int k, x;
	cin >> k >> x;

	if(500 * k >= x){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
let n = Int(readLine()!)
let arr = readLine()!.split(separator: " ").map({Int($0)!})

var costArr = [Int](repeating: 0, count: arr.count)
costArr[1] = abs(arr[0] - arr[1])

for i in 2 ..< arr.count {
    costArr[i] = min(costArr[i-1] + abs(arr[i] - arr[i-1]), costArr[i-2] + abs(arr[i] - arr[i-2]))
}
print(costArr.last!)

Measured memory_bytes: 12060
// finish date: 2018/03/14

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int H, W;
    cin >> H >> W;
    vs A(H);
    rep(i, H) cin >> A[i];
    int shape = 0;
    rep(i, H) rep(j, W) if (A[i][j] == '#') shape++;
    if (shape != H + W - 1) {
        cout << "Impossible" << endl;
        return 0;
    }

    int posx = 0, posy = 0;
    while (posx == W - 1 && posy == H - 1) {
        if (posx != W - 1 && A[posy][posx + 1]) {
            posx++;
        } else if (posy != H - 1 && A[posy + 1][posx]) {
            posy++;
        } else {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    cout << "Possible" << endl;

    return 0;
}

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

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

    bool MMYY = 0 < A / 100 && (A / 100) <= 12;
    bool YYMM = 0 < A % 100 && (A % 100) <= 12;

    if(YYMM && MMYY){
        cout << "AMBIGUOUS" << endl;
    }
    else if(YYMM){
        cout << "YYMM" << endl;
    }
    else if(MMYY){
        cout << "MMYY" << endl;
    }
    else{
        cout << "NA" << endl;
    }
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

//#define int long long

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

const int INF = 100000000;
const int M = 100000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/* ------------------------------------- */

int main() {
    int n, h[30];
    scanf("%d", &n);
    rep(i, n) {
        scanf("%d", &h[i]);
    }
    int ret = 0;
    rep(i, n) {
        if (i == 0) {
            ret++;
            continue;
        }
        bool b = false;
        rep(j, i) {
            if (h[j] > h[i]) {
                b = true;
            }
        }
        if (!b) {
            ret++;
        }
    }
    printf("%d", ret);

    /* --------------------------------- */
    printf("\n");
    return 0;
}

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

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

int main() {
    int n,m;cin>>n>>m;
    pair<ll,ll>a[n];
    rep(i,n){
        cin>>a[i].first;
        cin>>a[i].second;
    }
    sort(a,a+n);
    ll ans = 0;
    ll cc = 0;
    rep(i,n){
        if(cc + a[i].second > m){
            ans+=a[i].first * (m - cc);
            break;
        }
        else {
            cc += a[i].second;
            ans += a[i].first * a[i].second;
        }
    }
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5188
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
def sqrt(n):
    x = 1 << (n.bit_length() + 1) // 2
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
def calc(k):
    return (sqrt(8*k+1) - 1) // 2

N  = int(input())
pf = primeFactor(N)
print(sum([calc(pf[p]) for p in pf]))


Measured memory_bytes: 9352
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>

#define fio() cin.tie(0); ios::sync_with_stdio(false);
#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

int main(){
    fio();
    ll N,M;
    cin >> N >> M;
    vector <ll> a(N);
    REP(i,N)cin >> a[i];
    sort(a.begin(),a.end());

    //組合せがM以上となるものを二分探索
    ll ok = 200001;
    ll ng = -1;
    while(ng + 1 < ok)
    {
      ll mid = (ok + ng) / 2;
      ll num = 0;
      //ここでN回すのか
      REP(i,N)
      {
        //ここ組合せになってるのか
        ll zan = mid - a[i];
        //zanが対象
        auto itr = lower_bound(a.begin(), a.end(), zan);
        num += a.end() - itr;
      }
      if(num > M)ng = mid;
      else ok = mid;
    }

    //
    ll res = 0;
    vector <ll> sum(N+1, 0);
    ll num = 0;
    //累積和
    REP(i, N)sum[i+1] = sum[i] + a[i];
    
    REP(i, N)
    {
      ll zan = ok - a[i];
      auto itr = lower_bound(a.begin(), a.end(), zan);
      num += a.end() - itr;
      ll idx = itr - a.begin();
      
      //a[i]+ zan >= okを満たすもの
      res += sum[N] - sum[idx];
      //a[i]の個数
      res += a[i] * (N - idx);
    }

    //ちょうどMにはならないので、最後に、最低スコアを足し合わせる
    if(num < M)
    {
      res += (M - num) * ng;
    }

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



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

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    string s;
    cin>>s;
    int n = 0;
    for (auto c:s){
        n += (c-'0');
    }
    if (n%9==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 3776
# Author: cr4zjh0bp
# Created: Wed Mar 11 15:10:38 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

R = ni()

if R < 1200:
    print("ABC")
elif R < 2800:
    print("ARC")
else:
    print("AGC")

Measured memory_bytes: 3064
#include <iostream>

#include <tuple>

using std::cin;
using std::cout;
using std::endl;

using std::get;
using std::make_tuple;
using std::tuple;

static tuple<int, int, int>
solve(int N, int Y)
{
  if (1000 * N <= Y && Y <= 10000 * N)
  {
    for (int a = 0; a <= N; a++)
    {
      int ay = Y - 10000 * a;
      int an = N - a;
      if (1000 * an <= ay && ay <= 5000 * an)
      {
        int b = (ay - 1000 * an) / 4000;
        int c = an - b;
        if (5000 * b + 1000 * c == ay)
        {
          return make_tuple(a, b, c);
        }
      }
    }
  }
  return make_tuple(-1, -1, -1);
}

int
main()
{
  int N, Y;
  cin >> N >> Y;
  auto ret = solve(N, Y);
  cout << get<0>(ret) << ' ' << get<1>(ret) << ' ' << get<2>(ret) << endl;
  return 0;
}


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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
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<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }

int N, M;
vector<vector<int>> G;
int dp[100010];

int rec(int v) {
    if (dp[v] != -1) return dp[v];
    int res = 0;
    for (int nv : G[v]) {
        chmax(res, rec(nv) + 1);
    }
    return dp[v] = res;
}

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

    cin >> N >> M;
    G.assign(N, vector<int>());
    rep(i, M) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        G[x].pb(y);
    }

    Fill(dp, -1);

    int res = 0;
    rep(i, N) chmax(res, rec(i));
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 8192
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
#define erep(i,n) for(int i = 0;i<=n;i++)
#define rep1(i,n) for(int i = 1;i<n;i++)
#define erep1(i,n) for(int i = 1;i<=n;i++)
typedef long long ll;
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstring vector<string>
#define vdouble vector<double>
#define vll vector<ll>
#define vbool vector<bool>
#define INF 100000000000000009
#define int long long
using P = pair<int,int>;

signed main(){
    int n;
    cin >> n;
    vint s(n);
    rep(i,n) cin >> s[i];
    bool flag = false;
    int ans = 0;
    rep(i,n){
        if(s[i] == i + 1){
            ans++;
            i++;
        }
    }
    cout << ans << endl;
} 

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int main(){


    int x,y,z,k;
    cin >> x >> y >> z >> k;

    ll a[x];
    ll b[y];
    ll c[z];


    for(int i=0; i<x; i++){
        cin >> a[i];
    }

    for(int i=0; i<y; i++){
        cin >> b[i];
    }

    for(int i=0; i<z; i++){
        cin >> c[i];
    }

    vector<ll> b_c;
    for(int i=0; i<y; i++){
        for(int j=0; j<z; j++){
            b_c.push_back(b[i]+c[j]);
        }
    }

    sort(b_c.begin(), b_c.end(), greater<ll>());
    vector<ll> a_b_c;

    for(int i=0; i<x; i++){
        for(int j=0; j<min(3000, y*z); j++){
            a_b_c.push_back(b_c[j] + a[i]);
        }
    }

    sort(a_b_c.begin(), a_b_c.end(), greater<ll>());

    for(int i=0; i<k; i++){
        cout << a_b_c[i] << endl;
    }


    return 0;
}

Measured memory_bytes: 43388
# 0:14-
A,B,C = map(int,input().split())
if A*B*C % 2 == 0: ans = 0
else:
    a = max(A,B,C)
    b = min(A,B,C)
    c = A+B+C-a-b
    ans = b*c
print(ans)

Measured memory_bytes: 3060
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
c = list(b.items())
if all(i==0 for i in a):
    print("Yes")
elif len(b)==2 and n%3==0 and b[0]==n//3:
    print("Yes")
elif len(b)==3 and c[0][0]^c[1][0]^c[2][0]==0 and c[0][1]==c[1][1]==c[2][1]:
    print("Yes")
else:
    print("No") 

Measured memory_bytes: 15512