akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <array>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <stack>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define MOD ((ll)1000000007)

int main(int argc, char const *argv[])
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	ll A, B, K;
	cin >> A >> B >> K;

	cout << A - min(A, K) << " " << max(B - (K - min(A, K)), (ll)0) << endl;
	return 0;
}


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

using namespace std;
const int mod =1e9+7;
void add_self(int &a,int b)
{
    a+=b;
    if(a>=mod)
    {
        a-=mod;
    }
}
int mul(int a,int b)
{
    return (long long)a*b % mod;
}
int n;
struct M
{
    vector<vector<int>>t;
    M(){
        t.resize(n,vector<int>(n));
    }
    M operator*(const M &b)const{
        M c=M();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                for(int k=0;k<n;k++)
                {
                    add_self(c.t[i][k],mul(t[i][j],b.t[j][k]));
                }
            }
        }
        return c;
    }
};
int main()
{
    long long k;
    scanf("%d%lld",&n,&k);
    vector<vector<int>>can(n,vector<int>(n));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&can[i][j]);      
        }
    }
    M answer=M();
    for(int i=0;i<n;i++)
    {
        answer.t[i][i]=1;
    }
    M m=M();
    m.t=can;
    while(k)
    {
        if(k%2)
        {
            answer=answer*m;
        }
        m=m*m;
        k/=2;
    }
    int total=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            add_self(total,answer.t[i][j]);
        }
    }
    printf("%d\n",total);
    return 0;
}

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

ll modPow(ll a, ll n) {
  if (n == 0) return 1; // 0乗にも対応する場合
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n - 1)) % MOD;
  ll t = modPow(a, n / 2);
  return (t * t) % MOD;
}
ll modComb(ll n,ll a){
  ll x=1,y=1;
  rep(i,a){
    x*=n-i;
    x%=MOD;
    y*=i+1;
    y%=MOD;
  }
  y=modPow(y,MOD-2);
  return (x*y)%MOD;
}

