akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
  return std::vector<T>(n, std::forward<T>(val));
}

template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}

template<class T, class Cond>
struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  bool operator()(T& a, const T& b) const {
    if(cond(a, b)) { a = b; return true; }
    return false;
  }
};
template<class T, class Cond>
chain<T, Cond> make_chain(Cond cond) { return chain<T, Cond>(cond); }

#include <iostream>
using i64 = long long;
template<i64 M> struct modint { i64 a;
  constexpr modint(const i64 x = 0): a((x%M+M)%M){}
  constexpr i64 value() const { return a; }
  constexpr modint inv() const { return this->pow(M-2); }
  constexpr modint pow(i64 r) const {
    modint ans(1); modint aa = *this;
    while(r) { if(r & 1) ans *= aa; aa *= aa; r >>= 1; }
    return ans;
  }
  constexpr modint& operator=(const i64 r) { a = (r % M + M) % M; return *this; }
  constexpr modint& operator+=(const modint r) { a += r.a; if(a >= M) a -= M; return *this; }
  constexpr modint& operator-=(const modint r) { a -= r.a; if(a < 0) a += M; return *this; }
  constexpr modint& operator*=(const modint r) { a = a * r.a % M; return *this; }
  constexpr modint& operator/=(const modint r) { (*this) *= r.inv(); return *this; }
  constexpr modint operator+(const modint r) const { return modint(*this) += r; }
  constexpr modint operator-(const modint r) const { return modint(*this) -= r; }
  constexpr modint operator*(const modint r) const { return modint(*this) *= r; }
  constexpr modint operator/(const modint r) const { return modint(*this) /= r; }
  constexpr bool operator!=(const modint r) const { return this->value() != r.value(); }
};

template<const i64 M> std::ostream& operator<<(std::ostream& os, const modint<M>& m) { os << m.value(); return os; }


int main() {
  i64 N, K;
  cin >> N >> K;
  using fp = modint<(i64)(1e9 + 7)>;
  //[0, N]
  fp ans = 0;
  rep(i,K,N + 2) {
    i64 f = i * (i - 1) / 2;
    i64 b = N * (N + 1) / 2 - (N + 1 - i) * (N + 1 - i - 1) / 2;
    ans += fp(b) - fp(f) + fp(1);
  }
  std::cout << ans << endl;
}


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

int main() {
	int n, m, i, x[3] = { 10,10,10 }, c, s;
	cin >> n >> m;
	if (n == 1) {
		for (i = 0; i < m; i++) {
			cin >> s >> c;
			if (x[0] != 10 && x[0] != c) {
				cout << "-1";
				return 0;
			}
			else x[0] = c;
		}
		if (x[0] == 10)x[0] = 0;
		cout << x[0];
		return 0;
	}
	if (n == 2) {
		for (i = 0; i < m; i++) {
			cin >> s >> c;
			if (x[s-1] != 10 && x[s-1] != c) {
				cout << "-1";
				return 0;
			}
			if (s==1&&c==0) {
				cout << "-1";
				return 0;
			}
			else x[s-1] = c;
		}
		if (x[0] == 10)x[0] = 1;
		if (x[1] == 10)x[1] = 0;
		cout << x[0] << x[1];
	}
	if (n == 3) {
		for (i = 0; i < m; i++) {
			cin >> s >> c;
			if (x[s - 1] != 10 && x[s - 1] != c) {
				cout << "-1";
				return 0;
			}
			if (s == 1 && c == 0) {
				cout << "-1";
				return 0;
			}
			else x[s - 1] = c;
		}
		if (x[0] == 10)x[0] = 1;
		if (x[1] == 10)x[1] = 0;
		if (x[2] == 10)x[2] = 0;
		cout << x[0] << x[1]<<x[2];
	}
}

Measured memory_bytes: 256
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/

void build(){

}
#define N 111
int n , s[ N ];
int dp[ 2 ][ 10 ];
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    s[ i ] = getint();
}
void solve(){
  for( int i = 1 ; i < 10 ; i ++ )
    dp[ 0 ][ i ] = - INF;
  for( int i = 1 ; i <= n ; i ++ ){
    int now = i & 1 , pre = 1 - now;
    for( int j = 0 ; j < 10 ; j ++ )
      dp[ now ][ ( j + s[ i ] ) % 10 ] = max( dp[ pre ][ ( j + s[ i ] ) % 10 ] , 
                                              dp[ pre ][ j ] + s[ i ] );
  }
  int ans = 0;
  for( int i = 1 ; i < 10 ; i ++ )
    ans = max( ans , dp[ n & 1 ][ i ] );
  cout << ans << endl;
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 256
def main():
    N, K = map(int, input().split())
    
    ans = 0
    for b in range(K+1, N+1):
        p = N // b
        r = N % b
        # if K == 0:
        #     ans += p * max(0, )
        ans += p * (b - K) + max(0, r - K + 1)
        if K == 0:
            ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	private static final long N = 1_000_000_007L;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt(), k = scanner.nextInt();
			long answer = 0L;
			for (int i = k; i <= n + 1; i++) {
				answer += f(n + 1, i);
				answer = answer % N;
			}
			System.out.println(answer);
		}
	}

	private static long f(long n, long m) {
		return m * n - g(m - 1) - g(m) + 1;
	}

	private static long g(long m) {
		return m * (m + 1) / 2L;
	}
}


