akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
typedef pair<int,int> P;
using vi=vector<long long>;
using vvi=vector<vector<long long>>;
using vc=vector<char>;
using vvc=vector<vector<char>>;
const int inf=1000000009;
void chmin(auto &a,auto b){if(b<a)a=b;}
void chmax(auto &a,auto b){if(a<b)a=b;}

int ans=999999999;
vi x(3);
int n;
void dfs(vvi v,int c,int i,vi a){
  if(c!=3)v[c].push_back(a[i]);
  if(i==n-1)dfs(v,3,i+1,a);
  else if(i==n){
    bool b=true;
    int mp=0;
    rep(j,3){
      int sum=0;
      if(!v[j].size())b=false;
      mp+=(v[j].size()-1)*10;
      rep(k,v[j].size())sum+=v[j][k];
      mp+=abs(sum-x[j]);
    }
    if(b)chmin(ans,mp);
  }
  else{
    dfs(v,0,i+1,a);
    dfs(v,1,i+1,a);
    dfs(v,2,i+1,a);
    dfs(v,3,i+1,a);
  }
}
int main(){
  cin>>n;
  vvi v(3);
  rep(i,3)cin>>x[i];
  vi a(n);
  rep(i,n)cin>>a[i];
  dfs(v,3,-1,a);
  cout<<ans<<endl;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b=[0]*n
for i in range(m):
    b[a[i][0]-1]+=1
    b[a[i][1]-1]+=1
for i in range(n):
    print(b[i])

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int N = scan.nextInt();
    int cnt=0;
    while(true){
      if(cnt*2<N){
        cnt++;
      }
      else break;
    }
    System.out.printf("%d",cnt);
  }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


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

  int n;
  cin>>n;
  double ans=0;
  rep(i,n){
    double x;
    cin>>x;
    string u;
    cin>>u;
    if(u[0]=='J') ans+=x;
    else ans+=x*380000;
  }

  cout<<ans<<endl;


}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
	char s[27];
	int a[27]={0};
	scanf("%s",&s);
	for(int i=0;i<strlen(s);i++){a[s[i]-97]++;}
	for(int i=0;i<strlen(s);i++){
		if(a[i]==2){
			printf("no");
			return 0;
		}
	}
	
	printf("yes");
	return 0;
}

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


int main() {
 
    int n,m,x;
    cin >> n >> m >> x;
    
    int arr[n][m];
    int cost[n];
    
    for(int i = 0 ; i < n ; i++) {
        cin >> cost[i];
        for(int j = 0 ; j < m ; j++) {
            cin >> arr[i][j];
        }
    }
    
    int ans = INT_MAX;
    for(int q = 0 ; q < (1 << n) ; q++) {
        
        vector<int> skill(m, 0);
        int c = 0;
        for(int i = 0 ; i < n ; i++) {
            if((1 << i) & q) {
                c += cost[i];
                for(int j = 0 ; j < m ; j++)
                    skill[j] += arr[i][j];
            }
        }
        
        for(int i = 0 ; i < m ; i++)
            if (skill[i] < x) c = INT_MAX;
        
        ans = min(ans, c);
    }
    
    cout << ((ans == INT_MAX) ? -1 : ans) << endl;
    
    
}


Measured memory_bytes: 3632
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = I()
a =LI()
a.sort(reverse=True)
ans = 0
for i in range(n):
  ans += a[i//2]
print(ans - a[0])

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

using namespace std;

#define FOR(i,n) for(int i=0; i<n; ++i)
#define FORR(i,a,n) for(int i=a; i<n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

const int INF = 0x3f3f3f3f;

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
//int in() { int x; scanf("%d", &x); return x; }
//ll lin() { ll x; scanf("%lld", &x); return x; }
void printfv(VI a){ int n = a.size(); FOR(i, n) cout << a[i] << " "; }

int main(void){

	int n;
	cin >> n;

	int a[n], b[n];
	FOR(i, n){
		cin >> a[i];
		b[i] = a[i];
	}
	
	sort(b, b+n, greater<int>());

	FOR(i, n){
		if(a[i] == b[0]){
			cout << b[1] << '\n';
		} else {
			cout << b[0] << '\n';
		}
	}

    return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 300000;
const int MAXM = 200010;
const int MAXK = 110;
const int MAXQ = 200010;

int n, a[MAXN];
multiset<int> s;
vector<int> slimes, newSlimes;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,(1<<n)) cin >> a[i];
    FOR(i,1,(1<<n)) s.insert(-a[i]);
    slimes.emplace_back(*s.begin());
    s.erase(s.begin());
    FOR(i,1,n) {
        newSlimes.clear();
        FOR(j,0,SZ(slimes)-1) {
            multiset<int>::iterator it = s.upper_bound(slimes[j]);
            if (it == s.end()) {
                cout << "No";
                return 0;
            }
            newSlimes.emplace_back(*it);
            s.erase(it);
        }
        FOR(j,0,SZ(newSlimes)-1) slimes.emplace_back(newSlimes[j]);
        sort(ALL(slimes));
    }
    cout << "Yes";
    return 0;
}


Measured memory_bytes: 14840
#include <iostream>
#include <vector>
#include <math.h>
#include <iomanip>
using namespace std;

int main() {

	long double N, K;

	cin >> N >> K;

	long double p = 0.0;

	for (double i = 1; i <= N; i+=1.0) {
		double score = i;
		double count = 0;
		
		while (score < K) {
			score *= 2.0;
			count += 1.0;
		}

		p += (1/N)*pow(0.5, count);
	}

	cout << setprecision(16) << p << endl;

	return 0;

}

