akhauriyash/Code-Regression huggingface dataset:
//
//  main.cpp
//  ABC160E

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // sort
using namespace std;
int main(int argc, const char * argv[]) {
    long long X,Y,A,B,C;
    cin>>X>>Y>>A>>B>>C;
    vector<long long>p(A);
    vector<long long>q(B);
    vector<long long>r(C);
    vector<long long>s;
    for (long long i=0; i<A; i++) {
        cin >> p.at(i);
    }
    sort(p.begin(),p.end(),greater<long long>());
    p.erase(p.begin()+X,p.end());
    for (long long i=0; i<B; i++) {
        cin >> q.at(i);
    }
    sort(q.begin(),q.end(),greater<long long>());
    q.erase(q.begin()+Y,q.end());
    for (long long i=0; i<C; i++) {
        cin >> r.at(i);
    }
    sort(r.begin(),r.end(),greater<long long>());
    s.insert(s.end(),p.begin(),p.end());
    s.insert(s.end(), q.begin(),q.end());
    s.insert(s.end(), r.begin(),r.end());
    sort(s.begin(),s.end(),greater<long long>());
    //s.erase(s.begin()+X+Y,s.end());
    //cout<<accumulate(s.begin(), s.end(), 0)<<endl; // long long型を指定するには0LLと書く
    s.erase(s.begin()+X+Y,s.end());
    cout<<accumulate(s.begin(), s.end(), 0LL)<<endl;
    /*
    long long ans=0;
    for (long long i=0; i<(X+Y); i++) {
        ans+=s.at(i);
    }
    cout<<ans<<endl;
     */
    return 0;
}


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

int main(void) {
	int N, T, E;
	vector<int> x;

	cin >> N >> T >> E;
	for(int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		x.push_back(tmp);
	}

	for(int i = 0; i < x.size(); i++) {
		if(T - E <= x[i] * (((T - E - 1) / x[i]) + 1) && x[i] * (((T - E - 1) / x[i]) + 1) <= T + E) {
			cout << i + 1 << endl;
			return 0;
		}
	}

	cout << "-1" << endl;
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>

using namespace std;

int memo[201][201];

int gcd(int a, int b)
{
	if (memo[a][b] != 0)
	{
		return memo[a][b];
	}


	if (a%b == 0)
	{
		return b;
	}
	else {
		return memo[a][b] = gcd(b, a%b);
	}
}
int gcd(int a, int b, int c)
{
	return gcd(gcd(a, b), c);
}




int main()
{
	int N;
	long long res = 0;

	cin >> N;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			for (int k = 1; k <= N; ++k)
			{
				res += gcd(i, j, k);
			}

		}

	}

	cout << res << endl;
	return 0;
}

Measured memory_bytes: 3776
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> num(N);
  for(int i = 0; i < N; i++) {
    cin >> num[i];
  }
  sort(num.begin(), num.end());
  reverse(num.begin(), num.end());
  int alice = 0;
  int bob = 0;
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      alice += num[i];
    } else {
      bob += num[i];
    }
  }
  cout << alice - bob << endl;
    
}

Measured memory_bytes: 3616
/*
    Author : Simanta Deb Turja
*/
#include <bits/stdc++.h>
using namespace std;

#define Professor

using ll = long long;
using i64 = unsigned long long;

template <typename T> inline T Min (T a, T b, T c) { return min(a, min(b, c)); }
template <typename T> inline T Min (T a, T b, T c, T d) { return min(a, min(b, min(c, d))); }
template <typename T> inline T Max (T a, T b, T c) { return max(a, max(b, c)); }
template <typename T> inline T Max (T a, T b, T c, T d) { return max(a, max(b, max(c, d))); }

template <typename T> inline T Ceil(T a, T b) { return ((a % b == 0) ? (a / b) : (a / b + 1)); } 
template <typename T> inline T Floor(T a, T b) { return a / b; }

template <typename T> inline T Power (T a, T p) { T res = 1, x = a; while ( p ) { if ( p & 1 ) res = ( res * x ); x = ( x * x ); p >>= 1;}return res; }
template <typename T> inline T BigMod (T a,T p,T M) { a %= M;T ret = 1; while (p) { if (p & 1) ret = (ret * a) % M; a = (a * a) % M; p = p >> 1; } return ret; }
template <typename T> inline T InverseMod (T a,T M) { return BigMod (a, M - 2, M); }

template <typename T> inline T gcd ( T a, T b ) { a = abs(a); b = abs(b); while ( b ) { a = a % b; swap ( a, b ); } return a; }
template <typename T> inline T lcm(T x,T y) { return (((x)/gcd((x),(y)))*(y)); }


#define endl '\n'
#define eb emplace_back

const int N = (int)4e5 + 10;
const double EPS = 1e-7;
const double PI = acos(-1.0);
const ll LLINF = (ll)1e18+1;
const int INF = (int)1e9+1;
const ll MOD = (ll)1e9 + 7;

