akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int > v(n);
    
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        }
    
    int l=v[0];
    int r=v[0];
    
    for(int i=0;i<n;i++)
    {
        l=min(l,v[i]);
        r=max(r,v[i]);
        }
    int ans=10000000;
    for(int i=l;i<=r;i++)
    {
        int cost=0;
        
        for(int j=0;j<n;j++)
        {
            cost+= (v[j]-i)*(v[j]-i);
        }
        ans=min(ans,cost);
        
        
    }
    cout<<ans<<endl;
    
    
    
}


Measured memory_bytes: 256
#!/usr/bin/env python3

data1=input()
data2=input()
n=data1.split(" ")
a=data2.split(" ")
c={}
count = 0
for i in range(int(n[0])):
    if a[i] in c:c[a[i]] += 1
    else:c[a[i]] =1
c = sorted(c.items(), key = lambda x:x[1])
for i in range(len(c)-int(n[1])):
    count += c[i][1]
print(count)

Measured memory_bytes: 45064
#include<iostream>
#include<math.h>

using namespace std;

int main(void) {

	double n;
	int ans;
	
	cin >> n;

	if (fmod(n, 1000) == 0 || n == 0) {

		cout << 0;

	}
	else {

		ans = 1000 - fmod(n, 1000);
		cout << ans;

	}


	return 0;
}

Measured memory_bytes: 3200
/** 
 *  Author : Parth Prajapati
 * 	Institute : Pandit Deendayal Petroleum University
**/
#include<bits/stdc++.h>

using namespace std; 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,i,cnt=0;
    double sum = 0;
    cin>>n>>m;
    vector<int> a(n);
    for(i=0;i<n;++i)
    {
        cin>>a[i];
        sum += a[i];
    }
    sum /= (4*m);
    //cout<<sum<<" ";
    for(i=0;i<n;++i)
    {
        if(a[i] >= sum) ++cnt;
    }
    if(cnt >= m)    cout<<"Yes";
    else    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(0>=a&&0<=b)
        cout<<"Zero\n";
    else
        if(a>0&&b>0)
            cout<<"Positive\n";
        else{
            a=abs(a);
            b=abs(b);
            if((b-a)%2==0)
                cout<<"Negative\n";
            else
                cout<<"Positive\n";
        }
    return 0;
}

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

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int A, B, C, K; cin >> A >> B >> C >> K;
    int ans = 0;
    ans += min(A, K);
    K -= min(A, K);
    K -= min(B, K);
    ans -= min(C, K);
    cout << ans << endl;
}

Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <math.h> 

using namespace std;



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

	long long  n, i, j, k, ans, x, limit = 2E18;
	long double xx;
	cin >> n;
	vector<long long> a(n);
	bool haszero = false;
	for (i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 0) haszero = true;
	}

	if (haszero) ans = 0;
	else {
		ans = 1;
		for (i = 0; i < n; i++) {
			x = a[i];
			xx = 1.0 * x * ans;
			if (xx > limit) {
				ans = -1; break;
			}
			ans *= x;
		}
		if (ans > 1000000000000000000) ans = -1;
	}

	cout << ans << "\n";


	return 0;
}




Measured memory_bytes: 3992
a=int(input())
li=[0,0,0,0]#ac,wa,tle,re
for i in range(a):
  str=input()
  if str=="AC":
    li[0]+=1
  elif str=="WA":
    li[1]+=1
  elif str=="TLE":
    li[2]+=1
  elif str=="RE":
    li[3]+=1
    
print("AC x",li[0])
print("WA x",li[1])
print("TLE x",li[2])
print("RE x",li[3])

  

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

n, m = map(int,input().split())
A = list(map(int, input().split()))
num = sum(A)
bound = num * 1 / 4 / m
ans = 0
for a in A:
    if a >= bound:
        ans += 1
if ans >= m:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep1(i, n) for (int i = 1; i < n; ++i)
#define pb push_back
#define mp make_pair
#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)
ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

const string YES = "Yes";
const string NO = "No";

void solve(long long N, std::vector<long long> H) {
  // main coding
  H[0]--;
  rep1(i,N){
    if(H[i]-H[i-1]>0) H[i]--;
    else if(H[i]-H[i-1]==0) continue;
    else{
      cout<<NO<<endl;
      return;
    }
  }
  cout<<YES<<endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> H(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &H[i]);
  }
  solve(N, std::move(H));
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;

