akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
int main() {
    int N;
    cin >> N;
 
    vector<long long> v;
    vector<long long> m_A(N+1);
    vector<long long> m_C(N+1);
    vector<long long> m_C2(N+1);
    long long sum_C = 0;
 
    for (int i = 0; i < N; ++i) {
        long long A;
        cin >> A;
        v.push_back(A);
        m_A.at(A) = m_A.at(A) + 1;
    }
 
    for (int i = 1; i <= N; ++i) {
        if (m_A.at(i) > 1) {
            m_C.at(i) = m_A.at(i) * (m_A.at(i) - 1) / 2;
            sum_C += m_C.at(i);
        }
    }
 
    for (int i = 1; i <= N; ++i) {
        if (m_A.at(i) > 2) {
            m_C2.at(i) = sum_C - m_C.at(i) + (m_A.at(i) - 1) * (m_A.at(i) - 2) / 2;
        } else {
            m_C2.at(i) = sum_C - m_C.at(i);
        }
    }
 
    for (long long A: v) {
        cout << m_C2.at(A) << endl;
    }
 
    return 0;
}

Measured memory_bytes: 8944
import math
A, B, H, M = map(int, input().split())

h = H + M / 60

t = 360 * h / 12
c = M * 6

k = abs(t - c)

ans2 = A ** 2 + B ** 2 - 2 * A * B * math.cos(math.radians(k))
ans = math.sqrt(ans2)

print(ans)

Measured memory_bytes: 62368
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    vector<string> t = {"NS", "WE", "NEWS"};
    for (int i = 0; i < 3; i++) {
        sort(all(t[i]));
    }
    string s;
    cin >> s;
    sort(all(s));
    s.erase(unique(s.begin(), s.end()), s.end());
    if (find(all(t), s) == t.end()) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
import numpy as np

n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=np.zeros((501, 501), dtype=np.int)

for i in range(m):
    x[a[i][0], a[i][1]]+=1

x = np.cumsum(x, axis=0)
x = np.cumsum(x, axis=1)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)


Measured memory_bytes: 79856
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
auto fl = [](auto a, auto b) { assert(b != 0); return a / b - (a % b != 0 && ((a >= 0) != (b >= 0)) ? 1 : 0); };
auto ce = [](auto a, auto b) { assert(b != 0); return a / b + (a % b != 0 && ((a >= 0) == (b >= 0)) ? 1 : 0); };
auto mo = [](auto a, auto b) { assert(b != 0); a %= b; if(a < 0) { a += abs(b); } return a; };
LL gcd(LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)

// ---- ----

int main() {
	int h, n;
	cin >> h >> n;
	vector<int> a(n);
	inc(i, n) { cin >> a[i]; }
	
	int s = 0;
	inc(i, n) { s += a[i]; }
	
	cout << (s >= h ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
  ll A,B,ans=0;
  cin>>A>>B;
  if(A==B) cout<<"0"<<endl;
  else if(abs(A)==abs(B)) cout<<"1"<<endl;
  else if(abs(A)<abs(B)){
    if(A<0) ans++;
    if(B<0) ans++;
    cout<<abs(B)-abs(A)+ans<<endl;
  }else{
    if(A>0) ans++;
    if(B>0) ans++;
    cout<<abs(A)-abs(B)+ans<<endl;
  }
}


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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;
    if(s[0] == s[1] && s[1] == s[2]){
        if(s[0] == 'S') cout << 0 << '\n';
        else cout << 3 << '\n';
        return 0;
    }
    if(s[0] == s[1] && s[0] == 'R'){
        cout << 2 << '\n';
        return 0;
    }
    if(s[1] == s[2] && s[1] == 'R'){
        cout << 2 << '\n';
        return 0;
    }
    cout << 1 << '\n';
    return 0;
}


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

using namespace std;

const int inf = 1e8;

int main() {
	int h, n;
	cin >> h >> n;
	vector<int> dp(2 * h + 1, inf);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		a = min(a, h);
		for (int j = a; j <= 2 * h; j++) {
			dp[j] = min(dp[j], dp[j - a] + b);
		}
	}
	int ans = inf;
	for (int i = h; i <= 2 * h; i++) {
		ans = min(ans, dp[i]);
	}
	cout << ans << endl;
	return 0;
}

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

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

