akhauriyash/Code-Regression huggingface dataset:
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let v: Vec<String> = read_vec();

    if v[0] == v[1] {
        println!("H");
    } else {
        println!("D");
    }
}


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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define repll(i,n) for(ll i = 0; i < n; i++)
#define REPll(i,n) for(ll i = 1; i < n; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n") 
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}

ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}


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

  int n;
  cin >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi l(n), r(n);
  l[0] = a[0];
  r[n-1] = a[n-1];
  REP(i,n) l[i] = gcd(l[i-1], a[i]);
  for(int i = n-2; i >= 0; i--) r[i] = gcd(r[i+1], a[i]);
  int ans = 0;
  rep(i,n){
    int tmp;
    if(i==0) tmp = r[1];
    else if(i==n-1) tmp = l[i-1];
    else tmp = gcd(r[i+1], l[i-1]);
    ans = max(tmp, ans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    long long A, B, N;
    cin >> A >> B >> N;
    
    long long x = B - 1;
    if (x > N) x = N;
    cout << A * x / B - x / B * A << endl;
    return 0;
}


Measured memory_bytes: 3624
def main():
    N,M,Q = map(int, input().split())

    X = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        l,r = map(int, input().split())
        X[l-1][r-1] += 1

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Measured memory_bytes: 77400
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
from operator import mul
from bisect import bisect_left


def read():
    N, K = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, K, A


def sign(x):
    if x == 0:
        return 0
    return 1 if x > 0 else -1


def solve(N, K, A, p=10**9+7):
    A.sort(key=lambda a: -abs(a))
    s = 1  # sign
    v = 1  # value
    idx_minus = -1
    idx_not_minus = -1
    for i in range(K):
        _s = sign(A[i])
        s *= _s
        v *= A[i]
        v %= p
        if _s >= 0:
            idx_not_minus = i
        else:
            idx_minus = i
    if s >= 0 or N == K:
        return v
    
    # 以下、左からK個を掛けた数が負になるとき
    # 絶対値が小さな負の数を1つ取り除いて、絶対値が大きな正の数を1つ追加する
    a1 = A[idx_minus]
    b1 = max(A[K:])
    # 絶対値が小さな正の数を1つ取り除いて、絶対値が大きな負の数を1つ追加する
    a2 = A[idx_not_minus]
    b2 = min(A[K:])

    use_1, use_2 = True, True
    if not(idx_minus >= 0 and b1 >= 0):
        use_1 = False
    if not(idx_not_minus >= 0 and b2 < 0):
        use_2 = False
    
    if use_1 and use_2:
        if b1 * a2 >= b2 * a1:
            use_1 = True
            use_2 = False
        else:
            use_1 = False
            use_2 = True
    if use_1:
        v *= pow(a1, p-2, p)
        v %= p
        v *= b1
        v %= p
    elif use_2:
        v *= pow(a2, p-2, p)
        v %= p
        v *= b2
        v %= p
    else:
        # どうやっても正の数が作れないとき
        A.sort(key=lambda a: abs(a))
        s = 1
        v = 1
        for i in range(K):
            _s = sign(A[i])
            s *= _s
            v *= A[i]
            v %= p
    return v


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 33552
import math
c = 10**9+7

n, k = map(int, input().split())

def combinations_count(n, r):
  if n <= r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1, k+1):
  a = combinations_count(k-1, i-1) 
  if n-k >= i-1:
    b = combinations_count(n-k+1, i)
  else:
    b = 0
  print(int((a*b) % c))


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod = 1e9 + 7;
const int INF = 1e9;
int main(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i,h)cin >> s[i];
    vvi cr(h, vi(w, 0)), cl(h, vi(w, 0)), cu(h, vi(w, 0)), cd(h, vi(w, 0));
    rep(i,h){
        int l = 0, r = 0;
        rep(j,w){
            if(s[i][j] == '.')l++;
            else l = 0;
            if(j < w-1)cl[i][j+1] = l;
        }
        repr(j,w){
            if(s[i][j] == '.')r++;
            else r = 0;
            if(j > 0)cr[i][j-1] = r;
        }
        l = r = 0;
    }
    rep(j,w){
        int u = 0, d = 0;
        rep(i,h){
            if(s[i][j] == '.')u++;
            else u = 0;
            if(i < h-1)cu[i+1][j] = u;
        }
        repr(i,h){
            if(s[i][j] == '.')d++;
            else d = 0;
            if(i > 0)cd[i-1][j] = d;
        }
        u = d = 0;
    }
    /*cout << "left counter" << endl;
    rep(i,h)rep(j,w)cout << cl[i][j] << ((j < w-1)?" ":"\n");
    cout << "right counter" << endl;
    rep(i,h)rep(j,w)cout << cr[i][j] << ((j < w-1)?" ":"\n");
    cout << "up counter" << endl;
    rep(i,h)rep(j,w)cout << cu[i][j] << ((j < w-1)?" ":"\n");
    cout << "down counter" << endl;
    rep(i,h)rep(j,w)cout << cd[i][j] << ((j < w-1)?" ":"\n");
*/
    int ans = -1;
    rep(i,h)rep(j,w)if(s[i][j] != '#')ans = max(ans, cl[i][j] + cr[i][j] + cu[i][j] + cd[i][j] + 1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 69248
use whiteread::parse_line;

fn main() {
    let n: usize = parse_line().unwrap();
    let p: Vec<usize> = parse_line().unwrap();
    let mut cnt = 0;
    let mut min = p[0];

    for i in 0..n {
        min = min.min(p[i]);
        if p[i] == min {
            cnt += 1;
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 5124
#include<bits/stdc++.h>
using namespace std;
#define AC ios::sync_with_stdio(0),cin.tie(0);
#define ll long long int
ll mod=1e9+7;
ll dp[2005];
int main(){
	dp[0]=1;
	dp[1]=1;
	dp[2]=1;
	for(int i=3;i<=2000;i++){
		dp[i]=(dp[i-1]+dp[i-3])%mod;
	}
	int s;
	while(cin>>s){
		if(s<3)cout<<"0"<<endl;
		else cout<<dp[s-3]<<endl;
	}
}


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

int num(int n, int p[]) {
	int count = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i; j < n; j++)
			if (p[i] > p[j])
				count++;
		count *= n - i - 1;
	}
	return count;
}

int main(void) {
	int n;
	int p[8], q[8];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &p[i]);
	for (int i = 0; i < n; i++)
		scanf("%d", &q[i]);
	printf("%d\n", abs(num(n, p) - num(n, q)));
	return 0;
}

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

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  ll a,b;
  cin >> a >> b;
  if(a<= 0 && 0<= b) puts("Zero");
  else if( a <= -1 && (min(0LL,b) - min(0LL,a)) % 2 ==  0 ) puts("Negative");
  else puts("Positive");

  return 0;
}


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

