akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=2e5+10;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int n,m,a[N],b[N],vis[N];
char s[N];
vector<int> E[N];
void adde(int u,int v) {
    s[v]=='A'?++a[u]:++b[u],E[v].pb(u);
    swap(u,v);
    s[v]=='A'?++a[u]:++b[u],E[v].pb(u);
}
int main() {
    n=gi(),m=gi(),scanf("%s",s+1);
    for(int i=1,u,v;i<=m;i++) u=gi(),v=gi(),adde(u,v);
    queue<int> q;
    for(int i=1;i<=n;i++) {
        //cerr<<a[i]<<" "<<b[i]<<endl;
        if(!a[i]||!b[i]) q.push(i),vis[i]=1;
    }
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int v:E[u]) {
            s[u]=='A'?--a[v]:--b[v];
            if((!a[v]||!b[v])&&!vis[v]) vis[v]=1,q.push(v);
        }
    }
    for(int i=1;i<=n;i++) if(!vis[i]) return puts("Yes"),0;
    puts("No");
    return 0;
}


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

using namespace std;

#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define INF (int)1e9
typedef long long int int64;

void print() {
    cout << endl;
}

void print(const char* s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(char s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(string s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int64 s, bool endline = true) {
    cout << s;
    if (endline) print();
}

void print(int s, bool endline = true) {
    cout << s;
    if (endline) print();
}

template <typename T, typename T2>
void print(pair<T, T2>& p, bool endline = true) {
    cout << "(";
    print(p.first, false);
    cout << ", ";
    print(p.second, false);
    cout << ")";

    if (endline) print();
}

template <typename T>
void print(T& t, bool endline = true) {
    cout << "[";
    for (auto it = t.begin(); it != t.end(); ++it) {
        if (it != t.begin()) cout << ", ";
        print(*it, false);
    }
    cout << "]";

    if(endline) print();
}

template <typename T>
vector<T> operator+(const vector<T> &a, const vector<T> &b)
{
    vector<T> ret;
    ret.reserve( a.size() + b.size() );                // preallocate memory
    ret.insert( ret.end(), a.begin(), a.end() );        // add A;
    ret.insert( ret.end(), b.begin(), b.end() );        // add B;

    return ret;
}

template <typename T>
vector<T> &operator+=(vector<T> &a, const vector<T> &b)
{
    a.reserve( a.size() + b.size() );                // preallocate memory without erase original data
    a.insert( a.end(), b.begin(), b.end() );         // add B;
    return a;
}

bool c(const pair<int,int> &a, const pair<int,int> &b) 
{ 
    return (a.first + a.second > b.first + b.second); 
}

int main() {
    // g++ -Wall -Wextra -O2 -std=c++17 helloworld.cpp  
    int64 n;
    cin >> n;

    vector<int64> v;

    for(int64 i = 0; i < n; ++i) {
        int64 tmp;

        cin >> tmp;
        v.push_back(tmp);
    }

    unordered_map<int64, int> m;

    for(auto& num : v) {
        if(m.find(num - 1) == m.end()) {
            m[num] = 1;
        } else {
            m[num] = m[num - 1] + 1;
            m[num - 1] = 0;
        }
    }

    int64 best = 0;

    for(auto& p : m) {
        if(p.second > best) {
            best = p.second;
        }
    }

    cout << n - best << endl;
    
    return 0;
}

Measured memory_bytes: 10096
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	int n, m;
	cin >> n >> m;
	vector<lli> a(n), b(n), c(m), d(m);
	rep(i, n) cin >> a[i] >> b[i];
	rep(i, m) cin >> c[i] >> d[i];
	
	rep(i, n){
		vector<pair<lli, int>> t(m);
		rep(j, m) t[j] = pair<lli, int>(abs(a[i]-c[j])+abs(b[i]-d[j]), j);
		sort(t.begin(), t.end());
		cout << t[0].sec+1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

typedef struct NODE {
	int x, y;
} Node;

const int N = 10;

Node node[N];

double getDis(Node a, Node b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
	int n, cnt = 0;
	double sum = 0.0;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d%d", &node[i].x, &node[i].y);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			sum += getDis(node[i], node[j]);
			cnt ++;
		}
	}
	printf("%.10f\n", sum * (n - 1) / cnt);
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
	int n,t1,t2,i=0;
	int a[10]={11,19,24,10,65,9,35,51,25,20};
	cin>>n;
	while(n!=0){
		for(int I=0;I<n;I++)cin>>t1>>t2;
		cout<<a[i]<<endl;
		i++;
		cin>>n;
	}
}


Measured memory_bytes: 3088
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[]a = new int[m];
    int[]b = new int[m];
    int[]ans= new int[n];

    for(int i=0; i<m; i++){
        a[i] = sc.nextInt();
        	ans[a[i]-1]++;
        b[i] = sc.nextInt();
        	ans[b[i]-1]++;
}

   for(int i=0; i<n; i++){
		System.out.println(ans[i]);
    	}
}
}