int main(){
  ll N,Q;
  string S;
  cin >> N >> Q >> S;
  vector<ll> dp(N+1,0);
  dp.at(0)=0;
  for(ll i=1;i<N;i++){
    if(S.at(i-1)=='A'&&S.at(i)=='C'){
      dp.at(i+1)=dp.at(i)+1;
    }else{
      dp.at(i+1)=dp.at(i);
    }
  }
  rep(i,Q){
    ll l,r;
    cin >> l >> r;
    cout << dp.at(r)-dp.at(l) << endl;
  }
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define li 100005
#define lo long long
#define fi first
#define FOR for(int i=1;i<=n;i++)
#define	FOr for(int i=n;i>=1;i--)
#define For for(int j=1;j<=n;j++)
#define se second
#define inf 1000000000
using namespace std;
int n,k,m,cevv,cev,orta;
string s;
int main(){
    scanf("%d %d",&n,&m);
    printf("%d",(n-1)*(m-1));
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
int kaijo(int n){
	int ans=1;
	for(int i=2;i<=n;i++){
		ans*=i;
		ans%=MOD;
	}
	return ans;
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
	return kaijo(a)*modpow(kaijo(a-b),MOD-2)%MOD*modpow(kaijo(b),MOD-2)%MOD;
}
int n,m;
bool b[111111];
int dp[111111];
signed main(){
	cin>>n>>m;
	fill(b,b+n+1,true);
	rep(i,m){
		int a;
		cin>>a;
		b[a]=false;
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(b[i]==false)continue;
		if(i==1)dp[i]=dp[i-1];
		else dp[i]=dp[i-1]+dp[i-2];
		dp[i]%=MOD;
	}
	cout<<dp[n]<<endl;
	return 0;
}


Measured memory_bytes: 1152
n,m = map(int,input().split())

if n == m == 1:
    ans = 1
    
elif min(n,m) == 1 and max(n,m) == 2:
    ans = 0
    
elif min(n,m) == 1 and max(n,m) > 2:
    ans = max(n,m) - 2
    
else:
    ans = (n-2) * (m-2)
    
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define inf (1<<30)-1
#define INF (1LL<<62)-1
#define MOD 1000000007LL
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define PI acos(-1)
#define MEM(x,y) memset(x,y,sizeof (x))
#define debug cout<<"A"<<'\n'
#define REP(i,a,b) for (int i=(a); i<=(b); i++)
#define PER(i,a,b) for (int i=(a); i>=(b); i--)
#define REPL(i,a,b) for (LL i=(a); i<=(b); i++)
#define PERL(i,a,b) for (LL i=(a); i>=(b); i--)
#define print(x) cout<<x<<'\n'
#define itrALL(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define UNIQUE(X) X.erase( unique( X.begin(), X.end() ), X.end() )


typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<LL,LL>PLL;
typedef vector<int> VI;
typedef vector<LL> VL;


// Order Statistic Tree

/* Special functions:

        find_by_order(k) --> returns iterator to the kth largest element counting from 0
        order_of_key(val) --> returns the number of items in a set that are strictly smaller than our item
*/

typedef tree<
PII,
null_type,
less<PII>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

template <class T> inline T bigmod(T p,T e,T M)
{
    T ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}

template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
template <class T, class X> inline bool getbit(T a, X i) { T t=1; return ((a&(t<<i))>0);}
template <class T, class X> inline T setbit(T a, X i) { T t=1;return (a|(t<<i)); }
template <class T, class X> inline T resetbit(T a, X i) { T t=1;return (a&(~(t<<i)));}

/*end of header*/

int n,m;
int arr[304][304];
int ptr[304];
int cnt[304];
int dead[304];

int main()
{
    scanf("%d %d",&n,&m);
    int mx=inf,nowmx=0,ind;
    REP(i,1,n)
    {
        REP(j,1,m)scanf("%d",&arr[i][j]);
        ptr[i]=1;
        cnt[arr[i][1]]++;
        nowmx=max(nowmx,cnt[arr[i][1]]);
    }
    mx=min(mx,nowmx);
    while(true)
    {
        nowmx=0;
        REP(i,1,m)
        {
            if(cnt[i]>nowmx)
            {
                nowmx=cnt[i];
                ind=i;
            }
        }
        dead[ind]=1;
        MEM(cnt,0);
        bool flag=1;
        nowmx=0;
        REP(i,1,n)
        {
            while(ptr[i]<=m && dead[arr[i][ptr[i]]])ptr[i]++;
            if(ptr[i]>m)
            {
                flag=0;
                break;
            }
            cnt[arr[i][ptr[i]]]++;
            nowmx=max(nowmx,cnt[arr[i][ptr[i]]]);

        }
        if(flag==0)break;
        mx=min(nowmx,mx);
    }


    print(mx);
    return 0;
}



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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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

const int mod=1000000007;
int MAX=500000;

int N,M;

int fact[500005];
int fact_inv[500005];

class Comb{
public:
    Comb(int N){
        fact[0]=1;
        fact_inv[0]=1;
        for(int i=1;i<=N;++i){
            fact[i]=fact[i-1]*i%mod;
            fact_inv[i]=modPow(fact[i],mod-2);
        }
    }

    int modPow(int a, int n) {
        if(n==1)return a%mod;
        if (n%2==1)return(a*modPow(a,n-1))%mod;
        int t=modPow(a,n/2);
        return (t*t)%mod;
    }

    int comb(int n,int r){
        return (((fact[n]*fact_inv[r])%mod)*fact_inv[n-r])%mod;
    }

    int perm(int n,int k){
        return (fact[n]*fact_inv[n-k])%mod;
    }
};

signed main(){
    Comb C(MAX);
    cin>>N>>M;
    int a=(C.perm(M,N)*C.perm(M,N))%mod;
    for(int k=1;k<=N;++k){
        int houzyo=(C.perm(M-k,N-k)*C.perm(M-k,N-k))%mod;
        houzyo=(houzyo*C.perm(M,k))%mod;
        houzyo=(houzyo*C.comb(N,k))%mod;
        //cout<<houzyo<<endl;
        if(k%2==0)a+=houzyo;
        else a-=houzyo;
        a=(a+mod)%mod;
    }
    cout<<a<<endl;
    //cout<<((a*fact[M]%mod)*fact_inv[M-N])%mod<<endl;
}

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

int main(){
  int X;
  cin>>X;
  int maxsqrt = sqrt(X);
  int ans = 0;
  if(maxsqrt==1){ans = 1;}
  else{
  for(int i = 1;i<=maxsqrt;i++){
    int tmpmax = i;
    for(int j = 1;j < 10;j++){
      if(tmpmax>X){
        if((tmpmax/i)>ans){ans = tmpmax/i;
        }
        break;
      }
      tmpmax*=i;
    }
  }
  }

  cout<<ans<<endl;
}


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

int main(){

  int n, m;

  cin >> n;
  vector<int> v;
  int a[2000*20 + 1];
  int total = 0;

  memset(a,0,sizeof(a));

  for(int i = 0; i < n; i++){
    int k; 
    cin >> k; 
    total+=k;
    v.push_back(k);
  }
  for(int i = 0; i < (1<<n); i++){
    int sum = 0; 
    for(int j = 0; j < n; j++){
      if(i & (1<<j)){
	sum+=v[j];
      }
    }
    a[sum] = 1;

  }
  cin >> m;
  
  for(int i = 0; i < m; i++){
    int k;
    cin >> k;
    if(a[k] == 1) cout << "yes" << endl;
    else cout << "no" << endl;
  }
}

Measured memory_bytes: 1372
/*******************************
Author:galaxy yr
LANG:C++
Created Time:2019/08/10 20:04:35
*******************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m,_time,_end,f[maxn];
long long ans;
struct Node{
    int a,b;
    bool operator<(const Node & p)
    {
        if(b==p.b)
            return a<p.a;
        return b>p.b;
    }
}e[maxn];
int find(int x) { return (f[x]==x?x:f[x]=find(f[x])); }
int main()
{
        //freopen("d.in","r",stdin);
        //freopen("d.out","w",stdout);
        cin>>n>>m; m++;
        for(int i=1;i<=n;i++)
            cin>>e[i].a>>e[i].b;
        sort(e+1,e+n+1);
        for(int i=1;i<=m;i++)
            f[i]=i;
        for(int i=1;i<=n;i++)
        {
            if(m-e[i].a<0)continue;
            int fa=find(m-e[i].a);
            if(fa!=0)
            {
                ans+=e[i].b;
                f[fa]=find(fa-1);
            }
        }
        cout<<ans<<endl;
        return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
void alert(vector<int> vec){
  int64_t N = vec.size();
  for(int i=0; i<N-1; i++) cout << vec.at(i) << " ";
  cout << vec.at(N-1) << endl;
}

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> d(K);
  vector<vector<int>> A(K);
  for(int i=0; i<K; i++){
    cin >> d.at(i);
    for(int j=0; j<d.at(i); j++){
      int a; cin >> a;
      A.at(i).push_back(a-1);
    }
  }
  vector<int> res(N);
  int ans = N;
  for(int i=0; i<K; i++){
    for(int j=0; j<d.at(i); j++){
      int a = A.at(i).at(j);
      if(res.at(a)==0){
        res.at(a)++;
        ans--;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int> pii;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
ll D;
ll pw[20];
ll dx1[20],dx2[20];
vector<ll>v;

void dfs(int s,int e,vector<pair<ll,ll> >&w,ll val,ll cnt){
	if(s==e){
		w.push_back(make_pair(val,cnt));
		return;
	}
	for(int i=-9;i<=9;i++){
		dfs(s+1,e,w,val+v[s]*i,cnt*(s==0?dx2[i+10]:dx1[i+10]));
	}
}

ll solve(int len){
	v.clear();
	for(int i=0;len-1-i>i;i++){
		v.push_back(pw[len-1-i]-pw[i]);
	}
	
	vector<pair<ll,ll> >v1,v2;
	dfs(0,SZ(v)/2,v1,0LL,1LL);
	dfs(SZ(v)/2,SZ(v),v2,0LL,1LL);
	
	map<ll,ll>mp;
	for(int i=0;i<SZ(v1);i++){
		mp[v1[i].first]+=v1[i].second;
	}
	ll ans=0;
	for(int i=0;i<SZ(v2);i++){
		ans+=mp[D-v2[i].first]*v2[i].second;
	}
	if(len%2)ans*=10LL;
	return ans;
}

int main(){
	cin>>D;
	if(D%9!=0){
		cout<<0<<endl;
		return 0;
	}
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			dx1[i-j+10]++;
		}
	}
	for(int i=0;i<10;i++){
		for(int j=1;j<10;j++){
			dx2[i-j+10]++;
		}
	}
	
	pw[0]=1;
	for(int i=1;i<20;i++)pw[i]=pw[i-1]*10;
	
	ll ans=0;
	for(int i=2;i<=18;i++)ans+=solve(i);
	cout<<ans<<endl;
	return 0;
}

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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int 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(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
void ruisekiwa(ll A,vector<int>& digitA){
    int i=1;
    ll amari;
    ll k;
    if(A%4==3||A%4==0){
        digitA.push_back(0);
    }else{
        digitA.push_back(1);
    }
    while(pow(2,i)<=A){
        k=pow(2,i+1);
        amari=A%k;
        if(amari<pow(2,i)){
            digitA.push_back(0);
        }else{
            if(A%2==0){
                digitA.push_back(1);
            }else{
                digitA.push_back(0);
            }
        }
        i++;
    }
}
vector<bool> seen(100010);
vector<ll> D(100010,0);
ll N;
ll M;
vector<LP> G[100010];
bool dfs(ll now){
    seen[now]=true;
    REP(i,G[now].size()){
        P p=G[now][i];
        ll to=p.first;
        ll cost=p.second;
        if(seen[to]){
            if(D[to]!=D[now]+cost){
                return false;
            }
        }else{
            D[to]=D[now]+cost;
            if(!dfs(to))return false;
        }
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    N=in<ll>();
    M=in<ll>();
    REP(i,M){
        ll l,r,d;
        cin>>l>>r>>d;
        l--;r--;
        G[l].push_back(LP(r,d));
        G[r].push_back(LP(l,-d));
    }
    REP(i,N){
        if(!seen[i]){
            if(!dfs(i)){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 18304
n = int(input())
happy, a, b = [], [], []
for i in range(n):
    happy.append(tuple(map(int, input().split())))
happy.sort(key=lambda x: x[0] + x[1], reverse=True)
ans = 0
for i, (a, b) in enumerate(happy):
    if i % 2 == 0:
        ans += a
    else:
        ans -= b
print(ans)


Measured memory_bytes: 21312
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
	scanf("%d",&n);
	if(1<=n&&n<10)
		printf("%d\n",n);
	if(10<=n&&n<100)
		printf("9\n");
	if(100<=n&&n<1000)
		printf("%d\n",n-90);
	if(1000<=n&&n<10000)
		printf("909\n");
	if(10000<=n&&n<100000)
		printf("%d\n",n-9090);
	if(n==100000)
		printf("90909\n");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
typedef long long ll;
int main(){
  ll n,tmp;
  cin >> n;
  ll a[n],sum[n],ans=100000000000;
  for(int i=0;i<n;i++){
    cin >> a[i];
    sum[i]=a[i];
    if(i!=0){
      sum[i]+=sum[i-1];
    }
  }
  for(int i=0;i<n-1;i++){
    tmp = abs(sum[i]-(sum[n-1]-sum[i]));
    ans = min(ans,tmp);
  }
  cout << ans<<endl;
}


Measured memory_bytes: 3328
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication7
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int min = 100000;
            int sum = 0;

            string A,B;

            for (int i = 1; i <= N / 2; i++)
            {
                sum = 0;
                A = i.ToString();
                B = (N - i).ToString();


                for (int j = 0; j < A.Length; j++)
                {
                    sum += int.Parse(A[j].ToString());

                }
                for (int k = 0; k < B.Length; k++)
                {
                    sum += int.Parse(B[k].ToString());

                }
                if (sum < min) { 
                min = sum;
                    }
            }
                Console.WriteLine(min);
            }
        }
    }

Measured memory_bytes: 15184
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n,k ;
	cin >> n >> k ;
	ll ans = k ;
	for(int i=2;i<=n;i++) ans *= (k-1) ;
	cout << ans << endl ;
}


Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()

#define dump2(v) for(auto i:v) { for(auto j:i) std::cout << j << ' '; std::cout << "\n"; }

void dfs(int i, int current, std::vector<std::vector<int> >& from, std::vector<int>& val, std::vector<int>& ans, std::vector<int>& went) {
	went[i] = true;
	current += val[i];
	ans[i] = current;
	for(auto to:from[i]) {
		if(!went[to]) {
			dfs(to,current,from,val,ans,went);
		}
	}
}

signed main() {
	int n,q;
	std::cin >> n >> q;
	std::vector<std::vector<int> > from(n,std::vector<int> ());
	rep(i,n-1) {
		int a,b;
		std::cin >> a >> b;
		a--;b--;
		from[a].emplace_back(b);
		from[b].emplace_back(a);
	}

	std::vector<int> val(n,0);
	rep(i,q) {
		int p,x;
		std::cin >> p >> x;
		p--;
		val[p]+=x;
	}
	std::vector<int> ans(n,0);
	std::vector<int> went(n,false);
	dfs(0,0,from,val,ans,went);

	for(auto i:ans) std::cout << i << ' ';

	return 0;
}


Measured memory_bytes: 33664
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  int N, M;
  scanf("%d",&N);
  scanf("%d",&M);
  std::vector<int > k(M);
  std::vector<std::vector<int> > s(M);
  int s_temp;
  //printf("step0\n");
  for (int i=0; i<M; i++){
    scanf("%d",&k[i]);
    for (int j=0; j<k[i]; j++){
      scanf("%d",&s_temp);
      s_temp--;
      s[i].push_back(s_temp);
    }
  }
  //printf("step1\n");
  std::vector<int > p(M);
  for (int i=0; i<M; i++){
    scanf("%d", &p[i]);
  }
  //printf("step2\n");
  std::vector<int > k_temp(N);
  int ans = 0;
  for (int i=0; i<(1<<N); i++){
    //printf("i=%d\n",i);
    for (int j=0; j<N; j++){
      if ((i&(1<<j))!=0){
        k_temp[j] = 1;
      } else {
        k_temp[j] = 0;
      }
      //printf("k_temp[%d]=%d\n",j,k_temp[j]);
    }
    //printf("judge ok\n");
    bool ok = true;
    for (int j=0; j<M; j++){
      //printf("j=%d\n",j);
      int sum = 0;
      for (int l=0; l<s[j].size(); l++){
        //printf("+=k_temp[%d]=%d\n",s[j][l],k_temp[s[j][l]]);
        sum += k_temp[s[j][l]];
      }
      sum %=2;
      if (sum!=p[j]){
        //printf("sum=%d != k_temp[%d]=%d\n",sum,j,k_temp[j]);
        ok=false;
      }
    }
    if (ok){
      ans++;
    }
  }
  printf("%d\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

#define ll long long
#define all(v) v.begin(),v.end()
#define bootstrap ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);


void solve() {
    int num;
    cin >> num;
    cout << 1 - num;
}

int main() {
    bootstrap;
    solve();
}

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

int main(){
  string s;
  while(std::cin >> s, s != "0"){
    int a = 0, b = 0;
    for (int i = 1; i < s.length(); i++) {
      if(s[i] == 'A')a++;
      else b++;
    }
    if(a - b >= 1)a++;
    else b++;
    std::cout << a << " " << b << std::endl;
  }
  return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;

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

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)


template<class T = ll>
struct Edge {
  int to;
  T cost;
  Edge() {}
  Edge(int to, T cost) : to(to), cost(cost) {}
  bool operator>(const Edge &r) const { return this->cost > r.cost; }
};

template<class T = ll>
vector<T> Dijkstra(vector<vector<Edge<T>>> &edges, int st) {

  int V = (int)edges.size();
  vector<T> dist(V, INFLL);
  dist[st] = 0;

  priority_queue<Edge<T>, vector<Edge<T>>, greater<Edge<T>>> p_que;
  p_que.emplace(st, dist[st]);

  while (!p_que.empty()) {

    Edge<T> now(p_que.top().to, p_que.top().cost);
    p_que.pop();

    if (dist[now.to] < now.cost) continue;
    for (const Edge<T> &e : edges[now.to]) {
      T tmp_cost = now.cost + e.cost;
      if (dist[e.to] > tmp_cost) {
        dist[e.to] = tmp_cost;
        p_que.emplace(e.to, dist[e.to]);
      }
    }
  }

  return dist;
}

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

  ll N,M,S;
  cin>>N>>M>>S;
  S=min(S,5000ll);

  vector<ll>U(M),V(M),A(M),B(M),C(N),D(N);

  REP(i,M){
    cin>>U[i]>>V[i]>>A[i]>>B[i];
    U[i]--;V[i]--;
  }
  REP(i,N){
    cin>>C[i]>>D[i];
  }

  // max5000枚にしてしまうと頂点数がN*5001
  // 頂点番号は都市番号i銀貨Sとして、i*5001+Sとする
  vector<vector<Edge<ll> > > edges(N*5001);
  // 移動の辺
  REP(i,M){
    REP(s,5001){
      //U[i]からV[i]に移動するとA[i]減らしながら、costはB[i]
      if(s-A[i]>=0){
        edges[U[i]*5001+s].emplace_back(V[i]*5001+s-A[i],B[i]);
        edges[V[i]*5001+s].emplace_back(U[i]*5001+s-A[i],B[i]);
      }
    }
  }

  // 両替の辺
  REP(i,N){
    REP(s,5000){
      // sからC[i]枚増やすのにかかるcostがD[i]
      edges[i*5001+s].emplace_back(i*5001+min(5000ll,s+C[i]), D[i]);
    }
  }

  auto ans = Dijkstra<ll>(edges,S);

  FOR(i,1,N){
    ll tmp=INFLL;
    REP(s,5001){
      chmin(tmp,ans[i*5001+s]);
    }
    cout<<tmp<<endl;
  }
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    cin >> n;
    priority_queue<double, vector<double>, greater<double>> que;

    rep(i, n)
    {
        double v;
        cin >> v;
        que.push(v);
    }

    rep(i, n - 1)
    {
        double x = que.top();
        que.pop();
        double y = que.top();
        que.pop();
        que.push((x + y) / 2);
    }

    OP(que.top());

    return 0;
}

Measured memory_bytes: 256
def binarytruck(maxweight,truck,num):
    disp = 0
    for n in range(num):
        if maxweight - targ[n] - disp < 0:
            disp = targ[n]
            truck -= 1
        else:
            disp += targ[n]
    return truck > 0
num,truck = (int(n) for n in input().split(' '))
global targ
targ = []
for n in range(num):
    targ.append(int(input()))
best = max(targ) - 1
worst = sum(targ)
maxweight = (best + worst ) // 2
cnt = 0
while best != worst - 1:
    cnt += 1
    if binarytruck(maxweight,truck,num):
        worst = maxweight
        maxweight = (best + maxweight) // 2

    else:
        best = maxweight
        maxweight = (worst + maxweight) // 2
print(worst)

Measured memory_bytes: 11644
import java.util.*;
 class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long a = in.nextLong();
        long b = in.nextLong();
        long x = in.nextLong();
        System.out.println(countDivisibles(a,b,x));
    }
      public static long countDivisibles(long A, long B, long M)
     {

         if (A % M == 0)
             return (B / M) - (A / M) + 1;

         return (B / M) - (A / M);
     }

 }

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

#define ll long long int
ll mod=1e9+7;

int main()
{
    /* Faster input ouput */
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    /* To read input from a file and output to a file */
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    
    ll t = 1;
    // cin >> t;
    while(t--)
    {        
        ll n,i,j;
        cin >> n;
        ll arr[n];

        for(i=0;i<n;i++)
        {
            cin >> arr[i];
        }

        sort(arr,arr+n);

        ll ans = 0;
        ans += arr[n-1];

        ll count = 0;
        ll present = n-2;
        for(i=n-3;i>=0;i--)
        {
            if(count < 2)
            {
                ans += arr[present];
                count++;
            }

            if(count == 2)
            {
                present--;
                count = 0;
            }
        }

        cout << ans << '\n';
    }
    
    return 0;
}

Measured memory_bytes: 5200
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream> // cout, endl, cin
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
using namespace std;

const long long mod = 1000000007;

int main(){
    long long N;
    cin >> N;
    vector<unsigned long long> A(N + 1);
    cin >> A.at(1);
    vector<unsigned long long> S(N + 1);
    S.at(1) = A.at(1);
    for(long long i = 2; i <= N; i++){
        cin >> A.at(i);
        S.at(i) = S.at(i - 1) + A.at(i);
    }
    unsigned long long sum = 0;
    for(long long i = 1; i <= N; i++){
        sum += (A.at(i) % mod) * ((S.at(N) - S.at(i)) % mod);
      sum = sum % mod;
    }

    cout << sum % mod << endl;
}

Measured memory_bytes: 6408
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    int M = 0;
    int ans;
    for (int i = 0; i < N; i++) {
        int A, B;
        cin >> A >> B;
        if (M < A) {
            M = A;
            ans = A+B;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int inf = 2e9;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, a[N];
vector<int> adj[N];
vector<int> ans;

void dfs(int s, int p, vector<int>& v){
   auto it = lower_bound(v.begin(), v.end(), a[s]);
   int changed = 0;
   if (it != v.end()){
      changed = *it;
      *it = a[s];
   }
   else{
      v.push_back(a[s]);
   }
   ans[s] = lower_bound(v.begin(), v.end(), inf) - v.begin() - 1;
   for(auto i: adj[s]){
      if(i != p){
         dfs(i, s, v);
      }
   }
   if (changed){
      *it = changed;
   }
   else{
      v.pop_back();
   }
}

void solve(){
   cin >> n;

   ans.resize(n+1);
   for (int i = 1; i <= n; ++i)
   {
      cin >> a[i];
   }
   for (int i = 0; i+1 < n; ++i)
   {
      int x, y;
      cin >> x >> y;
      adj[x].push_back(y);
      swap(x, y);
      adj[x].push_back(y);
   }

   vector<int> x(n+1, inf);
   x[0] = 0;
   dfs(1, -1, x);
   for (int i = 1; i <= n; ++i)
   {
      cout<<ans[i]<<"\n";
   }
}

int32_t main(){_
   
   int t = 1;
   //cin >> t;

   while(t--){
     solve();
     cout << endl;
   }
   

   return 0;
}

Measured memory_bytes: 38032
# include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  // taking n value
  cin >> n;
  int A[n];
  int temp, B = 0;
  int C[n];
  // filling the order in which he eats
  for (int i = 0; i < n; i++){
  	cin >> A[i];
  }
  // satisfaction when he eats a dish
  for(int i = 0; i < n; i++){
  	cin >> temp;
    B += temp;
  }
  // additional satisfaction array
  for (int i = 0; i < n-1; i++){
  	cin >> C[i];
  }  
  // adding
  for (int i = 0; i < n-1; i++){
  	if(A[i+1] == A[i]+1)
      B += C[A[i]-1];
  }
  cout << B <<'\n';
	
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const int MOD = 998244353;
const ll INF = 1000000000000000000;


int main()
{
	int N;
	cin >> N;
	set<int> st;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		if (st.find(A) != st.end()) st.erase(A);
		else st.insert(A);
	}
	cout << st.size() << endl;
}

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

using namespace std;

long long int n,i,j,k;
long long int kompatybilnosc[17][17];
long long int tablica[1<<17];
long long int dp[1<<17];

int main() {
	cin >> n;
	for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            cin >> kompatybilnosc[i][j];
        }
	}
	for(i=1;i<1<<n;i++){
		for(j=0;j<n;j++){
			if(i>>j&1){
				tablica[i]=tablica[i^(1<<j)];
				for(k=0;k<n;k++){
                    if(i>>k&1){
                        tablica[i]+=kompatybilnosc[j][k];
                    }
				}
			}
		}
	}
	for(i=1;i<1<<n;i++){
		for(j=i;j!=0;j=(j-1)&i){
			dp[i]=max(dp[i],dp[i^j]+tablica[j]);
		}
	}
	cout<<dp[(1<<n)-1];
}


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

