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

// 插入此處

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int N; cin >> N;
    vector<int> A(N), acc(N+1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        ++acc[A[i]];
    }
    LL ans = 0;
    for (int i = 1; i <= N; ++i) {
        ans += 1LL * acc[i] * (acc[i] - 1) / 2;
    }
    for (int i = 0; i < N; ++i) {
        LL diff = 0;
        diff -= acc[A[i]] * (acc[A[i]] - 1) / 2;
        if (acc[A[i]] > 1) {
            diff += (acc[A[i]] - 1) * (acc[A[i]] - 2) / 2;
        }
        cout << ans + diff << endl;
    }
    return 0;
}


Measured memory_bytes: 4224
S = gets.chomp.split('')

loop.each do
  if S.size == 0
    puts 'YES'; exit
  elsif S.first(6).join == 'eraser'
    S.shift 6
  elsif S.first(5).join == 'erase'
    S.shift 5
  elsif S.first(11).join == 'dreameraser'
    S.shift 11
  elsif S.first(10).join == 'dreamerase'
    S.shift 10
  elsif S.first(7).join == 'dreamer'
    S.shift 7
  elsif S.first(5).join == 'dream'
    S.shift 5
  else
    puts 'NO'; exit
  end
end

Measured memory_bytes: 12540
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n;
	int m = 1;
	int z = 0;
	cin >> n;
	vector<int> a(n-1);
	vector<int> b(n,0);
	for (int i = 0;i < n - 1;i++) {
		cin >> a[i];
		b[a[i] - 1] += 1;
	}

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


Measured memory_bytes: 4844
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#include <numeric>
#include <stdio.h>
#include <map>
#include <iomanip>
#include <sstream>
//#include <boost/math/common_factor_rt.hpp>
#include<fstream>
#define EPS (1e-7)
using namespace std;
#define ll long long



class Employee {
public:
	int id;
	int parent;
	vector<int> children;
	int salary;

	Employee() {
		
	}

	Employee(int num, int nparent) {
		id = num;
		parent = nparent;
		salary = -1;
	}



};



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

bool check(vector<int> &v) {
	int s = v.size();
	bool ans = true;
	for (auto i = 0; i < s-1; i++)
	{
		if (v[i] > v[i + 1]) {
			ans = false;
			break;
		}
	}
	return ans;

}


vector<int> grow(vector<int>& vs) {
	for (auto& v : vs) {
		v -= 1;
	}
	return vs;
}


pair<int, int> count_nonzero_cluster(vector<int>& vs) {

	int number = 0;
	int prev = 0;
	int vmax = -1;
	pair<int, int> re = make_pair(number, vmax);
	for (auto& v:vs)
	{
		if (prev <= 0 && v > 0) {
			re.first += 1;
		}
		if (re.second < v)re.second = v;
		prev = v;
	}


	return re;
}

int main() {
	
	int N;
	cin >> N;
	vector<int> h(N);
	int ans = 0;
	for (auto i = 0; i < N; i++)
	{
		cin >> h[i];
	}

	pair<int, int> temp = make_pair(1,1);
	while (temp.second != 0) {
		temp = count_nonzero_cluster(h);
		ans += temp.first;
		grow(h);
	}

	cout << ans << endl;

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int ans = 0;
  for (int i = 1; i <= N; i += 2) {
    int c = 1;
    int h = i;
    for (int j = 2; j < sqrt(i); j++) {
      int k = 1;
      while (h % j == 0) {
        h /= j;
        k++;
      }
      c *= k;      
    }
    if (h != 1) {
      c *= 2;
    }
    if (c == 8) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3684
import java.util.*;

public class Main {

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

        long a = sc.nextInt();
        long b = sc.nextLong();
        long n = sc.nextLong();

        if(b > n) {
            System.out.println((int)Math.floor(a * n / b));
        } else {
            System.out.println((int)Math.floor(a * (b - 1) / b));
        }

        sc.close();
    }

}

Measured memory_bytes: 35816
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	var hs []int
	for i := 0; i <= n; i++ {
		var h int
		fmt.Scan(&h)
		hs = append(hs, h)
	}

	cnt := 0
	max := 0
	for i, h := range hs {
		if i+1 == n {
			break
		}
		if h >= hs[i+1] {
			cnt++
			if cnt > max {
				max = cnt
			}
		} else {
			cnt = 0
		}
	}

	fmt.Print(max)
}


Measured memory_bytes: 5504
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int X, A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> A >> B;

    if (B - A <= 0) printf("delicious\n");
    else if(B - A <= X) printf("safe\n");
    else printf("dangerous\n");
}

Measured memory_bytes: 256
def main():
    N, K = list(map(int, input().split(' ')))
    count = [0 for _ in range(N)]
    for _ in range(K):
        d = int(input())
        A = list(map(int, input().split(' ')))
        for a in A:
            count[a - 1] += 1
    answer = 0
    for c in count:
        if c == 0:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int n, m;