Measured memory_bytes: 35788
#include <iostream>
#include <cstdio>
#define MAX 10

using namespace std;

int n;
int output[MAX][MAX];

void compute(void){

  int x,y,v;
  for( int i = 1 ,x = 0,y = 0,v = 0 ; i <= n*n ; i++ ){
    output[x][y] = i;
    if( v == 0 ){ // 右上上昇
	x++;
	y--;
	if( y < 0 && x >= n ){ // 右上の角
	  y = 1;
	  x = n - 1;
	  v = 1;
	}else if( y < 0 ){ // y軸だけオーバー
	  y = 0 ;
	  v = 1;
	}else if( x >= n ){ // x軸だけオーバー
	  y += 2;
	  x = n - 1;
	  v = 1;
	}
      }else{ // 左下下降
	x--;
	y++;
	if( x < 0 && y >= n ){ // 左下の角
	  x = 1;
	  y = n - 1;
	  v = 0;
	}else if( x < 0 ){ // x軸だけオーバー
	  x = 0;
	  v = 0;
	}else if( y >= n ){ // y軸だけオーバー
	  y = n - 1;
	  x += 2;
	  v = 0;
	}	
    }
  }
}


int main(void){

  int CN = 1;
  while( cin >> n , n ){
    cout << "Case " << CN << ":" << endl;
    compute();
    CN++;
    for( int i = 0 ; i < n ; i++ ){
      for( int j = 0 ; j < n ;j++ ){
	printf("%3d",output[j][i]);
      }
      cout << endl;
    }
  }
  return 0;
}

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

long long a[200005];
long long alla;

int main(){
	long long N;
	cin >> N;
	for(long long i = 0; i < N; i++) {
		cin >> a[i];
		alla ^= a[i];
	}

	for(long long i = 0; i < N; i++) {
		cout << (alla^a[i]);
		if(i != N-1 ) {
			cout << " ";
		} else {
			cout << endl;
		}
	}
}


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

int main() {
	int N;
	int sum = 0;
	cin >> N;
	for (int i = 0; i < 4; i++) {
		int t = N % 10;
		if (t == 2) {
			sum++;
		}
		N /= 10;
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define ff first
#define ss second
#define p pair<int,int>
#define pb push_back
#define endl '\n'
#define w(t) ll test;cin>>test;while(test--)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define pi acos(-1)

int main()
{
    fast;
    ll n,x;
    cin>>n>>x;
    vector<ll> vec(n,0);
    for(auto &i:vec)
    {
        cin>>i;
    }
    ll ans=0;
    for(ll i=0;i<n-1;i++)
    {
        ll most=x;
        if(vec[i]>=most)
        {
            ans+=vec[i]-most;
            vec[i]=most;
            most=0;
        }
        else most-=vec[i];
        if(vec[i+1]>=most)
        {
            ans+=vec[i+1]-most;
            vec[i+1]=most;
            most=0;
        }
        else most-=vec[i];
    }
    cout<<ans<<endl;
}



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

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define debug( fmt, ... ) \
        fprintf( stderr, \
                  fmt "\n", \
                  ##__VA_ARGS__ \
        )

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1 << 29;
const double EPS = 1e-10;

double zero(double d) {
    return d < EPS ? 0.0 : d;
}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, a.size()) os << (i ? " " : "") << a[i];
    return os << ']';
}

string toString(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

const int MOD = 1000000007;
// a^k
ll fpow(ll a, ll k, int M) {
    ll res = 1ll;
    ll x = a;
    while (k != 0) {
        if ((k & 1) == 1)
            res = (res * x) % M;
        x = (x * x) % M;
        k >>= 1;
    }
    return res;
}

struct prepare {
	prepare() {
	    cout.setf(ios::fixed, ios::floatfield);
	    cout.precision(8);
	    ios_base::sync_with_stdio(false);
	}
} _prepare;

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

    vector<bool> dis(10, true);
    rep(i, K) {
        int t;
        cin >> t;
        dis[t] = false;
    }

    int now = N;
    while(true){
        stringstream ss;
        ss << now;
        string s = ss.str();
        bool ok = true;
        rep(i, s.size()) {
            if(!dis[s[i]-'0'])
                ok = false;
        }
        if(ok) {
            cout << now << endl;
            return 0;
        }

        now++;
    }
	
}

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

int main() {
    //
    long long num;
    long long tmp1, tmp2;
    cin >> num;

    for (long long h = 1; h <= 3500; h++) {
        for (long long n = 1; n <= 3500; n++) {
            tmp1 = num * h * n;
            tmp2 = 4 * h * n - num * n - num * h;
            
            if (tmp2 > 0 && tmp1 % tmp2 == 0) {
                long long tmp3 = tmp1 / tmp2;
                cout << h << " " << n << " " << tmp3;
                return 0;
            }
        }
    }
    //
}

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

using namespace std;

#define intt long long

intt n;

