akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int inf=10000000;

ll h,w,ans=0,white=0;
char lab[51][51];
int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int d[51][51];

int bfs()
{
  queue<P> que;
  rep(i,h+1)
  rep(j,w+1) d[j][i]=inf;

  que.push(P(1,1));
  d[1][1]=1;

  while(que.size())
  {
    P p=que.front();
    que.pop();
    if(p.first==w && p.second==h) break;

    rep(i,4)
    {
      int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<nx && nx<=w && 0<ny && ny<=h && lab[nx][ny]=='.' && d[nx][ny]==inf)
      {
        que.push(P(nx,ny));
        d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  return d[w][h];
}

int main()
{
  cin>>h>>w;
  for(int i=1;i<=h;i++)
  for(int j=1;j<=w;j++)
  {
    cin>>lab[j][i];
    if(lab[j][i]=='.') white++;
  }

  ans=bfs();
  if(ans==inf) ans=-1;
  else ans=white-ans;

  cout<<ans<<endl;
}

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

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

template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

typedef long long ll;

ll sodk(ll n){
  ll ret = 0;
  for (int i = 1; i*i <= n; ++i){
    ret += i*(i+n/i)*(n/i+1-i);
  }
  ll sq = sqrt(n);
  return ret-sq*(sq+1)*(2*sq+1)/6;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int n;  cin >> n;
  cout << sodk(n) << "\n";
  return 0;
}

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

int main(void){
    int N,T;
    int max;
    cin >> N >> T;
    vector<unsigned long> ti(N);
    max = N * T;
    for(int i = 0; i < N; i++){
        cin >> ti[i];
    }
    for(int i = 0; i < N; i++){
        if (i != N - 1 && ti[i + 1] - ti[i] < T){
            max = max - (T - (ti[i + 1] - ti[i]));
        }
    }
    cout << max << endl;
}


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

using namespace std;

int n,W;
long long w[101],v[101];
long long f[101][100001];

int main(){
	scanf("%d%d",&n,&W);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&w[i],&v[i]);
	for(int i=0;i<=n-1;i++){
		for(int j=0;j<=W;j++){
			f[i+1][j]=max(f[i+1][j],f[i][j]);
			if(j>=w[i+1])f[i+1][j-w[i+1]]=max(f[i+1][j-w[i+1]],f[i][j]+v[i+1]);
		}
	}
	for(int i=0;i<=W;i++)f[n][0]=max(f[n][i],f[n][0]);
	printf("%lld",f[n][0]);
	return 0;
}

Measured memory_bytes: 78464
#include <stdio.h>

int i , h , m , s ;

int main () {
	
	scanf ("%d" , &i);
	
	h=i/3600;
	
	m=(i%3600)/60;
	
	s=i-(3600*h)-(60*m);
	
	printf("%d:%d:%d\n" ,h , m ,s );
	
	return 0;
	
}



Measured memory_bytes: 2080
#include<stdio.h>
#include<string.h>
#define MAX 100010
int ans[MAX]={};

int main(){
  char str[MAX];
  scanf(" %s",str);
  int i;
  char temp='R';
  int count=0,j=0,len=strlen(str);
  for(i=0;i<len;i++) {
    if (temp==str[i]) {
      count++;
      continue;
    }
    if(temp=='R'){
      j=i;
      ans[j]+=count/2;
      ans[j-1]+=(count+1)/2;
    }else{
      ans[j-1]+=count/2;
      ans[j]+=(count+1)/2;
    }
    count=1;
    temp=str[i];
  }
  
  ans[j-1]+=count/2;
  ans[j]+=(count+1)/2;
  for(i=0;i<len;i++)
    printf("%d ",ans[i]);
  return 0;
}


/// confirm df==0 ///


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
//#include <stack>
#include <climits>
#include <map>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;

int n,m;
string s,t;

int gcd(int u, int v) {
    int r;
    while (v) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

int main() {
    cin >> n >> m;
    cin >> s >> t;
    int gc = gcd(n,m);
    ll aa = (ll)n*m/gc;
    int k = aa/n;
    int l = aa/m;
    for(ll i=0;i<aa;i+=k){
        if(i%l==0){
            if(s[i/k]!=t[i/l]){
                put("-1");
                return 0;
            }
        }
    }
    put(aa);
    return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

bool solve(ll x, ll base) {
	vector<ll> a(8);
	a[0] = 1;
	for (int i = 1; i < 8; i++) {
		if ((double)a[i - 1] * base >= 1e18 * 1.1) a[i] = 1e18 * 1.1;
		a[i] = a[i - 1] * base;
		// cout << a[i] << endl;
	}
	vector<ll> b(8);
	int N = 0;
	for (int i = 7; i >= 0; i--) {
		ll k = x / a[i]; x %= a[i];
		b[i] = k;
		if (k) N = max(N, i + 1);
	}
	rep(i, N) if (!b[i]) return false;
	string s = "FESTIVAL";
	string unko = "LAVITSEF";
	rep(i, N) rep(t, b[i] - 1) s.pb(unko[i]);
	for (int i = N - 2; i >= 0; i--)
		rep(t, base)
			s.pb(unko[i]);
	cout << s  << endl;
	return true;
}

int main() {
	ll x; cin >> x;
	random_device rd;
	mt19937 mt(rd());
	for (;;) {
		int base = 256 + mt() % 30;
		if (solve(x, base)) break;
	}
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;
const string sp=" ";

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    cin>>n;
    vp a(n);
    rep(i,n)cin>>a[i].se>>a[i].fi;
    sort(all(a));
    int t=0;
    rep(i,n){
        t+=a[i].se;
        if(t>a[i].fi){
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 3456
n=gets.to_i
aNs=gets.chomp.split.map(&:to_i)
bNs=gets.chomp.split.map(&:to_i)
cNs=gets.chomp.split.map(&:to_i)
total=0
beforeIndex = -1
aNs.each do |value|
  index = value - 1
  total += bNs[index]
  if beforeIndex != -1
    diff =  index - beforeIndex
    total += cNs[beforeIndex]  if diff == 1
  end
  beforeIndex = index
end
puts total

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

typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef vector< vector< vector<ll> > > vvvint;
typedef vector<string> vstring;
typedef vector< vector<string> > vvstring;
typedef vector<char> vchar;
typedef vector< vector<char> > vvchar;
typedef vector<long double> vdouble;
typedef vector< vector<long double> > vvdouble;
typedef vector< vector< vector<long double> > > vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ALL(obj) (obj).begin(), (obj).end()
// #define LLONG_MAX 9223372036854775806
#define MOD 1000000007
const double PI=3.14159265358979323846;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> T Ceil(T a, T b){return (a+b-1)/b;}

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

void printv(vint &v){
    for(auto e:v) cout<<e<<" ";
        cout<<endl;
    }
ll n,m,q;
vint a,b,c,d;
ll ans = 0;


void f(vint &v, ll minval){
    ll pos = v.size();
    if(pos == n){
        ll rtn = 0;
        rep(i,q){
            if(v[b[i]-1] - v[a[i]-1] == c[i]) rtn += d[i];
        }
        chmax(ans, rtn);
        return;
    }

    repf(i,minval, m+1){
        vint tmp = v;
        tmp.push_back(i);
        f(tmp, i);
    }

}

int main() {
    cout<<fixed<<setprecision(10);

    cin>>n>>m>>q;

    a.resize(q);b.resize(q);c.resize(q);d.resize(q);
    rep(i,q){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }

    vint v;
    f(v, 1);
    cout<<ans<<endl;

    return 0;

}

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

int findSumOfDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    int N;
    cin >> N;
    /*int res = 10000;
    if (N % 10 == 0) res = 10;
    else {
        for (int i = 0; i <= N; i++) {
            int A = i;
            int B = N - A;
            int Asum = findSumOfDigits(A);
            int Bsum = findSumOfDigits(B);
            if (Asum + Bsum < res) res = Asum + Bsum;
        }
    }
    cout << res << endl;*/
    
    if (N % 10 == 0) cout << 10 << endl;
    else cout << findSumOfDigits(N) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

int main() {
    ll N, L, T;
    cin >> N >> L >> T;
    ll X[N];
    ll W[N];
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> W[i];
    }
    ll w = W[0];
    ll num = 0;
    for (int i = 1; i < N; i++) {
        if (w == 1 && W[i] == 2) {
            ll dif = X[i] - X[0];
            if (2 * T >= dif) {
                num += (2 * T - dif) / L + 1;
            }
        } else if (w == 2 && W[i] == 1) {
            ll dif = L - (X[i] - X[0]);
            if (2 * T >= dif) {
                num -= (2 * T - dif) / L + 1;
            }
        }
    }
    ll XX[N];
    for (int i = 0; i < N; i++) {
        if (W[i] == 1) {
            XX[i] = (X[i] + T) % L;
        } else {
            XX[i] = ((X[i] - T) % L + L) % L;
        }
    }
    sort(XX, XX + N);
    // for (int i = 0; i < N; i++) {
    //     cout << XX[i] << endl;
    // }
    ll ans[N];
    num = (num % N + N) % N;
    if (w == 1) {
        ll id = (ll)(upper_bound(XX, XX + N, (X[0] + T) % L) - XX) - 1;
        id = (id % N + N) % N;
        //cout << id << endl;
        for (int i = 0; i < N; i++) {
            ans[num] = XX[id];
            num = (num + 1) % N;
            id = (id + 1) % N;
        }
    } else {
        ll id = (ll)(lower_bound(XX, XX + N, ((X[0] - T) % L + L) % L) - XX);
        //id = (id % N + N) % N;
        for (int i = 0; i < N; i++) {
            ans[num] = XX[id];
            num = (num + 1) % N;
            id = (id + 1) % N;
        }
    }
    for (int i = 0; i < N; i++) {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 4352
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 INT_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 INT_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<int>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define PI acos(-1)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 


int main()
{
	ll a,b,k,v;

	cin>>a>>b>>k;

	v = min(a,k);
	k = k - v;
	a=a-v;

	v = min(b,k);

	b = b - v;

	cout<<a<<" "<<b<<"\n";



	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ALL(a)  (a).begin(),(a).end()
 
const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;
 
template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}
 
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


int main(){
    // ll N,S,K;
    ll a,b,n;
    cin >> n >> a >>b ;

    cout << min(b,a*n);
}


Measured memory_bytes: 256
#バブルソート

length = int(input())
list = list(map(int, input().split()))

flag = 1
count = 0
while(flag):
    flag = 0
    for j in reversed(range(1, length)):
        if list[j] < list[j-1]:
            list[j], list[j-1] = list[j-1], list[j]
            flag = 1
            count += 1

result = ''
for l in list:
    result += str(l) + ' '

print(result[:-1])
print(count)


Measured memory_bytes: 5600
mod=1000000007
n,k=map(int,input().split())
s=int(n**0.5)
Num=[0]*(s+1)
for i in range(s,0,-1):
    Num[i]=i
    Num.append(n//i)
l=len(Num)
for i in range(1,l):
    Num[-i]=Num[-i]-Num[-i-1]
DP=[[0]*l for _ in range(k)]
DP[0]=Num[:]
for i in range(1,k):
    tmp=0
    for j in range(1,l):
        tmp+=DP[i-1][j]
        tmp%=mod
        DP[i][-j]=(tmp*Num[-j])%mod
ans=0
for i in DP[-1][1:]:
    ans+=i
    ans%=mod
print(ans)

Measured memory_bytes: 91272
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=200010;
int hd[N],to[M<<1],nxt[M<<1],ans[N];
int n,m,r,tot;
void add(int f,int t){
	to[++tot]=t;
	nxt[tot]=hd[f];
	hd[f]=tot;
}
void bfs(){
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		for(int i=hd[t],s;i;i=nxt[i]){
			s=to[i];
			if(!ans[s]&&s!=1) q.push(s),ans[s]=t,++r;
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d %d",&x,&y);
		add(x,y);add(y,x);
	}
	bfs();
	if(r==n-1){
		printf("Yes\n");
		for(int i=2;i<=n;++i) printf("%d\n",ans[i]);
	}
	else printf("No\n");
}

Measured memory_bytes: 7792
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
double acc=0;
bool vis[10];
int n;
pair<double,double> g[10];
double sqr(double x){return x*x;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>g[i].first>>g[i].second;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=i+1;j<=n;++j)
        {
            acc += sqrtl(sqr(g[i].first-g[j].first)+sqr(g[i].second-g[j].second))*2/n;
        }
    }
    printf("%.8f\n",acc);
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

template<typename T>
T mod(T a, T b){
    return (a + b) % b;
}

template<typename T>
T gcd(T a, T b){
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

// n を素因数分解
map<ll, ll> factor(ll n){
    map<ll, ll> mp;
    for (ll i = 2; i*i <= n; i++) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }

    if (n > 1) {
        mp[n]++;
    }

    return mp;
}

// 文字列に "hoge" が含まれているか
// string str = "hogepiyo";
// if (str.find("hoge") != string::npos) {
//     cout << "文字列が含まれています" << endl;
// }

// char to string
// char c = 'a';
// string str = {c};

void solve(){
    ll N;
    cin >> N;

    vector<ll> v(5);
    for (int i = 0; i < 5; i++) {
        cin >> v[i];
    }

    ll minval = *min_element(all(v));
    cout << ((N + minval-1) / minval) + 4 << endl;

    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


Measured memory_bytes: 256
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
//take care of precedence rule of operators 
//do not forget to change the sizes of arrays and value of contants and other things after debugging  
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define ld long double
#define pi acos(-1.0)
 
#define SZ(x)  (ll)(x.size())
 
//comment the below if not required
 
/*
 
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second
*/
 
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

//cout<<"Case #"<<c<<": "<<ans<<"\n" ;

const ll N = 2e5+1;

ll n,m,i,a,b,ans;
bool vis[N];
vector<ll> v[N];

ll dfs(ll node)
{
    vis[node]=1;

    ll tot=1;

    for(auto u : v[node])
    {
        if(!vis[u])
            tot += dfs(u);
    }

    return tot;

}

int main()
{

    cin>>n>>m;

    for(i=1;i<=m;++i)
    {
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }

    for(i=1;i<=n;++i)
    {
        if(!vis[i])
        {
            ans = max(ans,dfs(i));
        }
    }

    cout<<ans<<"\n";


    return 0;

}

Measured memory_bytes: 24136
a,b,k = map(int,input().split())
if 2*k>=b-a+1:
  for i in range(a,b+1):
    print(i)
else:
  for i in range(a,a+k):
    print(i)
  for i in range(b-k+1,b+1):
    print(i)

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

using ll_t = long long;
const int MAXN = 2000;

int a[MAXN];

ll_t solve(int n) {
  std::sort(a, a + n);
  ll_t res = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (i == j) continue;
      int max = a[i] + a[j];
      int min = a[j] > a[i] ? a[j] - a[i] : a[i] - a[j];
      int num = std::lower_bound(a, a + n, max) - a - 
                (std::lower_bound(a, a + n, min + 1) - a);
      if (min < a[i] && a[i] < max) --num;
      if (min < a[j] && a[j] < max) --num;
      // std::cout << a[i] << " " << a[j] << " min=" << min << " max=" << max << " num=" << num << std::endl;
      res += num;
    }
  }
  return res / 3;
}

int main() {
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) std::cin >> a[i];
  std::cout << solve(n) << std::endl;
  return 0;
}


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

using ll = long long;
using ull = unsigned long long;
using st = string;
using ch = char;
using db = double;
using bl = bool;
using vll = vector<long long>;
using vdb = vector<db>;
using vst = vector<st>;
using vch = vector<char>;
using vbl = vector<bl>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
#define mkp(a, b) make_pair(a, b) 
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;}
const ll mod = 1000000007;
const ll inf = 1LL << 60;
const db pi = acos(-1.0L);

int main(){
  ll n;
  cin >> n;
  vll a(n), b(n);
  rep(i, 0, n) cin >> a.at(i) >> b.at(i);
  sort(all(a)); sort(all(b));
  if(n % 2 == 0){
    ll amid = (a.at(n / 2) + a.at(n / 2 - 1));
    ll bmid = (b.at(n / 2) + b.at(n / 2 - 1));
    cout << bmid - amid + 1 << endl;
  }
  else{
    ll amid = a.at((n - 1) / 2);
    ll bmid = b.at((n - 1) / 2);
    cout << bmid - amid + 1 << endl;
  }
}

Measured memory_bytes: 6424
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace C
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = int.Parse(Console.ReadLine());
            var Scores = new int[N].Select(x => x = int.Parse(Console.ReadLine())).ToArray();
            var sum = Scores.Sum();
            if (sum % 10 != 0)
            {
                Console.WriteLine(sum);
                return;
            }
            Array.Sort(Scores);
            var x10 = true;
            for (var i = 0; i < Scores.Length; i++)
            {
                if (Scores[i] % 10 != 0)
                {
                    sum -= Scores[i];
                    x10 = false;
                    break;
                }
            }
            if (x10) sum = 0;
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 28148
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String[] str=sc.next().split(",");
			double x1=Double.parseDouble(str[0]);
			double y1=Double.parseDouble(str[1]);
			double x2=Double.parseDouble(str[2]);
			double y2=Double.parseDouble(str[3]);
			double xq=Double.parseDouble(str[4]);
			double yq=Double.parseDouble(str[5]);
			double x,y,d,e;
			if(x1==x2){
				y = yq;
				x = 2*x1 - xq;
			}else if(y1==y2){
				x = xq;
				y = 2*y1 - yq;
			}else{
				d = (y2-y1)/(x2-x1);
				e = y1-d*x1;
				x = (2*yq*d-2*d*e+xq-d*d*xq)/(d*d+1);
				y = (xq-x)/d+yq;
			}
			System.out.printf("%.6f %.6f\n",x,y);
		}
	}
}

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

int main(){
  int x,y;
  cin >> x >> y;

  for(int i = 0; i <= x; i++){
    int leg = i * 2 + (x - i) * 4;
    if(leg==y){
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 3600
a=int(input())
t=1
j=0
p=1
while a!=1:
  if a%2==0:
    a/=2
    t+=1
    continue
  else:
    a=(a-1)/2
    t+=1
for i in range(t):
  j+=p
  p*=2
print(j)
  



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

int main() {
  ll N;
  cin >> N;
  map<ll,ll,greater<ll>> length;
  for (ll i = 0; i < N; i++) {
    ll x;
    cin >> x;
    length[x] += 1;
  }
  
  ll sq = 1;
  for (auto m : length) {
    if (m.second >= 4 && sq == 1) {
      cout << (m.first)*(m.first) << endl;
      return 0;
    }
    if (m.second >= 2) {
      sq *= m.first;
      if (sq != m.first) {
        cout << sq << endl;
        return 0;
      }
    }
  }
  cout << 0 << endl;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
 
typedef long long ll;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}
 
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
 
#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e4 + 1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
oset s;

void build (int x)
{
    s.insert(x);
    if (x > 3234566667) return;
    
    int d = x % 10;
    if (d == 0) build(10*x), build(10*x + 1);
    else if (d == 9) build(10*x + 9), build(10*x + 8);
    else build(10*x + d), build(10*x + d + 1), build(10*x + d - 1);
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	read(k);
	FOR (i, 1, 9) build(i);
	cout << *s.find_by_order(k - 1);
}




Measured memory_bytes: 18432
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cmath>

typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

// 配列をすべて同じ値で埋める
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

using namespace std;

int main(void) {
    int n;
    cin >> n;
    int a[n+1];
    bool pushed[n+1];

    REP(i, n) {
        cin >> a[i+1];
        pushed[i+1] = false;
    }

    int pos = 1;
    int cnt = 0;
    while (true) {
        if (pushed[pos]) {
            cout << "-1" << endl;
            break;
        }
        cnt++;
        pushed[pos] = true;
        pos = a[pos];
        if (pos == 2) {
            cout << cnt << endl;
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 768
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XYZ):
    ans = 0
    for i, j, k in product([-1, 1], [-1, 1], [-1, 1]):
        ans = max(ans,
                  sum(
                      sorted(
                          [i * x + j * y + k * z for x, y, z in XYZ],
                          reverse=True)[:M]))
    return ans


def main():
    N, M = read_int_n()
    XYZ = [read_int_n() for _ in range(N)]

    print(slv(N, M, XYZ))


if __name__ == '__main__':
    main()


Measured memory_bytes: 8004
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    int N;
    cin >> N;
    int A[N];
    rep(i,N) cin >> A[i];
    sort(A,A+N);
    int count=0,kind=1;
    rep(i,N-1) if(A[i+1]==A[i]) count++;
    rep(i,N-1) if(A[i]!=A[i+1]) kind++;
    cout << kind-count%2 << endl;
}

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

int main() {
  int n;
  cin >> n;
  bool good = true;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (a % 2 == 0) {
      if (!(a % 3 == 0 || a % 5 == 0)) {
        good = false; break;
      }
    }
  }
  if (good) {
    cout << "APPROVED";
  }
  else {
    cout << "DENIED";
  }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>

using namespace std;
#define int long long
/*                      */    //#undef int
#define INF 1000000009
#define INFL 1000000000000000018ll
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define mk make_pair
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef priority_queue<PA, vector<PA>, greater<PA> >PQG;

int N, M , S, T;
struct edge
{
    int to, cost1, cost2;
};
vector<edge> G[100010];
int d[100010][2];
PQG que[2];

int s[2], dp[100010];

signed main()
{
    cin >> N >> M >> S >> T;
    s[0] = S;
    s[1] = T;
    for(int i = 0; i < M; i++){
        int a, b, c, D;
        cin >> a >> b >> c >> D;
        G[a].pb({b, c, D});
        G[b].pb({a, c, D});
    }
    for(int i = 1; i <= N; i++){
        for(int j = 0; j < 2; j++){
            d[i][j] = INFL;
        }
    }
    for(int k = 0; k < 2; k++){
        que[k].push(mk(0, s[k]));
        d[s[k]][k] = 0;
        while(!que[k].empty()){
            int dis = que[k].top().fi;
            int pos = que[k].top().se;
            que[k].pop();
            if(d[pos][k] < dis)continue;
            for(int i = 0; i < (int)G[pos].size(); i++){
                edge e = G[pos][i];
                int cost[2];
                cost[0] = e.cost1;
                cost[1] = e.cost2;
                if(d[e.to][k] > dis + cost[k]){
                    d[e.to][k] = dis + cost[k];
                    que[k].push(mk(d[e.to][k], e.to));
                }
            }
        }
    }
    dp[N] = d[N][0] + d[N][1];
    for(int i = N - 1; i >= 1; i--){
        dp[i] = min(d[i][0] + d[i][1], dp[i + 1]);
    }
    for(int i = 1; i <= N; i++){
        cout << 1000000000000000ll - dp[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 14200
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;

import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		long[] a = new long[2*n];
		long sum = 0;
		long[] half = new long[2];
		for(i=0;i<n;i++) {
			a[n+i] = a[i] = parseLong(sc.next());
			sum += a[i];
			if(i!=0) {
				half[i%2]+=a[i];
			}
		}
		sc.close();
		PrintWriter pw = new PrintWriter(out);
		for(i=0;i<n;i++) {
			pw.print(sum-2*half[(i+1)%2]);
			pw.print(" ");
			half[(i+1)%2]+=(-a[i+1]+a[n+i]);
		}
		pw.flush();
	}
}


Measured memory_bytes: 47608
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int K = sc.nextInt();
		
		boolean[][] squares = new boolean[H][W];
		for(int i = 0; i < H; i++) {
			String row = sc.next();
			for(int j = 0; j< W; j++) {
				squares[i][j] = row.charAt(j) == '#';
			}
		}
		int chooseWay = 0;
		for(int maskR = 0; maskR < (1<<H) - 1;maskR++) {
			for(int maskC = 0; maskC < (1<<W) - 1; maskC++) {
				int blackNum = 0;
				for(int i = 0; i < H; i++) {
					for(int j = 0; j < W; j++) {
						if((maskR & 1<<i) == 0 && (maskC & 1<<j) == 0 && squares[i][j]) {
							blackNum++;
						}
					}
				}
				if(blackNum == K) {
					chooseWay++;
				}
			}
		}
		System.out.println(chooseWay);
	}

}


Measured memory_bytes: 35664
{-# LANGUAGE Strict #-}
import qualified Data.ByteString.Char8 as B
import           Data.List             (unfoldr)


main :: IO ()
main = do
  [n, m] <- readIntsLn
  as <- readIntsLn
  print $ solve n m as

solve :: Int -> Int -> [Int] -> Int
solve n _ as = max (-1) $ n - sum as

readIntsLn :: IO [Int]
readIntsLn = unfoldr (B.readInt . B.dropWhile (== ' ')) <$> B.getLine


Measured memory_bytes: 4764
N=int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

if sum(A)<sum(B):
    print(-1)
else:
    C = [B[i]-A[i] for i in range(N)]
    C.sort()
    ans=0
    task=0
    i=-1
    while C[i]>0:
        ans+=1
        task+=C[i]
        i-=1

    i=0
    while task>0:
        ans+=1
        task+=C[i]
        i+=1
    print(ans)


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

#define int long long
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define eb emplace_back
#define dump(x) cout << #x << " = " << (x) << endl
#define chk() cout << "now" << endl;
#define ALL(x) (x).begin(), (x).end()
#define SORT(c) sort((c).begin(), (c).end())
#define SORTG(c) sort(ALL(c), greater<int>());
#define fi first
#define se second
int INF = 1e9 + 7;

typedef pair<int, int> P;
typedef vector<int> vi;

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 n;
vi a, b;

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

  cin >> n;
  rep(i, 0, n) {
    int A;
    cin >> A;
    a.pb(A);
    b.pb(A);
  }
  SORTG(a);
  if (a[0] == a[1]) {
    rep(i, 0, n) { cout << a[0] << endl; }
  } else {
    rep(i, 0, n) {
      if (b[i] == a[0])
        cout << a[1] << endl;
      else
        cout << a[0] << endl;
    }
  }

  return 0;
}


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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
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;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	int N, M, H[100000]; cin >> N >> M;
	vector<vint> G(N);
	REP(i, N) cin >> H[i];
	REP(i, M){
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].eb(b); G[b].eb(a);
	}
	int ans = 0;
	REP(i, N){
		bool yes = 1;
		for(int nx: G[i]){
			yes &= (H[i] > H[nx]);
		}
		if(yes) ans++;
	}
	cout << ans << ln;
}

Measured memory_bytes: 8744
/*
 * atcoder/abc126/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * それぞれの目aが出る事象の確率P(a) = 1/N
 * P(a)において勝つ確率P(b)（得点がK以上になる確率） = (1/2) ** pow_count if a < K
 *                                                   = 1 if a >= K
 * 答え = sum(P(a) * P(b) | a = from 1 to N)
 */

double log2(int n) {
  return log(n) / log(2);
}

int N, K;
void solve() {
  cin >> N >> K;
  double ans = 0.0;
  loop(n,1,N+1) {
    if (n<K) {
      int n_ = n, count = 0;
      while (n_ < K) {
        n_ *= 2; count++;
      }
      ans += (1/(double)N) * pow(0.5, count);
    }
    else ans += (1/(double)N);
  }
  cout << ans << endl;
}
int main() {
  cout.precision(15);
  cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
/**
 * Title: C - Traveling Salesman around Lake
 * Url: https://atcoder.jp/contests/abc160/tasks/abc160_c
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

    int k, n; cin >> k >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    int ans = k;
    for(int i=0; i<n; i++) {
        if(i==n-1) {
            ans = min(ans, a[i]-a[0]);
        } else {
            ans = min(ans, k-a[i+1]+a[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmin(T& a,T b){if(a > b){a = b;return 1;}return 0;}

const long long INF = 1LL << 60;


int main(){
    int n;
    cin >> n;
    vector<int> ans(n+1,1e9);
    for (int i = 0;i < n;i++) ans[i] = 10010;
    ans[0] = 0;
    for (int i = 0;i < n;i++){
        ans[i+1] = min(ans[i+1],ans[i]+1);

        int six = 6;
        while(i + six <= n){
            ans[i+six] = min(ans[i+six],ans[i] + 1);
            six *= 6;
        }
        int nine = 9;
        while(i+nine <= n){
            ans[i+nine] = min(ans[i+nine],ans[i]+1);
            nine *= 9;
        }

    }
    cout << ans[n] << endl;

}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <typeinfo>
using namespace std;
using ll = long long;

int main() {
	
	string s;
	ll k;
	cin >> s >> k;
	ll size = s.size();
	
	for (int i = 0; i < size; i++)
	{
		if (s.substr(i, 1) == "1")
			k--;
		else
		{
			cout << s[i] << endl;
			return 0;
		}

		if (k == 0)
		{
			cout << s[i];
			return 0;
		}
	}
	
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))

ans = 1
d = 0
for i in range(1,n):
    diff = A[i] - A[i-1]
    if not d:
        d = diff
    elif d*diff < 0:
        d = 0
        ans += 1
print(ans)

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

using namespace std;

int main(void){

    int N, a;
    cin >> N;
    //int* A = new int[N];
    vector<int> A(N);
    for(int i = 0; i < N; i++){
        cin >> a;
        A[a - 1] = i + 1;
    }
/*
    for(int i = 1; i <= N; i++){
        for(int j = 0; j < N; j++){
            if(i == A[j]){
                cout << j + 1 << " ";
                break;
            }
        }
    }
    */
   for(int i = 0; i< N; i++){
       cout << A[i] << " ";
   }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1152
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let mut antena = vec![];
  for _ in 0..5 {
    let a = read::<i32>();
    antena.push(a);
  }

  let k = read::<i32>();
  let mut answer = true;

  for i in 0..4 {
    for j in i + 1..5 {
      let b = antena[i];
      let c = antena[j];
      if c - b > k {
        answer = false;
        break;
      }
    }

  }

  if answer {
    println!("Yay!")
  } else {
    println!(":(")
  }
}



Measured memory_bytes: 4352
import sys
import math
n = int(sys.stdin.readline().strip())
if n % 2 != 0:
    print(0)
    sys.exit(0)
down = 10
accum = 0
while True:
    crt = n // down
    if crt < 1:
        break
    accum += crt
    down *= 5
print(accum)

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

using namespace std;
typedef long long lint;

lint l_ceil(lint a, lint b)
{
    return (lint)ceil((long double)a / b);
}
int main(void)
{
    lint a[5];
    lint N;
    cin >> N;
    for(int i = 0; i < 5; i++){
        cin >> a[i];
    }
    lint sum = 0;
    lint times = l_ceil(N, a[0]);
    lint max = times;
    for(int i = 1; i < 5; i++){
        times = l_ceil(N, a[i]);
        if(max < times){
            max = times;
        }
    }
    cout << max + 4 << endl;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int n, a[200000],maxv1=0,maxv2=0,maxel; cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		if (maxv1 < a[i]) {
			maxv1 = a[i];
			maxel = i;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (i != maxel)
			if (maxv2 < a[i]) maxv2 = a[i];
	}
	for (int i = 0; i < n; ++i) {
		if (i != maxel) cout << maxv1 << endl;
		else cout << maxv2 << endl;
	}
	return 0;
}

Measured memory_bytes: 2432
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int k = sc.nextInt();
        int[] T = new int[n];
        for(int i=0;i<n;i++) T[i]=sc.nextInt();
        Arrays.sort(T);
        int left = 0;
        int ans=0;
        while(left<n){
            int right = left;
            while(right<n&&T[right]-T[left]<=k&&right-left+1<=c) right++;
            ans++;
            left=right;
        }
        System.out.println(ans);
    }
}


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