Measured memory_bytes: 892
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	int N, m; cin >> N >> m;
	vector<int> c(m), d(m);
	for (int j = 0; j < m; j++) cin >> c[j] >> d[j];
	vector<int> a(N + 2), b(N + 2);
	for (int j = 0; j < m; j++) {
		a[c[j]]++;
		b[d[j]]++;
	}
	int l = -1, x = 0, ans = 0;
	for (int i = 0; i <= N + 1; i++) {
		ans++;
		if (a[i] > 0) {
			if (l == -1) l = i;
			x += a[i];
		}
		x -= b[i];
		if (x == 0 && l != -1) {
			ans += (i - l) * 2;
			l = -1;
		}
	}
	cout << ans - 1 << endl;
} 

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long long int x;
    cin>>x;
    if(x%11>6){
        cout<<(x/11)*2+2;
    }else if(x%11>0){
        cout<<(x/11)*2+1;
    }else{
        cout<<(x/11)*2;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    int i, N;
    long long p, q;

    while (cin >> N && N != 0) {
        cin.get();

        map<int, long long> sales;
        vector<int> sequence;        
        
        for (int n = 0; n != N; ++n) {
            cin >> i >> p >> q;
            if (!sales.count(i)) { 
                sequence.push_back(i);
            }
            sales[i] += p * q;
        }

        bool printNA = true;
        
        for (int i = 0; i != sequence.size(); ++i) {
            if (sales[sequence[i]] >= 1000000) {
                cout << sequence[i] << endl;
                printNA = false;
            }
        }

        if (printNA) {
            cout << "NA" << endl;
        }
    }
    return 0;
}

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

#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a, 0, sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define SIZE(array) (sizeof(array) / sizeof(array[0]))

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

#define MOD 1000000007L
#define INF 100000000000

signed main() {
	int n, m, k;
	cin >> n >> m >> k;
	bool ok = false;
	for (size_t i = 0; i <= n && !ok; i++) {
		if (i * m == k) {
			ok = true;
		}
	}
	for (size_t i = 0; i <= m && !ok; i++) {
		if (i * n == k) {
			ok = true;
		}
	}
	for (size_t i = 1; i <= n && !ok; i++) {
		for (size_t j = 1; j <= m && !ok; j++) {
			if ((i * j + (m - j) * (n - i)) == k) {
				ok = true;
			}
		}
	}
	cout << (ok ? "Yes" : "No") << endl;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll ,ll> pll;
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(), (X).end()
#define REP(i,x,y) for(ll i = x;i <= y;++i)
vector<string> vec_splitter(string s) {
    for(char& c: s) c = c == ','?  ' ': c;
    stringstream ss; ss << s;
    vector<string> res;
    for(string z; ss >> z; res.push_back(z))
        ;
    return res;
}
void debug_out(vector<string> args, int idx) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, Head H, Tail... T) {
    if(idx > 0) cerr << ", ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
void localTest() {
    #ifndef ONLINE_JUDGE
        freopen("inp", "r", stdin);
        freopen("out", "w", stdout);
    #endif      
}
int main() {

    localTest();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, ans = 0, tn;
    cin >> n;
    tn = n;
    for(ll i = 2;i * i <= tn;++i) {
        if(n % i == 0) {
            ll cnt = 0;
            while(n % i == 0) n /= i, ++cnt;
            // debug(i, cnt);
            for(ll j = 1;j <= 100;++j) {
                if((j * (j + 1)) / 2 > cnt) {
                    ans += (j - 1);
                    break;
                }
            }
        }
    }
    // debug(n);
    if(n > 1) ans++;
    cout << ans << "\n";   
    
    return 0;
}

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

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

typedef long long ll;
typedef vector<ll> vi;

int main(){
	ll n,k; cin>>n>>k;
	ll dp[109][nax];
	vi v(n);
	REP(i,n) cin>>v[i];

	REP(i,n+1) REP(j,k+1) dp[i][j] = 0LL;
	dp[0][0] = 1;

	FOR(i,1,n+1){
		dp[i][0] = 1LL;
		FOR(j,1,k+1){
			dp[i][j] = (dp[i][j-1] + dp[i-1][j])%1000000007LL;
			if(j-v[i-1]-1>=0) 
				dp[i][j] =(dp[i][j]- dp[i-1][j-v[i-1]-1]+1000000007LL)%1000000007LL;
		}
	}
/*	REP(i,n+1){
		REP(j,k+1){
			cout<<dp[i][j]<<" ";
		}
		cout<<endl;
	}*/
	
	cout<<dp[n][k]%1000000007LL;
	
	return 0;
}

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

int const MAX = 5005;
long long const MOD = 1000000007;
long long dp[MAX][MAX];

long long mult_mod(long long x,long long y) {
	return (x*y) % MOD;
}
long long plus_mod(long long x, long long y) {
	return (x + y) % MOD;
}

int main() {
	int n, m; string s;
	cin >> n >> s;
	m = s.size();
	dp[0][0] = 1;
	for (int i = 0; i <= n; i++) {
		dp[i][i + 1] = 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0) {
				dp[i][j] = plus_mod(dp[i - 1][0], mult_mod(2, dp[i - 1][1]));
			}
			else {
				dp[i][j] = plus_mod(dp[i - 1][j - 1], mult_mod(2, dp[i - 1][j + 1]));
			}
		}
	}
	cout << dp[n][m] << endl;
}


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

const int N=100010;
struct Edge{int u,v,del,next;} e[N<<1];
int h[N],sum=-1,pre[N];
bool vis[N];
int n,m,deg[N];

void add_edge(int u,int v)
{
    e[++sum]={u,v,0,h[u]};h[u]=sum;
    e[++sum]={v,u,0,h[v]};h[v]=sum;
}