char a[100][100];
char b[100][100];

bool check(int i, int j) {
    for (int x = 0; x < m; ++x) {
        for (int y = 0; y < m; ++y) {
            if (a[i + x][j + y] != b[x][y]) {
                return false;
            }
        }
    }
    return true;
}

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

    // 入力
    cin >> n >> m;
    rep(i, n) { cin >> a[i]; }
    rep(i, m) { cin >> b[i]; }

    // 処理
    bool flg = false;
    for (int i = 0; i <= n - m; i++) {
        for (int j = 0; j <= n - m; j++) {
            if (check(i, j)) {
                flg = true;
            }
        }
    }

    // 出力
    if (flg) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 384
module Merge
	def merge!(a,left,mid,right)
		n1 = mid - left 
		n2 = right - mid
		count = 0
		l = []
		r = []
		n1.times do |i|
			l << a[left + i]
		end
		l << Float::INFINITY
		n2.times do |i|
			r << a[mid + i]
		end 
		r << Float::INFINITY
		i = 0
		j = 0

		left.upto(right - 1) do |k|
			if l[i] <= r[j]
				a[k] = l[i]
				i += 1
				count += 1
			else
				a[k] = r[j]
				j += 1
				count += 1
			end
		end
		return count
	end

	def merge_sort!(a, left, right, count)
		ans = 0
		if left + 1 < right
			mid = (left + right)/2
		ans +=	merge_sort!(a, left, mid, count)
		ans +=	merge_sort!(a, mid, right, count)
		ans +=	merge!(a, left, mid, right) 
		end
		return ans
	end

	module_function :merge!, :merge_sort!
end

include Merge
n = gets.to_i 
m = gets.split.map(&:to_i)

ans = merge_sort!(m, 0, n, 0)

puts m.join(" ")
puts ans

Measured memory_bytes: 67108
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int x=0;
    int lnth;
    cin>>lnth;
    string s;
    cin>>s;
    char cur;
    int arr[101];
    arr[0]=0;
    
  	for(int i=1;i<=lnth;i++){
  		if(s[i-1]=='I'){arr[i]=arr[i-1]+1;}
  		if(s[i-1]=='D')arr[i]=arr[i-1]-1;
  		x=max(x,arr[i]);
  	}
  	cout<<x<<endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

N, M = list(map(int, input().split()))
G = [[] for _ in range(N)]

for _ in range(M):
    x, y = list(map(lambda x: int(x) - 1, input().split()))
    G[x].append(y)

dp = [-1]*(N)

