akhauriyash/Code-Regression huggingface dataset:
a, b = map(int, input().split())
c, d = map(int, input().split())
e, f = map(int, input().split())

x = [a, b, c, d, e, f]
x.sort()

if x == [1, 2, 2, 3, 3, 4]:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
#include<iostream>
#include<string.h>
using namespace std;

int main()
{
    int H, W;
    int h, w;
    cin >> H >> W;
    cin >> h >> w;
    int Z, z;
    Z = H * W;
    z = h * W + H * w;
    if (H == h or W == w){
        std::cout << 0 << std::endl;

    }
    else {
        int R, r;
        r = h * w;
        R = Z - z + r;
        std::cout << R << std::endl;
    }
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K, N;
  cin >> K >> N;
  vector<int> A(N);
  for (int i=0; i<N; i++)
    cin >> A.at(i);
  vector<int> D(N);
  for (int i=0; i<N-1; i++)
    D.at(i) = A.at(i+1) -A.at(i);
  D.at(N-1) = K - A.at(N-1) + A.at(0);
  int tmp=K, distance;
  for (int i=0; i<N; i++){
    distance = K - D.at(i);
    if (distance<tmp)
      tmp = distance;
  }
  cout << tmp << endl;
}

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

int main() {
  const int mod = 998244353;
  int N, tmp, mx;
  cin >> N;
  vector<int> cnt(N,0);
  for (int i=0; i < N; i++) {
    cin >> tmp;
    if ((i == 0 && tmp != 0) || (i != 0 && tmp == 0)) {
      cout << 0 << endl;
      return 0;
    }
    cnt.at(tmp)++;
    mx = max(mx, tmp);
  }
  if (mx == 0) {
    cout << (N == 0 ? 1 : 0) << endl;
    return 0;
  }
  int64_t ans = 1;
  int i = 1;
  while (i <= mx) {
    for (int j=0; j < cnt.at(i); j++) {
    ans *= cnt.at(i-1);
    ans %= mod;
    }
    i++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
import itertools
N = int(input())
F = [list(map(int,input().split())) for _ in range(N)]
F.insert(0,[0])
P = [list(map(int,input().split())) for _ in range(N)]
P.insert(0,[0])
cmax = -10**10
for x in itertools.product((0,1),repeat=10):
    if sum(x)>0:
        cnt = 0
        for i in range(1,N+1):
            c = 0
            for j in range(10):
                if x[j]==1 and F[i][j]==1:
                    c += 1
            cnt += P[i][c]
        cmax = max(cmax,cnt)
print(cmax)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
using namespace std;

signed main() {
	int a, b;
	cin >> a >> b;
	int c[50001];
	for (int d = 0; d <= a; d++) {
		c[d] = 1 << 29;
	}
	vector<int>f(b);
	for (int e = 0; e < b; e++)cin >> f[e];
	c[0] = 0;
	for (int g = 1; g <= a; g++) {
		for (int h = 0; h < b; h++) {
			if (g >= f[h])c[g] = min(c[g], c[g - f[h]] + 1);
		}
	}
	printf("%d\n", c[a]);
}

Measured memory_bytes: 3384
n,y=map(int,input().split())

for i in range(n+1):
    for j in range(n-i+1):
        #10000円札の枚数
        z=n-i-j
        if 1000*i+5000*j+10000*z==y:
            print(z,j,i)
            exit()
print(-1,-1,-1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define endl '\n'
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ll long long
#define ld long double
#define ii pair<int, int>
#define iii pair<int, ii>
#define vi vector<int>
#define vii vector<ii>
#define pq priority_queue
using namespace std;
const int ms = 2e5+100;
const int sigma = 30;
int n, m, k, t = 1;
string s;

void solve(){
  cin>>n;
  vi aux;
  vi a, b;
  for(int i=0; i<n; i++){
    cin>>k;
    a.pb(k);
  }
  for(int i=0; i<n; i++){
    cin>>k;
    b.pb(k);
  }
  for(int i=1; i<=n; i++) aux.pb(i);
  int ct = 0;
  vi ans;
  do{
    if(aux==a || aux==b) ans.pb(ct);
    ct++;
  }while(next_permutation(all(aux)));
  if(ans.size()==1) cout<<0<<endl;
  else cout<<abs(ans[0] - ans[1])<<endl;
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  while(t--){
    solve();
  }
}

Measured memory_bytes: 256
// Author: πα

#include <bits/stdc++.h>
using namespace std;

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long long long

int main()
{
    FastIO;
    int n, i;
    long count = 0, ans = 0;
    string s;
    cin >> s;
    n = s.length();
    for(i = n-1; i >= 0; i--)
    {
        if(s[i] == 'W')
            count++;
        else
            ans += count;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 720
'use strict'

function main(input) {
    let s = String(input.split('\n')[0].split(' ')[0]);
    let t = String(input.split('\n')[1].split(' ')[0]);
    let count = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] != t[i]) {
            count++;
        }
    }
    console.log(count);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 32960
#include <stdio.h>
#define N 100000
int depth (int);

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

node T[N];

int main () {
  int a, r, x, i, j, n, k;

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

  for(i = 0 ; i < n ; i++) {
    scanf("%d%d", &a, &k);
    if(k != 0) {
	scanf("%d", &x);
	T[a].left = x;
	T[x].parent = a;
	r = x;
      }
      for(j = 1 ; j < k ; j++) {
	scanf("%d", &x);
	T[x].parent = a;
	T[r].right = x;
	r = x;
      }
  }
      
  for(i = 0 ; i < n ; i++) {
    printf("node %d: parent = %d, depth = %d, ", i, T[i].parent, depth(i));
    if(T[i].parent == -1) {
      printf("root, ");
    }
    else if(T[i].left != -1) {
      printf("internal node, ");
    }
    else {
      printf("leaf, ");
    }
    printf("[");
    if(T[i].left != -1) {
      printf("%d", r=T[i].left);
    }
    while(T[r].right != -1) {
      printf(", %d", T[r].right);
      r = T[r].right;
    }
    printf("]\n");
  }
  return 0;
}
 
int depth(int x) {
  int c=0;
  while(T[x].parent >= 0) {
    c++;
    x = T[x].parent;
  }
  return c;
}

Measured memory_bytes: 1788
from collections import deque
around = [(0,1),(1,0),(0,-1),(-1,0)]

H,W = map(int,input().split())
grid = [list(input()) for _ in range(H)]

checked = [[0]*W for i in range(H)]

def bfs(si,sj):
    if grid[si][sj] == ".":
        b = 0; w = 1
    if grid[si][sj] == "#":
        b = 1; w = 0
    dq = deque()
    dq.append((si,sj))
    checked[si][sj] = 1
    while dq:
        i,j = dq.popleft()
        for di,dj in around:
            ni = i + di; nj = j + dj
            if not(0 <= ni <= H-1 and 0 <= nj <= W-1):
                continue
            if checked[ni][nj]:
                continue
            p = grid[i][j]
            np = grid[ni][nj]
            if (p,np) == (".","#"):
                b += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
            if (p,np) == ("#","."):
                w += 1
                dq.append((ni,nj))
                checked[ni][nj] = 1
    return b*w

ans = 0
for i in range(H):
    for j in range(W):
        if not checked[i][j] and grid[i][j] == ".":
            ans += bfs(i,j)
print(ans)

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

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}
int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}

bool solve(int N, vi& a, vi& b) {
    ll plus = 0, minus2 = 0, minus1 = 0;
    rep(i, N) {
        ll di = a[i] - b[i];
        if (di > 0) {
            plus += di;
        } else if (di < 0) {
            minus2 += -di / 2;
            minus1 += -di % 2;
        }
    }
    if (plus > minus2) return false;
    return true;
}

int main() {
    int N = loadint();
    vector<int> a(N), b(N);
    loadvec(a, N);
    loadvec(b, N);
    cout << (solve(N, a, b) ? "Yes":"No") << endl;
    return 0;
}


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

struct Node
{
	int key;
	Node* parent;
	Node* left;
	Node* right;
};

Node* root;
Node* NIL;

void insert(int key)
{
	Node* y = NIL;
	Node* x = root;
	Node* z;

	z = new Node;
	z->key = key;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL)
	{
		y = x;
		if (z->key < x->key)
		{
			x = x->left;
		}
		else
		{
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL)
	{
		root = z;
	}
	else
	{
		if (z->key < y->key)
		{
			y->left = z;
		}
		else
		{
			y->right = z;
		}
	}
}

void inOrder(Node* u)
{
	if (u == NIL)
	{
		return;
	}
	inOrder(u->left);
	cout << " " << u->key;
	inOrder(u->right);
}

void preOrder(Node* u)
{
	if (u == NIL)
	{
		return;
	}
	cout << " " << u->key;
	preOrder(u->left);
	preOrder(u->right);
}

int main()
{
	int m;
	cin >> m;
	for (int i = 0; i < m; ++i)
	{
		string command;
		cin >> command;
		if (command == "insert")
		{
			int key;
			cin >> key;
			insert(key);
		}
		else if (command == "print")
		{
			inOrder(root);
			cout << endl;
			preOrder(root);
			cout << endl;
		}
	}
	return 0;
}




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

int main() {
  double a,b,c,d;
  cin >> a >> b >> c >> d;
  double x=(a-c)*(a-c)+(b-d)*(b-d);
  cout << fixed << setprecision(4);
  cout << sqrt(x) << endl;
}


Measured memory_bytes: 3276
n = gets.to_i
t = gets.chomp.split(" ").map(&:to_i).unshift(0)
v = gets.chomp.split(" ").map(&:to_i).push(0).unshift(0)
for i in 1..n
  t[i] += t[i-1]
end
a = Array.new(t[-1]*2+1){|i|
  if i <= t[-1]*2-i
    i*0.5
  else
    (t[-1]*2-i)*0.5
  end
}
for i in 1..n
  if v[i] < v[i-1]
    for j in 0..t[i-1]*2
      if v[i]+0.5*(t[i-1]*2-j) < a[j]
        a[j] = v[i]+0.5*(t[i-1]*2-j)
      end
    end
  end
  for j in t[i-1]*2..t[i]*2
    if v[i] < a[j]
      a[j] = v[i]
    end
  end
  if v[i] < v[i+1]
    for j in t[i]*2..t[-1]*2
      if v[i]+0.5*(j-t[i]*2) < a[j]
        a[j] = v[i]+0.5*(j-t[i]*2)
      end
    end
  end
end
p a.inject(:+)/2

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S,class T>ostream&operator<<(ostream&os,map<S,T>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>ostream&operator<<(ostream&os,set<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;};
template<class S>auto&operator<<(ostream&os,vector<S>d){bool a=1;for(auto v:d){os<<(a?"":" ")<<v;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    rep(i,n){
        ll t;
        cin>>t;
        if(t%2==0 and (t%3!=0 and t%5!=0)){
            puta("DENIED");
            return 0;
        }
    }
    puta("APPROVED");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> llP;

ll mod(ll a, ll b){
  ll ret=a%b;
  if(ret<0) ret+=b;
  return ret;
}

ll modpow(ll a,ll b,ll c){
  ll res=1;
  while(b>0){
    if(b&1) res=mod(res*a,c);
    a=mod(a*a,c);
    b>>=1;
  }
  return res;
}

int main() {
  int h1,m1,h2,m2,k;
  cin>>h1>>m1>>h2>>m2>>k;
  int ans=0;
  if(h2==h1) ans+=m2-m1;
  else ans+=(60-m1)+m2+60*(h2-h1-1);
  cout<<ans-k<<endl;
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define forn(i, n) for (ll i = 0; i < (n); i++)
#define fori(i, b, e) for (ll i = (b); i < (e); i++)
#define forr(i, b, e) for (ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()
#define fi first
#define se second
#define Mat vector<vector<ll>>
#define Arr vector<ll>

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    cout << count_if(allele(s), [](char c)->bool{
        return c == '1';
    });
    return 0;
}

Measured memory_bytes: 256
(let ((a (read))
      (b (read))
      (c (read))
      (k (read)))
     (cond
       ((<= k a) (format t "~A" k))
       ((and (< a k)
             (<= k (+ a b))) (format t "~A" a))
       (t (format t "~A" (- a (- k a b))))))

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

int main()
{
    int N, D;
    cin >> N >> D;
    int Xi;
    vector<vector<int>> X(N, vector<int>(D));
    for(int i=0;i<N;i++){
        for(int j=0;j<D;j++){
            cin >> Xi;
            X[i][j]=Xi;
        }
    }
    int res = 0;
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            int tmp = 0;
            for(int k=0;k<D;k++){
                tmp += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
            }
            int tmp2 = sqrt(tmp);
            if(tmp2*tmp2 == tmp) res++;
        }
    }
    cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))

using namespace std;

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

int n;
ll dist[100000], vero[100000];

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

ll lcm(ll a, ll b)
{
	return ( a / gcd(a, b) * b);
}

void solve()
{	
	//dist[]/vero[]

	FOR(i, 0, n)//約分
	{
		ll cd = gcd(dist[i], vero[i]);
		dist[i] /= cd;
		vero[i] /= cd;
	}
	
	ll bs = dist[0];
	
	FOR(i, 0, n)//通分・分母
	{
		bs = lcm(bs, dist[i]);
	}
	
	FOR(i, 0, n)//通分・分子
	{
		vero[i] = vero[i] * (bs / dist[i]);
	}
	
	ll cm = vero[0];
	
	FOR(i, 0, n)//分子の最大公約数
	{
		cm = gcd(cm, vero[i]);
	}
	
	FOR(i, 0, n)
	{
		cout << vero[i]/cm << endl;
	}
	
	return;
}

int main()
{
	
	while(cin >> n, n)
	{
		FOR(i, 0, n)
		{
			cin >> dist[i] >> vero[i];
		}
		
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 1172
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
x,y = ips()

if y-x>=2019:
    print(0)
    exit(0)
x%=2019
y%=2019
if x>y:
    y+=2019
m = rem
for i in range(x,y):
    for k in range(i+1,y+1):
        m = min(m,(i*k)%2019)
print(m)

#3 * 673

Measured memory_bytes: 13768
#include<stdio.h>

int main(void)
{
	const double TSUBO = 3.305785;
	double a, b;
	double area;
	
	scanf("%lf %lf", &a, &b);
	
	area = (a * b) / TSUBO;
	
	printf("%.4f\n", area);
	
	return 0;
}

Measured memory_bytes: 648
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <algorithm>

#define REP(i, a, b) for (int i=a; i <b; i++)
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef vector< int > vi;

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

    vector<unsigned long long> a(n+1);

    a[0] = 2; a[1] = 1;
    REP(i, 2, n+1) {
        a[i] = a[i-1] + a[i-2];
    }

    printf("%llu", a[n]);
    return 0;
}

Measured memory_bytes: 256
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using Pair = pair<int64_t, int64_t>;

// std::cout << std::setprecision(20) << 1.1 << endl;

vector<vector<bool>> A;
vector<vector<bool>> T;

bool Matches(const int64_t r, const int64_t c) {
  const int64_t M = static_cast<int64_t>(T.size());
  for (int64_t i = 0; i < M; ++i) {
    for (int64_t j = 0; j < M; ++j) {
      if (A[r + i][c + j] != T[i][j]) {
        return false;
      }
    }
  }
  return true;
}

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

  int64_t N;
  cin >> N;
  vector<int64_t> A(N);
  for (int64_t i = 0; i < N; ++i) {
    cin >> A[i];
  }

  if (N <= 2) {
    cout << 1 << endl;
    return 0;
  }
  int64_t result = 1;
  int64_t start = 0;
  while (start < N) {
    int64_t compare = start + 1;
    while (compare < N && A[start] == A[compare]) {
      ++compare;
    }
    if (compare >= N) {
      break;
    }

    bool increase = (A[start] < A[compare]);

    while (compare < N && compare < N) {
      if (increase && A[compare - 1] > A[compare]) {
        break;
      }
      if (!increase && A[compare - 1] < A[compare]) {
        break;
      }
      ++compare;
    }
    if (compare >= N) {
      break;
    }
    ++result;
    start = compare;
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 1005

char JOI[MAX][MAX];
int h,w,n;
int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};

pair<int, int> goal[10];
bool check(int a,int b){
    return (a>=1&&a<=h&&b>=1&&b<=w);
}

int step[MAX][MAX];
int bfs(const pair<int, int>& st, const pair<int, int>& en){
    queue<pair<int,int> > q;
    q.push(st);
    memset(step, -1, sizeof(step));
    step[st.first][st.second]=0;
    int stp=0;
    while(!q.empty()){
        pair<int, int> S=q.front(); q.pop();
        int x=S.first;  int y=S.second;
        stp=step[x][y];
        for(int i=0; i<4; i++){
            int cx=x+dx[i]; int cy=y+dy[i];
            if(check(cx, cy)){
                if(JOI[cx][cy]!='X'&&step[cx][cy]==-1){
                    if(cx==en.first&&cy==en.second) return stp+1;
                    q.push(make_pair(cx, cy));
                    step[cx][cy]=stp+1;
                }
            }
        }
    }
}
int main(){
    cin>>h>>w>>n;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin>>JOI[i][j];
            if(JOI[i][j]=='S') goal[0]=make_pair(i, j);
            else if(JOI[i][j]>='0'&&JOI[i][j]<='9'){
                int x=JOI[i][j]-'0';
                goal[x]=make_pair(i, j);
            }
        }
    }
    int ans=0;
    for(int i=0; i<n; i++){
        ans+=bfs(goal[i],goal[i+1]);
    }
    cout<<ans<<endl;
}

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

