akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }

const int MAX = 5100000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
   fac[0] = fac[1] = 1;
   finv[0] = finv[1] = 1;
   inv[1] = 1;
   for (int i = 2; i < MAX; i++){
       fac[i] = fac[i - 1] * i % MOD;
       inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
       finv[i] = finv[i - 1] * inv[i] % MOD;
   }
}

// 二項係数計算
long long COM(int n, int k){
   if (n < k) return 0;
   if (n < 0 || k < 0) return 0;
   return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(int argc, char const *argv[]) {
  ll x,y;
  COMinit();
  cin >> x >> y;
  ll k=(2*y-x)/3,l=(2*x-y)/3;
  if((2*x-y)%3!=0 || (2*y-x)%3!=0) {
    cout << "0" << endl;
    return 0;
  }
  cout << COM(k+l,l)%MOD << endl;

  return 0;
}


Measured memory_bytes: 119808
#include<bits/stdc++.h>
using namespace std;
int main()
{
  float i,j,k,h,w,n;
  cin>>h>>w>>n;
    if((float)(n/max(h,w))==(int)(n/max(h,w)))
     {
       cout<<(int)(n/max(h,w));
     }
     else
     {
      cout<<(int)(n/max(h,w)) +1; 
     }
}

Measured memory_bytes: 256
x1, y1, x2, y2 = map(int,input().split())
x3 = x2 + (y1-y2)
y3 = y2 - (x1-x2)
x4 = x3 + (y2-y3)
y4 = y3 - (x2-x3)
print(x3,y3,x4,y4)


Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18; 
const int MAXN=5e3+10;
ll a[MAXN];
int n,x,y;
vector<ll>dp1[MAXN],dp0[MAXN],e[MAXN];
void pr(int x)
{
	cout << x << endl;
	exit(0);
}
void merge(int now,int u){
	vector<ll>q1,q0;
	for (int i=0;i<dp1[now].size()+dp1[u].size();i++) 
	{
		q1.push_back(inf); q0.push_back(-1);
	}
	for (int i=0;i<dp1[now].size();i++) {
		for (int j=0;j<dp1[u].size();j++) {
                   q1[i+j]=min(q1[i+j],dp1[now][i]+dp1[u][j]);
                   if (dp1[u][j]<0||dp0[u][j]==1) q1[i+j+1]=min(q1[i+j+1],dp1[now][i]);
                   if (dp0[u][j]!=-1&&dp0[now][i]!=-1) q0[i+j]=1;
                   if (dp1[u][j]<0||dp0[u][j]==1) if (dp0[now][i]!=-1) q0[i+j+1]=1;
		}
	}
	dp1[now]=q1; dp0[now]=q0;
}
void dfs(int now,int fa)
{ 
	dp1[now].push_back(a[now]);
	dp0[now].push_back(a[now]>0?1:-1);
	for (int i=0;i<e[now].size();i++) {
		int u=e[now][i];
		if (u==fa) continue;
		dfs(u,now);
		merge(now,u);
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
		for (int i=1;i<n;i++) {
			scanf("%d%d",&x,&y); e[x].push_back(y); e[y].push_back(x);
		}
	dfs(1,0);
	// cout << dp0[1][1] << endl;
	for (int i=0;i<=n;i++)
	 {
	 	if (dp0[1][i]>0) pr(i);
	 	if (dp1[1][i]<0) pr(i);
	 } 
}


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

int main(){
  int n,m,x;
  cin>>n>>m>>x;
  vector<int> c(n);
  vector<vector<int>> a(n, vector<int>(m));
  rep(i,n){
    cin>>c[i];
    rep(j,m){
      cin>>a[i][j];
    }
  }

  ll min=INF;

  for (int bit = 0; bit < (1<<n); ++bit) {
    vector<int> S;
    for (int i = 0; i < n; ++i) {
        if (bit & (1<<i)) { // 列挙に i が含まれるか
            S.push_back(i);
        }
    }

    int cnt=0;
    rep(i,m){
      int sum = 0;
      rep(j,(int)S.size()){
        sum+= a[S[j]][i];
      }
      if(sum>=x){
        cnt++;
      }
    }
    if(cnt==m){
      int sum_c=0;
      rep(i,(int)S.size()){
        sum_c+=c[S[i]];
      }
      if(sum_c<min){
        min = sum_c;
      }

    }
  }
  if(min==INF){
    cout<<"-1"<<endl;
  }else{
    cout<<min<<endl;
  }
  
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)



int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    string s;
    cin >> s;

    ll ans = 0;
    int c = 0;
    s = '0' + s;
    FORI(i, s.length()){
        s[i] += c;
        if (s[i] > '9'){
            s[i] = '0';
            c = 1;
        }
        else
            c = 0;
        if (s[i] > '5' || (s[i] == '5' && s[i-1] >= '5')){
            ans += '9' - s[i] + 1;
            s[i] = '0';
            c = 1;
        }
        else{
            ans += s[i] - '0';
        }
    }
//    cout << s << endl;
    ans += c;
    cout << ans << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 2332
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def SCC(N, edges):
    """ 強連結成分分解 """

    nodes1 = [[] for i in range(N)]
    nodes2 = [[] for i in range(N)]
    for u, v in edges:
        nodes1[u].append(v)
        nodes2[v].append(u)

    T = []
    visited = [False] * N
    def rec1(cur):
        visited[cur] = True
        for nxt in nodes1[cur]:
            if not visited[nxt]:
                rec1(nxt)
        # 行き止まったところから順にTに入れていく
        T.append(cur)

    # グラフが連結とは限らないので全頂点やる
    for u in range(N):
        if not visited[u]:
            rec1(u)

    visited = [False] * N
    group = [0] * N
    grpcnt = 0
    def rec2(cur):
        group[cur] = grpcnt
        visited[cur] = True
        for nxt in nodes2[cur]:
            if not visited[nxt]:
                rec2(nxt)

    # 逆順で進めるところまで行く
    for u in reversed(T):
        if not visited[u]:
            rec2(u)
            grpcnt += 1
    return grpcnt, group

def bfs(N, nodes, src):
    """ BFS(一般グラフ、重みなし) """
    from collections import deque

    que = deque([(src, -1, 0)])
    dist = [()] * N
    mn = INF
    end = -1
    while que:
        u, prev, c = que.popleft()
        # 同じ強連結成分内のみでやる
        if group[u] != group[src]:
            continue
        if dist[u]:
            # 訪問済で始点に帰ってきたら、最短チェック
            if u == src:
                if c < mn:
                    mn = c
                    end = prev
            continue
        dist[u] = (c, prev)
        for v in nodes[u]:
            que.append((v, u, c+1))
    # 経路、始点に戻ってくる最短距離、その直前の頂点を返す
    return dist, mn, end

def get_route(s, t, res):
    """ s,t間の経路を取得 """
    prev = t
    StoT = [t]
    while prev != s:
        prev = res[prev][1]
        if prev == -1:
            return None
        StoT.append(prev)
    StoT = StoT[::-1]
    return StoT

N, M = MAP()
nodes = [[] for i in range(N)]
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    edges.append((a, b))

# 強連結成分毎に見る
grpcnt, group = SCC(N, edges)
ans = INF
for i in range(N):
    # 経路、始点に戻ってくる最短距離、その直前の頂点
    dist, mn, end = bfs(N, nodes, i)
    if mn < ans:
        ans = mn
        route = get_route(i, end, dist)
if ans != INF:
    print(ans)
    [print(u + 1) for u in route]
else:
    # そもそも閉路なし
    print(-1)


Measured memory_bytes: 4852
#include <iostream>
#include<math.h>
using namespace std;
#define INF 1000000009
#define ll long long 
int main()
{
    ll int n,cap;
    cin>>n>>cap;
    ll int weight[n+1],value[n+1],total=0,ans=0;
    for(ll int i=1;i<=n;i++){
        cin>>weight[i]>>value[i];
        total+=value[i];
    }
    ll int dp[n+1][total+1];
    for(ll int i=0;i<=n;i++){
        dp[i][0]=INF;
    }
    for(ll int i=0;i<=total;i++){
        dp[0][i]=INF;
        if(value[1]>=i&&i){
            dp[1][i]=weight[1];
        }
        else{
            dp[1][i]=INF;
        }
    }
    for(ll int i=2;i<=n;i++){
        for(ll int j=1;j<=total;j++){
            if(value[i]>=j){
                dp[i][j]=min(weight[i],dp[i-1][j]);
            }
            else{
                dp[i][j]=min(dp[i-1][j],weight[i]+dp[i-1][j-value[i]]);
            }
        }
    }
    /*for(int i=0;i<=n;i++){
        for(int j=0;j<=total;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    for(ll int i=0;i<=total;i++){
        if(dp[n][i]<=cap){
            ans=i;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 79104
# https://atcoder.jp/contests/abs/tasks/abc085_c



N, Y = gets.split.map(&:to_i)

# 最小枚数となる組み合わせ
x_max = Y / 10000
(0..x_max).each do |x|
  y_max = (Y - 10000 * x) / 5000
  (0..y_max).each do |y|
    z = N - x - y
    break if z < 0

    if 10000 * x + 5000 * y + 1000 * z == Y
      puts "#{x} #{y} #{z}"
      exit
    end
  end
end

puts '-1 -1 -1'


Measured memory_bytes: 1788
#include"bits/stdc++.h"
using namespace std;
int main(){
  int n,h,b=0;
  cin >> h >> n;
  for(int i=0;i<n;i++){
    int s;cin >> s;
    b+=s;
  }
  if(b<h){cout << "No" << endl;
         }
  else cout << "Yes" << endl;
}
    


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<vector>
#define N 201
vector<int>G[N];
int n,m,low[N],dfn[N];
bool is_cut[N];
int father[N];
int tim=0;
void input()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);/*邻接表储存无向边*/
        G[b].push_back(a);
    }
}
void Tarjan(int i,int Father)
{
    father[i]=Father;/*记录每一个点的父亲*/
    dfn[i]=low[i]=tim++;
    for(int j=0;j<G[i].size();++j)
    {
        int k=G[i][j];
        if(dfn[k]==-1)
        {
            Tarjan(k,i);
            low[i]=min(low[i],low[k]);
        }
        else if(Father!=k)/*假如k是i的父亲的话，那么这就是无向边中的重边，有重边那么一定不是桥*/
            low[i]=min(low[i],dfn[k]);//dfn[k]可能！=low[k]，所以不能用low[k]代替dfn[k],否则会上翻过头了。
    }
}
void count()
{
    int rootson=0;
    Tarjan(1,0);
    for(int i=2;i<=n;++i)
    {
        int v=father[i];
        if(v==1)
        rootson++;/*统计根节点子树的个数，根节点的子树个数>=2,就是割点*/
        else{
            if(low[i]>=dfn[v])/*割点的条件*/
            is_cut[v]=true;
        }
    }
    if(rootson>1)
    is_cut[1]=true;
    int tte=0;
    for(int i=1;i<=n;++i)
    {
        int v=father[i];
        if(v>0&&low[i]>dfn[v])/*桥的条件*/
        tte++;
    }
    cout<<tte;
}
int main()
{
    input();
    memset(dfn,-1,sizeof(dfn));
    memset(father,0,sizeof(father));
    memset(low,-1,sizeof(low));
    memset(is_cut,false,sizeof(is_cut));
    count();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<ll>> vvll;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = 1; i <= (n); ++i)
#define irep(it, stl) for (auto it = stl.begin(); it != stl.end(); it++)
#define drep(i, n) for (ll i = (n)-1; i >= 0; --i)
#define mes(a) cout << (a) << endl
#define dmes(a, b) cout << (a) << " " << (b) << endl
#define re0 return 0
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define rSort(a) sort(a.rbegin(), a.rend())
#define Rev(a) reverse(a.begin(), a.end())
#define MATHPI acos(-1)
#define itn int
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
struct io
{
    io()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
};
const int INF = INT_MAX;
const ll LLINF = 1LL << 60;
const ll MOD = 1000000007;
const double EPS = 1e-19;

signed main() {
    ll n;
    cin >> n;
    
   
    mes(1-n);
}
    
    
    
    
    

Measured memory_bytes: 3628
#include <iostream>

using namespace std;

int main()
{
  //  cout << "Hello world!" << endl;
    int X,A,B;
    cin>>X>>A>>B;
    if(X>A)
    {
        A=X-A;
    }
    else
    {
        A=A-X;
    }

    if(X>B)
    {
        B=X-B;
    }
    else
    {
        B=B-X;
    }

    if(A>B)
        cout<<"B"<<endl;
    else
        cout<<"A"<<endl;

    return 0;
}


Measured memory_bytes: 256
import numpy as np

N = input()
N = int(N)
stN = str(N)
count = 0
if(len(stN)==6):
    count = 90909
elif(len(stN)==5):
    count = (N-10000+1)+909
elif(len(stN)==4):
    count = 909
elif(len(stN)==3):
    count = (N-100+1)+9
elif(len(stN)==2):
    count = 9
else:
    count = N
print(count)

Measured memory_bytes: 21512
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

int main() {
  ll x; cin >> x;
  vector<ll> A;
  loop(i,0,200) {
    ll f = i;
    ll y = 1;
    loop(j,0,5) y*=f;
    if (y > 200000000000) break;
    A.push_back(y);
  }
  
  int n = A.size();
  vector<ll> signs { -1, 1 };
  loop(i,0,n) {
    loop(j,0,n) {
      for (auto &&signA: signs) {
        for (auto &&signB: signs) {
          if (signA*A[i]-A[j]*signB == x) {
            cout << signA*i << " " << signB*j << endl;
            return 0;
          }
        }
      }
    }
  }
  assert(x == 0);
  return 0;
}


Measured memory_bytes: 3636
N = int(input())
a = list(map(int,input().split()))
import copy
b = copy.copy(a)
ave = (sum(a) // N) + 1
ave2 = sum(a) // N
for i in range(N):
    a[i] = (a[i] - ave)**2
for i in range(N):
    b[i] = (b[i] - ave2)**2
print(min(sum(a),sum(b)))

Measured memory_bytes: 3444
N, M = map(int, input().split())

d = {}
ans = [0, 0]

for i in range(M):
  p, s = input().split()
  r = d.get(p, 0)
  if r == 'AC':
    pass
  else:
    if s == 'AC':
      ans[0] += 1
      d[p] = 'AC'
    else:
      ans[1] += 1
      d[p] = r + 1

for key, value in d.items():
  if value != 'AC':
    ans[1] -= value

print(*ans)


Measured memory_bytes: 17120
#include <iostream>
#include <vector>

using namespace std;

void solve()
{
	int n, p;
	while(cin >> n >> p)
	{
		if(!n && !p)
		{
			break;
		}
		vector<int> Vec(n);
		int stone = p;
		int count = 0;
		while(true)
		{
			if(stone)
			{
				Vec[count]++;
				stone--;
				if(Vec[count] == p)
				{
					cout << count << endl;
					break;
				}
			}
			else
			{
				stone = Vec[count];
				Vec[count] = 0;
			}
			count++;
			count %= n;
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 0
#include<stdio.h>

int main(void){
   int a,b,c;
   
   scanf("%d %d %d",&a,&b,&c);
   int MAX =a;
   if(b>MAX)
     MAX = b; 
   if(c>MAX) 
     MAX=c;
   printf("%d\n",a+b+c-MAX);
   return 0;
}  

Measured memory_bytes: 128
def main():
    n = int(input())
    cs = input()
    color_list = []
    for i in range(n):
        if cs[i] == "W":
            color_list.append(0)
        else:
            color_list.append(1)
    r_count = sum(color_list)
    ans = r_count - sum(color_list[:r_count])
    print(ans)


if __name__ == "__main__":
    main()


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

int main(){
    int N, BS = 0, AS = 0;
    cin >> N;
    vector<int> a(N);
    for(int i = 0;i < N;i++){
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for(int i = 0;i < N;i++){
        if(i % 2 == 0)AS += a.at(i);
        else BS += a.at(i);
    }
    cout << AS - BS << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
	int n;
	scanf(" %d", &n);
	for(int i=0; i<n;++i){
		long s;
		scanf(" %ld", &s);
		
		printf("Case %d:\n", i+1);
		
		for(int j=0; j<10; ++j){
			s=s*s;
			
			int a[8];
			for(int k=0; k<8; ++k) a[k]=s%(long)pow(10,8-k) / (long)pow(10, 7-k);
			
			s=0;
			for(int k=2; k<6; ++k) s+=a[k]*pow(10,5-k);
			
			printf("%ld\n", s);
		}
	}
	return 0;
}

Measured memory_bytes: 1232
# 解説
def solve():
    n = int(input())
    a = tuple(map(int, input().split()))

    # n匹全体でA色とする
    # aloneな猫: a_i = A-1
    # 同色がいる猫: a_i = A

    M = max(a)
    m = min(a)

    delta = M - m
    # 最大値と最小値の差

    if delta > 1:
        return False
        # 各猫視点の色数の差は2以上にはならない
    elif delta == 1:
        # alone,同色ありが混在
        # aloneな猫: a_i = A-1
        # 同色がいる猫: a_i = A

        x = a.count(m)
        # alone猫数,この猫だけでx色ある

        y = n - x
        # 同色いる猫数
        # 最低1色、最大でy//2色（2匹ずつに分けて、端数はどこかのグループに入れる）

        if x >= M:
            return False
            # x + y//2 = A
            # x = A - y//2 < A

        if (y - (M - x) * 2) not in {0, 1}:
            return False
            # x + y//2 = A
            # y//2 = A - x
            # y = (A - x) * 2 or (A - x) * 2 + 1

        return True

    else:
        # if delta == 0
        if all(a_ == n - 1 for a_ in a):
            return True
            # 全員alone=A-1=n-1

        if all(a_ * 2 <= n for a_ in a):
            return True
            # 全員同色がいる=A
            # ooxxzz -> A=3: 色の総数は各グループが2匹以上なので、A*2<=n
            # oooxxx -> A=2

        return False

    return True


print('Yes' if solve() else 'No')


Measured memory_bytes: 54212
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<math.h>
#define INF ((1<<30)-1+(1<<30))
#define EPS 1.0e-6

using namespace std;

typedef long long ll;

int n,q;
int m[420000];

int init(int n)
{
	int k = 1;
	while (k < n) {
		k *= 2;
	}
	for (int i = 0; i < 2 * k; i++) {
		m[i] = INF;
	}
	return k;
}

//[l,r)???x?????´??°??????.[bottom,top),node??????????????????
void update(int x, int l, int r, int bottom = 0, int top = n, int node = 1)
{
	if (l <= bottom&&top <= r) {
		m[node] = x;
		return;
	}
	
	if (top <= l || r <= bottom)return;

	int mid = (bottom + top) / 2;

	//-INF???????????????????????¨?????????????????????????????¨?????¨???
	if (m[node] != -INF) {
		m[2 * node] = m[node];
		m[2 * node + 1] = m[node];
		m[node] = -INF;
	}
	update(x, l, r, bottom, mid, 2 * node);
	update(x, l, r, mid, top, 2 * node + 1);
}

int find(int i, int bottom = 0,int top=n,int node=1) {
	if (i < bottom || top <= i)return -INF;
	if (m[node] != -INF)return m[node];
	
	int mid = (bottom + top) / 2;
	int l = find(i, bottom, mid, 2 * node);
	int r = find(i, mid, top, 2 * node + 1);
	return max(l, r);
}

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

	n=init(n);

	int a, s, t, x, k;
	for (int i = 0; i < q; i++) {
		cin >> a;
		if (a == 0) {
			cin >> s >> t >> x;
			update(x, s, t + 1);
		}
		if (a == 1) {
			cin >> k;
			cout << find(k) << endl;
		}
	}

	return 0;
}

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

int main(){
	ll n,m;
	scanf("%lld %lld",&n,&m);
	vector<ll> h(n);
	for(int i =0; i< n; i++){
		scanf("%lld",&h[i]);
	}
	vector<ll> data[n];
	for(ll i = 0; i < m; i++){
		ll a,b;
		scanf("%lld %lld",&a,&b);
		data[a-1].push_back(b-1);
		data[b-1].push_back(a-1);
	}
	ll ans =0;
	for(ll i=0;i<n;i++){
		ll h_max = 0;
		for(ll j=0;j<data[i].size();j++){
			h_max = max(h_max,h[data[i][j]]);
		}
		if(h_max < h[i]) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 9860
N,K,Q=map(int,input().split())
Al=[int(input()) for i in range(Q)]
Kl=[K]*N
for p in range(0,Q):
    Kl[Al[p]-1]=Kl[Al[p]-1]+1
    
for q in range(0,N):
    Kl[q]=Kl[q]-Q
for r in range(0,N):
    if Kl[r]<=0:
        print("No")
    else:
        print("Yes")



Measured memory_bytes: 11796
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll A, B, K;
  cin>>A>>B>>K;
  if(K<=A){
    A -= K;
  }else if(K<=A+B){
    B -= (K-A);
    A = 0;
  }else{
    A = B = 0;
  }

  cout<<A<<" "<<B<<endl;
}

Measured memory_bytes: 256
import sys
N,M = map(int,input().split())
A,B = [],[]
for i in range(N):
    A.append(input())
for i in range(M):
    B.append(input())
for i in range(N-M+1):
    for j in range(N-M+1):
        check = True
        for di in range(M):
            for dj in range(M):
                if A[i+di][j+dj] != B[di][dj]:
                    check = False
        if check:
            print("Yes")
            sys.exit()
else:
    print("No")


Measured memory_bytes: 3064
/**
 *    SATAR ALLAH
 *
**/
#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()


int go(int A,int B){


     int a=0,b=0;

      while(A){

         a+=A%10;
         A/=10;
      }

      while(B){

         b+=B%10;
         B/=10;
      }

      return a+b;


 }
int main()
{

    int n;


      cin>>n;


     int ans=10000;
       for(int i=1;i<n;i++){


            ans=min(ans,go(i,n-i));
       }

       cout<<ans;

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }


signed main()
{
    int N, D;
    cin >> N >> D;

    int ans = 0;
    REP(i, N)
    {
        int x, y;
        cin >> x >> y;
        double d = x * x + y * y;
        if (D * D >= d)
        {
            ans++;
        }
    }
    cout << ans << endl;

}

 

Measured memory_bytes: 3196
N,MOD = map(int,input().split())
A = list(map(int,input().split()))

ODD = 0
EVEN = 0

for i in range(N):
    if A[i]%2==0:
        EVEN += 1
    else:
        ODD += 1

P = [1]

for i in range(ODD):
    P.append(P[-1]*(i+1))

ans = 0

for i in range(ODD+1):
    if i%2 == MOD:
        ans += P[ODD]//(P[i]*P[ODD-i])

print(2**EVEN*ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ut i=(a);i<(ut)(b);i++)
#define REP(i,b) FOR(i,0,b)
#define ALL(c) c.begin(),c.end()
#define PB push_back
#define cat //cout << __LINE__ << endl;
using namespace std;
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef pair<ut,ut> pr;
typedef pair<ut,pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr,Vpr,greater<pr> > PQ;
const ut INF=1LL<<30;
const int SIZE=5+1e5;
VI nums;
int N;
bool solve(){
	if(N>=3 && nums[0]==nums[1] && nums[1]==nums[2]) return false;
	int minium=nums[0],maxim=nums.back();
	int multiN=1+(nums[0]==nums[1]);
	int multi=minium;
	REP(i,N-1){
		if(abs(nums[i]-nums[i+1])>1) return false;
		if(nums[i]==nums[i+1] && nums[i]==multi+1) multi++;
	}
	if(multi!=maxim) return false;
	if(multiN==1 && minium*2==maxim) return true;
	if(multiN==2 && minium*2-1==maxim) return true;
	return false;
}
int main(){
	cin >> N;
	nums=VI(N);
	REP(i,N) cin >> nums[i];
	sort(ALL(nums));
	if(solve())
		cout <<"Possible" << endl;
	else
		cout <<"Impossible" << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main{
    static MyReader in = new MyReader();

    public static void main(String[] args){
        long N, K; {long[] a = in.ll(); N = a[0]; K = a[1];}
        
        out.println(Math.min(N%K, K - N%K));
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        ArrayList<Integer> li(){
            String[] ss = ss();
            ArrayList<Integer> li = new ArrayList<>();
            for(int j = 0; j < ss.length; j++) li.add(Integer.parseInt(ss[j]));
            return li;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


Measured memory_bytes: 21076
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <math.h>
#include <map>
#define ll long long 
#define PI 3.14159265358979323846
#define INF 10000000000
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;

int main() {
	ll N, D;
	cin >> N >> D;
	ll ans = 0;
	vector<ll> X(N), Y(N);
	rep(i, N) {
		cin >> X[i] >> Y[i];
		ll dis = pow(X[i], 2) + pow(Y[i], 2);
		ll dd = pow(D, 2);
		if (dd >= dis) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 6372
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public long MOD = 1000000007;

        public void Run()
        {
            string L = Console.ReadLine();
            L = new string(L.Reverse().ToArray());
            // Console.WriteLine(L);

            long[] dp1 = new long[L.Length];
            long[] dp2 = new long[L.Length]; // 1111

            int N = L.Length;
            int last = -1;

            for (int i = 0; i < N; i++)
            {
                dp2[i] = i == 0 ? 3 : dp2[i - 1] * 3;
                dp2[i] %= MOD;

            }

            for (int i = 0; i < N; i++)
            {
                if (L[i] == '1')
                {
                    dp1[i] += (i == 0 ? 1 : dp2[i - 1]);
                    dp1[i] += (last < 0 ? 2 : 2 * dp1[last]);
                    dp1[i] %= MOD;
                    last = i;
                }
                else
                {
                    dp1[i] = 0;
                }
            }

            Console.WriteLine(dp1[N - 1]);
        }
    }

    // libs ----------
    

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 14432
N,W = map(int,input().split())
Data = []
Data.append([0,0])
for _ in range(N):
    Data.append(list(map(int,input().split())))
DP = [[0]*(W+1) for _ in range(N+1)]

#DP[n][w]: n番目までの品物で wグラムまでの重さを入れた場合の価値の最大
for n in range(1,N+1):
    for w in range(1,W+1):
        wi,vi = Data[n]
        if w >= wi:
            DP[n][w] = max(DP[n][w],DP[n-1][w-wi]+vi)
        DP[n][w] = max(DP[n][w],DP[n-1][w])

print(DP[N][W])

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

using ll = long long;
//typedef long long ll;

#define INF (1LL << 31 - 1)
#define INFLL ((1LL << 62) - 1)
#define MOD int(1e9+7)
#define repi(i,j,n) for(int i = (j); i < (n); ++i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) for (int i = n; i >= 0; --i)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()

int vx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, vy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

inline bool check(int ux, int uy, int x, int y) {
  return (0 <= x and x < ux and 0 <= y and y < uy);
}

inline void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int n, m, a, b, c;
int g[101][101], d[101][101];

int main() {
  init();
  cin >> n >> m;
  memset(d, 0x3f, sizeof d);
  memset(g, 0x3f, sizeof g);
  rep(i,n) d[i][i] = 0;
  rep(i,m) {
    cin >> a >> b >> c;
    a--, b--;
    g[a][b] = g[b][a] = c;
    d[a][b] = d[b][a] = c;
  }
  rep(k,n) rep(i,n) rep(j,n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

  int ans = 0;

  rep(i,n) {
    repi(j,i+1,n) {
      bool f = true;

      rep(k,n) {

        if (i != k and j != k and d[i][j] == d[i][k] + d[k][j] and g[i][j] != 0x3f3f3f3f and g[i][j] > d[i][j]) {
          f = false;
          break;
        }
      }

      if (!f) ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    string str;
    cin >> str;
    int n;
    cin >> n;
    rep(i, n)
    {
        int a, b;
        string cmd;
        cin >> cmd >> a >> b;

        if (cmd == "replace")
        {
            string p;
            cin >> p;
            str.replace(a, b - a + 1, p);
        }
        else if (cmd == "reverse")
        {
            reverse(str.begin() + a, str.begin() + b + 1);
        }
        else if (cmd == "print")
        {
            OP(str.substr(a, b - a + 1))
        }
    }
    return 0;
}


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

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

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main() {
    string s;
    int ans = 0;


    cin >> s;

    if (s == "SUN") ans = 7;
    if (s == "MON") ans = 6;
    if (s == "TUE") ans = 5;
    if (s == "WED") ans = 4;
    if (s == "THU") ans = 3;
    if (s == "FRI") ans = 2;
    if (s == "SAT") ans = 1;

    cout << ans << endl;
}

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

int n;
int k;

vector<int> v;
map<int, int> mp;
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		mp[a]++;
	}
	for (auto it = mp.begin(); it != mp.end(); it++) {
		v.push_back((*it).second);
	}
	int need = mp.size();
	need -= k;
	need = max(need, 0);
	int ans = 0;
	sort(v.begin(), v.end());
	for (auto it = v.begin(); it != v.end(); it++) {
		need--;
		if (need >= 0) {
			ans += (*it);
		}
		else {
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 10748
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void io(){ ios_base::sync_with_stdio(false);cin.tie(NULL);  cout.tie(NULL);}
ll m=1e9+7;
ll fact[200003];
ll inv[200003];
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void init()
{
    fact[0]=inv[0]=1;
    for(int i=1;i<200003;i++)
    {
        fact[i]=(fact[i-1]*i)%m;
        inv[i]=binpow(fact[i],m-2,m);
    }
}
ll ncr(ll n ,ll r)
{
    ll ans=fact[n];
    ans=(ans*inv[r])%m;
    ans=(ans*inv[n-r])%m;
    return ans;
}
int main()
{
    //io();
    ll tt;
    tt=1;
    cout<<fixed;
    while(tt--)
    {
        ll n,k;
        cin>>n>>k;n++;
        ll ans=0;
        for(ll i=k;i<=n;i++)
        {
            ll p=(i*(i+1))/2;
            ll q=(n*(n+1))/2 - ((n-i)*(n-i+1))/2;
           // cout<<q-p+1<<"\n";
            ans+=(q-p+1);
            ans%=m;
        }
        cout<<ans;
    }
}


Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(long long (i)=0, i_bound = (long long)(n); (i)<i_bound; ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;

struct point{
    int x, y;
    int d; 
};

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

int main(){
    cin.tie(0);
    cout.sync_with_stdio(false);
    ll H, W; cin >> H >> W;
    vector<string> G(H);
    REP(i, H) cin >> G[i];
    queue<point> q;
    int res = 0;
    vector<vector<int>> F(H, vector<int>(W, MOD));
    REP(i, H) REP(j, W) if(G[i][j]=='#')q.push((point){i, j, 0});
    while(q.size()){
        point p = q.front();
        q.pop();
        int x = p.x;
        int y = p.y;
        int d = p.d;
        if(F[x][y]<MOD) continue;
        F[x][y] = d;
        //cout << x << " " << y << " " << d << endl;
        res = max(res, d);
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 or nx >= H) continue;
            if(ny < 0 or ny >= W) continue;
            q.push((point) {nx, ny, d+1});
        }

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

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

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

const int MaxN = 1e5 + 10;
int n, v[MaxN];
map<int, int> cnt[2];
vector<pair<int, int>> x[2];

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        cnt[i & 1][v[i]]++;
    }

    for (int j : {0, 1}) {
        for (auto it : cnt[j]) x[j].push_back({-it.second, it.first});
        x[j].push_back({0, 0});
        sort(x[j].begin(), x[j].end());
    }

    if (x[0][0].second != x[1][0].second) cout << n + x[0][0].first + x[1][0].first;
    else cout << n + min(x[0][0].first + x[1][1].first, x[0][1].first + x[1][0].first);

    return 0;
}



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

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

  int total_votes = 0;
  vector<int> items;

  rep(i, n) {
    int a;
    cin >> a;
    total_votes += a;
    items.push_back(a);
  }

  sort(items.begin(), items.end(), greater<int>());

  double threshold = total_votes * (1.0 / (4 * m));

  if (items[m - 1] >= threshold) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 3616
#include<cstdio>
#define N 303
#define ll long long
int c[N][N],f[N][N],g[N][N],i,j,k,l,m,n;
inline int mod(int x){return x<m?x:x-m;}
int main()
{
    scanf("%d%d%d",&n,&l,&m);
    for(i=0;i<=l;i++)f[1][i]=1,g[1][i]=(l-i+1)%m;
    for(i=0;i<=n;i++)for(j=*c[i]=1;j<=i;j++)c[i][j]=mod(c[i-1][j-1]+c[i-1][j]);
    for(i=2;i<=n+1;i++)for(j=l;j--;g[i][j]=mod(g[i][j+1]+f[i][j]))for(k=1;k<i;k++)f[i][j]=(f[i][j]+(ll)f[i-k][j]*g[k][j+1]%m*c[i-2][k-1])%m;
    return 0&printf("%d\n",f[n+1][0]);
}

Measured memory_bytes: 1280
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
       return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

   fastread();

   ll i,j,n,m,p,a,k,t,b,c,d,cnt=0,q,l,r;

   double ans=0;

      bool flag=false;

      string str;


      long double sum=0;

      cin>>n>>k;


       for(i=1; i<=n; i++)
       {
           if(i>k)
           {
               sum+=n-i+1;
               break;


           }


           long double value=1.0;

           a=i;

           while(a<k)
           {
               a*=2;

               value/=2.0;


           }

           //cout<<value<<endl;

           sum+=value;
       }

       sum/=n;
      cout<<setprecision(12)<<fixed<<sum<<endl;















}



Measured memory_bytes: 3716
<?php
// Your code here!
    fscanf(STDIN,"%d %d %d",$a,$b,$c);
    // var_dump($a);
    $trima = $a;
    $a = $b;
    $b = $trima;
    // echo $a,$b,$c;
    $ti2 = $a;
    $a = $c;
    $c = $ti2;
    echo $a,' ',$b,' ',$c;
?>


Measured memory_bytes: 4732
MOD = 10 ** 9 + 7


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=lambda x: abs(x), reverse=True)

    res = 1

    if k == n:
        for e in a:
            res *= e
            res %= MOD
    elif max(a) < 0:
        if k % 2 == 1:
            for i in range(n - k, n):
                res *= a[i]
                res %= MOD
        else:
            for i in range(k):
                res *= a[i]
                res %= MOD
    else:
        plus_a = [e for e in a if e >= 0]
        minus_a = [e for e in a if e < 0]

        minus_cnt = min(k, len(minus_a))
        minus_cnt -= minus_cnt % 2
        plus_cnt = k - minus_cnt

        minus_a = minus_a[:minus_cnt]
        minus_a.reverse()

        max_change_cnt = min(minus_cnt, len(plus_a) - plus_cnt)
        max_change_cnt -= max_change_cnt % 2
        change_cnt = 0
        while change_cnt < max_change_cnt:
            if plus_a[plus_cnt + change_cnt] * plus_a[plus_cnt + change_cnt + 1]\
                    <= minus_a[change_cnt] * minus_a[change_cnt + 1]:
                break
            change_cnt += 2

        for i in range(change_cnt, minus_cnt):
            res *= minus_a[i]
            res %= MOD

        for i in range(plus_cnt + change_cnt):
            res *= plus_a[i]
            res %= MOD

    print(res)


main()


Measured memory_bytes: 31796
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append((1, b-1))
        edge[b-1].append((1, a-1))
    from heapq import heappop, heappush

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  # True:未確定
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    dist = dijkstra(edge, 0)
    if dist[N-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()


Measured memory_bytes: 106572
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[]args) throws Throwable {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int arr[] = new int[1 << n];
		for (int i = 0 ; i < (1 << n) ; ++i) {
			arr[i] = sc.nextInt();
		}
		Comparator<Integer> byArrayValue = (Integer a, Integer b) -> arr[a] - arr[b];
		ArrayList<Integer>[] res = new ArrayList[1 << n];
		for (int i = 0 ; i < (1 << n) ; ++i) {
			res[i] = new ArrayList();
			res[i].add(i);
		}
		for (int msk = 0 ; msk < (1 << n) ; ++msk) {
			for (int i = 0 ; i < n ; ++i) {

				if ( (msk & (1 << i)) == 0) {
					int next = msk | (1 << i);

					for (int j = 0 ; j < res[msk].size() ; ++j) {
						if (!res[next].contains(res[msk].get(j))) {
							res[next].add(res[msk].get(j));
						}
					}
					Collections.sort(res[next],byArrayValue);
					while (res[next].size() > 2) {
						res[next].remove(0);
					}
				}
			}
		}

		int ans[] = new int[1 << n];
		for (int i = 0 ; i < (1 << n) ; ++i) {
			if (res[i].size() == 2) {
				ans[i] = arr[res[i].get(0)] + arr[res[i].get(1)];
			}
			if (i > 0) {
				ans[i] = Math.max(ans[i], ans[i - 1]);
			}
		}

		for (int i = 1 ; i < (1 << n) ; ++i) {
			out.print(ans[i]+" ");
		}
		out.flush();
		out.close();
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}

Measured memory_bytes: 81232
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define pb push_back

typedef long long ll;
typedef pair<int,int> pi;
const int MAXN = (int)1e6+7;

long double a[MAXN];

int main()
{

    int N;
    cin >> N;
    long double ans = 0;
    rep(i,1,N) {
        cin >> a[i];
        ans += 1.0/a[i];
    }
    ans = 1.0/ans;
    printf("%.12Lf",ans);


}




Measured memory_bytes: 256
use std::vec::Vec;

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}


fn main() {
    let mut v: Vec<i32> = read_vec();
    v.sort();
    if v[0] == v[1] {
      println!("{}", 2 * v[1])
    } else {
      println!("{}", 2 * v[1] - 1)
    }

}


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

#define itn int
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())

#define random_shuffle(...) shuffle(__VA_ARGS__, rng)
#define rand() rng()

using namespace std;

inline int nxt() {
	int x;
	scanf("%d", &x);
	return x;
}

int main() {
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	const int mod = 1000000007;
	map<char, int> M;
	string s;
	int n;
	cin >> n >> s;

	for (char c : s) {
		M[c] += 1;
	}
	long long ans = 1;
	for (auto p : M) {
		ans = ans * (p.second + 1) % mod;
	}
	cout << (ans + mod - 1) % mod << "\n";

	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ls( s) (s&(-s))
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =   998244353;
ll n,k;
int a1[N],a2[N],a3[N];
vector<ll> v;
 int main()
{  fast
  cin>>n>>k;
  for(int i=0;i<n;i++)
  {
  	cin>>a1[i];
  	a1[i]--;
  	a2[i]=i;
  }
  while(k)
  {
  	if(k&1)
  	{
  		for(int i=0;i<n;i++)a3[i]=a1[a2[i]];
  		for(int i=0;i<n;i++)a2[i]=a3[i];
	  }
	  k>>=1;
	  for(int i=0;i<n;i++)a3[i]=a1[a1[i]];
	  for(int i=0;i<n;i++) a1[i]=a3[i];
  }
  cout<<a2[0]+1<<endl;

}


Measured memory_bytes: 6000
steps = list(str(input()))
kisu = ["R", "U", "D"]
gusu = ["L", "U", "D"]
flag = "Yes"

for n in range(len(steps)):
    # 奇数
    if n % 2 != 1:
        if steps[n] in kisu:
            continue
        else:
            flag = "No"
            break
    # 偶数
    else:
        if steps[n] in gusu:
            continue
        else:
            flag = "No"
            break

print(flag)

Measured memory_bytes: 3060