int main (){
  int N; ll x;
  cin >> N >> x;
  ll a[N];
  ll ans=0;
  cin >> a[0];
  if(a[0]>x){
    ans+=a[0]-x;
    a[0]=x;
  }
  for (int i=1;i<N;i++){
    cin >> a[i];
    if(a[i]+a[i-1]>x){
      ans+=a[i]+a[i-1]-x;
      a[i]=x-a[i-1];
    }
  }
  cout << ans;
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (__typeof(a) i = (a); i < (b); ++i)
#define iter(it, c) \
  for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = ~(1 << 31);

#define sc second
#define fs first
#define pb push_back

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T>
T smod(T a, T b) {
  return (a % b + b) % b;
}
// vim: cc=60 ts=2 sts=2 sw=2:

int h[100'050];
int memo[100'050];

ll dp(int at) {
  if (at == 0) return 0;
  if (at == -1) return INF;
  if (memo[at] != -1) return memo[at];
  ll bst = min(dp(at - 1) + abs(h[at] - h[at - 1]),
               dp(at - 2) + abs(h[at] - h[at - 2]));
  return memo[at] = bst;
}

int main() {
  // code
  memset(memo, -1, sizeof(memo));

  int n;
  cin >> n;

  rep(i, 0, n) cin >> h[i];

  cout << dp(n - 1) << endl;

  // codend
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
typedef long long ll;
const ll INF = 1e+18;

int main(){
    int A,B,Q;
    cin >> A >> B >> Q;
    vector<ll> s(A+2),t(B+2);
    s[0]=-1e+11;
    t[0]=-1e+11;
    s[A+1]=1e+11;
    t[B+1]=1e+11;
    
    rep2(i,1,A+1) cin >> s[i];
    rep2(i,1,B+1) cin >> t[i];

    vector<ll> X(Q);
    rep(i,Q) cin >> X[i];
    ll s1,s2,t1,t2;
    rep(i,Q){
        ll ans=INF;
        ll ans_s=INF;
        ll ans_t=INF;
        ll x=X[i];

        // s1通る時
        auto itr = lower_bound(s.begin(),s.end(),x);
        s1=*itr;
        s2=*(itr-1);
        if(abs(s1-x)>abs(s2-x)){
            swap(s1,s2);
            ans_s=abs(s1-x);
            auto itr = lower_bound(t.begin(),t.end(),s1);
            t1=*itr;
            t2=*(itr-1);
            if(t1>x) ans_s+=min(abs(s1-t1),abs(s1-t2));
        }else{
            ans_s=abs(s1-x);
            auto itr = lower_bound(t.begin(),t.end(),s1);
            t1=*itr;
            t2=*(itr-1);
            if(t2<x) ans_s+=min(abs(s1-t1),abs(s1-t2));
        }

        // t1通る時
        itr = lower_bound(t.begin(),t.end(),x);
        t1=*itr;
        t2=*(itr-1);
        if(abs(t1-x)>abs(t2-x)){
            swap(t1,t2);
            ans_t=abs(t1-x);
            auto itr = lower_bound(s.begin(),s.end(),t1);
            s1=*itr;
            s2=*(itr-1);
            if(s1>x) ans_t+=min(abs(t1-s1),abs(t1-s2));
        }else{
            ans_t=abs(t1-x);
            auto itr = lower_bound(s.begin(),s.end(),t1);
            s1=*itr;
            s2=*(itr-1);
            if(s2<x) ans_t+=min(abs(t1-s1),abs(t1-s2));
        }
        ans=min(ans_s,ans_t);
        cout << ans << endl;
    }
}


Measured memory_bytes: 3712
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long l = sc.nextLong();
    long r = sc.nextLong();
    long ans = 0;
    if((r - l) <= 2019) {
      long t = 2019;
      for(long i = l; i < r; i++) {
        for(long j = i + 1; j <= r; j++) {
          long i2 = (i % 2019);
          long j2 = (j % 2019);
          t = Math.min(t, (i2 * j2) % 2019);
        }
      }
      ans = t;
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 35536
import java.util.Scanner;

class Main{


	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);			//文字の入力
		int a = sc.nextInt();
		String S1 =sc.next();
		String S2 =sc.next();
		long mod = 1000000007;


		long ans = 0L;

		if(a ==1){
			System.out.println(3);
			return;

		}
		if(a == 2){
			System.out.println(6);
			return;

		}
		if(a == 3){
			if(S1.charAt(1) == S2.charAt(1)){
				System.out.println(12);
			}else{
				System.out.println(6);
			}
			return;

		}

 
		long form = 0;
		int start = 0;

		if(S1.charAt(0) == S1.charAt(1)){

			if(S1.charAt(2)==S1.charAt(3)){
				ans = 18L;
				form = 2;
				start = 4;

			}else{
				ans =6L;
				form = 1;
				start = 3;
			}			
		}else{
			if(S1.charAt(1)==S1.charAt(2)){
				ans = 6L;
				form = 2;
				start = 3;

			}else{
				ans = 6L;
				form = 1;
				start = 2;
			}
		}

		for(int i = start;i < S1.length()-1;i++){

			if(form == 2){				//今、横型
				if(S1.charAt(i) == S1.charAt(i+1)){			//次、横型
					ans *= 3L;
					form = 2;
					i++;

				}else{						//次、たて型
					ans *= 1L;
					form = 1;


				}
			}else{				//今、縦型
				if(S1.charAt(i) == S1.charAt(i+1)){
					ans *= 2L;
					form = 2;
					i++;

				}else{
					ans *= 2L;
					form = 1;

				}
			}
		}

		if(S1.charAt(a-1) == S2.charAt(a-1)){
			if(form == 1){
				ans *= 2L;
			}

		}

		System.out.println(ans%mod);



	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), cost(n+1), ans(n);
    rep(i, n)cin >> a.at(i);
    cost.at(0) = abs(a.at(0));
    REP(i, n-1){
        cost.at(i) = cost.at(i-1) + abs(a.at(i) - a.at(i-1));
    }
    cost.at(n) = cost.at(n-1) + abs(a.at(n-1));
    a.push_back(0);
    a.insert(a.begin(), 0);
    REP(i, n){
        if(a[i-1] > a[i] && a[i] < a[i+1])ans.at(i-1) = cost[n] - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]);
        else if(a[i-1] < a[i] && a[i] > a[i+1])ans.at(i-1) = cost[n] - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]);
        else ans.at(i-1) = cost[n];
    }
    rep(i, n)cout << ans.at(i) << endl;
}