Measured memory_bytes: 35840
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) (v).begin(), (v).end()
ll MOD = 1000000007;
const long long INF = 1LL << 60;

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

int main()
{   
    int n,k; cin >> n >> k;
    vector<int> h(n);
    for(int i=0;i<n;i++)cin >> h[i];
    sort(all(h));
    int res = lower_bound(all(h),k) - h.begin();
    cout << n-res << endl;
}

Measured memory_bytes: 640
pub 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()
}

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

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::cmp::max;

fn main() {
    let kn: Vec<u32> = read_vec();
    let k = kn[0];
    let n = kn[1] as usize;

    let a: Vec<u32> = read_vec();
    let mut d = vec![0; n];

    for i in 0..n - 1 {
        d[i] = a[i + 1] - a[i];
    }
    d[n - 1] = a[0] + k - a[n - 1];

    let m = d.iter().fold(0, |s, a| max(s, *a));
    println!("{}", k - m);
}


Measured memory_bytes: 8444
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=200005;
int a[M],n,k,cnt[M];
void work()
{
   clr(cnt);
   f(i,1,n)
   {
       int d=a[i];
       int lft=i-d;
       int rgt=i+d;
       lft=max(lft,1LL);
       rgt=min(rgt,n);
       if(lft>rgt)continue;
       cnt[lft]++;
       cnt[rgt+1]--;
   }
   f(i,1,n)
   {
       cnt[i]+=cnt[i-1];
   }
   f(i,1,n)
   {
       a[i]=cnt[i];
   }
}
 main()

{
    fast
    cin>>n>>k;
    f(i,1,n)
    {
        cin>>a[i];
    }
    int tmp=1000;
    tmp=min(tmp,k);
    while(tmp--)
    {
        work();
    }
    f(i,1,n)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;

}





































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

int cnt=0;
string N;
int main(){
  
  cin>>N;
  if(((N[0]==N[1])&&(N[2]==N[1]))|((N[1]==N[2])&&(N[2]==N[3])))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 3604
n=int(input())
a=list(map(int,input().split()))
cnt=0;
a.sort()
for i in range(0,n):
    for j in range(i+1,n):
        if a[i]==a[j]:
            continue
        for k in range(j+1,n):
            if a[j]==a[k]:
                continue;
            if a[i]+a[j]>a[k]:
                cnt=cnt+1
print(cnt)


Measured memory_bytes: 9112
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define vi vector<int>
#define pb push_back
#define p push
#define sll stack<long long>
#define qll queue<long long>
#define vll vector<long long>
#define fori(n) for(int i=0;i<n;i++)
#define forj(n) for(int j=0;j<n;j++)
#define fork(n) for(int k=0;k<n;k++)
#define fori1(n) for(int i=1;i<n;i++)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define pi 3.14159265358979323
#include <math.h>
#define yn(n) if(n)cout<<"yes\n";else cout<<"no\n";
#define Yn(n) if(n)cout<<"Yes\n";else cout<<"No\n";
#define YN(n) if(n)cout<<"YES\n";else cout<<"NO\n";
#define mp   make_pair 
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}

vll r,b,g;ll ans=0;

ll md(ll n){
	if(n>0)return n;
	else return -n;
}



string str,str2;
void solve(){
    ll x,n;cin>>x>>n;
    set<ll> s;
    fori(n){
        ll a;cin>>a;
        s.insert(a);
    }
    int i=0;n=x;
    while(true){
        if(*(s.lower_bound(n-i))!=(n-i)){
            cout<<n-i;break;
        }
        if(*(s.lower_bound(n+i))!=(n+i)){
            cout<<n+i;break;
        }
        i++;
    }
}


int main(){

 
    	
	int t;
	t=1;
	//cin >> t;
	while(t--){
		solve();
		
	}
	
	
	//cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";

}

Measured memory_bytes: 3616
n, x = map(int,input().split())
l = list(map(int,input().split()))

a = 0
for i in range(n):
    a = a + l[i]
    #print(a)
    if x == a:
        print(i+1+1)
        break
    elif x < a:
        print(i+1)
        break
    else:
        continue
else:
    print(n+1)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
using namespace std;

pair<pair<int, int>, pair<int,int>> get_mode(map<int, int>& tag){
  vector<pair<int,int>> v;
  for(auto i : tag){
    // cout << i.first << '*' << i.second << " ";
    v.push_back(make_pair(i.second, i.first));
  }
  // cout << endl;
  sort(v.begin(),v.end(), greater<pair<int, int>>());

  if(tag.size() == 1){
    return make_pair(v.at(0), v.at(0));
  }else{
    return make_pair(v.at(0), v.at(1));
  }
}