using namespace std;

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

int W, H, N;

int main(){
  int x, y, a;
  int xs, xe, ys, ye;
  scanf("%d %d %d", &W, &H, &N);
  xs = ys = 0;
  xe = W; ye = H;
  rep(i, N){
    scanf("%d %d %d", &x, &y, &a);
    switch(a){
    case 1:
      xs = max(xs, x);
      break;
    case 2:
      xe = min(x, xe);
      break;
    case 3:
      ys = max(ys, y);
      break;
    case 4:
      ye = min(ye, y);
      break;
    }
  }
  
  if(xe <= xs || ye <= ys) printf("0\n");
  else printf("%d\n", (xe-xs)*(ye-ys));
}


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

map<ll, ll> prime;
void factrization(ll n) {
  for(ll i=2; i*i<=n; i++) {
    while(n%i==0) {
      prime[i]++;
      n/=i;
    }
  }
  
  if(n>1) prime[n]++;
}

ll moP(ll x, ll n) {
  ll res=1;
  while(n>0) {
    if(n&1) moC(res, *, x);
    moC(x, *, x);
    n>>=1;
  }
  return res;
}


int main(void) {
  ll N;
  cin >> N;
  ll i;
  ll a[MAX/10];
  
  priority_queue<P> q;
  
  for(i=0; i<N; i++) {
    cin >> a[i];
    
    prime.clear();
    factrization(a[i]);
    for(auto it=prime.begin(); it!=prime.end(); it++) {
      q.push({it->sc, it->ft});
    }
  }
  
  ll cnt[MAX*10]={};
  while(q.size()) {
    P u=q.top(); q.pop();
    ll p=u.sc;
    ll c=u.ft;
    
    if(cnt[p]) continue;
    cnt[p]=c;
  }
  
  ll S=1;
  for(i=0; i<MAX*10; i++) {
    moC(S, *, moP(i, cnt[i]));
  }
  
  ll ans=0;
  for(i=0; i<N; i++) {
    moC(ans, +, S*moP(a[i], MOD-2)%MOD);
  }
  
  pt(ans);
}


Measured memory_bytes: 9076
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define pb push_back
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
ll a,b,n;
bool s[50][50];
ll dp[20][20];

ll solve(int i,int j) {
    if(dp[i][j] >= 0)
        return dp[i][j];
    if(i == a - 1 && j == b - 1) {
        return dp[i][j] = 1;
    }

    ll ret = 0;
    if(i + 1 < a && !s[i + 1][j]) {
        ret += solve(i + 1,j);
    }
    if(j + 1 < b && !s[i][j + 1]) {
        ret += solve(i,j + 1);
    }
	return dp[i][j] = ret;
}

int main(){
    while(1) {
        cin >> a >> b;
        if(a == 0)
            break;
        cin >> n;
        REP(i,a) {
            REP(j,b) {
                s[i][j] = false;
            }
        }
        REP(i,n) {
            ll inx,iny;
            cin >> inx >> iny;
            s[inx - 1][iny - 1] = true;
        }

        REP(i,a) {
            REP(j,b) {
                dp[i][j] = -1;
            }
        }

        cout << solve(0,0) << endl;
    }
}




Measured memory_bytes: 3012
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
int main(){
    int h,a; cin >> h >> a;
    int ans=0;
    ans=(h+a-1)/a;
    cout << ans << endl; 
}

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

typedef long long LL;
typedef pair <int,int> pii;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int inf = 1e9;
const LL INF = 1e18;
const int N = 1e5 + 5;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  string s, t;
  cin >> s >> t;
  if (t.substr(0, (int)s.size()) == s) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}



Measured memory_bytes: 3640
#include<cstdio>
int main()
{
    int k,a[5],flag=0;
    for(int i=0; i<5; i++)
        scanf("%d",&a[i]);
    scanf("%d",&k);
    for(int i=1; i<5; i++)
        if(a[i]-a[0]>k)
        {
            flag=1;
            break;
        }
    if(flag)
        printf(":(");
    else
        printf("Yay!");
    return 0;
}