Measured memory_bytes: 2424
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        ret = dict()
        for i in range(self.n):
            r = self.find(i)
            if r in ret:
                ret[r].append(i)
            else:
                ret[r] = [i]
        return ret

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():

    N, M = in_nn()
    uni = UnionFind(N)

    for i in range(M):
        a, b = in_nn()
        a, b = a - 1, b - 1
        uni.union(a, b)

    roots = uni.roots()

    ans = 0
    for r in roots:
        ans = max(ans, uni.size(r))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 82604
import sys
import heapq

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())

INF = 10 ** 18


def warshall_floyd(V, cost):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] != INF and cost[k][j] != INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


def main():
    N, M = in_nn()
    cost = [[INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        cost[i][i] = 0

    edge = []
    for i in range(M):
        a, b, c = in_nn()
        a, b = a - 1, b - 1
        edge.append((min(a, b), max(a, b), c))
        cost[a][b] = c
        cost[b][a] = c

    warshall_floyd(N, cost)

    ans = set()
    for i in range(N):
        for j in range(i + 1, N):
            for e in edge:
                a, b, c = e
                if cost[i][j] == cost[i][a] + c + cost[b][j]:
                    ans.add((a, b))
                elif cost[i][j] == cost[i][b] + c + cost[a][j]:
                    ans.add((a, b))

    print(M - len(ans))


if __name__ == '__main__':
    main()


Measured memory_bytes: 68612
import sys
_input = sys.stdin.readline


def resolve():
    N = int(_input())
    T = [list(map(int, _input().split())) for _ in range(N)]
    t, x, y = 0, 0, 0
    for next_t, next_x, next_y in T:
        diff_xy = abs(x - next_x) + abs(y - next_y)
        diff_t = next_t - t
        if diff_xy > diff_t or (diff_xy % 2 != diff_t % 2):
            print('No')
            exit(0)
    print('Yes')


if __name__ == '__main__':
    resolve()

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

int main() {
  string S;
  cin >> S;
  
  vector<string> days = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
  for (int i = 0; i < 7; i++) {
    if (days.at(i) == S) {
      cout << 7 - i << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
// #include<boost/multiprecision/cpp_int.hpp>
// namespace multiprecisioninteger = boost::multiprecision;
// using cint=multiprecisioninteger::cpp_int;
using namespace std;
using ll=long long;
#define double long double
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
// using llset=tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,b,a) for(i=b-1;i>=(ll)a;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
// const ll mod=998244353;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

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

double distance(ddatas x,ddatas y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  if(n<r)return 0;
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

int main(){
  // startupcpp();
  // int codeforces;cin>>codeforces;while(codeforces--){
  ll i,j,N,H,W,ans;
  string s;
  cin>>N;
  rep(i,5){
    if(N%10==7)break;
    N/=10;
  }
  if(i==5)printno;
  else printyes;
  return 0;
}

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

int main(){
  int N, M;
  cin >> N >> M;
  double A[N];
  rep(i, N) {
    cin >> A[i];
  }
  sort(A, A+N, std::greater<int>());
  double sum = accumulate(A, A+N, 0);
  double target = A[M-1];
  if ((target / sum) < (1.0/ (4.0 * M))) {
    cout << "No" << "\n";
  } else {
    cout << "Yes" << "\n";
  }
}


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

int main() {
  int A, B;
  cin >> A >> B;
  if(A < 10000 || A > 99999 || B < 10000 || B > 99999){
    cout << "error" << endl;
    return 0;
  }
  
  int count = 0;
  const int digit = 5;
  int keta[digit];
  
  for(int C = A; C <= B; C++){
    int D = C;
    for(int i = 0 ; i < digit ; i++){
      keta[i] = D / pow(10, (digit-i-1));
      D -= keta[i] * pow(10, (digit-i-1));
    }
    
    if(keta[0] == keta[4] && keta[1] == keta[3])
      count += 1;
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
import std.stdio;
import std.ascii;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.random;
import std.regex;
import std.typecons;

int popcnt(int x) {
    int r = 0;
    foreach (i; 0 .. 22) if (x & (1 << i)) r++;
    return r;
}

void main() {
    int N, Hx, Hy, Dx, Dy;
    int[] Y, X;
    bool input() {
        scanf("%d %d %d %d %d\n", &N, &Hx, &Hy, &Dx, &Dy);
        if (N == 0) return false;
        Y = new int[N + 2];
        X = new int[N + 2];
        Y[0] = Hy;
        X[0] = Hx;
        foreach (i; 1 .. N + 1) {
            scanf("%d %d\n", &X[i], &Y[i]);
        }
        Y[N + 1] = Dy;
        X[N + 1] = Dx;
        return true;
    }
    double Distance(int a, int b) {
        double dy = Y[a] - Y[b],
               dx = X[a] - X[b];
        return sqrt(dy * dy + dx * dx);
    }
    void solve() {
        bool dfs(int v, int used, double t) {
            //writefln("%d %0" ~ (N + 2).to!string ~ "b %f", v, used, t);
            if (used == (1 << (N + 1)) - 1) return true;
            foreach (i; 1 .. N + 1) {
                if (used & (1 << i)) continue;
                if (Distance(v, i) + t >= Distance(N + 1, i)) return false;
            }
            foreach (i; 1 .. N + 1) {
                if (used & (1 << i)) continue;
                if (dfs(i, used | 1 << i, t + Distance(v, i))) return true;
            }
            return false;
        }
        writeln(dfs(0, 1, 0) ? "YES" : "NO");
    }
    while (input) solve;
}

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

using namespace std;

typedef long long int64;

struct SegmentTree
{
  vector< int64 > add, seg;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, 0);
    add.assign(2 * sz - 1, 0);
  }

  void update(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      add[k] += 1LL * x;
      return;
    }
    update(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    update(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
    int mid = (l + r) >> 1;
    seg[k] += add[2 * k + 1] * (mid - l);
    seg[k] += add[2 * k + 2] * (r - mid);
  }

  void update(int a, int b, int x)
  {
    update(a, b, x, 0, 0, sz);
  }

  int64 query(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (0LL);
    if(a <= l && r <= b) return (seg[k] + add[k] * (r - l));
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) +
            query(a, b, 2 * k + 2, (l + r) >> 1, r) + add[k] * (min(b, r) - max(a, l)));
  }

  int64 query(int a, int b)
  {
    return (query(a, b, 0, 0, sz));
  }
};

int main()
{
  int N, Q;
  scanf("%d %d", &N, &Q);
  SegmentTree tree(N);
  while(Q--) {
    int t;
    scanf("%d", &t);
    if(t == 0) {
      int s, t, x;
      scanf("%d %d %d", &s, &t, &x);
      tree.update(--s, t, x);
    } else {
      int s, t;
      scanf("%d %d", &s, &t);
      printf("%lld\n", tree.query(--s, t));
    }
  }
}

Measured memory_bytes: 7016
#include <stdio.h>
#include <stdlib.h>
int A[100000],A1[1000000],n,flag,cnt;
char C[100000],C1[1000000];
int Partition(int p,int r){
  int i,j,tmpn,x;
  char tmpc;
  x=A[r];
  i=p-1;

  for(j=p;j<=r-1;j++){
    if(A[j]<=x){
      
     
      i=i+1;
      tmpn=A[j];
      A[j]=A[i];
      A[i]=tmpn;

      tmpc=C[j];
      C[j]=C[i];
      C[i]=tmpc;
	
    }
   
  }
  tmpn=A[i+1];
  tmpc=C[i+1];

  A[i+1]=A[r];
  C[i+1]=C[r];

  A[r]=tmpn;
  C[r]=tmpc;
  return i+1;
}
void Quicksort(int p,int r){
  int q;
  if(p<r){
    q=Partition(p,r);
    Quicksort(p,q-1);
    Quicksort(q+1,r);
  }
}

void merge(int left,int mid,int right){
  int n1,n2,i,j,k;
  double *L,*R;
  char *L1,*R1;
  n1=mid-left;
  n2=right-mid;
 
  L=(double*)malloc((sizeof(double))*(n1+1));
  R=(double*)malloc((sizeof(double))*(n2+1));
  L1=(char*)malloc((sizeof(char))*(n1+1));
  R1=(char*)malloc((sizeof(char))*(n2+1));

  for(i=0;i<n1;i++){
    L[i]=A1[left+i];
    L1[i]=C1[left+i];
  }
 
  for(i=0;i<n2;i++){
    R[i]=A1[mid+i];
    R1[i]=C1[mid+i];
  }
  L[n1]=1.0/0.0;
  R[n2]=1.0/0.0;
  i=0;
  j=0;
  for(k=left;k<right;k++){
    cnt++;
    if(L[i]<=R[j]){
      A1[k]=L[i];
      C1[k]=L1[i];
      i++;
    }
    else {
      A1[k]=R[j];
      C1[k]=R1[j];
      j++;
    }
 
  }
   
  free(L);
  free(R);
 
}


void mergeSort(int left,int right){
  int mid;
   
  if(left+1<right){ mid=(left+right)/2;
    mergeSort(left,mid);
    mergeSort(mid,right);
    merge(left,mid,right);
  }
 
}



int main(){

  int i,p=0;

   scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf(" %c %d",&C[i],&A[i]);
    A1[i]=A[i];
    C1[i]=C[i];
  }

  mergeSort(0,n);
  Quicksort(0,n-1);
  for(i=0;i<n;i++){
    if(A1[i]==A[i] && C1[i]!=C[i]){
      flag=1;
      break;
    }
  }
  if(flag==0) printf("Stable\n");
  else printf("Not stable\n");

  for(i=0;i<n;i++){
    printf("%c %d\n",C[i],A[i]);
  }


  return 0;
}

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

using namespace std;

int main() {
  int N, C, K;
  scanf("%d%d%d", &N, &C, &K);
  int T[N];
  for (int i = 0; i < N; i++) {
    scanf("%d", T + i);
  }
  sort(T, T + N);
  int ans = 0, H = T[0] + K, M = 1;
  for (int i = 1; i < N; i++) {
    if (M == C) {
      ans++;
      M = 1;
      H = T[i] + K;
    } else if (T[i] <= H) {
      M++;
    } else {
      ans++;
      M = 1;
      H = T[i] + K;
    }
  }
  printf("%d\n", ans + 1);
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
#define fastIO \
ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl "\n"
#define ll long long
#define MOD 1000000007
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define pii pair<int,int> 

bool compare(const pii &a, const pii &b){
	return atan2(a.ss,a.ff) < atan2(b.ss,b.ff);
}
 
long double dis(pair<ll,ll> a, pair<ll,ll> b){
	long double x = abs(a.ff-b.ff), y = abs(a.ss-b.ss);
	return (x*x + y*y);
}
 
int main(){
	int n;
	cin >> n;
	vector <pii> v(n);
	for(int i=0;i<n;i++)	cin >> v[i].ff >> v[i].ss;
	sort(v.begin(), v.end(), compare);
	vector < pair<ll,ll> > prefix(2*n);
	prefix[0] = v[0];
	for(int i=1;i<n;i++)
		prefix[i] = mp(prefix[i-1].ff+v[i].ff, prefix[i-1].ss+v[i].ss);
	for(int i=n;i<2*n;i++)	
		prefix[i] = mp(prefix[i-1].ff+v[i%n].ff, prefix[i-1].ss+v[i%n].ss);
	long double ans = 0.0;
	for(int i=0;i<n;i++)
		for(int j=i;j<i+n;j++)
			ans = max(ans, dis(prefix[j], i>0?prefix[i-1]:mp(0LL,0LL)));
	cout << fixed << setprecision(50) << sqrt(ans) << endl;
	return 0;
}

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

using namespace std;
using ll = long long;
using ld = long double;

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> dp(n), v(n);
    for (int &e : v) {
        cin >> e;
    }
    for (int i = 1  ; i < n; i++) {
        dp[i] = 2e9;
        for (int j = 1; j <= k && i - j >= 0; j++) {
            dp[i] = min(dp[i], dp[i - j] + abs(v[i] - v[i - j]));
        }
    }
    cout << dp[n - 1];
}


Measured memory_bytes: 1024
#include<iostream>//A
#include<cstdio>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",(n>=9?9:n)+(n>=999?900:(n-99>0?n-99:0))+(n>=99999?90000:(n-9999>0?n-9999:0)));
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

struct RangeMinQuery{
  ll dat[(1<<19)-1];
  int size;

  void init(int n_){
    size=1;
    while(size<n_) size*=2;
    for(int i=0;i<2*size-1;i++)dat[i]=INF;
  }

  void update(int k,ll a){
    k+=size-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }

  ll subquery(int a,int b,int k,int l,int r){
    if(r<=a||b<=l)return INF;
    if(a<=l&&r<=b)return dat[k];
    else{
      return min(subquery(a,b,k*2+1,l,(l+r)/2),subquery(a,b,k*2+2,(l+r)/2,r));
    }
  }
  
  ll query(int a,int b){
    return subquery(a,b,0,0,size);
  }
};

RangeMinQuery rmq;
vector<P> rs[100010];

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

  ll N,M;
  cin>>N>>M;
  rep(i,M){
    ll l,r,c;
    cin>>l>>r>>c;
    l--;
    r--;
    rs[r].push_back(P(l,c));
  }

  rmq.init(N);
  rmq.update(0,0);
  repl(i,1,N){
    ll dp=INF;
    for(P p : rs[i]){
      minch(dp,rmq.query(p.fi,i)+p.se);
    }
    rmq.update(i,dp);
  }
  ll res=rmq.query(N-1,N);
  if(res==INF)cout<<-1<<endl;
  else cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 9472
# include <cstdio>

using namespace std;

int main() {
  int N;
  scanf("%d", &N);
  int m = 0;
  int cnt = 0;
  for (int i = 0; i < N; ++i) {
    int H;
    scanf("%d", &H);
    if (i == 0) {
      ++cnt;
      m = H;
      continue;
    }
    if (H >= m) {
      ++cnt;
      m = H;
    }
  }
  printf("%d", cnt);
  fflush(stdout);
  return 0;
}


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

const int maxn = 1e3+5;
int n,k,p[maxn];
int ans=0;
int main(){
	cin >> n >> k;
	for (int i=1;i<=n;i++){
		cin >> p[i];	
	}
	sort(p+1,p+n+1);
	for (int i=1;i<=k;i++){
		ans+=p[i];
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1e9+7;

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

    vector<int> oks(n+1, true);
    for(int i = 0; i < m; i++){
        int a;
        cin >> a;
        oks[a] = false;
    }

    vector<long long int> dp(n+1);
    dp[0] = 1;
    for(int now = 0; now < n; now++){
        for(int next = now+1; next <= min(n, now+2); next++){
            if(oks[next]){
                dp[next] += dp[now];
                dp[next] %= mod;
            }
        }
    }

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

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

using namespace std;

int main() {
  string S;
  cin >> S;
  
  int cnt_r = 0;
  for (int i = 0; i < S.length(); i++) {
    if (S[i] == '0') {
      cnt_r++;
    }
  }

  if(cnt_r > S.length()/2){
	  cout << (S.length() - cnt_r) * 2 << endl;
  }else{
	  cout << cnt_r * 2 << endl;
  }

  return 0;
}

Measured memory_bytes: 512
class UnionFind:
   def __init__(self,n):
       self.parent = [-1 for i in range(n)]

   def find(self, x):
       if self.parent[x] < 0:
           return x

       else:
           self.parent[x] = self.find(self.parent[x])
           return self.parent[x]

   def union(self, x, y):
       x, y = self.find(x), self.find(y)
       if (x == y):
           pass
       else:
           self.parent[x] = self.parent[y]
           self.parent[y] = x

   def isgroup(self, x, y):
       return True if self.find(x) == self.find(y) else False

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

ans = 0
for i in range(M):
    uf = UnionFind(N)
    temp = ab[:i] + ab[i+1:]
    for a, b in temp:
        uf.union(a-1, b-1)

    for i in range(1, N):
        if uf.isgroup(i, i-1) == False:
            ans += 1
            break

print(ans)

Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[101],w[101],dp[10001];
int main()
{
    int t,m,ans=2147483647;
    cin>>m>>t;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&w[i],&a[i]);
    for(int i=1;i<=m;i++)
    	if(w[i]<ans&&a[i]<=t)	ans=w[i];
    if(ans==2147483647)	cout<<"TLE"<<endl;
    else     cout<<ans;
    return 0;
}

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

public class Main{
    public static void main(String[] args){
        Scanner ir=new Scanner(System.in);
        outer:
        for(;;){
            int m=ir.nextInt();
            int n=ir.nextInt();
            if(m==0&&n==0){
                System.exit(0);
            }
            int MAX=10000000;
            boolean[] f=new boolean[MAX];
            int ct=0;
            for(int i=m;;i++){
                if(!f[i]){
                    ct++;
                    if(ct>n){
                        System.out.println(i);
                        continue outer;
                    }
                    for(int j=i;j<MAX;j+=i){
                        f[j]=true;
                    }
                }
            }
        }
    }
}


Measured memory_bytes: 87956
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static long MOD = (long) (Math.pow(10, 9) + 7);
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int num = 26;
		for (int i = 1; i <= 365; i++) {

			out(num--);
			if (num == 0) {
				num = 26;
			}
		}

	}

	/*
	 * 以下メソッド集
	 */
	static int[] sort(int[] n) {
		Arrays.sort(n);
		return n;
	}

	static void debug() {
		out("---");
	}

	static void debug(long a) {
		out("-------");
		out(a);
		out("-------");
	}

	static void debug(String a) {
		out("-------");
		out(a);
		out("-------");
	}

	static long[] sort(long[] n) {
		Arrays.sort(n);
		return n;
	}

	static int ketasuu(int n) {
		String str = "" + n;
		return str.length();
	}

	static int account(String str) {
		String target = "AC";
		int count = 0;
		int len = str.length();
		for (int i = 0; i < len - 1; i++) {
			if (target.equals(str.substring(i, i + target.length()))) {
				count++;
			}
		}
		return count;
	}

	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static double nd() {
		return sc.nextDouble();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void out(Object obj) {
		System.out.println(obj.toString());
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}

	static double max(double d, double e) {
		return Math.max(d, e);
	}

	static long max(long a, long b) {
		return Math.max(a, b);
	}

	static long min(long d, long e) {
		return Math.min(d, e);
	}

	static int min(int a, int b) {
		return (int) Math.min(a, b);
	}
}

class XY {
	int h;
	int c;

	XY(int h, int c) {
		this.h = h;
		this.c = c;
	}
}


Measured memory_bytes: 36496
A=list(map(int,input().split()))
A.sort(reverse=True)
cnt=0
cnt+=A[0]-A[1]
if (A[0]-(A[2]+cnt))%2==0:
    print(cnt+(A[0]-(A[2]+cnt))//2)
else:
    print(cnt+(A[0]-(A[2]+cnt))//2+2)

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

typedef long long ll;

using namespace std;
 
int mod = 1e9 + 7;

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
	int cnt[100005];
	
	int n, k; cin >> n >> k;
	cnt[k] = 1;	
	long long ans = k;
	for ( int i = k-1; i >= 1; i--) {
		int rp = k/i;
		cnt[i] = pw(rp, n);
		for(int j = i+i; j <= k; j+=i) {
			cnt[i] = cnt[i] + mod - cnt[j];
			if (cnt[i] >= mod) {
				cnt[i] -= mod;
			}
		}
		ans += 1LL * cnt[i] * i;
		ans %= mod;
	}
	cout << ans;
}





Measured memory_bytes: 3964
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int nextA(int a, int l){
  int d[l];
  for( int i=0;i<l;i++ ){
    d[i] = a%10;
    a /= 10;
  }
  sort(d,d+l);
  int min=0,max=0;
  for( int i=0,b=1;i<l;i++, b*=10 ){
    min += b * d[l-i-1];
    max += b * d[i];
  }
  return max - min;
}

int main(){
  int a,l;

  while( cin>> a>> l,l){
    vector<int> v;
    int k=0;
    v.push_back(a);
    bool f=true;
    while( f ){
      a = nextA(a, l);
      for( int i=0;i<(int)v.size();i++ ){
	if( v[i] == a ){
	  cout << i << " " << a << " " << (k-i+1) << endl;
	  f=false;
	  break;
	}
      }
      if( f )
	v.push_back(a);
      k++;

    }
  }
  return 0;
}

Measured memory_bytes: 1220
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	q := nextInt(sc)
	ans := make([]int, q)
	set := make(map[int]int, 0)
	for i := 0; i < q; i++ {
		op := nextInt(sc)
		x := nextInt(sc)
		if op == 0 {
			set[x]++
			ans[i] = len(set)
		} else if set[x] > 0 {
			ans[i] = 1
		}
	}
	for i := 0; i < len(ans); i++ {
		fmt.Println(ans[i])
	}
}



Measured memory_bytes: 14488
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
#define PI 3.1415926535897932384626433832795028
#define INF (1<<29)
#define LINF (1LL<<60)
using namespace std;
using INT = long long;
using P = pair<int,int> ;

int main(){
    vector<int> p;
    int x;
    cin >> x;
    int n;
    cin >> n;
    vector<int> check;
    
    rep(i,n){
        int a;
        cin >> a;
        p.emplace_back(a);
        check.emplace_back(abs(a-x));
    }
    
    sort(check.begin(),check.end());
    int checking = 0;
    bool conti=true;
    bool minus_check=true;
    bool plus_check=true;
    int ans=0;
    
    while(conti){
        rep(i,n){
            if(p[i]==x-checking){
                minus_check=false;
            }
            if(p[i]==x+checking){
                plus_check=false;
            }
        }
        if(!minus_check&&!plus_check){
            checking++;
        }
        else if(minus_check){
            ans = x - checking;
            conti = false;
        }
        else {
            ans = x + checking;
            conti = false;
        }
        minus_check = true;
        plus_check = true;
        
    }
    cout << ans;
	return 0;
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fast_io() ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 3e3 + 7;
const int MOD = 998244353;
int n, s;
int dp[N][N];
int a[N];
int binpow(int a, int b)
{
	a %= MOD;
	int res = 1;
	while (b)
	{
		if (b & 1) res = (res * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return res;
}
int add(int x, int y)
{
	int res = ((x % MOD) + (y % MOD)) % MOD;
	return res;
}
int mul(int x, int y)
{
	int res = ((x % MOD) * (y % MOD)) % MOD;
	return res;
}
int32_t main() {
	fast_io();
	cin >> n >> s;
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= s; j++)
			dp[i][j] = 0;
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	dp[0][0] = binpow(2LL, n);
	int inv2 = binpow(2LL, MOD - 2);
	// for (int i = 1; i <= n; i++)
	// 	dp[i][a[i]] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= s; j++)
		{
			dp[i][j] = add(dp[i][j], dp[i - 1][j]);
			if (j >= a[i])
			{
				dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - a[i]], inv2));
			}
		}
	}
	cout << dp[n][s] << "\n";
	return 0;
}


Measured memory_bytes: 74092
#include<bits/stdc++.h>
#define fr first


using namespace std;
// vector tuple solution
int main(){
    int n,x,y;
    cin>>n>>x>>y;
    //dist -- y-x-1++
    vector<int> dist(n,0);
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
        if(i>=x && i<y){
            if(j>=y)
            dist[min(i-x+1+j-y,j-i)]++;
            else 
            dist[min(j-i,i-x+y-j+1)]++;
        }
        
        if(i<x ){
            if(j<=x){dist[j-i]++;}
            else{
                dist[min(min(j-x,abs(y-j)+1)+ x-i,j-i)]++;
            }
        }
            
        
        if(i>=y) dist[j-i]++;// y equality done
    }
    }
    for(int i=1;i<n;i++){
        cout<<dist[i]<<"\n";
    }
    return 0;
}


