akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()
// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class X> void DEBUG(X d, T e){if(DEBUG_OUT == false)return;std::cout <<d<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//CODE

int gcd(int a,int b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

void solve(void)
{
  int N;
  cin>>N;
  int LCM = 1;
  for (int i = 0; i < N; i++)
  {
    int A;
    cin>>A;
    LCM = lcm(LCM,A);
  }
  cout<<LCM<<endl;
  

  return;
}


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

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();
  

 
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
typedef   long long int ll;
int main () 
{
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;cin>>k;
  cout<<a[k-1]<<endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr int INFI = 1000000007;
const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

// combination c(N);
// mint ans = c(N,n);
// cout << ans.x << endl;

// -------------------------------------------------------------


int main(){
  int x,y;
  cin >> x >> y;
  if((x+y)%3){
    cout << 0 << endl;
    return 0;
  }
  int n;
  n = (x+y)/3;
  x -= n;
  y -= n;
  if(x<0 || y<0){
    cout << 0 << endl;
    return 0;
  }
  combination c(x+y);
  mint ans = c(x+y,x);
  cout << ans.x << endl;
  return 0;
}


Measured memory_bytes: 10624
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
ll W,weight[110],value[110];

ll dp[110][100100];

int main(){
    cin>>N>>W;
    for(int i=0;i<N;i++) cin>>weight[i]>>value[i];
    
    for(int i=0;i<N;i++){
        for(int sum_w=0;sum_w<=W;sum_w++){
            if(sum_w-weight[i]>=0){
                chmax(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i]);
            }
            chmax(dp[i+1][sum_w],dp[i][sum_w]);
        }
    }
    
    cout<<dp[N][W]<<endl;
}

Measured memory_bytes: 79360
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 10e9;

void OddString() {
	string s;
	cin >> s;
	for (size_t i = 0; i < s.size(); i++)
	{
		if (i % 2 == 0) {
			cout << s[i];
		}
	}
	cout << endl;
}

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



Measured memory_bytes: 512
#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
typedef double db;
#define fo(i,j,k) for(i=j;i<=k;i++)
#define fd(i,j,k) for(i=j;i>=k;i--)
#define cmax(a,b) (a=(a>b)?a:b)
#define cmin(a,b) (a=(a<b)?a:b)
const int N=1e6+5,mo=998244353;
struct rec
{
	ll v;
	db t;
}s[N];
ll sum,t[N],v[N],l,r,n,L,prod,i,dec;
int main()
{
	scanf("%lld %lld",&n,&L);
	l=1;
	r=0;
	fo(i,1,n)
	{
		scanf("%lld %lld",t+i,v+i);
		while (sum+v[i]>L)
		{
			dec=min(s[l].v,sum+v[i]-L);
			s[l].v-=dec;
			sum-=dec;
			prod-=dec*s[l].t;
			if (!s[l].v) l++;
		}
		s[++r]={v[i],t[i]};
		prod+=v[i]*t[i];
		sum+=v[i];
		while (l<r&&s[r].t<s[r-1].t)
		{
			s[r-1].t=(s[r-1].t*s[r-1].v+s[r].t*s[r].v)/(s[r-1].v+s[r].v);
			s[r-1].v+=s[r].v;
			r--;
		}
		printf("%lf\n",(db)prod/L);
	}
}

Measured memory_bytes: 28928
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
signed main(){
    ll n,k;cin>>n>>k;
    vector<ll>pos(0);
    vector<ll>neg(0);

    rep(i,n){
        ll b;cin>>b;
        if(b<0){
            neg.pb(-b);
        }else{
            pos.pb(b);
        }
    }
    sort(rall(pos));
    sort(rall(neg));
    ll i=0;
    ll j=0;
    ll ans=1;
    if(n==k){
        rep(i,pos.size()){
            ans=ans*pos[i]%inf;
        }
        rep(i,neg.size()){
            ans=ans*(-neg[i])%inf;
        }
        if(ans<0)ans+=inf;
        cout<<ans<<endl;
        return 0;
    }
    if(neg.size()==n){
        if(k%2==0){
            rep(i,k){
                ans=ans*neg[i]%inf;
            }
            cout<<ans<<endl;
            return 0;
        }
        sort(all(neg));
        rep(i,k){
            ans=ans*(-neg[i])%inf;
        }
        if(ans<0)ans+=inf;
        cout<<ans<<endl;
        return 0;
    }
    ll cnt=0;
    while(cnt<k){
        if(i==pos.size()){
            ans=ans*(-neg[j])%inf;
            j++;
            cnt++;
        }else{
            if(j==neg.size()){
                ans=ans*pos[i]%inf;
                i++;
                cnt++;
            }else{
                if(pos[i]>neg[j]){
                    ans=ans*pos[i]%inf;
                    i++;
                    cnt++;
                }else{
                    ans=ans*(-neg[j])%inf;
                    j++;
                    cnt++;
                }
            }
        }
    }
    if(j%2==0){
        if(ans<0)ans+=inf;
        cout<<ans<<endl;
    }else{
        ll an1=1;
        ll an2=1;
        rep(k,i+1){
            if(k==pos.size())break;
            an1=an1*pos[k]%inf;
        }
        rep(k,j-1){
            an1=an1*(-neg[k])%inf;
        }
        rep(k,i-1){
            an2=an2*pos[k]%inf;
        }
        rep(k,j+1){
            if(k==neg.size())break;
            an2=an2*(-neg[k])%inf;
        }
        if(i==0){
            ans=an1;
        }else if(j==neg.size()){
            ans=an1;
        }else{
            if(pos[i]*pos[i-1]>=neg[j]*neg[j-1]){
                ans=an1;
            }else{
                ans=an2;
            }
        }
        if(ans<0)ans+=inf;
        cout<<ans<<endl;
    }
}

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

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define repf(i, f, l) for(int i = f; i < (int)l; ++i)
#define repit(it, t) for(__typeof((t).begin()) it = (t).begin(); it != (t).end(); it++)
#define endl "\n"
#define pb emplace_back
#define lb lower_bound
#define int long long
#define ul unsigned long
#define ull unsigned long long
#define ll long long
#define INF 1000000007
#define MOD 1000000007
#define fs first
#define sd second
#define DBG0(x) { cout << #x << ": " << x << "\t"; }
#define DBG(x) {DBG0(x); cout << endl;}
#define DBG2(x, y) {DBG0(x); DBG(y);}
#define DBG3(x, y, z) {DBG0(x); DBG2(y, z);}
#define DBG4(w, x, y, z) {DBG0(w); DBG3(x, y, z);}

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ul> vul;
typedef vector<ull> vull;
typedef vector<bool> vbl;
typedef pair<int, int> pii;

signed main(void){
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    vint xs = vint(m);
    rep(i, m) cin >> xs[i];
    if (n >= m) {
        cout << 0 << endl;
        return 0;
    }

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

    vint diffs = vint();
    repf(i, 1, m) {
        diffs.push_back(xs[i] - xs[i - 1]);
    }
    sort(diffs.begin(), diffs.end());
    reverse(diffs.begin(), diffs.end());

    int ans = xs[m - 1] - xs[0];
    repf(i, 1, n) {
        ans -= diffs[i - 1];
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
//Á½¸öÊýÏà³ËÊÇ4µÄ±¶Êý£¬ËµÃ÷ÆäÖÐÖÁÉÙÒ»¸öÊÇ4µÄ±¶Êý¡£»òÕßÁ½¸ö¶¼ÊÇ2µÄ±¶Êý
//Í³¼Æ2,4µÄ±¶ÊýµÄ¸öÊý¡£

int main()
{

	int N;
	cin >> N;
	int four = 0,one = 0,two = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if(a%4==0) four++;
		else if(a%2==0) two++;
		else one++;		//ÆæÊý
	}
	if(one > four+1) //ÓÐ2¸öÊÇ4µÄ±¶Êý£¬µ«ÊÇÓÐ4¸öÆæÊý£¬ÓàÏÂÁ½¸öÆæÊý½«ÎÞ·¨Åä¶Ô 
	{
		cout<<"No\n";
		return 0;
	} 
	if(one == four + 1 && two != 0) {	//2¸öÊÇ4µÄ±¶Êý£¬3¸öÊÇÆæÊý£¬ÇÒÓÐ2µÄ±¶Êý,2µÄ±¶ÊýÔòÒ²²»ÐÐ 
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes";
	return 0;

}


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //ifstream in("input.txt");
  //cin.rdbuf(in.rdbuf());
  int n,m;
  string str;
  cin >> str;
  char a = str[0];
  bool flag = false;
  for(int i=1;i<str.size();i++){
    if(str[i] == a) flag = true;
    a = str[i];
  }
  if (flag) cout << "Bad" << endl;
  else cout << "Good" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw10(19,1);

int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N,K,S; cin>>N>>K>>S;
    
    if(S==pw10[9]){
        rep(i,K) cout<<S<<" ";
        rep(i,N-K) cout<<S-1<<" ";
    }
    else{
        rep(i,K) cout<<S<<" ";
        rep(i,N-K) cout<<S+1<<" ";
    }
}



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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define rep(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

ll INF = 1ll << 60;

int main(){
  ll n, d;
  cin >> n >> d;
  d *= d;
  
  int cnt = 0;
  
  rep(i, 0, n){
    ll x, y;
    cin >> x >> y;
    x *= x;
    y *= y;
    if(x+y <= d)
      cnt++;
  }
  
  cout << cnt << endl;  
  
  return 0;
  
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M,C;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<vector<int>> A(N,vector<int>(M));
    for (int i=0;i<M;i++){
        cin >> B[i];
    }
    int ans =0;
    for (int i=0;i<N;i++){
        int tmp =C;
        for (int j=0;j<M;j++){
            cin >> A[i][j];
            tmp+=A[i][j]*B[j];
        }
        if (tmp > 0) ans+=1;
    }
    cout << ans;

}

Measured memory_bytes: 256
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = A_arr[0]
    ans = 0
    for A in A_arr:
        if A < cnt:
            ans += (cnt - A)
        else:
            cnt = A
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 92788
// I think of what the world could be, A vision of the one I see, A million dreams is all it's gonna take

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn];
vector<int> vec[3], pr[2];
int ans[maxn];

void dfs(int u, int h = 1, int par = -1){
    for(int y : v[u]){
	if(y != par){
	    dfs(y, h+1, u);
	}
    }
    pr[h&1].PB(u);
}

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

    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
	int a, b;
	cin >> a >> b;
	v[a].PB(b);
	v[b].PB(a);
    }
    for(int i = 1; i <= n; i++){
	vec[i%3].PB(i);
    }
    dfs(1);
    if(sz(pr[0]) > sz(pr[1]))
	swap(pr[0], pr[1]);
    if(sz(pr[0]) <= (n/3)){
	while(sz(pr[0]))
	    ans[pr[0].back()] = vec[0].back(), vec[0].pop_back(), pr[0].pop_back();
	for(int x : vec[1])
	    vec[0].PB(x);
	for(int x : vec[2])
	    vec[0].PB(x);
	while(sz(pr[1]))
	    ans[pr[1].back()] = vec[0].back(), vec[0].pop_back(), pr[1].pop_back();
    }
    else{
	if(sz(vec[1]) > sz(vec[2]))
	    swap(vec[1], vec[2]);
	while(sz(vec[1]))
	    ans[pr[0].back()] = vec[1].back(), pr[0].pop_back(), vec[1].pop_back();
	while(sz(vec[2]))
	    ans[pr[1].back()] = vec[2].back(), pr[1].pop_back(), vec[2].pop_back();
	while(sz(pr[0]))
	    ans[pr[0].back()] = vec[0].back(), pr[0].pop_back(), vec[0].pop_back();
	while(sz(pr[1]))
	    ans[pr[1].back()] = vec[0].back(), pr[1].pop_back(), vec[0].pop_back();
    }
    for(int i = 1; i <= n; i++){
	cout << ans[i] << " ";
    }
    return cout << endl, 0;
}


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