int main() {

	cin >> n;
	int ans = 0;
	intt m = n - 1;
	for (int i = 2; 1LL * i * i <= m; i ++) {
		if (m % i == 0) {
			ans ++;
			if (m != 1LL * i * i) {
				ans ++;
			}
		}
	}
	if (n != 2) ans ++;
	for (int i = 2; 1LL * i * i <= n; i ++) {
		if (n % i == 0) {
			m = n;
			while (m % i == 0) {
				m /= i;
			}
			if (m % i == 1) {
				ans ++;
			}
			if (n != 1LL * i * i) {
				m = n;
				intt j = n / i;
				while (m % j == 0) {
					m /= j;
				}
				if (m % j == 1) {
					ans ++;
				}
			}
		}
	}
	ans ++;
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define ub upper_bound
#define lb lower_bound
#define all(v) ((v).begin()),((v).end())
#define allr(v) ((v).rbegin()),((v).rend())
#define ff first
#define ss second
#define mp make_pair
#define pll pair<ll,ll> 
#define fo(i,n) for(ll i=0;i<n;i++)
#define foa(i,s,e) for(ll i=(s);i<e;i++)
#define fod(i,s,e) for(ll i= (s);i>=(e);i--)
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
#define sz(x) (ll)(x.size())
#define ANS cout<<ans<<'\n'
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
const ld pi = 3.14159265358979323846;
ll MOD = 1e9 + 7;
//ll MOD = 998244353;
const char nl = '\n';
const ll inf = 1e15;
ll mul(ll x,ll y){
    return (1ll* (x%MOD)*(y%MOD));
}
ll modpow(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=z*x;x =x*x ;y/=2;}return z;}
ll gcd(ll a,ll b){if(a<b) return gcd(b,a);if(b==0) return a;return gcd(b,a%b);} 
ll min(ll a,ll b){if(a<b)return a;return b;}
ll max(ll a,ll b){if(a>b)return a;return b;}
ll sq(ll a){
    ll ans = (1ll*a*a);
    return ans;
}
const ll N = 1e5 + 1;
ll dp[N];
void solve(){
  ll n, w;
  cin >> n >> w;
  fo(i, n){
    ll wt, val;
    cin >> wt >> val;
    for(ll j = w - wt; j >= 0; j--){
      dp[j + wt] = max(dp[j + wt], dp[j] + val);
    }
  }
  ll ans = 0;
  fo(i, w + 1){
    ans = max(ans, dp[i]);
  }
  ANS;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    ll TC = 1;
    //cin>>TC;
    while(TC--){
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

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

int main(void){
  int x[5] = {0};
  int i = 0;
  
  for(i=0;i<5;i++){
    cin >> x[i];
  }
  
  for(i=1;i<=5;i++){
    if(x[i-1] != i){
      cout << i << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 3584
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

int main() {
    int H;
    int W;
    scanf("%d %d", &H, &W);

    int ASTCOUNT = 0;

    char tmp[8];

    vector< vector<char> > A;
    vector< vector<int> > I;

    A.resize(H);
    I.resize(H);

    for (int i = 0; i < H; i++)
    {
        A[i].resize(W);
        I[i].resize(W);

        scanf("%s", tmp);

        for (int j = 0; j < strlen(tmp); j++)
        {
            A[i][j] = tmp[j];
            if (tmp[j] == '#') ASTCOUNT++;
        }
    }

    int y = 0;
    int x = 0;
    I[0][0] = 1;

    int STPCOUNT = 1;

    while (true)
    {
        if (x == W - 1 && y == H - 1)
        {
            if (A[y - 1][x] == '#' && I[y - 1][x] == 0)
            {
                printf("%s\n", "Impossible");
                return 0;
            }
            if (A[y][x - 1] == '#' && I[y][x - 1] == 0)
            {
                printf("%s\n", "Impossible");
                return 0;
            }
            break;
        }
        if (-1 < y - 1)
        {
            if (A[y - 1][x] == '#' && I[y - 1][x] == 0)
            {
                printf("%s\n", "Impossible");
                return 0;
            }
            I[y - 1][x] == 1;
        }
        if (-1 < x - 1)
        {
            if (A[y][x - 1] == '#' && I[y][x - 1] == 0)
            {
                printf("%s\n", "Impossible");
                return 0;
            }
            I[y][x - 1] = 1;
        }
        if (x + 1 < W)
        {
            I[y][x + 1] = 1;
            if (A[y][x + 1] == '#')
            {
                x = x + 1;
                STPCOUNT++;
                continue;
            }
        }
        if (y + 1 < H)
        {
            I[y + 1][x] = 1;
            if (A[y + 1][x] == '#')
            {
                y = y + 1;
                STPCOUNT++;
                continue;
            }
        }
        printf("%s\n", "Impossible");
        return 0;
    }

    if (ASTCOUNT == STPCOUNT)
    {
        printf("%s\n", "Possible");
        return 0;
    }
    else
    {
        printf("%s\n", "Impossible");
        return 0;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int64_t i=0;i<(n);i++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REV(c) reverse((c).begin(),(c).end())
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define VIN(n,v) for(int64_t i=0;i<(n);i++){cin >> (v).at(i);}

using namespace std;
typedef int64_t I;
typedef pair<I,I> P;
typedef vector<I> V;

I MOD = pow(10,9)+7;

// 最大公約数
I gcd(I a, I b) {
  return b != 0 ? gcd(b, a % b) : a;
}

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

int ctoi(char c){
  return c - '0';
}

int main(){
  I n;
  cin >> n;
  V v(n);
  VIN(n,v);
  SORT(v);
  double t = 0;
  REP(i,n){
    t += v.at(i);
    if (i != 0){
      t = t / 2;
    }
  }
  cout << t << endl;
  return 0;
}



Measured memory_bytes: 256
// ITP1_9_D Transformation
import java.io.*;

class Main {

   static String str;

   public static void main(String args[]) {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      try {
         str = br.readLine();
         int q = Integer.parseInt(br.readLine());
         for (int i = 0; i < q; i++) {
            String[] inst = br.readLine().split(" ");
            int a = Integer.parseInt(inst[1]);
            int b = Integer.parseInt(inst[2]) + 1;
            if (inst[0].equals("print"))  print(a, b);
            else if (inst[0].equals("reverse")) reverse(a, b);
            else if (inst[0].equals("replace")) replace(a, b, inst[3]);
         }
      }

      catch (Exception e) {
         System.err.println(e);
      }
   }

   static void print(int a, int b) {
      System.out.println(str.substring(a, b));
   }

   static void reverse(int a, int b) {
      String rev = new StringBuffer(str.substring(a, b)).reverse().toString();
      if (a == 0)
         str = rev + str.substring(b, str.length());
      else if (b == str.length())
         str = str.substring(0, a) + rev;
      else
         str = str.substring(0, a) + rev + str.substring(b, str.length());
   }

   static void replace(int a, int b, String p) {
      str = new StringBuffer(str).replace(a, b, p).toString();
   }
}

Measured memory_bytes: 21640
//84104971101048411497 - Can you guess what does this mean?
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define X real()
#define Y imag()
#define maxN 100005
#define maxC 2005
#define oo 1000000007
#define sz(a) (int)a.size()
#define EPS 1e-11

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int n, a[maxN];
ll d[maxN];

int main () {
    scanf("%d", &n);
    fto(i, 1, n) scanf("%d", &a[i]);

    sort(a+1, a+n+1);
    fto(i, 1, n) d[i] = d[i-1]+a[i];

    fdto(i, n-1, 0) {
        if (2*d[i] < a[i+1]) {
            printf("%d", n-i);
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <map>
using namespace std;

#define D

#ifdef D
void fncPrint(string& str) {
	int a, b;
	cin >> a >> b;
	cout << str.substr(a, 1 + b - a) << endl;
}
void fucreverse(string& str) {
	int a, b;
	cin >> a >> b;
	string::iterator it = str.begin();
	reverse(it + a,it + b+1);
}
void fucReplace(string & str) {
	int a, b;
	string p;
	cin >> a >> b >> p;
	str = str.substr(0,a) + p + str.substr(b+1,-1);
}
class mach {
public:
	mach() {
		arr.insert(make_pair("print", fncPrint));
		arr.insert(make_pair("reverse", fucreverse));
		arr.insert(make_pair("replace", fucReplace));

	}
public:
	void swichoder(string & oder,string& str) {
		it = arr.find(oder);
		if (it != arr.end())
			it->second(str);

	}
private:
	typedef 	map<string, void(*)(string&)> func_type;
	func_type	arr;
	func_type::iterator it;
};
mach ma;


int main(void)
{
	string str;
	cin >> str;
	int n;
	cin >> n;
	string oder;
	for (size_t i = 0; i < n; i++)
	{
		cin >> oder;
		ma.swichoder(oder,str);
	}

	return 0;
}
#endif // D

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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n) {
    string s;
    string t;
    cin >> s >> t;
    bool f = true;
    for (int i = 0; i < s.size(); ++i) {
      f = true;
      // cout << ">> " << i << endl;
      for (int j = 0; j < t.size() && i + j < s.size(); ++j) {
        f = f && (s[i + j] == t[j]);
        // cout << make_pair(s[i + j], t[j]) << endl;
      }
      if (f) {
        // cout << make_pair((n - i), i) << endl;
        cout << n * 2 - (n - i) << endl;
        break;
      }
    }
    if (!f) cout << s.size() + t.size() << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<string>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rep2(i,s,n) for(int i=s;i< (int)n; i++)
#define ll long long 
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
  string s;
  cin >>s;
  int a=0;
  int b=0;
  int c=0;
  int S=s.size();
  rep(i,s.size()){
    if(s[i]=='b') b++;
    if(s[i]=='a') a++;
    if(s[i]=='c') c++;
  }
  if(S==0) cout <<"NO"<<endl;
  else{
  if(S%3==0){
    if((a==S/3)&&(b==S/3)&&(c==S/3)) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
  }else if(S%3==1){
    if(((a==S/3+1)&&(b==S/3)&&(c==S/3))||((a==S/3)&&(b==S/3+1)&&(c==S/3))||((a==S/3)&&(b==S/3)&&(c==S/3+1))) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
  }else{
    if(((a==S/3+1)&&(b==S/3+1)&&(c==S/3))||((a==S/3)&&(b==S/3+1)&&(c==S/3+1))||((a==S/3+1)&&(b==S/3)&&(c==S/3+1))) cout <<"YES"<<endl;
    else cout <<"NO"<<endl;
  }
  }
}

Measured memory_bytes: 512
#include<iostream>
#include<cctype>
#include<cstring>
using namespace std;

int main(){
    int n;
    cin >> n;
    int taro = 0, hanako = 0;
    for(int i = 0; i < n; i++){
        string x,y;
        cin >> x >> y;
        if(x < y){
            hanako += 3;
        }else if (x > y){
            taro += 3;
        }else{
            hanako++;
            taro++;
        }
    }
    cout << taro << " " << hanako << endl;
    return 0;
}


Measured memory_bytes: 3184
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		double a = sc.nextInt();
		double b = sc.nextInt();
		double c = sc.nextInt();
		double f =9999;
		int g = 0;
		for(int i = 1; i <= a; i++){
			double d = sc.nextInt();
			double e = b-d*0.006;
			if(f>Math.abs(c-e)){
				f = Math.abs(c-e);
				g = i;
			}
		}
		System.out.println(g);
	}
}

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

#define rep(i, n) for(int i=0;i<n;i++)

double norm(int d, double *x, double *y) {
    double norm = 0;
    rep(i, d) {
        norm += (x[i] - y[i]) * (x[i] - y[i]);
    }
    return sqrt(norm);
}

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

    int n, d;
    cin >> n >> d;

    double x[n][d];
    rep(i, n){
        rep(j, d){
            cin >> x[i][j];
        }
    }

    int ans = 0;
    rep(i, n){
        for (int j = i + 1; j < n; j++){
            double dist = norm(d, x[i], x[j]);
            if (ceil(dist) == floor(dist)) {
                ans++;
            }
        }
    }

    cout << ans << "\n";

    return 0;
} 

Measured memory_bytes: 256
H, W = map(int, input().split())
M = [None]*(H*W)
S = [list(map(int, input().split())) for i in range(H)]
G = [[None]*W for i in range(H)]
for i in range(H):
    s = S[i]
    for j in range(W):
        M[s[j]-1] = (i, j)
D = 0,-1,0,1,0

ans = 0
for i in range(H*W):
    y, x = M[i]
    g = None
    for k in range(4):
        nx = x + D[k]; ny = y + D[k+1]
        if not 0 <= nx < W or not 0 <= ny < H or i+1 < S[ny][nx]:
            continue
        if g is None:
            g = G[ny][nx]
        elif g != G[ny][nx]:
            g = -1
    if g == -1:
        ans += 1
    if g is None:
        G[y][x] = i
    else:
        G[y][x] = g
print(ans)

Measured memory_bytes: 148472
#include<bits/stdc++.h>
#define A 100010
#define X first
#define Y second
using namespace std;int n,q,z,m[A],u[A];vector<int> c[A];stack<pair<char,int> > Q;void D(int x,int g){u[x]=g;if(m[x])g=x;for(int i=0;i<c[x].size();i++)D(c[x][i],g);}int F(int x){if(m[x])return x;int t=F(u[x]);u[x]=t;return t;}int main(){while(cin>>n>>q&&n){for(int i=0;i<n;i++){c[i].clear();u[i]=0,m[i]=0;}for(int i=1;i<n;i++){cin>>z;z--;c[z].push_back(i);}m[0]++;for(int i=0;i<q;i++){pair<char,int> r;cin>>r.X>>r.Y;r.Y--;if(r.X=='M')m[r.Y]++;Q.push(r);}D(0,0);long long s=0;while(!Q.empty()){if(Q.top().X=='M')m[Q.top().Y]--;else s+=F(Q.top().Y)+1;Q.pop();}cout<<s<<endl;}return 0;}

Measured memory_bytes: 13472
#include <cstdio>
#include <queue>
using namespace std;

int main(void)
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		queue <int> a;
		int tmp, b = 0, c = 0;
		for (int i = 0; i < 10; i++){
			scanf("%d", &tmp);
			a.push(tmp);
		}
		
		while (1){
			tmp = a.front();
			if (b < tmp) {
				b = tmp;
				a.pop();
			}
			else if (c < tmp) {
				c = tmp;
				a.pop();
			}
			else break;
		}
		
		if (a.empty()) puts("YES");
		else puts("NO");
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const double eps = 1e-7;
int N, M, Q, T;
ll A[MAXN], K;

int main()
{
	int i, j;
	scanf("%lld%d", &K, &N);
	for (i = 1; i <= N; ++i) {
		scanf("%d", &A[i]);
	}
	ll mini = LINF;
	for (i = 1; i < N; ++i) {
		mini = min(mini, K -(A[i + 1] - A[i]));
	}
	mini = min(mini, K - A[1] - (K - A[N]));
	printf("%lld", mini);
}

Measured memory_bytes: 1792
#include<iostream>

using namespace std;

int main()
{
	int A;
	int B;
	int C;
	int X;
	int counter=0;

	int i;
	int j;
	int k;

	cin >> A;
	cin >> B;
	cin >> C;
	cin >> X;

	for (i = 0;i <= A;i++) {
		for (j = 0;j <= B;j++) {
			for (k = 0;k <= C;k++) {
				if (500 * i + 100 * j + 50 * k == X) {
					counter++;
				}
			}
		}
	}

	cout << counter << endl;

    return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "algorithm"
#include "vector"
#include "string"

int main(int argc, char const *argv[]) {

  std::string S, T, SS;

  std::cin >> S;
  std::cin >> T;
  int l = S.size();

  SS.append(S);
  SS.append(S);

  // std::cout << l << '\n';
  // std::cout << SS << '\n';
  std::string res = "No";

  for (size_t i = 0; i < l; i++) {
    std::string Sc;

    for (size_t i2 = 0; i2 < l; i2++) {
      Sc.append(SS, i+i2, 1);
    }

    // std::cout << Sc << '\n';
    if(Sc == T) {
      res = "Yes";
      break;
    }
  }

  std::cout << res<<"\n" ;

  return 0;
}


Measured memory_bytes: 256
X, Y = map(int, input().split())

tf = False
if X == 1:
    if Y == 2 or Y == 4:
        tf = True
else:
    for i in range(0, X + 1):
        if i * 2 + (X - i) * 4 == Y:
            tf = True

if tf:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 61804
class Node:
    def __init__(self):
        self.parent_id = -1
        self.depth = 0
        self.children = []

global nodes

def calc_depth(node_id,a):
    nodes[node_id].depth = a
    for child in nodes[node_id].children:
        calc_depth(child, a+1)

n = int(input())
nodes = []
for l in range(n):
    node = Node()
    nodes.append(node)
for l in range(n):
    a = list(map(int,input().split()))
    node_id = a[0]
    num = a[1]
    for i in range(num):
        child_id = a[2+i]
        nodes[node_id].children.append(child_id)
        nodes[child_id].parent_id = node_id
    
for i in range(n):
    if nodes[i].parent_id == -1:
        calc_depth(i,0)
        break

for i in range(n):
    print("node {0}: parent = {1}, depth = {2}, ".format(i,nodes[i].parent_id,nodes[i].depth),end = "")
    if nodes[i].parent_id == -1:
        print("root,",end = "")
    else:
        if len(nodes[i].children)==0:
            print("leaf,",end="")
        else:
            print("internal node,",end = "")
    print(" [",end = "")
    print(', '.join(map(str,nodes[i].children)),end = "")
    print("]")


Measured memory_bytes: 40700
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;
int main(){
    int n;
    cin >> n;
    vector<int> data(n);
    rep(i,0,n){
        cin >> data[i];
    }
    int cnt=0;
    for(int i=0;i<n;i+=2){
        if(data[i]%2==1){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    
  return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin >> a >> b;
    if(a==1 && b==2)
        cout << "3" << endl;
    else if(a==2 && b==1)
        cout << "3" << endl;
    else if(a==2 && b==3)
        cout << "1" << endl;
    else if(a==3 && b==2)
        cout << "1" << endl;
    else if(a==1 && b==3)
        cout << "2" << endl;
    else if(a==3 && b==1)
        cout << "2" << endl;
    return 0;

}


Measured memory_bytes: 3600
#include <iostream>

using namespace std;

int main(){
  int N;
  cin >> N;
  int H[N];
  for(int i = 0;i<N;i++){
    cin >> H[i];
  }
  int sum = 0;
  int left_max = 0;

  for(int i=0; i<N; i++){
    if(left_max <= H[i]){
      sum += 1;
      left_max = H[i];
    }
  }
  std::cout << sum << std::endl;
  return 0;
}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
D = int(input())
count = 0
if(A<=B):
	if(C<=D):
		count = A+C
	else:
		count = A+D

else:
	if(C<=D):
		count = B+C
	else:
		count = B+D

print(count)

Measured memory_bytes: 3060
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,A,B,C,D;
  cin>>N>>A>>B>>C>>D;
  cout<<min((N+A-1)/A*B,(N+C-1)/C*D)<<endl;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < (int)(n);i++)
 
int main(){
    const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    const int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
 
    int h, w;
    string s[100];
 
    cin >> h >> w;
 
    rep(i,h){
        cin >> s[i];
    }
 
    rep(i,h){
        rep(j,w){
            int a=0;
 
            if(s[i][j]=='#'){
               // t[i][j] = '#';
                continue;
            }
 
            rep(k,8){
                const int ii = i + dy[k];
                const int jj = j + dx[k];
 
                if(ii<0||ii>h-1){
                    continue;
                }
                if(jj<0||jj>w-1){
                    continue;
                }
 
                if(s[i+dy[k]][j+dx[k]]=='#'){
                    a++;
                }
            }
 
 
            s[i][j] = (char) (a+(int)'0');
 
        }
    }
    rep(i,h){
        cout << s[i] << endl;
    }
    
 
}

Measured memory_bytes: 256
#include <cstdio>
int main(){
	long long A,B,K;
	scanf("%lld%lld%lld",&A,&B,&K);
	if(K <= A){
	printf("%lld %lld",(A-K),B);
	}
	else if((K-A) >= B){
	printf("%lld %lld",0,0);
		}
	else {
	
	printf("%lld %lld",0,B-(K-A));
		}
	return 0;
	}

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

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>

const int INF = 0x3f3f3f3f;
const ll  LINF = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = 45+10;
const int mod = 1e9+7;

using namespace std;

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

	int k,v=7,ans=-1;
	
	cin >> k;

	for(int i=1;i<=1e6+10;++i){
		if(v%k==0){
			ans=i;
			break;
		}
		v = (v*10+7);
		v%=k;
	}

	cout << ans << endl;

    return 0;
}



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

int main() {
    int x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i,x) cin >> a[i];
    rep(i,y) cin >> b[i];
    rep(i,z) cin >> c[i];
    vector<ll> ab;
    rep(i,x)rep(j,y) {
      ab.push_back(a[i]+b[j]);
    }
    sort(ab.rbegin(), ab.rend());
    
    vector<ll> abc;
    for (int i = 0; i < min(k, (int)ab.size()); i++) {
      rep(j,z) {
        abc.push_back(ab[i]+c[j]);
      }
    }
    sort(abc.rbegin(), abc.rend());
    rep(i,k) cout << abc[i] << endl;
    return 0;
}

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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define MOD (ll)1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

int main()
{
    int D,G;
    cin >> D >> G;

    vector<int> p(D);
    vector<ll> c(D);
    rep(i,D) cin >> p[i] >> c[i];
    ll ans = INF_LL;

    rep(bit,(1<<D))
    {
        vector<int> S;
        rep(i,D)
        {
            if (bit & (1<<i)) S.push_back(i);
        }

        // 全完する問題
        ll score = 0;
        ll accept_num = 0;
        for (int i = 0; i < (int)S.size(); ++i)
        {
            score += (S[i]+1)*100*p[S[i]];
            score += c[S[i]];
            accept_num += p[S[i]];
        }
        //cout << "ans is " << accept_num << " and score is " << score << endl;

        // 一部解く問題
        sort(all(S),greater<int>());
        for( int i = D-1; i > -1; i-- )
        {

            if( score >= G )break;

            bool used = false;
            rep(j,S.size())
            {
                if( i == S[j] )
                {
                    used = true;
                    break;
                }
            }
            if(used) continue;
            rep(j,p[i])
            {
                score += (i+1)*100;
                accept_num++;
                if( score >= G )break;
            }
        }
        /*
        cout << " S is ";
        rep(i,S.size()) cout << S[i] << " ";
        cout << "and ans is " << accept_num << endl;
        cout << endl;
        */
        if( score >= G ) chmin(ans, accept_num);
    }
    cout << ans << endl;
}


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

int main() {
	int n;
	cin >> n;
	vector<int> ans(n);
	rep(i, n) {
		int a;
		cin >> a;
		a--;
		ans[a] = i + 1;
	}
	rep(i, n) cout << ans[i] << " ";
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int i;
    string n;
    cin>>n;
    for (i=0;i<3;i++)
    {
        if (n[i]=='1')
            cout<<'9';
        else if (n[i]=='9')
            cout<<'1';
        else
            cout<<n[i];
    }
}


Measured memory_bytes: 256
#coding: utf-8
#scoreの中から10の倍数でなくかつ最小のものを返す
def search_min(list):
    l = []
    for i in list:
        if i % 10 != 0:
            l.append(i)
    if len(l) > 0:
        return min(l)
    else:
        return 0



N = int(input())
score = [int(input()) for i in range(N)]

sum = 0
for i in score:
    sum = sum + i

if sum % 10 != 0:
    print (sum)
else:
    s = 0
    while s % 10 == 0:
        m = search_min(score)
        if m == 0:#配点がすべて10の倍数のとき
            break
        else:
            s = sum - m
            score.remove(m)
    print (s)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  int count=0;
  string str;

  cin>>n>>str;
  for(int i=0;i<n-2;i++){
    if(str[i]=='A' && str[i+1]=='B' && str[i+2]=='C') count++;
  }

  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var L = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        var ans = 0;
        var sortedL = L.OrderBy(x => x).ToArray();

        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                for (int k = j + 1; k < N; k++)
                {
                    if (sortedL[i] + sortedL[j] <= sortedL[k])
                    {
                        continue;
                    }
                    ans++;
                }
            }
        }

        WriteLine(ans);
    }
}


Measured memory_bytes: 28872
def gcd(a, b):
    return gcd(b, a%b) if b!=0 else a

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def isprime(n):
    sup = int(n**0.5)
    for i in range(2, sup+1):
        if n%i==0:
            return False
    return True

A, B = map(int, input().split())
g = gcd(A, B)
divs = make_divisors(g)
ans = 0
for d in divs:
    ans += 1 if isprime(d) else 0
print(ans)

Measured memory_bytes: 3276
import static java.lang.Math.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int modP = 1000000007;

	static class TaskX {
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt();
			long[] t = new long[n], a = new long[n];
			for (int i = 0; i < n; i++) {
				t[i] = in.nextLong();
				a[i] = in.nextLong();
			}
			for (int i = 1; i < n; i++) {
				if (t[i-1]>t[i] || a[i-1]>a[i]) {
					long m1, m2;
					if (t[i-1]%t[i]==0) {
						m1 = t[i-1]/t[i];
					} else {
						m1 = (t[i-1]/t[i])+1;
					}
					if (a[i-1]%a[i]==0) {
						m2 = a[i-1]/a[i];
					} else {
						m2 = (a[i-1]/a[i])+1;
					}
					long multi = max(m1, m2);
					t[i] *= multi;
					a[i] *= multi;
				}
			}
			out.println(t[n-1]+a[n-1]);

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}

	}

}


