akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int mod = 1000000007;
struct UnionFind{
    vector<int> d;
    UnionFind(int n=0):d(n,-1){}
    int root(int x){
        if(d[x] < 0) return x;
        return d[x] = root(d[x]);
    }
    void unite(int x,int y){
        int root_x = root(x);
        int root_y = root(y);
        if(root_x == root_y) return;
        if(d[root_x] > d[root_y]) swap(root_x,root_y);
        d[root_x] += d[root_y];
        d[root_y] = root_x;
    }
    bool same(int x,int y){return root(x) == root(y);}
    int size(int x){return -d[root(x)];}
};

int main(){
    int n,m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        uf.unite(a,b);
    }
    int ans = 0;
    rep(i,n) if(uf.d.at(i) < 0) ans++;
    ans = max(ans-1,0);
    cout << ans << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pp push_back
#define pi pair<ll,ll>
#define pii pair<int,int>
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,i,j,k,l,m,a,b,t,sum,sum1,flag;
    cin>>n>>m>>k;
    sum=0;
    for(i=n;i<=m;i++){
        if(i%k==0){
            sum+=1;
        }
    }
    cout<<sum<<endl;

}


Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define mk make_pair
#define pi pair<int, int>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = a; i >= (b); --i)
using namespace std;
int dt[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {0, 0}};
//typedef pair<int, int> P;
//priority_queue<int, vector<int>, greater<int> > q;

const int N = 2010;
ll f[N];

int main()
{
    IOS;
    int s;
    cin >> s;
    f[0] = 1;
    rep(i, 3, s)
    {
        rep(j, 3, i)
        {
            f[i] = (f[i] + f[i - j]) % mod;
        }
    }
    cout << f[s];
}


Measured memory_bytes: 3580
#include <stdio.h>
#include <limits.h>
typedef unsigned int uint;