template <typename T> bool cmp (const pair <T, T> &a, const pair <T, T> &b) { return a.first < b.first; }


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    auto Solve = [&]() {
        #ifdef __APPLE__
            cout << "Running\n";
        #endif
        int n, W;
        cin >> n >> W;
        vector <ll> w(n), v(n);
        for (int i = 0; i < n; ++i) {
            cin >> w[i] >> v[i];
        }
        vector <ll> dp(W + 1);
        for (int i = 0; i < n; ++i) {
            for (int j = W; j >= w[i]; --j) {
                dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
        cout << dp[W] << endl;
    };
    Solve();
    
    return 0;
}



Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
const int mod=998244353;

long long fac[maxn], inv[maxn];
void pre()
{
    fac[0] = 1; inv[0] = 1;
    fac[1] = inv[1] = 1;
    for(int i=2;i<maxn;i++)
    {
        fac[i] = fac[i-1] * i %mod;
        inv[i] = (mod - mod / i) * inv[mod%i] %mod;
    }
    for(int i=1;i<maxn;i++)
    {
        inv[i] = inv[i] * inv[i-1] % mod;
    }
}
long long getc(int a,int b)
{
    if(a<0) return 0;
    if(a>b) return 0;
    //printf("%lld %lld %lld\n", fac[b], inv[a], inv[b-1]);
    return fac[b] * inv[a] % mod * inv[b-a] %mod;
}
int main()
{
    long long n, a, b;
    pre();
    long long k;
    scanf("%lld%lld%lld%lld",&n,&a,&b,&k);
    long long ans=0;
    for(int i=0;i<=n;i++)
    {
        if(i*a>k) break;
        if((k-i*a)%b==0){
            ans = (ans + getc(i,n)*getc((k-i*a)/b,n)) % mod;
            //printf("%dss %lld %lld\n",i,getc(i,n),getc((k-i*a)/b,n));
        }

    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

    //紙に気持ちの証明したけど最上位桁からやるほうがよさそう．
    //２つの数合わせたときに左のほうはたかだか1にしかならないから
    int m;cin>>m;
    ll ans=0;
    ll prev=0;
    rep(i,m){
        ll d,c;cin>>d>>c;
        ll loop=0;
        if(prev==0){
            prev=d;c--;
        }

        ll kosu=c+1;
        ll num=prev;
        while(c>0){
            num+=d;
            loop++;ans++;
            c--;
            if(num>9){
                num=num/10+num%10;
                loop++;ans++;
            }

            if(num==prev) break;
        }

        if(c==0){
            prev=num;continue;
        }
        // loop回でprevが繰り返し出てくるねん
        // cout<<"c: "<<c<<endl;
        // cout<<"loop: "<<loop<<endl;

        ll dec=kosu-c-1;
        ans+=(c/dec)*loop;
        c=c%dec;

        //prev dddddd...
        while(c>0){
            num+=d;
            loop++;ans++;
            c--;
            if(num>9){
                num=num/10+num%10;
                loop++;ans++;
            }

            if(num==prev) break;
        }
        
        prev=num;
    }


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


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	int N; cin >> N;

	int ans = 0;

	for (int i = 1;i <= N;i += 2){
		int cnt = 0;
		for (int j = 1;j <= i;j++){
			if(i%j == 0) cnt++;
		}
		if(cnt == 8) ans++;
	}

	cout << ans << endl;

	return 0;

}


Measured memory_bytes: 256
N = int(input())
p = list(map(int,input().split()))
P = p[0:N]
P.sort()
count = 0
for _ in range(0,N):
    if p[_] != P[_]:
        count += 1
if count == 0 or count == 2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std; 
#define rep(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
const int INF = 1<<29;
const int MOD=1073741824;
#define pp pair<ll,ll>
#define ppi pair<int,int>
typedef long long int ll;
bool isPowerOfTwo (ll x)  
{  
    return x && (!(x&(x-1)));  
}
void fastio()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
const int dx[] = {1,0,-1,0,1,1,-1,-1};
const int dy[] = {0,-1,0,1,1,-1,-1,1};
////////////////////////////////////////////////////////////////////

int main(){
    int tc=1;
    // cin>>tc;
    while(tc--){
        int a,b,c,k;
        cin>>a>>b>>c>>k;
        while(b<=a && k){
            b*=2;
            k--;
        }
        while(c<=b && k){
            c*=2;
            k--;
        }
        if(b>a && c>b)cout<<"Yes";
        else cout<<"No";
    }
}

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

using namespace std;

int f(int n) {
  int x = n;
  while (x > 0) {
    if (x % 10 != 0 && x != 1) return false;
    x /= 10;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int x = N;
  if (f(N)) {
    cout << 10 << '\n';
    return 0;
  }
  int res = 0;
  while (N > 0) {
    int x = N % 10;
    res += (x / 2) + (x - x / 2);
    N /= 10;
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

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

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

bool X[510][510];
bool Y[510][510];

int main() {
    ios::sync_with_stdio(false);
    memset(X, 0, sizeof(X));
    memset(Y, 0, sizeof(Y));
    string T[510];
    int N;
    cin >> N;
    for (int i = 0;i < N;i++) {
    	char c;
    	string s = "";
    	for (int j = 0;j < N;j++) {
    		cin >> c;
    		if (c == '#') {
    			X[i][j] = 1;
    			s.push_back('1');
    		}
    		else {
    			s.push_back('0');
    		}
    	}
    	T[i] = s;
    }
    bool ok = 0;
    for (int i = 0;i < N;i++) {
    	for (int j = 0;j < N;j++) {
    		if (X[j][i] == 1) ok = 1;
    	}
    }
    if (!ok) {
		cout << -1 << endl;
		return 0;
	}
    int num = 1E9;
    for (int i = 0;i < N;i++) {
    	int k = 0;
    	bool missing = 0;
        for (int j = 0;j < N;j++) {
        	if (X[i][j] == 0) {
        		k++;
        	}
        }
        if (k != 0) {
	    	bool y = 0;
    		for (int n = 0;n < N;n++) {
    			if (X[n][i] == 1) y = 1;
    		}
    		if (!y) missing = 1;
        }
        for (int j = 0;j < N;j++) {
        	bool ok = 1;
        	for (int n = 0;n < N;n++) {
        		if (X[n][j] == 0) ok = 0;
        	}
        	if (!ok) k++;
        }
        if (missing) k++;
        num = min(num, k);
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 29;
constexpr lint   INFL = 1LL << 61;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  lint n;
  vector<lint> v(5);
  cin >> n;
  rep (i, 5) cin >> v[i];
  lint maxi = LLONG_MIN;
  rep (i, 5) maxi = max(maxi, (n + v[i] - 1) / v[i]);
  cout << maxi + 4 << endl;
  return 0;
}

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

int main() {
  int n; cin >> n;
  int ans = 0;
  REP(i, n) {
    int tmp; cin >> tmp;
    ans += tmp;
  }
  cout << ans - n << endl;
  
  return 0;
}

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

int main(){
  string S;
  cin >> S;
  for(int ii=0; ii<S.size(); ii++){
    if(ii%2==0){
      if(S[ii]=='L'){
        cout << "No" << endl;
        return 0;
      }
    }else{
      if(S[ii]=='R'){
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
import math
import collections
import sys

#input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

s=input()
ans=""
for i in range(3):
    if s[i]=="1":
        ans+=str(9)
    else:
        ans+=str(1)
print(ans)

Measured memory_bytes: 3316
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B= MAP()
print((A-1)*(B-1))

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


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

int main() {
  int N;
  cin>>N;
  long long ans=0;
  
  
  for(int a=1;a<=N;a++){
    for(int b=1;b<=N;b++){
      for(int c=1;c<=N;c++){
          ans+=gcd(gcd(a,b),c);
       }
    }
   }
  cout<<ans;
  
  
return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int MAXN=2e3+5;
vector<int> g[MAXN];
int dist[MAXN];
bool visited[MAXN];
ll ans[MAXN];
int main() {
	int n;
	int x,y;
	cin>>n>>x>>y;
	for(int i=1;i<n;i++)
	{
	    g[i].pb(i+1);
	    g[i+1].pb(i);
	}
	g[x].pb(y);
	g[y].pb(x);
	for(int i=1;i<n;i++)
	{
	    queue<int> q;
	    q.push(i);
	    memset(dist,0,sizeof(dist));
	    memset(visited,false,sizeof(visited));
	    visited[i]=true;
	    while(!q.empty())
	    {
	        int pos=q.front();
	        q.pop();
	        for(int j=0;j<g[pos].size();j++)
	        {
	            if(!visited[g[pos][j]])
	            {
	                visited[g[pos][j]]=true;
	                dist[g[pos][j]]=dist[pos]+1;
	                q.push(g[pos][j]);
	            }
	        }
	    }
	    for(int j=i+1;j<=n;j++)
	    {
	        ans[dist[j]]++;
	    }
	}
	for(int i=1;i<n;i++)
	{
	    cout<<ans[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 384
a=[list(map(int,input().split())) for _ in range(3)]
n=int(input())
b=[int(input()) for _ in range(n)]
used=[[False]*3 for _ in range(3)]
for k in range(n):
    for i in range(3):
        for j in range(3):
            if a[i][j]==b[k]:
                used[i][j]=True

for i in range(3):
    if used[0][i] and used[1][i] and used[2][i]:
        print("Yes")
        exit()
        
for i in range(3):
    if used[i][0] and used[i][1] and used[i][2]:
        print("Yes")
        exit()

if used[0][0] and used[1][1] and used[2][2]:
        print("Yes")
        exit()

if used[0][2] and used[1][1] and used[2][0]:
        print("Yes")
        exit()                
print("No")

Measured memory_bytes: 68040
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
vector<int> inv;
const int p = 1e9 + 7;
const int N = 2e5 + 5;
inline int pw(int a, int b) { 
	int ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return ans % p;
}
inline int c(int a, int b) { 
	int ans = 1;
	for (int i = a; i >= a - b + 1; --i)
    	ans = (ans * i) % p;
	for (int i = b; i >= 1; --i)
		ans = ans * inv[i] % p;
	return (ans % p + p) % p;
}
inline void init() { 
    inv.push_back(0), inv.push_back(1);
	for (int i = 2; i <= N; ++i) {
        int k = (p - p / i) * inv[p % i] % p;
        inv.push_back(k);
    }
}
signed main() {
	init();
	int n, a, b; cin >> n >> a >> b;
	int ans = pw(2, n) - 1; ans %= p;
	ans -= (c(n, a) + c(n, b)) % p; ans %= p;
	ans = (ans + p) % p;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5196
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


A, B = nl()
S = s()

tokens = S.split('-')
if len(tokens) == 2 and len(tokens[0]) == A and len(tokens[1]) == B:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
import itertools

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

n = 0
s = 0

S = list(itertools.permutations(range(1, N+1)))
for i, item in enumerate(S):
    if P == item:
        n = i
    if Q == item:
        s = i
    if s > 0 and n > 0:
        break

print(abs(s-n))


Measured memory_bytes: 8052
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();



int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    vector<ll> pre(n+1, 0);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        pre[i+1] = pre[i] + arr[i];
    }
    // divide and conquer O(N);
    int l_idx = 0;
    int r_idx = 0;
    ll ans = INT_MAX * 1e8;
    ll M, m;
    for(int i = 0; i <= n; i++) {
        ll l_sum = pre[i];
        ll r_sum = pre[n] - pre[i]; // pre[i] - pre(l_idx) - pre(l_idx)
        // cout << "mid = " << i << ", l = " << l_sum << ", r = " << r_sum << endl;
        while (l_idx+1 <= i && llabs(pre[i] - pre[l_idx+1]*2) < llabs(pre[i] - pre[l_idx]*2)){
            l_idx += 1;
        }
        // cout << "l_idx = " << l_idx << endl;
        M = max(pre[l_idx], pre[i]-pre[l_idx]);
        m = min(pre[l_idx], pre[i]-pre[l_idx]);
        // pre[n] - pre[r_idx] - (pre[r_idx] - pre[i])
        while (r_idx+1 <= n && llabs(pre[n] + pre[i] - pre[r_idx+1]*2) < llabs(pre[n]+ pre[i] - pre[r_idx]*2)) {
            r_idx += 1;
        }
        // cout << "r_idx = " << r_idx << endl;
        M = max(M, pre[n] - pre[r_idx]);
        M = max(M, pre[r_idx]-pre[i]);
        m = min(m, pre[n] - pre[r_idx]);
        m = min(m, pre[r_idx] - pre[i]);
        ans = min(ans, M-m);
    }
    cout << ans << endl;
    return 0;
}



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

ll dp[110][2][5];
int main(){
    string s; cin >> s;
    int n = s.size();
    ll K; cin >> K;

    dp[0][0][0]=1;
    rep(i,n){
        int D = s[i]-'0';
        rep(j,2){
            rep(k,K+1){
                for(int d=0;d<=(j ? 9:D);d++){
                    dp[i+1][j | (d<D)][k + (d>0)] += dp[i][j][k];
                }
            }
        }
    }

    cout << dp[n][0][K]+dp[n][1][K] << endl;
}

Measured memory_bytes: 3624
if isfile("mystdin.txt");mystdin=open("mystdin.txt","r");redirect_stdin(mystdin);end
pI(x)=parse(Int,x)
pM(x::Array{SubString{String},1})=map(pI,x)
function howdiv2(n::Int)
  ans=0
  while n%2==0
    ans+=1
    n/=2
  end
  return ans
end
function main()
  n=pI(readline())
  a=[howdiv2(i) for i=pM(split(readline()))]
  println(minimum(a))
end
main()
if isdefined(Base, :mystdin);close(mystdin);end

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> ls(m), rs(m);
  for (int i = 0; i < m; i++) {
    cin >> ls[i] >> rs[i];
  }
  
  vector<int> imos(n, 0);
  for (int i = 0; i < m; i++) {
    imos[ls[i] - 1]++;
    if (rs[i] < n) {
      imos[rs[i]]--;
    }
  }
  for (int i = 1; i < n; i++) {
    imos[i] += imos[i - 1];
  }
  
  cout << count(imos.begin(), imos.end(), m) << endl;
  
  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define _GLIBCXX_DEBUG

int main(){
    int k,s;
    cin>>k>>s;
    int count=0;
    rep(i,k+1){
        rep(j,k+1){
            if(i+j<=s&&s-i-j<=k) count++;
        }
    }

    cout<<count<<endl;
    
}

Measured memory_bytes: 3600
#include <stdio.h>
#include <string.h>


int main (void){
    long number; 
    long b=0;
    long n;
    
    
    scanf("%ld",&number);
    n=number;
    
    while(number!=0){
    b = b + number % 10;
    number = number / 10;
  }

    if(n%b == 0){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    
    return 0;
}
/*int main(void)
{
  
  int number;
  int digit = 0;
 
  
  printf("数値 = ");
  scanf("%d", &number);
 
  
  while(number!=0){
    number = number / 10;
    ++digit;
  }
 
  
  printf("桁数 = %d\n", digit);
 
  return 0;
}*/


Measured memory_bytes: 128
MOD = 998244353


def pow(a, b):
	if b == 0:
		return 1

	if (b % 2) == 0:
		x = pow(a, b // 2) % MOD
		return x * x % MOD
	else: 
		return a * pow(a, b - 1) % MOD

def inverse(x):
	return pow(x, MOD - 2)

n, m, K = map(int, input().split())

result = 0

bin_coeff = 1

for k in range(K + 1):
	incr = (((bin_coeff * m % MOD)) % MOD) * pow(m - 1, n - k - 1) % MOD
	#print(incr, bin_coeff)
	result = (result + incr)  % MOD
	bin_coeff = ((bin_coeff * (n - k - 1) % MOD) * inverse(k + 1)) % MOD

print(result)



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

int main() {
    int K, X;
    cin >> K >> X;
    vector<int> ans;
    for (int i = -K + 1; i < K; ++i) {
        if (-1000000 <= X + i && X + i <= 1000000) ans.push_back(X + i);
    }
    for (int i = 0; i < ans.size() - 1; ++i) cout << ans[i] << " ";
    cout << ans[ans.size() - 1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()


ll combination(int n, int r)
{
	//nCr = nC(n-r)を使用して計算量を節約
	if (n - r < r) r = n - r;

	//自明な場合の戻り値
	if (r == 0) return 1;
	if (r == 1) return n;

	//組み合わせの数の定義に登場する分母・分子の要素
	vector<int> numerator(r, 0);
	vector<int> denominator(r, 0);

	//初期化
	rep(k, r)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	//分子を分母で割っていく。
	reple(p, 2, r)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				//分子は割り切れる場所までスライド
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	rep(k, r)
	{
		//残りを全部乗算
		if (numerator[k] > 1)
		{
			result *= (numerator[k] % mod);
			result %= mod;
		}
	}

	return result;
}

ll powmod(ll x, ll n)
{
	ll ret = 1;
	while (0 < n)
	{
		if ((n % 2) == 0)
		{
			x *= x;
			x %= mod;
			n >>= 1;
		}
		else
		{
			ret *= x;
			ret %= mod;
			--n;
		}
	}

	return ret;
}

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

	if (n <= 2)
	{
		cout << 0 << endl;
		return 0;
	}

	//総数 = 2^n - nCa - nCb - 1

	//2^nを累乗計算
	ll s = powmod(2, n);
	ll ca = combination(n, a);
	ll cb = combination(n, b);

	s -= (ca + cb + 1) % mod;
	while (s < 0) s += mod;

	cout << s << endl;

	return 0;
}

Measured memory_bytes: 1792
<?php
fscanf(STDIN, "%d", $N);
$list = fscanf(STDIN, str_repeat("%d", $N));

rsort($list);
$data = new SplMaxHeap();
$start = min($list[0], $list[1]);
$data->insert($start);
$data->insert($start);
$ans = $list[0];
unset($list[0]);
unset($list[1]);
foreach($list as $value){
    $ans += $data->extract();
    $data->insert($value);
    $data->insert($value);
}
echo $ans;


Measured memory_bytes: 29756
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
# define ll int64_t
# define str string
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;



#define INF 2000000000
#define MAX_V 10



bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

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

ll factorial(ll n){
    ll x=1;
    rrep(i,n) x*=i;
    return x;
}

ll gcd(ll a,ll b) { return b ? gcd(b, a%b) : a; }

ll func(ll a,ll b,ll& ans_x,ll& ans_y){
    if(b == 0){
        ans_x = 1;
        ans_y = 0;
        return a;
    }else{
        ll ret = func(b,(a%b),ans_y,ans_x);
        ans_y -= (a/b)*ans_x;
        return ret;
    }
}

vector<bool> IsPrime;

ll sieve(ll max){
    ll sum=0;
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    }
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(ll i=2; i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) {
            sum++;
            for(size_t j=2; i*j<=max; ++j) IsPrime[i*j] = false;
        }
    return sum;
}

ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}
const ll MAX = 5100000;
const ll MOD = 1000000007;
 
ll fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

using graph = vector<vector<ll>>;
pair<pair<ll,ll>,ll> p[100010];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    vector<ll> a(5);
    rep(i,5) {
        cin>>a[i];
        if(a[i]==0){
            cout<<i+1<<endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 3616
#include<stdio.h>
#include<string.h>

int main(void){
    char s[3];
    int count;

    scanf("%s",s);

    if(strcmp(s,"RRR")==0) count = 3;
    if(strcmp(s,"RRS")==0) count = 2;
    if(strcmp(s,"SRR")==0) count = 2;
    if(strcmp(s,"SRS")==0) count = 1;
    if(strcmp(s,"RSS")==0) count = 1;
    if(strcmp(s,"SSR")==0) count = 1;
    if(strcmp(s,"RSR")==0) count = 1;
    if(strcmp(s,"SSS")==0) count = 0;
    

    printf("%d",count);

    return 0;
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

ll s(ll n){
  ll sum = 0;
  while(n > 0){
    sum += n % 10;
    n /= 10;
  }

  return sum;
}


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

  ll n;
  cin >> n;

  if(n % s(n) == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  
  
}


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

int main(void)
{
    int x;
    cin >> x;

    int large = x / 500;
    x -= 500 * large;
    int small = x / 5;
    cout << large * 1000 + small * 5 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <stack>
#include <stdio.h>
#include <math.h>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	int cnt = 0;
	int fBlist = 0;
	int bAlist = 0;
	int vlist = 0;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i].size() - 1; j++) {
			if (s[i][j] == 'A') {
				if (s[i][j + 1] == 'B') {
					cnt++;
				}
			}
		}
		if (s[i][0] == 'B' && s[i][s[i].size() - 1] == 'A') vlist++;
		if (s[i][0] == 'B')fBlist++;
		if (s[i][s[i].size() - 1] == 'A')bAlist++;
	}

	if (vlist == fBlist && fBlist == bAlist && vlist!=0) {
		cnt--;	
	}
	cnt += fBlist < bAlist ? fBlist: bAlist;
	cout << cnt;
	return 0;
}


Measured memory_bytes: 768
#include<iostream>

using namespace std;
const int MOD = 1e9 + 7;

int N;
int order[100005];

long long pow(long long x, int n) {
    long long res = 1;
    while (0 < n) {
        if(n % 2 != 0)
            res = res * x % MOD;
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

int main() {
    cin >> N;
    int num;
    int d = (N - 1) % 2;
    for (int i = 0; i < N; i++){
        cin >> num;
        order[num]++;

        if(num % 2 != d || order[num] > 2 || order[0] > 1) {
            cout << 0 << endl;
            return 0;
        }
    }

    cout << pow(2, N / 2) << endl;
    return 0;
}

Measured memory_bytes: 3932
#include <string.h>

char s[200005];

int main(){

	scanf("%s",s);

	int i;

	int len=strlen(s);

	int A;
	int Z=0;

	for(i=0;i<len;i++){
		if(s[i]=='A'){
		A=i;
		break;
		}
	}
	for(i=A;i<len;i++){
		if(s[i]=='Z'&&i>Z){
		Z=i;
		}
	}
	printf("%d\n",Z-A+1);

	return 0;
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long k;
  cin >> k;
  long long x = 0;
  for (int i = 0; i < (int) 1e6; i++) {
    x = (x * 10 + 7) % k;
    if (x == 0) {
      cout << i + 1 << '\n';
      return 0;
    }
  }
  cout << -1 << '\n';
  return 0;
}


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

int main() {
    int n; cin >> n;
    vector<pair<int, int>> vp(n);
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        vp[i].first = b;
        vp[i].second = a;
    }
    sort(vp.begin(), vp.end());
    Int time = 0;
    Int current = 0;
    for (auto p : vp) {
        //printf("current=%lld, p.first=%d, p.second=%d\n", current, p.first, p.second);
        if (current + p.second > (Int)p.first) {
            puts("No");
            return 0;
        }
        current += p.second;
    }
    puts("Yes");
}

Measured memory_bytes: 4824
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
const ll mod=1000000007;
ll pow(ll x,ll y){
  ll res=1;
  for(ll i=0;i<y;i++){
    res*=x;
  }
  return res;
}

ll powmod(ll x,ll y){
  ll res=1;
  for(ll i=0;i<y;i++){
    res=res*x%mod;
  }
  return res;
}

main(){
  ll n;cin >> n;
  ll ans;
  ans = powmod(10,n) - powmod(9,n) - powmod(9,n) + powmod(8,n);
  ans%=mod;
  ans=(ans+mod)%mod;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> p[200010];
int main()
{
    int n,m,i,j,k,x,y,flag=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        p[x].push_back(y);
        p[y].push_back(x);
    }
    for(i=0;i<p[1].size();i++)
    {
        k=p[1][i];
        for(j=0;j<p[k].size();j++)
        if(p[k][j]==n)
        {
            flag=1;
            break;
        }
    }
    if(flag)
        printf("POSSIBLE\n");
    else
        printf("IMPOSSIBLE\n");
    return 0;
}


Measured memory_bytes: 11888
import itertools 


n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
kind = [i for i in range(1, n+1)]
li = list(itertools.permutations(kind))
a = li.index(p)
b = li.index(q)

print(abs(a-b))


Measured memory_bytes: 8052
N = gets.to_i
A = gets.split.map(&:to_i)

S = [0]

A.each do |a|
  S << S.last + a
end

ans = 0

S.group_by { |s| s }.each do |v, list|
  next if list.size == 1

  l = list.size
  ans += l * (l - 1) / 2
end

puts ans


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

using namespace std;

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int table[5][5];
int dp[5][1<<8];
int score[4]={0,60,70,80};

int main(void){
	int T;
	cin >> T;
	rep(loop,T){
		rep(i,5)rep(j,5) cin >> table[i][j];
		rep(i,5)rep(j,1<<8) dp[i][j]=-1;
		dp[0][0]=0;
		rep(i,4)rep(mask,1<<8){
			if(dp[i][mask]==-1) continue;
			rep(mask2,1<<8){
				int sw[4]={0,0,0,0};
				rep(j,4) sw[j]+=(mask>>(2*j))&3;
				rep(j,4) sw[j]+=(mask2>>(2*j))&3;
				rep(j,4) sw[j]%=4;
				int cur=0;
				rep(j,5){
					if(table[i][j]==0)continue;
					int index=table[i][j]-1;
					if(j-1>=0) index=(index+sw[j-1])%4;
					if(j<4) index=(index+sw[j])%4;
					cur+=score[index];
				}
				dp[i+1][mask2]=max(dp[i+1][mask2],dp[i][mask]+cur);
			}
		}
		int ans=0;
		rep(mask,1<<8){
			int sw[4]={0,0,0,0};
			rep(j,4) sw[j]+=(mask>>(2*j))&3;
			rep(j,4) sw[j]%=4;
			int cur=0;
			rep(j,5){
				if(table[4][j]==0)continue;
				int index=table[4][j]-1;
				if(j-1>=0) index=(index+sw[j-1])%4;
				if(j<4) index=(index+sw[j])%4;
				cur+=score[index];
			}
			ans=max(ans,dp[4][mask]+cur);
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
import java.util.Scanner;

public class  Main {

	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()){
			
			int n = Integer.parseInt(sc.next());
			int x = Integer.parseInt(sc.next());
			
			if(n == 0 && x == 0){
				break;
			}
			
			int answer = culculate(n,x);
			System.out.println(answer);
			
		}
		
		
		sc.close();
		
	}

	private static int culculate(int n, int x) {
		
		int answer = 0;
		
		for(int i = 1;i<=n;i++){
			
			for(int j = i+1; j<n;j++){
				
				for(int k = j+1;k<=n;k++){
					
					if(x == (i + j + k)){
						
						answer++;
						
					}
					
					
				}
			}
			
		}
		
		return answer;
	}
}



Measured memory_bytes: 26104
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int g[100010];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int main() {
    int n,L,T;
    long long s=0;
    cin>>n>>L>>T;
    for(int i=0;i<n;i++) {
	int x=gi(),y=gi();
	if(y==1) {
	    g[i]=(x+T)%L;
	    if(T>=L-x) s+=(T-L+x)/L+1;
	}
	else {
	    g[i]=((x-T)%L+L)%L;
	    if(T>=x+1) s-=(T-x-1)/L+1;
	}
    }
    s=(s%n+n)%n,sort(g,g+n);
    for(int i=0;i<n;i++) printf("%d\n",g[(s+i)%n]);
    return 0;
}

Measured memory_bytes: 1536
#include <cstdio>
 
int main()
{
	int N;
	int sum = 0;
 
	scanf("%d", &N);
	int tmp = N;
	while (tmp > 0) {
		sum += tmp % 10;
		tmp /= 10;
	}
	if (N % sum == 0) {
		puts("Yes");
	} else {
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 128
# from math import factorial
# from collections import defaultdict, deque
#  from heapq import heappush, heappop

# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# A = int(input())

A, B = [int(i) for i in input().split(" ")]
total = A
ans = 1
while True:
   if B <= total: break
   ans += 1
   total += A  -1
if B == 1:  print(0)
else: print(ans)




Measured memory_bytes: 2940
import sys

n=int(input())
word=[]
for i in range(n):
	w=input()
	if w in word:
		print("No")
		sys.exit()
	if i>=1 and w[0]!=word[-1][-1]:
		print("No")
		sys.exit()
	word.append(w)
print("Yes")


Measured memory_bytes: 2940
class UnionFindTree:
    def __init__(self, a_elements):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        class ZeroDict(dict):
            def __missing__(self, key):
                self[key] = 0
                return 0 

        class OneDict(dict):
            def __missing__(self, key):
                self[key] = 1 
                return 1 
        self.parents = KeyDict()
        self.ranks = ZeroDict()
        self.sizes = OneDict()

        if a_elements is not None:
            for e in a_elements:
                _ = self.parents[e]
                _ = self.ranks[e]

    def find_root(self, a_x):
        if self.parents[a_x] == a_x:
            return a_x

        self.parents[a_x] = self.find_root(self.parents[a_x])
        return self.parents[a_x]

    def unite(self, a_x, a_y):
        rx = self.find_root(a_x)
        ry = self.find_root(a_y)
        if rx == ry:
            return

        if self.ranks[rx] < self.ranks[ry]:
            self.parents[rx] = ry
            self.sizes[ry] = self.sizes[ry] + self.sizes[rx]
        else:
            self.parents[ry] = rx
            self.sizes[rx] = self.sizes[rx] + self.sizes[ry]
            if self.ranks[rx] == self.ranks[ry]:
                # find_root makes the depth of tree whose root is ry one
                # +1 indicates child ry
                self.ranks[rx] = self.ranks[rx] + 1
    
    def is_same(self, a_x, a_y):
        return self.find_root(a_x) == self.find_root(a_y)

N, M = [int(e) for e in input().split(" ")]
uft = UnionFindTree([i for i in range(1, N+1)])
ABs = []
for _ in range(M):
    ABs.append([int(e) for e in input().split(" ")])
maxValue = N * (N-1) // 2
ans = [maxValue]
flagSkip = False
for i in range(M-1):
    a, b = ABs[M-1-i]
    if flagSkip is True:
        ans.append(0)
        continue
    
    ra = uft.find_root(a)
    rb = uft.find_root(b)
    delta = 0
    if ra != rb:
        size_a = uft.sizes[ra]
        size_b = uft.sizes[rb]
        delta = size_a * size_b
        uft.unite(a, b)
    
    d = ans[-1] - delta
    ans.append(d)
    if d == 0:
        flagSkip = True

txt = "\n".join(map(str, reversed(ans)))
print(txt)


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

using namespace std;

const static int MAX = 100000;
const static int NIL = -1;

typedef struct {
  int parent;
  int left;
  int right;
} Node;

Node T[MAX];
int D[MAX];

void printChildren(int u) {
  int c = T[u].left;
  int i = 0;
  printf("[");
  while (c != NIL) {
    if (i > 0) printf(", ");
    i++;
    printf("%d", c);
    c = T[c].right;
  }
  printf("]");
}

void setDepth(int u, int p) {
  D[u] = p;
  if (T[u].left != NIL) {
    setDepth(T[u].left, p + 1);
  } 
  if (T[u].right != NIL) {
    setDepth(T[u].right, p);
  }
}

int main() {
  int n, id, m, node1, node2, root;

  scanf("%d", &n);
  
  for (int i = 0; i < n; i++) {
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
  }

  for (int i = 0; i < n; i++) {
    scanf("%d", &id);
    scanf("%d", &m);

    node1 = NIL;
    for (int j = 0; j < m; j++) {
      scanf("%d", &node2);
      if (T[id].left == NIL) {
        T[id].left = node2;
      }
      T[node2].parent = id;
      if (node1 != NIL)
        T[node1].right = node2;
      node1 = node2;
    }
  }
  for (int i = 0; i < n; i++) {
    if (T[i].parent == NIL) {
      root = i;
      break;
    }
  }

  setDepth(root, 0);

  for (int i = 0; i < n; i++) {
    printf("node %d: parent = %d, depth = %d, ", i, T[i].parent, D[i]);
    if (T[i].parent == NIL) printf("root, ");
    else if (T[i].left == NIL) printf("leaf, ");
    else printf("internal node, ");
    printChildren(i);
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 4764
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
template<class T> using V=vector<T>; 
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
vector<vector<int>> graph;
int n;
int main(){
    cin>>n;
    graph.resize(n);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        graph[a].emplace_back(b);
        graph[b].emplace_back(a);
    }
    queue<P> q;
    q.emplace(0,0);
    V<V<ll>> dat(2);
    V<bool> used(n,false);
    used[0]=true;
    while(q.size()){
        int now=q.front().fi,c=q.front().se;
        q.pop();
        dat[c].emplace_back(now);
        for(int v:graph[now]){
            if(used[v])continue;
            used[v]=true;
            q.emplace(v,c^1);
        }
    }
    set<ll> s;
    for(int i=1;i<=n;i++)s.insert(i);
    V<ll> ans(n,inf);
    int th=1;
    if(dat[0].size()<=n/3){
        for(int v:dat[0]){
                ans[v]=th*3;
                s.erase(th*3);
                th++;
        }
    }
    else if(dat[1].size()<=n/3){
        for(int v:dat[1]){
                ans[v]=th*3;
                s.erase(th*3);
                th++;
        }

    }
    else{
    for(int i=0;i<2;i++){
        int t=0;
        for(ll v:dat[i]){
            ll val=t*3+(i+1);
            if(val>n){
                if(th*3>n){
                    break;
                }
                ans[v]=th*3;
                s.erase(th*3);
                th++;
                continue;
            }
            ans[v]=val;
            s.erase(val);
            t++;
        }
    }
}
if(s.size()){
    for(int i=0;i<n;i++){
        if(ans[i]==inf){
            ans[i]=*s.begin();
            s.erase(ans[i]);
        }
    }
}
for(int i=0;i<n;i++)cout<<ans[i]<<" ";
cout<<endl;
}

Measured memory_bytes: 25580
#include <bits/stdc++.h>
#define MAX 100005
#define ll long long
#define upperlimit 1000100
#define INF 1e18
#define eps 1e-8
#define endl '\n'
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define MOD 1000000007
#define slld(t) scanf("%lld",&t)
#define sd(t) scanf("%d",&t)
#define pd(t) printf("%d\n",t)
#define plld(t) printf("%lld\n",t)
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define vi vector<int>
#define clr(a) memset(a,0,sizeof(a))
#define debug(a) printf("check%d\n",a)
#define csl ios::sync_with_stdio(false);cin.tie(0);
#define fi(a,b,c) for(int i=a;i<b;i=i+c)
#define fj(a,b,c) for(int j=a;j<b;j+=c)
using namespace std;
 
ll gcd(ll n1,ll n2) {
	if(n1%n2==0)return n2;
	return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent) {
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%MOD;
		base=(base*base)%MOD;
		exponent/=2;
	}
	return ans;
}
ll max(ll a,ll b,ll c) {
	return max(a,max(b,c));
}
int max(int a,int b,int c) {
	return max(a,max(b,c));
}
vi dp(100005, -1), e[100005];
int trav(int i){
	if(dp[i]!=-1){
		//cout<<i<<" ";
		return dp[i];
	}else{
		int mx=-1;
		for(int x=0;x<e[i].size();x++){
			mx=max(mx, trav(e[i][x]));
		}
		dp[i]=mx+1;
		return dp[i];
	}
}
int main()
{
	int n,m;
	sd(n);sd(m);
	for(int i=0;i<m;i++){
		int a,b;
		sd(a);sd(b);
		e[a].pb(b);
	}
	int mx=-1;
	for(int i=0;i<n;i++){
		mx=max(mx, trav(i+1));
	}
	cout<<mx;
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define szz(x) (int) (x).size()
#define FOR(i,a,b) for (int i = (a), _for = (b); i < _for; i++)
#define REP(i,n) FOR(i,0,(n))
#define _ << " " <<
const ll MOD = 1000000007ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll SUB(ll a, ll b) { return a-b >= 0ll ? a-b : a-b+MOD; }
inline ll ADD(ll a, ll b) { return a+b >= MOD ? a+b-MOD : a+b; }
inline ll MUL(ll a, ll b) { return a*b % MOD; }

constexpr int MAX = 300;
double dp[MAX + 3][MAX + 3][MAX + 3];
int n;
double N;

double f(int i, int j, int k) {
  if (i == 0 && j == 0 && k == 0) {
    return 0.0;
  }
  if (dp[i][j][k] > 0.0) {
    return dp[i][j][k];
  }
  double ret = 1.0;
  if (i > 0) {
    double prob = (double)i / N;
    ret += prob * f(i-1,j+1,k);
  }
  if (j > 0) {
    double prob = (double)j / N;
    ret += prob * f(i,j-1,k+1);
  }
  if (k > 0) {
    double prob = (double)k / N;
    ret += prob * f(i,j,k-1);
  }
  double r = i + j + k;
  double p123 = r / N;
  dp[i][j][k] = ret / p123;
  return dp[i][j][k];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  N = (double) n;
  vi fq(4, 0);
  REP(i,n) {
    int x; cin >> x;
    fq[x]++;
  }
  cout << setprecision(12) << f(fq[3], fq[2], fq[1]) << endl;
}

Measured memory_bytes: 217344