int comb(int x, int y){
    int ans = 1, i;
    for(i = 0; i < y; i++){
        ans *= x - i;
    }
    for(i = 1; i <= y; i++){
        ans /= i;
    }
    return ans;
}

int par(int x, int y){
    int ans = 1, i;
    for(i = 0; i < y; i++){
        ans *= x - i;
    }
    return ans;
}

int main(void){
    int n;
    cin >> n;
    
    int p[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
    int p_cnt[15] = {0};
    
    int cp_i, j;
    for(int i = 2; i <= n; i++){
        cp_i = i;
        j = 0;
        while(j < 15){
            if(cp_i % p[j] == 0){
                p_cnt[j]++;
                cp_i /= p[j];
            }else{
                j++;
            }
        }
    }
    
    int ans = 0;
    if(p_cnt[0] >= 74){
        ans++;
    }
    
    int cnt2 = 0, cnt4 = 0, cnt14 = 0, cnt24 = 0;
    
    for(int i = 0; i < 15; i++){
        if(p_cnt[i] >= 24){
            cnt24++;
        }else if(p_cnt[i] >= 14){
            cnt14++;
        }else if(p_cnt[i] >= 4){
            cnt4++;
        }else if(p_cnt[i] >= 2){
            cnt2++;
        }
    }
    
    ans += (cnt4 + cnt14 + cnt24) * comb(cnt4 + cnt14 + cnt24 - 1, 2);
    ans += cnt2 * comb(cnt4 + cnt14 + cnt24, 2);
    
    ans += par(cnt14 + cnt24, 2);
    ans += cnt4 * (cnt14 + cnt24);
    
    ans += par(cnt24, 2);
    ans += (cnt2 + cnt4 + cnt14) * cnt24;
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
ll n, m, k;
map<ll, ll> MAP;
ll num;
void dfs(int cnt) {
  if(cnt == n) {
    MAP[max(1LL, num-k)]++;
  } else {
    FOR(i,1,m+1) {
      num += i;
      dfs(cnt+1);
      num -= i;
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  while(cin>>n>>m>>k,n||m||k) {
    num = 0;
    MAP.clear();
    ll waru = pow(m, n);
    dfs(0);
    double ans = 0;
    for(auto M : MAP) {
      ans += (double)M.first * M.second / waru;
    }
    printf("%.10lf\n", ans);
  }
  return 0;
}

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  
  int sum = 0;
  
  for (int i = 1; i <= N; i++) {
    int amount = i;
    int c5 = amount / 10000;
    amount %= 10000;
    int c4 = amount / 1000;
    amount %= 1000;
    int c3 = amount / 100;
    amount %= 100;
    int c2 = amount / 10;
    amount %= 10;
    int c1 = amount;
    
    int c = c5 + c4 + c3 + c2 + c1;
    if (A <= c && c <= B) {
      sum += i;
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 3528
#include <iostream>
#include <vector>
#include <algorithm>
#define all(a) a.begin(),a.end()
using namespace std;
typedef pair<int,int> P;

int main(){
  int n;
  cin >> n;
  vector<P> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i].first; a[i].first--;
    a[i].second=i+1;
  }
  sort(all(a));
  vector<int> ans(n*n);
  for(int i=0;i<n;i++) ans[a[i].first]=a[i].second;
  int now=0;
  int k=a[now].second-1;
  int nnow=0;
  int nk=n-a[nnow].second;
  for(int i=0;i<n*n;i++){
    if(ans[i]==0){
      while(k==0){
        now++;
        k=a[now].second-1;
      }
      ans[i]=a[now].second;
      k--;
      if(now>=n){
        //cerr << i << endl;
        while(nk==0){
          nnow++;
          nk=n-a[nnow].second;
        }
        ans[i]=a[nnow].second;
        nk--;
      }
    }
  }
  //for(int i=0;i<n;i++) cout << a[i].first << ' ' << a[i].second << endl;
  vector<int> check(n);
  int x=0;
  for(int i=0;i<n*n;i++){
    check[ans[i]-1]++;
    if(a[x].first==i){
      if(check[ans[i]-1]!=ans[i]){
        cout << "No" << endl;
        return 0;
      }
      x++;
    }
  }
  cout << "Yes" << endl;
  for(int i=0;i<n*n;i++) cout << ans[i] << ' ';
  cout << endl;
}

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

#define REP(i,n) for (int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()

using namespace std;

template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

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

    int N, M;
    cin >> N >> M;
    vector<vector<int>> A(N, vector<int>(M));
    REP(i, N) REP(j, M) {
        cin >> A[i][j];
        --A[i][j];
    }
    
    int result = N;
    vector<bool> is_open(M, true);
    int n_opens = M;
    while (n_opens >= 2) {
        vector<int> cnt(M);
        REP(i, N) {
            REP(j, M) {
                if (is_open[A[i][j]]) {
                    cnt[A[i][j]]++;
                    break;
                }
            }
        }
        int k = max_element(all(cnt)) - cnt.begin();
        amin(result, cnt[k]);
        is_open[k] = false;
        --n_opens;
    }

    cout << result << endl;

    return 0;
}


Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		int m=i,c=0;
		while(m>0) {
			m/=10;++c;
		}
		if(c%2) ++ans;
	}
	printf("%d",ans);
	return 0;
}

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
	os << p.first << " " << p.second;
	return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}
