akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
bool isect (int l1, int r1, int l2, int r2){
    pii p1,p2;
    p1 = mp(l1,r1); p2 = mp(l2,r2);
    if(p1>p2)swap(p1,p2);
    if(p2.fi <= p1.se)return true;
    else return false;
}
ll fexp (ll num1, ll num2, ll MOD){
    if(num2==0)return 1;
    else if(num2==1)return num1;
    else{
        ll temp = fexp (num1,num2/2,MOD); ll res = ((temp%MOD) * (temp%MOD))%MOD;
        if(num2%2==1) res = ((res%MOD)*(num1%MOD))%MOD; return res;
    }
}
ll invmod (ll num, ll MOD){return fexp (num,MOD-2,MOD);}
ll gcd (ll num1, ll num2){
    if(num1 < num2) swap(num1,num2); ll num3 = num1 % num2 ;
    while(num3 > 0){ num1 = num2; num2 = num3; num3 = num1 % num2;}
    return num2;
}
ll lcm (ll num1 , ll num2){return (ll) (num1/gcd(num1,num2))*num2;}

// end of Template

int n,c;
ll memo[200][100010],v[100010],w[100010];
bool calc[200][100010];
ll dp (ll x, ll y){
    if(x>n)return 0;
    else if(calc[x][y])return memo[x][y];
    else{
        // dont take
        ll res = 0;
        res = max(res, dp(x+1,y));

        //take
        if(w[x]<=y){res = max(res,v[x] + dp(x+1,y-w[x]));}

        calc[x][y]=true;
        memo[x][y]=res;
        return res;
    }
}
int main(){

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];

    cout<<dp(1,c);
}


Measured memory_bytes: 89856
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	char s[15];cin>>s;
	if(s[0]!='A'){
		cout<<"WA";return 0;
	}
	if(count(s+2,s+strlen(s)-1,'C')!=1){
		cout<<"WA";return 0;
	}
	if(count_if(s+1,s+strlen(s),[](char c){return c>='A'&&c<='Z';})>1){
		cout<<"WA";return 0;
	}
	cout<<"AC";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using ll = long long;
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if (a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
}


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

int main() {
int a,b;
  cin>>a>>b;
  if(a<0&&b>0){
    cout<<"Zero"<<endl;
  return 0;}
  if(a==0||b==0){
    cout<<"Zero"<<endl;
  return 0;}
  
  if(a>0){
    cout<<"Positive"<<endl;
    return 0;}
  if(b<0){
    int n=b-a+1;
    if(n%2==0){
      cout<<"Positive"<<endl;
      return 0;}
    else{
      cout<<"Negative"<<endl;
      return 0;}
  }
  
}

Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]
v = []
for i in range(n):
    a, b = [int(i) for i in input().split()]
    v.append((a, b))

ans = 0
for a, b in sorted(v):
    if m > b:
        ans += a * b
        m -= b
    else:
        ans += a * m
        break
print(ans)


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