int main(){
    ll x[4],y[4];
    cin>>x[0]>>y[0]>>x[1]>>y[1];
    ll a,b;
    a=x[1]-x[0];
    b=y[1]-y[0];
    //cout<<a<<endl;
    //cout<<b<<endl;
    x[2]=x[1]-b;
    y[2]=y[1]+a;
    x[3]=x[0]-b;
    y[3]=y[0]+a;
    cout<<x[2]<<" "<<y[2]<<" "<<x[3]<<" "<<y[3]<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n,a,b,c,d[101];
	int i,j,temp;
	int max,cal,dol;
	int k;
	
	scanf("%d",&n);
	scanf("%d %d",&a,&b);
	scanf("%d",&c);
	for(i=0;i<n;i++){
		scanf("%d",&d[i]);
	}
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(d[i]<d[j]){
				temp=d[i];
				d[i]=d[j];
				d[j]=temp;
			}
		}
	}
	max=c/a;
	k=0;
	cal=c;
	dol=a;
	for(i=0;i<n;i++){
		k++;
		cal+=d[i];
		dol+=b;
		if(max<(cal/dol)){
			max=(cal/dol);
		}
	}
	printf("%d\n",max);
	return 0;
}
	

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

int main(){
	int n;
	int a[220];
	cin >> n;
	rep(i,n) cin >> a[i];
	int ans = 0;
	while(true){
		bool exist_odd = false;
		rep(i,n){
			if(a[i]%2 != 0)	exist_odd = true;
			}
			if(exist_odd) break;
		rep(i,n){
			a[i] /= 2;
		}
		++ans;
	}	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
//http://lightoj.com/volume_showproblem.php?problem=1068

#include<bits/stdc++.h>
using namespace std;

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define LL              long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

const LL MOD=1e9+7;
int len,inp[10005],k;
LL dp[10005][105][2];
bool vis[10005][105][2];

LL call(int pos,bool isSmall,int rem)
{
    if(pos==len) {
        if(rem==0) return 1;
        else return 0;
    }
    if(vis[pos][rem][isSmall]==1) return dp[pos][rem][isSmall];
    vis[pos][rem][isSmall]=1;
    int last=9;
    if(!isSmall) last=inp[pos];
    LL ret=0;
    for(int i=0;i<last;i++) ret=(ret+call(pos+1,1,(rem+i)%k))%MOD;
    if(!isSmall) ret=(ret+call(pos+1,0,(rem+last)%k))%MOD;
    else ret=(ret+call(pos+1,1,(rem+last)%k))%MOD;
    return dp[pos][rem][isSmall]=ret;
}

int solve(string str){
    for(len=0;len<str.size();len++){
        inp[len]=str[len]-'0';
    }
    return (call(0,0,0)-1+MOD)%MOD;
}

int main()
{
    Fast
    string str;
    cin >> str >> k;
    cout << solve(str);
}


Measured memory_bytes: 19712
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

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

    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int s = h1 * 60 + m1, t = h2 * 60 + m2;
    cout << t - s - k << endl;
}