int slove(int n, map<int, int> odd, map<int, int> even){
  auto omode = get_mode(odd);
  auto emode = get_mode(even);

  if(omode.first.second == emode.first.second){
    if(omode.first.second == emode.second.second) return n / 2;
   return min((n / 2) - omode.first.first + (n / 2) - emode.second.first,(n / 2) - omode.second.first + (n / 2) - emode.first.first);
  }else{
    return (n / 2) - omode.first.first + (n / 2) - emode.first.first;
  }
}

int main(void){
  int n, buf;
  map<int, int> m_even;
  map<int, int> m_odd;
  vector<pair<int, int>> v_even;
  vector<pair<int,int>> v_odd;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> buf;
    if(i % 2 != 0){
      auto itl = m_odd.find(buf);
      if(itl == m_odd.end()){
        m_odd[buf] = 1;
      }else{
        itl->second++;
      }
    }else{
      auto itl = m_even.find(buf);
      if(itl == m_even.end()){
        m_even[buf] = 1;
      }else{
        itl->second++;
      }
    }
  }

  cout << slove(n, m_odd, m_even) << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;
int deg[N];

int main(){
  fastIO;
  int n, m;
  cin >> n >> m;
  int a, b;
  for(int i = 0 ; i < m ; i ++ ){
    cin >> a >> b;
    deg[a] ^= 1;
    deg[b] ^= 1;
  }
  for(int i =1 ; i <= n; i ++ ){
    if(deg[i]){
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n";
  return 0;
}

Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1e5+1)
	sc.Buffer(buf, 1e5+1)

	sc.Scan()
	S := []byte(sc.Text())

	var previous byte = 'a'
	texts := make([]int, 0)
	for _, s := range S {
		if s != previous {
			texts = append(texts, 1)
			previous = s
		} else {
			texts[len(texts)-1] += 1
		}
	}

	result := 0
	for i := 0; i < len(texts)-1; i++ {
		if texts[i] >= texts[i+1] {
			result += 2 * texts[i+1]
			if i+2 < len(texts) {
				texts[i+2] += texts[i] - texts[i+1]
			}
			texts[i+1] = 0
		} else {
			result += 2 * texts[i]
			texts[i+1] -= texts[i]
		}
	}

	fmt.Println(result)
}


Measured memory_bytes: 5632
#S= str(input())
#T= str(input())
#N = int(input())
A,B,M= map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C=10**6
for i in range(M):
    x,y,c= map(int,input().split())
    cost = A[x-1] + B[y-1] - c
    if cost<=C:
        C=cost
if min(A)+min(B)<=C:
    C=min(A)+min(B)
print(C)


Measured memory_bytes: 18648
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  vector<int> ABC(3);
  for (int i = 0; i < 3; i++) {
    cin >> ABC.at(i);
  }
  int f = 0;
  int s = 0;
  for (int i = 0; i < 3; i++) {
    if (ABC.at(i) == 5) {
      f ++;
    }else if (ABC.at(i) == 7) {
      s ++;
    }
  }
  if ((f == 2) && (s == 1)) {
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <utility>
#define REP(i,A) for(int i=0;i<A;i++)

using namespace std;
using ll = long long int;
using ld = long double;
using vl = vector<ll>;
using vd = vector<ld>;
using pi = pair<int, int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

	int H, W, N,sr,sc;
	cin >> H >> W >> N >> sr >> sc;
	string S, T;
	cin >> S >> T;

	int l=0, r=0, d=0, u=0;

	for (int i = N - 1; i >= 0; i--) {
		if (T[i] == 'R') {
			l = max(0, l - 1);
		}
		if (T[i] == 'L') {
			r = max(0, r - 1);
		}
		if (T[i] == 'U') {
			d = max(0, d - 1);
		}
		if (T[i] == 'D') {
			u = max(0, u - 1);
		}
		
		if (S[i] == 'R') {
			r++;
		}
		if (S[i] == 'L') {
			l++;
		}
		if (S[i] == 'U') {
			u++;
		}
		if (S[i] == 'D') {
			d++;
		}

		


		if (u + d >= H || l + r >= W) {
			cout << "NO";
			return 0;
		}
	}

	if (sr > u && sr <= H - d && sc > l && sc <= W - r) {
		cout << "YES";
	}
	else {
		cout << "NO";
	}

	
	return 0;
}

Measured memory_bytes: 920
#include <cstdio>

#define CH_G(a, g) (a == 1) ? true : g
#define CH_C(a, c) (a == 2) ? true : c
#define CH_P(a, p) (a == 3) ? true : p