double distance(double x1, double y1, double x2, double y2) {
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

int factorial(int n) {
    if (n > 1)
        return n * factorial(n - 1);
    else
        return 1;
}

int main() {
    int N; cin >> N;
    vector<pair<double, double>> coordinates(N);
    for (int i = 0; i < N; i++) {
        double x, y; cin >> x >> y;
        coordinates[i].first = x;
        coordinates[i].second = y;
    } 

    vector<int> v(N);
    iota(v.begin(), v.end(), 0);
    double ans = 0.0;
    do {
        for (int i = 0; i < N - 1; i++) {
            ans += distance(coordinates[v[i]].first, coordinates[v[i]].second, coordinates[v[i + 1]].first, coordinates[v[i + 1]].second);
        }
    } while (next_permutation(v.begin(), v.end()));

    cout << fixed;
    cout << setprecision(6) << ans / (double)factorial(N) << endl;
    return 0;
}

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

int dist(int a, int b){
  int sa;
  if (a<b){
    sa=b-a;
  } else {
    sa=a-b;
  }

  return sa;

}

int main(){
  int w, h, n, i, count=0;
  int x[10000], y[10000];

  cin >> w >> h >> n;

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

  for (i=1; i<n; i++){
    count+=dist(x[i],x[i-1])+dist(y[i],y[i-1]);
    if ((x[i]-x[i-1])*(y[i]-y[i-1])>0){
      w=dist(x[i],x[i-1]); h=dist(y[i],y[i-1]);
      if (w<h){
	count-=w;
      } else {
	count-=h;
      }
    }
  }

  cout << count << endl;

  return 0;

}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main(){
    ll a,b,q;
    cin>>a>>b>>q;
    vector<ll> s(a+2),t(b+2), xl(q);
    s[0]=-1e18;
    t[0]=-1e18;
    for(int i = 0; i < a; i++)
    {
        cin>>s[i+1];
    }
    for(int i = 0; i < b; i++)
    {
        cin>>t[i+1];
    }
    s[a+1]=1e18;
    t[b+1]=1e18;
    for(int i = 0; i < q; i++)
    {
        cin>>xl[i];
    }
    for(int i = 0; i < q; i++)
    {
        ll x = xl[i];
        ll s1, s2, t1, t2, ans=1e18;
        s1 = s[lower_bound(all(s),x)-s.begin()-1];
        s2 = s[lower_bound(all(s),x)-s.begin()];
        t1 = t[lower_bound(all(t),x)-t.begin()-1];
        t2 = t[lower_bound(all(t),x)-t.begin()];
        //cout<<s1<<"\t"<<s2<<"\t"<<t1<<"\t"<<t2<<endl;
        ans = min(ans, abs(x-s1)+abs(s1-t1));
        ans = min(ans, abs(x-t1)+abs(s1-t1));

        ans = min(ans, abs(x-s1)+abs(s1-t2));
        ans = min(ans, abs(x-t2)+abs(s1-t2));

        ans = min(ans, abs(x-s2)+abs(s2-t1));
        ans = min(ans, abs(x-t1)+abs(s2-t1));

        ans = min(ans, abs(x-s2)+abs(s2-t2));
        ans = min(ans, abs(x-t2)+abs(s2-t2));

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

Measured memory_bytes: 3712
#include <cstdio>

int main() {
    int a;
    int c5 = 0, c7 = 0;

    for (int i = 0; i < 3; i++) {
        scanf("%d", &a);
        if (a == 5) c5++;
        if (a == 7) c7++;
    }

    if (c5 == 2 && c7 == 1) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1e18;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> void puts(T x) { std::cout << x << std::endl; }
using namespace std;

ll N, K, Q;
ll p[100010];

int main() {
    cin >> N >> K >> Q;

    rep(i, N) p[i] = K - Q;

    rep(i, Q) {
        ll a; cin >> a;
        p[a-1]++;
    }

    rep(i, N) {
        if (p[i] > 0) puts("Yes");
        else puts("No");
    }
}


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

#define reint register int
#define coint const int

using namespace std;

coint SIZE = 100000 + 5;

char li[SIZE];
int len, dis[SIZE], cnt[SIZE];

inline int nxt(coint x) { return li[x] == 'L' ? x - 1 : x + 1; }

int main(void) {
    scanf("%s", li + 1), len = strlen(li + 1);
    memset(dis, -1, sizeof dis);
    for (reint i = 1; i < len; ++i)
        if (li[i] == 'R' && li[i + 1] == 'L') dis[i] = dis[i + 1] = 0;
    for (reint i = 2; i <= len; ++i)
        if (dis[i] && li[i] == 'L') dis[i] = dis[i - 1] + 1;
    for (reint i = len - 1; i; --i)
        if (dis[i] && li[i] == 'R') dis[i] = dis[i + 1] + 1;
    //for (reint i = 1; i <= len; ++i)
        //printf("len[%d] = %d\n", i, dis[i]);
    for (reint i = 1; i <= len; ++i) {
        int ind;
        if (li[i] == 'L') ind = i - dis[i];
        else ind = i + dis[i];
        if (dis[i] & 1) ind = nxt(ind);
        ++cnt[ind];
    }
    for (reint i = 1; i <= len; ++i)
        printf("%d%c", cnt[i], " \n"[i == len]);
    return 0;
}



Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define pow power
#define int long long
using namespace std;
const int mod=1e6+3;
int sqr(int x){return x*x%mod;}
int pow(int a,int n){return !n?1:sqr(pow(a,n/2))*(n&1?a:1)%mod;}
int inv(int x){return pow(x,mod-2);}
int x,d,n,q,f[mod+3],invf[mod+3];
main()
{
	f[0]=1;
	for(int i=1;i<mod;i++)f[i]=f[i-1]*i%mod;
	invf[mod-1]=inv(f[mod-1]);
	for(int i=mod-2;i>=0;i--)invf[i]=invf[i+1]*(i+1)%mod;
	cin>>q;
	while(q--)
	{
		cin>>x>>d>>n;n--;
		if(!d){cout<<pow(x,n+1)<<'\n';continue;}
		int lim=(mod-x*inv(d)%mod)%mod;
		if(n>=lim){cout<<"0\n";continue;}
		cout<<pow((mod-d)%mod,n+1)*f[lim]%mod*invf[lim-n-1]%mod<<'\n';
	}
}


Measured memory_bytes: 16512
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MAX 200003
#define MOD 1000000007
typedef int FLOW;

int main(){
  int N;
  cin>>N;
  vector<int> p(N);
  for(int i=0;i<N;i++){
    cin>>p.at(i);
  }
  vector<int> a(N),b(N);
  for(int i=0;i<N;i++){
    a.at(i)=30000*(i+1);
    b.at(i)=30000*(N-i);
  }
  for(int i=0;i<N;i++){
    a.at(p.at(i)-1)+=i;
    b.at(p.at(i)-1)+=i;
  }

  for(int i=0;i<N;i++){
    cout<<a.at(i)<<" ";
  }
  cout<<endl;
  for(int i=0;i<N;i++){
    cout<<b.at(i)<<" ";
  }
  cout<<endl;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long n,a;
    map<long,long>mp;
    cin>>n;
    for(int i=0; i<n-1; i++)
    {
        cin>>a;
        mp[a]++;
    }
   for(int i=1;i<=n;i++)
   {
         cout<<mp[i]<<endl;
   }

}


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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

ll n,a,b,c,d;
map<ll,ll> f;

ll getans(ll n){
	if(!n) return 0;
	if(n==1) return d;
	if(f.count(n)) return f[n];
	ll res;
	if((1ll<<60)/d<n) res=1ll<<60;
	else res=n*d;
	if(n%2==0) chkmin(res,getans(n/2)+a);
	else chkmin(res,getans(n/2+1)+a+d),chkmin(res,getans(n/2)+a+d);
	if(n%3==0) chkmin(res,getans(n/3)+b);
	else chkmin(res,getans(n/3+1)+b+(3-n%3)*d),chkmin(res,getans(n/3)+b+n%3*d);
	if(n%5==0) chkmin(res,getans(n/5)+c);
	else chkmin(res,getans(n/5+1)+c+(5-n%5)*d),chkmin(res,getans(n/5)+c+n%5*d);
	return f[n]=res;
}

int main(){
	int T=readint();
	while(T--){
		n=readint(); a=readint(); b=readint(); c=readint(); d=readint();
		f.clear();
		printf("%lld\n",getans(n));
	}
	return 0;
}

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

int main(){
    ll l, r;
    cin >> l >> r;
    r = min(r, l + 4038);
    int ans = 2018;
    for (ll i = l; i <= r; i++){
    for(ll j = i + 1; j <= r; j++){
        int x = i * j % 2019;
        ans = min(ans, x);
    }
    }
  cout << ans << endl;  
    }

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,f,s[14][8],t,h,ans;
int main()
{
  scanf("%d%d",&n,&f);
  for(int i=1;i<=11;i++)
    for(int j=1;j<=7;j++)
    {
      t++;
      s[i][j]=t;
    }
  for(int i=1;i<=11;i++)
    for(int j=1;j<=7-3+1;j++)
    {
      t=0;
      for(int k=0;k<3;k++)
        for(int l=0;l<3;l++)
          t+=s[(i+k-1)%11+1][j+l];
      if(t%11==f)h++;
    }
  ans+=max(0,(n/11-1))*h;
  if(n/11>0)n-=(n/11-1)*11;
  for(int i=1;i<=n-3+1;i++)
    for(int j=1;j<=7-3+1;j++)
    {
      t=0;
      for(int k=0;k<3;k++)
        for(int l=0;l<3;l++)
          t+=s[(i+k-1)%11+1][j+l];
      if(t%11==f)ans++;
    }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 256
//#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

//ifstream cin("tema.in");
//ofstream cout("tema.out");

const int MAXN = 200000;

vector<vector<int> > g1, g2;
bool seen1[1 + MAXN], seen2[1 + MAXN];
int which1[1 + MAXN], which2[1 + MAXN];
int answer[1 + MAXN];
int components1 = 0, components2 = 0;

void BFS(int start, bool seen[], const vector<vector<int> > &g, int current, int which[]) {
    queue<int> Queue;
    Queue.push(start);
    seen[start] = true;
    which[start] = current;
    while (!Queue.empty()) {
        int node = Queue.front();
        Queue.pop();
        for (auto &it : g[node])
            if (!seen[it]) {
                seen[it] = true;
                which[it] = current;
                Queue.push(it);
            }
    }
}

struct Node {
    pair<int, int> value;
    int index;

    bool operator < (const Node &other) const {
        return value < other.value;
    }
};

Node nodes[1 + MAXN];

int main() {
    int n, k, l;
    cin >> n >> k >> l;
    g1.resize(n + 1);
    g2.resize(n + 1);
    for (int i = 1; i <= k; i++) {
        int a, b;
        cin >> a >> b;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    for (int i = 1; i <= l; i++) {
        int a, b;
        cin >> a >> b;
        g2[a].push_back(b);
        g2[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (!seen1[i]) {
            components1++;
            BFS(i, seen1, g1, components1, which1);
        }
        if (!seen2[i]) {
            components2++;
            BFS(i, seen2, g2, components2, which2);
        }
        nodes[i] = {make_pair(which1[i], which2[i]), i};
    }
    sort(nodes + 1, nodes + n + 1);
    for (int i = 1, j; i <= n; i = j) {
        int value = 0;
        j = i;
        while (j <= n && nodes[i].value == nodes[j].value) {
            value++;
            j++;
        }
        j = i;
        while (j <= n && nodes[i].value == nodes[j].value) {
            answer[nodes[j].index] = value;
            j++;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << answer[i] << " ";
    return 0;
}


Measured memory_bytes: 21028
A = input() + 'x'
B = input() + 'y'
C = input() + 'z'

d = 'a'
while  True:
    if d == 'a':
        d = A[0]
        A = A[1:]
    if d == 'b':
        d = B[0]
        B = B[1:]
    if d == 'c':
        d = C[0]
        C = C[1:]
    if d == 'x':
        print('A')
        break
    if d == 'y':
        print('B')
        break
    if d == 'z':
        print('C')
        break


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

int main(){
    ll a, b; cin >> a >> b;
    ll gcd;
    while(true){
        swap(a,b);
        b = b % a;
        if(b == 0){
            gcd = a;
            break;
        }
    }

    ll ans = 1;
    for (ll i = 2; i*i <= gcd; i++) {
        if(gcd % i == 0){
            ans++;
            while(gcd % i == 0){
                gcd /= i;
            }
        }
      	if(gcd == 1) break;
	}
    if(gcd != 1) ans++;

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main(){
	char a[N + 1];
	char b[N + 1];
	char c[30];
	bool d[30];
	f(i, N + 1){
		a[i] = 0;
		b[i] = 0;
	}
	f(i, 30){
		c[i] = 0;
		d[i] = false;
	}

	int n;
	bool v = true;
	scanf("%s", a);
	scanf("%s", b);
	n = strlen(a);
	f(i, n){
		if (c[(a[i] - 'a')] == 0){
			c[(a[i] - 'a')] = b[i];
			if (d[b[i] - 'a'])v = false;
			else d[b[i] - 'a'] = true;
		}
		else{
			if (c[(a[i] - 'a')] != b[i])v = false;
		}
	}

	if(v)printf("Yes\n");
	else printf("No\n");


	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <math.h>
int main()
{
    int N;
    scanf("%i", &N);
    int array[N];
    for (int i = 0; i < N; i++) {
        scanf("%i", &array[i]);
    }
    int max = array[0];
    for (int j = 0; j < N;j++) { 
        if (array[j] > max) {
            max = array[j];
        }
    }
    printf("%i ", max);
    double mid = max / 2.0;
    double ans = array[0];
    for (int k = 0; k < N;k++) { 
        if (array[k] == max) {
            continue;
        }
        if (fabs(array[k]-mid) <= fabs(ans-mid)) {
            ans = array[k];
        }
    }
    printf("%i\n", (int)ans);
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
ll d,a;
pair<ll,ll> ms[200001];
map<ll,ll> mp;
ll e[200001];
int main(){
	cin>>n>>d>>a;
	rep(i,n){
		ll x,h;
		cin>>x>>h;
		ms[i]=m_p(x,h);
	}
	sort(ms,ms+n);
	int last=0;
	memset(e,-1ll,sizeof(e));
	rep(i,n){
		for(;last<n;last++){
			if(ms[last].fr>ms[i].fr+2ll*d)
			break;
		}
		e[i]=ms[last-1].fr;
	}
	ll ans=0ll;
	for(int i=0;i<n;i++){
		int j=i+1;
		ll s=ms[i].se;
		s=(s+a-1ll)/a;
		ans+=s;
		s*=a;
		mp[e[i]]=s;
		while(j<n&&ms[j].fr<=ms[i].fr+2ll*d){
			if(ms[j].se>s){
				ms[j].se-=s;
				ll s1=ms[j].se;
				s1=(s1+a-1ll)/a;
				ans+=s1;
				s1*=a;
				s+=s1;
				mp[e[j]]+=s1;
				i=j;
			}
			s-=mp[ms[j].fr];
			mp[ms[j].fr]=0ll;
			j++;
		}
		i=j-1;
	}
	cout<<ans;
	re 0;
}


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

int main(){
  long long h,w;
  cin >> h >> w;
  if (min(h,w)==1){
    cout << 1 << endl;
    return 0;
  }
  long long n=h*w;
  long long ans = (n+1)/2;
  cout << ans << endl;
  return 0;
}


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

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

fn main() {
    let s: u32 = read();

    let cnt1 = s / 100;
    let cnt2 = (s - 100 * cnt1)  / 10;
    let cnt3 = (s - (100 * cnt1) - (10 * cnt2))  / 1;

    println!("{}", cnt1 + cnt2 + cnt3);
}


Measured memory_bytes: 4352
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
	static void solve(){//Here is the main function
		  int N = nextInt();
		  ArrayList<Integer> list = nextIntArray();
		  int count = 0;
		  for(int i = 1; i < N - 1; i++){
		    if((list.get(i - 1) < list.get(i) && list.get(i) < list.get(i + 1)) || (list.get(i - 1) > list.get(i) && list.get(i) > list.get(i + 1))){
		      count++;
		    }
		  }
		  myout(count);
	}
	//Method addition frame start




	//Method addition frame end
}


Measured memory_bytes: 32544
s1=input()
s=list(s1)

if s[0]=='R' and s[1]=='S' and s[2]=='R':
    print('1')
elif s[0]=='R' and s[1]=='R' and s[2]=='R':
    print('3')
elif s[0]=='R' and s[1]=='R' and s[2]=='S':
    print('2')
elif s[0]=='S' and s[1]=='R' and s[2]=='R':
    print('2')
elif s[0]=='S' and s[1]=='S' and s[2]=='S':
    print('0')  
else :
    print('1')

Measured memory_bytes: 9068
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<climits>
#include<set>
#include<utility>
using namespace std;
typedef long long int ll;

int main(){
	vector<string> t;
	string s;
	int k;
	cin >> s >> k;
	for(int i=0; i<s.size(); i++){
		for(int j=1; j<=5; j++){
			t.push_back(s.substr(i, j));
		}
	}
	sort(t.begin(), t.end());
	unique(t.begin(), t.end());
	cout << t[k-1] << endl;

	return 0;
}


Measured memory_bytes: 1660
#include <stdio.h>
 
int main(void){
	int A,B,T,i=1,num=0;
  
  	scanf("%d %d %d",&A,&B,&T);
  	
  	while((double)(i*A) <= (double)T+0.5){
    	num += B;
      	i++;
    }
  	printf("%d\n",num);
  	return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
	long long max= 1000000001;
	int N,fre=0;
	long long Sum=0,Min=max,tmp;
	
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> tmp;
		if(tmp<0){
			tmp=0-tmp;
			fre++;
		}
		Sum += tmp;
		if(tmp<Min) Min=tmp;
	}
	if(fre%2==1) Sum-=Min*2;

		cout << Sum;
	return 0;
}

Measured memory_bytes: 256
def odd_number_has_eigith_divisors(odd_number):
    divisor_number = 0
    for n in range(1, odd_number+1):
        divisor = 0
        if n % 2 == 0:
            pass
        else:
            for i in range(1, n+1):
                if n % i == 0:
                    divisor += 1
            if divisor == 8:
                divisor_number += 1

    return divisor_number


if __name__ == '__main__':
    input_num = int(input())
    print(odd_number_has_eigith_divisors(input_num))

Measured memory_bytes: 3060
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<iostream>
#define llong long long
using namespace std;

inline int read()
{
    int x=0; bool f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
    if(f) return x;
    return -x;
}

const int N = 2e5;
struct Element
{
    int u,v,typ;
} a[N+3];
int uf[N+3];
int n,q,c; llong m;

int findfa(int u) {return uf[u]==u?u:uf[u]=findfa(uf[u]);}

int main()
{
    scanf("%d%lld%d",&n,&m,&q);
    for(int i=1; i<=n; i++) uf[i] = i;
    for(int i=1; i<=q; i++)
    {
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].typ); a[i].u++; a[i].v++;
        if(a[i].typ==0)
        {
            int uu = findfa(a[i].u),vv = findfa(a[i].v);
            if(uu!=vv) {uf[uu] = vv;}
        }
    }
    int cnt1 = 0; c = 0;
    for(int i=1; i<=n; i++) {if(i==findfa(i)) c++;}
    for(int i=1; i<=q; i++)
    {
        if(a[i].typ==1)
        {
            cnt1++;
            int uu = findfa(a[i].u),vv = findfa(a[i].v);
            if(uu==vv) {puts("No"); return 0;}
        }
    }
    llong l = cnt1?max(3ll,(llong)c):c-1ll,r = 1ll*c*(c-1ll)/2ll;
    if(m-(n-c)>=l && m-(n-c)<=r) {puts("Yes");}
    else {puts("No");}
    return 0;
}

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

#define ll long long
#define rep(i,N) for(ll i=0; i<N; i++)
const int mx = 2e5;

int main(void){
  string S;
  ll K;
  
  cin >> K;
  cin >> S;
  
  if(S.length()<=K){
    cout << S;
  }else{
    cout << S.substr(0,K) << "...";
  }

  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std; 
#define MAXN 9999
int N,M;
vector<int> islands[200005];
bool ans=false;
bool used[200005];
void dfs(int start,int shiptimes)
{
  //cout << "NOW" << start << ' ' << "ship" << shiptimes << endl;
  used[start]=true;
  if(start==N && shiptimes<=2)
    {
      ans=true;
      return;
    }
  else if(start!=N && shiptimes>=2)
    {
      return;
    }
  for(int i=0;i<islands[start].size();i++)
    {
      if(used[islands[start][i]]) continue;
      dfs(islands[start][i],shiptimes+1);
    }
  return;
}


int main(int argc,char const* argv[])
{
  cin >> N >> M;
  memset(used,false,sizeof(used));
  for(int i=0;i<M;i++)
    {
      int a,b;
      cin >> a >> b;
      islands[a].push_back(b);
      islands[b].push_back(a);
    }
  dfs(1,0);
  if(!ans)
    {
      cout << "IMPOSSIBLE" << endl;
    }
  else
    {
      cout << "POSSIBLE" << endl;
    }
  return 0;
}


Measured memory_bytes: 12144
#!/usr/bin/env python
# coding:utf-8
import os, sys
import math
from collections import defaultdict
w = raw_input()
m = defaultdict(int)

for i in range(len(w)):
    m[w[i]]+=1
b = True
for k,v in m.iteritems():
    b &= (v%2==0)
print "Yes" if b else "No"





Measured memory_bytes: 2812
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int readin()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll qmod(ll a,ll b,ll mod)
{
	ll r=1;
	while(b)
	{
		if(b&1)
		r=r*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return r;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(a==0&&b==0)
	return -1;
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
ll niyuan(ll a,ll n)
{
	ll x,y;
	ll d=exgcd(a,n,x,y);
	if(d==1)
	return (x%n+n)%n;
	return -1;
}
const int N=1e5+5;
struct ashon37w
{
    int k1,k2,de;
}c[N];
int co1[N],co2[N];
int main()
{
    int i,j;
    int a=readin(),b=readin(),m=readin();
    int mi1=1e9,mi2=1e9;
    for(i=1;i<=a;i++)
    {
        co1[i]=readin();
        mi1=min(mi1,co1[i]);
    }
    for(i=1;i<=b;i++)
    {
        co2[i]=readin();
        mi2=min(mi2,co2[i]);
    }
    for(i=1;i<=m;i++)
    {
        c[i].k1=readin(),c[i].k2=readin(),c[i].de=readin();
    }
    int q=1e9;
    for(i=1;i<=m;i++)
    {
        q=min(q,co1[c[i].k1]+co2[c[i].k2]-c[i].de);
    }
    q=min(q,mi1+mi2);
    cout<<q<<endl;


}


Measured memory_bytes: 2176
K, A, B = map(int,input().split())
if B - A <=2:
    print(1 + K)
    exit()
if K < A:
    print(1 + K)
    exit()
bis_num = A
K = K - A + 1
if K % 2 == 1:
    K  = K - 1
    bis_num += 1
x = K // 2
_bis_num = x * (B - A)
bis_num += _bis_num
print(bis_num)

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

#define REP(i,n) for(int i = 0; i < n; i++)
#define ll long long
#define PI M_PI

using namespace std;

int main(void){
    int N, D; cin >> N >> D;

    if(N % (2 * D + 1) != 0) cout << N / (2 * D + 1) + 1 << endl;
    else cout << N / (2 * D + 1) << endl;
    
    return 0;
}

Measured memory_bytes: 256
def is_prime(num):
	if num <= 1: return False
	if num == 2: return True
	if num % 2 == 0: return False
	i = 3
	while i <= num**0.5:
		if num % i == 0: return False
		i += 2
	return True
	
n = int(input())
cnt = 0
for i in range(n):
	if is_prime(int(input())):
		cnt += 1
print(cnt)



Measured memory_bytes: 5676
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
static long n = long.Parse(Console.ReadLine());
static long[,] nextMatrix = new long[n,n];//隣接行列
static long[] startTime = new long[n];//頂点に初めて着いた時刻
static long[] goalTime = new long[n];//頂点を調べ終わった時刻
static long[] colors = new long[n];//隣接頂点を調べ終わったら2
static long timeMemo = 0;
static long[] nextVertexes = new long[n];

	static void Main()
	{
    for(long i = 0; i < n; i++)
    {
		  long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
      for(long j = 0; j < nums[1]; j++)
      {
        nextMatrix[i,nums[j+2]-1] = 1;//隣接行列の作成
      }
    }
    DFS();
	}

  static void DFS()//深さ優先探索、O(V^2)
  {
    for(long i = 0; i < n; i++)
    {
      colors[i] = 0;//初期化
      nextVertexes[i] = 0;
    }
    timeMemo = 0;

    for(long i = 0; i < n; i++)
    {
      if(colors[i] == 0) DFSvisit(i);
    }

    for(long i = 0; i < n; i++)
    {
      Console.WriteLine((i+1) + " " + startTime[i] + " " + goalTime[i]);
    }
  }

  static void DFSvisit(long startVertex)//開始頂点から
  {
    for(long i = 0; i < n; i++)
    {
      nextVertexes[i] = 0;
    }

    var stack = new Stack<long>();//スタック
    stack.Push(startVertex);
    colors[startVertex] = 1;
    timeMemo++;
    startTime[startVertex] = timeMemo;

    while(stack.Count > 0)
    {
      long topMemo = stack.Peek();
      long v = NextVertex(topMemo);
      if(v != -1)
      {
        if(colors[v] == 0)
        {
          colors[v] = 1;
          timeMemo++;
          startTime[v] = timeMemo;
          stack.Push(v);
        }
      }else
      {
        stack.Pop();
        colors[topMemo] = 2;
        timeMemo++;
        goalTime[topMemo] = timeMemo;
      }
    }
  }

  static long NextVertex(long vertexMemo)
  {
    for(long i = nextVertexes[vertexMemo]; i < n; i++)
    {
      nextVertexes[vertexMemo] = i+1;
      if(nextMatrix[vertexMemo, i] == 1) return i;
    }
    return -1;
  }
  
}


Measured memory_bytes: 18340
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main() {
    ll n, a, b;
    cin>>n>>a>>b;
    if (n == 1){
        if(a== b) cout<<1<<endl;
        else cout<<0<<endl;
    } else {
        if (a > b){
            cout<<0<<endl;
        } else cout<<(b-a)* (n-2) + 1<<endl;
    }
}


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

using namespace std;
typedef long long ll;

const int N=1e6+5,P=1e9+7;
int n,f[N];ll sum,ans;

int main(){
	scanf("%d",&n);
	f[0]=f[1]=1;sum=2;
	for(int i=2;i<=n;i++)f[i]=(sum-f[i-2])%P,sum+=f[i];
	for(int i=0;i<n-1;i++)ans+=((ll)n*n-2*n+i+2)%P*f[i]%P;
	ans+=(ll)f[n-1]*(n-1)+f[n];
	printf("%d\n",ans%P);
	return 0;
}

Measured memory_bytes: 4096
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

#UnionFindのクラス
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n,m = map(int,ipt().split())
    bl = [tuple(map(int,ipt().split())) for i in range(m)]
    uf = UnionFind(n+1)
    num = n*(n-1)//2
    ans = [str(num)]
    for ai,bi in bl[::-1]:
        if uf.same(ai,bi):
            ans.append(str(num))
        else:
            num -= uf.size(ai)*uf.size(bi)
            ans.append(str(num))
            uf.union(ai,bi)
    for i in range(m):
        print(ans[m-i-1])

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 100504
fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val a = readLine()!!.split(" ").map(String::toLong)

  var x2 = 0L
  (0 until n).forEach { i -> x2 += if (i%2 == 0) a[i] else -a[i] }

  var ans = mutableListOf<Long>()
  ans.add(x2 / 2)
  (0 until n - 1).forEach { i -> ans.add(a[i] - ans[i]) }
  (0 until n).forEach { i -> ans[i] = ans[i] * 2 }
  println(ans.joinToString(" "))
}

Measured memory_bytes: 66696
#include<bits/stdc++.h>
using namespace std;
#define int long long

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

int lcm(int a,int b){ // lcm = a*b / gcd
  return a / gcd(a,b) * b; // a*bにおいてgcdだけ重複掛けしてる
}

signed main(){

  int n; cin >> n;
  int ans = 1;
  for(int i = 0; i < n; i++){
    int t; cin >> t;
    ans = lcm(ans,t);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <array>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <numeric>
#include <cassert>
#include <functional>
using namespace std;

typedef unsigned long long int llui;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
constexpr double pi = 3.141592653589793238462643383279502884L;

// TODO: Mod class

const int sz = 1e5;

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;

  auto dist = [](pii a, pii b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
  };

  pii cur;
  cur.first = cur.second = 0;
  int last_t = 0;

  bool can = true;
  for (int t = 0; t < n; ++t) {
    int tt;
    pii xy;
    cin >> tt >> xy.first >> xy.second;
    int dd = dist(cur, xy); 
    int ct = tt - last_t;
    if (ct < dd || (dd - ct) % 2 != 0) {
      can = false;
    }
    cur = xy;
    last_t = tt;
  }

  if (can) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
a, b = map(int, input().split())
cnt = 1
l = [1]
m = []

for i in range(2, 1000):
    cnt += i
    l.append(cnt)

for j in range(len(l) - 1):
    d = l[j + 1] - l [j]
    m.append(d)
n = m.index(b - a)
print(l[n] - a)
  

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

int main() {
  int a,b;
  cin >>a >>b;
  if ( (a+b)%2==1 ){
    cout << (a+b)/2+1 << endl;
  }
    else {
      cout << (a+b)/2 << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define f(i,a,n) for(ll i=a;i<n;i++)
const ll mod=1000000007;
using namespace std;
typedef pair<ll, ll> pa;

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    ll a[n + 1], b[n + 1], c[n + 1];
    f (i, 1, n + 1) cin >> a[i];
    f (i, 1, n + 1) cin >> b[i];
    f (i, 1, n) cin >> c[i];
    ll ans = 0;
    f (i, 1, n+1) {
        ans += b[a[i]];
        if (i != n and a[i + 1] - a[i] == 1) ans += c[a[i]];
    }
    cout << ans;
    return 0;
}

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

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

    string s;
    cin >> s;
    int loop;
    cin >> loop;

    int is_reverse = false;
    string head = "";
    string tail = "";

    // O(n)
    while (loop--) {
        int t;
        cin >> t;

        // reverse
        if (t == 1) {
            is_reverse = !is_reverse;
        } else {
            // adding
            int f;
            cin >> f;
            string c;
            cin >> c;

            if (is_reverse) {
                f = 3 - f;
            }

            if (f == 1)
                head = c + head;
            else
                tail += c;
        }
    }

    string ans = head + s + tail;
    if (is_reverse) {
        reverse(ans.begin(), ans.end());
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1416
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    if (N == K) {
        cout << 1 << endl;
        return 0;
    } else cout << (N - K + K - 1 - 1)/(K - 1) + 1 << endl;
    return 0;
}

Measured memory_bytes: 640
//Himanshu Shukla
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define file_input
//#define multitest
//#define measure_time
#define ll long long
#define v32 vector<int>
#define v64 vector<ll>
#define s32 set<int>
#define s64 set<ll>
#define graph vector<v32>
#define p32 pair<int, int>
#define p64 pair<ll, ll>
#define sz(v) (ll)(v).size()
#define fi first
#define se second
#define ln '\n'
#define debug(x) cerr << (#x) << ": " << (x) << ln
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll add(ll a, ll b, ll m) { return (((a % m + b % m) % m + m) % m); }
inline ll mul(ll a, ll b, ll m) { return (((a % m * b % m) % m + m) % m); }
const double EPS = 1e-6;
const ll MOD = 1e9 + 7;
template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
	out << '[' << p.fi << ", " << p.se << ']';
	return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print_container(const ContainerType<ValueType, Args...> &c)
{
	cout << "{ ";
	for (const auto &v : c)
		cout << v << ' ';
	cout << '}' << ln;
}

void solve()
{
	int n;
	cin >> n;
	vector<pair<int, string>> work;
	map<string, int> M;
	string temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		M[temp]++;
	}
	for (auto itr : M)
		work.push_back({itr.se, itr.fi});
	sort(work.rbegin(), work.rend());
	vector<string> ans;
	for (int i = 0; i < sz(work); i++)
	{
		int j = i + 1;
		ans.push_back(work[i].se);
		while (j < n && work[j].fi == work[i].fi)
		{
			ans.push_back(work[j].se);
			j++;
		}
		break;
	}
	sort(ans.begin(), ans.end());
	for (auto itr : ans)
		cout << itr << ln;
	return;
}

int main()
{
	FASTIO;
#ifdef file_input
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	clock_t start, stop;
	int t = 1;
#ifdef multitest
	cin >> t;
#endif
#ifdef measure_time
	start = clock();
#endif
	for (int tc = 1; tc < t + 1; tc++)
		solve();
#ifdef measure_time
	stop = clock();
	cerr << "Time :" << fixed << setprecision(5) << double(stop - start) / double(CLOCKS_PER_SEC) << "s" << ln;
#endif
	return 0;
}


Measured memory_bytes: 30572
n, k = map(int, input().split())
d = set(list(map(str, input().split())))
for i in range(n, 10**6):
    w = True
    idx = 0
    i = str(i)
    while idx < len(str(i)):
        if i[idx] in d:
            w = False
            break
        idx += 1
    if w:
        print(i)
        exit()

Measured memory_bytes: 3060
n = int(input())

if n < 10**1:
  print(n)
elif n < 10**2:
  print(9)
elif n < 10**3:
  print(9 + n - 10**2 + 1)
elif n < 10**4:
  print(909)
elif n < 10**5:
  print(909 + n - 10 **4 + 1)
else:
  print(90909)


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

using namespace std;

int main() {
  string S;cin>>S;
  char c1,c2;
  int cc1, cc2;
  bool yes = true;
  c1 = c2 = S[0];
  cc1 = 1;
  cc2 = 0;
  for (int i = 1; i < 4; i++) {
    if (S[i] != c1) {
      if (c2 == c1) {
        c2 = S[i];
        cc2++;
      } else {
        if (S[i] != c2) {
          yes = false;
        } else {
          cc2++;
        }
      }
    } else {
      cc1++;
    }
  }

  if (cc1 != 2 || cc2 != 2) yes = false;

  if (yes) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
t_tairyoku, t_kougeki, a_tairyoku, a_kougeki = map(int, input().split())

winner=""
while True:
    a_tairyoku = a_tairyoku-t_kougeki
    if a_tairyoku <= 0:
        winner="takahashi"
        break
    t_tairyoku = t_tairyoku-a_kougeki
    if t_tairyoku <= 0:
        winner ="aoki"
        break

if winner == "takahashi":
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9176
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


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

  vector<long> data;
  for(int i=0; i<N; i++)
  {
    int x;
    cin >> x;

    data.push_back(x);
  }

  long sum = abs(data[0]);
  int mindata = abs(data[0]);

  int negcnt;
  if(data[0] < 0) negcnt = 1;
  else negcnt = 0;

  int zeroFlag = 0;
  for(int i=1; i<N; i++)
  {
    long Ai = data[i];
    sum += abs(Ai);

    if(Ai<0) negcnt++;
    if(Ai == 0) zeroFlag = 1;

    if(mindata > abs(Ai)) mindata = abs(Ai);
  }

  if( (negcnt % 2 == 0) || zeroFlag ) cout << sum;
  else cout << sum - 2*(int)mindata;

  return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> v(n);
  for(int i=0; i<n; i++) cin >> v.at(i);
  int sum1=0,sum2=0;
  int ans=100000;
  for(int t=0; t<n-1; t++){
    for (int i=0; i < t+1; i++) sum1+=v.at(i);
    for (int k=t+1; k < n;k++) sum2+=v.at(k);
    int temp=abs(sum1-sum2);
    if (temp < ans) ans=temp;
    sum1=0;
    sum2=0;
  }
  cout << ans << 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() {
    string s;
    cin>>s;
    int ans=0;
    rep(i,s.length()/2){
        if(s[i]!=s[s.length()-i-1]) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3640
x = [[0]*3 for _ in range(3)]
a = [[0]*3 for _ in range(3)]

for i in range(3):
    a[i][0],a[i][1],a[i][2] = list(map(int,input().split()))
N = int(input())
b = [0] * N
for i in range(N):
    b[i] = int(input())
    for j in range(3):
        for k in range(3):
            if b[i] == a[j][k]:
                x[j][k] += 1

for i in range(3):
    if x[1][i]==x[2][i]==x[0][i]==1 \
    or x[i][1]==x[i][2]==x[i][0]==1 \
    or x[1][1]==x[2][2]==x[0][0]==1 \
    or x[0][2]==x[1][1]==x[2][0]==1:
        print('Yes')
        exit()

print('No')


Measured memory_bytes: 3064
N, K, S = map(int, input().split())

ans = [0]*N
T = 10**9
if T == S:
    T = 10**9 - 1
for i in range(N):
    if i < K:
        ans[i] = S
    else:
        ans[i] = T
print(" ".join(map(str, ans)))


Measured memory_bytes: 12068
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,Q;
  string S;
  vector<int> l;
  vector<int> r;
  vector<int> ac_pos;//i番目までのACの数
  vector<int> ans;
  cin >> N >> Q;
  cin >> S;
  for(int i = 0;i < Q;i++){
    int a,b;
    cin >> a >> b;
    l.push_back(a);
    r.push_back(b);
  }
  
  int tmp=0;
  ac_pos.push_back(0);
  for(int i=1;i <N ;i++){
    if(S[i-1]=='A'){
      if(S[i]=='C'){
        tmp++;
      }
    }
    ac_pos.push_back(tmp);
  }
  
   for(int i = 0;i < Q;i++){
     if(l[i] != 1){
       //cout << "" << r[i]<< " " << l[i]<< endl;
       //cout << "r_" << ac_pos[r[i]-1] << " l_" << ac_pos[l[i]-1] << endl;
       cout << ac_pos[r[i]-1] - ac_pos[l[i]-1] << endl;
     }else{
       //cout << "r_" << ac_pos[r[i]-1] << endl;
       cout << ac_pos[r[i]-1] << endl;
     }
   }
  
  /*
  for(int i = 0;i < Q;i++){
    int j = l[i] - 1;
    int tmp = 0;
    while(j < r[i] - 1){
      if(S[j]=='A'&& S[j+1]=='C'){
        tmp++;
      }
      j++;
    }
    ans.push_back(tmp);
  }
  
  for(int i=0;i<ans.size();i++){
    cout << ans[i] << endl;
  }
  */
  return 0;
}


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

char S[205];
int cnt[26];

int main(){

	scanf("%s",S);

	int len=strlen(S);

	int i;

	for(i=1;i<=2;i++){
		S[len-i]='\0';
	}
	len-=2;

	while(1){

		int flag=0;

		for(i=0;i<len/2;i++){
			if(S[i]!=S[i+(len/2)]){
				flag=1;
			}
		}
		if(flag==1){
			for(i=1;i<=2;i++){
				S[len-i]='\0';
			}
			len-=2;
		}
		else{break;}
	}

	printf("%d\n",len);

	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int a = in.nextInt();
    int b = in.nextInt();
    int c = in.nextInt();
    if (a < b && b < c) {
      System.out.println("Yes");
    }
    else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 26200
n = int(input()) #1行目のNを取得する
list = [input() for i in range(n)] #複数行の数値の入力を取得
lint = [int(s) for s in list]

ans = max(lint)
index = lint.index(max(lint))
lint.remove(max(lint))
ans2 = max(lint)

if ans == ans2:
    for i in range(n):
        print(ans)
else:
    for i in range(0, index):
        print(ans)
    print(ans2)
    for i in range(index+1, n):
        print(ans)

Measured memory_bytes: 25332