Measured memory_bytes: 3652
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
    
comInit(MOD)

N, K = map(int, input().split())
A = list(map(int, input().split()))
cnt_a = Counter(A)
AA = sorted(list(set(A)))
f_max = 0
f_min = 0

acc = 0
for a in AA:
    cnt = cnt_a[a]
    f_min += (com(N - acc, K, MOD) - com(N - acc - cnt, K, MOD)) * a
    f_min %= MOD
    acc += cnt

acc = 0
for a in AA[::-1]:
    cnt = cnt_a[a]
    f_max += (com(N - acc, K, MOD) - com(N - acc - cnt, K, MOD)) * a
    f_max %= MOD
    acc += cnt
print((f_max - f_min) % MOD)


Measured memory_bytes: 116508
#include<stdio.h>
#define N 12
char tab[N][N];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
void dfs(int x,int y){
  int g,nx,ny;
  tab[x][y]='0';
  for(g=0;g<4;g++){
    ny=y+dy[g];
    nx=x+dx[g];
    if(nx>=0&&nx<N&&ny>=0&&ny<N){
      if(tab[nx][ny]=='1')dfs(nx,ny);
    }
  }
  
}
int main(void){
  int a,b,i,k,j,ans;
  char d;
  while(1){
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(scanf("%c",&tab[j][i])==EOF)return 0;
      }
      scanf("%c",&d);
    }
    ans=0;
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
	if(tab[j][i]=='1'){
	  dfs(j,i);
	  ans++;
	}
      }
    }
    printf("%d\n",ans);
    scanf("%c",&d);
  }
  return 0;
}