void dfs(int u)
{
    vis[u]=1;
    for(int t=h[u];~t;t=e[t].next)
    {
        if(e[t].del) continue;
        int v=e[t].v;
        if(vis[v]) continue;
        pre[v]=t;dfs(v);
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        deg[u]++;deg[v]++;
    }
    int four=0,six=0;
    for(int i=1;i<=n;i++)
    {
        if(deg[i]&1) return puts("No"),0;
        if(deg[i]==4) four++;
        if(deg[i]==6) six++;
    }
    if(six>=1) return puts("Yes"),0;
    if(four>=3) return puts("Yes"),0;
    if(four<2) return puts("No"),0;
    int A=0,B=0,cnt=0;
    for(int i=1;i<=n;i++)
        if(deg[i]==4) (!A)?(A=i):(B=i);
    while(1)
    {
        memset(vis,0,sizeof(vis));
        dfs(A);
        if(!vis[B]) break;
        for(int u=B;u!=A;u=e[pre[u]].u)
            e[pre[u]].del=e[pre[u]^1].del=1;
        cnt++;
    }
    puts(cnt==2?"Yes":"No");
    return 0;
}

Measured memory_bytes: 5376
#include<cstdio>
#include<algorithm>
using std::max;

typedef long long ll;
const int maxn = 1e5 + 10;
const ll INF = 1ll<<60;

ll dp[maxn][2];//1: flipped

ll A[maxn];

inline void upt(ll &x, ll y)
{
	x = x < y ? y : x;
}

int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
	{
		scanf("%lld", &A[i]);
		dp[i][0] = dp[i][1] = -INF;
	}
	
	A[0] = 0;
	dp[1][0] = A[1];
	for(int i = 2; i <= N; ++i)
	{
		upt(dp[i][0], dp[i-1][0] + A[i]);
		upt(dp[i][0], dp[i-1][1] + A[i]);
		upt(dp[i][1], dp[i-1][0] - A[i] - 2 * A[i - 1]);
		upt(dp[i][1], dp[i-1][1] - A[i] + 2 * A[i - 1]);
	}
	printf("%lld\n", max(dp[N][0], dp[N][1]));
}

Measured memory_bytes: 2560
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
S = set(A)
if len(S) == 1:
    if 0 in S:
        print("Yes")
    else:
        print("No")
elif len(S) == 2:
    K = Counter(A)
    if 0 in K and K[0] == n//3:
        print("Yes")
    else:
        print("No")
elif len(S) == 3:
    K = Counter(A)
    ans = []
    for i,j in K.items():
        ans.append([i,j])
    if ans[0][1] == ans[1][1] and ans[1][1] == ans[2][1] and ans[0][0]^ans[1][0]^ans[2][0] == 0:
        print("Yes")
    else:
        print("No")
else:
    print("No")
        
    

Measured memory_bytes: 14468
#include<stdio.h>

int main(void)
{
  int i=0,p=0,p_save=0;
  char s[10];
  
  scanf("%s",s);
  
  for(i=0;i<10;i++){  
      
    if((s[i]=='A')||(s[i]=='T')||(s[i]=='C')||(s[i]=='G'))
    {
      p++;
      if(p > p_save)p_save=p;
    }
     else   p=0;  
  }
  
  printf("%d",p_save);
    
  
  
 return 0 ;
}

Measured memory_bytes: 128
import threading, queue

N, M = map(int, input().split())
AB = [[] * N for _ in range(N)]
m = [0] * (N + 10)
q = queue.Queue()
q.put(0)

for _ in range(M):
  A, B = map(int, input().split())
  AB[A - 1].append(B - 1)
  AB[B - 1].append(A - 1)
  
while not q.empty():
  s = q.qsize()
  for _ in range(s):
    t = q.get()
    for p in AB[t]:
      if m[p] == 0:
        m[p] = t + 1
        q.put(p)

print('Yes')
for i in range(1, N):
  print(m[i])

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

