akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        //入力
        var arr = arrInt();
        var n = arr[0];
        var k = arr[1];
        arr = arrInt();
        string t = crS();

        //定義
        var win = new char[n];
        int sum = 0;

        for(int i = 0; i < n; i++)
        {
            var a = t[i];
            var hen = henkan(a);
            if(i-k >= 0)
            {
                if (win[i - k] == hen)
                {
                    if(i + k < n)
                    {
                        if (henkan(t[i + k]) != a) win[i] = a;
                        else win[i] = Other(a, hen);
                    }
                    continue;
                }
            }
            win[i] = hen;
            sum += point(hen, arr);
        }
        Console.WriteLine(sum);
    }

    static char henkan(char a)
    {
        if (a == 'r') return 'p';
        if (a == 's') return 'r';
        if (a == 'p') return 's';
        return 'e';
    }

    static char Other(char a, char b)
    {
        char[] arr = { 'r', 's', 'p' };
        foreach (var ele in arr) if (a != ele && b != ele) return ele;
        return 'e';
    }

    static int point(char a , int[] arr)
    {
        if (a == 'r') return arr[0];
        if (a == 's') return arr[1];
        if (a == 'p') return arr[2];
        return 0;
    }
    

    //入力受け取り用
    static string crS() { return Console.ReadLine(); }
    static int crI() { return int.Parse(Console.ReadLine()); }
    static int[] arrInt(){return Console.ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();}
    static long[] arrLong(){ return Console.ReadLine().Split(' ').Select(v => long.Parse(v)).ToArray(); }
    static string[] arrStr(){return Console.ReadLine().Split(' ').ToArray();}

}

Measured memory_bytes: 28944
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
 
 
 
 
using namespace std;
typedef long long ll;
 