int main(void)
{
	int hand[5];
	int i;
	bool g, c, p;
	
	while (1){
		g = c = p = false;
		
		scanf("%d", &hand[0]);
		if (hand[0] == 0) break;
		g = CH_G(hand[0], g);
		c = CH_C(hand[0], c);
		p = CH_P(hand[0], p);
		
		for (i = 1; i < 5; i++){
			scanf("%d", &hand[i]);
			g = CH_G(hand[i], g);
			c = CH_C(hand[i], c);
			p = CH_P(hand[i], p);
		}
		
		if ((g && c && p) || (g && !c && !p) || (!g && c && !p) || (!g && !c && p)){
			for (i = 0; i < 5; i++) printf("3\n");
		}
		else if (g && c){
			for (i = 0; i < 5; i++){
				if (hand[i] == 1) printf("1\n");
				else printf("2\n");
			}
		}
		else if (c && p){
			for (i = 0; i < 5; i++){
				if (hand[i] == 2) printf("1\n");
				else printf("2\n");
			}
		}
		else if (g && p){
			for (i = 0; i < 5; i++){
				if (hand[i] == 3) printf("1\n");
				else printf("2\n");
			}
		}
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = (int)1e8;

int main() {
    int n, m, d[102][102]; 
    int a[1003], b[1003], c[1003];

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = INF;
        }
        d[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
        d[a[i]][b[i]] = d[b[i]][a[i]] = c[i];
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    
    int ans = 0;

    for (int i = 0; i < m; i++) {
        if (d[a[i]][b[i]] != c[i]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define ll long long
#define pb push_back

int main(){

	int N,i;
	cin>>N>>i;
	cout<<N+1-i<<endl;

	return 0;
}

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

vector<int> p, q, r, b;

int lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

int dfs(int v)
{
    if (v == -1) return 1;    
    int lw = dfs(r[v]), rw = dfs(b[v]);
    int l = lcm(p[v] * lw, q[v] * rw);
    return l / p[v] + l / q[v];
}
 
void init(int N)
{
    p.resize(N); q.resize(N);
    r.resize(N); b.resize(N);
}

int main()
{
    int N;
    while (cin >> N, N) {
        init(N);
        bool used[MAX_N] = {};
        for (int i = 0; i < N; i++) {
            cin >> p[i] >> q[i] >> r[i] >> b[i];
            r[i]--; b[i]--;
            if (r[i] >= 0) used[r[i]] = 1;
            if (b[i] >= 0) used[b[i]] = 1;
            int gcd = __gcd(p[i], q[i]);
            p[i] /= gcd;
            q[i] /= gcd;
        }
        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                cout << dfs(i) << endl;
                break;
            }            
        }
    }
    return 0;
}

Measured memory_bytes: 3024
#include<stdio.h>
int main()
{
  char  n[5];
  scanf("%s", &n);
  if((n[0]==n[1]&&n[1]==n[2])||(n[1]==n[2]&&n[2]==n[3])){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

#define FOR(i, b, e) for(int i=(b);i<(e);i++)
#define REP(i, n) FOR(i,0,n)

#define ALL(v) (v).begin(),(v).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000007;
const int INF = 1e9;

const double EPS = 1e-9;
const double PI = acos(-1.0);

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

LL N;

int main() {
    cin >> N;
    LL S = (N - 1) * N / 2;
    cout << S << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
//ll a[N];
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    ll a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    if(a+b<=2*c){
        cout << a*x+b*y<<endl;
    }
    else{
        ll ans=0;
        if(x<y){
            ans+=x*2*c;
            y-=x;
            x-=x;
//            cout << ans <<" "<<x<<" "<<y<<endl;
            if(b*y<=2*c*y)  ans+=b*y;
            else    ans+=2*c*y;
        }
        else{
            ans+=y*2*c;
            x-=y;
            y-=y;
            if(a*x<=2*c*x){
                ans+=a*x;
            }
            else    ans+=2*c*x;
        }cout <<ans << endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,c=0;
  cin>>n;
  map<int,int> mp;
  for(int i=0;i<n;i++){
    cin>>a;
    mp[a]++;
  }
  for(auto au:mp){
    if(au.first<au.second) c+=au.second-au.first;
    else if(au.first>au.second) c+=au.second;
  }
  cout<<c;
}

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

using namespace std;
int s[5];
int main()
{
    char a[5];
    cin>>a;
    memset(s,0,sizeof(s));
    for(int i=0;i<3;i++)
    {
        if(a[i]=='a')
            s[0]=1;
         if(a[i]=='b')
            s[1]=1;
        if(a[i]=='c')
            s[2]=1;
    }
    int cnt=0;
    for(int i=0;i<3;i++){
        if(s[i]==1)
            cnt++;
    }
    if(cnt==3)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#define maxn 2010
using namespace std;
int n, k;
int head[maxn], top;
struct E {
	int to, nxt;
} edge[maxn << 1]; 
inline void insert(int u, int v) {
	edge[++top] = (E) {v, head[u]};
	head[u] = top;
}
int cur;
void dfs(int u, int pre, int d) {
	if (d > k / 2) ++cur;
	for (int i = head[u]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if (v == pre) continue;
		dfs(v, u, d + 1);
	}
}
int main() {
	cin >> n >> k;
	int u, v, ans = (int)2e9;
	for (int i = 1; i < n; ++i) {
		 cin >> u >> v;
		 insert(u, v), insert(v, u);
	}
	if (k & 1)
		for (int u = 1; u <= n; ++u)
			for (int i = head[u]; i; i = edge[i].nxt) {
				cur = 0;
				int v = edge[i].to;
				dfs(u, v, 0);
				dfs(v, u, 0);
				ans = min(ans, cur);
			}
	else 
		for (int u = 1; u <= n; ++u) {
			cur = 0;
			dfs(u, 0, 0);
			ans = min(cur, ans);
		}
	cout << ans;
	return 0;
}

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

using namespace std;

int main(void){
    string S, T;
    cin >> S >> T;
    int idx = S.length() - T.length();
    for(;idx >=0; idx--){
        bool match = true;
        for(int i=0;i<T.length();i++){
            if(S[idx+i]!='?' && S[idx+i] != T[i]){
                match = false;
                break;
            }
        }
        if(match) break;
    }

    if(idx < 0){
        cout << "UNRESTORABLE" << endl;
    } else {
        for(int i=0;i<S.length();i++){
            if(S[i]=='?') {
                if(i-idx >= 0 && i-idx < T.length()) cout << T[i-idx];
                else cout << 'a';
            } else {
                cout << S[i];
            }
        }
        cout << endl;    
    }
    return 0;
}

Measured memory_bytes: 256
import math 

N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(list(map(int, input().split()[1:])))
P = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    i_bin = bin(i)[2:]
    i_bin = (N - len(i_bin))*'0' + i_bin
    flag = True
    for m in range(M):
        cnt = 0
        for n in range(N):
            if i_bin[n]=='1' and n+1 in S[m]:
                cnt += 1
        if cnt%2 != P[m]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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

const ll MAXN = 200000;
const ll INF = 1001001001;
const ll MOD = 1000000007;

ll N, M, ans=0, tmp=INF;
vector<ll> out, in, ok;
vector<vector<ll>> G, B;
vector<set<ll>> S;

void bfs(ll id) {
    queue<ll> Q;
    vector<ll> color, A;
    color.resize(N,-1);
    Q.push(id);
    while(!Q.empty()) {
        ll u = Q.front();
        Q.pop();
        //cout << "OK" << endl;
        for(int i=0;i<G[u].size();i++) {
            if(ok[G[u][i]]>0&&color[G[u][i]]==-1) {
                if(G[u][i]==id) {
                    ll pr = u;
                    while(pr!=id) {
                        A.push_back(pr);
                        pr = color[pr];
                        //cout << "while" << endl;
                    }
                    A.push_back(pr);
                    //cout << "finished" << endl;
                    if(tmp>A.size()) {
                        B.push_back(A);
                        tmp = A.size();
                    }
                    return;
                }
                color[G[u][i]] = u;
                Q.push(G[u][i]);
            }
        }
    }
}

signed main(){
    cin >> N >> M;
    out.resize(N,0);
    in.resize(N,0);
    ok.resize(N,0);
    G.resize(N);
    S.resize(N);
    for(int i=0;i<M;i++) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        out[a]++;
        in[b]++;
        G[a].push_back(b);
        S[a].insert(b);
    }
    for(int i=0;i<N;i++) {
        if(out[i]>0&&in[i]>0) {
            ok[i]++;
        }
    }
    for(int i=0;i<N;i++) {
        if(ok[i]>0) {
            bfs(i);
        }
    }
    if(B.size()==0) {
        cout << -1 << endl;
        return 0;
    }
    cout << B.back().size() << endl;
    for(int i=0;i<B.back().size();i++) {
        cout << B.back()[i]+1 << endl;
    }
    return 0;
}

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

int main(){

  int cnt=0, D1, D2, i, N;
  cin>>N;
  
  for(i=0; i<N; i++){
    cin>>D1>>D2;
    if(D1==D2){
      cnt++;
    }else{
      cnt=0;
    }
    if(cnt==3){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
vector<int> edge[100005],a;
int dis1[100005],dis2[100005];
void dfs(int u,int fa,int val,int tag){
    if(tag==1) dis1[u]=val;
    if(tag==2) dis2[u]=val;
    for(int i=0;i<edge[u].size();i++){
        int v=edge[u][i];
        if(v==fa) continue;
        dfs(v,u,val+1,tag);
    }
}
int main(){
    int n,start,end,ans=0;
    cin>>n>>start>>end;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(end,-1,0,1);
    dfs(start,-1,0,2);
    for(int i=1;i<=n;i++){
        if(dis1[i]>dis2[i]){
            ans=max(ans,dis1[i]-1);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 12928
#include<bits/stdc++.h>
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()

using namespace std;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b){
    return (a*b)/gcd(a,b);
}
int ncr(int n, int k){
    int res = 1;
    if ( k > n - k )
        k = n - k;

    for (int i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

int fibonacci(int n){
    double phi = (1LL + sqrt(5))/(double)2;
    int nth_fib = round(pow(phi,n)/sqrt(5));
    return nth_fib;
}
bool checkYear(int year)  
{  

    if (year % 400 == 0)  
        return true;  
  
    if (year % 100 == 0)  
        return false;  

    if (year % 4 == 0)  
        return true;
        
    return false;  
}
signed main(){

    fastIO

    int a, b, t;
    cin >> a >> b >> t;
    int count = 0;
    for(int i =a; i<=t; i+=a){
        count += b; 
    }
    cout << count ;

    return 0;
}


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

const int MAX_N = 1e5+10;
int N, M;
int p[MAX_N];
int x[MAX_N], y[MAX_N];
int par[MAX_N];

int look(int x)
{
	if(x == par[x]) return x;
	else return par[x]=look(par[x]);
}

void comb(int x, int y)
{
	int a=look(x), b=look(y);
	if(a!=b){
		par[a]=b;
	}
}

void solve()
{
	for(int i=1;i<=N;++i) par[i]=i;
	//for(int i=1;i<=N;++i) comb(i, p[i]);
	for(int i=0;i<M;++i){
		comb(p[x[i]], p[y[i]]);
	}
	int ans = 0;
	for(int i=1;i<=N;++i){
		if(i == p[i] || (look(i)==look(p[i]))) ans++;
	}
	cout << ans << '\n';
} 

int main()
{
	cin >> N >> M;
	for(int i=1;i<=N;++i) cin >> p[i];
	for(int i=0;i<M;++i) cin >> x[i] >> y[i];
	solve();
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

int main() {
  string w;
  cin >> w;
  map<char, int> mp;

  rep(i, w.length()) mp[w[i]]++;

  bool flg = true;
  for (auto x : mp)
    if (x.second % 2 != 0) flg = false;

  cout << (flg ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>

using namespace std;

int main () {
    //ifstream cin("input.in");
    int a, b, c;
    cin >> a >> b >> c;
    if (a % 2 == 0  && a == b && a == c) {
        cout << "-1\n";
        return 0;
    }
    int answer = 0;
    while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
        int a0 = (b + c) / 2, b0 = (a + c) / 2, c0 = (a + b) / 2;
        a = a0;
        b = b0;
        c = c0;
        answer++;
    }
    cout << answer << "\n";
    return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, n) for (int i = (a); i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define FOR(it, c) \
  for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

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

  double ret = 0;
  REP(i, 1, N + 1) {
    double p = 1.0;
    int x = i;
    while (x < K) {
      p *= 0.5;
      x *= 2;
    }
    ret += 1.0 / N * p;
  }

  printf("%.12lf\n", ret);

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int N, L[101], count=0;
    scanf("%d", &N);
    for(int i=0; i<N; i++) scanf("%d", &L[i]);
    for(int i=0; i<N-2; i++){
        for(int j=i+1; j<N-1; j++){
            for(int k=j+1; k<N; k++){
                if(L[i]!=L[j] && L[i]!=L[k] && L[j]!=L[k]) {
                    if(L[i]+L[j]>L[k] && L[j]+L[k]>L[i] && L[k]+L[i]>L[j]){
                        count++;
                    }
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
 
set<int> s;
 
int check[101];
struct node{
    int x,y;
    bool color;
};
 
bool comp(struct node &A,struct node B){
    if(A.x < B.x) return 1;
    return 0;
}
 
int main(int argc, const char * argv[]) {
 
    int n;
    struct node ball[202];
    scanf("%d",&n);
    
    for(int i=0,a,b;i<n;i++){
        scanf("%d %d",&a,&b);
        ball[i].x=a;
        ball[i].y=b;
        ball[i].color = 0;
    }
    
    for(int i=0,c,d;i<n;i++){
        scanf("%d %d",&c,&d);
        ball[n+i].x =c;
        ball[n+i].y =d;
        ball[n+i].color = 1;
    }
    
    sort(ball,ball+2*n,comp);
    int ans2 = 0;
    for(int i=0;i<2*n;i++){
       if(ball[i].color==0){
            s.insert(ball[i].y);
        }else{
            auto ans = s.lower_bound(ball[i].y);
           
            if(ans == s.begin()) continue;
            s.erase(--ans);
            ans2++;
        }
    }
    printf("%d\n",ans2);
return 0;
}

Measured memory_bytes: 256
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, N);
    ll m = N % 10;
    if (m == 2 or m == 4 or m == 5 or m == 7 or m == 9)
    {
        OUT("hon");
    }
    else if (m == 3)
    {
        OUT("bon");
    }
    else
    {
        OUT("pon");
    }
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=2e5+100;
vector <int> g[N];
ll hi[N];
ll dfs(ll v,ll p){
    hi[v]=hi[p]+1;
    for (auto u : g[v]){
        if (u==p) continue;
        dfs(u,v);
    }
}
ll ans[N];
ll q[4];
int32_t main(){
    ll n;
    cin >> n ;
    ll t1=(n+2)/3,t2=(n+1)/3,t3=n/3;
    for (int i=0;i<n-1;i++){
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,1);
    vector <int> a,b;
    for (int i=1;i<=n;i++){
        if (hi[i]%2) a.pb(i);
        else b.pb(i);
    }
    if (a.size()>b.size()) swap(a,b);
   // cout << a.size() << " " << b.size() << endl;
    if (a.size()<=n/3){
        for (auto u :a) ans[u]=3,t3--;
        for (int i=1;i<=n;i++){
            if (ans[i]) continue;
            if (t1) ans[i]=1,t1--;
            else if (t2) ans[i]=2,t2--;
            else if (t3) ans[i]=3,t3--;
        }
    }
    else{
        for (int i=0;i<t1;i++) ans[a[i]]=1;
        for (int i=0;i<t2;i++) ans[b[i]]=2;
        for (int i=1;i<=n;i++) if (ans[i]==0) ans[i]=3;
    }
    q[1]=1,q[2]=2,q[3]=3;
    for (int i=1;i<=n;i++) cout << q[ans[i]] << " " ,q[ans[i]]+=3;
}


Measured memory_bytes: 21484
#include <stdio.h>
#include <string.h>
#include <ctype.h>

void str_toupper(char *str)
{
	int i = 0;
	while(str[i] != '\0') {
		str[i] = toupper((int)str[i++]);
	}
}

int main()
{
	int counter = 0;
	char search[21];
	char word[21];
	scanf("%s", search);
	str_toupper(search);

	while (1) {
		scanf("%s", word);
		if (strcmp(word, "END_OF_TEXT") == 0) break;
		str_toupper(word);
		if (strcmp(word, search) == 0) counter++;
	}
	printf("%d\n", counter);
	return 0;
}



Measured memory_bytes: 2620
/*
 Shahadat Hossain
 I.C.T Department
 Comilla University
 Session: 2013-2014
 */

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define valid(x,y) x>=0 && y>=0 && x<n && y<m
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define ms(a,b) memset(a, b, sizeof(a))
#define eps 1e-5
#define input freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)
#define output freopen("/Users/shahadat/Desktop/output.txt", "w", stdout)
#define d(x) cout << #x << " = " << x << endl
#define dd(x,y) cout << #x << " = " << x << "   " << #y << " = " << y << endl
#define ddd(x,y,z) cout << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << endl
//fprintf(stdout,"\nTIME: %.3lf sec\n", (double)clock()/(CLOCKS_PER_SEC));
//int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
#define bit(n,k) (((n)>>(k))&1)
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define pr(x) {cout << (x) << '\n';  }
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define mask(i) ((1LL<<(i)))
#define endl '\n'
double const PI = acos(-1);
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}


int Check(int n, int pos){return n & (1 << pos);}
int Set(int n, int pos){return n |= (1 << pos);}


using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
int const MOD = 1e9 + 7;

int n;
double dp[301][301][301];

double fun(int a, int b, int c){
    if(!a && !b && !c) return 0;
    
    if(dp[a][b][c] > 0) return dp[a][b][c];
    double res = 0.0;
    if(a > 0) res += a * fun(a - 1, b, c);
    if(b > 0) res += b * fun(a + 1, b - 1, c);
    if(c > 0) res += c * fun(a, b + 1, c - 1);
    res = 1 + (res / (double)n);
    res *= (n / double(a + b + c));
    return dp[a][b][c] = res;
}


int32_t main(){
    cin >> n;
    ms(dp, -1);
    int ar[4] = {};
    for(int i = 1; i <= n; i++){
        int temp; cin >> temp;
        ar[temp]++;
    }
    
    cout << fixed << setprecision(12) << fun(ar[1], ar[2], ar[3]) << endl;
}


Measured memory_bytes: 213376
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define vpii vector<pair<int,int>> 
#define pb push_back

void solve() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int i=0,j=n-1;
	int cnt=0;
	int r1=0,w1=0;
	for(int i=0;i<n;i++) {
		if(s[i]=='R') r1++;
		else w1++;
	}
	while(i<j&&i<n&&j>=0) {
		if(s[i]=='W') {
			while(j>=0&&s[j]!='R') {
				j--;
			}
			if(j>=0&&j>i) {
				swap(s[j],s[i]);
				cnt++;
			}
		}
		i++;
	}
	//cout<<s<<"\n";
	j=n-1;
	while(j>=0&&s[j]!='R') j--;
	for(i=0;i<=j;i++) {
		if(s[i]=='W') {
			cnt++;
			s[i]='-';
		}
	}
	//cout<<s<<"\n";
	cout<<cnt<<"\n";
}
 
int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    //freopen("ou.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc=1;
    //cin>>tc;
    for(int t=1;t<=tc;t++) {
        //cout<<"Case #"<<t<<": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 3736
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    String S = sc.nextLine();
    char c1 = S.charAt(0);
    char c2 = S.charAt(1);
    char c3 = S.charAt(2);
    char c4 = S.charAt(3);
    
    String ans = "No";
    if((c1 == c2 && c3 == c4 && c1 != c3) || (c1 == c3 && c2 == c4 && c1 != c2) || (c1 == c4 && c2 == c3 && c1 != c2)){
      ans = "Yes";
    }    
    System.out.println(ans);
  }
}

Measured memory_bytes: 24020
#include<stdio.h>
 
int S[100000];
int T[50000];
 
int search(int* S, int n, int* T, int q){
    int i;
    int left, mid, right;
    int ans = 0;
    for(i=0; i<q;i++){
        left = 0;
        right = n-1; 
        while(left <= right){
            mid = (left + right)/2;
            if(T[i] == S[mid]){
                ans++;
                break;
            }
            if(T[i] > S[mid]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return ans;
}
 
 
int main(void){
    int n,q;
    int i;
    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%d", &S[i]);
    }
    scanf("%d", &q);
    for(i=0;i<q;i++){
        scanf("%d", &T[i]);
    }
     
    printf("%d\n", search(S,n,T,q));
    return 0;
}


Measured memory_bytes: 2380
import sys
input = sys.stdin.readline

class segtree:
    x_unit=0 # 単位元
    x_func=max  # 関数
    condition=lambda self,a,b: a>=b # max_right用に定義
    def __init__(self,n,seq): # 元のseqと要素数n
        self.n=n
        self.x=[self.x_unit]*(2*n)
        for i,j in enumerate(seq, self.n): # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
    def update(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def get(self, i): # 値を入手
        return self.x[i+self.n] 
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)
    def max_right(self, l, v): 
        # index lを含めて右にある値の中でa[j]>=vを満たす最小のindexを求める
        # 存在しない場合はnを出力
        r=self.n
        if self.condition(self.fold(l,r),v)==False:
            return r
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return l
    def min_left(self, r, v): 
        # index rを含まずに左にある値の中でa[j]>=vを満たす最大のindexを求める
        # 存在しない場合は0を出力
        l=0
        if self.condition(self.fold(l, r),v)==False:
            return l
        else:
            while r-l>1:
                l1=l
                r1=l+(r-l)//2
                l2=l+(r-l)//2
                r2=r
                if self.condition(self.fold(l1, r1),v)==True:
                    l=l1
                    r=r1
                else:
                    l=l2
                    r=r2
            return r

n,q=map(int,input().split()) 
*a,=map(int,input().split())
seg=segtree(n,a)


for i in range(q):
    t,x,y=map(int,input().split()) 
    if t==1:
        x-=1
        seg.update(x, y)
    elif t==2:
        print(seg.fold(x-1,y))
    else:
        print(seg.max_right(x-1, y)+1)

Measured memory_bytes: 107828
#include<stdio.h>
int check_so_chan(int n)
{
    if(!(n%2 == 0)) return 0;
    return 1;
}
main()
{
    int N;
    int check = 1;
    scanf("%d", &N);
    int A[N];
    for(int i = 0 ; i< N ; i++)
    {
        scanf("%d", &A[i]);
    }
    // for(int i = 0 ; i < N ; i++)
    // {
    //     printf("%d ", A[i]);
    // }
    for(int i = 0 ; i < N ; i++)
    {
        if(check_so_chan(A[i]))
        {
            if(!((A[i] % 3 == 0) || (A[i] % 5 == 0))) 
            check = 0;
        }
    }
    if(check == 1) printf("APPROVED");
    else printf("DENIED");
}

Measured memory_bytes: 1652
n = int(input())
b = list(map(int, input().split()))

a = [b[0]]

for i in range(n-1):
    if i < n-2:
        a.append(b[i] if b[i+1] >= b[i] else b[i+1])
    else:
        a.append(b[i])

print(sum(a))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
char a[10100];
int main(){
    int n;
    cin >> n;
    scanf("%s", a);
    int len = strlen(a);
    for(int i = 0; i < len; i++){
        printf("%c", ((a[i]-'A'+n)%26)+'A');
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

    while (in.hasNext()) {
      int A = in.nextInt();
      int B = in.nextInt();
      int C = in.nextInt();

      System.out.println(Math.min(B / A, C));
    }
  }
}

Measured memory_bytes: 23252
def f(n, s, max)
  # s????????????max?????????
  max_min = ((2*s/n.to_f+n-1)/2)
  if n == 1
    # n=1?????¨??????s???????????´??°?????????????????????0???????????????
    if max >= s and s != 0
      return 1
    else
      return 0
    end
  elsif max < max_min
    return 0
  else
    result = 0
    max = s if s < max
    for i in (max_min.ceil)..max
      result += f(n-1, s-i, i-1)
    end
    return result
  end
end
while (n, x = gets.split(" ").map(&:to_i)) != [0,0]
  puts f(3, x, n)
end

Measured memory_bytes: 8764
#include <cstdlib>
#include <iostream>
#include <string>
std::string B="4141212141412121";
int main(){
	int i,j,C[8]={},x[8]={},s,m,p,tmp;
	for(i=8;i--;)C[i]=atoi(B.substr(i,8).c_str());
	while(std::cin>>x[0]){
		m=x[0];
		for(i=1;i<8;i++){
			std::cin>>x[i];
			m+=x[i];
		}
		for(i=8;i--;){
			s=0;
			for(j=8;j--;){
				tmp=x[j]-B[i+j]+'0';
				s+=(tmp>0?tmp:0);
			}
			if(s<m){
				m=s;
				p=i;
			}
			else if(m==s&&C[i]<C[p])p=i;
		}
		for(i=0;i<8;i++)std::cout<<B[p+i]<<" \n"[i==7];
	}
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){

    ll a,b,c,d;
    cin >> a >> b >>  c >> d;
    if(a>b) swap(a,b);
    if(c<d) swap(c,d);
    ll lcm =d*(c/(__gcd(c,d)*1ll));
    ll ans1 = (b/c) - ((a-1)/c);
    ll ans2 = (b/d) - ((a-1)/d);
    ll ans3 = b/lcm - ((a-1)/lcm);
    cout << b-a+1-ans1-ans2+ans3<< endl;




return 0;
}


Measured memory_bytes: 256