def f(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for nv in G[v]:
        ans = max(ans, f(nv) + 1)
    dp[v] = ans
    return ans

ans = 0
for i in range(N):
    ans = max(ans, f(i))

print(max(dp))

Measured memory_bytes: 119928
//  atcodder.xcode
//  main.cpp
//  Created by conan1024hao on 2019/11/11.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリ
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll>P;
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define PI acos(-1.0)
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll cmp(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//---------------------------------------------------------------------------
ll L[300000],R[300000];
vector<ll>a(500000);
ll merge(int n,int l,int m,int r){
    int n1=m-l;
    ll cnt=0;
    int n2=r-m;
    for(int i=0;i<n1;i++){
        L[i]=a[l+i];
    }
    for(int i=0;i<n2;i++){
        R[i]=a[m+i];
    }
    L[n1]=INF;
    R[n2]=INF;
    int i=0;
    int j=0;
    for(int k=l;k<r;k++){
        if(L[i]<=R[j]){
            a[k]=L[i++];
        }
        else{
            a[k]=R[j++];
            cnt+=n1-i;
        }
        
    }
    return cnt;
}
ll mergesort(int n,int l,int r){
    ll v1,v2,v3;
    if(l+1<r){
        int m=(l+r)/2;
        v1=mergesort(n,l,m);
        v2=mergesort(n, m, r);
        v3=merge(n,l,m,r);
        return (v1+v2+v3);
    }
    return 0;
}
//---------------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll cnt=mergesort(n,0,n);

    cout<<cnt<<endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------



Measured memory_bytes: 8296
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll H, W, K;
  cin >> H >> W >> K;
  vector<string> s(H);
  ll start_row = -1;
  vector<bool> target_row(H, false);
  for (int i = 0; i < H; i++) {
    cin >> s[i];
    for (int j = 0; j < W; j++) {
      if (s[i][j] == '#') {
        target_row[i] = true;
        if (start_row == -1) start_row = i;
      }
    }
  }
  vector<vector<int>> ans(H, vector<int>(W, 0));
  int cur_color = 1;
  for (int i = 0; i < H; i++) {
    if (!target_row[i]) continue;
    int cnt = 0;
    for (int j = 0; j < W; j++) {
      if (s[i][j] == '.')
        ans[i][j] = cur_color;
      else if (cnt > 0) {
        cur_color++;
        ans[i][j] = cur_color;
      } else {
        cnt++;
        ans[i][j] = cur_color;
      }
    }
    cur_color++;
  }
  int cur_target_row = start_row;
  for (int i = 0; i < H; i++) {
    if (target_row[i]) {
      cur_target_row = i;
      continue;
    }
    for (int j = 0; j < W; j++) {
      ans[i][j] = ans[cur_target_row][j];
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 4148
N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    flag2 = True
    start = 0
    for j in range(3):
        flag = False
        for k in range(start, N):
            if(num[j] == S[k]):
                flag = True
                start = k+1
                break
        if flag == False:
            flag2 = False
            break
    if flag2:
        ans += 1

print(ans)

Measured memory_bytes: 42076
H, W, K = map(int, input().split())
c = [input() for i in range(H)]
"""                                                                                                                                  
H = 6                                                                                                                                
W = 6                                                                                                                                
K = 3                                                                                                                                
c = ['...#.#',                                                                                                                       
     '...###',                                                                                                                       
     '#.....',                                                                                                                       
     '...#..',                                                                                                                       
     '...###',                                                                                                                       
     '...##.']                                                                                                                       
"""
ret = 0
for i in range(2**H):
    for j in range(2**W):
        num = 0
        mask_h = str(bin(i))[2:].zfill(H)
        mask_w = str(bin(j))[2:].zfill(W)
        for  k in range(H):
            if mask_h[k] == '0': continue
            for l in range(W):
                if mask_w[l] == '0': continue
                if c[k][l] == '#':
                    num += 1
        if num == K:
            ret += 1

print (ret)


Measured memory_bytes: 9220
#include<bits/stdc++.h>
    #define int ll
    #define M 1000000007
    #define hell 998244353
    #define big 1e18
    #define pb push_back
    #define pi 3.1415926536
    #define mp make_pair
    #define ub upper_bound
    #define lb lower_bound
    #define mem0(a) memset(a,0,sizeof(a))
    #define memf(a) memset(a,false,sizeof(a))
    #define mem1(a) memset(a,1,sizeof(a))
    #define all(a) a.begin(),a.end()
    #define ll long long
    #define vec vector <int>
    #define pii pair<int,int>
    #define endl "\n"
    using namespace std;
    int power(int x, unsigned int y, unsigned int m) 
	{ 
    	if (y == 0) 
        	return 1; 
    	int p = power(x, y/2, m) % m; 
    	p = (p * p) % m; 
  
 	   return (y%2 == 0)? p : (x * p) % m; 
	} 
	int modInverse(int a, int m) 
	{   
    	return power(a, m-2, m);
	}
    signed main()
    {
    	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	ll t=1;
    	// cin >> t;
    	/*SAARE INPUTS LENA*/
    	/*VARIABLES KI RANGE DEKHLENA*/
    	while(t-->0)
    	{
    		ll n=0,b=0;
    		cin>>n;
    		int a[n+1];
    		for (int i = 0; i <=n; ++i)
    		{
    			a[i]=0;
    		}
    		for (int i = 0; i < n-1; ++i)
    		{
    			cin>>b;
    			a[b]+=1;
    		}
    		for (int i = 1; i <=n; ++i)
    		{
    			cout<<a[i]<<endl;
    		}
    	}
    	return 0;
    }

Measured memory_bytes: 5220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAX_N = int(1e5 + 5);
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, m, a[1005], b[1005], used = 0, ans = 1;
    cin >> n >> m;
    REP(i,n) cin >> a[i];
    REP(i,m) cin >> b[i];
    sort(a,a+n);
    sort(b,b+m);
    REP(i,n-1){
        if(a[i]==a[i+1])ans = 0;
    }
    REP(i,m-1){
        if(b[i]==b[i+1])ans = 0;
    }
    // 大きい数から埋める
    // 書きこみ可能なマスの個数をかけていく
    for(int k = n*m; k>0; k--){
        int i = lower_bound(a,a+n,k)-a;
        int j = lower_bound(b,b+m,k)-b;
        if(a[i]==k && b[j]==k){

        }
        else if(a[i]==k){
            ans *= m-j;
        }
        else if(b[j]==k){
            ans *= n-i;
        }
        else{
            ans *= max(0ll,(n-i)*(m-j)-used);
        }
        used++;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int S, h, m, s;
	scanf("%d",&S);
	h = S / 3600;
	m = (S % 3600) / 60;
	s = (S % 3600) % 60;
	printf("%d:%d:%d\n",h ,m ,s);
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vs = vector<string>;
using vd = vector<double>;
using ul = unsigned long;
 
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
 
int vtotal(vi& v){
  int total=0;
  rep(i,v.size()) total+=v[i];
  return total;
}
 
int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
  
  int w,h,n;cin>>w>>h>>n;
  vpii p(n);
  vi a(n);
  rep(i,n){
    int x,y;cin>>x>>y;
    p[i]=mp(x,y);
    cin>>a[i];
  }
  
  int l=0;
  int r=w;
  int b=0;
  int t=h;
  
  rep(i,n){
    int e=a[i];
    int px=p[i].first;
    int py=p[i].second;
    if(e==1&&l<px)l=px;
    if(e==2&&r>px)r=px;
    if(e==3&&b<py)b=py;
    if(e==4&&t>py)t=py;
  }
  int ans=(r-l)*(t-b);
  if((r-l)<0||(t-b)<0)ans=0;
  cout(ans);
  
  return 0;
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size();
	vi v(n + 1);
	v[0] = 1;
	REP(i, n)v[i + 1] = s[i] - '0';
	bool ok = true;
	if (v[n] == 1 || v[1] == 0)ok = false;
	REP(i, (n - 1) / 2) {
		if (v[i + 1] != v[n - 1 - i])ok = false;
	}
	ll cnt = 0;
	for (int i = 2; i < n / 2; ++i) {
		if (v[i] == 1 && v[i + 1] == 0) {
			cnt += i;
		}
	}
	int num = 1, tmp = 0, k = 1;
	vector<pii> ans;
	for (int i = 1; i < n; ++i) {
		if (v[i]) {
			REP(j, tmp) {
				ans.push_back({ k, num+1});
				num++;
			}
			ans.push_back({ k,num + 1 });
			num++;
			k = num;
			tmp = 0;
		}
		else {
			tmp++;
		}
	}
	if (num > n || !ok)cout << -1 << endl;
	else REP(i, n - 1)cout << ans[i].first << " " << ans[i].second << endl;
}

Measured memory_bytes: 2884
/*
H行W列的表格，每个格子被涂上黑色('#')和白色('.')。
重复下面的操作，这道所有的小方格都变为黑色：
   对每一个与黑色方格有相邻边的白色方格都变为黑色。
求需要操作的次数。开始时至少有一个方格为黑色
数据范围：1<=H,w<=1000 
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
#define N 10002
int h, w, ret, dir[4][2]={0, 1, 0, -1, 1, 0, -1, 0};
char g[N][N];
struct node{
	int x, y;
	int d;
	node(int x1=0, int y1=0, int d1=0):x(x1),y(y1),d(d1){
		
	}
};
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int i, j;
	queue<node>q;
	cin>>h>>w;
	for(i=1; i<=h; i++){
		cin>>(&g[i][1]); 
	}
	
	for(i=1; i<=h; i++){
		for(j=1; j<=w; j++){
			if(g[i][j]=='#'){
				q.push(node(i, j));
			}
		}
	}
	int x, y, dx, dy, d;
	while(!q.empty()){
		node t;
		t = q.front();
		q.pop();
		x = t.x, y = t.y, d = t.d;
		for(i=0; i<4; i++){
			dx = x + dir[i][0];
			dy = y + dir[i][1];
			if(dx<1 || dx>h || dy<1 || dy>w)
				continue;
			if(g[dx][dy]=='.'){
				g[dx][dy] = '#';
				q.push(node(dx, dy, d+1));
				if(d+1>ret)
					ret = d + 1;
			}
		}
	}
	cout<<ret<<endl;
	return 0;
}


Measured memory_bytes: 21648
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

ll inf = 1e15;

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

    ll n;
    cin >> n;
    ll a, b, c;
    //g:隣接リスト([from].to/.cost)
    vector<vector<P>> g(n);
    REP(i, n - 1){
        cin >> a >> b >> c;
        a--;
        b--;
        g[a].push_back(P{b, c});
        g[b].push_back(P{a, c});
    }
    //d:頂点0から各点への距離を求める(今回のグラフは木なので経路はunique)
    vll d(n, inf);
    d[0] = 0;
    //que:未調査頂点リスト
    queue<ll> que;
    que.push(0);
    //DFS
    while(!que.empty()){
        ll now = que.front();
        que.pop();
        for(auto v : g[now]){
            ll nxt = v.first, w = v.second;
            if(d[nxt] != inf) continue; //走査済
            d[nxt] = d[now] + w;
            que.push(nxt);
        }
    }
    REP(i, n){
        if(d[i] % 2) cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 8704
S=sorted(input())
T=sorted(input())
for i in range(min(len(S),len(T))):
  if S[i] < T[-1*(i+1)]:
    print("Yes")
    break
  elif S[i] == T[-1*(i+1)]:
    if i+1 == min(len(S),len(T)) and len(S) < len(T):
      print("Yes")
      break
    
  else:
    print("No")
    break
else:
  print("No")

Measured memory_bytes: 61904
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define msi map<string,int>
#define mii map<int,int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define po pop_back
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
const int maxn = 2e4 + 10;
const int inf = 1e9;
int dp[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int h,n;
	cin>>h>>n;
	int w[n],v[n];
	rep(i,n){
		cin>>w[i]>>v[i];
		// max1 = max()
	}
	// rep(i,n){
	// 	for(int j=maxn-1;j>=w[i];j--){
	// 		dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
	// 	}
	// }
	rep(i,maxn)dp[i]=inf;
	dp[0] = 0;
	rep(i,maxn){
		rep(j,n){
			if(w[j]<=i){
				dp[i] = min(dp[i],dp[i-w[j]]+v[j]);
			}
		}
	}
	// rep(i,10){
	// 	cout<<dp[i]<<" ";
	// }
	int ans = inf;
	repa(i,h,maxn){
		ans = min(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
/* 
Hey there stalker....
 
█▀▀▄░░░░░░░░░░░▄▀▀█
░█░░░▀▄░▄▄▄▄▄░▄▀░░░█
░░▀▄░░░▀░░░░░▀░░░▄▀
░░░░▌░▄▄░░░▄▄░▐▀▀
░░░▐░░█▄░░░▄█░░▌▄▄▀▀▀▀█ 
░░░▌▄▄▀▀░▄░▀▀▄▄▐░░░░░░█
▄▀▀▐▀▀░▄▄▄▄▄░▀▀▌▄▄▄░░░█
█░░░▀▄░█░░░█░▄▀░░░░█▀▀▀
░▀▄░░▀░░▀▀▀░░▀░░░▄█▀
░░░█░░░░░░░░░░░▄▀▄░▀▄
░░░█░░░░░░░░░▄▀█░░█░░█
░░░█░░░░░░░░░░░█▄█░░▄▀
░░░█░░░░░░░░░░░████▀
░░░▀▄▄▀▀▄▄▀▀▄▄▄█▀
 
Like what you see?
*/
#include <bits/stdc++.h>
using namespace std;
 
#define fastIO ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
#define ld long double
#define lli long long int
#define p_b push_back
#define m_p make_pair
#define fs first
#define sc second
#define all(x) x.begin(),x.end()
#define fr(i,a,n) for(lli i=a; i<n; i++)
#define fre(i,a,n) for(lli i=a; i<=n; i++)
const lli mod = 1e9 + 7;
/*****************************************************/
int main()
{
    fastIO
    lli n,k,j,i;
    cin>>n>>k;
    lli h[n+1],tab[n+1];
    fre(i,1,n)
    {
        cin>>h[i];
        tab[i]=INT_MAX;
    }
    tab[1]=0;
    if(n<=k)
    {
        for(i=2;i<=n;i++)
        {
            for(j=1;j<i;j++)
                tab[i]=min(tab[i],tab[j]+abs(h[i]-h[j]));
        }
        cout<<tab[n];
        return 0;
    }
    for(i=2;i<=k;i++)
    {
        for(j=1;j<i;j++)
            tab[i]=min(tab[i],tab[j]+abs(h[i]-h[j]));
    }
    for(i=k+1;i<=n;i++)
    {
        for(j=i-1;j>=i-k;j--)
            tab[i]=min(tab[i],tab[j]+abs(h[i]-h[j]));
    }
    cout<<tab[n];
    //cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
    return 0;
} 

Measured memory_bytes: 1792
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
language={i:[] for i in range(1,M+1)}
for i in range(0,N):
    L=list(map(int,input().split()))
    K=L[0]
    for j in range(1,K+1):
        language[L[j]].append(i)

uf=UnionFindVerSize(N)
for i in range(1,M+1):
    if language[i]:
        p=language[i][0]
        if len(language[i])>1:
            for j in range(1,len(language[i])):
                uf.unite(p,language[i][j])


if uf.calc_group_num()==1:
    print('YES')
else:
    print('NO')


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

#define TASKNAME ""

using namespace std;

const int INF = 1e9 + 7;
const int MAXN = 1e6 + 7;
const double EPS = 1e-8;

vector <vector <int> > gr;

vector <bool> used;
vector <int> inLeft;

bool dfs(int v) {
    if (used[v]) {
        return false;
    }
    used[v] = true;
    for (int u : gr[v]) {
        if (inLeft[u] == -1 || dfs(inLeft[u])) {
            inLeft[u] = v;
            return true;
        }
    }
    return false;
}

int main() {
    #ifdef MY
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #else
        //freopen(TASKNAME".in", "r", stdin);
        //freopen(TASKNAME".out", "w", stdout);
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    #endif // MY
    int n;
    cin >> n;
    gr.resize(n);
    vector <pair <int, int> > a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i].first >> b[i].second;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i].first < b[j].first && a[i].second < b[j].second) {
                gr[i].push_back(j);
            }
        }
    }
    used.resize(n, 0);
    inLeft.resize(n, -1);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        used.assign(n, 0);
        if (dfs(i)) {
            cnt++;
        }
    }
    cout << cnt;
}


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

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

  map<pair<string, string>, int> mp;
  for (int bit = 0; bit < (1 << N); bit++) {
    string r = "", b = "";
    for (int i = 0; i < N; i++) {
      if ((bit >> i) & 1) {
        r += s[i];
      } else {
        b += s[i];
      }
    }
    mp[{r, b}]++;
  }

  int ans = 0;
  for (int bit = 0; bit < (1 << N); bit++) {
    string r = "", b = "";
    for (int i = 0; i < N; i++) {
      if ((bit >> i) & 1) {
        r += s[N + i];
      } else {
        b += s[N + i];
      }
    }
    reverse(r.begin(), r.end());
    reverse(b.begin(), b.end());

    ans += mp[{r, b}];
  }

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