typedef long long ll;

ll f(ll x) {
    ll ret;
    if (x % 4 == 0 || x % 4 == 3) ret = 0;
    else ret = 1;
    int i = 1;
    while ((1LL << i) <= x) {
        if (x % (1LL << (i + 1)) >= (1LL << i) && x % 2 == 0) ret+= (1LL << i); 
        i++;
    }
    return ret;
}

int main() {
    ll A, B;
    cin >> A >> B;
    if (A == 0) cout << f(B) << "\n";
    else cout << (f(A - 1) ^ f(B)) << "\n";
}

Measured memory_bytes: 256
from collections import deque


def bfs(start, goal):
    q = deque([[start]])
    visited = set()
    while q:
        path = q.popleft()
        i, j = path[-1]
        if (i, j) == goal:
            return path
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                continue
            if (ni, nj) not in visited:
                q.append(path + [(ni, nj)])
                visited.add((ni, nj))
    return []


H, W = map(int, input().split())
field = [input() for _ in range(H)]
shortest_path = bfs((0, 0), (H - 1, W - 1))
if shortest_path:
    print(sum(v == "." for row in field for v in row) - len(shortest_path))
else:
    print(-1)


Measured memory_bytes: 9488
import sys
def input():
    return sys.stdin.readline()[:-1]

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

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Measured memory_bytes: 111836
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;
//typedef pair<int,int> P;
int const INF=1001001001;
ll const LINF=1001001001001001001;
ll const MOD=1000000007;