Measured memory_bytes: 540
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 1000006, MAX_C = 102;
const ll lmod = 1e9+7;

int main(){
  ll x,y;
  cin >> x >> y ;
  int cnt = 0;
  while(x<=y){
    x *= 2;
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

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

	void run() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int P = sc.nextInt();
		int[] A = new int[M];
		int[] B = new int[M];
		int[] C = new int[M];
		for (int i = 0; i < M; ++i) {
			A[i] = sc.nextInt() - 1;
			B[i] = sc.nextInt() - 1;
			C[i] = sc.nextInt() - P;
		}
		long[] cost = new long[N];
		Arrays.fill(cost, -Long.MAX_VALUE / 3);
		cost[0] = 0;
		long ans = 0;
		for (int t = 0; t < N; ++t) {
			for (int j = 0; j < M; ++j) {
				cost[B[j]] = Math.max(cost[B[j]], cost[A[j]] + C[j]);
				cost[B[j]] = Math.max(cost[B[j]], -Long.MAX_VALUE / 3);
			}
		}
		ans = cost[N - 1];
		for (int t = 0; t < N; ++t) {
			for (int j = 0; j < M; ++j) {
				cost[B[j]] = Math.max(cost[B[j]], cost[A[j]] + C[j]);
				cost[B[j]] = Math.max(cost[B[j]], -Long.MAX_VALUE / 3);
			}
		}
		if (ans < cost[N - 1]) {
			System.out.println(-1);
		} else {
			System.out.println(Math.max(0, ans));
		}
	}

	class Edge implements Comparable<Edge> {
		int src;
		int dst;
		int cost;

		public Edge(int src, int dst, int cost) {
			this.src = src;
			this.dst = dst;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(cost, o.cost);
		}
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


Measured memory_bytes: 40064
using System;
using System.Collections;
class Program
{
    static int Calc(int n)
    {
        int n2 = n / 10;
        n2 += (n % 10 == 0) ? 0 : 1;
        int m = n2 / 365;
        m += (n2 % 365 == 0) ? 0 : 1;
        return m;
    }
    static void Main()
    {
        ArrayList al = new ArrayList();
        while (true)
        {
            int n = int.Parse(Console.ReadLine());
            if (n == 0)
                break;
            al.Add(n);
        }
        int[] nums = (int[])al.ToArray(typeof(int));
        int[] ans = new int[31];
        ans[0] = 1;
        ans[1] = 1;
        ans[2] = 2;
        for (int i = 3; i < 31; i++)
            ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
        foreach (var i in nums)
        {
            Console.WriteLine(Calc(ans[i]));
        }
    }
}


Measured memory_bytes: 9268
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int s = Math.abs(a - x);
		int t = Math.abs(x - b);

		if(s > t) {
			System.out.println('B');
		}else {
			System.out.println('A');
		}
	}
}


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