Measured memory_bytes: 128
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    n, W = readi(2)
    ws, vs = zip(*readi(n, 2))
    dp = arr(n + 1, W + 1)
    for i in range(n):
        for w in range(W + 1):
            if w - ws[i] >= 0:
                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w - ws[i]] + vs[i])
            dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
    print(dp[n][W])


if __name__ == "__main__":
    main()


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

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

  rep(i,s.length()-1){
    if(s[i] != s[i+1]) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;

signed main(){
	int n, k; cin>>n>>k;
	
	int arr[n], dp[n];;
	for(int i=0; i<n; i++){
		cin>>arr[i];
		dp[i]=1000000007;
	}
	
	
	
	dp[0]=0;
	for(int i=1; i<=k and i<n; i++){
		dp[i]=abs(arr[i]-arr[0]);
	}
	
	for(int i=k+1; i<n; i++){
		for(int j=1; j<=k; j++){
			dp[i]=min(dp[i], dp[i-j]+abs(arr[i]-arr[i-j]));
		}
	}
	
	cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
/*
	3种选择，不能连续两天做同一件事情 
*/
using namespace std;
const int MAXN = 100005;
int v[MAXN][3];
int dp[MAXN][3];
int main(){
	int n;
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>v[i][0]>>v[i][1]>>v[i][2];
	}
	for(int i = 0; i < 3; i++){
		dp[1][i] = v[1][i];
	}
	for(int i = 2; i <= n; i++){
		for(int j = 0; j < 3; j++){
			dp[i][j] = 0;
			for(int k = 0; k < 3; k++){
				if(j != k){
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + v[i][j]);
				}
			}
		}
	}
	int ans = max(dp[n][0], max(dp[n][1], dp[n][2]));
	printf("%d",ans);
	return 0; 
}

Measured memory_bytes: 2560
import numpy as np
n = int(input())
h = list(map(int, input().split()))
h = np.array(h)
ans = 0
def mizuyari(list):
    global ans
    # print(list)
    if len(list) == 0:
        return
    if len(list) == 1:
        ans += min(list)
        return
    min_list = min(list)
    list = list - min_list
    ans += min_list
    zero_list = np.where(list == 0)[0]
    mizuyari(list[:zero_list[0]])
    mizuyari(list[zero_list[-1]+1:])
    for i in range(len(zero_list)-1):
        mizuyari(list[zero_list[i]+1:zero_list[i+1]])
mizuyari(h)
print(ans)


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

typedef long long ll;
typedef unsigned long long ull;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

string s;

int main() {
    while(cin >> s) {
        //cout<<"s: "<<s<<endl;
        bool f = false;
        // tate 
        rep(i,3) {
            if(s[i] == 's') continue;
            if(s[i]==s[i+3] and s[i]==s[i+6]) {
                if(s[i]=='o') {cout<<"o"<<endl;}
                else {cout<<"x"<<endl;}
                f = true;
            }
        }

        // yoko
        for(int i=0; i<9; i+=3) {
            if(s[i]=='s') continue;
            if(s[i]==s[i+1] and s[i]==s[i+2]) {
                if(s[i]=='o') {cout<<"o"<<endl;}
                else {cout<<"x"<<endl;}
                f = true;
            }
        }

        // naname
        if(s[0]==s[4] and s[0]==s[8]) {
            if(s[0]=='o') {cout<<"o"<<endl;}
            else {cout<<"x"<<endl;}
            f = true;
        }
        if(s[2]==s[4] and s[2]==s[6]) {
            if(s[2]=='o') {cout<<"o"<<endl;}
            else {cout<<"x"<<endl;}
            f = true;
        }

        if(!f) cout << "d" << endl;
    }

    return 0;
}

Measured memory_bytes: 1176
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class Program
{
    static void Main()
    {
        var sc = new StreamScanner(OpenStandardInput());
        var N = sc.Integer();
        var A = new int[N];
        var s = 0L;
        for (int i = 0; i < A.Length; i++)
        {
            var k = sc.Integer();
            A[i] = k;
            if ((i & 1) == 0) s += k;
            else s -= k;
        }

        var sb = new System.Text.StringBuilder(10 * N);
        sb.Append(s).Append(' ');

        for (int i = 1; i < N; i++)
        {
            s = (A[i - 1] - (s >> 1)) * 2;
            sb.Append(s).Append(' ');
        }
        SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        WriteLine(sb);
        Out.Flush();
    }
}

public class StreamScanner
{
    public StreamScanner(System.IO.Stream stream)
    {
        str = stream;
    }

    public readonly System.IO.Stream str;
    private readonly byte[] buf = new byte[1024];
    private int len, ptr;
    public bool isEof;

    public bool IsEndOfStream
    {
        get { return isEof; }
    }

    private byte read()
    {
        if (isEof) return 0;
        if (ptr < len) return buf[ptr++];
        ptr = 0;
        if ((len = str.Read(buf, 0, 1024)) > 0) return buf[ptr++];
        isEof = true;
        return 0;
    }