int main(void)
{
    int n;
    long d;
    cin >> n >> d;
    
    int cnt = 0;
    for (int i = 0; i < n; i++){
        long x, y;
        cin >> x >> y;
        if ( x*x + y*y <= d*d){
            cnt++;
        }
    }

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


Measured memory_bytes: 3592
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char st[7];
int main()
{
	int ans=0;
	scanf("%s",st+1);
	for(int i=1;i<=6;i++)
	{
		if(st[i]=='1')ans++;
	}
	if(ans==0)printf("0\n");
	else printf("%d\n",ans);
}

Measured memory_bytes: 256
import sys

s = input()
s_no_x = s.replace('x', '')
s_no_x_inv = s_no_x[::-1]

if not s_no_x == s_no_x_inv:
    print(-1)
    sys.exit()

count = 0
l = 0
r = len(s) - 1
while l < r:
    if l >= r:
        break
    if s[l] == s[r]:
        l += 1
        r -= 1
    if not s[l] == s[r]:
        count += 1
        if s[l] == 'x':
            l += 1
        else:
            r -= 1
print(count)


Measured memory_bytes: 3316
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MOD 998244353
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long lli;
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int main()
{
    int n, nn, k, i;
    scanf("%d %d",&n,&k);
    double p = 0;
    for(i=1; i<=n; i++) {
        int j;
        nn = i;
        for(j=0; ; j++) {
            if(j>0) nn*=2;
            if(nn >=k) break;
            // printf("%d %d\n",i,j);
        }
        p += powl(0.5, j) / (double)n;
    }
    printf("%.11lf",p);
    return 0;
}


Measured memory_bytes: 384
import java.util.*;
import java.io.*;

public class Main {

  void solve(InputReader in, PrintWriter out) {
    int n = in.nextInt();
    int k = in.nextInt();

    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (int i = 0; i < n; ++i) {
      q.offer(-1 * in.nextInt());
      if (q.size() > n - k)
        q.poll();
    }
    
    long ans = 0;
    while (!q.isEmpty()) {
      ans -= q.poll();
    }
    out.println(ans);
  }

  public static void main(String[] args) throws Exception {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Main solver = new Main();
    solver.solve(in, out);
    out.close();
  }

  static class InputReader {
    BufferedReader in;
    StringTokenizer st;

    public InputReader(InputStream is) {
      in = new BufferedReader(new InputStreamReader(is));
    }

    public String next() {
      try {
        while (st == null || !st.hasMoreTokens()) {
          st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }
  }
}


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

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

int n;
char s[500010];
int v[500010];

int stk[1000010];
int stki = 0;

int main(){
  scanf("%s",s);
  n=strlen(s);
  rep(i,0,n+1){
    v[i] = -1;
  }
  if(s[0] == '<'){
    v[0] = 0;
    stk[stki++] = 0;
  }
  if(s[n-1] == '>'){
    v[n] = 0;
    stk[stki++] = n;
  }
  rep(i,1,n){
    if(s[i] == '<' && s[i-1] == '>'){
      v[i] = 0;
      stk[stki++] = i;
    }
  }
  ll ans = 0;
  int st = 0;
  while(st < stki){
    int idx = stk[st];
    if(idx > 0 && s[idx-1] == '>' && (v[idx-1] == -1|| v[idx-1]<v[idx]+1)){
      if(v[idx-1] != -1){
        ans -= v[idx-1];
      }
      v[idx-1] = v[idx] + 1;
      ans += v[idx-1];
      stk[stki++] = idx-1;
    }
    if(idx < n && s[idx] == '<' && (v[idx+1] == -1|| v[idx+1]<v[idx]+1)){
      if(v[idx+1] != -1){
        ans -= v[idx+1];
      }
      v[idx+1] = v[idx] + 1;
      ans += v[idx+1];
      stk[stki++] = idx+1;
    }
    st++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 6528
from math import gcd

def main():
  n = int(input())
  ans = 0
  for i in range(n):
    for j in range(n):
      for k in range(n):
        ans += gcd(i+1, gcd(j+1,k+1))
  print(ans)

if __name__ == '__main__':
  main()

Measured memory_bytes: 9176
#include<stdio.h>
int main(){
  int a,b,c;
  char s[1000];
  gets(s);
  for(a=0;s[a]!='\0';a++){
    if(s[a]!=' '){
      if(s[a]>='a' && s[a]<='z'){
	s[a]=s[a]-32;
      }
    }
  }
  printf("%s\n",s);
  return (0);
}

Measured memory_bytes: 520
import sys

input = sys.stdin.readline

H, W = map(int, input().split())

grid = []

count_w = [[0] * W for _ in range(H)]
count_h = [[0] * W for _ in range(H)]

for _ in range(H):
  grid.append([x for x in input()])
  

for h in range(H):
  r = 0
  count = 0
  for l in range(W):
    while r < W and grid[h][r] == '.':
      r += 1
      count += 1
    count_w[h][l] = count
    if r == l:
      r += 1
      count = 0
      
for w in range(W):
  r = 0
  count = 0
  for l in range(H):
    while r < H and grid[r][w] == '.':
      r += 1
      count += 1
    count_h[l][w] = count
    if r == l:
      r += 1
      count = 0

answer = 0

for h in range(H):
  for w in range(W):
    answer = max(answer, count_h[h][w] + count_w[h][w] - 1)

print(answer)


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

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;

const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}

ll minll(ll a, ll b){
    if(a >= b)  return b;
    else    return a;
}

ll maxll(ll a, ll b){
    if(a >= b)  return a;
    else    return b;
}

ll n,k;
const int SIZE = 100+10;
ll v[SIZE];
ll mem_arr[SIZE],r_sum[SIZE],l_sum[SIZE];
ll ans;

void solve(ll dust_num, ll in_num){
    ll tmp_ans;
    if(in_num > n)  in_num = n;
    for(int r_num = 0; r_num <= in_num; r_num++){
        int l_num = in_num-r_num;
        tmp_ans = 0;
        for(int i = 0; i < r_num; i++){
            mem_arr[i] = v[i];
            tmp_ans += v[i];
        }
        for(int i = 0; i < l_num; i++){
            mem_arr[r_num+i] = v[n-1-i];
            tmp_ans += v[n-1-i];
        }
        sort(mem_arr,mem_arr+in_num);
        for(int i = 0; i < dust_num; i++){
            if(mem_arr[i] < 0)  tmp_ans -= mem_arr[i];
            else    break;
        }

       // cout << r_num << ' ' << l_num << ' ' << tmp_ans << endl;
        ans = max(ans,tmp_ans);
    }
}


int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        r_sum[i] += v[i];
    }

    for(int i = 0; i < n; i++){
        l_sum[i] += v[n-1-i];
    }

    ll score = 0, l_pos = 0, r_pos = n-1;

    for(int i = 0; i <= k/2; i++){
        solve(i,k-i);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int h, w, d;
pair<int, int> invP(int a) { return make_pair(a / h, a % h); }
int toP(int x, int y) { return x * h + y; }
int cost(int x, int y, int x2, int y2) { return abs(x - x2) + abs(y - y2); }
int cost(pair<int, int> p, pair<int, int> p2) {
  return cost(p.first, p.second, p2.first, p2.second);
}
vector<vector<int>> a;
int q;
vector<pair<int, int>> lrs;
vector<int> inv;
vector<vector<int>> path;

int solve(int l, int p) {
  int ret = 0;
  for (int i = 0; p > 0; p /= 2, i++) {
    if (p % 2 == 1) {
      ret += path[l][i];
      l += (1 << i) * d;
    }
  }
  return ret;
}

int main() {
  cin >> h >> w >> d;
  a.resize(h);
  for (int i = 0; i < h; i++) {
    a[i].resize(w);
    for (int j = 0; j < w; j++)
      cin >> a[i][j];
  }
  cin >> q;
  lrs.resize(q);
  for (int i = 0; i < q; i++)
    cin >> lrs[i].first >> lrs[i].second;
  path.resize(h * w);
  inv.resize(h * w);
  for (int i = 0; i < h; i++)
    for (int j = 0; j < w; j++)
      inv[a[i][j] - 1] = toP(j, i);
  for (int i = 0; i < h * w - d; i++) {
    path[i].push_back(cost(invP(inv[i]), invP(inv[i + d])));
  }
  for (int l = 1; (1 << l) * d < h * w; l++) {
    for (int i = 0; i < h * w - (1 << l) * d; i++)
      path[i].push_back(path[i][l - 1] + path[i + (1 << (l - 1)) * d][l - 1]);
  }
  for (int i = 0; i < q; i++) {
    cout << solve(lrs[i].first - 1, (lrs[i].second - lrs[i].first) / d) << endl;
  }
  return 0;
}


Measured memory_bytes: 13312
from operator import itemgetter
from bisect import bisect_right
import sys
input = sys.stdin.readline

n, d, a = map(int, input().split())
monster = [tuple(map(int, input().split())) for _ in range(n)]
monster.sort(key=itemgetter(0))
xx = [xi for xi, hi in monster]

# 尺取
d_range = [-1] * n
idx = 0
for i, (xi, hi) in enumerate(monster):
    while idx < n and xx[idx] - xi <= 2 * d:
        idx += 1
    d_range[i] = idx

ans = 0
imos = [0] * (n + 1)
for i, (xi, hi) in enumerate(monster):
    hi -= imos[i]
    if hi > 0:
        c = (hi + a - 1) // a
        ans += c
        idx = d_range[i]
        imos[i] += c * a
        imos[idx] -= c * a

    # update imos
    imos[i + 1] += imos[i]

print(ans)


Measured memory_bytes: 89916
n=int(input())
A=list(map(int,input().split()))
t= [[i] for i in range(1,n+1)]
for i in range(n):
  t[i].append(A[i])
t1=sorted(t,key=lambda x: x[1])
for i in range(n-1):
  print(str(t1[i][0])+" ",end="")
print(t1[-1][0])

Measured memory_bytes: 24700
import java.util.*;
class Main{
 static public void main(String[] args){
  Scanner sc=new Scanner(System.in);
   int a=sc.nextInt(),b=sc.nextInt();
   int count=0;
   for(int i=a;i<=b;i++){
    if(j(Integer.toString(i)))count++;
   }
   System.out.print(count);
   sc.close();
 }
 static boolean j(String a){
    int in=0;
    int ind=a.length()-1;
    while(in<ind){
        if(a.charAt(in++)!=a.charAt(ind--))return false;
    }
    return true;
 }
}


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

signed main(void)
{
	int n, m; 
	cin >> n >> m;
	map<int, int> a;

	rep(i, m) 
	{
		int s, c;
		cin >> s >> c;
		if ((a.count(s) && a.at(s) != c)|| (s == 1 && c == 0 && n != 1))
		{
			cout << "-1" << endl;
			return 0;
		}
		else 
			a[s] = c;
	}
	if (m == 0 && n == 1)
	{
		cout << "0" << endl;
		return 0;
	}
	rep(i, n)
	{
		if (a.count(i + 1))
			cout << a.at(i + 1);
		else if (i != 0)
			cout << "0";
		else
			cout << "1";
	}
	cout << endl;
}


Measured memory_bytes: 256
def solve():
    N,K = [int(s) for s in input().split() if s]
    h = [int(input()) for _ in range(N)]
    h = sorted(h)
    result = 10**9+1
    # print(h)
    for i in range(N-K+1):
        diff = h[i+K-1]-h[i]
        # print(h[i+K-1],h[i],diff)
        if result > diff:
            result = diff
    print(result)
    
solve()

Measured memory_bytes: 8280
func readIntArray() -> [Int] {
    readLine()!.split(separator: " ").map({Int($0)!})
}

let N = Int(readLine()!)!
var A = readIntArray()
A.sort(by: {$0 > $1})

var ans = 0

for i in 1..<N {
    ans += A[i / 2]
}
print(ans)


Measured memory_bytes: 21340
import numpy as np
def main():
    a_list = np.array([list(map(int, input().split())) for _ in range(3)])
    n = int(input())
    b_list = [int(input()) for _ in range(n)]
    for b in b_list:
        tmp = np.argwhere(a_list == b).tolist()
        if tmp:
            a_list[tmp[0][0], tmp[0][1]] = 0
    for i in range(3):
        # 横
        if all([a == 0 for a in a_list[i]]):
            print("Yes")
            return
    # 縦
    for i in range(3):
        if all([a_list[j][i] == 0 for j in range(3)]):
            print("Yes")
            return
    # ななめ
    if a_list[0][0] == a_list[1][1] == a_list[2][2] == 0:
        print("Yes")
        return
    if a_list[0][2] == a_list[1][1] == a_list[2][0] == 0:
        print("Yes")
        return
    print("No")
main()


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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


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

	int mx = 100001;
	bool isprime[mx];
	for (int i = 0; i < mx; i++) {
		isprime[i] = true;
	}
	isprime[1] = false;
	for (int i = 2; i < mx; i++) {
		for (int j = i*2; j < mx; j+=i) {
			isprime[j] = false;
		}
	}

	int num[mx];
	num[0] = 0;

	int sum = 0;
	for (int i = 1; i < mx; i++) {
//		isprime[i];
		if (isprime[i] && isprime[(i+1)/2] && i % 2 != 0) {
			sum++;
		}
		num[i] = sum;
	}

	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
//		cout << num[r] << " " << num[l-1] << endl;
		cout << num[r] - num[l-1] << "\n";
	}
}


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

using namespace std;

int main()
{
	string S;

	getline(cin,S);

	char s1 = S[0];
	char s2 = S[1];
	char s3 = S[2];

	//cout << s1 <<":"<< s2 <<":"<< s3<<endl;

	if((s1 == s2) && (s2 == s3) && (s1 == 'R'))
		cout<<3<<'\n';
	else if((s1 == s2) && (s2 == s3) && (s1 == 'S'))
		cout<<0<<'\n';
	else if((s1 == s2) && (s2 == 'R') && (s3 == 'S'))
		cout<<2<<'\n';
	else if((s2 == s3) && (s2 == 'R') && (s1 == 'S'))
		cout<<2<<'\n';
	else
		cout<<1<<'\n';
}

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

int main() {
  int n, m;
  cin >> n >> m;
  int count = 0;
  double sum = 0;
  double a[100];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum += a[i];
  }
  for (int i = 0; i < n; i++) {
    if (a[i] >= sum / (4.0 * m))
      count ++;
  }
  if (count >= m)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
MAX_list = []
ans = 0
A = -10**9-2

for _ in range(N):
    X, L = map(int, input().split())
    MAX_list.append(((X + L), (X - L)))
MAX_list = sorted(MAX_list)

for m, l in MAX_list:
    if l >= A:
        ans += 1
        A = m

print(ans)

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

#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(v) reverse((v).begin(),(v).end())
#define ANS(ans) cout<<(ans)<<endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  for (int i = 0; i < (n); ++i)

void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

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

    VI v(n);
    REP(i,n){
        v[i] = i + 1;
    }
    VI p(n);
    VI q(n);
    REP(i,n){
        cin >> p[i];
    }
    REP(i,n){
        cin >> q[i];
    }

    long long i = 0;
    long long cp, cq;
    do{
        if(v == p){
            cp = i;
        }
        if(v == q){
            cq = i;
        }
        i++;
    } while (next_permutation(v.begin(), v.end()));


    ANS(abs(cp - cq));
    return 0;
}


Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)]