Measured memory_bytes: 256
fn input() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_string()
}

fn main() {
    loop {
        let line = &input();
        let seg: Vec<&str> = line
            .split_whitespace()
            // .map(|s| s.parse::<i64>().unwrap())
            // .map(|s| s.to_owned())
            .collect();
        if seg[1] == "?" {
            break;
        } else {
            simple_calcurator(seg);
        }
    }
}

fn simple_calcurator(v: Vec<&str>) {
    match v[1] {
        "+" => println!(
            "{}",
            v[0].parse::<i32>().unwrap() + v[2].parse::<i32>().unwrap()
        ),
        "-" => println!(
            "{}",
            v[0].parse::<i32>().unwrap() - v[2].parse::<i32>().unwrap()
        ),
        "*" => println!(
            "{}",
            v[0].parse::<i32>().unwrap() * v[2].parse::<i32>().unwrap()
        ),
        "/" => println!(
            "{}",
            v[0].parse::<i32>().unwrap() / v[2].parse::<i32>().unwrap()
        ),
        _ => (),
    }
}


Measured memory_bytes: 5032
N = input()
if len(N) == 1:
    print(int(N))
elif len(N) == 2:
    print(9)
elif len(N) == 3:
    print(9+int(N)-99)
elif len(N) == 4:
    print(909)