int N;
string X;

int popcount(int n){
    int res=0;
    while(n>0){
        res+=n%2;
        n/=2;
    }
    return res;
}

int f(int n,int cnt){
    if(n==0) return 1;
    n%=cnt;
    return f(n,popcount(n))+1;
}

int main(){
    cin>>N>>X;

    int cnt=0;
    rep(i,N) cnt+=X[i]-'0';

    int plus=0, minus=0;
    rep(i,N) plus=(plus*2+(X[i]-'0'))%(cnt+1);
    if(cnt>1) rep(i,N) minus=(minus*2+(X[i]-'0'))%(cnt-1);
    //cout<<plus<<' '<<minus<<'\n'<<endl;
    
    vector<int> tmpp(N+1); tmpp[N]=0;
    vector<int> tmpm(N+1); tmpm[N]=0;
    rep(i,N) tmpp[N-i-1]=(tmpp[N-i]*2+1)%(cnt+1);
    if(cnt>1) rep(i,N) tmpm[N-i-1]=(tmpm[N-i]*2+1)%(cnt-1);
    //rep(i,N) cout<<tmpp[i]<<endl;cout<<endl;
    //rep(i,N) cout<<tmpm[i]<<endl;cout<<endl;

    rep(i,N){
        int n=0;
        int diff=0;
        if(X[i]=='0'){
            diff=(tmpp[i]-tmpp[i+1]+cnt+1)%(cnt+1);
            n=(plus+diff+cnt+1)%(cnt+1);
        }else if(cnt>1){
            diff=(tmpm[i]-tmpm[i+1]+cnt-1)%(cnt-1);
            n=(minus-diff+cnt-1)%(cnt-1);
        }else{
            cout<<0<<endl;
            continue;
        }
        //cout<<diff<<' '<<n<<endl;
        //cout<<n<<' '<<popcount(n)<<endl;
        int ans=f(n,popcount(n));
        cout<<ans<<endl;//cout<<endl;
    }
}

Measured memory_bytes: 5236
S=input()
A=[0 for x in range(len(S))]

if S[0]=="A" or S[0]=="T" or S[0]=="C" or S[0]=="G":
  A[0]=1

for i in range(1,len(S)):
  if S[i]=="A" or S[i]=="T" or S[i]=="C" or S[i]=="G":
    A[i]=A[i-1]+1
  else:
    A[i]=0
    
print(max(A))

Measured memory_bytes: 3064
N = int(input())
P = [int(input()) for _ in range(N)]

# ans = N - (1,2,3 のように連続する最長の部分列(飛ばしてOK)の長さ)

memo = {}
for p in P:
  if p-1 in memo:
    memo[p] = memo[p-1] + 1
  else:
    memo[p] = 1

print(N - max(memo.values()))

Measured memory_bytes: 35024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        cout << s << endl;
        cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 256
LI = lambda: list(map(int, input().split()))

N = int(input())
A = [int(input()) for _ in range(N)]


def main():
    a = 1
    for i in range(N + 1):
        if a == 2:
            print(i)
            return 0
        a = A[a - 1]
    print(-1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 13056