inline static uint gl(void){
    uint x = 0;
    for(;;){
        const uint c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}

uint v[200000];
int main(void){
    const uint h = gl();
    gl();
    const uint n = gl();
    for(uint i=0; i<h; i++){ v[i] = i+2; }
    for(uint i=0; i<n; i++){
        uint x = gl()-1;
        uint y = gl();
        v[x] = y<v[x] ? y : v[x];
    }
    uint right = 1;
    for(uint x=1; x<h; x++){
        if(v[x]<right+1){
            printf("%d\n", x);
            return 0;
        }else if(v[x]>right+1){
            right++;
        }
    }
    printf("%d\n", h);
    return 0;
}


Measured memory_bytes: 896
#include <cstdio>

int main(void)
{
	int n;
	int i, j;
	int count, ct, k = 0;
	int num[2][15];
	
	while (scanf("%d", &n), n){
		count = 0;
		for (i = 0; i < n; i++){
			scanf("%d", &num[0][i]);
		}
		k = 0;
		while (1){
			for (i = 0; i < n; i++){
				ct = 0;
				for (j = 0; j < n; j++){
					if (num[k][i] == num[k][j]) ct++;
				}
				num[1 - k][i] = ct;
			}
			ct = 0;
			for (i = 0; i < n; i++){
				if (num[0][i] == num[1][i]) ct++;
			}
			if (ct == n){
				break;
			}
			k = 1 - k;
			count++;
		}
		
		printf("%d\n%d", count, num[0][0]);
		for (i = 1; i < n; i++){
			printf(" %d", num[0][i]);
		}
		printf("\n");
	}
	return (0);
}

Measured memory_bytes: 1032
export class Main {
  static main(input: string): string {
    const tmp: string[] = input.split("\n");
    const [a, b, n]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    const x = Math.min(b - 1, n);
    return `${Math.floor(a * x / b) - a * Math.floor(x / b)}`;
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 29640
import sys
while True:
    m, f, r = map(int, input().split())
    if m == f == r == -1:
        sys.exit()
    if m == -1 or f == -1:
        print('F')
    elif m + f >= 80:
        print('A')
    elif m + f >= 65:
        print('B')
    elif m + f >= 50:
        print('C')
    elif m + f >= 30:
        if r >= 50:
            print('C')
        else:
            print('D')
    else:
        print('F')


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)n; i++)
const int MOD = 1000000007;
// long long a;
int main(){
  string s;
  cin >> s;
  int l = 0;
  int r = s.size();
  for(int i =0;i < r ; i ++){
    if(s[i] == 'A'){
      l = i;
      break;
    }
  }
  for(int i = s.size() - 1;i >=0 ; i --){
    if(s[i] == 'Z'){
      r = i;
      break;
    }
  }
  cout << r- l + 1 << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<ll, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int n;
int x[200010],y[200010],u[200010],p[200010],q[200010];
map<int,set<P>> ma_x,ma_y,ma_p,ma_q;
string s[200010];

void solve(){
  cin >> n;
  rep(i,n){
    cin >> x[i] >> y[i] >> s[i];
    if(s[i]=="U") u[i]=0;
    if(s[i]=="D") u[i]=1;
    if(s[i]=="R") u[i]=2;
    if(s[i]=="L") u[i]=3;
    p[i]=x[i]+y[i];
    q[i]=x[i]-y[i];
    ma_p[p[i]].insert(P(q[i],u[i]));
    ma_q[q[i]].insert(P(p[i],u[i]));
    // x[i]*=2;
    // y[i]*=2;
    ma_x[x[i]].insert(P(y[i],u[i]));
    ma_y[y[i]].insert(P(x[i],u[i]));
  }
  ll ans=mod;
  for(auto s:ma_p){
    ll ma_R=-INF,ma_D=-INF;
    for(P p:s.second){
      //cout << p.first << " " << p.second << endl;
      if(p.second==0){
        ans=min(ans,p.first-ma_R);
      }
      if(p.second==1){
        ma_D=p.first;
      }
      if(p.second==2){
        ma_R=p.first;
      }
      if(p.second==3){
        ans=min(ans,p.first-ma_D);
      }
    }
  }
  for(auto s:ma_q){
    ll ma_R=-INF,ma_U=-INF;
    for(P p:s.second){
      //cout << p.first << " " << p.second << endl;
      if(p.second==0){
        ma_U=p.first;
      }
      if(p.second==1){
        ans=min(ans,p.first-ma_R);
      }
      if(p.second==2){
        ma_R=p.first;
      }
      if(p.second==3){
        ans=min(ans,p.first-ma_U);
      }
    }
  }
  for(auto s:ma_x){
    ll ma_U=-INF;
    for(P p:s.second){
      //cout << p.first << " " << p.second << endl;
      if(p.second==0){
        ma_U=p.first;
      }
      if(p.second==1){
        ans=min(ans,p.first-ma_U);
      }
    }
  }
  for(auto s:ma_y){
    ll ma_R=-INF;
    for(P p:s.second){
      //cout << p.first << " " << p.second << endl;
      if(p.second==2){
        ma_R=p.first;
      }
      if(p.second==3){
        ans=min(ans,p.first-ma_R);
      }
    }
  }
  if(ans==mod) cout << "SAFE" << endl;
  else cout << ans*5 << endl;
}

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

Measured memory_bytes: 131224
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld long double
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    pair<int,int> a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j].first;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j].second;
        }
    }
    vector<bool> v[n][m];
    int nax=(n+m)*80;
    v[n-1][m-1].resize(nax,false);
  //  return 0;
    v[n-1][m-1][abs(a[n-1][m-1].first-a[n-1][m-1].second)]=true;
    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            v[i][j].resize(nax,false);
            for(int k=0;k<nax;k++){
                if(i+1 <= n-1){
                    if(v[i+1][j][k]){
                    int g=a[i][j].first-a[i][j].second;
                    v[i][j][abs(g+k)]=true;
                    v[i][j][abs(k-g)]=true;
                }
                }
                if(j+1 <= m-1){
                    if(v[i][j+1][k]) {
                    int g=a[i][j].first-a[i][j].second;
                    v[i][j][abs(g+k)]=true;
                    v[i][j][abs(k-g)]=true;
                }
                }
            }
        }
    }

    for(int i=0;i<nax;i++){
        if(v[0][0][i]){
            cout<<i; return 0;
        }
    }
}


Measured memory_bytes: 10624
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
ll n,m,h,hh,l,lll;