const long long INF = 1LL << 60;

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

  cout << (a <= 8 && b <= 8 ? "Yay!" : ":(") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <random>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0)
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n, m;
lli cnt[40];
int main() {
  cin >> n >> m;
  fill(begin(cnt), end(cnt), 0);
  for (lli i=0; i<n; ++i) {
    lli k; cin >> k;
    for (lli j=0; j<k; ++j) {
      lli a; cin >> a;
      cnt[a]++;
    }
  }
  lli ans = 0;
  for (lli i=1; i<=m; ++i) {
    if (cnt[i]==n) ++ans;
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s,t; cin>>s>>t;
	vector<vector<int>>sc(26),tc(26);
	for(int i=0;i<s.size();++i){
		sc.at(s.at(i)-'a').emplace_back(i);
		tc.at(t.at(i)-'a').emplace_back(i);
	}
	string ans="Yes"s;
	for(int i=0;i<s.size();++i){
		if(sc.at(s.at(i)-'a')==tc.at(t.at(i)-'a')){
			sc.at(s.at(i)-'a').clear();
			tc.at(t.at(i)-'a').clear();
			continue;
		}
		ans="No"s;
		break;
	}
	cout<<ans<<"\n"s;
}


Measured memory_bytes: 6012
#include <bits/stdc++.h>
using namespace std;
int n,a[100005];
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if(a[i]-a[i-1]>0) a[i]--;
        if(a[i]<a[i-1]){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <utility>
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstring>
using namespace std;
using ll = long long;

int main(){
  int n; cin >> n;
  map<string, bool> mp;

  string s, t; cin >> s;
  mp[s] = true;
  bool f = true;
  for(int i=1; i<n; i++){
    cin >> t;
    
    if(s[s.size()-1] != t[0] || mp[t]){
      f = false;
    }
    s = t;
    mp[t] = true;
  }

  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
} 


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int64_t n; cin>>n;
	vector<char>ans;
	while(n){
		--n;
		ans.emplace_back('a'+n%26);
		n/=26;
	}
	for(auto i=ans.rbegin();i!=ans.rend();++i)cout<<*i;
	cout<<"\n"s;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, n, m) for (int i = n; i < m; i++)
#define ll long long int

using namespace std;

string s;
int n,k;

bool f(int size) {
  int l = 0;
  int r = size-1;

  // 初期状態のswapの個数
  int swap = 0;
  char b = s[0];
  if (b == '0') {
    swap++;
  }
  if (s[r] == '0') {
    swap++;
  }
  FOR(i,1,size) {
    if(b != s[i]) {
      swap++;
      b = s[i];
    }
  }

  while(r < n) {
    if(swap/2 <= k) {
      return true;
    }
    if(r+1 == n) {
      return false;
    }
    if(s[l] == '0') {
      swap--;
    }
    if(s[r] == '0') {
      swap--;
    }
    if(s[l] != s[l+1]) {
      swap--;
    }
    if(s[r] != s[r+1]) {
      swap++;
    }
    if(s[l+1] == '0') {
      swap++;
    }
    if(s[r+1] == '0') {
      swap++;
    }
    l++;
    r++;
  }
  return false;
}

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

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

    if (f(mid))
    {
      ok = mid;
    }
    else
    {
      ng = mid;
    }
  }

  cout << ok << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, c) for(long long i=0; i<(long long)c; i++)
const ll INF=1000000000000001;
int main() {
	int l,r,d;
	ll ans=0;
	cin >>l>>r>>d;
	for(int i=l;i<=r;i++){
		if (i%d==0) ans++;
	}
	cout <<ans<<endl;
	return 0;
}


Measured memory_bytes: 3592
//
//  main.cpp
//  tpcoder
//
//  Created by Sankalp Bhamare on 29/07/20.
//  Copyright © 2020 sankalp. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    int n,k;
    scanf("%d %d",&n,&k);
    vector<int> a(n);
    for(int i = 0; i < n;i++){
        scanf("%d",&a[i]);
    }
    sort(a.begin(), a.end());
    long totalCost = 0;
    for(int i = 0; i < k;i++){
        totalCost += a[i];
    }
    cout << totalCost << endl;
    return 0;

}

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

#define jaldi ios_base::sync_with_stdio(false)
#define fr(i,j,n) for(i=j;i<n;i++)
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%ld",&x)
#define sll(x) scanf("%lld",&x)
#define sc(x) scanf("%c",&x)
#define ss(x) scanf("%s",x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%ld",x)
#define pll(x) printf("%lld",x)
#define pc(x) printf("%c",x)
#define ps(x) printf("%s",x)
#define vi vector<int> 
#define vl vector<long> 
#define vll vector<long long>
#define vc vector<char>  
#define vs vector<string>
#define vvi vector<vector<int>> 
#define vvll vector<vector<long long>> 
#define F first
#define S second
#define ll long long
#define pb push_back
#define ppii pair<int,int> 
#define ppll pair<long long,long long>
#define ppcc pair<char,char>
#define ppss pair<string,string> 
#define vpll vector<pair<long long,long long>>
#define PI 3.1415926535897932384626
#define precision(x) cout<<fixed<<setprecision(x) 
#define mod 998244353

int x_d[8] = {-1,1,0,0,-1,-1,1,1};
int y_d[8] = {0,0,-1,1,-1,1,-1,1};