Measured memory_bytes: 22228
#include <cstdio>

int main(int argc, char *argv[]) {
	int e1, e2 ,dline, sum_rhom=0, sum_rect=0;
	while (EOF != fscanf(stdin, "%d,%d,%d", &e1, &e2, &dline)) {
		// if has 90-angle
		if (e1*e1+e2*e2 == dline*dline) {
			sum_rect++;
			continue;
		}
		// if rhombic
		if (e1 == e2) {
			sum_rhom++;
			continue;
		}
	}
	printf("%d\n", sum_rect);
	printf("%d\n", sum_rhom);
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
    string s;
    cin>>s;
    int ans=700;
    for(int i=0; i<3; i++){
        if(s[i]=='o'){
            ans+=100;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<cstdio>
using ll = long long;
constexpr ll p=1e9+7;
ll fct[2001];
long long ext_gcd(long long a,long long b,long long &x,long long &y){
    if(b==0){x=1;y=0;return a;}
    long long q=a/b, g=ext_gcd(b,a-q*b,x,y), z=x-q*y;
    x=y; y=z;
    return g;
}
long long inv(long long a){
    long long x,y;
    ext_gcd(a,p,x,y);
    return (x+p)%p;
}
void make_factorial(long long *x, int len){
    x[0]=1;
    for(int i=1;i<len;i++)x[i]=(x[i-1]*i)%p;
}

long long ncr(long long n,long long r){
    if(n<0||n<r||r<0)return 0;
    return (fct[n]*inv(fct[r])%p)*inv(fct[n-r])%p;
}

int main(){
    ll k,n;
    scanf("%lld%lld",&n,&k);
    make_factorial(fct,2001);
    for(int i=1;i<=k;i++){
        printf("%lld\n",ncr(n-k+1,i)*ncr(k-i+i-1,i-1)%p);
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
	int x, y; cin >> x >> y;
	int ans = 0;
	if (x <= 3) ans += (4 - x) * 100000;
	if (y <= 3) ans += (4 - y) * 100000;
	if (x == 1 && y == 1) ans += 400000;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}

int main(){
    int H,W;
    cin>>H>>W;
    char maps[103][103];
    int dp[103][103];
    for(int i=0;i<103;i++){
        for(int j=0;j<103;j++){
            dp[i][j]=11111;
            maps[i][j]='.';
        }
    }
    dp[0][1]=0;
    dp[1][0]=0;
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin>>maps[i][j];
       }
    }
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            if(maps[i][j]=='.'){
                dp[i][j]=min(dp[i][j-1],dp[i-1][j]);
            }else{
                dp[i][j]=min((dp[i][j-1]+(maps[i][j-1]=='.')),(dp[i-1][j]+(maps[i-1][j]=='.')));
            }

        }
    }
    cout<<dp[H][W];

}

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

int main(){
  int k; cin >> k;
  int a, b; cin >> a >> b;
  bool ans = false;
  if(a%k==0)ans = true;
  else{
    if((a/k+1)*k<=b) ans = true;
  }
  if(ans)cout << "OK" << endl;
  else cout << "NG" << endl;
  return 0;
}

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

typedef signed long long ll;
typedef long double ld;

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

#define DEBUG

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

	int ans = a - (2 * b);
	if(ans < 0)
	{
		ans = 0;
	}
	cout << ans << endl;
	return 0;
}


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

int main() {

    int P, Q, R;
    cin >> P >> Q >> R;

    int m = max(P, max(Q, R));

    cout << P + Q + R - m << endl;

    return 0;
}

Measured memory_bytes: 3540