    public long Long()
    {
        if (isEof) return long.MinValue;
        long ret = 0;
        byte b;
        var ng = false;
        do b = read(); while (b != 0 && b != '-' && (b < '0' || '9' < b));
        if (b == 0) return long.MinValue;
        if (b == '-')
        {
            ng = true;
            b = read();
        }
        for (; ; b = read())
        {
            if (b < '0' || '9' < b)
                return ng ? -ret : ret;
            ret = ret * 10 + b - '0';
        }
    }

    public int Integer()
    {
        return (isEof) ? int.MinValue : (int)Long();
    }
}


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

int main() {
  int num;
  int in,out;
  int cntIn = 0;
  int cntOut = 0;
  
  cin >> num >> in >> out;
  
  vector<char> vec(num);
  for(int i = 0; i < num; i++){
    cin >> vec.at(i);
  }
  
  for(int i = 0; i < num; i++){
    if(vec.at(i) == 'a'){
      if(in + out > cntIn + cntOut){
        cout << "Yes" << endl;
        cntIn++;
      }else{
        cout << "No" << endl;
      }
    }else if(vec.at(i) == 'b'){
      if(in + out > cntIn + cntOut && cntOut < out){
        cout << "Yes" << endl;
        cntOut++;
      }else{
        cout << "No" << endl;
      }
    }else{
      cout << "No" << endl;
    }
  }
}


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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define X first
#define Y second
#define pb push_back
#define make_unique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define int long long

const LL mod = 1e9 + 7;


template<class T>
istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }

template<class T, class U>
istream& operator >> (istream& in, pair<T, U> & v){ in >> v.X >> v.Y;return in; }

template<class T, class U>
ostream& operator << (ostream& out, pair<T, U> & v){ out << v.X << " " << v.Y;return out; }

void chkmax(int &a, int b) {
    a = max(a, b);
    return;
}

void chkmin(int &a, int b) {
    a = min(a, b);
    return;
}

LL ppow (LL x, LL s) {
    if (!s) return 1;
    if (!(s - 1)) return x % mod;
    if (s % 2) return (x * ppow (x, s - 1)) % mod;
    LL b = ppow (x, s / 2);
    return (b * b) % mod;
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //freopen("ILUXA.in", "r", stdin);
    int n, k;
    cin >> n >> k;
    vector<int> a(k);
    cin >> a;
    int sum = 0;
    for (auto x : a) {
        sum += x;
    }
    cout << ((sum >= n) ? "Yes" : "No");
    return 0;
}


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

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

	int x = 0;
	int cnt = 1;
	bool flag = false;
	while (x < N)
	{
		x += cnt++;

		if(x == N)flag = true;
	}

	if (flag)
	{
		cout<<"Yes"<<endl;
		cout<<cnt<<endl;

		vector<vector<int>>GRID(cnt);
		int x = 1;
		for(int i=1;i<cnt;i++)
		{ 
			for (int j = 0; j < i; j++)
			{
				GRID[i].push_back(x);
				GRID[j].push_back(x);
				x++;
			}
		}

		for (int i = 0; i < cnt; i++)
		{
			cout<<cnt-1;
			for (int j = 0; j < cnt - 1; j++)
			{
				cout<<" ";
				cout<<GRID[i][j];
			}
			cout<<endl;
		}
	}
	else {
		cout<<"No"<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 2304
#include<iostream>
#include<map>
#include<list>
#include<queue>
#include<vector>
#include<algorithm>
#include<climits>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define f   first
#define s   second
#define fastio ios_base::sync_with_stdio(0)\
               ;cin.tie(0)\
               ;cout.tie(0)    
#define forxNi(x,n) for(int i=x;i<n;i++)
#define forxNj(x,n) for(int j=x;j<n;j++)
#define forNxi(n,x) for(int i=n;i>=x;i--)
#define forNxj(n,x) for(int j=n;j>=x;j--)  
#define vll    vector<ll> 
#define vpll   vector<pair<ll,ll> >
#define vill   vector<pair<int,int> >
#define wloop   int t\
               ;cin>>t\
               ;while(t--)



int main(){
    fastio;
    int n,k;cin>>n>>k;
    int a[n];
    forxNi(0,n){
        cin>>a[i];
    }
    int dp[n];
    forxNi(0,n){
    	dp[i]=INT_MAX;
    }
    dp[0]=0;
    ll sum=0;
    forxNi(1,n){
    		if(i>1){
    			if(i>k){
    				forxNj(i-k,i){
	    				dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i]);
	    			}
	    		}
	    		else{
	    			forxNj(0,i){
	    				dp[i]=min(dp[i],abs(a[j]-a[i])+dp[j]);
	    			}
	    		}
    		}
    		else dp[1]=abs(a[1]-a[0]);
    }
    // forxNi(0,n){
    // 	cout<<dp[i]<<" ";
    // }
    cout<<dp[n-1];
    cout<<'\n';
    
    return 0;
}