L = ["0"]*N
for i in range(N):
    temp = ["0"]*10
    for j in range(10):
        temp[j] = S[i][j]
    temp.sort()
    L[i] = temp
        
L.sort()
ans = 0
cnt = 1
temp = L[0]
for i in range(1, N):
    if temp == L[i]:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        temp = L[i]
        
ans += cnt*(cnt-1)//2
print(ans)

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

#define _GLIBCXX_DEBUG

#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define rep(i, n) for ((i) = 0; (i) < (n); (i)++)

int main(){
    ll N; 
    vll S;
    
    ll i, j, k;
    vll ans_tree;

    set<int> indices;

    cin >> N;
    S.resize(1 << N);
    rep (i, 1 << N) {
        cin >> S[i];
    }

    sort(S.rbegin(), S.rend());

    ans_tree.assign(1 << (N + 1), 0);
    indices.insert(1);
    ll prev_S = 0, prev_elem = 0;
    for (auto s: S) {
        if (prev_S != s) {
            prev_elem = 0;
        }
        auto it = indices.lower_bound(prev_elem);
        while (it != indices.end() and ans_tree[*it/2] == s) {
            it++;
        }

        if (it == indices.end()) {
            cout << "No\n";
            return 0;
        }

        auto elem = *it;
        prev_S = s;
        prev_elem = elem;
        indices.erase(it);
        ans_tree[elem] = s;
        elem <<= 1;
        while (elem < (1 << (N + 1))) {
            ans_tree[elem] = s;
            indices.insert(elem + 1);
            elem <<= 1;
        }
        /* for (auto e: indices) {
            cout << (e) << ' ';
        }
        cout << '\n'; */
    }
    
    

    cout << "Yes\n";

    return 0;
}