int main()
{
    cin>>n>>m;
    h=(n+1)/2;
    hh=n-h;
    l=(m+1)/2;
    lll=m-l;
    if(n==1 || m==1) cout<<"1"<<endl;
    else cout<<h*l+hh*lll<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,t,a;
    cin >> n >> t >> a;
    double dif = INF;
    int res;
    rep(i,n){
        int h;
        cin >> h;
        if(dif > abs(a-(t-h*0.006))){
            dif = abs(a-(t-h*0.006));
            res = i;
        }
    }
    cout << res+1 << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repl(i,n) for(int64_t i=0;i<(int64_t)(n);i++)
#define ll int64_t
#define all(v) (v).begin(),(v).end()
#define P pair<int,int>
using namespace std;

int main() {
  int w,h,x,y; cin>>w>>h>>x>>y;
  double ans=(double)w*h/2;
  int num= (w==x*2 && h==y*2)?1:0;
  printf("%.10f %d\n",ans,num);
  return 0;
}

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

int main(){
    int n;
    string s1,s2;
    cin>>n;
    cin>>s1>>s2;
    
    ll ans=1;
    int i=0;
    if(s1[i]==s2[i]){
        ans*=3;
        i++;
    }else{
        ans*=6;
        i+=2;
    }
    while(i<n){
        if(s1[i]==s2[i]){
            if(s1[i-1]==s2[i-1]){
                ans*=2;
                ans%=M;
            }
            i++;
        }else{
            if(s1[i-1]==s2[i-1]){
            ans*=2;
            ans%=M;
            }else{
                ans*=3;
                ans%=M;
            }
            i+=2;
            
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#C_Snuke Festival
import bisect

def SnukeFestival(N, A, B, C):
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)
    count = 0

    for b in B:
        n_a = bisect.bisect_left(A,b)
        n_c = bisect.bisect_right(C,b)
        count += n_a * (N - n_c)

    print(count)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    SnukeFestival(N, A, B, C)

Measured memory_bytes: 23360
import fractions

A,B,C,D = map(int, input().split())
lcm_number = C*D // fractions.gcd(C, D)
all_number = B -A + 1

answer_C = B // C - (A-1) // C
answer_D = B // D - (A-1) // D
answer_lcm = B // lcm_number - (A-1) // lcm_number

print(all_number - answer_C - answer_D + answer_lcm)

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

using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair

int main()
{
	ios::sync_with_stdio(false);
  	cin.tie(0);
	int a,b;
	char c;
	cin >> a >> c >> b;
	if(c == '-')
		cout << a-b << "\n";
	else cout << a+b << "\n";	
	return 0;
}

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

int main() {
    ll n, x;
    cin>>n;

    ll minv = LLONG_MAX;
    for(int i=0;i<5;i++) {
        cin>>x;
        minv = min(minv, x);
    }

    cout<<((n+minv-1)/(minv)) + 4<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    bool tf = true;
    while (tf) {
        c -= b;
        if (c <= 0) {
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if (a <= 0) {
            cout << "No" << endl;
            return 0;
        }

    }
}


Measured memory_bytes: 3652
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
#include <map>
#include <queue>
#include <iostream>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n)
    {
           if(n&1)
           {
               cout<<n*2<<endl;
           }
           else
            cout<<n<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

A = [1]*(N+1)
res = 0
def f(n):
    global res
    if n == N+1:
        res = max(f2(), res)
        return
    for i in range(A[n-1], M+1):
        A[n] = i 
        f(n+1)
    return res

def f2():
    num = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            num += d
    return num

f(1)
print(res)

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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
// end of Template

int n,a[60];
vpii seq;

int main(){

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    cin>>n;

    for(int i=1;i<=n;i++)cin>>a[i];
    int mx = -1;
    int idx = 0;

    for(int i=1;i<=n;i++){
        if(abs(a[i]) > mx) {mx = abs(a[i]); idx = i;}
    }

    cout<<2*n<<newl;
    if(a[idx]>=0){
        cout<<idx<<" "<<1<<newl;
        cout<<idx<<" "<<1<<newl;
        for(int i=1;i<n;i++){
            cout<<i<<" "<<i+1<<newl;
            cout<<i<<" "<<i+1<<newl;
        }
    }
    else{
        cout<<idx<<" "<<n<<newl;
        cout<<idx<<" "<<n<<newl;
        for(int i=n;i>1;i--){
            cout<<i<<" "<<i-1<<newl;
            cout<<i<<" "<<i-1<<newl;
        }
    }


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL k;
string s;
int main(){
	LL i;
	cin>>s>>k;
	for(i=0;i<(LL)s.length();i++)if(s[i]!='1')break;
	k-=i;
	if(k<=0)cout<<"1\n";
	else{
		for(i=0;i<(LL)s.length();i++){
			if(s[i]!='1'){
				cout<<s[i]<<endl;
				return 0;
			}
		}
	}
	return 0;
}

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

using namespace std;

int main()
{

    long long x,k,d;
    cin>>x>>k>>d;
    long long abso = abs(x);
    long long count = 0;
    if(abso <= d)
    {
        if(k%2 == 1)
        {
            cout<<abs(abso - d);
        }
        else
        {
            cout<<abso;
        }
    }
    else
    {
        long long dist = abso - d;
        long long steps = dist%d==0?dist/d:dist/d + 1;
        if(steps >= k)
        {
            cout<<abso - k*d;
        }
        else
        {
            long long curpos = abso - steps * d;
            long long rem = k - steps;
            if(rem % 2 == 1)
            {
                cout<<abs(curpos - d);
            }
            else
            {
                cout<<curpos;
            }
            
        }
        
    }
    
    
    
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int sum, n, a, b, c, d;
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        n = a + b;
        int l = 0, r = n + 1, mid, A, B;
        sum = (max(a, b) - 1) / (min(a, b) + 1) + 1;
        while (l < r) {
            mid = (l + r) >> 1;
            A = a - mid / (sum + 1) * sum - mid % (sum + 1);
            B = b - mid / (sum + 1);
            (B <= 1ll * A * sum) ? l = mid + 1 : r = mid;
        }
        A = a - l / (sum + 1) * sum - l % (sum + 1), B = b - l / (sum + 1);
        r = l + B - A * sum + 1;
        for (int i = c; i <= min(d, l); ++i) putchar(i % (sum + 1) ? 'A' : 'B');
        for (int i = max(c, l + 1); i <= d; ++i)
            putchar((i - r) % (sum + 1) ? 'B' : 'A');
        puts("");
    }
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
    cin>>S>>N;
    ll ls = S.size(),ns;
    ll N2=N;
    while(N2<10)  N2 *= 9;
    mat dp1(ls,vec(N2,0));//すでに下回ってる
    mat dp2(ls,vec(N2,0));//ギリギリ
    const int mod = (1e+9)+7;
    rep(i,ls){
        ns = S.at(i) - '0';
        if(i == 0){
            rep(j,ns) dp1.at(i).at(j) = 1;
            dp2.at(i).at(ns) = 1;
        }else {
            rep(j, N2) {
                rep(k, 10) {
                    if (j - k < 0) (dp1.at(i).at(j) += dp1.at(i-1).at(j - k + N2)) %= mod;
                    else (dp1.at(i).at(j) += dp1.at(i-1).at(j - k)) %= mod;
                }
                rep(k, ns) {
                    if (j - k < 0) (dp1.at(i).at(j) += dp2.at(i-1).at(j - k + N2)) %= mod;
                    else (dp1.at(i).at(j) += dp2.at(i-1).at(j - k)) %= mod;
                }
                if (j - ns < 0) (dp2.at(i).at(j) += dp2.at(i-1).at(j - ns + N2)) %= mod;
                else (dp2.at(i).at(j) += dp2.at(i-1).at(j - ns)) %= mod;
            }
        }
    }
    ll ans=0;
    if(N == N2) {
        (ans +=dp1.at(ls-1).at(0)+dp2.at(ls-1).at(0))%=mod;
        (ans += mod-1)%=mod;
        cout<<ans<<endl;
    }else{
        if(N != 1) rep(i,9) (ans += dp1.at(ls-1).at(N*i)+dp2.at(ls-1).at(N*i))%=mod;
        else rep(i,81)(ans += dp1.at(ls-1).at(N*i)+dp2.at(ls-1).at(N*i))%=mod;
        (ans += mod-1)%=mod;
        cout<<ans<<endl;
    }
    /*rep(i,ls){
        rep(j,N2){
            cout<<dp1[i][j]<<' ';
        }
        cout<<endl;
    }
    rep(i,ls){
        rep(j,N2){
            cout<<dp2[i][j]<<' ';
        }
        cout<<endl;
    }*/
}


Measured memory_bytes: 16640
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{

    public static void Main()
    {
        int[] n = SpRead(' ').Select(a => int.Parse(a)).ToArray();
        int sa = n[1] - n[0];
        int ans = 0;
        for (int i = sa; i != 0;ans += i ,i--);
        Console.WriteLine(ans-n[1]);
    }
}


public class Atcoder
{
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static int LCM(int a, int b)
    {
        int c = a * b;
        if (a < b) Swap(ref a, ref b);
        int d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static string strReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static int intRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }

}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int n,Max,Min;

int Find(int Max,int Min)
{
	int MinMoney=INT_MAX,NowMoney=0;
	for(int i=Min;i<=Max;i++)
	{
		NowMoney=0;
		for(int j=1;j<=n;j++)
			NowMoney+=((a[j]-i)*(a[j]-i));
		MinMoney=min(NowMoney,MinMoney);
	}
	return MinMoney;
}
int main()
{
	Max=INT_MIN;
	Min=INT_MAX;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		Max=max(Max,a[i]);
		Min=min(Min,a[i]);
	}
	int money=Find(Max,Min);
	cout<<money<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    ll N;
    cin>>N;
    vector<pair<ll,ll>> d;
    for(ll i=1;i<=N;i++){
        ll x;
        cin>>x;
        d.push_back(make_pair(x,i));
    }
    sort(d.begin(),d.end());
    reverse(d.begin(),d.end());
    multiset<ll> S;
    S.insert(N+1);
    S.insert(0);
    S.insert(N+1);
    S.insert(0);

    ll ans=0;
    for(int i=0;i<d.size();i++){
        ll f=d.at(i).first, s=d.at(i).second;
        S.insert(s);
        auto itr=S.find(s);
        auto itl=itr;
        ll l1,l2,r1,r2;
        itr++; r1=*itr;
        itr++; r2=*itr;
        itl--; l1=*itl;
        itl--; l2=*itl;
        ans+=f*((l1-l2)*(r1-s) + (s-l1)*(r2-r1));
    }

    cout<<ans<<endl;
    

}

Measured memory_bytes: 6512
// g++ macro.cpp -std=c++14
#include <bits/stdc++.h> //STL include
typedef long long ll;// long long int
const ll INF = 10000000000;//INFinity
using namespace std;//namespace

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

//#define int long long // yabai

#define dump(x)  cout << #x << " = " << (x) << endl;// debug cout

#define FOR(i,a,b) for(int i=(a);i<(b);++i)// for macro
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define ALL(obj) (obj).begin(),(obj).end()// iterator

#define pb(a) push_back(a)//push_back
#define mp make_pair// make_pair


int main(){

    int a,b;
    string s;
    cin>>a>>b>>s;
    bool flag=true;
    if(s.size()!=a+b+1)flag=false;

    REP(i,s.size()){

        if(i==a&&s.at(i)!='-')flag=false;
        if(i!=a&&s.at(i)=='-')flag=false;
    }
    cout<<(flag?"Yes":"No")<<endl;

    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
ans=[0]*n
for i in range(n):
    num1=n-i
    num2=0
    for j in range((n//num1)-1):
        num2+=ans[num1*(j+2)-1]
    num2%=2
    ans[-1-i]=(num2+a[-1-i])%2
print(ans.count(1))
ans2=[]
for i in range(n):
    if ans[i]==1:
        ans2.append(i+1)
if len(ans2)!=0:
    print(*ans2)


Measured memory_bytes: 17804
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 n,q;
  string s;
  cin >> n >> q >> s;
  vpi data(q);
  rep(i,q) cin >> data[i].first >> data[i].second;
  vi place(n);
  in6 count = 0;
  repa(i,1,n) {
    if(s[i-1] == 'A' && s[i] == 'C') { count++; place[i] = count;}
    else place[i] = count;
  }
  rep(i,q) {
    cout << place[data[i].second-1] - place[data[i].first-1];
    hinata;
  }
}

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

int main(){
    int N;
    cin >> N;
    int a = N/100;
    N -= a*100;
    int b = N/10;
    N -= b*10;
    int c = N;
    if(a==7||b==7||c==7) cout <<"Yes"<<endl;
    else cout << "No" <<endl;
    
}


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

int main(){
    ll n,x,y=0;
    vector<ll> a;
    cin >> n;
    rep(i,3*n){
        cin >> x;
        a.push_back(x);//vectorへのcin
    } 
    
    sort(a.begin(), a.end(), greater<int>());

  //  rep(i, 3 * n) cout << a[i] << endl;

    rep(i,n){
        y += a[2 * i + 1];
    }
    cout << y << endl;
}

Measured memory_bytes: 6256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,a,b = map(int, input().split())

def sub(n,a,b):
    ps = list(range(a))
    for i in range(1, b):
        ps.append(-a*i)
    count = a+b-1
    if count==n:
        return ps
    for i in range(1,b):
        for j in range(1,a):
            ps.append(-a*i+j)
            count += 1
            if count==n:
                break
        if count==n:
            break
    return ps

if a+b>n+1:
    ans = -1
elif a*b<n:
    ans = -1
else:
    # a*b個の列
    ps = sub(n,a,b)
    pps = [(i+1,p) for i,p in enumerate(ps)]
    pps.sort(key=lambda x: x[1])
    ans = [item[0] for item in pps]
if ans==-1:
    print(ans)
else:
    write(" ".join(map(str, ans)))

Measured memory_bytes: 125476
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	M := nextInt()
	var pq priorityQueue
	heap.Init(&pq)
	for i := 0; i < N; i++ {
		heap.Push(&pq, &pair{first: nextInt(), second: 1})
	}
	for i := 0; i < M; i++ {
		heap.Push(&pq, &pair{second: nextInt(), first: nextInt()})
	}

	var ans int
	for i := 0; i < N; i++ {
		p := heap.Pop(&pq).(*pair)
		ans += p.first
		if p.second > 1 {
			p.second--
			heap.Push(&pq, p)
		}
	}

	fmt.Println(ans)
}

type pair struct {
	first, second int

	index int
}

type priorityQueue []*pair

func (pq priorityQueue) Len() int { return len(pq) }

func (pq priorityQueue) Less(i, j int) bool {
	if pq[i].first == pq[j].first {
		return pq[i].second > pq[j].second
	}

	return pq[i].first > pq[j].first
}

func (pq priorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *priorityQueue) Push(x interface{}) {
	n := len(*pq)
	p := x.(*pair)
	p.index = n
	*pq = append(*pq, p)
}

func (pq *priorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	p := old[n-1]
	p.index = -1
	*pq = old[0 : n-1]
	return p
}

func (pq *priorityQueue) update(p *pair, first, second int) {
	p.first = first
	p.second = second
	heap.Fix(pq, p.index)
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextFloat() float64 {
	sc.Scan()
	f64, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}

	return f64
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

// ---------- Util.


Measured memory_bytes: 12288
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    int n; cin >> n;
    string s; cin >> s;
    
    vector<int> w(n);
    vector<int> b(n);
    rep(i, n){
        if(s[i] == '.'){
            w[i] = 1, b[i] = 0;
        }else{
            w[i] = 0, b[i] = 1;
        }
    }
    vector<int> w_sum(n + 1);
    vector<int> b_sum(n + 1);

    b_sum[0] = 0, w_sum[0] = 0;
    rep(i, n + 1){
        w_sum[i] = w_sum[i - 1] + w[i - 1];
        b_sum[i] = b_sum[i - 1] + b[i - 1];
    }
    int ans;
    int ans_min = INFINITY;
    _rep(i, 1, n + 1){
        ans = b_sum[i - 1] + (w_sum[n] - w_sum[i]);
        ans_min = min(ans, ans_min);
    }
    cout << ans_min << endl;
}


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

#define INF INT_MAX
#define UINF UINT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

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

using namespace std;

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

    char n;
    cin >> n;

    cout << (char)(n+1) << endl;
    return 0;
}

Measured memory_bytes: 256
A, B = gets.split.map(&:to_i)

num = [0, 1, 1, 0]
ans = num[B%4] ^ num[(A-1)%4]

(1..50).each do |b|
    s = (B%2+1) * B[b] - ((A-1)%2+1) * (A-1)[b]
    ans += 1<<b if s%2 == 1
end
puts ans

Measured memory_bytes: 1788
a, b, x = map(int, input().split())
import math
h = x / (a * a)
if h > b / 2:
    w = a / 2
    ans = math.atan2(b - h, w) * 180 / math.pi
else:
    area = h * a
    w = 2 * area / b
    ans = math.atan2(b, w) * 180 / math.pi
print(ans)

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i32 = int32_t;
using i64 = int64_t;
constexpr char newl = '\n';

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
//#define F first
//#define S second
#define debug(x) cout << #x << ": " << x << '\n';

#if 1

constexpr int MOD = 1e9 + 7; // 1e9 + 7

// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;

  vector<int> a(N);
  F0R(i, N) {
    cin >> a[i];
  }
  
  // dp[i][j] := i + 1 人に j 個の飴を分けるときの方法の数
  vector<vector<int>> dp(N, vector<int>(K + 1));

  F0R(i, K + 1) {
    dp[0][i] = i <= a[0] ? 1 : 0;
  }

  FOR(i, 1, N) {
    dp[i][0] = 1;
    FOR(j, 1, K + 1) {
      if (j <= a[i]) {
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
        if (dp[i][j] >= MOD) dp[i][j] -= MOD;
      }
      else {
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i-1][j-a[i] - 1];
        if (dp[i][j] >= MOD) dp[i][j] -= MOD;
        if (dp[i][j] < 0) dp[i][j] += MOD;
      }
    }
  }

  cout << dp[N - 1][K];
}
#endif


Measured memory_bytes: 39808
import Control.Applicative ((<$>), (<*>))

main :: IO ()
main = solve <$> readLn <*> readLn <*> readLn <*> readLn <*> readLn >>= print

solve :: Int -> Int -> Int -> Int -> Int -> Int
solve a b c d e | a < 0 = (-a) * c + d + b * e
                | otherwise = (b-a)*e



Measured memory_bytes: 3620
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime> 
#define full(a) a.begin(), a.end()

#define sz(x) ((ll)(x).size())
#define ll long long
using namespace std;

ll inp() {
    ll n; cin >> n;
    return n;
}

void prvc(vector<ll> vec) {
    for (auto i : vec)cout << i << " ";
    cout << endl;
}

pair<int, int> hat(pair<int, int> l, pair<int, int> r) {
    pair<int, int> ans;
    if (l.first > r.first)swap(l, r);
    if (r.first > l.second) {
        return pair<int, int>(-1, -1);
    }
    ans.first = r.first;
    ans.second = min(l.second, r.second);
    return ans;
}

ll cnm(ll n, ll m) {
    ll k = n - m;
    if (k < m)std::swap(k, m);
    ll l1 = 1;
    for (int i = k + 1; i <= n; i++) {
        l1 *= i;
        if (l1 % m == 0)l1 /= m, m--;
    }
    for (int i = 2; i <= m; i++)
    {
        l1 /= i;
    }
    return l1;
}

void solve() {
    string n; cin >> n;
    int ans = 0;
    for (int i = 0; i < n.size(); i++)
    {
        ans += (n[i] - '0');
    }
    cout << ((ans % 9) ? "No" : "Yes");
}

int main()
{
    //ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //ll n; cin >> n;
    //while (n--)
        solve();

    return 0;
}

Measured memory_bytes: 3760
import java.util.*;

public class Main {
  public static void main(String[] args) {
    new Main().run();
  }

  private void run() {
    while(sc.hasNext()) {
      int n = sc.nextInt();
      int r = sc.nextInt();

      if(n == 0 && r == 0) break;

      int[] ps = new int[r];
      int[] cs = new int[r];
      for(int i = 0; i < r; i++) {
        ps[i] = sc.nextInt();
        cs[i] = sc.nextInt();
      }

      int x = n;
      for(int i = r - 1; i >= 0; i--) {
        int a = n - ps[i] - cs[i] + 1;
        if(x <= a) continue;
        else if(x <= n - cs[i]) x += cs[i];
        else x -= ps[i] - 1;
      }

      System.out.println(x);
    }
  }

  private final Scanner sc = new Scanner(System.in);
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ll = long long int;
using vec = vector<int>;
using P = pair<int,int>;
const int INF = 1e9+7;

int main() {
  ll n, q; cin >> n >> q;
  vector<P> v1, v2;
  v1.emplace_back(n-2, n-2);
  v2.emplace_back(n-2, n-2);

  ll sum = (n-2)*(n-2);

  rep(qi,q) {
    int q0, r; cin >> q0 >> r;
    r-=2;

    if (q0 == 1) {
      auto rit = lower_bound(v2.rbegin(), v2.rend(), P(r,0));
      sum -= rit->second;
      if (r < v1.back().second) {
        v1.emplace_back(rit->second, r);
      }
      // cout << rit->second << " ; ";
    } else {
      auto rit = lower_bound(v1.rbegin(), v1.rend(), P(r,0));
      sum -= rit->second;
      if (r < v2.back().second) {
        v2.emplace_back(rit->second, r);
      }
      // cout << rit->second << " ; ";
    }
    // for (P p : v1) {
    //   cout << p.first << "," << p.second << " ";
    // }
    // cout << "; ";
    // for (P p : v2) {
    //   cout << p.first << "," << p.second << " ";
    // }
    // cout << endl;
  }

  cout << sum << endl;
}


Measured memory_bytes: 5188
#include <iostream>
#include <algorithm>
using namespace std;
int m,a[100005],ans,in;
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>in;
		if(in>m) ans++;
		else a[in]++;
	}
	for(int j=1;j<=m;j++){
		if(a[j]>j) ans=ans+a[j]-j;
		if(a[j]<j) ans=ans+a[j];
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define rep(i,n) for(int i = 0;  i < n ; ++i)
#define REP(i,a,b) for(int i = a ; i <= b ; ++i)
#define filei freopen("input.txt", "r", stdin);
#define fileo freopen("output.txt", "w", stdout);
#define gooi cout<<"Case #"<<i+1<<" :";
#define s(n) scanf("%d",&n)
#define rev(i,n) for(int i = n ; i >= 0 ; --i)
#define REV(i,a,b) for(int i = a ; i >= b ; --i)
#define miN(a,b) (((a)<(b))?(a):(b))
#define sc(n) scanf("%c",&n)
#define tr(c,i) for(typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define INF 1000000000
#define pii pair<long long int,long long int>
#define pb(a) push_back(a)
#define F first
#define S second
typedef long long ll;
using namespace std;
void pre(){}
void solve(){
    string s,t;cin>>s>>t;
    ll ans = 0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]){
            ans++;
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}





Measured memory_bytes: 3884
#include<bits/stdc++.h>
using namespace std;
int main(){
//	static priority_queue< int, vector<int>, greater<int> > pq;
	static priority_queue<int> pq;
	long long ans=0;
	int i, n, m, x;
	
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++) {
		scanf("%d", &x);
		pq.push(x);
	}
	for(i=1; i<=m; i++) {
		x = pq.top();
		pq.pop();
		pq.push(x / 2);
	}
	while(!pq.empty()) {
		ans += pq.top();
		pq.pop();
	}
	printf("%lld\n", ans);
	
	return 0;
}

Measured memory_bytes: 892
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long int ll;
typedef vector< int > vi;
typedef pair< int, int > ii;
typedef vector< ii > vii;
typedef vector< ll > vll;
// #define DEBUG_MODE
#ifdef DEBUG_MODE
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(x) fprintf(stderr, "[%s = %d]\n", #x, x)
#else
	#define errp(...)
	#define dbg(x) 
#endif

int n, k;

double solve () {
	double p = 0;
	for (int i = k; i <= n; i++) p += 1;

	for (int i = 1; i <= min(n, k - 1); i++) {
		double t = 1;
		int x = i;
		while (x < k) { x *= 2; t *= 2; }
		p += (double)1 / t;
	}
	p /= n;
	return p;
}

int main () { 
#ifdef DEBUG_MODE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d", &n, &k);
	printf("%.12f\n", solve());
}

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


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

x2 = [i ** 2 for i in x]
ans = float('inf')
sum1 = sum(x)
sum2 = sum(x2)
for p in range(1, 101):
    cnt = sum2 + (sum(x) * (-1) * 2 * p) + (p**2*n)
    ans = min(ans, cnt)
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;
#define MOD 1000000007
#define EPS 10e-8

int main(){
    ll L,R,t;
    t=2018;
    cin >> L >> R;
    if(R-L>=2018){
        t=0;
    }
    else{
        if(L>2019){
            int d=L/2019*2019;
            L=L-d;
            R=R-d;
        }
        if(L%2019+R-L>=2019){
            t=0;
        }
        else{
            for(int i=L;i<=R-1;i++){
                for(int j=L+1;j<=R;j++){
                    if(t>(i*j)%2019){
                        t=(i*j)%2019;
                    }
                }
            }
        }
        
    }
    cout << t << endl;
}



Measured memory_bytes: 888
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int main(){

    int a;
    char cor[1123];

    scanf("%d", &a );
    scanf("%s", cor );

    if (a < 3200) {
        printf("red\n");
    } else
    printf("%s\n", cor);


return 0;
}


Measured memory_bytes: 128
from bisect import bisect
from bisect import bisect_left

_ = input()
l = input()
l = sorted(list(map(int, l.split())))
count = 0

for i in range(len(l)):
	for j in range(i+1, len(l)):
		c = l[i]+l[j]
		count += bisect_left(l,c) - (j+1)

print(count)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int INF = 1001001001;
int dp[1005][10007];
int main(){
   int h,n;
   cin >> h >> n;
   int a[n],b[n];
   rep(i,n) cin >> a[i] >> b[i];
   rep(i,1005)rep(j,10007) dp[i][j] = INF;
   dp[0][0] = 0;
   rep(i,n){
       rep(j,h+1){
           dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
           dp[i+1][min(j+a[i],h)] = min(dp[i+1][min(j+a[i],h)],dp[i+1][j]+b[i]);
       }
   }
   cout << dp[n][h] << endl;
}

Measured memory_bytes: 39552
#include <iostream>
#include<algorithm>
using namespace std;
#define debug(n) cout<<#n<<": "<<n<<'\n';
typedef long long ll;

int power(int x, unsigned int y) { 
    int res = 1;     // Initialize result 
    while (y > 0) { 
        if (y & 1)  res = res*x; 
        y = y>>1; // y = y/2 
        x = x*x;  // Change x to x^2 
    } 
    return res; 
}

int modpower(int x, unsigned int y, int p) {  
    int res = 1;     // Initialize result  
    x = x % p; // Update x if it is more than or  
    if (x == 0) return 0; // In case x is divisible by p; 
    while (y > 0) {  
        if (y & 1) res = (res*x) % p;  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  

int main() {
	//ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t=1;
 	//cin>>t;
	while(t--) {
	     int n,k;
	     cin>>n>>k;
	     int a[n],sum=0;
	     for(int i=0;i<n;i++) cin>>a[i];
	     sort(a,a+n);
	     for(int i=0;i<k;i++) sum+=a[i];
	     cout<<sum<<'\n';
	}    
	return 0;
}


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

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

  // ここにプログラムを追記
  int A=0;
  int i=0,Kaisuu=0,Min_Kaisuu=104857600;
  for (int i=0; i<N; i++) {
    Kaisuu = 0;
    cin >> A;
    while (true) {
      if (A % 2!=0) {
        break;
      }
      A/=2;
      Kaisuu++;
    }
    if (Min_Kaisuu > Kaisuu) {
      Min_Kaisuu = Kaisuu;
    }
  }
  cout << Min_Kaisuu << endl;
  return 0;
}


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

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

signed main() {
	int n;
	cin >> n;
	int a[200005];
	rep(i, n) {
		cin >> a[i];
		a[i] -= i;
	}
	sort(a, a + n);
	int ans = 0;
	rep(i, n) {
		ans += abs(a[i] - a[n / 2]);
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

class Main {
    static Scanner sc;
    public static void main(final String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sc = new Scanner(System.in);
        int numberOfPeople;
		try {
			numberOfPeople = Integer.parseInt(br.readLine());
		
        Long numberOfCoordinates[] = new Long[numberOfPeople];
        
        String string[] = br.readLine().split(" ");
        for (int i = 0; i < numberOfPeople; i++){
            numberOfCoordinates[i] = Long.parseLong(string[i]);
        }

        long output = Long.MAX_VALUE;

        for(int i = 0; i <= 100; i++){
            long cost = 0;
            for (int j = 0; j < numberOfPeople; j++){
                cost += Math.pow(numberOfCoordinates[j]-i,2);
            }
            output = Math.min(output,cost);
        }

        System.out.println(output);

    } catch (NumberFormatException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    }

    public static int findBaseK(int n, final int k) {
        if(n==0) return 1;

        int i = 0;
        while(n!=0){
            n = Math.floorDiv(n, k);
            i++;
        }


        return i;
    }

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

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

using namespace std;
set<long long>s;
void rec(long long cur){
    if(cur >= (long long)1e11 + 1 || s.find(cur) != s.end())return;
    s.insert(cur);
    for(int i = 0 ; i < 10; ++i){
        if(abs(cur%10 - i) < 2){
            rec(cur*10 + i);
        }
    }
}

int main() {
    rec(1);rec(2);rec(3);rec(4);rec(5);rec(6);rec(7);rec(8);rec(9);
    int n; cin>>n;
    vector<long long>v(s.begin() , s.end());
    cout<<v[n - 1]<<"\n";
}

Measured memory_bytes: 32000