ll power(ll b,ll e)
{
    if(b==0)
        return 0;
    
    ll r=1;
    while(e>0)
    {
        if(e%2)
            r=(r*b)%mod;
        b=(b*b)%mod;
        e/=2;
    }
    return r;
}

int main()
{
    jaldi;
    precision(20);
    
    ll n,i;
    cin>>n;

    vll A(n,0);
    ll x;
    fr(i,0,n-1)
    {
        cin>>x;
        // x=0;
        A[x]++;
    }
    // cout<<"ABC";
    fr(i,1,n)
    {
        cout<<A[i]<<endl;
    }
    cout<<0<<endl;

    return 0;
}

Measured memory_bytes: 4844
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF 1e18
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define PI (acos(-1))

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

int main() {

    int c[3][3];
    int sum = 0;
    REP(i, 3) REP(j, 3) {
        cin >> c[i][j];
        sum += c[i][j];
    }
    if (sum % 3 == 0 && sum / 3 == c[0][0] + c[1][1] + c[2][2]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
const int MOD = 1e9+7;
const int MX = 2e5+5;
const ll  INF = 1e18;
const ld  PI = acos((ld) -1);
template<class T> inline void array_input(T a[], size_t n){for(size_t i = 0; i < n; i++)cin >> a[i];}


//#define FILE

int main(){
#ifdef FILE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // 0

    int x;
    cin >> x;
    cout << !x << '\n';

    return 0;
}


Measured memory_bytes: 3628
from collections import deque
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
D = {0:".",1:"#"}
G = {}
C = {}
hist = [[-1 for _ in range(W)] for _ in range(H)]
col = -1
for i in range(H):
    for j in range(W):
        if S[i][j]=="#" and hist[i][j]==-1:
            col += 1
            G[col] = [(i,j)]
            que = deque([(i,j,1)])
            hist[i][j] = col
            cnt = 0
            while que:
                y,x,a = que.popleft()
                if x+1<W and S[y][x+1]==D[1-a]:
                    if a==1 and hist[y][x+1]!=col:
                        cnt += 1
                        que.append((y,x+1,1-a))
                        hist[y][x+1]=col
                    elif a==0 and hist[y][x+1]==-1:
                        G[col].append((y,x+1))
                        que.append((y,x+1,1-a))
                        hist[y][x+1]=col
                if y-1>-1 and S[y-1][x]==D[1-a]:
                    if a==1 and hist[y-1][x]!=col:
                        cnt += 1
                        que.append((y-1,x,1-a))
                        hist[y-1][x]=col
                    elif a==0 and hist[y-1][x]==-1:
                        G[col].append((y-1,x))
                        que.append((y-1,x,1-a))
                        hist[y-1][x]=col
                if x-1>-1 and S[y][x-1]==D[1-a]:
                    if a==1 and hist[y][x-1]!=col:
                        cnt += 1
                        que.append((y,x-1,1-a))
                        hist[y][x-1]=col
                    elif a==0 and hist[y][x-1]==-1:
                        G[col].append((y,x-1))
                        hist[y][x-1]=col
                        que.append((y,x-1,1-a))
                if y+1<H and S[y+1][x]==D[1-a]:
                    if a==1 and hist[y+1][x]!=col:
                        cnt += 1
                        que.append((y+1,x,1-a))
                        hist[y+1][x]=col
                    elif a==0 and hist[y+1][x]==-1:
                        G[col].append((y+1,x))
                        que.append((y+1,x,1-a))
                        hist[y+1][x]=col
            C[col] = cnt
tot = 0
for col in G:
    tot += len(G[col])*C[col]
print(tot)

Measured memory_bytes: 44784
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, k):
        self.n = n
        self.k = k
        #fprint('k') # debug
        #fprint(k) # debug
        self.ans_list = [0] * (k + 1) # var[i] = count of gcd() == i case
        #fprint('self.ans_list') # debug
        #fprint(self.ans_list) # debug
        self.m = 10 ** 9 + 7

    def gcd_count(self, i):
        times = k // i
        cases = pow(times, n, self.m)
        j = i * 2
        while not (j > k):
            cases -= self.ans_list[j]
            j += i
        #fprint('i') # debug
        #fprint(i) # debug
        self.ans_list[i] = cases % self.m

    def run(self):
        for i in range(k, 0, -1):
            #print('i') # debug
            #print(i) # debug
            self.gcd_count(i)
        ans = 0
        for i, a in enumerate(self.ans_list):
            ans += i * a
        #fprint('self.ans_list') # debug
        #fprint(self.ans_list) # debug
        return ans % self.m



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    ans = Solver(n, k).run()
    #fprint('ans') # debug
    print(ans)


    #fprint('\33[32m' + 'end' + '\033[0m') # debug


Measured memory_bytes: 70648
#include <iostream>
#include <math.h>

using namespace std;

int main(void) {

	while (1) {
		int n;
		double ave = 0;
		double var = 0;
		cin >> n;
		int *m = new int[n];

		if (n == 0) break;

		for (int i = 0; i < n; i++) {
			cin >> m[i];
			ave += m[i];
		}
		ave /= n;
		for (int i = 0; i < n; i++) {
			var += pow(m[i] - ave, 2) / n;
		}
		var = sqrt(var);
		cout << var << endl;

		delete[] m;
	}
	
	return 0;
}

Measured memory_bytes: 3280
numbers = ["0","1","2","3","4","5","6","7","8","9"]
a = 0
b = 0
while True:
  try:
    l = [s for s in input()]
  except:
    break
  b = 0
  for s in l:
    if s in numbers:
      b *= 10
      b += int(s)
    else:
      if b != 0:
        a += b
        b = 0
  if b != 0:
    a += b
print(a)

Measured memory_bytes: 7568
#include <stdio.h>

int main(void) {
	int a[100][100], b[100];
	int n, m, sum;
	int i, j;
	
	scanf("%d %d", &n, &m);
	
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	
	for (i = 0; i < m; i++) scanf("%d", &b[i]);
	
	for (i = 0; i < n; i++) {
		sum = 0;
		
		for (j = 0; j < m; j++) sum += a[i][j] * b[j];
		printf("%d\n", sum);
	}
	
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <functional>
#include <set>
#define DB cerr<<"D"<<endl
#define pb push_back
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";}
using P=pair<ll,ll>;
const ll M = 1e9+7;
void add(ll& x, ll y) {x+=y; x%=M;}
void chmax(ll& x, ll y) {if (x<y) x=y;}

int main() {
  int n; cin>>n;
  ll a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  ll an=0, nw=1;
  for(int i=0;i<n;i++) {
    ll us = a[i]/nw;
    if (a[i] - us * nw == 0) us--;
    a[i] -= us * nw;
    an += us;
    if (us == 0) {
      nw = max(nw, a[i]+1);
    } else {
      nw = max(nw, 2LL);
    }
    //cout<<us<<" "<<nw<<endl;
  }
  cout<<an<<endl;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
	long long n, m, d;
	cin >> n >> m >> d;
	double ans = 2.0 * (n - d) * (m - 1) / n / n;
	if (d == 0) {
		ans /= 2;
	}
	printf("%.8f\n", ans);
}


Measured memory_bytes: 256
function main() {
  var
  l = Infinity,
  h = -Infinity;
  input.forEach(function(n){
    n = parseFloat(n);
    l = min(n, l);
    h = max(n, h);
  });
  console.log(h - l);
}

function min(x, y) {
  return x < y ? x : y;
}
function max(x, y) {
  return x > y ? x : y;
}

var
input = '';

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  main();
});