using namespace std;

typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; ++i) cin >> d[i];
  sort(d.begin(), d.end());
  int res = 0;
  if (N % 2 == 1) res = 0;
  else {
    int abc_upper = d[N / 2 - 1];
    int arc_lower = d[N / 2];
    res = arc_lower - abc_upper;
  }
  cout << res << endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e13;
const int mod = 1e9+7;
#define ll long long
map<char, int> m;
signed main() {
    int n, a, b;
    cin >> n >> a >> b;
    if(a==b && n==1) cout << 1 << endl;
    else if(n<2) cout << 0 << endl;
    else if(a>b) cout << 0 << endl;
    else {
        cout << b*(n-1)+a - (a*(n-1)+b) + 1 << endl;
    }
  return 0;
}



Measured memory_bytes: 3612
#include<stdio.h>

#define MOD 1000000007

long mod_multi(long a,long b){
    long long int ret;
    ret = a*b;
    if(ret>MOD)ret %= MOD;
    return ret;
}

int main(void){
    int n;
    scanf("%d",&n);
    char str[n+1];
    scanf("%s",str);
    long ans = 1;
    int cc[26] = {};
    for(int i = 0;i < n;i++)cc[str[i]-'a']++;
    for(int i = 0;i < 26;i++)ans = mod_multi(ans,cc[i]+1);
    printf("%ld",ans-1);
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String s = scanner.next();
		String t = scanner.next();
		int count = 0;
		for (int i = 0; i < 3; i++) {
			if (s.charAt(i) == t.charAt(i))
				count++;
		}
		System.out.println(count);
	}

}


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

const int mod = 1e9 + 7;
int dp[1<<10][1<<10];
char str[1<<10][1<<10];

int main(){
	int n, m; cin >> n >> m;
	for(int i = 0;i < n;i++){
		cin >> str[i];
	}
	dp[1][0]=1;
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= m;j++){
			if(str[i - 1][j - 1] ==  '.'){
				(dp[i][j] =  dp[i][j - 1] + dp[i - 1][j]) %= mod;
				
			}
		}
	}cout << dp[n][m] << "\n";
}

Measured memory_bytes: 5248
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int main(){
    int n,d,p;
    cin>>n>>d;
    vector<vector<int> > x(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<d; j++){
            cin>>p;
            x[i].push_back(p);
        }
    }


    double dis=0;
    int cnt=0;
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            dis=0;
            for(int k=0; k<d; k++){
                //cout<<x[j][k]<<"-"<<x[i][k]<<endl;
                dis+=pow((x[j][k]-x[i][k]),2);
                //cout<<"pow:"<<pow((x[j][k]-x[i][k]),2)<<endl;
            }
            dis=sqrt(dis);
            //cout<<"dis="<<dis<<endl;           
            if(dis==int(dis)){
                //cout<<"dis="<<dis<<endl;
                cnt++;
            }
        }
    } 

    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int r;
    cin >>r;
    cout << 3*r*r << endl;
    return 0;
}

Measured memory_bytes: 3556
n = int(input())
lh = list(map(int,input().split()))

i = len(lh)-1
mi = lh[i]
while(i > 0): 
    if (lh[i-1] <= mi+1):
        mi = min(mi, lh[i-1])
        i -= 1
    else:
        print("No")
        exit()
    
print("Yes")
 

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, K, X, Y;
    cin >> N >> K >> X >> Y;
    
    cout << min(K, N)*X + max(N-K, 0LL)*Y << endl; 
    return 0;
}

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vi v(n), c(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  int x = 0;
  int y = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] > c[i]) {
      x += v[i];
      y += c[i];
    }
  }
  cout << x - y << endl;
  return 0;
}


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