Measured memory_bytes: 87040
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		String s = scan.next();
		String t = scan.next();

		//char型の配列に変える
		char[] s_char = s.toCharArray();
		char[] t_char = t.toCharArray();

		long sum = 0;

		for (int i = 0; i < s_char.length; i++) {
			if (s_char[i] != t_char[i]) {
				sum++;
			}
		}

		System.out.println(sum);
	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 32720
def solve():
    N = int(input())
    X = list(map(int, input().split()))
    ans = float('inf')
    for p in range(1, 100 + 1):
        tmp = 0
        for x in X:
            tmp += (x-p)**2
        ans = min(ans, tmp)
    return ans

print(solve())

Measured memory_bytes: 3060
#include<stdio.h>

int A[1000000],n;

int binarySearch(int key){
	int left=0;
	int right=n;
	int mid;
	
	while(left<right){
		mid=(left+right)/2;
		if(key==A[mid])return 1;
		if(key>A[mid])left=mid+1;
		else if(key<A[mid])right=mid;
	}
	return 0;
}

int main(){
	int i,q,k,sum=0;
	
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	
	scanf("%d",&q);
	for(i=0;i<q;i++){
		scanf("%d",&k);
		if(binarySearch(k))sum++;
	}
	printf("%d\n",sum);
	return 0;
}