ll solve1(ll,ll,int);
ll solve2(ll,ll,int);
ll solve3(ll,int);
int main(){
	ll a,b;
//	freopen("aorb.in","r",stdin);
//	freopen("aorb.out","w",stdout);
	scanf("%lld%lld",&a,&b);
	printf("%lld\n",solve1(a,b,60));
	return 0;
}
ll solve1(ll a,ll b,int d){
	if (d == 0) return a == b ? 1 : 2;
	
	ll x = 1,c = a^b;x <<= d;
	if (c&x) {
		x--;
		return solve2(a&x,b&x,d-1)+x-a+1;
	}
	else {x--;return solve1(a&x,b&x,d-1);}
}
ll solve2(ll a,ll b,int d){
	if (d == 0) return 2;
	ll x = 1;x <<= d;
	if (b&x) return x*2;
	if (a&x) return x*2-a+solve3(b,d-1);
	return x+solve2(a&(x-1),b&(x-1),d-1);
}
ll solve3(ll a,int d){
	if (d == 0) return a+1;
	ll x = 1;x <<= d;
	if (a&x) return x*2;
	return solve3(a,d-1);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    int main()
    {
    	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      	ll n;
      	cin >> n;
      	cout << (n * (n - 1)) / 2 << "\n";
      	return 0;
    }

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

using namespace std;
#define INP "solve"
#define OUT "solve"
const int QQ = 3e5 + 10;
const int maxN = 3e5 + 10;
const int maxM = 3e5 + 10;
const int oo = 1e9;
const int module = 1e9 + 7;

void doc() {
    freopen(INP ".inp","r",stdin);
    freopen(OUT ".out","w",stdout);

}

void solve() {
    int n;
    cin >> n;
    int a[n + 1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    int F[n + 1];
    memset(F, 0, sizeof(F));
    vector <int> Res;
    for (int i = n; i >= 1; i--) {
        int vl = 0;
        for (int j = i + i; j <= n; j += i) vl += F[j];
        vl %= 2;
        if (vl != a[i]) {
            F[i] = 1;
            Res.push_back(i);
        }
    }
    reverse(Res.begin(), Res.end());
    cout << (int)Res.size() << '\n';
    for (int x : Res) cout << x << ' ';
}
int main(int argc,char *argv[]) {
    //srand(time(nullptr));
    ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
   // doc();
    solve();
}


Measured memory_bytes: 3192
n = int(input())
s = input()

res = 0
for i in range(1, n):
    cnt = 0
    sub_b, sub_a = set(s[:i]), set(s[i:])
    for j in sub_b:
        if j in sub_a:
            cnt += 1
    res = max(res, cnt)
    
print(res)

Measured memory_bytes: 39152
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

const int MX = 400005;
const int MM = 1000000007;

int D[MX];
ll sum[MX];
int N, A, B, K;

struct BIT{
	int t[MX];
	void update(int x, int v){
		while(x < MX) t[x] += v, x += x&-x;
	}
	int read(int x){
		int r = 0;
		while(x) r += t[x], x -= x&-x;
		return r;
	}
} tree;

int main()
{
	scanf("%d%d", &N, &K);
	vector<ll> X;
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
		D[i] -= K;
		sum[i] = sum[i-1] + D[i];
		X.push_back(sum[i]);
	}
	X.push_back(0);
	sort(X.begin(), X.end());

	ll ans = 0;
	for(int i = 0; i <= N; i++){
		int ad = lower_bound(X.begin(), X.end(), sum[i]) - X.begin() + 1;
		ans += tree.read(ad);
		tree.update(ad, 1);
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 7280
# 意外とめんどくさいけど， よく考えると，末尾だけはかんたんにきまる．末尾から順番に決定していけばいいのだ．
N = int(input())
AL = []
while N >0:
    N -= 1
    amari = N % 26 # 26番目の要素は25にする
    AL.append(amari)
    N = int(N // 26)

S = [chr(ord('a')+al) for al in AL]

print(''.join(S[::-1]))




Measured memory_bytes: 9044
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <numeric>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
#define int long long
#define vint vector<int>
#define pint pair<int,int>
#define pb(a) push_back(a)
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " = " << (x) << endl
#define yn(b) cout << ((b) ? "Yes" : "No") << endl
#define YN(b) cout << ((b) ? "YES" : "NO") << endl

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

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

	int A, B, C;
	cin >> A >> B >> C;
	cout << min(B / A, C) << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 100010
ll n,a[N];
ll f[N],g[N];
ll val[N],cs[N];
int main(){
    cin>>n;
    lol(i,n)cin>>a[i];
    f[0]=1;
    for(ll i=1;i<=n;i++)f[i]=f[i-1]*i%mod;
    g[n+1]=1;
    for(ll i=n;i>=1;i--)g[i]=g[i+1]*i%mod;
    for(ll i=2;i<=n;i++){
	val[i]=f[i-1]*g[i+1]%mod;
    }
    val[1]=g[2];
    cs[0]=cs[1]=0;
    for(ll i=2;i<=n;i++)cs[i]=(cs[i-1]+val[i])%mod;
    ll ans=0;
    lol(i,n){
	ll cur=cs[i+1]+cs[n-i]+val[1];
	ans=(ans+cur*a[i])%mod;
    }
    return cout<<ans<<endl,0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
     
int main(void){
  string str;
  cin >> str;
  int temp = 0,max = 0;
  for(int i = 0; str[i] != '\0'; i++){
    if(str[i] == 'A' || str[i] == 'T' || str[i] == 'G' || str[i] == 'C')temp++;
    else temp = 0;
    if(temp > max)max = temp;
  }
  cout << max << endl;
	return 0;
}

Measured memory_bytes: 760
#include<bits/stdc++.h>
#define o 3005
using namespace std;
int a[o],b[o];
int n,K,Q,ans;
bool check(int l,int r)
{
	int x=1,y,num=0,zm=0;
	while(x<=n)
	{
		if(a[x]<l)
		{
			x++;
			continue;
		}
		y=x;
		while(y<n&&a[y+1]>=l) y++;
		zm=0;
		for(int k=x; k<=y; k++) if(a[k]<=r) zm++;
		num+=min(zm,max((y-x+1)-(K-1),0));
		x=y+1;
	}
	return num>=Q;
}
int main()
{
	scanf("%d%d%d",&n,&K,&Q);
	for(int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=a[i];

	sort(b+1,b+n+1);
	ans=b[Q]-b[1];
	int sz=1;
	for(int i=2; i<=n; i++) if(b[i]!=b[i-1]) b[++sz]=b[i];
	for(int i=1; i<=sz; i++)
	{
		int l=i,r=sz,mid,as=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(check(b[i],b[mid])) as=mid,r=mid-1;
			else l=mid+1;
		}
		if(as) ans=min(ans,b[as]-b[i]);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <list>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(d) string(1,d)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll ans;

pair<ll,ll> f(ll x, ll y){
	ll a = min(x,y);
	ll b = max(x,y);
	ans += 3*a*(b/a);
	return mp(a,b%a);
}

int main() {
	ll n,x;
	cin>>n>>x;
	ll k = min(x,n-x);
	ans = 0;
	ll a = k;
	ll b = n-k;
	while(1){
		pair<ll,ll> ret = f(a,b);
		if(ret.fi==0||ret.se == 0)break;
		a = ret.fi;
		b = ret.se;
	}
	cout << ans << endl;
	return 0;
}

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

const int N = 100;

int n, w;
int wt[N + 1], vl[N + 1];
map<pair<int, long long>, long long> mem;

long long solve(int i, long long curw) {
  if (i == n) {
    return 0;
  }
  
  if (mem[{i, curw}]) {
    return mem[{i, curw}];
  }
  
  long long x = 0, y = 0;
  if (curw + wt[i] <= w) {
    x = solve(i + 1, curw + wt[i]) + vl[i];
  }
  y = solve(i + 1, curw);
  
  return mem[{i, curw}] = max(x, y);
}

int main() {
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    cin >> wt[i] >> vl[i];
  }
  cout << solve(0, 0) << endl;
  return 0;
}


Measured memory_bytes: 9700
#include<stdio.h>
int main()
{
	int n,have_num, have[4][13] = { 0 }, a, b;
	char mark;
	scanf("%d", &n);
	for (a=0;a<n;a++)
	{
		scanf(" %c %d", &mark, &have_num);
		switch (mark)
		{
		case 'S': have[0][have_num - 1] = 1; break;
		case 'H': have[1][have_num - 1] = 1; break;
		case 'C': have[2][have_num - 1] = 1; break;
		case 'D': have[3][have_num - 1] = 1; break;
		}
	}
		for (a=0;a<4;a++)
		{
			for (b = 0; b < 13; b++)
			{
				if (have[a][b] == 0)
				{
					     if (a == 0) mark = 'S';
					else if (a == 1) mark = 'H';
					else if (a == 2) mark = 'C';
					else if (a == 3) mark = 'D';
					printf("%c %d\n",mark,b+1);
				}
			}
		}

	return 0;
}

Measured memory_bytes: 596
import java.util.*;
   
class Main{
   public static void main(String[] args){
     Scanner stdId = new Scanner(System.in);
     int a = stdId.nextInt(); 
         int b = stdId.nextInt();
         int c = stdId.nextInt();
     int[] num = {a,b,c};
     Arrays.sort(num);
     System.out.println("" + num[0] + " " + num[1] + " " + num[2]);
  }
}

Measured memory_bytes: 26152
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <cctype>
#include <iostream>
using namespace std;

typedef long long LL;
typedef stringstream strstm;
#define PI acos(-1.0)
#define E 2.718281829459
#define pb push_back
#define lowbit(x) (x & (-x))
#define DBG(x) cout << (x) << " ";
#define MST(a,b) memset(a,b,sizeof(a));
#define _for(i,a,b) for(int i = (a); i < (b); ++i)
#define _rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define _ech(x,z) for(auto x = z.begin(); x != z.end(); ++x)

struct FastIO {
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint() {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline LL xlongint() {
        LL s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s) {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c> 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x) {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s) {
        while (*s) wchar(*s++);
    }
    ~FastIO() {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;


const int maxn = 100005;
int n,v,ans,a[maxn],b[maxn];

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >>v;
    for (int i = 1;i <= n; i++) cin >> a[i] >> b[i];
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for (int i = n;i >= 1 && b[i] > a[n] && v > 0; v -= b[i],i--,ans++);
    if(v>0) ans = ans + v/a[n] + (v%a[n] != 0);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

int const MAXN=110000;
int N;
int S[MAXN];

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N;
	rep(i,0,N) cin>>S[i];
	
	ll res=0;
	for (int d=1; d*d<=N; ++d) {
		vector<vector<ll>> sums(d);
		rep(i,0,N) {
			ll v=S[i];
			if (!sums[i%d].empty()) v+=sums[i%d].back();
			sums[i%d].push_back(v);
		}
		
		rep(A,1,N-1) if ((N-1-A)%d==0) {
			int k=(N-1-A)/d;		
			if (A<=d || (A%d==0 && k>=A/d)) continue;
			ll sum=sums[0][k];
			sum+=sums[A%d][A/d+k];
			if (A/d>0) sum-=sums[A%d][A/d-1];
			res=max(res,sum);
		}
	}
		
	cout<<res<<"\n";
}


Measured memory_bytes: 2400
#include<stdio.h>
#include<string>
#include<string.h>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>
#include <cmath>
#include <limits>
#include <numeric>
#include <cmath>
#include <limits>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main(){
    int n;
    ll a[200005]={};
    ll b[200005]={};
    ll aa[200005]={};
    ll bb[200005]={};
    scanf("%d",&n);
    REP(i,n)scanf("%lld",&a[i]);
    REP(i,n)scanf("%lld",&b[i]);
    REP(i,n){
        aa[i]=a[i];
        bb[i]=b[i];
    }
    sort(a,a+n,std::greater<ll>());
    sort(b,b+n,std::greater<ll>());
    int flag=0;
    REP(i,n){
        if(a[i]>b[i]){
            printf("No\n");
            return 0;
        }
        else{
            if(a[i]<=b[i+1]){
                flag=1;
            }
        }
    }
    if(flag==1){
        printf("Yes\n");
        return 0;
    }
    std::map<ll,ll> ma;
    REP(i,n)ma[a[i]]=i;
    ll aaa[200005]={};
    REP(i,n)aaa[i]=ma[aa[i]];
    
    std::map<ll,ll> mb;
    REP(i,n)mb[b[i]]=i;
    ll bbb[200005]={};
    REP(i,n)bbb[i]=mb[bb[i]];
    
    std::map<ll,ll> maaa;
    REP(i,n)maaa[aaa[i]]=i;
    int now=bbb[0];
    REP(i,n){
        now = bbb[maaa[now]];
        if(i!=n-1 && now==bbb[0]){
            printf("Yes\n");
            return 0;
        }
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 28416
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    long x, y;
    cin >> x >> y;
    
    for(long i=1; true; i++){
        x *= 2;
        if(x > y){
            cout << i << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Your code here!
n,k=map(int,input().split())
ans=0
for i in range(k,n+2):
 ans+=(n*(n+1))//2-max(0,(k+1-i)*(k-i)//2)-i*(i-1)//2+1
 #print((n*(n+1))//2-max(0,(k+1-i)*(k-i+2)//2))
 ans%=10**9+7
 #print(ans)
print(ans)


Measured memory_bytes: 9184
#include<stdio.h>
 
int main(){
    int n,d,min,max;
    long long sum;
    scanf("%d %d",&n,&d);
    sum = min = max = d;
 
    for(int i=1;i<n;i++){
        scanf("%d",&d);
        if(d <= min)min = d;
        if(d >= max)max = d;
 
        sum += d;
    }
    printf("%d %d %lld\n",min, max,sum);
    return 0;
}


Measured memory_bytes: 2112
H, W, K = map(int, input().split(' '))
ls, rst = [], 0
for i in range(H):
    ls.append(input())
for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for s in range(H):
            if i >> s & 1:
                continue
            for t in range(W):
                if j >> t & 1:
                    continue
                if ls[s][t] == '#':
                    cnt += 1
        if cnt == K:
            rst += 1
print(rst)

Measured memory_bytes: 9208
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;
int main(){
	int N;
	cin >> N;

	if (888<N&&N <= 999) {
		cout << "999" << endl;
	}
	else if (777 < N&&N <= 888) {
		cout << "888" << endl;
	}
	else if (666 < N&&N <= 777) {
		cout << "777" << endl;
	}
	else if (555 < N&&N <= 666) {
		cout << "666" << endl;
	}
	else if (444 < N&&N <= 555) {
		cout << "555" << endl;
	}
	else if (333 < N&&N <= 444) {
		cout << "444" << endl;
	}
	else if (222 < N&&N <= 333) {
		cout << "333" << endl;
	}
	else if (111 < N&&N <= 222) {
		cout << "222" << endl;
	}
	else if (99 < N&&N <= 111) {
		cout << "111" << endl;
	}
 }



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
string a,b,c;
cin >> a >> b >>c;
if(a[a.size() - 1] != b[0] || b[b.size() - 1] != c[0]){
cout <<"NO"<<endl;
}
else{
cout << "YES" <<endl;
}
return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int a[4] , t;
	cin >> t;
	a[0] = t/1000;
	a[1] = t/100 - a[0] * 10;
	a[2] = t/10 - a[1] * 10 - a[0] * 100;
	a[3] = t - a[2] * 10 - a[1] * 100 - a[0] * 1000;
  	if(a[0] + a[1] + a[2] + a[3] == 7){
		cout << a[0] << "+" << a[1] << "+" << a[2] << "+" << a[3] << "=7";
		return 0;
	}
	if(a[0] - a[1] - a[2] - a[3] == 7){
		cout << a[0] << "-" << a[1] << "-" << a[2] << "-" << a[3] << "=7";
		return 0;
	}
	if(a[0] - a[1] + a[2] + a[3] == 7){
		cout << a[0] << "-" << a[1] << "+" << a[2] << "+" << a[3] << "=7";
		return 0;
	}
	if(a[0] - a[1] - a[2] + a[3] == 7){
		cout << a[0] << "-" << a[1] << "-" << a[2] << "+" << a[3] << "=7";
		return 0;
	}
	if(a[0] + a[1] - a[2] + a[3] == 7){
		cout << a[0] << "+" << a[1] << "-" << a[2] << "+" << a[3] << "=7";
		return 0;
	}
	if(a[0] + a[1] - a[2] - a[3] == 7){
		cout << a[0] << "+" << a[1] << "-" << a[2] << "-" << a[3] << "=7";
		return 0;
	}
	if(a[0] + a[1] + a[2] - a[3] == 7){
		cout << a[0] << "+" << a[1] << "+" << a[2] << "-" << a[3] << "=7";
		return 0;
	}
	if(a[0] - a[1] + a[2] - a[3] == 7){
		cout << a[0] << "-" << a[1] << "+" << a[2] << "-" << a[3] << "=7";
		return 0;
	}
	
	return 0;
}

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

int main() {
  while (1) {
      string str;
      cin >> str;
      if(str == "-"){
          return 0;
      }
      int m;
      cin >> m;
      for(int i = 0; i < m; i++){
          int h;
          cin >> h;
          string temp = "";
          for(int j = 0; j < h; j++){
              temp += str[j];
          }
          str.erase(str.begin(),str.begin()+h);
          str = str + temp;
      }
      cout << str << endl;
  }
  return 0;
}


Measured memory_bytes: 3160
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb(x) push_back(x)

typedef pair<ll,ll> pp;
int lcm(int a, int b)
{
    int lar = max(a, b);
    int small = min(a, b);
    for (int i = lar; ; i += lar) {
        if (i % small == 0)
            return i;
    }
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b) {
    return (a.second < b.second);
}

ll power(ll x, unsigned ll y, ll p)
{
    ll res = 1;     // Initialize result
  
    x = x % p; // Update x if it is more than or
                // equal to p
   
    if (x == 0) return 0; // In case x is divisible by p;
  
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
  
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

struct ArrayWrapper
{
    int a[101][101];
};

bool isPowerOfTwo (ll x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));
}


void solve(){
    ll a, b, n;
    cin >> a >> b >> n;
    ll x;
    if(b > n) x = n;
    else{
        x = (n/b)*b - 1;
    }
    cout << (a*x)/b - a*(x/b) << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //ll t; cin >> t; while(t--)
        solve();
}


Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n;
int ans;
int main()
{

  int i=1;
  cin>>n;
  a[0]=n;
  while(ans==0){
    if(a[i-1]%2==0){
      a[i]=a[i-1]/2;
    }else{
      a[i]=a[i-1]*3+1;
    }
    for(int j=0;j<i;j++){
      if(a[i]==a[j]){
	ans=i;
      }
    }
    i++;
  }
  cout<<ans+1<<endl;
  return 0;
}


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

int main(){
  ll K;
  cin >> K;
  ll g=0,h=0,ans=0;
  for(ll i=1;i<=K;++i){
    for(ll j=1;j<=K;++j){
      h = __gcd(i,j);
      if(h==1){
        ans += K;
        continue;
      }
      else{      
        for(ll k=1;k<=K;++k){
        g = __gcd(h,k);
        ans += g;
        }
      }
    }
  }
  cout << ans << endl;
}

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

using namespace std;

int main()
{
	int n,W;
	cin >> n >> W;
	long long int w[n+1],v[n+1];
	w[0] = 0;
	v[0] = 0;
	for(int i=1; i<=n; i++)
	{
		cin >> w[i] >> v[i];
	}

    long long int dp[W+1][n+1];

	for(int i=0;i<=n;i++)  dp[0][i] = 0;

	for(int i=0;i<=W;i++)  dp[i][0] = 0;

	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=W;j++)
		{
			dp[j][i] = dp[j][i-1];

			if(w[i] <= j)  dp[j][i] = max(dp[j][i-1], dp[j-w[i]][i-1] + v[i]);

		}
	}	

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

Measured memory_bytes: 79104
#include<bits/stdc++.h>
// #include <boost/math/common_factor.hpp> 
#pragma GCC optimize ("-O3")
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define int long long
#define double long double
#define pb push_back
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define diff(a,b) (a>b?a-b:b-a)
#define F first
#define S second
//#define tr(container, it) \
//for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
const int N=1e6+5;
int mod = 1e9+7;
void pairsort(int a[], int b[], int n){
    pair<int, int> pairt[n];
    for (int i = 0; i < n; i++) 
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }
    sort(pairt, pairt + n);
    for (int i = 0; i < n; i++) 
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}
ll pow1(ll n,ll p)
{
    if(p==0)    return 1;
    ll x=pow1(n, p/2);
    x=(x*x)%mod;
    if(p%2==0)
        return x;
    else
        return (x*n)%mod;
}
ll binarySearch(ll arr[], ll l, ll r,ll x) 
{ 
    if (r >= l) 
    { 
        ll mid = l + (r - l) / 2;  
        if (arr[mid] == x) 
        return mid; 
        if (arr[mid] > x) 
        return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    }
    return -1; 
}
bool compare(const pair<ll, ll>&p1, const pair<ll,ll>&p2)
{
    if(p1.F < p2.F) return true;
        if(p1.F == p2.F) return p1.S < p2.S;
        return false;
}
bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
}
int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}
int isPrime(int n){
    if(n < 2)
        return 0;
    if(n < 4)
        return 1;
    if(n % 2 == 0 or n % 3 == 0)
        return 0;
    for(int i = 5; i*i <= n; i += 6)
        if(n % i == 0 or n % (i+2) == 0)
            return 0;
    return 1;
}
long long C(int n, int r) {
    if(r>n-r) 
        r=n-r;
    long long ans=1;
    for(int i=1;i<=r;i++){
        ans*=n-r+i;
        ans/=i;
    }
    return ans;
}
int modexpo(int x,int p){
    int res = 1;
    x = x%mod;
    while(p){
        if(p%2)
            res = res * x;
        p >>= 1;
        x = x*x % mod;
        res %= mod;
    }
    return res;
}
int32_t main()
{
    IOS;

    int n,k ;

    cin >> n>>k;
    vector<int>a(n+1);

    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    vector<int>dp(n+1,INT_MAX);

    dp[0] = 0;
    dp[1] = 0;
    dp[2] = abs(a[2] - a[1]);
    // int total = dp[2];
    for(int i=3;i<=n;i++){
        for(int j=i-k;j<i;j++)
            if(j>=1)
            dp[i] = min(dp[j] + abs(a[i] - a[j]), dp[i]);
    }
    // for(int i = 1;i<=n;i++)cout<<dp[i]<<" ";
    //     cout<<endl;
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(){
    int a,b,c,d,v=0;
    scanf("%d %d %d %d", &a, &b, &c, &d);

    if((c>=a)&&(c<=b)){
        if(d<b)
            v=d-c;
        else
            v=b-c;
    }
    if((a>=c)&&(a<=d)){
        if(b<d)
            v=b-a;
        else
            v=d-a;
    }
    printf("%d\n",v);

    return 0;
}


Measured memory_bytes: 128
import java.io.File;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.*;
import java.util.Map.Entry;

public class Main{
	
	public static void main(String[] args) throws IOException{
		//File file = new File("input.txt");
		//Scanner in = new Scanner(file);
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for(int i = 0; i < N; i++){
			int a = in.nextInt();
			for(int j = -1; j <= 1; j++){
				Integer count = map.get(a+j);
				if(count == null) map.put(a+j, 1);
				else map.put(a+j, count+1);
			}
		}
		
		List<Entry<Integer, Integer>> listEntries = new ArrayList<Entry<Integer, Integer>>(map.entrySet());
        
        Collections.sort(listEntries, new Comparator<Entry<Integer, Integer>>() {
            public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });
        
        System.out.println(listEntries.get(0).getValue());
	}
}


Measured memory_bytes: 63396
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pb push_back
#define pob pop_back
#define mp make_pair
#define ff first
#define ss second
#define pi 3.14159265
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <ll, ll> pll;
const ll M=1e9+7;
ll inf=1e18;
int main()
{
    int n;
    cin>>n;
    int k=1000-(n%1000);
    if(k<1000)
        cout<<k;
    else
        cout<<0;
}


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

struct UnionFind {
    vector<int> data;
    int sz;
    UnionFind(int sz) : data(sz, -1), sz(sz) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) == (y = root(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y]; data[y] = x; sz--;
        return true;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    int size() { return sz; }
};

int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> es(m);
    for (auto &p: es) cin >> p.first >> p.second, p.first--, p.second--;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        UnionFind uf(n);
        for (int j = 0; j < m; j++) if (i != j) {
            uf.unionSet(es[j].first, es[j].second);
        }
        if (uf.size(0) != n) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
 int N;
 cin >>N;
 vector<int> D(N);
 
 for(int i=0; i<N; i++){
 cin >>D[i];
 } 
 
 sort(D.begin(), D.end());
 int count=0;
  
 for(int i=0; i<N; i++){
   if(D[i]<D[i+1]){
     count++;
   }
 }
  
  cout << count+1 <<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        int tmp = 0;
        for (int i = a; i <= b; i++) {
            if ((c%i) == 0) {
                tmp++;
            }
        }

        System.out.println(tmp);
    }

}


Measured memory_bytes: 26268
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include<iomanip>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int inf = 1000000;

int main(int argc, const char * argv[]) {
  ll N;
  long K;
  cin >> N >> K;
  vector<long> nums(N);
  vector<int> cnt(40);
  
  for(int i = 0; i < N; i++) {
    cin >> nums[i];
    for (int j = 39; j >= 0; j--) {
      if (nums[i] & (1L << j)) {
        cnt[j]++;
      }
    }
  }
  
  long X = 0;
  for (int j = 39; j >= 0; j--) {
    if ((X + (1L << j)) <= K) {
      if (cnt[j] < N - cnt[j]) {
        X += (1L << j);
      }
    }
  }
  
  long result = 0;
  for (int i = 0; i < N; i++) {
    result += X ^ nums[i];
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int a[200010],b[200010];
int main(){
	int n,m;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i);
	scanf("%d",&m);
	for(int i=0;i<m;i++)scanf("%d",b+i);
	a[n]=b[m]=2e9;
	for(int i=0,j=0;i<n;){
		if(a[i]<b[j])printf("%d\n",a[i++]);
		else if(a[i]>b[j])j++;
		else i++,j++;
	}
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {
	int N;
	cin >> N;
	vl A(N);
	rep(i, N)cin >> A[i];
	map<ll, ll> Ap, Am;
	rep(i, N) {
		Ap[A[i] + i + 1]++;
		Am[-A[i] + i + 1]++;
	}
	auto it = Ap.begin();
	ll ans = 0;
	while (it != Ap.end()) {
		ll a = it->first;
		ans += Am[a] * (it->second);
		it++;
	}

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

Measured memory_bytes: 39100
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp make_pair
#define INF (1<<28)

int N, B[64], C[64];
string A[64], D[64][64];
int g[64][64], cf[64], ct[64];
int dp[1<<20];

int solve() {
    const int n = N / 2, m = N - n;
    const int nn = 1<<n, mm = 1<<m;
    memset(cf, 0, sizeof(cf));
    memset(ct, 0, sizeof(ct));
    rep (i, n) rep (j, n) if (g[i][j]) cf[i] |= 1<<j;
    rep (i, m) rep (j, m) if (g[i+n][j+n]) cf[i+n] |= 1<<j;
    rep (i, m) rep (j, n) if (g[i+n][j]) ct[i] |= 1<<j;
    rep (i, nn) dp[i] = -INF;
    rep (b, nn) {
        if (b&1) {
            bool ok = true;
            rep (i, n) if (b&(1<<i) && b&cf[i]) { ok = false; break; }
            if (ok) {
                int s = 0;
                rep (i, n) if (b&(1<<i)) s += B[i];
                dp[b] = max(dp[b], s);
            }
        }
        rep (i, n) dp[b|(1<<i)] = max(dp[b|(1<<i)], dp[b]);
    }
    int ans = 0;
    rep (b, mm) {
        bool ok = true;
        rep (i, m) if (b&(1<<i) && b&cf[i+n]) { ok = false; break; }
        if (!ok) continue;
        int s = 0, z = 0;
        rep (i, m) if (b&(1<<i)) s += B[i+n], z |= ct[i];
        ans = max(ans, dp[nn-1-z] + s);
    }
    return ans;
}

int main() {
    for (;;) {
        cin >> N;
        if (N == 0) return 0;
        map<string, int> of;
        rep (i, N) {
            cin >> A[i] >> B[i] >> C[i];
            of[A[i]] = i;
            rep (j, C[i]) cin >> D[i][j];
        }
        memset(g, 0, sizeof(g));
        rep (i, N) rep (j, C[i]) g[i][of[D[i][j]]] = 1;
        printf("%d\n", solve());
    }
}

Measured memory_bytes: 5476
#include<iostream>
#include<utility>

using namespace std;

int partition(int A[],int p,int r);

int main(){

	int *A;
	int n;
	cin>>n;
	A = new int[n];

	for(int i=0;i<n;i++) cin>>A[i];

	int c = partition(A,0,n-1);
	
	for(int i=0;i<n;i++){
		if(i) cout<<" ";
		if(i==c){
			cout<<"["<<A[i]<<"]";
		}else{
			cout<<A[i];
		}
	}
	cout<<endl;

	delete [] A;

	cin.get();
	cin.get();

}

int partition(int A[],int p,int r){
	int x = A[r];
	int i = p-1;
	for(int j=p;j<r;j++){
		if(x>=A[j]){
			i++;
			swap(A[i],A[j]);
		}
	}
	swap(A[r],A[i+1]);
	return i+1;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int a,b,c;
  cin >> a >> b >> c;
  int ans = (c - (a - b));
  if (ans > 0)
    cout << ans << endl;
  else
    cout << "0" << endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i, j) for (int i = 0; i < j; i++)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int gcd(int x, int y);

const int INF = 1001001001;
const int mod = 1000000007;

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

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }


int main() {
    int n;
    cin >> n;
    mint ans = 1;
    for(int i = 1; i <= n; i++) {
        ans *= i;
    }
    cout << ans << endl;
    return 0;
}
/*���C�u�����ő����*/
//���[�O���b�h�̌ݏ��@
int gcd(int x, int y) {
    int num[3];
    num[0] = (x > y) ? x : y;
    num[1] = (x <= y) ? x : y;
    num[2] = num[0] % num[1];

    while (num[2]) {
        num[0] = num[1];
        num[1] = num[2];
        num[2] = num[0] % num[1];
    }

    return num[1];
}

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

int main(){
    double pai=3.141592653589,da,db;
    int a,b;
    scanf("%d %d",&a,&b);
    da=static_cast<double>(a);
    db=static_cast<double>(b);
    printf("%d %d %.8lf\n",a/b,a%b,da/db);
    return 0;
}



Measured memory_bytes: 3208
/*
 * kadai3_3
 * kamecha
 */
#include<stdio.h>

int main(void){
    int num, kurai;
    scanf("%d %d", &num, &kurai);
    /*
     * 何桁かを求めれば良いので何回割れるかを求めればOK
     */
    int ans = 0;
    while(num > 0){
        num /= kurai;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>

#define int long long
#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define showp(n) cerr<<n.fs<<", "<<n.sc<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", "}cerr<<endl

#define yes printf("YES\n")
#define no printf("NO\n")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using ull=unsigned long long;
using vi=vector<int>;
using pint=pair<int,int>;

const int INF=1LL<<55;

int n;
int x;
bool hasodd=false;
int k=0;

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

    cin>>n;

    rep(i,n){
        cin>>x;
        if(x&1) k++;
        else hasodd=true;
    }
    if(k&1){
        if(k==2&&hasodd) yes;
        else no;
    }else{    
        yes;
    }

    return 0;
}


Measured memory_bytes: 632
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;

int main(void){
  int n, ans, now;
  vector<PII> v;
  
  cin >> n;
  for (int i=0; i<n; i++){
    int s,t;
    cin >> s >> t;
    v.push_back(make_pair(t,s));
  }
  sort(v.begin(), v.end());
  ans = 0;
  now = -1;
  for (int i=0; i<n; i++){
    if (v[i].second > now){
      ans++;
      now = v[i].first;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3840
#include<iostream>

using namespace std;

int main(){
    string n;
    for(int i=0;i<4;i++){
        cin>>n[i];
    }
    int a,b,c,d;
    a=n[0]-'0';
    b=n[1]-'0';
    c=n[2]-'0';
    d=n[3]-'0';
    if(a+b+c+d==7)
        cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
    else if(a+b+c-d==7)
        cout<<a<<"+"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
    else if(a+b-c+d==7)
        cout<<a<<"+"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
    else if(a+b-c-d==7)
        cout<<a<<"+"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
    else if(a-b+c+d==7)
        cout<<a<<"-"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
    else if(a-b+c-d==7)
        cout<<a<<"-"<<b<<"+"<<c<<"-"<<d<<"=7"<<endl;
    else if(a-b-c+d==7)
        cout<<a<<"-"<<b<<"-"<<c<<"+"<<d<<"=7"<<endl;
    else if(a-b-c-d==7)
        cout<<a<<"-"<<b<<"-"<<c<<"-"<<d<<"=7"<<endl;
}


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

#define LL long long
set<LL> s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	LL n, m, x, g = 1;
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		cin >> x; x /= 2;
		if(s.find(x) == s.end()) {
			if(!i) g = x;
			g /= __gcd(x, g);
			g *= x;
		}
		s.insert(x);
	}

	for(auto x : s) {
		if((g / x) % 2 == 0) {
			cout << 0;
			return 0;
		}
	}

	g = m / g;
	g = (g+1) / 2;

	cout << g;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    ll ans = 0;
    ll mod = 1e9+7;
    for (int i = 0; i < 60; i++)
    {

        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if ((a[j]>>i) & 1) cnt++;
        }
        ans = (ans + (1ll<<i)%mod * cnt%mod * (n-cnt))%mod;
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 2560
import math
N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]

h.sort(reverse = True)

def det(m):
  C = [max(0, a-B*m) for a in h]
  #print(m, C)
  if sum([math.ceil(b/(A-B)) for b in C]) > m:
    return False
  else:
    return True
  
l = 0
r = math.ceil(max(h)/A*N)
#print(l, r)
while r - l > 1:
  c = (l + r) // 2
  if det(c):
    r = c
  else:
    l = c
    
print(r)
    
  
  


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

int main() 
{
    string s,t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    
    int dp[n+1][m+1];

    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0 || j==0) dp[i][j] = 0;
            else{
                if(s[i-1]==t[j-1]) dp[i][j] = 1+dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    
    int i=n, j=m;
    string ans="";
    
    while(i>0 && j>0) {
        if(s[i-1]==t[j-1]) {
            ans = s[i-1] + ans;
            i--;
            j--;
        } else{
            if(dp[i-1][j]>dp[i][j-1]) i--;
            else j--;
        }
    }
    
    cout<<ans<<endl;
    
	return 0;
}

Measured memory_bytes: 35456
def main(argv)
  n = gets.chomp.to_i
  s = gets.chomp
  
  t = 1
  c = s[0]
  
  (1...n).each do |i|
    if s[i] != c then
      t += 1
      c = s[i]
    end
  end
  
  puts t.to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

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

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

        int n = stdIn.nextInt();
        int[] p = new int[n];
        int[] q = new int[n];
        for(int i=0; i<n; i++){
            p[i] = stdIn.nextInt();
        }
        for(int i=0; i<n; i++){
            q[i] = stdIn.nextInt();
        }

        Permutation permP = new Permutation(p);
        Permutation permQ = new Permutation(q);

        int counterP = 0;
        while(true){
            counterP++;
            if(isSameArray(p, permP.getPerm())){
                break;
            }
            permP.next();
        }

        int counterQ = 0;
        while(true){
            counterQ++;
            if(isSameArray(q, permQ.getPerm())){
                break;
            }
            permQ.next();
        }

        System.out.println(Math.abs(counterP - counterQ));
    }

    static boolean isSameArray(int[] a, int[] b){
        for(int i=0; i<a.length; i++){
            if(a[i] != b[i]){
                return false;
            }
        }
        return true;
    }
}

class Permutation{
    int[] seed;
    int[] perm;

    public Permutation(int [] seed){
        this.seed = new int[seed.length];
        for(int i=0; i<this.seed.length; i++){
            this.seed[i] = seed[i];
        }

        this.perm = new int[seed.length];
        for(int i=0; i<this.perm.length; i++){
            this.perm[i] = seed[i];
        }
        sort(this.perm, 0, this.perm.length);
    }

    public int[] getPerm(){
        return this.perm;
    }

    public boolean next(){
        for(int i=perm.length-1; i>0; i--){
            if(perm[i] > perm[i-1]){
                changePerm(i);
                return true;
            }
        }

        return false;
    }

    private void changePerm(int index){
        int targetIndex = index;
        int min = Integer.MAX_VALUE;
        for(int i=index; i<perm.length; i++){
            if(min > perm[i] && perm[index-1] < perm[i]){
                min = perm[i];
                targetIndex = i;
            }
        }

        int temp = perm[index - 1];
        perm[index - 1] = perm[targetIndex];
        perm[targetIndex] = temp;

        sort(perm, index, perm.length);
    }

    private void sort(int[] a, int from, int to){
        for(int i=from; i<to; i++){
            int x = a[i];
            int j = i;
            while(j > from && a[j-1] > x){
                a[j] = a[j-1];
                j--;
            }
            perm[j] = x;
        }
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
   	ll N, K;
    cin >> N >> K;
  	ll A[N];
  	int sum = 0;
  	int ans = 0;
    for(int i = 0; i < N; ++i){
   		cin >> A[i];
    }
  	ll table[N] = {0};
   	for(int i = 0; i < N; ++i){
   		table[A[i]-1]++;
    }
  	sort(table, table + N, greater<int>());
  	for(int i = 0; i < K; i++){
      sum += table[i];
    }
  	ans = N - sum;
   
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
using namespace std;
const int M = 1e9 + 7;
int n;
int memo[100010][2] = {0};

int step(const vector<int>& a, int i = 0)
{
    if(i >  n) return 0;
    if(i == n) return 1;
    if(a[i] == 1) return 0;
    if(memo[i+1][0] == 0){
        memo[i+1][0] = 1;
        memo[i+1][1] = step(a, i+1);
    }
    if(memo[i+2][0] == 0){
        memo[i+2][0] = 1;
        memo[i+2][1] = step(a, i+2);
    }
    return (memo[i+1][1]%M + memo[i+2][1]%M)%M;
}
int main()
{
    int m, k;
    cin >> n >> m;
    vector<int> a(n, 0);
    for(int i = 0; i < m; i++){
        scanf("%d", &k);
        a[k] = 1;
    }
    cout << step(a) << endl;
    return 0;
}

Measured memory_bytes: 4480
function Main(input){
	var N = input;
  var arr = [];
  
  if(N == 0)return "0";
  
 	while(N != 0){
  	var m = N % (-2);
  	var x = (N - m) / -2;
  	if(m < 0){x++;m+=2}
    arr.push(m);
    N = x;
  }
  return arr.reverse().join("");
}

// If you are interested in the algorithms I used, 
// there is no need to read down from this line.

((b,c,d)=>"undefined"!=typeof require?console.log(Main(require("fs").readFileSync("/dev/stdin","utf8"))):[b=b.split("\n").slice(1,-1).join("\n"),c=function(){try{return Main(b)}catch(f){return f.stack||f.message}}(),d=typeof c,"string"==d||(c=JSON.stringify(c)),$("<form>").append([[10,b],0,[1,d],0,[10,c]].map(f=>$(f?"<textarea>":"<br>",f&&{rows:f[0],cols:40,text:f[1]}))).appendTo("body")])(`
0
`);

Measured memory_bytes: 7752
#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};

int main() {
  int A, B;
  cin >> A >> B;
  int num = 1;
  int count = 0;
  while (num < B) {
    num += A - 1;
    count++;
  }
  cout << count << '\n';
}


Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(){
	int n, k, x, y, ans;
	scanf("%d%d%d%d", &n, &k, &x, &y);
	if(n <= k){
		ans = n * x;
	}else{
		ans = k * x + (n - k) * y;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128