#define debug_input freopen("stdin.in", "r", stdin)
#define debug_output freopen("stdout.out", "w", stdout)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORALL(i, n) for(int i = 0; i < n; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define SORT(a) sort(a.begin(), a.end())
#define REV(a) reverse(a.begin(), a.end())
#define NP(a) next_permutation(a.begin(), a.end())
#define ALL(a) a.begin, a.end()
#define mp make_pair
#define pb push_back
#define endl "\n"
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	 
	bool x;
	cin >> x;
	cout << !x << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;

#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define sz size()
#define all(A)    A.begin(), A.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define f0(i,b)   for(int i=0;i<(b);i++)
#define f1(i,b)   for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define mod 1000000007

#define forr(i,n)    for(i=0; i<n; i++)
#define whilee(i,t)  while(i!=t)
#define  sl(a)  scanf("%lld",&a)
#define  pl(a)  printf("%lld\n",a)

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

//for(auto it =A.begin(); it!=A.end(); it++)
//sort(A.begin(),A.end());
//binary_search(A.begin(),A.end(),x);
//reverse(A.begin(), A.end());
//cout << *max_element(A.begin(), A.end());
//cout << *min_element(A.begin(), A.end());
//count(A.begin(), A.end(), X); //counts the occurrences of X
//distance(A.begin(),A.end());  //distance between first to last element
//accumulate(A.begin(), A.end(), 0); //add
//next_permutation(A.begin(), A.end());
//prev_permutation(A.begin(), A.end());
//swap(S[0], T[0]);

//scanf("%d",&x);
//printf("%d\n",x);
//while (scanf("%d %d", &a, &b) == 2)
//printf("Case %d: %d\n", t++, a);

//vector <int> A;
//deque <int> A;
//queue <int> A;
//stack <int> A;
//set <int> A;
//map <int,int> A;
//pair <int,int> A ;
//vector <pair <int,int>> A ;
//bitset<32> bset1;
//char ch;
//string S, T, U;
ll gcd(ll a, ll b)
{
    if (b == 0)
    {
        return a;
    }
    return gcd(b, a % b);
}
ll i, j, k, a, b, c=0, d, f, g, h, l, m, n, p, q, r, s, t=1, u, v, w, x, y, z, maxx=INT_MIN, minn=INT_MAX, ans=1, sum=0, cnt=0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);//NULL
    cout.tie(nullptr);//NULL

    //scan(n);
    cin>>n;
    ll A[n], left[n], right[n];
    forr(i,n)
    {
        cin>>A[i];
        if(i==0)
        {
            left[i]=A[i];
        }
        else
        {
            left[i] = gcd(left[i-1],A[i]);
        }
    }
    fr(i,n-1,0)
    {
        if(i==n-1)
        {
            right[i]=A[i];
        }
        else
        {
            right[i] = gcd(right[i+1],A[i]);
        }
    }
    maxx=max(left[n-2],right[1]);
     for(i=1; i<n-1; i++)
    {
            ans= gcd(left[i-1],right[i+1]);
            if(ans>maxx)
            {
                maxx=ans;
            }

    }
    cout<< maxx <<endl;
    return 0;
}






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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 111;

int M[MAX][MAX];
int A[MAX][MAX];
int B[MAX][MAX];
int x, y;
int n, m;

int DP[MAX][MAX];

void rotate()
{
	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			B[j][n - i - 1] = M[i][j];
		}
	}

	int x1 = y;
	int y1 = n - x - 1;

	x = x1;
	y = y1;

	swap(n, m);

	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			M[i][j] = B[i][j];
		}
	}

	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			A[i][j] = M[i][j];
			if (i) A[i][j] += A[i-1][j];
			if (j) A[i][j] += A[i][j-1];
			if (i && j) A[i][j] -= A[i-1][j-1];
		}
	}
}

int getSum(int x1, int y1, int x2, int y2)
{
	int res = A[x2][y2];
	if (x1 > 0) res -= A[x1 - 1][y2];
	if (y1 > 0) res -= A[x2][y1 - 1];
	if (x1 > 0 && y1 > 0) res += A[x1 - 1][y1 - 1];
	return res;
}


