akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] s = new int[n];
        for (int i = 0; i < n; i++) s[i] = scanner.nextInt();

        int count = mergeSort(s, n, 0, n);

        System.out.println(Arrays.toString(s).replaceAll("[\\[\\],]", ""));
        System.out.println(count);
    }

    private static int mergeSort(int[] s, int n, int left, int right) {
        if (left + 1 >= right) return 0;
        int count = 0;
        int mid = (left + right) / 2;
        count += mergeSort(s, n, left, mid);
        count += mergeSort(s, n, mid, right);
        count += merge(s, n, left, mid, right);
        return count;
    }

    private static int merge(int[] s, int n, int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] l = new int[n1 + 1];
        int[] r = new int[n2 + 1];
        for (int i = 0; i < n1; i++) l[i] = s[left + i];
        for (int i = 0; i < n2; i++) r[i] = s[mid + i];
        l[n1] = Integer.MAX_VALUE;
        r[n2] = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        int count = 0;
        for (int k = left; k < right; k++) {
            count++;
            if (l[i] <= r[j]) {
                s[k] = l[i++];
            } else {
                s[k] = r[j++];
            }
        }
        return count;
    }
}



Measured memory_bytes: 178920
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <assert.h>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
using ll = long long;
using ld = long double;
const ll inf = 1000000000000000008;
ll N, A, B, C, D;
vector<ll> mul = {2, 3, 5};

unordered_map<ll, ll> Map;

ll calc(ll n) {
	if(n==0ll) return 0ll;
	if(n==1ll) return D;
	if(Map.count(n)) return Map[n];
    
	ll ret = inf;
	if(n<ret/D) ret = n*D;
	for(auto x:mul) {
		ll ex;
		if(x==2) ex = A;
		else if(x==3) ex =B;
		else ex = C;
		if(n%x==0) ret = min(ret, calc(n/x)+ex);
		else {
			ll up = (n/x+1)*x;
			ll down = (n/x)*x;
			ret = min(ret, calc(down/x)+D*(n-down)+ex);
			ret = min(ret, calc(up/x)+D*(up-n)+ex);
		}
	}
	return Map[n] = ret;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll tc; cin>>tc;
	while(tc--) {
		cin>>N>>A>>B>>C>>D;
		cout << calc(N) << '\n';
		Map.clear();
	}
	return 0;
}