elif len(N) == 5:
    print(909+int(N)-9999)
else:
    print(90909)

Measured memory_bytes: 3060
from itertools import product
from math import ceil

d, g = map(int, input().split())
pc = []
for i in range(d):
    pc.append(list(map(int, input().split())))

ans = 10 ** 10
for e in product((0, 1), repeat=d):
    total_cnt = 0
    score = 0
    odd_idx = 0
    for j in range(d):
        if e[j] == 1:
            cnt = pc[j][0]
            bonus = pc[j][1]
            score += cnt * ((j + 1) * 100) + bonus
            total_cnt += cnt
        else:
            odd_idx = j

    if g <= score:
        ans = min(ans, total_cnt)
    else:
        odd_point = (odd_idx + 1) * 100
        odd_cnt = pc[odd_idx][0] - 1
        if g <= score + (odd_cnt * odd_point):
            total_cnt += ceil((g - score) / odd_point)
            ans = min(ans, total_cnt)
print(ans)


Measured memory_bytes: 40432
fun main(args: Array<String>) {
    val n = readInt()
    val a = readLongList()
    val q = readInt()
    val arr = mutableListOf<Pair<Int, Int>>()
    repeat(q) {
        val (b, c) = readIntList()
        arr.add(Pair(b, c))
    }

    val num = Array(100001) { 0L }
    a.forEach {
        num[it.toInt()]++
    }

    var sum = a.sum()
    for (i in 0 until q) {
        val tmpNum = num[arr[i].first]
        num[arr[i].first] = 0
        num[arr[i].second] += tmpNum
        sum += (arr[i].second - arr[i].first) * tmpNum
        println(sum)
    }
}