Measured memory_bytes: 4380
#include <iostream>
#include <algorithm>
using namespace std; 
int main() {
  int n;
  cin >> n;
  for(int i=0; i<n; i++) {
    int a[3];
    for(int j=0; j<3; j++) {
      cin >> a[j];
    }
    sort(a, a+3);
    if(a[0]*a[0]+a[1]*a[1]==a[2]*a[2]) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 1168
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printInt(a) printf("%d\n", a)
#define printll(a) printf("%lld\n", a)
#define printYes() printf("Yes\n")
#define printNo() printf("No\n")
#define scanll(a) scanf("%lld", &a)
#define scanInt(a) scanf("%d", &a)
#define scan2Int(a, b) scanf("%d %d", &a, &b)
#define scan3Int(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define scan4Int(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
typedef long long ll;
using namespace std;

int main() {
    ll n, a, b;
    scanf("%lld %lld %lld", &n, &a, &b);
    ll step = n / (a + b);
    ll amari = n % (a+b) < a ? n % (a + b) : a;
    ll ans = step * a + amari;
    printll(ans);
    return 0;
}


Measured memory_bytes: 3828
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

class UnionFind{
public:
    vector<int> par;
    vector<int> rank;
    vector<int> sz;
    int uf_size;

    UnionFind(int n){
        par.resize(n);
        rank.resize(n);
        sz.resize(n);
        uf_size = n;
        for(int i=0; i<n; i++){
            par[i] = i;
            rank[i] = 0;
            sz[i] = 1;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }
    
    bool same(int x, int y){
        return find(x) == find(y);
    }

    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y]) swap(x, y);
        if(rank[x] == rank[y]) rank[x]++;
        uf_size--;
        par[y] = x;
        sz[x] = sz[x] + sz[y];
        return true;
    }

    int size(int x){
        return sz[find(x)];
    }
};

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

    ll n, m; cin>>n>>m;
    vector<int> a(m), b(m);
    for(int i=0; i<m; i++) cin>>a[i]>>b[i];

    UnionFind uf(n);

    ll sum = n * (n - 1) / 2;
    vector<ll> ans;
    for(int i=m-1; i>=0; i--){
        ans.emplace_back(sum);
        a[i]--, b[i]--;
        if(!uf.same(a[i], b[i])){
            sum -= (ll)uf.size(a[i]) * uf.size(b[i]);
            uf.unite(a[i], b[i]);
        }
    }

    reverse(all(ans));
    for(auto i : ans) cout << i << endl;

    return 0;
}

Measured memory_bytes: 4212
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int k = sc.nextInt();

		double exp = (double) 1 / n;
		double sum = 0;

		for (int i = 1; i <= n; i++) {
			int count = 1;
			int tmp = i;
			while (tmp < k) {
				tmp *= 2;
				count *= 2;
			}
			sum += exp / count;
		}

		System.out.println(sum);

	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define boost  ios_base::sync_with_stdio(0);
#define N 1000
#define ll long long int
#define pb push_back
#define f first
#define s second
#define fo(i,a,b) for(i = a; i < b; i++)
#define foe(i, a,b) for(i = a; i <= b; i++)
#define tc long long int t; cin >> t; while(t--)
#define vect vector <ll>
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define be begin
#define en end

int main(){
	boost;
	ll i;
	ll n;
	cin >> n;
	ll a[n];
	fo(i,0,n){
		cin >> a[i];
	}
	ll dp[n+1];
	fo(i,0,n){
		dp[i] = INT_MAX;
	}
	dp[0] = 0;
	fo(i,0,n){
		for(ll j : {i + 1,i+2}){
			dp[j] = min(dp[j], dp[i] + abs(a[i] - a[j]));
		}
	}
	cout << dp[n-1] <<endl;
	
	return 0;
}

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