int main()
{
	//freopen("in.txt","r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);


	cin>>n>>m;
	FOR (i, 0, n)
	{
		string s;
		cin>>s;
		FOR (j, 0, m)
		{
			if (s[j] == 'o') A[i][j] = M[i][j] = 1;
			if (s[j] == 'E')
			{
				x = i;
				y = j;
			}
		}
	}

	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			if (i) A[i][j] += A[i-1][j];
			if (j) A[i][j] += A[i][j-1];
			if (i && j) A[i][j] -= A[i-1][j-1];
		}
	}

	int res = 0;

	FOR (it, 0, 4)
	{
		FOR (a, x, n)
		{
			FOR (b, y, m)
			{
				int lx = n - a;
				int ly = m - b;

				FOR (i, x, a+1)
				{
					FOR (j, y, b + 1)
					{
						DP[i][j] = 0;
					}
				}

				DP[x][y] = getSum(x - lx + 1, y - ly + 1, x, y);

				FOR (i, x, a + 1)
				{
					FOR (j, y, b + 1)
					{
						int mx = i - x;
						int my = j - y;

						mx = max(mx, x - lx + 1);
						my = max(my, y - ly + 1);

						DP[i+1][j] = max(DP[i+1][j], DP[i][j] + getSum(i+1, my, i + 1, j));
						DP[i][j+1] = max(DP[i][j+1], DP[i][j] + getSum(mx, j+1, i, j + 1));
					}
				}

				res = max(res, DP[a][b]);
			}
		}
		rotate();
	}

	cout<<res<<endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);
 
using namespace std;
 
namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;
 
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n;
	ll a, b; cin >> n >> a >> b;
	if(a > b) swap(a, b);
	vector<ll> s(n); rep(i, n) cin >> s[i];
	rep(i, n - 2) if(s[i + 2] - s[i] < a){
		cout << 0 << endl;
		return 0;
	}
	s.insert(s.begin(), -b);
	
	const int mod = 1e9 + 7;
	vi dp(n + 1);
	dp[0] = 1;
	int zero = 0, sum = 0;
	for(int i = 0, j = 0; i < n; i++){
		while(j <= i && s[j] + b <= s[i + 1]){
			(sum += j < zero ? 0 : dp[j]) %= mod;
			j++;
		}
		dp[i + 1] = sum;
		if(s[i + 1] - s[i] < a){
			while(zero < i){
				if(zero < j) sum = (sum + mod - dp[zero]) % mod;
				dp[zero++] = 0;
			}
		}
	}
	ll ans = 0;
	for(int i = zero; i <= n; i++) ans += dp[i];
	cout << ans % mod << endl;
	
	return 0;
}

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

typedef long long ll;
const int MOD = 1e9+7;
const int N = 100005;
int a[N],pos[N];
ll fac[N],inv[N],finv[N];
void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i = 2;i < N;i++)
	{
		inv[i] = MOD - inv[MOD%i]*(MOD/i) % MOD;
		fac[i] = fac[i-1]*i%MOD;
		finv[i] = finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)//C(a,b)
{
	if(a < b)
		return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int main()
{
	make();
	memset(pos,-1,sizeof(pos));
	int n,pos1,pos2;
	cin >> n;
	for(int i = 1;i <= n+1;i++)
	{
		scanf("%d",&a[i]);
		if(pos[a[i]] == -1)
			pos[a[i]] = i;
		else
		{
			pos1 = pos[a[i]];
			pos2 = i;
		}
	}

	int d = pos2 - pos1 + 1;
	ll ans;
	for(int k = 1;k <= n+1;k++)
	{
		ans = C(n+1,k) - C(n+1-d,k-1);
		if(ans < 0)
			ans += MOD;
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 4352
#include<stdio.h>
#include<math.h>

int main(void){
	int s[1000]={0};
	int i,n=0;
	double sum,ave,a,a2=0;
	
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		for(i=0;i<n;i++){
			scanf("%d",&s[i]);
			sum=sum+s[i];
		}
		ave=sum/n;
		for(i=0;i<n;i++){
			a2=a2+pow(s[i]-ave,2);
		}
		a2=a2/n;
		a=sqrt(a2);
		printf("%lf\n",a);
		
		sum=0;
		ave=0;
		a=0;
		a2=0;
	}
	
	return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

bool ch(vector<ll> &a, ll x, ll n, ll m){
	ll co = 0;
	rep(i, n){
		ll add = lower_bound(a.begin(), a.end(), x - a.at(i)) - a.begin();
		add = n - add;
		co += add;
	}
	return co < m;
}

int main(){
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n);
	rep(snip_i, n) cin >> a.at(snip_i);
	sort(a.begin(), a.end());
	ll ng = 0, ok = LLONG_MAX;
	while(ok - ng > 1){
		ll mid = (ng+ok)/2;
		if(ch(a, mid, n, m)) ok = mid;
		else ng = mid;
	}
	// cerr << "tst" << ok << endl;

	vector<ll> sum(n+1, 0);
	rep(i, n){
		sum.at(i+1) = sum.at(i) + a.at(i);
	}
	ll ans = 0;
	rep(i, n){
		ll index = upper_bound(a.begin(), a.end(), ng - a.at(i)) - a.begin();
		ll add = n - index;
		ans += add * a.at(i) + sum.at(n) - sum.at(index);
		m -= add;
	}
	ans += m * ng;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <string>

using namespace std;
using LL = long long;

const int N = 1e5 + 99;
const int INF = 0x3F3F3F3F;

int main() {
    LL n;
    cin >> n;
    --n;
    cout << n * (n + 1) / 2 << endl;
    return 0;
}
// 13
// 13 1 2 3 4 5 6 7 8 9 10 11 12

Measured memory_bytes: 256
A = []
for i in range(3):
    A.append(list(map(int, input().split())))
    
N = int(input())
b = []
for i in range(N):
    b.append(int(input()))
    
bingo = [[0,0,0],[0,0,0],[0,0,0]]

def my_index(L, x):
    return L.index(x) if x in L else -1

for k in b:
    for i in range(3):
        if my_index(A[i], k) != -1:
            bingo[i][my_index(A[i], k)] = 1
            
ans = 0
for i in range(3):
    if bingo[i] == [1,1,1]:
        ans = 1
    if bingo[0][i] * bingo[1][i] * bingo[2][i]:
        ans = 1
    if bingo[0][0] * bingo[1][1] * bingo[2][2]:
        ans = 1
    if bingo[0][2] * bingo[1][1] * bingo[2][0]:
        ans = 1
        
if ans:
    print("Yes")
else:
    print("No")
    
    
    


Measured memory_bytes: 3064
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

    int n = sc.nextInt();
    List<String> inputs = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      String input = sc.next();
      if (input.equals("0")) {
        System.out.println(0);
        return;
      }
      inputs.add(input);
    }
    BigInteger res = new BigInteger(inputs.get(0));
    BigInteger max = new BigInteger("1000000000000000000");
    for (int i = 1; i < n; i++) {
      BigInteger num = new BigInteger(inputs.get(i));
      res = res.multiply(num);
      if (res.compareTo(max) > 0) {
        System.out.println(-1);
        return;
      }
    }
    System.out.println(res.longValue());
  }
}