Measured memory_bytes: 15676
from collections import deque
N, K = map(int,input().split())
V = list(map(int,input().split()))

ans = []
for i in range(min(N,K)+1):
  for j in range(min(N,K)+1-i):
    Vc = deque(V.copy())
    cal = deque([0])
    for k in range(i):
      cal.append(Vc.popleft())
    for l in range(j):
      cal.append(Vc.pop())
    cal = deque(sorted(cal))
    for m in range(K-i-j):
      if cal[0] < 0:
        cal.popleft()
      else:
        break
    ans.append(sum(cal))

print(max(ans))


Measured memory_bytes: 3436
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;
const int INF = 1001001001;

int main(){
    
    int n; cin>>n;
    cout << (n/2)*((n+1)/2) << endl;
    
    return 0;
}

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

int root(int x, vector<int> &par){
        return par.at(x)==x ? x : par.at(x) = root(par.at(x),par);
}

int unite(int x, int y, vector<int> &par, vector<int> &rank){
        x = root(x,par);
        y = root(y,par);
        if(x==y) return -1;
        if(rank.at(x)<rank.at(y)){
                par.at(x) = y;
                rank.at(y) += rank.at(x);
                return rank.at(y);
        }else{
                par.at(y) = x;
                rank.at(x) += rank.at(y);
                return rank.at(x);
        }
}

int main(){
        int n,m,i,a,b,nodes=1;
        cin >> n >> m;
        vector<int> par(n);
        for(i=0;i<n;++i) par.at(i) = i;
        vector<int> rank(n,1);
        for(i=0;i<m;++i){
                cin >> a >> b;
                --a; --b;
                nodes = max(nodes, unite(a,b,par,rank));
        }
        cout << nodes << endl;
        return 0;
}

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