/*
typedef __int128_t Int;
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
  if (s) {
	__uint128_t tmp = value < 0 ? -value : value;
	char buffer[128];
	char *d = std::end(buffer);
	do {
	  --d;
	  *d = "0123456789"[tmp % 10];
	  tmp /= 10;
	} while (tmp != 0);
	if (value < 0) {
	  --d;
	  *d = '-';
	}
	int len = std::end(buffer) - d;
	if (dest.rdbuf()->sputn(d, len) != len) {
	  dest.setstate(std::ios_base::badbit);
	}
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
	if ('0' <= s[i] && s[i] <= '9')
	  ret = 10 * ret + s[i] - '0';
  return ret;
}
*/

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template <class T> bool chmin(T &a, const T &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N; cin >> N;
	int NN = N;
	N -= N & 1;
	vector<pii>ans;
	rep(i, 1, N + 1) {
		rep(j, i + 1, N + 1) {
			if (i + j != N + 1) {
				ans.eb(i, j);
			}
		}
	}
	if (NN % 2 == 1) {
		rep(i, 1, NN) {
			ans.eb(i, NN);
		}
	}
	cout << ans.size() << endl;
	for (auto p : ans) {
		cout << p << endl;
	}

	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>				//Written by ThiDaiLoc
using namespace std;				//Team Three Wolves
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> trp;
typedef vector<ll> vi;
typedef vector<pll> vp;

#define fu(i,a,b)   for(ll i=a;i<=b;i++)
#define f1(i,n)     for(ll i=1;i<=n;i++)
#define fs(i,s)     for(ll i=0;i+1<=s.length();i++)
#define fd(i,b,a)   for(ll i=b;i>=a;i--)
#define fuv(i,a)    for(ll i=0;i<a.size();i++)
#define fdv(i,a)    for(ll i=(ll)a.size()-1;i>=0;i--)
#define ms(a,x)     memset(a, x, sizeof a)
#define prec(n)     fixed<<setprecision(n)
#define uni(a)      (a).erase(unique(all(a)), (a).end())
#define pb(i)       push_back(i)
#define pob         pop_back()
#define sc(a)       cin>>a
#define sc2(a,b)    cin>>a>>b
#define sc3(a,b,c)  cin>>a>>b>>c
#define pr(a)       cout<<a<<endl
#define pr2(a,b)    cout<<a<<" "<<b<<endl
#define rpr(a)      return cout<<a<<endl,0
#define prY         cout<<"YES"<<endl
#define prN         cout<<"NO"<<endl
#define bit(n,i)    (((n)>>(i))&1)
#define lowb(a,n,x) lower_bound(a,a+n,x) -a
#define lowb2(a,x)  lower_bound(all(a),x) -a.begin()
#define all(x)      (x).begin(), (x).end()
#define sz(a)       (ll)a.size()
#define le(s)       (ll)s.length()		
#define re          return 	
#define	mp(a,b)     make_pair(a,b)
#define	mp3(a,b,c)  make_pair(a,make_pair(b,c))
#define se          second
#define fi          first 
#define sse         second.second
#define sfi         second.first
#define soA         sort(A+1,A+1+n)
#define so(A,n)     sort(A+1,A+1+n)
#define sov(v)      sort(all(v))
#define sovr(v)     sort(all(v),greater<ll>())
#define debug(x)    cerr << #x << " = " << x << endl
#define INPUT       freopen("locin.txt", "r", stdin)
#define OUTPUT      freopen("locout.txt", "w", stdout)
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline ll mnz(ll& a,ll b){return a=(a>b?b:a);}
inline ll mxz(ll& a,ll b){return a=(a<b?b:a);}
inline string toString(ll n) {stringstream ss; ss << n;return ss.str();}
double const eps = 1e-6;
ll const Base=1e9+7,oo=1e17,MAXN=1e6;


ll A[MAXN+5];

ll Solves(){
	
	ll n,m,k,cnt=0,ans=0,x,y,q,c,sum=0,v,t;
	// PROCESS IN HERE
	sc2(n,m);
	pr(n/m+(n%m!=0));
	
	
	
	
	
	
	re 0;
	// Hack it if you can :)
}

int main(){
	//INPUT;
	if(fopen("locin.txt", "r"))INPUT;
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll test=1;
//	sc(test);
	fu(T,1,test){
//		cout<<"Case #"<<T<<": ";
		Solves();
	} 		
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  ll N = s.size();
  vvll a(26, vll(0));
  vvll num(26, vll(0));
  for(int i = 0; i < N; i++){
    ll aa = s.at(i) - 'a';
    a.at(aa).push_back(i);
  }
  ll ans = INF;
  for(int i = 0; i < 26; i++){
    ll tmp = a.at(i).size();
    if(tmp == 0) continue;
    for(int j = 0; j < tmp; j++){
      if(j == 0) num.at(i).push_back(a.at(i).at(j));
      else{
        num.at(i).push_back(a.at(i).at(j) - a.at(i).at(j-1) - 1);
      }
    }
    num.at(i).push_back(N - 1 - a.at(i).at(tmp-1));
    sort(ALL(num.at(i)), greater<ll>());
    chmin(ans, num.at(i).at(0));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,a=0,b=0,c=0,d=0,e=0,ans=0;
  cin >> n;
  for(int i=0;i<n;i++){
    string s;
    cin >> s;
    if(s[0]=='M'){
      a++;
    }else if(s[0]=='A'){
      b++;
    }else if(s[0]=='R'){
      c++;
    }else if(s[0]=='C'){
      d++;
    }else if(s[0]=='H'){
      e++;
    }
  }
  if(a+b+c+d+e<3){
    cout << ans << endl;
    return 0;
  }
  int x=0;
  if(a!=0){
    x++;
  }
  if(b!=0){
    x++;
  }
  if(c!=0){
    x++;
  }
  if(d!=0){
    x++;
  }
  if(e!=0){
    x++;
  }
  if(x<3){
    cout << ans << endl;
    return 0;
  }
  if(a!=0&&b!=0&&c!=0){
    ans+=a*b*c;
  }
  if(a!=0&&b!=0&&d!=0){
    ans+=a*b*d;
  }
  if(a!=0&&b!=0&&e!=0){
    ans+=a*b*e;
  }
  if(a!=0&&c!=0&&d!=0){
    ans+=a*c*d;
  }
  if(a!=0&&c!=0&&e!=0){
    ans+=a*c*e;
  }
  if(a!=0&&d!=0&&e!=0){
    ans+=a*d*e;
  }
  if(b!=0&&c!=0&&d!=0){
    ans+=b*c*d;
  }
  if(b!=0&&c!=0&&e!=0){
    ans+=b*c*e;
  }
  if(b!=0&&d!=0&&e!=0){
    ans+=b*d*e;
  }
  if(c!=0&&d!=0&&e!=0){
    ans+=c*d*e;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int A,B,i,s,l,a,b,c;
  cin >> A >> B;
  s = 0;
  for (i=A;i<B+1;i++){
    l = i;
    a = i % 10;
    l /= 10;
    b = l%10;
    l /= 100;
    c = l % 10;
    l /= 10;
    if(a == l && b == c)
      s++;
  }
  cout << s << endl;
}

Measured memory_bytes: 256