// Tools
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)

Measured memory_bytes: 72684
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cctype>
#include <map>
#include <functional>
using namespace std;

typedef vector<int> vint;

int ans;
const char *ptr;
char buf[256];
map<string,int> mp;

size_t cmp(const vint &v1, const vint &v2){
	return v1.size() < v2.size();
}

vint block(bool brace, string defvar = string()){
	vector<vint> freqs;
	map<string,int>::iterator it;
	
	if(!defvar.empty()){
		mp.insert(make_pair(defvar, 1));
	}

	if(brace) ++ptr;
	while(*ptr != '}'){
		if(*ptr == '{'){
			freqs.push_back(block(true));
		}
		else if(*ptr == 'V'){	//VAR
			ptr += 3;
			ans += 3;

			int dif = 0;
			sscanf(ptr, " %[a-z]%n", buf, &dif);
			string varname = buf;
			ptr += dif;

			freqs.push_back(block(false, varname));
		}
		else if(islower(*ptr)){
			sscanf(ptr, "%[a-z]", buf);
			string varname = buf;
			ptr += varname.size();
			++mp[varname];
		}
		else if(!isspace(*ptr++)){
			++ans;
		}
	}
	if(brace){
		++ptr;
		ans += 2;
	}

	vint res;
	if(freqs.size() == 1){
		res.swap(freqs[0]);
	}
	else if(freqs.size() > 1){
		int maxsize = max_element(freqs.begin(), freqs.end(), cmp)->size();
		for(int i = 0; i < maxsize; ++i){
			int s = 0;
			for(int j = 0; j < freqs.size(); ++j){
				if(i < freqs[j].size()){
					s += freqs[j][i];
				}
			}
			res.push_back(s);
		}
	}

	if(!defvar.empty()){
		map<string,int>::iterator it = mp.find(defvar);
		res.push_back(it->second);
		mp.erase(it);
	}
	sort(res.begin(), res.end(), greater<int>());

	return res;
}

