akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1001001001

void solve(ll N, ll M, ll X, vector<ll> C, vector<vector<ll> > A){
    int ans = INF;
    for (int i = 0; i < (1<<N); i++)
    {
        int cost = 0;
        vector<int> d(M, 0);
        for(int j = 0; j < N; j++){
            if(i>>j&1){
                cost += C[j];
                for(int k = 0; k < M; k++) d[k] += A[j][k];
            }
        }
        bool ok = true;
        for(int j = 0; j < M; j++) if(d[j] < X) ok = false;
        if(ok) ans = min(ans, cost);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return;
}

int main(){
    ll N, M, X;
    cin >> N >> M >> X;
    vector<ll> C(N);
    vector<vector<ll> > A;
    for(ll i = 0; i < N; ++i){
        cin >> C[i];
        vector<ll> temp_a(M);
        for(ll j = 0; j < M; ++j){
            cin >> temp_a[j];
        }
        A.push_back(temp_a);
    }
    solve(N, M, X, C, A);
    return 0;
}


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

int main() {
    int n; cin >> n;
    for (int i = 1; i <= 9; i++)
    {
        for (int j = 1; j <= 9; j++)
        {
            if (i*j == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter


n = int(input())
lst_v = list(map(int, input().split()))


if len(set(lst_v)) == 1:
    ans = n // 2
else:
    lst_odd = lst_v[::2]
    lst_even = lst_v[1::2]
    cnt_odd = sorted(Counter(lst_odd).items(), key=lambda x: -x[1])
    cnt_even = sorted(Counter(lst_even).items(), key=lambda x :-x[1])

    if cnt_odd[0][0] == cnt_even[0][0]:
        rem_number = max(cnt_odd[0][1] + cnt_even[1][1], cnt_odd[1][1] + cnt_even[0][1])
    else:
        rem_number = cnt_odd[0][1] + cnt_even[0][1]
    sum_odd = sum(t[1] for t in cnt_odd)
    sum_even = sum(t[1] for t in cnt_even)
    ans = sum_odd + sum_even - rem_number


print(ans)


Measured memory_bytes: 21084
/* Ajay Jadhav */
#include <bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

const int N=1e5+5;
vi g[N];
bool vis[N];
stack<int> st;

void dfs(int u)
{
    vis[u]=true;
    for(int v:g[u])
    {
        if(!vis[v])
            dfs(v);
    }
    st.push(u);
}

void solve()
{
    int n,m;
    cin>>n>>m;
    rep(i,0,m)
    {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
    }
    vi dis(n+1);
    rep(i,1,n+1)
    {
        if(!vis[i])
            dfs(i);
    }
    dis[1]=0;
    while(!st.empty())
    {
        int u=st.top();
        st.pop();
        for(int v:g[u])
        {
            if(dis[v]<dis[u]+1)
                dis[v]=dis[u]+1;
        }
    }
    int ans=0;
    rep(i,1,n+1) ans=max(ans,dis[i]);
    cout<<ans;
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

int N;
vector<vector<pair<int, int>>> tree;
vector<bool> flag;
vector<int> ans;
void dfs(int i, int p, int e) {
  flag[i] = true;
  for(int k = 0; k < tree[i].size(); ++k) {
    if(flag[tree[i][k].first] == true) continue;
    if(p == e) {
      ans[tree[i][k].second + 1] = e + 1;
      dfs(tree[i][k].first, e + 1, 1);
      e += 2;
    } else {
      ans[tree[i][k].second + 1] = e;
      dfs(tree[i][k].first, e, 1);
      e++;
    }
  }
}

int main() {
  cin >> N;
  tree.resize(N + 1); ans.resize(N + 1, 0); flag.resize(N + 1, false);
  REP(i, N - 1) {
    int a, b; cin >> a >> b;
    tree[a].push_back(make_pair(b, i));
    tree[b].push_back(make_pair(a, i));
  }
  REP(i, N + 1) {
    sort(all(tree[i]));
  }
  dfs(1, 0, 1);
  map<int, int> m;
  for(int i = 1; i < N; ++i) m[ans[i]]++;
  cout << m.size() << endl;
  for(int i = 1; i < N; ++i) {
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 10280
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int count = 0;
  vector<int>vec(n);
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
  }
  for(int i=0;i<n;i++){
    if(i%2 == 1)
      continue;
    if(vec.at(i)%2 == 1){
      count++;
    }
  }
  cout << count;
}



Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    string s,ans;
    int len;
    cin>>len;
    cin>>s;
    stack<char>st;
    for(int i=0; i<len; i++)
    {
        if(st.empty())
        {
            st.push(s[i]);
        }
        else
        {
            if(st.top()=='(' && s[i]==')')
                st.pop();
                else
                st.push(s[i]);
        }
    }
    int x=0,y=0;
    while(!st.empty())
    {
        if(st.top()==')')
            x++;
        else
            y++;
        st.pop();
    }
    for(int i=0; i<x; i++)
        ans+="(";
    ans+=s;
    for(int i=0; i<y; i++)
        ans+=")";
    cout<<ans<<endl;


    return 0;
}


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

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

	dev = (a * b) % 2;

	if (dev == 0) {
		cout << "Even" << endl;
	} else {
		cout << "Odd" << endl;
	}
}

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

typedef long long ll;




int main () {
	ll A;
	int B;
	char input[8];
	cin >> A >> input;
	char *p = input;
	int itg = 0, dec = 0;
	while (*p != '.' && *p != '\0') {
		itg = itg*10 + (int)(*p-'0');
		p++;
	}
	if (*p != '\0') {
		p++;
		while (*p != '\0') {
			dec = dec*10 + (int)(*p-'0');
			p++;
		}
	}
	ll tmp = A*dec/100;
	cout << A*itg + tmp << endl;

	return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>

int main(void){
    int a, b, c;
    scanf("%d %d %d",&a,&b,&c);
    int count=0;
    for(int i=a;i<=b;i++){
        if(c%i==0)count++;
    }
    
printf("%d\n", count);
return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < int(n); i++)

int main(){
    int L;
    cin >> L;
    vector<int> cat;
    vector<bool> is_there(1000, false);
    rep(i, L){
        int c;
        cin >> c;
        if(c >= 1){
            if(is_there[c]){
                cout << i + 1 << endl;
                return 0;
            }
            cat.push_back(c);
            is_there[c] = true;
        }else{
            if(cat.empty() || cat.back() != -c){
                cout << i + 1 << endl;
                return 0;
            }
            cat.pop_back();
            is_there[-c] = false;
        }
    }
    cout << "OK" << endl;
}





Measured memory_bytes: 3160
#include<iostream>
#include<vector>
#include<algorithm>

#define int long long
using namespace std;

int K, A, B;
int ans;

signed main()
{
	cin >> K >> A >> B;
	if (A >= B - 2 || K<A) {
		cout << K + 1 << endl;
	}
	else {
		K -= A - 1;
		ans = A;
		ans += (B - A)* (K / 2);
		ans += K % 2;
		cout << ans << endl;
	}

	return 0;

}




Measured memory_bytes: 256
# coding: utf-8
# Your code here!
n = int(input())
a = [int(i) for i in input().split()]

from heapq import *

pq1 = a[:n]
heapify(pq1)
s = sum(pq1)
score1 = [s]
for i in range(n):
    c=heappushpop(pq1, a[n+i])
    s += a[n+i] - c
    score1.append(s)

pq2 = [-i for i in a[2*n:]]
heapify(pq2)
s = sum(pq2)
score2 = [s]
for i in range(1,n+1):
    c=heappushpop(pq2, -a[2*n-i])
    s += -a[2*n-i] - c
    score2.append(s)

#print(score1)
#print(score2)
ans = -10**17
for i,j in zip(score1,reversed(score2)):
    ans = max(ans, i+j)

print(ans)
    


Measured memory_bytes: 39124
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=998244353;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e9+7;
const long double PI=acos(-1);

int n;
int a[2*N];


void solve(int T){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    ll ans=a[n-1];
    int i=n-2;
    int x=n-3;
    int m=0;
    while(x>=0){
        ans+=a[i];
        m++;
        if(m==2){
            m=0;
            i--;
        }
        x--;
        //cout<<ans<<" "<<a[i]<<"\n";
    }
    cout<<ans<<"\n";
}

int main() {
    fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
        if(i<T)cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 4376
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll b[4][4];
int main() 
{
    
    ll i,j;
    i=1;
    while(i<=3)
    {
        j=1;
        while(j<=3)
        {
            cin>>b[i][j];
            j++;
        }
        
        i++;
    }
    ll n;map<ll,ll> a1;cin>>n;
     i=1;
    while(i<=n)
    {
        ll x;
        cin>>x;
        a1[x]++;
        
        
        i++;
    }
    
    ll c=0;
    i=1;
    while(i<=3)
    {
        ll c1=0;
        j=1;
        while(j<=3)
        {
            if(a1[b[i][j]]>=1)
            {
                c1++;
            }
            j++;
        }
        if(c1==3)
        {
            c=1;
        }
        
        
        i++;
    }
    
     j=1;
    while(j<=3)
    {
        ll c1=0;
        i=1;
        while(i<=3)
        {
            if(a1[b[i][j]]>=1)
            {
                c1++;
            }
            i++;
        }
        if(c1==3)
        {
            c=1;
        }
        
        
        j++;
    }
    
    
    
    if(a1[b[1][1]]>=1 && a1[b[2][2]]>=1 && a1[b[3][3]]>=1)
    {
        c=1;
    }
    
     
    if(a1[b[1][3]]>=1 && a1[b[2][2]]>=1 && a1[b[3][1]]>=1)
    {
        c=1;
    }

    
    if(c==0)
    {
        cout<<"No";
    }
    else
    {
        cout<<"Yes";
    }
    
    
    return 0;
}

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  int m = max({A, B, C});
  int s = A + B + C;

  if (3 * m % 2 != s % 2)
    m++;

  int ans = (3 * m - s) / 2;

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define MO 1000000007
using namespace std;
vector<vector<lli> >v2;
void heapPermutation(lli a[], lli size, lli n) 
{ 
	lli i;
    if (size == 1) 
    { 
    	vector<lli>v1;
    	for(i=0;i<n;i++)	v1.push_back(a[i]);
        v2.push_back(v1);
        return; 
    } 
    for (i=0; i<size; i++) 
    { 
        heapPermutation(a,size-1,n); 
        if (size%2==1) 
            swap(a[0], a[size-1]);
        else
            swap(a[i], a[size-1]); 
    } 
} 
int main()
{
    lli n,i,j,x,y;
    cin >> n;
    lli a[n];
    for(i=0;i<n;i++)	a[i]=i+1;
    heapPermutation(a,n,n);
    vector<lli>p(n),q(n);
    stable_sort(v2.begin(),v2.end());
//    for(i=0;i<6;i++)
//    {
//    	for(j=0;j<v2[i].size();j++)
//    		{
//    			cout << v2[i][j] << " ";
//			}
//			cout << endl;
//	}
    for(i=0;i<n;i++)	cin >> p[i];
    for(i=0;i<n;i++)	cin >> q[i];
    for(i=0;i<v2.size();i++)
    {
    	if(v2[i]==p)
    	{
    		x=i+1;
    		break;
		}
	}
	for(i=0;i<v2.size();i++)
    {
    	if(v2[i]==q)
    	{
    		y=i+1;
    		break;
		}
	}
	cout << abs(x-y) << endl;
    
    return 0;
}


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


using namespace std;

using ll = long long;

int main() {
  string s;
  cin >> s;
  string ss[] = {"eraser", "erase", "dreamer", "dream"};
  reverse(s.begin(), s.end());
  for (int i = 0; i < 4; i++) {
    reverse(ss[i].begin(), ss[i].end());
  }

  for (int i = 0; i < (int)s.size();) {
    bool ng = true;
    for (int j = 0; j < 4; j++) {
      if (s.substr(i, ss[j].size()) == ss[j]) {
        ng = false;
        i += ss[j].size();
        break;
      }
    }
    if (ng) {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 3736
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool f(string s) { for (int i = 1; i < s.size(); i++)if (s[i] != s[0])return false; return true; }
int main() {
	string s; cin >> s;
	int ans = 114514;
	for (int i = 0; i < s.size(); i++) {
		string a, b;
		a = s;
		for (int j = 0; ; j++) {
			if (f(a)) {
				ans = min(ans, j);
				goto heaven;
			}
			for (int k = 0; k < a.size() - 1; k++) {
				if (a[k] == s[i] || a[k + 1] == s[i])b += s[i];
				else b += a[k];
			}
			a = b;
			b = "";
		}
	heaven:;
	}
	cout << ans << endl;
	cin >> s;
	return 0;
}

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

int main(){
    int n;
    scanf("%d",&n);
    string s;
    cin >> s;
    int ans=1;
    char last=s[0];
    for(int i=1;i<n;i++){
        if(s[i]!=last) ans++;
        last=s[i];
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> A(N);
  vector<ll> B(N);
  ll a_sum = 0, b_sum = 0;
  for (ll i = 0; i < N; ++i) {
    cin >> A.at(i);
    a_sum += A.at(i);
  }
  for (ll i = 0; i < N; ++i) {
    ll b;
    cin >> b;
    B.at(i) = b;
    b_sum += b;
  }
  if (a_sum < b_sum) {
    cout << -1 << endl;
    return 0;
  }
  ll ans = 0;
  vector<bool> chage(N, false);
  ll chage_num = 0;
  for (ll i = 0; i < N; ++i) {
    if (A.at(i) < B.at(i)) {
      chage.at(i) = true;
      chage_num += B.at(i) - A.at(i);
      ans += 1;
    }
  }
  vector<ll> can_chage;
  for (ll i = 0; i < N; ++i) {
    if (chage.at(i)) {
      continue;
    }
    can_chage.push_back(A.at(i) - B.at(i));
  }
  sort(can_chage.begin(), can_chage.end());
  reverse(can_chage.begin(), can_chage.end());
  ll temp = 0;
  for (ll i = 0; i < can_chage.size(); ++i) {
    if (temp >= chage_num) {
      break;
    }
    temp += can_chage.at(i);
    ans += 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 2940
s=input()
dp=[[0]*13 for _ in range(len(s)+5)]
dp[0][0]=1
for i in range(len(s)):
    
    if s[i]!='?':  
        j=int(s[i])
        for k in range(13):
            dp[i+1][(k*10+j)%13]+=dp[i][k]
            dp[i+1][(k*10+j)%13]%=(10**9+7)
    else:
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
                dp[i+1][(k*10+j)%13]%=(10**9+7)

print(dp[len(s)][5])

Measured memory_bytes: 61788
import java.util.*;
//import java.util.stream.Collectors;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		int d = Integer.parseInt(sc.next());
		int count = 0;
		for(int i=0; i<n; i++){
			long x = Integer.parseInt(sc.next());
			long y = Integer.parseInt(sc.next());
			if(Math.sqrt(x * x + y * y) <= d){
				count++;
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 58732
from collections import defaultdict as dd
N, K = map(int, input().split())
sushi = [tuple(map(int, input().split())) for _ in range(N)]
oishisa_sorted = sorted(sushi, key=lambda x: -x[1])

kiso = 0
n = 0
netanum = dd(int)
ans = 0
revidx = K - 1
for neta, oishisa in oishisa_sorted:
  if n < K:
    kiso += oishisa
    netanum[neta] += 1
    n += 1
    if n == K:
      ans = kiso + len(netanum) ** 2
  else:
    if netanum[neta] == 0:
      while revidx >= 0:
        neta2, oishisa2 = oishisa_sorted[revidx]
        revidx -= 1
        if netanum[neta2] >= 2:
          kiso = kiso - oishisa2 + oishisa
          netanum[neta2] -= 1
          netanum[neta] += 1
          tmp = kiso + len(netanum) ** 2
          ans = ans if ans > tmp else tmp
          break
print(ans)

Measured memory_bytes: 27032
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
using namespace std;
using ll = long long;
using d = double;
 
int main(){
  int n;
  string s;
  cin >> n >> s;
  vector<int> m(3);
 
  rep(i,n){
    if(s[i]=='R')++m[0];
    if(s[i]=='B')++m[1];
    if(s[i]=='G')++m[2];
  }
  ll t=1;
  rep(i,3) t*=m[i];
  for(int j=1;j<n;++j){
    rep(i,j){
      int k=j+(j-i);
      if(k>=n)continue;
      if(s[i]==s[j] || s[j]==s[k] || s[k]==s[i])continue;
      --t;
    }
  }
  cout << t << endl;
  return 0;
}

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

int main() {
  string s;
  int a, b;
  ostringstream os;
  for (int i = 0; i < 9; i++) {
    cin >> s >> a >> b;
    os << s << " " << a + b << " " << a * 200 + b * 300 << "\n";
  }
  cout << os.str();
}


Measured memory_bytes: 3120
// AOJ 1037 Midnight Teatime
// 2018.2.3 bal4u@uu

#include <stdio.h>
#include <string.h>

int info[10];
char tree[100], *p;
int buf[20][16], sz;

int *calc()
{
	int i, j, k;
	int *left, *right, *ans;

	ans = buf[sz++];
	if (*p == '(') {
		p++, left = calc(), p++, right = calc(), p++;
		for (i = 0; i < 16; i++) for (j = 0; j < 16; j++) {
			if (k = left[i] * right[j]) {
				ans[i & j] += k;
				ans[i | j] += k;
				ans[i ^ j] += k;
			}
		}
	} else ans[info[*p++ -'1']] = 1;
	return ans;
}

int main()
{
	int n, i, j;
	int *ans;
	char s[20];

	while(fgets(tree,100, stdin) && *tree != 'E') {
		memset(buf, 0, sizeof(buf));
		memset(info, 0, sizeof(info));

		fgets(s, 5, stdin), n = *s & 0xf;
		for (i = 0; i < n; i++) {
			fgets(p=s, 20, stdin);
			for (j = 0; j < 4; j++, p+=2) if (*p & 1) info[i] |= (1<<j);
		}

		p = tree, sz = 0, ans = calc();
		printf("%d\n", ans[15]);
	}
	return 0;
}


Measured memory_bytes: 2024
#include <iostream>
#include <stdio.h>

using namespace std;
typedef long long int lint;

void answer()
{
	int i, x;
	i = 0;
	while (1) {
		i++;
		cin >> x;
		if (x == 0) break;
		printf("Case %d: %d\n", i, x);
	}
}

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

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
const ll mod = 1e9 + 7;
const int INF = 1e9;

int main() {
	cin.sync_with_stdio(false);
	string S;
	cin >> S;
	string s = { "YAKI" };
	rep(i, 4) {
		if (S[i] != s[i]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
box = []
ans = 0
for i in range(20):
    if 2**i >= k:
        aa = i
        break
for j in range(1,n+1):
    cnt = 0
    for h in range(20):
        #print(aa)
        #print(j/(2**h))
        if (j/(2**h))*2**aa >= k:
            cnt = h
            #print(cnt)
        else:
            break
    box.append(cnt)
for y in range(1,n+1):
    ans += (1/n)*((1/2)**(max(0,(aa-box[y-1]))))
    #print((1/n)*((1/2)**(aa-box[y-1])))
    #print((1/n)*((1/2)**(aa-box[y-1]))
    #print((1/2)**(max((aa-box[y-1]),0))
#print(aa)
#print(box)
print(ans)

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

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

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    vector<tuple<ll, ll, ll>> A(N - 1);
    rep(i, N - 1) {
        ll C, S, F;
        cin >> C >> S >> F;
        A[i] = tuple<ll, ll, ll>{C, S, F};
    }
    rep(i, N) {
        ll t = 0;
        rep2(j, i, N - 1) {
            ll temp = t - get<1>(A[j]);
            if(temp < 0) temp = 0;
            t = get<2>(A[j]) * (temp / get<2>(A[j]) + !!(temp % get<2>(A[j]))) + get<1>(A[j]) + get<0>(A[j]);
        }
        cout << t << endl;
    }
    return 0;
}


Measured memory_bytes: 3656
N, K = map(int, input().split())
cnt = N
snuke = [0] * N
for i in range(K):
    d = int(input())
    a = list(map(int, input().split()))
    for j in range(d):
        if snuke[a[j] - 1] == 0:
            cnt -= 1
        snuke[a[j] - 1] += 1
print(cnt)


Measured memory_bytes: 9180
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define NIL NULL

using namespace std;

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root;

Node treeSearch(Node x, int k){
  while(x != NIL && k != x->key){
    if(k < x->key) x = x->left;
    else x = x->right;
  }
  return x;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = (Node)malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  z->parent = y;

  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;

}

void inorder(Node x){
  if(x == NIL) return;
  inorder(x->left);
  cout << " " << x->key;
  inorder(x->right);
}
void preorder(Node x){
  if(x == NIL) return;
  cout << " " << x->key;
  preorder(x->left);
  preorder(x->right);
}

bool find(int k){
  Node x = treeSearch(root, k);
  return x != NIL;
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      if(find(x)) cout << "yes" <<endl;
      else cout << "no" << endl;
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}


Measured memory_bytes: 21800
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n; cin >> n;
	vi a(n); rep(i, n) cin >> a[i];
	
	ll ans = 0;
	int x = 0;
	for(int i = 0, j = 0; i < n; i++){
		while(j < n && !(x & a[j])) x |= a[j++];
		ans += j - i;
		x ^= a[i];
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    int n, K; cin >> n >> K;

    int cur = (n - 1) * (n - 2) / 2;
    int a = 1, b = 2;

    using Edge = tuple<int, int>;
    vector<Edge> edges;
    rep(i, 1, n){
        edges.emplace_back(i, n);
    }

    if(cur < K){
        cout << -1 << endl;
        return 0;
    }
    while(cur > K){
        if(a >= n-1 and b >= n-1){
            cout << -1 << endl;
            return 0;
        }

        cur--;
        edges.emplace_back(Edge(a, b));

        if(b == n-1){
            a++;
            b = a + 1;
        }
        else {
            b++;
        }
    }

    cout << edges.size() << endl;
    for(auto& e : edges){
        int a, b; tie(a, b) = e;
        cout << a << " " << b << endl;
    }

    return 0;
}


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

#define INF 100100100
#define MOD 1000000007

using namespace std;
using ll = long long;
using ull = unsigned long long ;

int main(int argc, char const* argv[]){
   ios::sync_with_stdio(false);
   cin.tie(0);

   int N,K;
   cin>>N>>K;
   map<int,int>M;
   int a;
   for(int i=0;i<N;i++){
      cin>>a;
      M[a]++;
   }

   vector<pair<int,int> >A;
   for(auto it: M){
      A.push_back(make_pair(it.second,it.first));
   }

   if(A.size() <= K){
      cout<<0<<endl;
      return 0;
   }

   sort(A.begin(),A.end());

   ll ans = 0;

   for(int i=0;i<A.size()-K;i++){
      ans += A[i].first;
   }

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


Measured memory_bytes: 11764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int N,M,ans[200010];
vector<int> edge[200010];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>M;
	for(int i=0;i<M;i++){
		int u,v; cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	queue<int> q;
	q.push(1); ans[1]=1;
	while(!q.empty()){
		int now=q.front(); q.pop();
		for(auto i:edge[now]) if(!ans[i]){
			q.push(i);
			ans[i]=now;
		}
	}
	cout<<"Yes"<<endl;
	for(int i=2;i<=N;i++) cout<<ans[i]<<endl;
	return 0;
}

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

#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl "\n"
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define rev(a) (a).rbegin(),(a).rend()
#define pll pair<ll,ll>
#define rep(i,a,b) for(long long i = (a); i <= (b); i++)

const int mod = 1e9+7;
const int N = 1e5+5; 

int main(){
	fast;
	ll t = 1; 
	//cin >> t;
	while(t--){
	    ll n; cin >> n;
	    bool f = false;
	    ll cnt = 0;
	    rep(i,1,n){
	        ll a,b; cin >> a >> b;
	        if(a == b){
	            cnt++;
	        }    
	        else{
	            cnt = 0;
	        }
	        
	        if(cnt >= 3) f = true;
	    }
	    
	    if(f) cout << "Yes\n";
	    else cout << "No\n";
	}
}

Measured memory_bytes: 3632
#include <stdio.h>

#define NMAX 501

int N, M, Q;
int l, r, p, q;
int lr[NMAX][NMAX], s[NMAX][NMAX];

int main()
{
	int i, j;
	int sum;
	
	for(i = 0; i <= N; i++) {
		for(j = 0; j <= N; j++) {
			lr[i][j] = 0;
			s[i][j] = 0;
		}
	}
	
	scanf("%d %d %d", &N, &M, &Q);
	for(i = 0; i < M; i++) {
		scanf("%d %d", &l, &r);
		lr[l][r]++;
	}
	
	for(i = 1; i <= N ; i++) {
		for(j = 1; j <= N; j++) {
			s[i][j] = s[i][j-1] + lr[i][j];
		}
	}
	
	for(i = 0; i < Q; i++) {
		scanf("%d %d", &p, &q);
		sum = 0;
		for(j = p; j <= q; j++) {
			sum += s[j][q] - s[j][p-1];
		}
		printf("%d\n", sum);
	}
	return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, s, e) for(ll i=s; i>=e; i--)
#define reps(i, s, e) for(ll i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<ll>())
#define sz(x) x.size()
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
using namespace std;
template<typename T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){ a=b; return true; } return false; }
template<typename T> T gcd(T a, T b){ if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b){ return a*(b/gcd(a, b)); }
template<typename T> T keta(T num){ T k=0; while(num>0){ num/=10; k++; } return k; }
template<typename T> void vdebug(vector<T> v){ for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> void adebug(T arr[], ll n){ reps(i, 0, n){ cout << arr[i] << " "; } cout << endl; }
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


bool solve1(ll x, ll y, ll z){
    if(x%2==0){
        cout << 0 << endl;
        return true;
    }
    return false;
}

ll solve2(ll x, ll y, ll z){
    ll v1 = (x/2)*y*z;
    ll v2 = (x/2+1)*y*z;
    return abs(v1-v2);
}

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

    ll a, b, c;
    cin >> a >> b >> c;

    if(solve1(a, b, c)) return 0;
    if(solve1(b, c, a)) return 0;
    if(solve1(c, a, b)) return 0;

    ll cand1 = solve2(a, b, c);
    ll cand2 = solve2(b, c, a);
    ll cand3 = solve2(c, a, b);

    cout << min(cand1, min(cand2, cand3)) << endl;

    return 0;
}


Measured memory_bytes: 256
import itertools
import collections

def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

def calc_dist(x, y):
	return abs(x - 1) + abs(y - 1)

n = int(input())
ll = prime_factorize(n)
c = collections.Counter(ll)
kk = list(c.keys())
vv = list(c.values())
pp = [list(range(vv[i] + 1)) for i in range(len(kk))]

min_dist = 10 ** 12
# print(c)
# print(kk)
# print(vv)
for bb in itertools.product(*pp):
	l = 1
	r = 1
	for i in range(len(kk)):
		l *= max(kk[i] ** bb[i], 1)
		r *= max(kk[i] ** (vv[i] - bb[i]), 1)
	#print(bb, l, r, calc_dist(l, r))
	min_dist = min(min_dist, calc_dist(l, r))
print(min_dist)

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

namespace _20170409_AOJ
{
    class ALDS1_1D
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int min;
            int maxD = int.MinValue;

            min= int.Parse(Console.ReadLine());
            for (int i = 1; i < n; i++)
            {
                int t = int.Parse(Console.ReadLine());
                maxD = Math.Max(maxD, t - min);
                min = Math.Min(min, t);
            }

            Console.WriteLine(maxD);

            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 9124
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, l;
  cin >> n >> l;
  vector<int> a(n);
  int sum = 0;
  for(int i = 0; i < n; i++) {
  	a[i] = l + i;
    sum +=  l + i;
  }
  int dmin = 30000;
  bool s;
  for (int i = 0; i < n; i++) {
    s = a[i];
    if (a[i] <= 0) {
    	dmin = min(dmin, -1*a[i]);
      if(dmin == -1*a[i]) {
      	s = false;
      }
    }
    else {
     	dmin = min(dmin, a[i]);
      if(dmin == a[i]) {
      	s = true;
      }
    }
  }
  if (s) {
  	cout << sum - dmin << endl;
  }
  else {
  	cout << sum +  dmin << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a) for(i = 0 ; i < a ; i++)
#define whln(t) while(t--)
#define whlp(t) while(t++)
ll i=0,j=0;


int main(void){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
	#endif
	 // int t ;
	 // cin>>t;
	 // whln(t){

   	ll arr[3][3];
   	rep(i,3)
   		rep(j,3)
   			cin>>arr[i][j];
   	ll  n ;
   	cin>>n;
   	set<ll> b;
   	rep(i,n){
   		ll x ;
   		cin>>x;
   		b.insert(x);
   	}

   	rep(i,3)
   		rep(j,3){
   			if(b.find(arr[i][j])!=b.end())
   				arr[i][j]=0;
   		}
   	bool f = false;	
   	rep(i,3){
   		if(arr[i][0]==0 && arr[i][1]==0 && arr[i][2]==0)
   			f = true ;
   	}
   	rep(i,3){
   		if(arr[0][i]==0 && arr[1][i]==0 && arr[2][i]==0)
   			f = true ;
   	}

   	if(arr[0][0]==0&&arr[2][2]==0&&arr[1][1]==0)
   		f = true ;
   	if(arr[0][2]==0 && arr[1][1]==0 && arr[2][0]==0)
   		f = true ;

   	if(f)
   		cout<<"Yes";
   	else
   		cout<<"No";
   			
   		

}
//   *****  *******   !
//   *		     *    !
//   ***       *      !
//   *       *        !
//   *****  *******   !

Measured memory_bytes: 3608
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>; 
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){
  int n; cin >> n;
  int res = n + n*n + n*n*n;
  cout << res << ln;
}


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

using namespace std;

void solve(){
    string s;
    cin>>s;
    if(s[s.size()-1]=='s')
    {
        s+="es";
    }
    else{
        s+='s';
    }
    cout<<s<<endl;
}

int main()
{
    solve();
}

Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string str, longest="";
    map<string, int> words;
    while(cin>>str){
        if(longest.length()<str.length()) longest=str;
        if(words.find(str)==words.end()) words[str]=1;
        else ++words[str]; 
    }
    auto max = words.begin();
    for(auto it=words.begin(); it!=words.end(); ++it){
        if(max->second<it->second) max=it;
    }
    cout<<max->first<<' '<<longest<<'\n';
    return 0;
}

Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
#define Yes "Yes"
#define No "No"
#define YES "YES"
#define NO "NO"
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 >& p) {
  os << "{" <<p.first << ", " << p.second << "}";
  return os;
}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const int INF = (ll)1e9;
const ll INFLL = (ll)1e18+1;
const ll MOD = (ll)1e9+7;
const double PI = acos(-1.0);
/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

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

    ll K;
    cin >> K;
    
    auto check = [&](ll X){
        // Xを桁ごとのvectorに変換
        vector<int> vx;
        ll tmp = X;
        while(tmp > 0){
            vx.push_back(tmp%10);
            tmp/=10;
        }
        reverse(all(vx));
        //桁数
        int N = vx.size();
        // dp[i][smaller][0以外を一度でも取ったか][最後の数字]
        ll dp[N+1][2][2][10];
        rep(i,N+1)rep(j,2)rep(k,2)rep(l,10)
            dp[i][j][k][l] = 0;

        dp[0][0][0][0] = 1;
        //dpの遷移
        for(int i = 0; i < N; i++)rep(j,2)rep(k,2)rep(l,10){
            for(int nxt = max(0, l-1); nxt <= (k ? min(l+1, (j ? 9:vx[i])): j ? 9 : vx[i]); nxt++){
                dp[i+1][j || nxt < vx[i]][k || nxt > 0][nxt] +=  dp[i][j][k][l];
            }
        }
        ll cnt = 0;
        rep(j,2)rep(l,10)cnt += dp[N][j][1][l];
        return cnt >= K;
    };
    ll ng = 0;
    ll ok = 1e18;
    while(ok - ng > 1){
        ll mid = (ok + ng) / 2;
        if(check(mid))ok = mid;
        else ng = mid;
    }
    cout << ok << endl;
}

Measured memory_bytes: 256
from math import atan2, pi

a, b, x = map(int, input().split())
V = a * a * b
p2t = 180 / pi
if V == x:
    print(0)
elif V/2 < x:
    # print(p2t*tan(a**3/(2*(V-x))))
    print(90-p2t*atan2(a, 2*(V-x)/a**2))
else:
    # print(p2t*tan(a**3/(2*x)))
    print(90-p2t*atan2(2*x/a/b, b))


Measured memory_bytes: 3060
-- 解法見た
local read = io.read
local xor = bit.bxor

local N = read("*n")
local S = 0
local a = {}
for i = 1, N do
	a[i] = read("*n")
end

for i = 1, N do
	S = xor(S, a[i])
end

local out = {}
for i = 1, N do
	out[i] = xor(S, a[i])
end

print(table.concat(out, " "))


Measured memory_bytes: 11120
txt, n = [input() for i in range(2)]
n = int(n)

first_flg = True
present_char = txt[0]
present_cnt = 0
numlen_list = []

for x in txt:
  if x == present_char:
    present_cnt += 1
  else:
    first_flg = False
    numlen_list.append(present_cnt)
    present_cnt = 1
    present_char = x

numlen_list.append(present_cnt)
guruguru_flg = (txt[0] == txt[-1])


if len(numlen_list) == 1:
  print(numlen_list[0] * n // 2)
elif guruguru_flg:
  print(sum([x // 2 for x in numlen_list[1:-1]]) * n
        + (numlen_list[0] + numlen_list[-1]) // 2 * (n-1)
        + numlen_list[0] // 2
        + numlen_list[-1] // 2)
else:
  print(sum([x // 2 for x in numlen_list]) * n)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cassert>
using namespace std;

int dp[202020];
unordered_map<int, int> dp2;

int main() {
    string s;
    cin >> s;
    int n = int(s.size());
    
    int x = 0;
    dp2[0] = 0;
    for (int i = 0; i < n; i++) {
        x ^= 1 << (s[i] - 'a');
        int m = 1e9;
        if (dp2.count(x) == 0) {
            dp2[x] = 1e9;
        }
        m = min(m, dp2[x]);
        
        for (int j = 0; j < 26; j++) {
            int xx = x ^ (1 << j);
            if (dp2.count(xx) == 0) dp2[xx] = 1e9;
            m = min(m, dp2[xx]);
        }
        
        dp2[x] = min(dp2[x], m + 1);
        dp[i] = m + 1;
    }
    
    cout << dp[n - 1] << endl;
}


Measured memory_bytes: 171100
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<n;++i)

typedef long long ll;
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll l, r;
    cin >> l >> r;
    vector<ll> res = {};
    int cnt = 0;
    for(ll i=l;i<=r;++i){
        res.push_back(i%2019LL);
        ++cnt;
        if(cnt==2020)break;
    }
    sort(res.begin(), res.end());
    ll ans = 2020;
    for(ll i=0;i<cnt-1;++i){
        for(ll j=i+1;j<cnt;++j){
            ans = min(ans, (res[i]*res[j])%2019LL);
        }
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

	for(int i=30;i>=0;i--){
	    if((N / Math.pow(K,i)) >= 1){
		System.out.print(i+1);
		break;
	    }
	}
    }
}


Measured memory_bytes: 23764
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        B solver = new B();
        solver.solve(1, in, out);
        out.close();
    }

    static class B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int N = Integer.parseInt(in.next());
            Integer a[] = new Integer[N];
            for (byte i = 0; i < N; i++) {
                a[i] = Integer.parseInt(in.next());
            }
            Arrays.sort(a, Comparator.reverseOrder());
            int Alice = 0;
            int Bob = 0;
            for (int i = 0; i < N; i += 2) {
                Alice += a[i];
            }
            for (int i = 1; i < N; i += 2) {
                Bob += a[i];
            }
            out.println(Alice - Bob);
        }

    }
}



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


int main()
{
  	string S, answer;
	cin >> S;
	bool hantei_1, hantei_2;
	int N;
	N = stoi(S);
	if (N>=100 && N<=1299){
		hantei_1 = true;
	}
	else {
		hantei_1 = false;
	}

	if (N%100>=1 && N%100<=12){
		hantei_2 = true;
	}
	else {
		hantei_2 = false;
	}
	if (hantei_1 == true && hantei_2 == true){
		answer = "AMBIGUOUS";
	}
	if (hantei_1 == true && hantei_2 == false){
		answer = "MMYY";
	}
	if (hantei_1 == false && hantei_2 == true){
	answer = "YYMM";
	}
	if (hantei_1 == false && hantei_2 == false){
		answer = "NA";
	}
	cout << answer << endl;

	return 0;
}

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

ll n, a, b;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
    if (a > b) {
        cout << 0 << "\n";
        return 0;
    } if (n == 1 && a != b) {
        cout << 0 << "\n";
        return 0;
    }

    cout << 1 + (n-2)*(b-a) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>

using namespace std;


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

    if(a >= 13) cout << b << endl;
    else if(a >= 6 && a <= 12) cout << b/2 << endl;
    else cout << 0 << endl;




    return 0;
}


Measured memory_bytes: 888
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int Q=1505;
char a[Q][Q];
int f[Q][Q],l[Q][Q],r[Q][Q];
int n;
int Ok(int x,int y)
{return (x<=n)&(y<=n)&(a[x][y]!='#');}
int main()
{
    ll als=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    for(int i=n;i;--i)
        for(int j=n;j;--j){
            if(!Ok(i,j)){
                l[i][j]=n+1,r[i][j]=-1;
                continue;
            }
            int D=Ok(i+1,j),R=Ok(i,j+1);
            int val=a[i][j]-'0';
            if(!(D|R)){
                f[i][j]=val;
                l[i][j]=r[i][j]=j;
                for(int k=i+1;k<=n;k++)
                    l[k][j]=n+1,r[k][j]=0;
            }
            else if(D&R){
                f[i][j]=f[i+1][j]+f[i][j+1]+val;
                for(int k=i+1,mxr=0;k<=n;k++){
                    int &lv=l[k][j+1],&rv=r[k][j+1];
                    if(lv>mxr&&lv<=r[k][j])f[i][j]-=f[k][lv];
                    mxr=max(mxr,r[k][j]);
                    l[k][j]=min(l[k][j],lv);
                    r[k][j]=max(r[k][j],rv);
                }
                l[i][j]=j;
                r[i][j]=r[i][j+1];
            }
            else if(D){
                f[i][j]=f[i+1][j]+val;
                l[i][j]=r[i][j]=j;
            }
            else{
                f[i][j]=f[i][j+1]+val;
                
                for(int k=i;k<=n;k++)
                    l[k][j]=l[k][j+1],r[k][j]=r[k][j+1];l[i][j]=j;
            }
            als+=1LL*val*(f[i][j]-val);
        }
    printf("%lld\n",als);
    return 0;
}

Measured memory_bytes: 18688
fun main(args: Array<String>) {
  val c = Array(3) { listOfInt() }
  val y = c[0]
  val x = IntArray(3) { c[it][0] - y[0] }
  val good =
    (0 until 3).all { i ->
      (0 until 3).all { j ->
        c[i][j] == (x[i] + y[j])
      }
    }
  val ans = if(good) "Yes" else "No"
  println(ans)
}

fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun nextInt(offset: Int = 0) = nextInt() + offset
fun nextLong() = java.lang.Long.parseLong(next())
fun nextLong(offset: Long = 0L) = nextLong() + offset
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }

Measured memory_bytes: 36052