int main()
{
    int h,w;
    cin >> h >> w;
    int a[10][10];
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin >> a[i][j];
        }
    }
    int t[10] = {};
    for(int i=0; i<h*w; i++){
        int j;
        cin >>j;
        if(j==-1) continue;
        t[j]++;
    }

    //warshall-floyd
    for(int k=0; k<10; k++){
        for(int i=0; i<10; i++){
            for(int j=0; j<10; j++){
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=0; i<10;i++){
        if(i==1) continue;
        ans += a[i][1]*t[i];
        // cout << i << " :" << a[i][1] << " , " << t[i]<< endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
memo = [0] * (N + 1)

def factor(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            memo[i] += cnt
        i += 1
    if n > 1:
        memo[n] += 1

for n in range(2, N + 1):
    factor(n)

mod = 10 ** 9 + 7
ans = 1
for m in memo:
    if m >= 1:
        ans *= m + 1
        ans %= mod
print(ans)


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

int main()
{
	int a, b, x, c, i = 0;

	cin >> x >> a >> b;

	c = x - a;

	while (c - b * i >= 0)
	{
		i++;
	}

	cout << c - b * (i - 1) << endl;


}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



namespace Test1 {

    class ClassMain {

        public static int ryoukin(int taiseki, int weight) {
            if (taiseki <= 60 && weight <= 2) { return 600; }
            if (taiseki <= 80 && weight <= 5) { return 800; }
            if (taiseki <= 100 && weight <= 10) { return 1000; }
            if (taiseki <= 120 && weight <= 15) { return 1200; }
            if (taiseki <= 140 && weight <= 20) { return 1400; }
            if (taiseki <= 160 && weight <= 25) { return 1600; }
            return 0;
        }
       
        public static void Main(String[] args) {
            string line;

            while ((line = Console.ReadLine()) != null) {
                int n = int.Parse(line);
                if (n == 0) { break; }
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    line = Console.ReadLine();
                    string[] strs = line.Split(' ');
                    int x = int.Parse(strs[0]), y = int.Parse(strs[1]), z = int.Parse(strs[2]),
                        w = int.Parse(strs[3]);
                    sum += ryoukin(x + y + z, w);

                }
                Console.WriteLine(sum);

            }
        }


    }

}

Measured memory_bytes: 5816
N, K = map(int, input().split())
A = list(map(int, input().split()))
passlist = [0]*N
point = 1
depth = 0
waylist = []
while passlist[point-1] == 0:
    waylist.append(point)
    passlist[point-1] = depth
    point = A[point-1]
    depth+=1
roop = waylist[waylist.index(point):len(waylist)]
firstreach = passlist[roop[0]-1]
if K < firstreach:
  print(passlist.index(K)+1)
else:
  print(roop[(K-firstreach)%len(roop)])

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

int main() {
    std::cout<<std::fixed<<std::setprecision(10);
    
    int N; cin >> N;
    int nbg = N/2;
    cout << float(N-nbg)/N << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);


    public static void main(String[] args) {
        long n = sc.nextLong();
        long sum = 0;
        for (int i = 1; i < n; i++) {
            sum += i;
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>


using namespace std;



int main() {

	int N, D, **X;

	cin >> N >> D;

	X = new int*[N];

	for (int i = 0; i < N; i++) {
		X[i] = new int[D];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < D; j++) {
			cin >> X[i][j];
		}
	}
	

	int count = 0;
	double sum;

	for (int i = 0; i < N-1; i++) {
		for (int j = i + 1; j < N; j++) {
			sum = 0;
			for (int k = 0; k < D; k++) {
				sum += pow(abs(X[i][k] - X[j][k]), 2);
			}
			if (sqrt(sum) == floor(sqrt(sum))) {
				count++;
			}
		}
	}

	cout << count;


	return 0;

}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{

    int i,j=0,n,x;

    scanf("%d%d",&n,&x);

    int a[n],b[n];

    for(i=0;i<=n;i++){

        b[i]=0;

    }


    for(i=1;i<=n;i++){

        scanf("%d",&a[i]);
        b[i]=b[i-1]+a[i];

    }
    for(i=0;i<=n;i++){

       if(b[i]<=x){
        j++;
       }

    }

    printf("%d\n",j);
}


Measured memory_bytes: 128
def smaller(x, y):
	if x < y: return x
	return y
A, B, C, X, Y = map(int, raw_input().split())
sum = 0
if A+B > 2 * C:
	c = smaller(X, Y)
	sum += c * 2 * C
	X -= c
	Y -= c
	if A > 2 * C: sum += X * 2 * C
	else: sum += X * A
	if B > 2 * C: sum += Y * 2 * C
	else: sum += Y * B
else:
	sum = A * X + B * Y
print sum

Measured memory_bytes: 28012
#include <iostream>

using namespace std;

int main()
{
    int a, b;

    cin >> a >> b;
    while (a != 0 || b != 0)
    {
        if (b < a)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        cout << a << ' ' << b << endl;
        cin >> a >> b;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<map>
#include<list>
#include<set>
#include<algorithm>
#include<limits.h>
#include<vector>
#define foreach(t,p) for(t::iterator it=p.begin();it!=p.end();p++)
using namespace std;
#define MAX 5000000

bool notp[MAX];

int main()
{
    notp[0]=true;
    notp[1]=true;
    for(unsigned int i = 2;i<MAX;i++)
        if(!notp[i]) for(unsigned int j=2*i;j<MAX;j+=i)
        {
            notp[j]=true;
        }
    vector<int> primes;
    for(int i =0;i<MAX;i++)
    {
        if(!notp[i]) primes.push_back(i);
        if(primes.size()>100100)break;
    }
    //for(int l=0;l<25;l++)cout << primes[l] << endl;
    int n,p;
    cin >> n >> p;
    int k;

    while(n!=-1 && p!=-1)
    {
        list<int> mnps;
        for(k=0;;k++) 
        {
            if (primes[k] > n ) break;
        }
        for(int i =0;i<100;i++)for(int j=i;j<100;j++)
            mnps.push_back(primes[i+k]+primes[j+k]);

        mnps.sort();
        list<int>::iterator mit = mnps.begin();
        for(int i =0;i<p-1;i++)++mit;
        cout << *mit << endl;
        cin >> n >> p;
    }
    return 0;
}

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

int gcd(int a, int b){
    int r = a % b;
 while(r!=0){
   a = b;
   b = r;
   r = a % b;
 }
 return b;
}

int main(void){
    int N,index=0,A,B;
    long long int X, ans;
    cin>>N>>X;
    vector<int> data(N);

    for(int i=0;i<N;i++)cin>>data[i];

    if(N==1){
      cout<<abs(X-data[0])<<endl;
      return 0;
    }

    sort(data.begin(),data.end());//昇順ソート

    vector<int> d(N);

    for(int i=0;i<N-1;i++){
      d[i] = data[i+1] - data[i];
      //cout <<d[i]<<endl;
    }
    // cout<<"a"<<endl;
    if(X<data[0]){
      A = data[0]-X;
      B =A;
    }
    else if (X>data[N-1]){
      A = X - data[N-1];
      B = A;
    }
    else{
    for(int i=0;i<N-1;i++){
      if(data[i]<X && X<data[i+1]){
        A = data[i+1] - X;
        B = X -data[i];
      }
    }
    }
    // cout << A<<B<<endl;
    d[N-1] = gcd(A, B);
    ans = d[N-1];
    // for(int i=0;i<N;i++){
    //   cout<<d[i]<<endl;
    // }
    for(int i=0;i<N-1;i++){
      ans = gcd(gcd(d[i], d[i+1]), ans);
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 1024
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;
import std.ascii;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

bool calc(string s) {
    if (s[0] != 'A') return false;
    if (s[2..$-1].count!(c => c == 'C') != 1) return false;
    if (s.count!(c => isUpper(c)) > 2) return false;
    return true;
}

void main() {
    auto s = readln.chomp;
    writeln(calc(s) ? "AC" : "WA");
}


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

int main()
{
    int n;
    scanf("%d",&n);
    int num[100005];
    for(int i=0; i<n; i++)
        cin>>num[i];
    sort(num,num+n);
    int ans = 0;
    for(int i=0; i<n; )
    {
        int j = i + 1;
        int k = 0;
        while(num[i] == num[j])
        {
            k++;
            j++;
        }
        if(k&1) i = j;
        else
        {
            i = j;
            ans ++ ;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int a=0,sum=0;
	for(int i=0;i<s.size();i++){
		int n=(s[i]-(int)'0');
		sum+=n;
		for(int j=i+1;j<s.size();j++) n*=10;
		a+=n;
	}
	if(a%sum==0) cout<<"Yes";
	else cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool p[10000010];
vector<long long> v,a;
long long x,b[50],ans;
int main(){
	for (long long i=2;i<1e7;i++)
		if (p[i]==0)
			for (long long j=i+i;j<i;j+=i) p[j]=1;
	for (long long i=2;i<=1e7;i++) if (p[i]==0) v.push_back(i);
	for (long long i=1;i<50;i++) b[i]=b[i-1]+i;
	cin>>x;
	for (long long i=0;i<v.size();i++)
		if (x%v[i]==0){
			long long z=0;
			while (x%v[i]==0){
				z++;
				x/=v[i];
			}
			a.push_back(z);
		}
	if (x!=1) a.push_back(1);
	for (long long i=0;i<a.size();i++)
		for (long long j=0;j<50;j++)
			if (b[j]>a[i]){
				ans+=j-1;
				break;
			}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 134320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring> //memset
using namespace std;


int main()
{
	long N;

	cin >> N;

	vector<int> v;

	for (long long iN = 0; iN < N; iN++) {
		int value;

		cin >> value;

		v.push_back(value);
	}

	std::sort(v.begin(), v.end());

	double result = 0.0;
	result = (v[0] + v[1]) / 2.0;
	for (long long iN = 2; iN < N; iN++) {
		result = (result + v[iN]) / 2.0;
	}

	cout << result << endl;
}


//int main()
//{
//	long a;
//	string s;
//
//	cin >> a >> s;
//
//	if (a >= 3200) {
//		cout << s << endl;
//	}
//	else {
//		cout << "red" << endl;
//	}
//
//}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author YahiaAshraf74
 */

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <complex>
#include <string>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <assert.h>

using namespace std;
#define el  '\n'
#define ll long long
#define clr(a, b)memset(a,b,sizeof(a))
#define sz(a) (int)(a).size()
const long long N = (int) 3e2 + 5, OO = 0x3f3f3f3f, MOD = (int) 1e9 + 7;

double dp[N][N][N];

class JSushi {
public:
    void init() {
        clr(dp,0);
    }

    void solve(istream &cin, ostream &cout) {
        init();
        int n;
        cin >> n;
        vector<int> cnt(4);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        for (int k = 0; k <= n; k++) {
            for (int j = 0; j + k <= n; j++) {
                for (int i = 0; i + j + k <= n; i++) {
                    if (i == 0 && j == 0 && k == 0) {
                        continue;
                    }
                    double wait = 1.0 * n / (i + j + k);
                    double pi = 1.0 * i / (i + j + k);
                    double pj = 1.0 * j / (i + j + k);
                    double pk = 1.0 * k / (i + j + k);
                    if (i != 0) {
                        dp[i][j][k] += pi * dp[i - 1][j][k];
                    }
                    if (j != 0) {
                        dp[i][j][k] += pj * dp[i + 1][j - 1][k];
                    }
                    if (k != 0) {
                        dp[i][j][k] += pk * dp[i][j + 1][k - 1];
                    }
                    dp[i][j][k] += wait;
                }
            }
        }
        cout << fixed << setprecision(10) << dp[cnt[1]][cnt[2]][cnt[3]] << el;
    }
};
int main() {
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	JSushi solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int n, m;

int main(){
	int i, j;
	string s;
	cin >> s;
	n = s.size();
	int ans=0, r=s.size()-2;
	for(i=n-2; i; i-=2){
		bool ok = 1;
		for(j=0;j<i/2;j++){
			if(s[j]!=s[j+i/2])ok=0;
		}if(ok){
			cout << i;
			return 0;
		}
	}return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#define Pr pair<int,int>
using namespace std;
const int N=1e5+10;
struct xxx{
	int y,nxt;
}a[N*2];
queue<Pr> q;
map<Pr,int> cnt;
set<int> rec[N];
set<int>::iterator it,tmpit;
int h[N],f[N];
int req[N][2];
int n,m,tot;
Pr mp(int x,int y){if (x>y) swap(x,y); return make_pair(x,y);}
int get_f(int x){return f[x]=f[x]==x?f[x]:get_f(f[x]);}
bool link(int x,int y){
	Pr tmp;
	rec[x].insert(y); rec[y].insert(x);
	tmp=mp(x,y);
	++cnt[tmp];
	if (cnt[tmp]==2) q.push(tmp);
}
void cut(int x,int y){
	rec[x].erase(y); rec[y].erase(x);
	cnt.erase(mp(x,y));
}

int main(){
#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
#endif
	Pr tmp;
	int x,y,num;
	scanf("%d",&n);
	memset(h,-1,sizeof(h));
	tot=0;
	cnt.clear();
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		link(x,y);
	}
	for (int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		link(x,y);
	}
	for (int i=1;i<=n;++i) f[i]=i;
	for (int tm=1;tm<n;++tm){
		if (q.empty()){printf("NO\n"); return 0;}
		x=get_f(q.front().first); y=get_f(q.front().second); q.pop();
		if (x==y) continue;
		if (rec[x].size()>rec[y].size()) swap(x,y);
		//printf("%d %d\n",x,y);
		f[x]=y;
		cut(x,y);
		for (it=rec[x].begin();it!=rec[x].end();it=tmpit){
			tmpit=it; num=*it; ++tmpit;
			num=get_f(num);
			if (num==y) continue;
			cut(x,num);
			link(y,num);
		}
	}
	printf("YES\n");
}

Measured memory_bytes: 39040
# coding: utf-8
# ?????°
B = 20
S = 19
# ?????´???????????\??°?????????
normal_months =  [B,S,B,S,B,S,B,S,B,S]
special_months = [B,B,B,B,B,B,B,B,B,B]
# ?????´?????\??°
normal_dates = 0
normal_months.each do |months|
  normal_dates += months
end
special_dates = 0
special_months.each do |months|
  special_dates += months
end

# ??????????????????
line = gets
# ???????????¨?????????
while line = gets do
  # ????????§????????£???????????????????????????????????????
  year,month,date = line.split
  year = year.to_i
  month = month.to_i
  date = date.to_i
  result = 0
  if year != 1000
    months = []
    if year % 3 != 0
      months = normal_months
    else
      months = special_months
    end
    # ?????¨?????\???????????????????????§?????\???????¶????
    result += months[month-1] - date
    month += 1
    # ?????¨??????-??´????????§???????????\??°????¶????
    while month != 11
      result += months[month-1]
      month += 1
    end
  end
  year += 1
  while year != 1000 do
    if year % 3 != 0
      result += normal_dates
    else
      result += special_dates
    end
    year += 1
  end
  result += 1
  puts result
end

Measured memory_bytes: 8784
#include <iostream>
#include <string>

using namespace std;

int main() {
	int n;
	string s;
	cin >> n >> s;
	int c = 0,d = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') {
			d++;
		}
		else {
			if (d > 0) {
				d--;
			}
			else {
				c++;
			}
		}
	}
	for (int i = 0; i < c; i++) cout << '(';
	cout << s;
	for (int i = 0; i < d; i++)cout << ')';
	cout << endl;

}

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

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int ar[n];
    int mn=9999,mx=0;
    for(int i=0; i<n; i++){
        cin >> ar[i];
        mx = max(mx,ar[i]);
        mn = min(mn,ar[i]);
    }
    cout << mx-mn << endl;

}


Measured memory_bytes: 256
#include <stdio.h>

#define maxN 10

void dfs(int time, int color, int bfr[maxN][maxN]);
int changeColor(int bfr[maxN][maxN], int panel[maxN][maxN], int color, int x, int y);

int h, w, c, max;
int vx[] = {1,0,-1,0};
int vy[] = {0,1,0,-1};

int main(){
	int i, j;

	while(1){
		int panel[maxN][maxN] = {};

		scanf("%d %d %d", &h, &w, &c);
		if(h==0&&w==0&&c==0) break;

		for(i=1; i<=h; i++){
			for(j=1; j<=w; j++){
				scanf("%d", &panel[i][j]);
			}
		}
		dfs(0, panel[1][1], panel);
		printf("%d\n", max);

		max = 0;
	}

	return 0;
}

void dfs(int time, int color, int bfr[maxN][maxN]){
	int panel[maxN][maxN];
	int i, j, cnt = 0;

	for(i=0; i<maxN; i++){
		for(j=0; j<maxN; j++){
			panel[i][j] = bfr[i][j];
		}
	}

	if(time<4){
		for(i=1; i<=6; i++){
			if(i==color) continue;
			cnt = changeColor(bfr, panel, i, 1, 1);
			dfs(time+1, i, panel);
		}
	}else if(time==4){
		cnt = changeColor(bfr, panel, c, 1, 1);
		dfs(time+1, c, panel);
	}else if(time==5){
		cnt = changeColor(bfr, panel, 7, 1, 1);
		if(max<cnt) max = cnt;
	}
}

int changeColor(int bfr[maxN][maxN], int panel[maxN][maxN], int color, int x, int y){
	int i, cnt = 1;
	panel[y][x] = color;
	for(i=0; i<4; i++){
		if(bfr[y+vy[i]][x+vx[i]]==bfr[y][x] && panel[y+vy[i]][x+vx[i]]!=color){
			cnt += changeColor(bfr, panel, color, x+vx[i], y+vy[i]);
		}
	}
	return cnt;
}

Measured memory_bytes: 608