int main(){
	string s, lines;
	int n;
	while(cin >> n, n){
		cin.ignore();
		lines = "{";
		for(int i = 0; i < n; ++i){
			getline(cin, s);
			lines += s;
		}
		lines += '}';
		
		ans = -2;
		mp.clear();
		ptr = lines.c_str();
		vint v = block(true);
		
		v.resize(1024, 0);
		vint::iterator it1 = v.begin(), it2;
		for(int i = 1; i <= 9; ++i){
			it2 = it1 + (1 << i);
			ans += accumulate(it1, it2, 0) * i;
			it1 = it2;
		}
		
		cout << ans << '\n';
	}
}

Measured memory_bytes: 1808
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;

template <typename T>
struct BIT
{
    int n;
    vector<T> bit;
    
    BIT(){}
    
    BIT(int n) : n(n){
        bit.resize(n + 1);
    }
    
    T sum(int i){
        i++;
        T res = 0;
        while(i){
            res += bit[i];
            i -= (i & -i);
        }
        return res;
    }
    
    void add(int i, T x){
        i++;
        while(i <= n){
            bit[i] += x;
            i += (i & -i);
        }
    }
};

ll a[200005];
ll s[200005];
P p[200005];
int r[200005];

int main()
{
    int n;
    ll k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] -= k;
    }
    s[0] = 0;
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i - 1];
    for(int i = 0; i <= n; i++) p[i] = P(s[i], i);
    sort(p, p + n + 1);
    for(int i = 0; i <= n; i++) r[p[i].second] = i;
    BIT<ll> bit(n + 2);
    ll ans = 0;
    for(int i = 0; i <= n; i++){
        ans += bit.sum(r[i]);
        bit.add(r[i], 1);
    }
    cout << ans << endl;
}


Measured memory_bytes: 11976
import java.util.*;

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

    int n = sc.nextInt();
    int k = sc.nextInt();
    String s = sc.next();
    char[] c = new char[n];
    c = s.toCharArray();

    if(c[k - 1] == 'A'){
      c[k - 1] = 'a';
    } else if(c[k - 1] == 'B'){
      c[k - 1] = 'b';
    } else {
      c[k - 1] = 'c';
    }

    for(int i = 0; i < n; i++){
      System.out.print(c[i]);
    }
  }
}


Measured memory_bytes: 21332