Measured memory_bytes: 7652
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

void Main() {
	string W; cin >> W;
	string T;
	int ans = 0;
	while (cin >> T) {
		if (T == "END_OF_TEXT") break;
		if (T.size() != W.size()) continue;
		bool ok = true;
		REP(i, T.size()) {
			if (0x41 <= T[i] && T[i] <= 0x5a) {
				if (T[i] + 0x20 != W[i]) {
					ok = false;
					break;
				}
	        } else if (0x61 <= T[i] && T[i] <= 0x7a) {
	    	    if (T[i] != W[i]) {
					ok = false;
					break;
				}
	        } else {
				ok = false;
				break;
	        }
		}
		if (ok) ++ans;
	}
	cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}



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

int main() {
    int N;
    cin>>N;
    vector<int>L;
    int tmp;
    for(int i=0;i<N;++i){
        cin>>tmp;
        L.push_back(tmp);
    }
    sort(L.begin(), L.end());
    int sum[2010];
    for(int i=0;i<2010;++i){
        sum[i] = 0;
    }
    for(int i=0;i<N;++i){
        sum[L[i]]++;
    }
    for(int i=1;i<2010;++i){
        sum[i] += sum[i-1];
    }
    /**
    for(int i=0;i<10;++i){
        cout<<sum[i]<<endl;
    }
    **/
    long ans = 0;
    for(int i=0;i<N;++i){
        for(int j=i+1;j<N;++j){
            ans += sum[L[i]+L[j]-1] - j-1;
        }
    }
    cout<<ans<<endl;
}


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

using namespace std;