using namespace std;
typedef long long ll;

int main() {
    int n,x;
    cin >> n >> x;
    vector<ll> a(n); 
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll before = 0;
    for(int i = 0; i < n; i++) {
        before += ll(a[i]);
    }
    if(a[0] > x) {
        a[0] = x;
    }
    for(int i = 0; i < n-1; i++) {
        if(a[i] + a[i+1] > x) {
            a[i+1] = x - a[i];
        }
    }
    ll after = 0;
    for(int i = 0; i < n; i++) {
        after += ll(a[i]);
    }
    cout << before - after << "\n";
    return 0;
}

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

int main(){
    double A,V,B,W,T,d;
    cin >> A >> V >> B >> W >> T;
    d = abs(A-B);
    if(V>W && (d/(V-W))<=T){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

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

using namespace std;

using ll = long long;

vector<int> a, b;
vector< vector<int> > g;
vector<ll> s;
vector<int> cnt;

int dfs(int cur, int par) {
    int& res = cnt[cur];
    for (int i : g[cur]) {
        int nex = (cur == a[i] ? b[i] : a[i]);
        if (nex == par) continue;
        res += dfs(nex, cur);
    }
    res++;
    return res;
}

void dfs2(int cur, int par, vector<ll>& ans, ll& sum) {
    for (int i : g[cur]) {
        int nex = (cur == a[i] ? b[i] : a[i]);
        if (nex == par) continue;
        int c = cnt[nex];
        int rest = g.size() - c;
        if (c == rest) ans[i] = -c;
        else {
            ans[i] = (s[nex] - s[cur]) / (rest - c);
            sum += ans[i] * c;
        }
        dfs2(nex, cur, ans, sum);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    a.resize(n - 1);
    b.resize(n - 1);
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        g[a[i]].push_back(i);
        g[b[i]].push_back(i);
    }

    s.resize(n);
    for (int i = 0; i < n; i++) cin >> s[i];

    cnt.resize(n, 0);
    dfs(0, -1);

    vector<ll> ans(n - 1, 0);
    ll sum = 0;
    dfs2(0, -1, ans, sum);
    for (int i = 0; i < n - 1; i++) {
        if (ans[i] < 0) {
            ans[i] = (s[0] - sum) / (-ans[i]);
            break;
        }
    }

    for (int i = 0; i < n - 1; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 16896
using System;
using System.Collections.Generic;
//using System.Linq;
class Program
{
  //static List<string> list;
	static void Main(string[] args)
	{
		// 入力フェーズ
        string[] input = Console.ReadLine().Split(' ');
        int K = int.Parse(input[0]);
        int S = int.Parse(input[1]);

        long pattern = 0;
        for(int x=0; x<=Math.Min(S,K); x++)
        {
          // x = ?の場合、Y+Z=S-x
          if(S-x-K > K) continue; // 組が作れない

          // x = ?の場合、Y+Z=Tを作りたいとして、min(T,K)から0になるまで...
          int T = S-x;
          if(T <= K)
          {
            // T通り作れる
            pattern += T + 1;
          }
          else
          {
            // (T-K) + K → T-2K + 0までのうち、左側の項 <= Kのだけ作れる
            pattern += Math.Max(2*K - T + 1, 0); // ０未満だと作れない
          }
        }

    // 出力
        Console.WriteLine(pattern);
    }
		class myClass{ //自作クラス
			public int ID {set; get;}
			public long Point {set; get;}
		}

}


Measured memory_bytes: 11092
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N, M = getNM()

if M == 1:
    print(1)
    exit()

def cmb_2(x,y):
    r = 1
    for i in range(1, y + 1):
        r = (r * (x - i + 1) * pow(i, mod - 2, mod)) % mod
    return r

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

num = prime_factorize(M)

ans = 1
for i in num:
    ans *= cmb_2(N + i[1] - 1, i[1])
    ans %= mod
print(ans)

Measured memory_bytes: 83492
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int b[N];

int main()
{
    int n,l;
    cin>>n>>l;
    int ans=0;
    for(int i=1; i<=n; i++)
        a[i]=l+i-1,ans+=a[i];

    int minn=INT_MAX;
    int res=0;
    for(int i=1; i<=n; i++)
    {
        if(minn>abs(a[i]))
        {
            minn=abs(a[i]);
            res=ans-a[i];
        }
    }
    cout<<res<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>

#define KETA 5

using namespace std;

void Display(char abacus[KETA][9]){
	char disp[8][KETA];

	for(int i = 0; i < KETA; ++i){
		for(int j = 0; j < 8; ++j){
			disp[j][KETA - i - 1] = abacus[i][j];
		}
	}
	for(int i = 0; i < 8; i++){
		for(int j = 0; j < KETA; ++j){
			cout << disp[i][j];
		}
		cout << '\n';
	}
}
int main(void){
	bool bFirst = true;
	const char *table[] ={
		"* = ****",
		"* =* ***",
		"* =** **",
		"* =*** *",
		"* =**** ",
		" *= ****",
		" *=* ***",
		" *=** **",
		" *=*** *",
		" *=**** "
	};
	while( true ){
		int n;
		char abacus[KETA][9] = {{0,},};

		cin >> n;
		cin.ignore();
		if(cin.eof())
			break;
		
		if( bFirst )
			bFirst = false;
		else
			cout << '\n';

		for(int i = 0; i < KETA; ++i){
			int k = n % 10;
			n /= 10;
			strcpy( abacus[i], table[k] ); 
		}
		Display( abacus );
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

int N;

int main(void){
    
    scanf("%d", &N);
    vector<ll> a(N);
    for(int i = 0; i < N; ++i) scanf("%lld", &a[i]);
    
    vector<ll> up, down; up = down = a;
    sort(up.begin(), up.end()), sort(down.begin(), down.end(), greater<ll>());
    
    vector<ll> v1(N, 0), v2(N, 0);
    if(N % 2){
        int cnt = 0, idx = 0;
        for(int i = N / 2; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v1[i] = up[idx++];
        cnt = 0, idx = 0;
        for(int i = N / 2 - 1; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v1[i] = down[idx++];
        
        cnt = 0, idx = 0;
        for(int i = N / 2; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v2[i] = down[idx++];
        cnt = 0, idx = 0;
        for(int i = N / 2 - 1; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v2[i] = up[idx++];
        
    }
    else{
        int cnt = 0, idx = 0;
        for(int i = N / 2 - 1; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v1[i] = up[idx++];
        cnt = 0, idx = 0;
        for(int i = N / 2; i >= 0 && i < N; i += (cnt % 2) ? -(cnt * 2) : cnt * 2) ++cnt, v1[i] = down[idx++];
        
        cnt = 0, idx = 0;
        for(int i = N / 2 - 1; i >= 0 && i < N; i += (cnt % 2) ? cnt * 2 : -(cnt * 2)) ++cnt, v2[i] = down[idx++];
        cnt = 0, idx = 0;
        for(int i = N / 2; i >= 0 && i < N; i += (cnt % 2) ? -(cnt * 2) : cnt * 2) ++cnt, v2[i] = up[idx++];
    }
    
    ll sum1 = 0, sum2 = 0;
    for(int i = 0; i < N - 1; ++i) sum1 += abs(v1[i] - v1[i + 1]), sum2 += abs(v2[i] - v2[i + 1]);
    printf("%lld\n", max(sum1, sum2));
    
    return 0;
}

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

using namespace std;
#define LL long long

const int INF  = 0x3f3f3f3f;
const int MAXN = 512345;

const double eps = (double) 1e-8;

bool equal (LL X, LL y) {
	double Y = (double) X / 2.0;
	// cout << fixed << setprecision(8) << Y << ' ' << y << endl;
	return fabs (Y - (double)y) <= eps;
}

int main () {

	ios_base::sync_with_stdio(false); cin.tie(NULL);

	LL W, H, x, y;
	cin >> W >> H >> x >> y;

	// cout << equal (H, y) << endl;

	bool can = (equal(W, x) && equal (H, y));

	double area = (W * H) / 2.0;

	cout << fixed << setprecision(6) << area << ' ' << can << endl;


	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define LL long long
int N;
LL ans;
LL X, A, B;
int main(){
	std::cin >> N >> A >>B>> X;
	for (int i = 1; i < N; i++) {
		LL tmp;
		std::cin >> tmp;
		ans += std::min((tmp - X)*A, B);
		X = tmp;
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

int n,k;
int h[100005];
int dp[100005] = {0};

int main(){
	memset(dp,0x3f,sizeof(dp)); dp[1] = 0;
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= n;i ++) scanf("%d",&h[i]);
	for(int i = 2;i <= n;i ++){
		for(LL j = 1;j <= k;j ++){
			if(i - j >= 0) dp[i] = min(dp[i],dp[i - j] + abs(h[i] - h[i - j]));
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 1024
# coding:utf-8
# ??\??????????????´??°????°???????????????????

i = 1
x = 1
y = 1
while x != 0 or y != 0:
    xy = raw_input().split()
    x = int(xy[0])
    y = int(xy[1])
    if x == 0 and y ==0:
        break
    if x < y :
        print x,y
    else:
        print y,x

Measured memory_bytes: 6312
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define INF 9223372036854775807
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0;
string s;
bool flag;
#pragma endregion
#define MAX 111111



int main(void) {
  vll edge[MAX];
  queue<ll> que;
  ll d1[MAX], dn[MAX];
  ll a, b;
  cin >> n;
  FOR(i, 0, n - 1) {
	cin >> a >> b;
	edge[a].pb(b);
	edge[b].pb(a);
  }
  FOR(i, 1, n + 1) {
	d1[i] = INF;
	dn[i] = INF;
  }
  d1[1] = 0;   dn[n] = 0;

  que.push(1);
  while (!que.empty()) {
	tmp = que.front();
	que.pop();
	FOR(j, 0, edge[tmp].size()) {
	  m = edge[tmp][j];
	  if (d1[m] == INF) {
		que.push(m);
		d1[m] = d1[tmp] + 1;
	  }
	}
  }

  que.push(n);
  while (!que.empty()) {
	tmp = que.front();
	que.pop();
	FOR(j, 0, edge[tmp].size()) {
	  m = edge[tmp][j];
	  if (dn[m] == INF) {
		que.push(m);
		dn[m] = dn[tmp] + 1;
	  }
	}
  }

  FOR(i, 1, n + 1) {
	if (d1[i] <= dn[i]) cnt++;
  }

  if (cnt > (n - cnt)) {
	cout << "Fennec" << endl;
  }
  else {
	cout << "Snuke" << endl;
  }

  return 0;
}

Measured memory_bytes: 8192
#include <iostream>
#include <string>
#include <cstdint>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <numeric>
#include <algorithm>
#include <cassert>

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k,a,b;
    cin >> k >> a >> b;
    for(int i = a; i <= b; ++i){
        if(i % k == 0){
            cout << "OK\n";
            return 0;
        }
    }
    cout << "NG\n";
    return 0;
}


Measured memory_bytes: 3652
N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])

Measured memory_bytes: 19076
import java.util.*;

class Main{
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        
        String S = sc.next();
        int l = S.length();
        char[] a = S.toCharArray();
        int child = 0;
        int[] ans = new int[l];
        int x = 0;
        int y = 0;

        for(int i=0; i<l-1; i++){
            child += 1;
            if(a[i]!=a[i+1] && a[i]=='R'){
                x = i;
                y = i + 1;
                ans[i + 1] += child / 2;
                ans[i] += child - child / 2 ;
                child = 0;
            }
            else if(a[i]!=a[i+1] && a[i]=='L'){
                ans[x] += child / 2;
                ans[y] += child - child / 2;
                child = 0;
            }
        }
        child += 1;
        ans[x] += child / 2;
        ans[y] += child - child / 2;
        System.out.print(ans[0]);
        for(int i=1; i<l-1; i++){
            System.out.print(" " + ans[i]);
        }
        System.out.println(" " + ans[l - 1]);
    }
}

Measured memory_bytes: 39912
#include <iostream>
#include <queue>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <string>
using namespace std;

int main(){
	double x1, x2, x3, y1, y2, y3, xp, yp;
	while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp) {
		double xa = x2 - x1;
		double ya = y2 - y1;
		double xb = x3 - x1;
		double yb = y3 - y1;
		double x = xp - x1;
		double y = yp - y1;
		double div = xa * yb - xb * ya;
		double a = (yb * x - xb * y) / div;
		double b = (-ya * x + xa * y) / div;
		if (a >= 0 && b >= 0 && a + b <= 1) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1220
#include<stdio.h>

int main(void){

  int P , Q , R;
  scanf("%d %d %d", &P , &Q , &R);

  int min = P + Q;
  min = (Q + R < min) ? Q + R : min;
  min = (P + R < min) ? P + R : min;

  printf("%d\n", min );
  
  return 0;
}


Measured memory_bytes: 128
dic = {}
dic1 = {}
s=input()
t=input()
ans = "Yes"
for i in range(len(s)):
  try:
    if dic[s[i]]!=t[i]:
      ans = "No"
  except:
    dic[s[i]] = t[i]
  try:
    if dic1[t[i]]!=s[i]:
      ans = "No"
  except:
    dic1[t[i]] = s[i]
print(ans)

Measured memory_bytes: 68220
while 1:
  H , W = map( int,raw_input().split() )
  if ( H , W ) == ( 0 , 0 ):
    break
  for k in range(H):
    if k%2 == 0 and W%2 == 0:
      print "#." * ( W/2 )
    elif k % 2 == 0 and W % 2 == 1:
      print "#." * ( W/2 ) + "#"
    elif k%2 == 1 and W%2 == 0:
      print ".#" * ( W/2 )
    elif k%2 == 1 and W%2 == 1:
      print ".#" * ( W/2 ) + "."
  print ''

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

int main(){
  int i,j;
  string s;
  cin>>s;
  
  for(i=0;i<s.size();i++){
    for(j=0;j<s.size();j++){
      if(i==j){
        continue;
      }
      if(s[i]==s[j]){
        cout<<"no"<<endl;
        return 0;
      }
    }
  }
  cout<<"yes"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(void){
  int n,x;
  while(cin>>n>>x,n){
    int table[301]={0};
    for(int i=1;i<=n;i++){
      for(int j=i+1;j<=n;j++){
    for(int k=j+1;k<=n;k++){
      table[i+j+k]++;
    }
      }
    }
    cout<<table[x]<<endl;
  }
  return 0;
}


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

int main(){
    int N;
    cin>>N;
    int  A[200];
    int MIN=1e9;
    for(int i=0;i<N;i++){
        cin>>A[i];
        int cnt=0;
        while(A[i]%2==0){
            cnt++;
            A[i]/=2;
        }
        MIN=min(MIN,cnt);
    }
    cout<<MIN<<endl;

    return 0;
}

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

// main.cpp

int main() {
  std::int_fast64_t N;
  std::cin >> N;
  std::vector<std::int_fast64_t> p;
  p.reserve(N);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), N, std::back_inserter(p));
  std::transform(p.begin(), p.end(), p.begin(), [](const std::int_fast64_t x){ return x - 1; });

  std::int_fast64_t answer = 0;
  for (std::int_fast64_t i = 0; i < N;) {
    if (p[i] == i) {
      if (i < N - 1) {
        if (p[i + 1] == i + 1) {
          ++answer;
          i += 2;
        } else {
          ++answer;
          i += 2;
        }
      } else {
        ++answer;
        ++i;
      }
    } else {
      ++i;
    }
  }

  std::cout << answer << std::endl;
  return 0;
}

Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;
import java.util.Random;

public class Main {
    private static FastScanner sc = new FastScanner();
    private static boolean DEBUG_FLG = false;

    public static void main(String[] args) {
    	long A = sc.nextLong();
    	long B = sc.nextLong();
    	long C = sc.nextLong();
    	long D = sc.nextLong();
    	long lcm = C * D / Gcd(C, D);
    	long x = B/C + B/D - B/lcm;
    	long y = (A-1)/C + (A-1)/D - (A-1)/lcm;
    	System.out.println((B-A+1) - x + y);
    }

    public static long Gcd(long a, long b) {
        if (a < b)
            return Gcd(b, a);
        while (b != 0) {
            long remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    static void debug(long... args) {
    	if(!DEBUG_FLG) return;
    	boolean flg = false;
    	for(long s : args) {
    		if(flg) System.out.print(" ");
    		flg = true;
    		System.out.print(s);
    	}
    	System.out.println();
    }



    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }

    static void shuffleArray(long[] arr){
        int n = arr.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n-i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
    }
}


Measured memory_bytes: 23124
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lb(x) x&-x
#define il inline
#define ll long long
#define llu unsigned long long
#define mem(x) memset(x,0,sizeof(x))
#define mem3(x) memset(x,0x3f,sizeof(x))
#define ccA() puts("耐心冷静查代码")
#define cc() puts("谁知盘中餐，粒粒皆辛苦")
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define fd(i,a,b) for(register int i=a;i>=b;--i)
#define fk(i,j) for(register int i=fir[j];i;i=nxt[i])
#define fv(i,q) for(int i=0;i<q.size();i++)
using namespace std;
inline ll read(){
    ll x=0,f=1;char c;
    for(c=getchar();c<'0'||c>'9';f=((c=='-')?-1:f),c=getchar());
    for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());
    return x*f;
}
inline void write(ll a){
    if(a==0){putchar('0');return;}
    if(a<0)putchar('-'),a=-a;
    char c1[120];
    ll h=0;
    while(a)c1[++h]=a%10+'0',a/=10;
    fd(i,h,1)putchar(c1[i]);
    return;
}
inline void write_(ll a){write(a);putchar(' ');}
inline void writeln(ll a){write(a);putchar('\n');}
//------------------------------------------------------
const int N=1000;
int n;
struct node{
	string st;
	int s,id;
}a[N];

bool cmp(node x,node y){
	if(x.st!=y.st)return x.st<y.st;
	return x.s>y.s;
}

int main(){
	n=read();
	fo(i,1,n){
		cin>>a[i].st>>a[i].s;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	fo(i,1,n){
		writeln(a[i].id);
	}
	return 0;
}

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

#define ll long long int
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MOD = 1e9 + 7;
typedef unsigned long long u64;

int main()
{
    IOS;
    int t = 1;
    //cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int h[n + 1];
        h[0] = -1;
        for (int i = 1; i <= n; i++) cin >> h[i];
        int ar[n + 1];
        bool br[n + 1];
        for (int i = 1; i <= n; i++)
        {
            ar[i] = 0;
            br[i] = true;
        }
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            ar[a] = 1;
            ar[b] = 1;
            if (h[a] < h[b]) br[a] = false;
            else if (h[b] < h[a]) br[b] = false;
            else
            {
                br[a] = false;
                br[b] = false;
            }
        }
        ll ct = 0;
        for (int i = 1; i <= n; i++)
        {
            if (br[i]) ct += 1;
        }
        cout << ct << endl;
    }
    return 0;
}


Measured memory_bytes: 4540
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    s = readline().rstrip()
    cnt = 0
    for i in range(1000):
        x = str(i).zfill(3)
        a = s[:-1].find(x[0])
        if a != -1:
            b = s[a + 1: -1].find(x[1])
            if b != -1:
                c = s[a + b + 2:].find(x[2])
                if c != -1:
                    cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9560
#include <iostream>

int N, C;
int Dr[31][31];
int Cr[501][501];
long long dp[3][31];

int main() {
  std::cin>>N>>C;
  for (int i = 1; i <= C; ++i)
    for (int j = 1; j <= C; ++j)
      std::cin>>Dr[i][j];
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= N; ++j)
      std::cin>>Cr[i][j];

  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= N; ++j) {
      for (int c = 1; c <= C; ++c)
        dp[(i+j)%3][c] += Dr[Cr[i][j]][c];
    }
  }

  long long ans = (1LL << 60);
  for (int a = 1; a <= C; ++a) {
    for (int b = 1; b <= C; ++b) {
      if (b == a)
        continue;
      for (int c = 1; c <= C; ++c) {
        if (c == a or c == b)
          continue;
        long long wrong = dp[0][a] + dp[1][b] + dp[2][c];
        ans = std::min(ans, wrong);
      }
    }
  }
  std::cout<<ans<<"\n";

  return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>
  
int main(){
  int i,n,cnt=1;
  scanf("%d",&n);
  getchar();
    char a[n];
  for(i=0;i<n;i++){
  scanf("%c",&a[i]);
  }
  
  for(i=0;i<n-1;i++){
    if(a[i]!=a[i+1])
	cnt++;
  }
  printf("%d\n",cnt);

  return 0;
}

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

int main() {
  int n;cin>>n;
  ll mod=1e9+7;
  int ans=1;
  for(int i=1;i<=n;i++){
    ans=i%mod*ans%mod;
  }
  cout<<ans<<endl;
}

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

int main(){
    int N, M, cntV, cnt;
    cin >> N >> M;
    vector<int> box(N);
    vector<bool> vote(N);
    for(int i = 0; i < N ; i++){
        vote.at(i) = false;
    }
    cntV = 0;
    cnt = 0;
    for(int i = 0; i < N ; i++){
        cin >> box.at(i);
        cntV += box.at(i);
    }

    for(int i = 0; i < N ; i++){
        if(cntV % (4*M) == 0){
            if(box.at(i) >= cntV / (4*M)){
                vote.at(i) = true;
            }
        }else{
            if(box.at(i) > cntV / (4*M)){
                vote.at(i) = true;
            }
        }
    }

    for(int i = 0; i < N ; i++){
        if(vote.at(i) == true){
            cnt++;
            if(cnt == M){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;

}

Measured memory_bytes: 256
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

def main():
	n,m,k=MI()
	mod=998244353
	
	f=[1]
	for i in range(1,n+10):
		f.append((f[-1]*i)%mod)
	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	
	mp=[1]
	for i in range(1,n+10):
		mp.append((mp[-1]*(m-1))%mod)
		
	
	ans=0
	for kk in range(k+1):
		cnt=f[n-1]*finv[kk]*finv[n-1-kk]
		cnt%mod
		cnt*=m*mp[n-kk-1]
		ans+=cnt
		ans%mod
	print(ans%mod)













if __name__=="__main__":
	main()


Measured memory_bytes: 114280