Measured memory_bytes: 4100
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
#define limit(x, l, r) max(l, min(x, r))
#define lims(x, l, r) (x = max(l, min(x, r)))
#define isin(x, l, r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)), x.end())
#define show(x) cout << #x << " = " << x << endl;
#define PQ(T) priority_queue<T, v(T), greater<T>>
#define bn(x) ((1 << x) - 1)
#define dup(x, y) (((x) + (y)-1) / (y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int main() { 
  int h,w;
  cin >> h>>w;
  vector<string> s(h);
  rep(i,h){
    cin >>s[i];
  }
  rep(i,h){
    rep(j,w){
      bool ok = false;
      if(s[i][j] == '.')continue; 
      rep(k,4){
        int y = i+dy[k];
        int x = j+dx[k];
        if(x<0|x>=w|y<0|y>=h)continue;
        ok|=(s[y][x] == '#');
      }
      if(!ok){
        cout<<"No"<<endl;
        return 0;
      }
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

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

if (A + 2 >= B):
    print(K + 1)
elif (A >= K):
    print(K + 1)
else:
    rest = K - (A - 1)
    if (rest%2 == 0):
        print((B - A) * int(rest / 2) + A)
    else:
        print((B - A) * int(rest / 2) + A + 1)

Measured memory_bytes: 3060
input_num = str(input())

def calc_adding(left_str, skip_cnt, const):
  # 1桁まで来たら、+ を挟めない
  if len(left_str) <= 1 + skip_cnt:
    return int(left_str) + const

  # + の有無で分岐を増やす
  # + を入れない場合
  res_np = calc_adding(left_str, skip_cnt + 1, const)

  # + 入れる場合
  const += int(left_str[:1 + skip_cnt])
  res_p = calc_adding(left_str[1 + skip_cnt:], 0, const)

  return res_np + res_p

res = calc_adding(input_num, 0, 0)
print(res)

Measured memory_bytes: 38384
(let* ((n (read))
       (d (make-array (list n))))
  (loop :for i :from 0 :to (1- n)
        :do (setf (aref d i) (read)))
  (setf d (sort d #'<))
  (format t "~A~%" (- (aref d (/ n 2)) (aref d (1- (/ n 2))))))


Measured memory_bytes: 77264
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int mo = 1000000007;
const int maxn = 100010;
using namespace std;
int n, k, a[maxn], f[maxn];
int mul(int a, int b) {
	ll ans = 1, w = a % mo;
	for ( ; b; b /= 2, w = w * w % mo)
		if (b & 1) ans = ans * w % mo;
	return (int) ans; 
}
int main() {
	scanf("%d%d", &n, &k); a[0] = 0;
	for (int i = 1; i * i <= n; ++ i) if (n % i == 0)
		a[++ a[0]] = i, a[++ a[0]] = n / i;
	if (a[a[0]] == a[a[0] - 1]) -- a[0];
	sort(a + 1, a + a[0] + 1);
	rep(i, 1, a[0]) f[i] = mul(k, (a[i] + 1) / 2);
	rep(i, 1, a[0]) rep(j, 1, i - 1) if (a[i] % a[j] == 0)
		f[i] = (f[i] - f[j] + mo) % mo;
	int ans = 0, INV = mul(2, mo - 2);
	rep(i, 1, a[0]) if (a[i] % 2 == 0) f[i] = (ll) f[i] * INV % mo;
	rep(i, 1, a[0]) ans = (ans + (ll) f[i] * a[i] % mo) % mo;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
map<string,int> mp;
int main()
{
    string st;
    int n,i;
    char fir;
    cin >> n;
    for (i=1;i<=n;i++)
    {
        cin >> st;
        mp[st]++;
        if (((i!=1) && (st[0]!=fir)) || (mp[st]>1)) {cout << "No";return 0;}
        int len=st.size();
        fir=st[len-1];
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
/******************************************
* AHAM BRAHMASHMI ;) *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define F first
#define S second


int main()
{

#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//ios_base& scientific (ios_base& str);
    ll x;
    cin >> x;
    for (int i = -120; i <= 120; i++)
    {
        int f = 0;
        for (int j = -120; j <= 120; j++)
        {
            ll cand1 = max(i, j);
            ll cand2 = min(i, j);
            if (pow(cand1, 5) - pow(cand2, 5) == x)
            {
                cout << cand1 << " " << cand2 << "\n";
                f = 1;
                break;
            }

        }
        if (f)
            break;
    }
    return 0;
}

Measured memory_bytes: 4112
#!/usr/bin/env python3
import sys
import collections

def solve(N: int, K: int, A: "List[int]"):
    a_counter = collections.Counter(A)
    if len(a_counter) <= K:
        print(0)
        return 

    values = sorted(list(a_counter.values()))
    answer = 0
    for i in range(len(a_counter)-K):
        answer += values[i]
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 43760
use std::io;
use std::cmp;


/// https://beta.atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualC_b
/// a - 1 - (k - a)
fn main() {
    let (k, _) = {
        let i = read::<isize>();
        (i[0], i[1])
    };
    let a = read::<isize>().into_iter().max().unwrap();
    println!("{}", cmp::max(2 * a - 1 - k, 0))

}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

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



typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef vector< vector< vector<ll> > > vvvint;
typedef vector<string> vstring;
typedef vector< vector<string> > vvstring;
typedef vector<char> vchar;
typedef vector< vector<char> > vvchar;
typedef vector<long double> vdouble;
typedef vector< vector<long double> > vvdouble;
typedef vector< vector< vector<long double> > > vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ALL(obj) (obj).begin(), (obj).end()
// #define LLONG_MAX 9223372036854775806
#define vmax(vec) *max_element(vec.begin(), vec.end())
#define vmin(vec) *min_element(vec.begin(), vec.end())
#define vsort(vec) sort(vec.begin(), vec.end())
#define vsortgr(vec) sort(vec.begin(), vec.end(), greater<ll>())
#define MOD 1000000007
// #define MOD 998244353
// #define MOD LLONG_MAX
const double PI=3.14159265358979323846;

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




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



void printv(vint &v){
  for(auto e:v) cout<<e<<" ";
  cout<<endl;
}


// 繰り返し二乗法
ll power(ll a, ll b){
  if(a==1)return a;
  // if(a==0)re
  ll res=1;
  while(b>0){
    if(b&1) res=res*a%MOD;
    a=a*a%MOD;
    b>>=1;
  }
  return res;
}

const int MAX=2100000;
 
ll fact[MAX], fact_inv[MAX];
 
void init_fact(ll n){
  fact[0]=1;
  // 階乗の計算
  rep(i, n) fact[i+1]=fact[i]*(i+1)%MOD;
  fact_inv[n]=power(fact[n], MOD-2);
  // 逆元の計算
  for(ll i=n-1;i>=0;i--) fact_inv[i]=fact_inv[i+1]*(i+1)%MOD;
}
 
ll comb(ll n, ll r){
  return (fact[n]*fact_inv[r])%MOD*fact_inv[n-r]%MOD;
}
 
ll perm(ll n, ll r){
  return (fact[n]*fact_inv[n-r])%MOD;
}






int main() {
  cout<<fixed<<setprecision(10);

  string s; cin>>s;

  if(s[2] == s[3] && s[4] == s[5]) puts("Yes");
  else puts("No");


}






Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 998244353

long long dp[303][90999];
long long dp2[303][90999];

void add(long long &x, long long y){
    x = (x + y) % MOD;
}

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

    dp[0][0] = 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<=90000; j++){
            add(dp[i+1][j+a[i]], dp[i][j]);
            add(dp[i+1][j], (2*dp[i][j])%MOD);
        }
    }

    dp2[0][0] = 1;
    for(int i=0; i<N; i++){
        for(int j=0; j<=90000; j++){
            add(dp2[i+1][j+a[i]], dp2[i][j]);
            add(dp2[i+1][j], dp2[i][j]);
        }
    }

    long long sm = 0;
    for(int i=0; i<N; i++)
        sm += a[i];

    long long ans = 0;
    for(int i=sm/2+1; i<=90000; i++)
        add(ans, dp[N][i]);

    if(sm % 2 == 0){
        add(ans, dp[N][sm/2]%MOD);
        add(ans, MOD-dp2[N][sm/2]);
    }

    ans = (3 * ans) % MOD;

    long long pow3 = 1;
    for(int i=0; i<N; i++)
        pow3 = (3 * pow3) % MOD;

    ans = (pow3 - ans + MOD) % MOD;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 429568
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int N;
    scanf("%d", &N);

    char *A, *B, *C;
    A = (char *)malloc(sizeof(char) * N);
    B = (char *)malloc(sizeof(char) * N);
    C = (char *)malloc(sizeof(char) * 2 * N);

    for(int i = 0 ; i <= N ; i++)
        scanf("%c", &A[i]);
    
    for(int i = 0 ; i <= N ; i++)
        scanf("%c", &B[i]);

    for(int i = 0 ; i <= N ; i++){
        printf("%c%c", A[i],B[i]);
    }

    printf("\n");
}

Measured memory_bytes: 128
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, string> pls;

ll a[200010],ans[200010];

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

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

	ll nusuke = sum,arai = 0,res = (ll)1e10;
	for (int i = 0; i < N-1; i++) {
		arai += a[i];
		nusuke -= a[i];
		ans[i] = abs(arai-nusuke);
	}
	sort(ans,ans+N-1);

	res = ans[0];

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

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

int main()
{
	int A;
	int B;
	int C;
	int D;
	int firstArea;
	int secondArea;

	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;

	firstArea = A*B;
	secondArea = C*D;

	if (firstArea > secondArea) {
		cout << firstArea << endl;
	}
	else if (firstArea < secondArea) {
		cout << secondArea << endl;
	}
	else {
		cout << secondArea << endl;
	}

}

Measured memory_bytes: 256
#include <stdio.h>
int main () {
  int n;
  int m;
  double a;

  scanf ("%d", &n);

  if (n % 2 == 0) printf ("0.500000\n");

  else {
    m = (n + 1) / 2;
    a = (double) m / n;
    printf ("%lf\n", a);
  }

  return 0;
}


Measured memory_bytes: 128
import java.util.*;
class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	int po = sc.nextInt();
      	int q = sc.nextInt();
      	int point[] = new int[n];
      	for(int i=0;i<n;i++){
        	point[i] = 0;
        }
      	for(int i=0;i<q;i++){
        	int k = sc.nextInt();
          	point[k-1]++;
        }
      	for(int i=0;i<n;i++){
        	if(po-q+point[i]<=0){
            	System.out.println("No");
            }else{
            	System.out.println("Yes");
            }
        }
    }
}

Measured memory_bytes: 75480
k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    ans = 1
    num = 7 % k
    temp = 7 % k
    while True:
        if num % k == 0:
            print(ans)
            break
        else:
            ans += 1
            temp = temp * 10 % k
            num += temp % k
            num %= k


Measured memory_bytes: 9132
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(int i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int> > a(n, vector<int>(n, 0)), b(n, vector<int>(n, 0));
    rep (i, n) rep (j, n) cin >> a[i][j];
    b = a;
    rep (k, n) rep (i, n) rep (j, n) chmin(b[i][j], b[i][k] + b[k][j]);
    bool wrong = false;
    rep (i, n) rep (j, n) wrong |= (a[i][j] != b[i][j]);
    if (wrong) {
        cout << -1 << "\n";
    } else {
        vector<vector<bool> > use(n, vector<bool>(n, false));
        rep (i, n) rep (j, n) if (i != j) use[i][j] = true;
        rep (i, n) {
            rep (j, n) {
                rep (k, n) {
                    if (i == j || j == k || k == i) continue;
                    if (a[i][j] == a[i][k] + a[k][j]) {
                        use[i][j] = false;
                        break;
                    }
                }
            }
        }
        ll ans = 0;
        rep (i, n) repp (j, i + 1, n) if (use[i][j]) ans += a[i][j];
        cout << ans << "\n";
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>

using namespace std;

long long int A, B, C;

int main() {
	cin >> A >> B >> C;
	if (A != B && A != C)cout << A << endl;
	if (B != A && B != C)cout << B << endl;
	if (C != A && C != B)cout << C << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define db double
const int N=1e6;

#define C getchar()-48
ll read()
{
  ll s=0,t=1,k=C;
  for (;k<0||9<k;k=C) if (k==-3) t=-1;
  for (;0<=k&&k<=9;k=C) s=(s<<1)+(s<<3)+k;
  return s*t;
}

//如题意 
  ll n,L;
	ll t[N],v[N];
void in()
{
  cin>>n>>L;
  for (int i=0;++i<=n;)
	  t[i]=read(),v[i]=read();
}

//单调队列 
  ll l=1,r; 
  struct rec
    {
      ll v;
      db t;
    }s[N];

//混合
#define mix(a,b) (s[a].t*s[a].v+s[b].t*s[b].v)/(s[a].v+s[b].v)

  ll sum,prod,de;
  db A[N];
void wor()
{
  for (int i=0;++i<=n;)
    {

      while (sum+v[i]>L)
        {
          de=min(s[l].v,sum+v[i]-L);
          s[l].v-=de;
          sum-=de;
          prod-=de*s[l].t;
          if (!s[l].v) l++;
        }
        
      sum+=s[++r].v=v[i];
			s[r].t=t[i];
      prod+=v[i]*t[i];
      
      while (l<r&&s[r].t<s[r-1].t)
        s[--r].t=mix(r,r+1),
				s[r].v+=s[r+1].v;

      A[i]=(db)prod/L;
    }
}

void out()
{
  for (int i=0;++i<=n;)
    printf("%lf\n",A[i]);
}

int main()
{
  in();
	wor();
	out();
  exit(0);
}

Measured memory_bytes: 35200
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const int MAX = 100000;
static const int NIL = -1;
using namespace std;

 ll calC(ll a, ll b){

     if(a == 1) return 0;
     ll ans = 1;
    ll tmpB = b;
    ll tmpA = a;
    for(int i = 1; i <= b; i ++){
         ans *= tmpA;
         tmpA --;
     }
     for(int i = 1; i <= b; i ++){
         ans /= tmpB;
         tmpB --;
     }

    return ans;
}
int main() {
    ll n; cin >> n;
    ll ans = 0;
    ll count = 1;
    string prev = "",cur;
    vector<string> s(n);
    vector<string> S(n);
    rep(i,n) {
        cin >> s[i];
        sort(s[i].begin(),s[i].end());
        S[i] = s[i];
    }
    sort(S.begin(),S.end());


    prev = S[0];
    for(int i = 1; i < n; i ++){
        cur = S[i];
        if(prev != cur){
            ans += calC(count,2);
            count = 1;
        }else{
            count ++;
        }
        prev = cur;
    }

    ans += calC(count,2);
    count = 0;

    cout << ans;

    return 0;
}

Measured memory_bytes: 9512
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>

#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	int n, t, a;
	cin >> n >> t >> a;

	double mini = 1000000;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		double tmp = t - x * 0.006;
		if (abs(a - tmp) < mini) {
			ans = i + 1;
			mini = abs(a - tmp);
		}
	}

	COUT(ans);

	return 0;
}


Measured memory_bytes: 256
N = int(input())

start = 0
end = 0

person = N

cap = [10 ** 15 + 1]

for _ in range(5) :
    cap.append(int(input()))

for i in range(1, 6) :
    person = N - (end - start) * cap[i]
    if person <= 0 :
        person = 1
    end += - (- person // cap[i])
    start += 1
print(end)


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

int main()
{
	string s;
	cin >> s;
	int n = s.size();
	string ans;
	for(int i = 0;i<n;i++)
	{
		if(s[i]=='B')
		{
			if(!ans.empty())
			{
				ans.pop_back();
			}
		}
		else
		{
			ans.push_back(s[i]);
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
# AOJ 1026 Hedro's Hexahedron
# Python3 2018.7.5 bal4u

while True:
	n = int(input())
	if n == 0: break
	ans = s = n >> 1
	i, k = 1, 2
	while i*i < s:
		ans += (n+k-1)//k
		i += 1
		k += 2
	ans = ans*2 - i*i
	if n & 1: ans += 1
	print((ans+n) << 3)


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

using namespace std;

int main() {
    long long n, q, num, a, b, sum = 0;
    cin >> n;
    unordered_map<int, int> M;
    for (int i = 0; i < n; i++) {
        cin >> num;
        sum += num;
        M[num]++;
    }
    cin >> q;
    while (q--) {
        cin >> a >> b;
        M[b] += M[a];
        sum += ((b - a) * M[a]);
        M[a] = 0;
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 7076
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
using namespace std;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
typedef pair<int,int> P;
int n,used[12][6],cnt;
char mas[13][6];
bool is_color(char s){
  return (s != '.' && s != 'O');
}
bool no_over(int i,int j){
  if(i < 0 || i >= 12 || j < 0 || j >= 6) return false;
  return true;
}
void ELASE(){
  for(int i=0;i<12;i++){
    for(int j=0;j<6;j++){
      if(used[i][j]){
        mas[i][j] = '.';
        for(int k=0;k<4;k++){
          int nx = i + dx[k] , ny = j + dy[k];
          if(mas[nx][ny] == 'O') mas[nx][ny] = '.';
        }
      }
    }
  }
}
int search(int x,int y,char m){
  if(used[x][y]) return 0;
  used[x][y] = true;
  cnt++;
  for(int i=0;i<4;i++){
    int nx = x + dx[i] , ny = y + dy[i];
    if(no_over(nx,ny)){
      if(mas[nx][ny] == m){
        search(nx,ny,m);
      }
    }
  }
}
void Down(){
  for(int k=0;k<72;k++){
    for(int i=0;i<12;i++){
      for(int j=0;j<6;j++){
        if(mas[i+1][j] == '.'){
          swap(mas[i][j],mas[i+1][j]);
        }
      }
    }
  }
}
int solve(){
  int rec; bool flg;
  for(rec = -1 , flg = false ; !flg ; rec++){
    flg = true;
    Down();
    for(int i=0;i<12;i++){
      for(int j=0;j<6;j++){
        if(is_color(mas[i][j])){
          cnt = 0;
          memset(used,false,sizeof(used));
          search(i,j,mas[i][j]);
          if(cnt >= 4){
            flg = false;
            ELASE();
          }
        }
      }
    }
  }
  return rec;
}
int main(){
  cin >> n;
  while(n--){
    for(int i=0;i<12;i++){
      for(int j=0;j<6;j++){
        cin >> mas[i][j];
      }
    }
    cout << solve() << endl;
  }
}

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

int main(){
  string s;
  getline(cin, s);
  if(s[0]==s[1]&&s[1]==s[2]){
    cout << "Yes" << endl;
  }else if(s[2]==s[3]&&s[1]==s[2]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3592
package main

import (
	"bufio"
	"fmt"
	basicIO "io"
	"os"
	"strconv"
)

func main() {
	protagonist(os.Stdin, os.Stdout)
}

func protagonist(r basicIO.Reader, w basicIO.Writer) {
	io := NewIO(r, w)
	N := io.nextInt()
	arr := make([][][]int, N)
	for i := range arr {
		arr[i] = make([][]int, io.nextInt())
		for j := range arr[i] {
			arr[i][j] = make([]int, 2)
			arr[i][j][0] = io.nextInt()
			arr[i][j][1] = io.nextInt()
		}
	}

	max := 0
	for i := 0; i < pow2(N); i++ {
		for j := 0; j < N; j++ {
			if (i%pow2(j+1))/pow2(j) == 0 {
				//io.PutString(fmt.Sprintf("pass:%b %d", i, j))
				continue
			}
			for _, v := range arr[j] {
				if (i&pow2(v[0]-1) > 0) == (v[1] == 1) {
					continue
				}
				//io.PutString(fmt.Sprintf("goto:%b %d v0:%d v1:%d", i, j, v[0], v[1]))
				goto HOGE
			}
		}
		if n := num(i, N); max < n {
			max = n
			//io.PutString(fmt.Sprintf("set:%b n:%d", i, n))
		}
	HOGE:
	}
	io.PutInt(max)
}

func num(i, N int) int {
	acc := 0
	for j := 0; j < N; j++ {
		if (i%pow2(j+1))/pow2(j) == 1 {
			acc++
		}
	}
	return acc
}

func pow2(n int) int {
	acc := 1
	for i := 0; i < n; i++ {
		acc *= 2
	}
	return acc
}

type IO struct {
	Scanner *bufio.Scanner
	Writer  basicIO.Writer
}

func NewIO(r basicIO.Reader, w basicIO.Writer) *IO {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	return &IO{
		Scanner: s,
		Writer:  w,
	}
}

func (io *IO) nextString() string {
	io.Scanner.Scan()
	return io.Scanner.Text()
}

func (io *IO) nextInt() int {
	io.Scanner.Scan()
	i, _ := strconv.Atoi(io.Scanner.Text())
	return i
}

func (io *IO) PutInt(v int) {
	fmt.Fprintf(io.Writer, "%d\n", v)
}

func (io *IO) PutString(s string) {
	fmt.Fprintf(io.Writer, "%s\n", s)
}


Measured memory_bytes: 640
/********************************
* AUTHOR:  ARNAB SEN             *
* NICK  :  arnab1729             *
* INSTITUTION: IIEST, SHIBPUR    *
********************************/

#include<bits/stdc++.h>

using namespace std;

typedef string                         STR;
typedef long long                      LL;
typedef long double                    LD;
typedef unsigned long long             ULL;
typedef vector<int>                    VI;
typedef priority_queue<int>            PQI;
typedef vector<LL>                     VLL;
typedef vector<ULL>                    VULL;
typedef vector<STR>                    VS;
typedef vector<char>                   VC;
typedef pair<int,int>                  PII;
typedef pair<LL,LL>                    PLL;
typedef pair<STR,int>                  PSI;
typedef pair<int,STR>                  PIS;
typedef vector<PII>                    VII;
typedef map<int,int>                   MII;
typedef map<LL,LL>                     MLL;
typedef map<STR,int>                   MSI;
typedef map<char,int>                  MCI;
typedef map<int,STR>                   MIS;
typedef set<STR>                       SS;
typedef set<int>                       SI;
typedef set<LL>                        SLL;

#define FF                             first
#define SS                             second
#define PB                             push_back
#define PF                             push_front
#define MP                             make_pair
#define all(a)                         (a).begin(), (a).end()
#define dec(n)                         cout<<fixed<<setprecision(n);
#define f(i, n)                     for(LL i=0; i<n; i++)
#define fr(i,n)                     for(LL i=n-1; i>=0; i--)

#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL))

const LL MOD     = 1000000007;
const LL SIZE    = 100000;
const int INF    = 0x3f3f3f3f;
const LL LL_INF  = 0x3f3f3f3f3f3f3f3f;
const LD PI      = acos(-1);
const LL MAXN    = numeric_limits<LL>::max();

template<class T>  T maxT(T a, T b){return (a>b?a:b);}
template<class T>  T minT(T a, T b){return (a<b?a:b);}
template<class T>  void setmin(T &a, T b){a=(a>b ?a:b);}
template<class T>  void setmax(T &a, T b){a=(a<b ?a:b);}

void fileio(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
}

void ofileio(){
  freopen("input.txt","r", stdin);
  freopen("output.txt", "w", stdout); 
}

void clock_out(){
  cerr<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
}


void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << H;
  debug_out(T...);
}
 
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define fio() fileio()
#define ofio ofileio()
#define clock() clock_out()
#else
#define debug(...) 1
#define fio() 1
#define ofio() ofileio()
#define clock() 1
#endif

void solve(){
   dec(7);
   LD l;
   cin>>l;
   l=l/3;
   cout<<l*l*l;
}

int main(){
  fast;
  //fio();

  LL t=1;
  //cin>>t;
  while(t--){
      solve();
  }
  clock();
  return 0;
}


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

l = []
r = []
for i in range(k):
  a, b = map(int, input().split())
  l.append(a)
  r.append(b)

mod = 998244353

dp = [0] * (n + 1)
#１マス目の行き方は１通り
dp[1] = 1
dpsum = [0] * (n + 1)
dpsum[1] = 1
for i in range(2, n + 1):
  for j in range(k):
    li = i - r[j]
    ri = i - l[j]
    if ri < 0:
      continue
    li = max(1, li)

    dp[i] += (dpsum[ri] - dpsum[li - 1]) % mod
  
  dpsum[i] = dpsum[i - 1] + dp[i]

print(dp[n] % mod)



Measured memory_bytes: 29972
N,A,B = $stdin.gets.chomp.split(" ").map{ |a| a.to_i }
V = $stdin.gets.chomp.split(" ").map{ |a| a.to_i }.sort.reverse

Combs = (1..N).map{ |n|
  v = 1
  (0..n).map{ |r|
    v0 = v
    v = v * (n-r) / (r+1)
    v0
  }
}



def gcd(x,y)
  return gcd(y,x) if x < y
  return x if y == 0
  gcd(y,x % y)
end

def comb(n,r)
  Combs[n-1][r]
end


Os = (A..B).map{ |n| [n, V[0...n].inject(:+)] }.sort{ |a,b| a[1]*b[0] <=> b[1]*a[0] }.reverse
       .each{ |o| g = gcd(o[1],o[0]); o[1] = o[1]/g; o[2] = o[0]/g }

MAV = [Os[0][1],Os[0][2]]

Ws = Os.select{  |o| o[1] == MAV[0] && o[2] == MAV[1] }

#p Ws

ways = 0
Ws.map { |w|
  k = V[w[0]-1]
  n = V.count(k)
  r = V[0...w[0]].count(k)
  ways += comb(n,r)
}

puts sprintf("%1.6f", MAV[0].to_f / MAV[1])
puts sprintf("%d", ways)





Measured memory_bytes: 1788
import Control.Monad
import Data.List

f :: Int -> Int -> [Int] -> [Int] -> Int
f r s [] _ = r
f r s (x:xs) (sgn:sgns)
  | signum ns == sgn = f r ns xs sgns
  | otherwise = f (r + abs (ns - sgn)) sgn xs sgns
  where 
    ns = s + x

calc xs = let sgns = cycle [1, -1] in min (f 0 0 xs sgns) (f 0 0 xs (tail sgns))

main = getLine >> getLine >>= print . calc . map read . words

Measured memory_bytes: 36220
using System;
using System.Collections.Generic;

namespace AtCoder2020Ned
{
    class Program
    {
        static void Main(string[] args)
        {
            var hon = new List<string>(new[] { "2", "4", "5", "7", "9" });
            var pon = new List<string>(new[] { "0", "1", "6", "8" });
            var bon = new List<string>(new[] { "3" });

            var input = Console.ReadLine().ToCharArray();

            if (hon.Contains(input[input.Length - 1].ToString()))
            {
                Console.WriteLine("hon");
            }
            else if (pon.Contains(input[input.Length - 1].ToString()))
            {
                Console.WriteLine("pon");
            }
            else
            {
                Console.WriteLine("bon");
            }

            Console.Read();
        }
    }
}


Measured memory_bytes: 26012
dx=[-1,0,1,-1,1,-1,0,1]
dy=[-1,-1,-1,0,0,1,1,1]
h,w=map(int,input().split())
field = []
for i in range(h):
    field.append(list(input()))
for y in range(h):
    for x in range(w):
        if field[y][x]=="#":
            continue
        cnt=0
        for k in range(8):
            nx=x+dx[k]
            ny=y+dy[k]
            if nx<0 or nx>=w or ny<0 or ny>=h:
                continue
            if field[ny][nx]=="#":
                cnt+=1
        field[y][x]=str(cnt)
for i in range(h):
    print("".join(field[i]))

Measured memory_bytes: 3188
//2019.4.13 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
#define RG register
inline int read(){
    res s=0,ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline LL Read(){
    RG LL s=0;
    res ch=getchar();
    bool w=0;
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void swap(res &x,res &y){
    x^=y^=x^=y;
}
const int N=1e5+10;
namespace MAIN{
    int n;
    char str[N];
    int ans;
    int sum;
    inline void MAIN(){
        scanf("%s",str+1);
        n=strlen(str+1);
        for(res i=1;i<=n;i++){
            if(str[i]-'0'!=(i&1))ans++;
        }
        for(res i=1;i<=n;i++){
            if(str[i]-'0'==(i&1))sum++;
        }
        printf("%d\n",min(ans,sum));
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

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

ll mod=1e9+7;

ll pow(ll x,ll n){
    if(n==0)return 1;
    ll res=pow(x*x%mod,n/2);
    if(n&1)res=res*x%mod;
    return res;
}

int main(){
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    V memo(k+1,0);

    /*V prime(1e7);
    vector<bool> is_prime(1e7,true);
    ll p=0;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<1e7;i++){
        if(is_prime[i]){
            prime[p++]=i;
            for(ll j=2*i;j<1e7;j+=i)is_prime[j]=false;
        }
    }*/

    for(ll i=k;i>=1;i--){
        ll x=k/i;
        if(x==1){
            memo[i]=1;
            ans+=memo[i]*i;
        }else{
            ll kaburi=0;
            for(ll s=2;s*i<=k;s++){
                kaburi+=memo[s*i];
                kaburi%=mod;
            }
            memo[i]=pow(x,n)-kaburi;
            ans+=memo[i]*i;
        }
        ans%=mod;
    }
    cout<<(ans+mod)%mod<<endl;
}


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

int main()
{
	while (true)
	{
		int m, f, r;
		cin >> m >> f >> r;
		if ((m == -1) && (f == -1) && (r == -1))break;
		if ((m == -1) || (f == -1)) {
			cout << "F" << endl;
		}
		else if ((m + f) >= 80)
		{
			cout << "A" << endl;
		}
		else if ((m + f) >= 65)
		{
			cout << "B" << endl;
		}
		else if ((m + f) >= 50)
		{
			cout << "C" << endl;
		}
		else if ((m + f) >= 30)
		{
			if (r >= 50) {
				cout << "C" << endl;
			}
			else
			{
				cout << "D" << endl;
			}
		}
		else
		{
			cout << "F" << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3092
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    
    ans = 0
    for a in range(1, N+1):
        ans += N // a
        if N % a == 0:
            ans -= 1
    
    print(ans)


if __name__ == '__main__':
    main()

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

int main()
{
    int n,ans=1,m=7;

    cin>>n;

    if(n%10==5||(n%10)%2==0){
        ans=-1;
    }
    else{
        while(1){
            if(m%n==0){
                break;
            }
            m=(m%n)*10+7;
            ans++;
        }
    }
    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 3612
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    System.out.print(sc.next().toUpperCase().charAt(0));
    System.out.print(sc.next().toUpperCase().charAt(0));
    System.out.print(sc.next().toUpperCase().charAt(0));
    System.out.println();
  }
}

Measured memory_bytes: 21460
#include<iostream>
#include<cstring>
using namespace std;
int save[1000][10];
int fun(char op,int num[]) {
	int tmp = num[1];
	switch(op) {
		case 'N':
			num[1] = num[2];
			num[2] = num[6];
			num[6] = num[5];
			num[5] = tmp;
			break;
		case 'W':
			num[1] = num[3];
			num[3] = num[6];
			num[6] = num[4];
			num[4] = tmp;
			break;
		case 'E':
			num[1] = num[4];
			num[4] = num[6];
			num[6] = num[3];
			num[3] = tmp;
			break;
		case 'S':
			num[1] = num[5];
			num[5] = num[6];
			num[6] = num[2];
			num[2] = tmp;
			break;
	}
	return 0;
}

bool equal(int a[], int b[]) {
	for(int i=1;i<=6;i++) if(a[i]!=b[i]) return false;
	return true;
}

int main() {
	//freopen("in","r",stdin);
	int n; cin>>n;
	for(int i=0;i<n;i++) {
		for(int j=1;j<=6;j++) {
			cin>>save[i][j];
		}
	}
	bool all_different = 1;
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<n;j++) {
			if(equal(save[i],save[j])) all_different = 0;
			for(int cishu1=1;cishu1<=4;cishu1++) {
				fun('N',save[j]);
				if(equal(save[i],save[j])) all_different = 0;
				for(int cishu2=1;cishu2<=4;cishu2++) {
					fun('W',save[j]);
					if(equal(save[i],save[j])) all_different = 0;
					for(int cishu3=1;cishu3<=4;cishu3++) {
						fun('E',save[j]);
						if(equal(save[i],save[j])) all_different = 0;
						for(int cishu4=1;cishu4<=4;cishu4++) {
							fun('S',save[j]);
							if(equal(save[i],save[j])) all_different = 0;
						}
					
					}
				}
			}
		}
	}
	
	if(all_different) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

void solve(){
	int h,w,k;
	cin>>h>>w>>k;
	string s[h];
	int ans=0;
	for(int i=0;i<h;i++){
		cin>>s[i];
	}
	for(int i=0;i<(int)1<<h;i++){
		for(int j=0;j<(int)1<<w;j++){
			string temp[h];
			for(int k=0;k<h;k++) temp[k]=s[k];
			// for(int k=0;k<h;k++){
			// 	for(int l=0;l<w;l++){
			// 		cout<<temp[k][l];
			// 	}
			// 	cout<<endl;
			// }
			// cout<<endl;
			for(int k=0;k<h;k++){
				if(bool( ((int)1<<k) & (i) )>0){
					for(int l=0;l<w;l++) temp[k][l]='.';
				}
			}
			for(int k=0;k<w;k++){
				if(bool( ((int)1<<k) & (j) )>0){
					for(int l=0;l<h;l++) temp[l][k]='.';
				}
			}
			int res=0;
			for(int k=0;k<h;k++){
				for(int l=0;l<w;l++){
					if(temp[k][l]=='#') res++;
				}
			}
			if(res==k){ans++; //cout<<i<<" "<<j<<endl;
			}
		}
	}
	cout<<ans<<endl;
}

int32_t main(){
	IOS;
	int t=1;
	//cin>>t;
	while(t--){
		solve();	
	}
}

Measured memory_bytes: 3664
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;


int main() {

    while (true) {

        int n, w;
        cin >> n >> w;

        if (n == 0 && w == 0) break;

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

        int width = 0;
        for (int i = 0; i < n; i++) width = max(width, v[i] / w + 1);

        vector<int> h(width, 0);
        for (int i = 0; i < n; i++) h[v[i] / w]++;

        int highest = *max_element(h.begin(), h.end());

        vector<double> h_rate(width, 0);
        for (int i = 0; i < width; i++) h_rate[i] = (double) h[i] / (double) highest;
//        for (int i = 0; i < width; i++) cout << fixed << setprecision(10) << h_rate[i] << " ";
        cout << endl;


        vector<double> w_rate(width, 0);
        for (int i = 0; i < width; i++) w_rate[i] = 1 - (1.0 / (double) (width - 1)) * i;
//        for (int i = 0; i < width; i++) cout << fixed << setprecision(10) << w_rate[i] << " ";

        double ans = 0;
        for (int i = 0; i < width; i++) ans += (h_rate[i] * w_rate[i]);
        ans += 0.01;
        cout <<  fixed << setprecision(10) << ans << endl;

    }

    return 0;
}

































Measured memory_bytes: 3200
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int mod = 1000000007;
const int INF = 1001001001;

vector<long long> fct(0),invfct(0);

long long modpow(long long a,long long n, long long mod){
    long long res = 1;
    while(n>0){
        if ( n & 1 ) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

void fct_input(long long maximum,long long mod){
    fct.resize(maximum+1,-1);
    fct.at(0) = 1;
    fct.at(1) = 1;
    long long x = 1;
    for(long long i=2;i<=maximum;i++){
        x = x * i % mod;
        fct.at(i) = x;
    }
 }

void invfct_input(long long maximum,long long mod){
    invfct.resize(maximum+1,-1);
    invfct.at(0) = 1;
    invfct.at(1) = 1;
    long long x = 1;
    for(long long i=2;i<=maximum;i++){
        x = x * i % mod;
        invfct.at(i) = modpow(x,mod - 2,mod);
    }
}

ll nck(int n,int k){
  if(n<k) return 0;
  return ((invfct.at(k) * invfct.at(n-k) % mod) * fct.at(n) ) % mod; 
}

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

  fct_input(n,mod);
  invfct_input(n,mod);

  vector<ll> a(n);
  rep(i,n) cin >> a.at(i);
  sort(a.begin(),a.end());
  ll minus = 0, plus = 0;
  
  rep(i,n){
    int x = (a.at(i)) * nck(i,k-1)%mod;
    if(x<0) x+=mod;    
    plus = (plus + x)%mod;
  }
  rep(i,n){
    int x = a.at(i) * nck(n-1-i,k-1)%mod;
    if(x<0) x+mod;
    minus = (minus + x)%mod;
  }
  ll ans = (plus-minus)%mod;
  if(ans<0) ans+=mod;
  cout << ans << endl;
}


Measured memory_bytes: 2560
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int x,y;
    R(x,y);
    int d=y-x;
    W(d*(d-1)/2-x);
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	List<Long> A, B;
	int N;
	List<Long> diffs;

	Main() {
		Scanner in = new Scanner(System.in);
		N = Integer.parseInt(in.nextLine());
		A = new ArrayList<>(N);
		B = new ArrayList<>(N);
		String[] tokens = in.nextLine().split(" ");
		for (int i = 0; i < tokens.length; ++i) {
			A.add(Long.parseLong(tokens[i]));
		}
		tokens = in.nextLine().split(" ");
		for (int i = 0; i < tokens.length; ++i) {
			B.add(Long.parseLong(tokens[i]));
		}
		in.close();

		diffs = new ArrayList<>(N);
		for (int i = 0; i < N; ++i) {
			diffs.add(A.get(i) - B.get(i));
		}
	}

	int calc() {
		List<Long> pluses = new ArrayList<>();
		List<Long> minuses = new ArrayList<>();
		long minusSum = 0;
		for (int i = 0; i < N; ++i) {
			if (diffs.get(i) > 0) {
				pluses.add(diffs.get(i));
			}
			if (diffs.get(i) < 0) {
				minuses.add(diffs.get(i));
				minusSum -= diffs.get(i);
			}
		}
		if (minusSum == 0) {
			return 0;
		}
		Collections.sort(pluses);
		Collections.reverse(pluses);
		long sum = 0;
		int result = 0;
		for (int i = 0; i < pluses.size(); ++i) {
			sum += pluses.get(i);
			if (sum >= minusSum) {
				result = i + 1;
				break;
			}
		}
		result += minuses.size();
		return result;
	}

	boolean isEnable() {
		long sum = 0L;
		for (Long diff : diffs) {
			sum += diff;
		}
		if (sum >= 0) {
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) {
		Main ins = new Main();
		if (!ins.isEnable()) {
			System.out.println(-1);
		} else {
			System.out.println(ins.calc());
		}
	}

}

Measured memory_bytes: 56380
from heapq import heappop,heappush
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
bc=[[int(i) for i in input().split()]for j in range(m)]
bc=sorted(bc, key=lambda x:x[1],reverse=True)

ans=[]
for b,c in bc:    
    while b>0 and a: 
        x = heappop(a)
        if x<c:
            ans.append(c)
            b-=1
        else:
            ans.append(x)
print(sum(ans)+sum(a))

Measured memory_bytes: 27852
#include<iostream>

using namespace std;

int main(){
  int y,m,d;
  char s1,s2;

  cin>>y>>s1>>m>>s2>>d;

  if(y<2019){
    cout<<"Heisei";
    return 0;
  }

  else if(y==2019){
    if(m<4){
      cout<<"Heisei";
      return 0;
    }
    else if(m==4){
      if(d<=30){
        cout<<"Heisei";
        return 0;
      }
      else{
        cout<<"TBD";
        return 0;
      }

    }
    else{
      cout<<"TBD";
      return 0;
    }
  }

  else{
    cout<<"TBD";
    return 0;
  }

  return 0;

}


Measured memory_bytes: 256