Measured memory_bytes: 2248
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m,a,b;
  cin>>n>>m;
  int box[n];
  for(int i=0;i<n;i++){
    box[i]=0;
  }
  for(int i=0;i<m;i++){
    cin>>a>>b;
    box[a-1]++;
    box[b-1]++;
  }
  for(int i=0;i<n;i++){
    cout<<box[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
/*

  _|_|                              _|  _|    _|
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|
_|    _|  _|_|          _|          _|  _|_|
_|    _|  _|          _|      _|    _|  _|  _|
  _|_|    _|        _|_|_|_|    _|_|    _|    _|

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
const int maxn=2e5+1000;
const int inf=1e9+100;
using namespace std;
vi E[maxn],inset[maxn];
int s=2e5+1,t=2e5+2,cnt=1,head[maxn];
struct gg{
    int u,v,w,next;
}side[maxn*4];
void ins(int u,int v,int w) {
    side[++cnt]=(gg){u,v,w,head[u]};head[u]=cnt;
    side[++cnt]=(gg){v,u,0,head[v]};head[v]=cnt;
}
int rk[maxn],cur[maxn];
queue<int>q;
bool bfs() {
    memset(rk,0,sizeof(rk));rk[s]=1;
    while(!q.empty())q.pop();q.push(s);
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=side[i].next) {
            int v=side[i].v;if(rk[v]||!side[i].w)continue;
            rk[v]=rk[u]+1;
            q.push(v);
        }
    }
    if(!rk[t])return 0;
    return 1;
}
int dfs(int u,int flow) {
    if(u==t||!flow)return flow;
    int tot=0;
    for(int &i=cur[u];i;i=side[i].next) {
        int v=side[i].v;//cout<<v<<' '<<rk[v]<<endl;
        if(rk[v]!=rk[u]+1||!side[i].w)continue;
        int sent=dfs(v,min(flow,side[i].w));
        side[i].w-=sent;side[i^1].w+=sent;
        flow-=sent;tot+=sent;
    }
    return tot;
}
int dinic(){
    int maxflow=0;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        maxflow+=dfs(s,inf);
    }
    return maxflow;
}
int match[maxn];//match[set_id]=match_point_id
bool inq[maxn];
pii ans[maxn];
int main(){
    //ios::sync_with_stdio(0);
    int n;scanf("%d",&n);//cin>>n;
    rep(i,1,n-1) {
        int c;scanf("%d",&c);//cin>>c;
        rep(j,1,c) {
            int u;scanf("%d",&u);//cin>>u;
            E[i].pb(u);inset[u].pb(i);
            ins(u,n+i,1);
        }
    }
    rep(i,2,n)ins(s,i,1);
    rep(i,1,n-1)ins(n+i,t,1);
    int flow=dinic();
    if(flow!=n-1) {
        printf("-1\n");//cout<<"-1";
        return 0;
    }
    rep(i,n+1,n+n-1) {
        for(int j=head[i];j;j=side[j].next) {
            int v=side[j].v;
            if(v<=n&&side[j].w) {
                match[i-n]=v;break;
            }
        }
    }
    while(!q.empty())q.pop();
    int tot=1;q.push(1);inq[1]=1;
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=0;i<inset[u].size();i++) {
            int setid=inset[u][i],set_match=match[setid];
            if(!inq[set_match]) {
                inq[set_match]=1;ans[setid]=mk(u,set_match);
                q.push(set_match);tot++;
            }
        }
    }
    if(tot!=n) {
        printf("-1\n");//cout<<"-1";
        return 0;
    }
    for(int i=1;i<n;i++) {
        printf("%d %d\n",ans[i].fi,ans[i].se);
        //cout<<ans[i].fi<<' '<<ans[i].se<<endl;
    }
    return 0;
}


Measured memory_bytes: 41848
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    A, B = mi()
    
    A -= 1
    if A % 2 == 1:
        # 偶数個
        if (A // 2) % 2 == 1:
            A = 0
        # 奇数個
        else:
            A = 1
    else:
        if (A // 2) % 2 == 0:
            A = 0 ^ A
        else:
            A = 1 ^ A

    if B % 2 == 1:
        if (B // 2) % 2 == 1:
            B = 0
        else:
            B = 1
    else:
        if (B // 2) % 2 == 0:
            B = 0 ^ B
        else:
            B = 1 ^ B

    print(A ^ B)

    return

main()


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

using namespace std;

int main(){
    string s1,s2,s3;
    cin>>s1>>s2>>s3;
    cout<<char(s1[0]-0x20)<<char(s2[0]-0x20)<<char(s3[0]-0x20)<<endl;
    
}

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

s_t = 0
s_h = 0
for i in range(n):
    c_t, c_h = input().split()
    if c_t > c_h:
        s_t += 3
    elif c_t < c_h:
        s_h += 3
    else:
        s_t += 1
        s_h += 1

print(s_t, s_h)



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

int main(){
  char a[15],b[15],c[15];
  scanf("%s%s%s",a,b,c);
  if(a[strlen(a)-1]==b[0] && b[strlen(b)-1]== c[0]) printf("YES");
  else printf("NO");
  //printf("%d",strlen(a));
  return 0;
}

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main()
{
    lli h, w;
    string line;
    vector<string> s;
    cin >> h >> w;

    for(lli i=0; i<h; i++){
        cin >> line;
        s.push_back(line);
        s.push_back(line);
    }

    for(vector<string>::iterator it=s.begin(); it!=s.end(); it++)
        cout << *it << endl;
    return 0;
}

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

"""
input:
147 105

output:
21
"""

import sys


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    n1, n2 = map(int, _input[0].split())
    print(gcd(n1, n2))

Measured memory_bytes: 7632
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define NFOR(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); --i)
#define rep(i, a) for (ll i = 0; i < a; i++)
#define endl "\n"
#define fi first
#define se second
#define MOD 1000000007
#define inf 1e12
#define pb push_back
#define Case cout<<"Case #"<<++cas<<": ";
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;

#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T>ostream& operator <<(ostream& os, const multiset<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}

const int maxn = 305;

double dp[maxn][maxn][maxn];

void solve() {
	ll mod = 1000000007;
	ll n;
	cin >> n;
	vl cnt(4, 0);
	rep(i, n) {
		ll temp;
		cin >> temp;
		cnt[temp]++;
	}

	rep(c, n + 1)
		rep(b, n + 1)
			rep(a, n + 1) {
				if (a + b + c > n) continue;

				ll em = n - (a + b + c);
				dp[a][b][c] = 0;
				if (a)
					dp[a][b][c] = dp[a - 1][b][c] * (1.0 * a) / (1.0 * n);
				if (b)
					dp[a][b][c] += dp[a + 1][b - 1][c] * (1.0 * b) / (1.0 * n);
				if (c)
					dp[a][b][c] += dp[a][b + 1][c - 1] * (1.0 * c) / (1.0 * n);

				if (a + b + c > 0)
					dp[a][b][c] += 1;
				if (em < n)
					dp[a][b][c] /= 1 - (1.0 * em) / (1.0 * n);
			}

	cout << setprecision(10) << fixed << dp[cnt[1]][cnt[2]][cnt[3]] << endl;
}

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


Measured memory_bytes: 219520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#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())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;
/*
ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) a=a*a%MOD;
		else res=res*a%MOD;
		b>>=1;
	}
	res=res*a%mod;
	return res;
}
*/

int a[maxn];
int main()
{
	//IOS;
	int n;
	cin>>n;
	REP(i,n) cin>>a[i];
	ll A=0,B=0;

	sort(a,a+n,greater<int>());

	REP(i,n){
		if(i%2) B+=a[i];
		else A+=a[i];
	}
	cout<<A-B;
	return 0;
}


Measured memory_bytes: 256
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define int ll
const ll mod = 1000000007;
const ll nmax=1000003;
int n, m, dp[(1<<13)];

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m;
    for(int i=1; i<(1<<n); i++) dp[i]=1e18;
    for(int i=1; i<=m; i++){
		int key=0, cost, b;
		cin>>cost>>b;
		for(int j=1, x; j<=b; j++) cin>>x, key=(key|(1<<(x-1)));
		for(int mask=0; mask<(1<<n); mask++){
			dp[(mask|key)]=min(dp[(mask|key)], dp[mask]+cost);
		}
	}
	cout<<(dp[(1<<n)-1]>1e17 ? -1 : dp[(1<<n)-1]);
}


Measured memory_bytes: 256
#include<cstdio>

int main(){
  int price;
  scanf("%d",&price);
  bool disable[10];
  for(int i = 0;i < 10;i++){
	disable[i] = false; 
  }
  int K;
  scanf("%d",&K);
  for(int i = 0;i < K;i++){
 	int n;
 	scanf("%d",&n);
	disable[n] = true; 
  }
  int tmp;
  while(true){
   tmp = price;
   while(!disable[tmp % 10]){
	tmp /= 10;
   	if(tmp == 0) break;
   }
   //printf("%d\n",price);
   if(tmp == 0) break;
   price++;
  }
  printf("%d\n",price);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
void solve(long long N) {
  if( N <= 111 ){ cout << 111 << endl; return ; }
    if( N <= 222 ){ cout << 222 << endl; return ; }
    if( N <= 333 ){ cout << 333 << endl; return ; }
    if( N <= 444 ){ cout << 444 << endl; return ; }
    if( N <= 555 ){ cout << 555 << endl; return ; }
    if( N <= 666 ){ cout << 666 << endl; return ; }
    if( N <= 777 ){ cout << 777 << endl; return ; }
    if( N <= 888 ){ cout << 888 << endl; return ; }
    cout << 999 << endl;
}
 
// 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)
int main() {
  long long N;
  scanf("%lld", &N);
  solve(N);
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    cnt = 0
    for i in range(1,N):
        a = N//i
        if N%i == 0:
            cnt += a-1
        else:
            cnt += a
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9176
#include<stdio.h>
#define N 101

int n, M[N][N];
int color[N], d[N], f[N], tt;

void dfs_visit(int u){
  int v;
  color[u]=1;
  d[u]=++tt;
  for(v=1;v<=n;v++){
    if(M[u][v]==0) continue;
    if(color[v]==0) dfs_visit(v);
  }
  color[u]=2;
  f[u]=++tt;
}

void dfs(){
  int u;
  for(u=1;u<=n;u++) color[u]=0;
  tt=0;

  for(u=1;u<=n;u++){
    if(color[u]==0) dfs_visit(u);
  }
  for(u=1;u<=n;u++) printf("%d %d %d\n",u,d[u],f[u]);
}

int main(){
  int u,v,i,j,k;

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

  for(i=1;i<=n;i++){
    scanf("%d %d", &u, &k);
    for(j=1;j<=k;j++){
      scanf("%d", &v);
      M[u][v]=1;
    }
  }

  dfs();

  return 0;
}
    



Measured memory_bytes: 2108
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int number = sc.nextInt();
		int mod = 1000000007;
		int[] a = new int[number+1];
		long ans = 1;
		for(int i = 2; i <= number; i++){
			int k = i;
			for(int j = 2; j <= k; j++){
				while(k%j==0){
					a[j]++;
					k/=j;
				}
			}
		}
		for(int i = 0; i <= number; i++){
			if(a[i]>0){
				ans = ans*(a[i]+1)%mod;
			}
		}
		System.out.println(ans);
	}
}

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

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end(), greater<int>());
  ll ans = 0;
  ll cnt = 0;
  for (ll i = 1; i < n; i++) {
    ans += a[cnt];
    if (i % 2 == 1) cnt++;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	int n = 1;
	n += (N - K) / (K - 1);
	if ((N - K) % (K - 1) != 0) {
		n++;
	}
	cout << n << endl;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
int x,No1,No2,No3;
No1=0;
No2=0;
No3=0;
for(int i=0;i<10;i++){
cin>>x;
if(x>No1){
No3=No2;
No2=No1;
No1=x;
}else if(x>No2){
No3=No2;
No2=x;
}else if(x>No3){
No3=x;
}
}
cout<<No1<<endl<<No2<<endl<<No3<<endl;
return 0;
}

Measured memory_bytes: 1160