Measured memory_bytes: 66728
n = int(input())
a = list(map(int, input().split()))

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
      dp[i * ai] += 1
      i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Measured memory_bytes: 121632
i = input()
a,b,c = map(int, i.split())

if a > b :
  x = a
  a = b
  b = x

if b > c :
  x = b
  b = c
  c = x

if a > b :
  x = a
  a = b
  b = x


print(a,b,c)


Measured memory_bytes: 5596
require 'pp'
require 'prime'

N,M = readline.chomp.split.map(&:to_i)
B = 1_000_000_007
ps = Prime.prime_division(M)

s = 1
ps.each do |prime,a|
  s *= (N..(N-1+a)).each.inject(1,:*) / (1..a).each.inject(1,:*)
  s %= B
end
puts s



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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl ;
typedef pair<ll,ll> pl;
 
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define rep(i,N) for(int i=0; i < (N); i++)
#define all(v) (v).begin(),(v).end()

int main(){
	int N, X, Y;
	cin >> N >> X >> Y;
	vl ans(N-1, 0);
	for(int i=0; i<N-1; i++){
		for(int j=i+1; j<N; j++){
			//cout << i << " " << j << " " << min(abs(i-j), abs(i-(X-1))+abs(j-(Y-1))+1) << endl;
			int a = min(abs(i-j), abs(i-(X-1))+abs(j-(Y-1))+1);
			ans[a-1]++;
		}
	}
	for(auto i: ans){
		cout << i << endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int ans = 0;
		for (int i = 0;; i++) {
			if ((double)n >= Math.pow(2, i)) {
				continue;
			}else{
				ans = (int)Math.pow(2, i-1);
				break;
			}
		}
		
		System.out.println(ans);
		scanner.close();
	}
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pll> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-9;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

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

ll gcd(ll *begin, ll *end) {
	ll res = *begin;
	while (begin != end) res = gcd(res, *begin), ++begin;
	return res;
}

ll lcm(ll *begin, ll *end) {
	ll res = *begin;
	while (begin != end) res = lcm(res, *begin), ++begin;
	return res;
}

int n;
ll d[10], v[10], ans[10];

int main() {
	while (cin >> n, n) {
		ll g, l, t;
		REP(i, n) {
			scanf("%lld %lld", d + i, v + i);
			g = gcd(d[i], v[i]);
			d[i] /= g; v[i] /= g;
		}
		
		l = lcm(d, d + n);
		g = gcd(v, v + n);
		
		REP(i, n) {
			ll ans = (l / d[i]) * (v[i] / g);
			cout << ans << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 3152