using namespace std;

using ll = __int128_t;
using ld = long double;
using ull = unsigned long long;

const int LEN = 18;


vector<int> td(ll x) {
    vector<int> ans;
    for (int i = 0; i < LEN; i++) {
        ans.push_back(x % 10);
        x /= 10;
    }
    return vector<int>(ans.rbegin(), ans.rend());
}

int d[LEN];

ll brute(const vector<int>& a, int sm, int pos, bool fl) {
    if (pos == LEN && sm == 0) {
        ll ans = 0;
        for (int i = 0; i < LEN; i++) {
            ans = 10 * ans + d[i];
        }
        return ans;
    }
    if (sm < 0) {
        return -1;
    }
    if (sm > 9 * (LEN - pos)) {
        return -1;
    }
    int l = 0;
    if (!fl) {
        l = a[pos];
    }
    for (int cd = l; cd < 10; cd++) {
        d[pos] = cd;
        bool gfl = fl;
        if (cd != a[pos]) {
            gfl = true;
        }
        ll go = brute(a, sm - cd, pos + 1, gfl);
        if (go != -1) {
            return go;
        }
    }
    return -1;
}

ll solve(ll x, int sm) {
    auto dc = td(x);
    return brute(dc, sm, 0, false);
}

int sm(ll x) {
    int res = 0;
    while (x) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

bool ok(ll x, ll y) {
    return x * sm(y) <= y * sm(x);
}

bool better(ll x, ll y) {
    ll xx = x * sm(y), yy = y * sm(x);
    if (xx < yy) return true;
    if (xx > yy) return false;
    return xx < yy;
}
const ll LIM = 1e16 + 42;
const int MD = 9 * 30;
int main() {
#ifdef BZ
    freopen("in", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    vector<ll> go;
    ll last = 0;
    while (last < LIM) {
        last++;
        vector<ll> cands;
        for (int sm = 1; sm < MD; sm++) {
            ll x = solve(last, sm);
            if (x == -1) {
                continue;
            }
            cands.push_back(x);
        }
        ll nxt = cands[0];
        for (ll x : cands) {
            if (better(x, nxt)) {
                nxt = x;
            }
        }
        go.push_back(nxt);
        if (go.size() == 662) {
            int x = 1234;
        }
        last = go.back();
    }
    go.pop_back();
    for (int i = 0; i < go.size(); i++) {
        for (int j = i + 1; j < go.size(); j++) {
            assert(ok(go[i], go[j]));
        }
    }
    int k;
    cin >> k;
    for (int i = 0; i < min(k, int(go.size())); i++) {
        cout << (long long)(go[i]) << "\n";
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<cmath>
int main(){
	int w,a,b;
	scanf("%d %d %d",&w,&a,&b);
	if(b-a<w&&b-a>-w){
		printf("%d\n",0);
	}
	else if(b-a>=w){
		printf("%d\n",b-a-w);
	}
	else{
		printf("%d\n",a-b-w);
	}
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}
template<class A,size_t N,class T>void Fill(A(&a)[N],const T&v){fill((T*)a,(T*)(a+N),v);}

const int MOD = 1e9+7; //998244353;

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m=MOD){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m=MOD){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>Fac,Rac;void setF(int n,int m=MOD){Fac=Rac=V<ll>(++n);Fac[0]=1;FOR(i,1,n)Fac[i]=Fac[i-1]*i%m;Rac[n-1]=modInv(Fac[n-1],m);FORR(i,n-1,1)Rac[i-1]=Rac[i]*i%m;}
//ll comb(int a,int b,int m=MOD){return a<b||b<0?0:Fac[a]*Rac[b]%m*Rac[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int N = 2e5;
const double PI = acos(-1);
int n, c;
char alf[10]={'a','b','c','d','e','f','g','h','i','j'};
V<char> v;
void f(int d){
  if(d==n){
    for(char cc:v) cout << cc;
    cout << endl;
    return;
  }
  FOR(i, 0, c){
    v.pb(alf[i]);
    f(d+1);
    v.pop_back();
  }
  v.pb(alf[c]);
  c++;
  f(d+1);
  c--;
  v.pop_back();
}
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  f(0);
}

Measured memory_bytes: 3608
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

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

    cout << (x-a)%b << endl;
    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const int mod = 1000000007;
const int inf = 1ll << 61;
typedef pair<int, int> P;
typedef pair<int, P>PP;

vector<int>G[100006];
int al[100006], au[100006];
int des[100006],dis[100006];
void dfs1(int now, int par) {
	rep(i, G[now].size()) {
		int e = G[now][i];
		if (e == par)continue;
		al[e] = max(al[e], al[now]-1);
		au[e] = min(au[e], au[now]+1);
		dis[e] = dis[now] + 1;
		dfs1(e, now);
	}
	return;
}

void dfs2(int now, int par) {
	rep(i, G[now].size()) {
		int e = G[now][i];
		if (e == par)continue;
		dfs2(e, now);
	}
	for (auto c : G[now]) {
		if (c == par)continue;
		al[now] = max(al[now], al[c]-1);
		au[now] = min(au[now], au[c]+1);
	}
}

signed main() {
	int n; cin >> n;
	rep(i, n-1) {
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int k; cin >> k;
	rep(i, n) {
		al[i] = -inf; au[i] = inf; des[i] = -1;
	}
	rep(i, k) {
		int v, p; cin >> v >> p;
		v--;
		al[v] = p; au[v] = p; des[v] = p;
	}
	dfs1(0, -1);

	int isok[2][2] = { { 0,0 },{0,0} };
	rep(i, n) {
		if (des[i] >= 0) {
			int p1 = dis[i] & 1, p2 = des[i] & 1;
			isok[p1][p2]++;
		}
	}

	if ((isok[0][0] && isok[0][1]) || (isok[1][0] && isok[1][1])||(isok[0][0]&&isok[1][0])||(isok[0][1]&&isok[1][1])) {
		cout << "No" << endl; return 0;
	}
	
	dfs2(0, -1);
	
	rep(i, n) {
		if (au[i] < al[i]) {
			cout << "No" << endl; return 0;
		}
	}
	au[0] = al[0];
	dfs1(0, -1);
	cout << "Yes" << endl;
	rep(i, n)cout << al[i]<< endl;
}


Measured memory_bytes: 14208
#define PI 3.14159265

#include <stdio.h>
#include <math.h>

int main(void) {

	double a, b, c, C;
	double S, L, h;

	scanf("%lf %lf %lf", &a, &b, &C);

	S = 0.5 * a * b * sin(C * PI / 180);

	c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(C * PI / 180));
	L = a + b + c;

	h = S / a * 2;

	printf("%f\n%f\n%f\n", S, L, h);
	
	return 0;
}

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

int main() {
  int ans = 0;
  int n, l, r;
  cin >> n;

  rep (i, n) {
    cin >> l >> r;
    ans += (r - l + 1);
  }
  cout << ans << endl;
  return 0;
}



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

int main() {
  int n;
  cin >> n;
  map<string, int> mp;
  rep(i,n){
    string s;
    cin >> s;
    mp[s]++;
  }
  int m;
  cin >> m;
  rep(i,m){
    string t;
    cin >> t;
    mp[t]--;
  }
  int mx = 0;
  for(auto p : mp) mx = max(mx,p.second);
  cout << mx << endl;
  return 0;
}

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

int main(){
    int n; cin >> n;
    double a[n], sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    double mi = 100,ave = sum/n;
    int ind;
    for(int i = 0; i < n; i++){
        if(mi > abs(a[i]-ave)){
            mi = abs(a[i]-ave); ind = i;
        }
    }
    cout << ind <<endl;
    return 0;
}

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


int main() {
    int N,Q; std::cin >> N >> Q;
    std::string S; std::cin >> S;
    std::vector<int> counts(N, 0);
    std::vector<int> ans(Q);
    int count = 0;
    for (int i = 0; i < N - 1; ++i) {
        if (S[i] == 'A' && S[i + 1] == 'C')counts[i + 1] = ++count;
        else counts[i + 1] = count;
    }
    for (int i = 0; i < Q; ++i) {
        int l, r; std::cin >> l >> r;
        ans[i] = counts[r - 1] - counts[l - 1];
    }
    for (auto& v : ans)std::cout << v << std::endl;
}

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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

typedef long long ll;

int main(){
  ll a, b, n; cin >> a >> b >> n;
  ll x = min(n, b-1);
  cout << a*x/b - a*(x/b) << endl;
  return 0;
}

Measured memory_bytes: 3624
#include<iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
#include <functional>
#include <set> 

using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)

signed main()
{
	int dog, monkey;
	cin >> dog >> monkey;
	int s = abs(dog - monkey);
	int res = 1;
	if (s >= 2) res = 0;
	else  {
		for (int i = dog; i > 0; i--) { res *= i;  res = res % 1000000007; }
		for (int i = monkey; i > 0; i--) { res *= i;  res = res % 1000000007; }
		if (s == 0) res *= 2;
		res = res % 1000000007;
	}
	cout << res << endl;
}

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

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

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

	for (int i=1;i<=k;i++) printf("%lld ",s);
	for (int i=k+1;i<=n;i++) printf("%lld ",(s==1e9)?s-1:s+1);
  return 0;
}


Measured memory_bytes: 1280
#include <stdio.h> 
using namespace std;
 long long Fibonacci[43] = {0};
 long long fibo(int n){ 
if(n == 0) return 1;
 else if(n == 1) return 1; 
else{ if(Fibonacci[n-1] != 0 && Fibonacci[n-2] != 0){ 
//Do nothing }else if(Fibonacci[n-1] != 0){
 Fibonacci[n-2] = fibo(n-2); 
}
else if(Fibonacci[n-2] != 0){ 
Fibonacci[n-1] = fibo(n-1);
 }
else{ Fibonacci[n-1] = fibo(n-1);
 Fibonacci[n-2] = fibo(n-2); 
} 
return Fibonacci[n-1] + Fibonacci[n-2]; 
}
 } 

int main(){ int n; 
scanf("%d",&n);
 printf("%lld\n",fibo(n));

 } 


Measured memory_bytes: 2756
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
            String strSplit[] = br.readLine().split(" ");
            int N = Integer.parseInt(strSplit[0]);
            int K = Integer.parseInt(strSplit[1]);
            
            String strSplitFruitsPrice[] = br.readLine().split(" ");
            int fruitsPrice[] = new int[N];
            for(int i=0; i<N; i++){
                fruitsPrice[i] = Integer.parseInt(strSplitFruitsPrice[i]);
            }
            
            Arrays.sort(fruitsPrice);
            
            int ans = 0;
            
            for(int i=0; i<K; i++){
                ans = ans + fruitsPrice[i];
            }
            
            System.out.println(ans);
            
        }catch(Exception e){
            System.out.println(e);
        }
    }
}

Measured memory_bytes: 32820
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    vec<int> cnt(N);
    for(int i=0;i<K;i++){
        int d;
        cin >> d;
        while(d--){
            int a;
            cin >> a;
            a--;
            cnt[a]++;
        }
    }
    cout << count(cnt.begin(),cnt.end(),0) << "\n";
}

Measured memory_bytes: 3656