int main() {
  vector<int> x(5);
  vector<int> y(5);
  for (int i = 0; i < 5; ++i) {
    cin >> x[i];
    if (x[i] % 10 == 0) {
      y[i] = 0;
    } else {
      y[i] = abs((x[i] % 10) - 10);
    }
  }

  vector<size_t> idx(y.size());
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&y](size_t i1, size_t i2) {return y[i1] < y[i2];});
  int ans = 0;
  for (int i = 0; i < 5; ++i) {
    ans += x[idx[i]];
    if (ans % 10 != 0 && i < 4) {
      ans += abs((x[idx[i]] % 10) - 10);
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
sa = input()
sb = input()
sc = input()
now = sa[0]

for i in range(320):
    if now == 'a':
        if len(sa) == 0:
            print('A')
            break
        else:
            now = sa[0]
            sa = sa[1:]
    elif now == 'b':
        if len(sb) == 0:
            print('B')
            break
        else:
            now = sb[0]
            sb = sb[1:]
    elif now == 'c':
        if len(sc) == 0:
            print('C')
            break
        else:
            now = sc[0]
            sc = sc[1:]

Measured memory_bytes: 3064
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,sum=0,i,j,min,max,mid;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    
    sort(a,a+n);
    for(i=0;i<n;i++){
       for(j=i+2;j<n;j++){
           min=i;
           max=j;
           while(max-min>1){
               mid=(min+max)/2;
               if((a[i]+a[mid])>a[j]){
                   max=mid;
                   
               }
               else {
                   min=mid;
               }
           }
           sum=sum+j-max;
       }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define MAXK 100000
#define PRIME 1000000007
using namespace std;
long long pow(long long b, int e){
	long long ret = 1;
	for(; e; b=b*b % PRIME, e/=2)
		if(e & 1)
			ret = ret * b % PRIME;
	return ret;
}
int main(){
	int N, K;
	cin >> N >> K;
	vector<int> divisor[MAXK+1];
	long long cnt[MAXK+1];
	for(int i=1; i<=K; i++)
		for(int j=i+i; j<=K; j+= i)
			divisor[j].push_back(i);
	for(int i=1; i<=K; i++)
		cnt[i] = pow(K / i, N);
	for(int i=K; i; i--)
		for(int d:divisor[i])
			cnt[d] = (cnt[d] + PRIME - cnt[i]) % PRIME;
	long long ans = 0;
	for(int i=1; i<=K; i++)
		ans = (ans + cnt[i] * i) % PRIME;
	cout << ans <<endl;
}




Measured memory_bytes: 14752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int w, h, x, y;
  cin >> w >> h >> x >> y;
  cout << 1.0 * w * h / 2 << " ";
  if (w % 2 == 0 && h % 2 == 0 && x == w / 2 && y == h / 2) {
    cout << 1 << endl;
  } else cout << 0 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (long long i=0; i<n; ++i)
#define rep1(i, n) for (long long i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

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;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll h, w; cin >> h >> w;
    if (h % 3 == 0 || w % 3 == 0) puts("0");
    else {
        ll ans = min(h, w);
        rep1(i, h) {
            ll sa = i * w;
            ll sb = (h-i) * (w/2);
            ll sc = (h-i) * (w - (w/2));
            chmin(ans, max({sa, sb, sc}) - min({sa, sb, sc}));
        }
        rep1(i, w) {
            ll sa = i * h;
            ll sb = (w-i) * (h/2);
            ll sc = (w-i) * (h - (h/2));
            chmin(ans, max({sa, sb, sc}) - min({sa, sb, sc}));   
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
S = input()
sum_list = []

for i in range(1 << (len(S)-1)):
    temp = int(S[0])
    ans = 0
    for j in range(len(S)-1):
        if ((i >> j) & 1) == 1:
            ans += temp
            temp = int(S[j+1])
        else:
            temp = temp*10 + int(S[j+1])
    ans += temp
    sum_list.append(ans)
print(sum(sum_list))


Measured memory_bytes: 3060
#include <stdio.h>

// 入力受付用の変数
#define BUF 200002
char str[BUF];

// 入力された値
long long A, B;
int C, D;

void receive_input() {
	fgets(str, sizeof(str), stdin);
	sscanf(str, "%lld %lld %d %d", &A, &B, &C, &D);
}

long long anti_div(long long n, int x) {
	return n - n / x;
}

long long gcd(int a, int b) {
	if(a < b){
		long long temp = a;
		a = b;
		b = temp;
	}

	long long r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

long long lcm(int a, int b) {
	return (long long)a * b / gcd(a, b);
}

void solve() {
	// long long div_c = anti_div(B, C) - anti_div(A-1, C);
	// long long div_d = anti_div(B, D) - anti_div(A-1, D);
	// long long div_cd = anti_div(B, lcm(C, D)) - anti_div(A-1, lcm(C, D));
	//
	// long long ans = div_c + div_d - div_cd;
	//
	long long div_b = B - B/C - B/D + B/lcm(C,D);
	long long div_a = (A-1) - (A-1)/C - (A-1)/D + (A-1)/lcm(C,D);

	long long ans = div_b - div_a;

	// printf("%lld %lld %lld =>\n", div_c, div_d, div_cd);
	printf("%lld\n", ans);
}

int main(void) {
	receive_input();

	solve();

	return 0;
}


Measured memory_bytes: 128
# https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c

import sys
# sys.setrecursionlimit(100000)
import heapq


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = input_int_list()
    B = input_int_list()
    plus = []
    minus = 0
    cnt = 0

    # a < b はすべて調整の必要あり
    # a < b の補填は それぞれの b > a のうち b-a が大きいところから貪欲に補填する
    for i in range(n):
        d = B[i] - A[i]
        if d > 0:
            minus += d
            cnt += 1
        else:
            heapq.heappush(plus, d)

    while minus > 0 and plus:
        minus -= -heapq.heappop(plus)
        cnt += 1

    if minus <= 0:
        print(cnt)
    else:
        print(-1)
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 97860
#!/usr/bin/env python
"""
This file is part of https://github.com/Cheran-Senthil/PyRival.

Copyright 2018 Cheran Senthilkumar all rights reserved,
Cheran Senthilkumar <hello@cheran.io>
Permission to use, modify, and distribute this software is given under the
terms of the MIT License.

"""
from __future__ import division, print_function

import cmath
import itertools
import math
import operator as op
# import random
import sys
from atexit import register
from bisect import bisect_left, bisect_right
# from collections import Counter, MutableSequence, defaultdict, deque
# from copy import deepcopy
# from decimal import Decimal
# from difflib import SequenceMatcher
# from fractions import Fraction
# from heapq import heappop, heappush

if sys.version_info[0] < 3:
    # from cPickle import dumps
    from io import BytesIO as stream
    # from Queue import PriorityQueue, Queue
else:
    # from functools import reduce
    from io import StringIO as stream
    # from pickle import dumps
    # from queue import PriorityQueue, Queue


if sys.version_info[0] < 3:
    class dict(dict):
        """dict() -> new empty dictionary"""
        def items(self):
            """D.items() -> a set-like object providing a view on D's items"""
            return dict.iteritems(self)

        def keys(self):
            """D.keys() -> a set-like object providing a view on D's keys"""
            return dict.iterkeys(self)

        def values(self):
            """D.values() -> an object providing a view on D's values"""
            return dict.itervalues(self)

    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip


def sync_with_stdio(sync=True):
    """Set whether the standard Python streams are allowed to buffer their I/O.

    Args:
        sync (bool, optional): The new synchronization setting.

    """
    global input, flush

    if sync:
        flush = sys.stdout.flush
    else:
        sys.stdin = stream(sys.stdin.read())
        input = lambda: sys.stdin.readline().rstrip('\r\n')

        sys.stdout = stream()
        register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


def gcd(x, y):
    """greatest common divisor of x and y"""
    while y:
        x, y = y, x % y
    return x


def main():
    n = int(input())
    a, b = map(int, input().split(' '))
    p = list(map(int, input().split(' ')))

    part1 = len(list(filter(lambda x: x <= a, p)))
    part2 = len(list(filter(lambda x: a + 1 <= x <= b, p)))
    part3 = len(list(filter(lambda x: b + 1 <= x, p)))

    print(min(part1, part2, part3))


if __name__ == '__main__':
    sync_with_stdio(False)
    main()


Measured memory_bytes: 28908
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;

int tab[N];

 int main()
 {
	int n,i;
	scanf("%d",&n);

	for(i=1;i<=n;i++)
	{
		scanf("%d",&tab[i]);
	}

	ll wn1,wn2,sum;
	wn1=0;

	sum=0;
	for(i=1;i<=n;i++)
	{
		sum+=tab[i];

		if(i%2==1)	
		{
			if(sum>=0)
			{
				wn1+=(sum+1);
				sum=-1;
			}	
		}

		else if(sum<=0)
		{
			wn1-=(sum-1);
			sum=1;	
		}	
	}

	wn2=0;
	sum=0;
	for(i=1;i<=n;i++)
	{
		sum+=tab[i];

		//printf("(%lld ",sum);

		if(i%2==0)	
		{
			if(sum>=0)
			{
				wn2+=(sum+1);
				sum=-1;
			}	
		}

		else if(sum<=0)
		{
			wn2-=(sum-1);
			sum=1;	
		}	

		//printf("%lld)\n",sum);
	}	

	//p/rintf("%lld %lld\n",wn1,wn2);

	printf("%lld\n",min(wn1,wn2));
 }



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

enum inf = 1_001_001_001;
enum inf6 = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N;
    scan(N);
    auto P = readln.split.map!(x => x.to!int).enumerate.array;

    P.sort!"a.value > b.value"();
    debug {
        writeln(P);
    }

    auto rbt = redBlackTree(-1, N);
    long ans;

    foreach (pi; P) {
        auto i = pi.index.to!int;
        auto v = pi.value;

        int L1, L2, R1, R2;
        L1 = L2 = R1 = R2 = i;
        auto lw = rbt.lowerBound(i);
        auto up = rbt.upperBound(i);
        L1 = L2 = lw.back;
        if (L1 != -1) {
            lw.popBack();
            L2 = lw.back;
        }
        R1 = R2 = up.front;
        if (R1 != N) {
            up.popFront();
            R2 = up.front;
        }
        ans += 1L * (i - L1) * (R2 - R1) * v;
        ans += 1L * (L1 - L2) * (R1 - i) * v;

        rbt.insert(i);
    }

    writeln(ans);
}







void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    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;
}


Measured memory_bytes: 8520
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using P=pair<int,int>;
using G=vector<vector<int>>;
using ll=long long;




int main(){
    int n,m;
    cin>>n>>m;
    int s[m];
    char c[m];

    rep(i,0,m){
        cin>>s[i]>>c[i];
    }

    //vector<int> ans(n,-1);

    for(int i=0;i<1000;i++){
        string num=to_string(i);
        if(num.size()!=n) continue;
        bool able=true;
        rep(j,0,m){
            if(num[s[j]-1]!=c[j]) able=false;
        }
        if(able){
            cout<<i<<endl;
            return 0;
        }
        //else{
        //    cout<<"oppai"<<endl;
        //}
    }


    cout<<-1<<endl;
}/*
        bool able=true;
        string num=to_string(i);
        for(int j=0;j<m;j++){
            if(s[i]>n){
                able=false;
                break;
            }
            if(num[s[i]-1]!=c[i]){
                able=false;
                break;
            }
        }

        if(able){
            cout<<i<<endl;
            return 0;
        }
    }

    cout<<-1<<endl;
}*/


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

#define int             long long int
#define ff              first
#define ss              second
#define pb              push_back

#define vi              vector <int>
#define pii             pair <int, int>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))

#define endl            "\n"
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl



template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve()
{
	int n;
	cin >> n;
	int a[n];
	loop(i, 0, n) cin >> a[i];

	bool f = 0;
	int i = 0, m = 1000, s = 0;

	int x = 0;

	while (i < n)
	{
		if (f)
		{
			while (i < n - 1 and a[i + 1] >= a[i]) i++;
			m += (s * a[i]);
			s = 0;
			f = 0;
		}
		else
		{
			while (i < n + 1 and a[i + 1] <= a[i]) i++;
			s = (m / a[i]);
			x = s * a[i];
			m -= x;
			f = 1;
		}
		i++;

	}
	if (f) m += x;

	cout << m << endl;

	return;

}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt",  "r",  stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t = 1;
	//cin >> t;
	while (t--) solve();

	return 0;
}

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

using namespace std;

static const int INF = 1e9 + 7;

template<typename T>
using Vec = vector<T>;

template<typename T, typename T2>
using P = pair<T, T2>;

template<typename... Args>
using Tup = tuple<Args...>;

template<typename T>
using qp = priority_queue<T, Vec<T>, greater<T> >;

template<typename T>
using pq = priority_queue<T>;

using llong = long long;
using ullong = unsigned long long;
using uint = unsigned int;

template<typename T>
T gcd(T x, T y)
{
	return y ? gcd(y, x % y) : x;
}

void hawawa()
{
	int n;
	int d, x;
	cin >> n;
	cin >> d >> x;
	int ans = x;
	while (n--) {
		int a;
		cin >> a;
		ans += 1 + (d - 1) / a;
	}
	cout << ans << "\n";
}


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


Measured memory_bytes: 256
#include <stdio.h>

int cnt=0;

void merge(int s[],int n,int left,int mid,int right){
	int i,j,k;
	int L[n];
	int R[n];
	int n1 = mid - left;
	int n2 = right - mid;
	
	for(i = 0;i<n1;i++){
		L[i] = s[left + i];
	}
	for(i = 0;i<n2;i++){
		R[i] = s[mid+i];
	}
	L[n1]=10000000000;
	R[n2]=10000000000;
	i = 0;
	j = 0;
	for(k = left;k<right;k++){
		cnt++;
		if(L[i]<=R[j]){
			s[k] = L[i++];
		}
		else{ 
			s[k] = R[j++];
		}
	}
}
	
void mergeSort(int s[],int n,int left,int right){
	if(left+1< right){
		int mid; 
		mid= (left + right)/2;
		mergeSort(s,n,left, mid);
		mergeSort(s,n,mid, right);
		merge(s,n,left,mid, right);
	}
}
	
int main(void){
	int i,n;
	int s[500000];
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&s[i]);
	}
	
	mergeSort(s,n,0,n);
	
	for(i=0;i<n;i++){
		if(i==n-1){
			printf("%d\n",s[i]);
		}
		else{
			printf("%d ",s[i]);
		}
	}
	
	printf("%d\n",cnt);
	
	return 0;
}


Measured memory_bytes: 5660
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
typedef long long ll;

using namespace std;


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int x;
	cin >> x;
	int k = 0;
	int ans = 0;
	while (x > k) {
		ans++;
		k += ans;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int *, int *);

int main(){
  int i,j,n,count = 0;
  int A[100];

  scanf("%d",&n);

  for(i = 0; i < n; i++){
    scanf("%d",&A[i]);
  }

  for(i = 0; i < n-1; i++){
    for(j = n-1; j > i; j--){
      if(A[j] < A[j-1]){
	swap(&A[j],&A[j-1]);
	count++;
      }
    }
  }

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

  printf("\n%d\n",count);

  return 0;

}

void swap(int *x, int *y){
  int p;

  p = *x;
  *x = *y;
  *y = p;
}



Measured memory_bytes: 2124
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define EPS 1e-14

#define all(v) v.begin(),v.end()
#define INF 1<<30
#define mp make_pair
#define pb push_back

#define fi first
#define se second

#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

typedef long long ll;

void solve(){
	long long n,m,a;
	cin >> n >> m;
	a = 1900 * m + 100 * (n-m);
	long long t = pow(2,m);
	cout << a*t <<endl;
}

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

Measured memory_bytes: 256
N, M = map(int, input().split())

if N == 1 and M == 1:
    print('0')
elif N == 1:
    calc = (M * (M-1)) // 2
    print(calc)
elif M == 1:
    calc = (N * (N-1)) // 2
    print(calc)
else:
    calc = (M * (M-1)) // 2 + (N * (N-1)) // 2
    print(calc)

Measured memory_bytes: 3064
def change_n_shinsu(x, n):
    ans = []
    while True:
        shou = x // n
        amari = x % n
        if shou == 0 and amari == 0:
            break
        ans.append(amari)
        x = shou
    # ans = ans.zfill(k)
    return ans

n = int(input())

lst = [26]
for i in range(100):
    lst.append(lst[-1]*26)

ruiseki = [26]
for i in range(1, 100):
    ruiseki.append(ruiseki[-1]+lst[i])

keta = 1
while n > ruiseki[keta-1]:
    keta += 1

if keta == 1:
    print(chr(n+ord('a')-1))
    exit()

n -= ruiseki[keta-2]+1

sin = change_n_shinsu(n, 26)
while len(sin) < keta:
    sin.append(0)
sin = sin[::-1]

ans = ''
for i in range(keta):
    ans += chr(sin[i]+ord('a'))

print(ans)

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

int main() {
    int n, ans;
    ans = 0;
    string s;
    cin >> n >> s;

    for(int i = 0; i < n-2; i++) {
        if(s.at(i) == 'A' && s.at(i+1) == 'B' && s.at(i+2) == 'C') {
            ans++;
        }
    }

    cout << ans << endl;
   
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define hell 998244353
#define PI 3.14159265358979323846
using namespace std;

int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    //int c=0;
    while(t--) {

       ll n,x,m,i,j;
       cin>>n>>x>>m;
       vector<ll> dp;
       dp.pb(0);
       dp.pb(x);
       map<ll,ll> mp;
       mp[x]=1;
       for(i=1;i<min(n,m+5);i++)
       {
           x=(x*x)%m;
           if(x==0)
            break;
           if(mp[x])
            break;
           mp[x]=i+1;
           dp.pb(x);
       }
       if(!x || i==n)
       {
           ll ans=0;
           for(i=0;i<dp.size();i++)
            ans+=dp[i];
           cout<<ans;
           return 0;
       }

       ll c;
       ll pos=mp[x];
       n=n-(pos-1);
       vector<ll> v2;
       for(i=pos;i<dp.size();i++)
        v2.pb(dp[i]);
       ll ans=0;
       for(i=0;i<pos;i++)
        ans+=dp[i];
       c=v2.size();
       for(i=1;i<v2.size();i++)
        v2[i]+=v2[i-1];
        ll r=n/c;
        ans+=v2[c-1]*r;
        r=n%c;
        if(r)
        ans+=v2[r-1];

       cout<<ans;
    }

}


Measured memory_bytes: 7420
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
typedef long long int ll;
using namespace std;
using Graph = vector<vector<int> >;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a,b,c;
cin>>a>>b>>c;

string ans;
if(a==b+c || b==a+c||c==a+b){
    ans="Yes";
}
else{
    ans="No";
}
cout<<ans<<endl;
//system("pause");
return 0;
}

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

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

    vector<int> p(N);
    for (int& x : p) cin >> x, --x;

    vector<int> a(N);
    for (int i = 1; i <= N; i++) {
        a[i - 1] = i * N;
    }

    for (int i = 0; i < N; i++) {
        a[p[i]] += i;
    }

    for (int x : a) cout << x << " ";
    cout << endl;

    reverse(a.begin(), a.end());
    for (int x : a) cout << x / N * N << " ";
    cout << endl;
}


Measured memory_bytes: 896