akhauriyash/Code-Regression huggingface dataset:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

def main():
    N=I()
    A=LIN(N)
    now = 1
    ans = A[0]-1
    for a in A[1:]:
        if a <= now + 1:
            now = max(a,now)
            continue
        ans += (a-1)//(now+1)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 10824
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        #print("j:"+str(j))
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True

        if max(white_list)>K:
            break


        if is_over:
            div_count += 1
            white_count = white_list


        #print(white_list)   
        #print(white_count)
        #print("div_count"+str(div_count))
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)

Measured memory_bytes: 46172
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

int up[101];
int down[101];

bool isaonb(int a,int b){
  while(up[b]){
    if(a==b)return true;
    b=up[b];
  }
  return false;
}

void overaf(int a){
  while(up[a]){
    int upa=up[a];
    down[up[a]]=0;
    up[a]=0;
    a=upa;
  }
  down[a]=0;
}

int topa(int a){
  while(up[a])a=up[a];
  return a;
}

main(){
  int m;
  while(cin>>m){
    if(m==0)break;

    memset(up,0,sizeof(up));
    memset(down,0,sizeof(down));

    int i,j;
    while(cin>>i>>j){
      if(i==0 && j==0)break;
      if(i==j)continue;
      if(i==0)continue;
      if(j==0){
	if(down[i]==0)continue;
	else {
	  overaf(down[i]);
	  continue;
	}
      }

      if(isaonb(i,j)){
	continue;
      }else if(isaonb(j,i)){
	if(down[i])overaf(down[i]);
	else overaf(i);
	up[j]=i;
	down[i]=j;
	continue;
      }else{
	if(down[i])overaf(down[i]);
	else overaf(i);
	int topj=topa(j);
	up[topj]=i;
	down[i]=topj;
	continue;
      }
    }

    vector<int> pile;
    for(int i=1;i<=m;i++){
      if(down[i])continue;
      int num=1;
      int cur=i;
      while(up[cur]){
	++num;
	cur=up[cur];
      }
      pile.push_back(num);
    }
    sort(pile.begin(),pile.end());
    for(int i=0;i<pile.size();i++){
      cout<<pile[i]<<endl;
    }
    cout<<"end"<<endl;
  }
}

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

int main(){
  int n; cin>>n;
  vector<int>a(n),b(n),c(n);
  int  x[100000];
  for(int i=0;i<100000;i++){
    x[i]=0;
  }
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  for(int i=0;i<n;i++){
    b[i]=a[i]+1;
    c[i]=a[i]-1;
  }
  for(int i=0;i<n;i++){
    x[a[i]]++;
    x[b[i]]++;
    x[c[i]]++;
  }
  int ans=0;
  for(int i=0;i<100000;i++){
    if(ans<x[i]){
      ans=x[i];
    }
  }
  cout<<ans<<endl;
}


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

int main()
{

        int A, B;
        cin >> A;
        cin >> B;

        int c;
        if (A == 1 && B == 2) {
                c = 3;
        }
        else if (A == 2 && B  == 1) {
                c = 3;
        }
        else if ((A == 2 && B == 3) || (A == 3 && B == 2)) {
                c = 1;
        }
        else if ((A == 1 && B == 3) || (A == 3 && B == 1)) {
                c = 2;
        }
        cout << c << endl;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<pair<int, int>> order;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int h, w; cin >> h >> w;
	rep(i, 0, h) {
		if (i % 2 == 0) {
			rep(j, 0, w) order.push_back({i, j});
		} else {
			rep(j, 0, w) order.push_back({i, w - 1 - j});
		}
	}

	reverse(all(order));
	int n; cin >> n;
	vector<vi> mp(h, vi(w));
	rep(i, 1, n + 1) {
		int t; cin >> t;
		rep(j, 0, t) {
			int a, b; tie(a, b) = order.back(); order.pop_back();
			mp[a][b] = i;
		}
	}

	rep(i, 0, h) {
		rep(j, 0, w) cout << mp[i][j] << " \n"[j + 1 == w];
	}
}


Measured memory_bytes: 512
n, m = map(int, input().split())
s = []
g = []
for _ in range(m):
    A, B = map(int, input().split())
    if A == 1 or B == 1:
        s.append(A * B)
    elif A == n or B == n:
        g.append(A + B - n)
if len(set(s) & set(g)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


Measured memory_bytes: 21824
// const TOP: u64 = 1_000_000_007;

pub struct Poper<'a> {
	iter: std::str::SplitWhitespace<'a>,
}

impl<'a> Poper<'a> {
	pub fn new(iter: std::str::SplitWhitespace) -> Poper {
		Poper { iter: iter }
	}
	pub fn read<T: std::str::FromStr>(&mut self) -> T
	where
		<T as std::str::FromStr>::Err: std::fmt::Debug,
	{
		self.iter.next().unwrap().parse().unwrap()
	}
}

// use std::collections::BTreeMap;

fn main() {
	let input = {
		use std::io::Read;
		let mut s = String::new();
		std::io::stdin().read_to_string(&mut s).unwrap();
		s
	};
	let mut iter = Poper::new(input.split_whitespace());

	let hs: usize = iter.read();
	let ws: usize = iter.read();

	let mut map: Vec<Vec<bool>> = Vec::new();
	let mut count: Vec<Vec<u64>> = Vec::new();

	for h in 0..hs {
		map.push(Vec::new());
		count.push(Vec::new());
		let line: String = iter.read();
		let chars: Vec<char> = line.chars().collect();
		for w in 0..ws {
			map[h].push('#' == chars[w]);
			count[h].push(0);
		}
	}

	for h in 0..hs {
		let mut cnt: u64 = 0;
		for w in 0..ws {
			if map[h][w] {
				if 0 < cnt {
					for i in 1..(cnt as usize) + 1 {
						count[h][w - i] += cnt;
					}
					cnt = 0;
				}
				continue;
			} else {
				cnt += 1;
			}
		}
		if 0 < cnt {
			for i in 1..(cnt as usize) + 1 {
				count[h][ws - i] += cnt;
			}
		}
	}

	for w in 0..ws {
		let mut cnt: u64 = 0;
		for h in 0..hs {
			if map[h][w] {
				if 0 < cnt {
					for i in 1..(cnt as usize) + 1 {
						count[h - i][w] += cnt;
					}
					cnt = 0;
				}
				continue;
			} else {
				cnt += 1;
			}
		}
		if 0 < cnt {
			for i in 1..(cnt as usize) + 1 {
				count[hs - i][w] += cnt;
			}
		}
	}

	let max: u64 = count
		.into_iter()
		.map(|v| v.into_iter().max().unwrap())
		.max()
		.unwrap();
	if 0 < max {
		println!("{}", max - 1);
	} else {
		println!("{}", 0);
	}
}


Measured memory_bytes: 53496
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

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

	c = b - a;

	d = 0;
	for (int i = 1; i < c + 1; ++i) {
		d += i;
	}

	printf("%d\n", d - b);
}

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

set<string> pq;
vector<string> pq2;
string S;
int K;

int main() {
  cin >> S >> K;
  for(int i=1; i<=min(5, (int)S.size()); i++) {
    for(int j=0; j<S.size()-(i-1); j++) {
      pq.insert(S.substr(j, i));
      /* cout << S.substr(j, i) << endl; */
    }
  }
  for(auto it=pq.begin(); it!=pq.end(); it++) {
    pq2.push_back(*it);
  }
  sort(pq2.begin(), pq2.end());
  cout << pq2[K-1] << endl;
  return 0;
}



Measured memory_bytes: 1920
use std::collections::HashSet;

fn read() -> HashSet<i32> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let set: HashSet<i32> = s
        .trim()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    set
}

fn main() {
    let set = read();
    println!("{}", set.len());
}


Measured memory_bytes: 4352
from collections import defaultdict

D,G=map(int,input().split())

bonus=[]

for i in range(D):
  a,b=map(int,input().split())
  bonus.append([a,b])

def solve(bit):
  ans=0
  turn=0
  for j in range(D):
    if (bit >> j ) % 2:
      ans+=(bonus[j][0] * (j+1) * 100 + bonus[j][1])
      turn+=bonus[j][0]
  if ans >= G:
    return turn
  for k in range(D-1,-1,-1):
    if (bit >> k ) % 2 == 0:
      for l in range(bonus[k][0]-1):
        ans += (k+1)*100
        turn += 1
        if ans >= G:
          return turn
  return -1
        

bits = (1 << D)

res=10**10
for i in range(bits):
  c=solve(i)
  if c > 0:
    res=min(res,c)
  
print(res)

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

class Program
{
    static readonly char _one = '1';
    static readonly char _nine = '9';

    static void Main(string[] args)
    {
        // 1を9に、9を1に変換した配列を、1つの文字列に直して出力します.

        char[] StrArray = Console.ReadLine()
                                .ToList()
                                .Select(x => x == _one ? _nine : (x == _nine ? _one : x))
                                .ToArray();

        Console.Write( string.Join( "", StrArray ) );

#if DEBUG
        Console.ReadLine();
#endif
    }
}

Measured memory_bytes: 13396
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace A
{
    class Program
    {
        public static void Main(string[] args)
        {
            var a = ReadLineStringSplit();
            var c = new char[2];
            var result = "=";

            for (int i = 0; i < a.Length; i++) {
                c[i] = char.Parse(a[i]);
            }


            

            if(c[0] < c[1]) {
                result = "<";
            }else if(c[0] > c[1]) {
                result = ">";
            }

            Console.WriteLine(result);
            ReadLine();
        }

        /// <summary>
        /// stringを一文字ずつintにキャストして配列に変換します。
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public static int[] StringCharArrayIntArray(string str)
        {
            List<int> b = new List<int>();
            for (int i = 0; i < str.Length; i++) {
                b.Add( int.Parse(str[i].ToString()));
            }
            return b.ToArray();
        }

        public static string ReadLine()
        {
            return Console.ReadLine();
        }

        public static int ReadLineInt()
        {
            return int.Parse(Console.ReadLine());
        }

        public static string[] ReadLineStringSplit(char a = ' ')
        {
            return ReadLine().Split(a).ToArray();
        }

        public static int[] ReadLineIntSpilit(char a = ' ')
        {
            return ReadLine().Split(a).Select(x => int.Parse(x)).ToArray();
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main(){
    int N;
    long long A,B;
    cin>>N>>A>>B;
    long long ans=0;
    vector<long long> X(N);
    rep(i,N){
        cin>>X.at(i);
    }
    long long now=X.at(0);
    rep2(i,1,N){
        ans+=min(B,A*(X.at(i)-now));
        now=X.at(i);
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int num, current , before=0, ans=0;
    cin >> num;
    for(int i=0;i<num;i++){
        cin >> current;
        if(current > before){
            ans += current - before;
        }
        before = current;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    a, b = map(int, input().split())
    if a >= 13:
        print(b)
    elif 12 >= a >=6:
        print(b // 2)
    else:
        print(0)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
// AtCoder ABC070 C - Multiple Clocks
// 2020.1.25 bal4u

#include <stdio.h>

typedef long long ll;

ll gcd(ll a, ll b) {
	ll r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

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

int main()
{
	int N; ll T, ans;
	scanf("%d", &N);
	scanf("%lld", &ans);
	while (--N) {
		scanf("%lld", &T);
		ans = lcm(ans, T);
	}
	printf("%lld\n", ans);
	return 0;
}


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

int main(){
	int N;
	cin >> N;
	int ans = 0;
	rep(i, N) {
		int a;
		cin >> a;
		ans += a - 1;
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  if(a>12){
    cout << b << endl;
  }
  else if(a<6){
    cout << 0 << endl;
  }else{
    cout << b/2 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    for( int i=0; i<n; i++){
        cin >> l.at(i);
    }
    vector<int> d(n+1);
    d[0] = 0;
    int ans;
    ans = 0;
    for( int i=1; i<n+1; i++){
        d.at(i) = d.at(i-1) + l.at(i-1);
    }
    //check
    /*for( int i=0; i<n+1; i++){
        cout << d.at(i) << endl;
    }
    return 0;
    */
    for ( int i=0; i<n+1; i++){
        if( d.at(i) <= x){
            ans++;
        }
    }
    cout << ans << endl; 
}



Measured memory_bytes: 256
from collections import Counter
import math
N,A,B = map(int,input().split())
S = input()
a_count = 0
b_count = 0
for i in range(N):
	if S[i] == "a":
		if a_count + b_count > A + B -1:
			print("No")
		else:
			print("Yes")
			a_count += 1
	elif S[i] == "b":
		if A + B >= a_count + b_count + 1 and B >= b_count + 1 :
			print("Yes")
			b_count += 1
		else:
			print("No")
	else:
		print("No")

Measured memory_bytes: 4500
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double D;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef long double ld;

#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d %d",&x,&y)
#define rd3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define rl(x) scanf("%lld",&x)
#define rl2(x,y) scanf("%lld %lld",&x,&y)
#define rl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define wd(x) printf("%d" ,x)
#define wd2(x,y) printf("%d %d",x,y)
#define wl(x) printf("%lld",x)
#define wl2(x,y) printf("%lld %lld",x,y)
#define PC(x) putchar(x)
#define GC() getchar()
#define NL printf("\n")
#define SP printf(" ")
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define F first
#define S second
#define MP make_pair
#define PB push_back


#define L_B lower_bound
#define U_B upper_bound

#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fr(i,s,e) for(int i=s;i<e;i++)
#define frl(i,s,e) for(ll i=s;i<e;i++)
#define frr(i,s,e) for(int i=s-1;i>=e;i--)
#define frv(i,a) for(int i = 0;i<(int)a.size();i++)
#define frvr(i,a) for(int i = a.size()-1;i>=0;i--)
#define tr(i,a) for(typeof(a.begin()) i = a.begin(); i != a.end();i++)

#define inf (1000*1000*1000+5)
#define mod 1000000007
#define maxn 100009
#define maxr 100009
int main(){
	//sstd::ios::sync_with_stdio(false); cin.tie(NULL);
	string a,b;
	cin>>a>>b;
	ll x,y;
	rl2(x,y);
	string t;
	cin>>t;
	if(t==a)
		x--;
	else
		y--;
	cout<<x<<" "<<y<<endl;
	return 0;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double n;
    cin >> n;
    REP(x,50001){
        if(floor((double)x * 1.08) == n){
            cout << x << endl;
            return 0;
        }
    }
    cout << ":(\n";
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int i = 0, count[26] = {};
	char ch;
		
	while(scanf("%c",&ch) != EOF)
	{
		if(ch >= 'a'&& ch <= 'z')
		{
			i = ch - 'a';
			count[i]++;	
		}		
		else if(ch >= 'A' && ch <= 'Z')
		{
			i = ch - 'A';
			count[i]++;
		}
	}
	
	ch = 'a';
	for(i = 0;i < 26;i++)
	{
		printf("%c : %d\n",ch,count[i]);
	ch++;
	}
return 0;
}


Measured memory_bytes: 2128
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int main() {
    int N;
    string S;
    cin >> N >> S;
    int length = S.length();
    if(length % 2 == 1) {
        cout << "No" << endl;
    } else {
        bool flag = true;
        REP(i, length/2) {
            if(S[i] != S[length/2 + i]) {
                flag = false;
                break;
            }
        }
        if(flag) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    ll n;
    ll a;
    ll m = INF;

    cin >> n;

    for (int i = 0; i < 5; i++)
    {
        cin >> a;
        m = min(m, a);
    }

    cout << (n + m - 1) / m + 4 << endl;
}

Measured memory_bytes: 256
#include <ctype.h>
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <signal.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

//char rbuf[]; int rbufl;
//#define getchar() rbuf[rbufl++]
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }
void printint(int32_t x){ if(x<0){x=-x; putchar('-');}else if(x==0){putchar('0');} int d=0; char s[10]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putchar(s[i]); putchar('\n'); }
void rsorta_d32(void *base, const int count, const int size, const int index){
	typedef int32_t rsort_t;
	rsort_t (*a)[size] = (rsort_t(*)[size])base;
	rsort_t (*b)[size] = (rsort_t(*)[size])malloc(count*size*sizeof(rsort_t));
	int c[0x100];
	for(int k=0; k<4; k++){
		memset(c, 0, sizeof(c)); for(int i=0; i<count; i++){ c[(a[i][index]>>(k<<3))&0xFF]++; } for(int i=1; i<0x100; i++) c[i]+=c[i-1]; for(int i=count-1; i>=0; i--){ int to=--c[(a[i][index]>>(k<<3))&0xFF]; for(int j=0; j<size; j++){ b[to][j]=a[i][j]; } }{rsort_t(*t)[size]=a; a=b; b=t;}
	}
	free(b);
}

#define P 998244353

int dat[1048577];
int d[10][2];

void update(int k, int x){
	k+=524288-1;
	dat[k]=(dat[k]+x)%P;
	while(k>0){
		k=(k-1)/2;
		dat[k]=(dat[k]+x)%P;
	}
}

// q(a, b, 0, 0, m)
// [a, b)
int query(int a, int b, int k, int l, int r){
	if(r<=a || b<=l) return 0;
	if(a<=l && r<=b) return dat[k];
	int m=(l+r)/2;
	int vl = query(a, b, k*2+1, l, m);
	int vr = query(a, b, k*2+2, m, r);
	return (vl+vr)%P;
}

inline int q(int l, int r){
	return query(l, r, 0, 0, 524288);
}

int main(void){
	int n=nextint();
	int k=nextint();
	for(int i=0; i<k; i++){
		d[i][0]=nextint();
		d[i][1]=nextint();
	}
	update(n, 1);
	for(int i=n-1; i>0; i--){
		long A=0;
		for(int j=0; j<k; j++){
			A += q(i+d[j][0], i+d[j][1]+1);
		}
		A%=P;
		update(i, A);
	}
	int ans = q(1, 2);
	printf("%d\n", ans);
}


Measured memory_bytes: 3204
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

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

  ll N,ans = 0; cin >> N;
  vector<ll> vec(N);
  for (ll i = 0; i < N; ++i) cin >> vec[i];
  sort(vec.begin(),vec.end());
  ll lhalf = vec[N/2 -1];
  ll rhalf = vec[N/2];
  for (ll i = lhalf+1; i <= rhalf; ++i) ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e09;

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

  string s;
  cin >> s;

  REP(i, 3){
    if(s[i] == '1') cout << 9;
    else if(s[i] == '9') cout << 1;
    else cout << s[i];
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
/*
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*    ▀▀       ▀▀▀▀▀▀    ▀     ▀▀▀▀▀▀      ▀    ▀
*   ▀  ▀      ▀         ▀     ▀            ▀  ▀
*  ▀    ▀     ▀ ▀ ▀     ▀     ▀ ▀ ▀         ▀
* ▀ ▀▀▀▀ ▀    ▀         ▀     ▀             ▀
*▀        ▀   ▀         ▀     ▀             ▀
*▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
*/
using namespace std;
void afify()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
#define ll long long
#define ld long double
#define mk make_pair
#define loop(i,intial,n)  for(int i=int(intial);i<n;i++)
#define loopn(j,n) for(int j=int(n);j>=0;j--)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(v) v.begin(),v.end()
///////////////////////////////////////
#define SCD(a) scanf("%d",&a)
#define SCD2(a,b) scanf("%d %d",&a,&b)
#define SCLL(a) scanf("%lld",&a)
#define SCLL2(a,b) scanf("%lld %lld",&a,&b)
#define PRD(a) printf("%d\n",a)
#define PRLL(a) printf("%lld\n",a)
///////////////////////////////////////
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vi> vvi;
typedef vector <vll> vvll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<vpii> vvpii;
typedef stringstream ss;
const ll oo = (ll) 10e9+7;
const double EPS = 1e-4;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
//ifstream ifs("input.txt");
//ofstream ofs("output.txt");

int main()
{
   afify();
   int arr1[100];
   arr1[1]=1;arr1[3]=1,arr1[5]=1;arr1[7]=1;arr1[10]=1;arr1[12]=1;arr1[8]=1;
   int arr2[100];
   arr2[4]=1;arr2[6]=1;arr2[9]=1;arr2[11]=1;
   int x,y;
   cin>>x>>y;
   if(arr1[x]==1 && arr1[y]==1){cout<<"Yes"<<endl;}
   else if(arr2[x]==1 && arr2[y]==1){cout<<"Yes"<<endl;}
   else {cout<<"No"<<endl;}

	return 0; 
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
acc = [0]
ans = 0
for i in a:
    acc.append(acc[-1]+i)
acc = acc[1:]
for i, v in enumerate(a):
    ans += (v*(acc[-1]-acc[i]))%MOD
print(ans%MOD)

Measured memory_bytes: 103528
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> g(N);
    vector<int> A(N), B(N);
    REP(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].pb(b);
        g[b].pb(a);
        A[i] = a, B[i] = b;
    }

    auto dfs = [&](auto f, int v, int p, int d, int k) -> int {
        int ret = 0;
        if (d > k) ret++;
        FORE(w, g[v]) {
            if (w == p) continue;
            ret += f(f, w, v, d + 1, k);
        }
        return ret;
    };
    
    int ans = INF;
    if (K % 2) {
        REP(i, N - 1) {
            int a = A[i], b = B[i];
            int tmp = dfs(dfs, a, b, 0, (K - 1) / 2) + dfs(dfs, b, a, 0, (K - 1) / 2);
            chmin(ans, tmp);
        }
    } else {
        REP(v, N) {
            int tmp = dfs(dfs, v, -1, 0, K / 2);
            chmin(ans, tmp);
        }
    }
    cout << ans << endl;
    return (0^_^0);
}



Measured memory_bytes: 512
#include <iostream>
#include <queue>
#define INF 2000000000
#define N 30
using namespace std;
void bfs();
int w,h,data[N][N][4];//0:left,1:up,2:right,3:down
int main(){
  int l,in;
  while(1){
    cin >> w >> h;
    if(w==0&&h==0) break;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	for(int k=0;k<4;k++){
	  data[i][j][k]=1;
	}
      }
    }
    for(int i=0,l=0;i<2*h-1;i++){
      if(i%2==0){
	for(int j=0;j<w-1;j++){
	  cin >> in;
	  if(in==0) data[l][j][2]=data[l][j+1][0]=0;
	}
      }else{
	for(int j=0;j<w;j++){
	  cin >> in;
	  if(in==0) data[l][j][3]=data[l+1][j][1]=0;
	}
	l++;
      }
    }
    bfs();
  }
  return 0;
}
void bfs(){
  int d[h][w];
  queue<pair<int,int> > Q;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      d[i][j]=INF;
    }
  }
  d[0][0]=1;
  Q.push(make_pair(0,0));
  while(!Q.empty()){
    pair<int,int> u=Q.front();
    Q.pop();
    if(data[u.first][u.second][0]==0){
      if(d[u.first][u.second-1]>d[u.first][u.second]+1){
	d[u.first][u.second-1]=d[u.first][u.second]+1;
	Q.push(make_pair(u.first,u.second-1));
      }
    }
    if(data[u.first][u.second][1]==0){
      if(d[u.first-1][u.second]>d[u.first][u.second]+1){
	d[u.first-1][u.second]=d[u.first][u.second]+1;
	Q.push(make_pair(u.first-1,u.second));
      }
    }
    if(data[u.first][u.second][2]==0){
      if(d[u.first][u.second+1]>d[u.first][u.second]+1){
	d[u.first][u.second+1]=d[u.first][u.second]+1;
	Q.push(make_pair(u.first,u.second+1));
      }
    }
    if(data[u.first][u.second][3]==0){
      if(d[u.first+1][u.second]>d[u.first][u.second]+1){
	d[u.first+1][u.second]=d[u.first][u.second]+1;
	Q.push(make_pair(u.first+1,u.second));
      }
    }
  }
  if(d[h-1][w-1]!=INF) cout << d[h-1][w-1] << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr ll INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    priority_queue<int, vector<int>, greater<int> > Q,P;
    int N;cin >> N;
    int A[N];
    REP(i,N){
        cin >> A[i];
        if(i % 2 == 0) Q.push(A[i]);
        else P.push(A[i]);
    }
    int cnt = 0,X,Y;
    bool flag = 0;
    vector<int> ans;
    while(!P.empty() || !Q.empty()){
        if(!Q.empty()) X = Q.top();//偶数番目
        else X = INF;
        if(!P.empty()) Y = P.top();//奇数番目
        else Y = INF;

        if(ans.size() % 2 == 0 && X < Y){
            ans.pb(X);
            Q.pop();
        }
        else if(ans.size() % 2 == 0 && X > Y){
            if(flag){
                cnt++;
                flag = 0;
            }
            else flag = 1;
            ans.pb(Y);
            P.pop();
        }
        else if(ans.size() % 2 == 1 && X > Y){
            ans.pb(Y);
            P.pop();
        }
        else if(ans.size() % 2 == 1 && X < Y){
            if(flag){
                cnt++;
                flag = 0;
            }
            else flag = 1;
            ans.pb(X);
            Q.pop();
        }
    }
    cout << cnt << endl;
}


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

int main(void){
    //文字列SとTに値を代入する
    char S[200001];
    char T[200001];
    memset(&S,'\0',sizeof(S));
    memset(&T,'\0',sizeof(T));
    scanf("%s",S);
    scanf("%s",T);
    
    //文字列Sの長さをsizeに代入する
    int size = strlen(S);

    //アルファベットの箱を用意し、初期化する
    char alpha[26];
    memset(&alpha,'\0',sizeof(alpha));

    //TとSの関係を確認する
    for(int i = 0;i<size;i++){
        //アルファベットT[i]の中身が\0の場合、S[i]を代入する
        if(alpha[T[i] - 'a'] == '\0'){
            alpha[T[i] - 'a'] = S[i];
        //アルファベットT[i]の中身がS[i]でない場合、Noを出力しプログラムを終了させる
        }else if(alpha[T[i] - 'a'] != S[i]){
            printf("No\n");
            return 0;
        }
    }
    
    //重複チェックのフラグを用意する
    int flag = 0;

    //アルファベットの箱の中身に、重複したアルファベットがないかチェックする
    for(int i = 0;i<26;i++){
        for(int j = 0;j<26;j++){
            //アルファベットをa-zまで順繰りに調べていき、
            //アルファベットの箱の中身に一致したものがある場合、flagを加算する
            if(alpha[j] == 'z' - i){
                flag++;
            }
        }
        //アルファベットに2つ以上重複したものがある場合、Noを出力しプログラムを終了させる
        if(flag > 1){
            printf("No\n");
            return 0;
        }
        //重複がなかった場合フラグをリセットする
        flag = 0;
    }
    
    //途中でNoが出なかった場合Yesを出力する
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int count=-1;
  int endflag;
  vector<int> vec(N);
for (int i = 0; i < N; i++) {
  cin >> vec.at(i);
}
  while(endflag ==0){
  for(int i = 0;i<N;i++){
    if(vec.at(i)%2 ==0){
      vec.at(i) /= 2;
    }else{
    endflag++;
    }
  }
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
k, n = map(int, input().split())
a = list(map(int, input().split()))

max_val = 0

for i in range(n):
    lg = 0
    if i == 0:
        lg = int(a[i] + (k - a[n-1]))
    else:
        lg = int(a[i] - a[i-1])

    if lg > max_val:
        max_val = lg
print(k - max_val)

Measured memory_bytes: 26444
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    int n; cin >> n;
    rep(i,n) {
        int x, y, b, p; cin >> x >> y >> b >> p;
        int ans = x*b + y*p;
        for(int i = b; i < b+6; i++) {
            for(int j = p; j < p+3; j++) {
                int price=INF;
                if(i>=5 && j>=2) {
                    price = (x*i+y*j)*0.8;
                }
                ans = min(ans,price);
            }
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3128
n = int(input())
ab = [[int(i) for i in input().split()] for _ in range(n)]
ans = 0
for i in range(n)[::-1]:
    if (ab[i][0]+ans)%ab[i][1]==0:
        y = 0
    else:
        y = ab[i][1] - ((ab[i][0]+ans)%ab[i][1])
    ans += y
print(ans)

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

namespace _0138
{
    public class Program

    {
        public static void Main(string[] args)
        {
            SortedList<int, double> set1 = new SortedList<int, double>(8);
            SortedList<int, double> set2 = new SortedList<int, double>(8);
            SortedList<int, double> set3 = new SortedList<int, double>(8);
            SortedList<int, double> setAll = new SortedList<int, double>(24);

            for (int i = 0 ; i < 24 ; i++)
            {
                double[] numAndTime = RDoubleAr();
                setAll.Add((int)numAndTime[0], numAndTime[1]);
                if (i < 8) set1.Add((int)numAndTime[0], numAndTime[1]);
                else if (i < 16) set2.Add((int)numAndTime[0], numAndTime[1]);
                else set3.Add((int)numAndTime[0], numAndTime[1]);
            }

            int cnt = 0;
            foreach (var item in set1.OrderBy(x => x.Value))
            {
                cnt++;
                Console.WriteLine("{0} {1}", item.Key, item.Value.ToString("0.00"));
                setAll.Remove(item.Key);
                if (cnt == 2) break;
            }
            cnt = 0;
            foreach (var item in set2.OrderBy(x => x.Value))
            {
                cnt++;
                Console.WriteLine("{0} {1}", item.Key, item.Value.ToString("0.00"));
                setAll.Remove(item.Key);
                if (cnt == 2) break;
            }
            cnt = 0;
            foreach (var item in set3.OrderBy(x => x.Value))
            {
                cnt++;
                Console.WriteLine("{0} {1}", item.Key, item.Value.ToString("0.00"));
                setAll.Remove(item.Key);
                if (cnt == 2) break;
            }
            cnt = 0;
            foreach (var item in setAll.OrderBy(x => x.Value))
            {
                cnt++;
                Console.WriteLine("{0} {1}", item.Key, item.Value.ToString("0.00"));
                if (cnt == 2) break;
            }
        }

        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RStAr(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }

}



Measured memory_bytes: 14908
import numpy as np

N = int(input())
a = list(map(int,input().split()))

a = np.array(a)




def make_Xor(a,b):
	d_ = []
	for i in range(len(a)):
		if a[i] == b[i]:
			d_.append("0")
		else:
			d_.append("1")
	return d_


def judge_of_3(a):
	a_ = []
	a_.append(list(format(a[0],'b')))
	a_.append(list(format(a[1],'b')))
	a_.append(list(format(a[2],'b')))
	max_len = max(len(a_[0]),len(a_[1]),len(a_[2]))
	for i in range(3):
		while len(a_[i]) < max_len:
			a_[i].insert(0,'0')
	if make_Xor(a_[0],a_[1]) == a_[2]:
		return True
	else:
		return False
	
	
judge = True

if N % 3 == 0:
	a_1 = np.unique(a)
	if len(a_1) <= 3:
		a = list(a)
		a.sort()
		div_3 = N // 3
		for i in range(3):
			if a[i * div_3] != a[(i+1) * div_3 - 1]:
				judge = False
		a_1 = [a[0],a[div_3],a[2*div_3]]
		if judge:
			if judge_of_3(a_1):
				judge = True
			else:
				judge = False
	else:
		judge = False
else:
	a_1 = np.unique(a)
	a_1 = list(a_1)
	if len(a_1) != 1:
		judge = False
	if a_1[0] != 0:
		judge = False

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


Measured memory_bytes: 23892
A, B, C, D = map(int, input().split())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd (a, b)

C_ok = (B // C) - ((A-1) // C) 
D_ok = (B // D) - ((A-1) // D)
C_D_ok = (B // lcm(C, D)) - ((A-1) // lcm(C, D))
print((B-A+1)-C_ok-D_ok+C_D_ok)


Measured memory_bytes: 38256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;
using namespace std;
using ll=long long;
#define double long double
using datas=pair<ll,ll>;
using ddatas=pair<double,double>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
// using llset=tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
#define For(i,a,b) for(i=a;i<(ll)b;i++)
#define bFor(i,a,b) for(i=a;i>=(ll)b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define print(v) cout<<v<<endl
#define printyes cout<<"Yes"<<endl
#define printno cout<<"No"<<endl
#define printYES cout<<"YES"<<endl
#define printNO cout<<"NO"<<endl
#define output(v) do{bool f=0;for(auto outi:v){cout<<(f?" ":"")<<outi;f=1;}cout<<endl;}while(0)
const ll mod=1000000007;
const ll inf=1LL<<60;
const double PI = acos(-1);
const double eps = 1e-9;
template<class T> inline bool chmax(T& a,T b){bool x=a<b;if(x)a=b;return x;} 
template<class T> inline bool chmin(T& a,T b){bool x=a>b;if(x)a=b;return x;} 

void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
}

double distance(ddatas x,ddatas y){
  double a=x.first-y.first,b=x.second-y.second;
  return sqrt(a*a+b*b);
}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

vec modncrlistp,modncrlistm;

ll modncr(ll n,ll r){
  ll i,size=modncrlistp.size();
  if(size<=n){
    modncrlistp.resize(n+1);
    modncrlistm.resize(n+1);
    if(!size){
      modncrlistp[0]=modncrlistm[0]=1;
      size++;
    }
    For(i,size,n+1){
      modncrlistp[i]=modncrlistp[i-1]*i%mod;
      modncrlistm[i]=modinv(modncrlistp[i]);
    }
  }
  return modncrlistp[n]*modncrlistm[r]%mod*modncrlistm[n-r]%mod;
}

ll modpow(ll a,ll n){
  ll res=1;
  while(n){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll gcd(ll a,ll b){if(!b)return a;return (a%b==0)?b:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

int main(){
  startupcpp();
  // ll test;cin>>test;while(test--){
  ll i,j,N,A,B,ans=0;
  cin>>A>>B;
  rep(i,10000){
    if(i*8/100==A&&i/10==B)break;
  }
  if(i==10000)print(-1);
  else print(i);
}

Measured memory_bytes: 256
/*Bismillahir Rahmanir Rahim
->>Code by Aimon
->>CUET,CSE
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define f(a,b,x) for(int a=b;a<x;a++)
#define pb push_back
#define endl "\n"
#define MX INT_MAX
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define vi vector<int>

int main()
{
    int a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
    if(a==0)
        cout<<1<<endl;
    else if(b==0)
        cout<<2<<endl;
    else if(c==0)
        cout<<3<<endl;
    else if(d==0)
        cout<<4<<endl;
    else if(e==0)
        cout<<5<<endl;
}


Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int i = 1;
    int max_number = i;
    while (1)
    {
        if(i * i <= n)
        {
            max_number = i * i;
        }else{
            break;
        }
        i++;
    }
    cout << max_number << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define rep(i,n) for(int i=0;i<n;i++) 
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main() {
    //ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    ll sum=0;
    rep(i,N){
        cin >> A[i];
        sum+=A[i];
    }
    vector<ll> r(N);
    vector<ll> sr(N);
    vector<ll> div=divisor(sum);
    reverse(all(div));
    rep(i,div.size()){
        ll d=div[i];
        rep(j,N){
            r[j]=A[j]%d;
        }
        sort(all(r));
        sr[0]=r[0];
        for(int j=1;j<N;j++){
            sr[j]=sr[j-1]+r[j];
        }
        bool b=false;
        rep(j,N){
            if(sr[j]<=K && sr[j]-sr[N-1]+(N-j-1)*d<=K){
                b=true;
                break;
            }
        }
        if(b){
            cout << d;
            break;
        }
    }


}

/*



 */



Measured memory_bytes: 256
package main

import "fmt"

func min(a int, b int) int {
	if a <= b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	h := make([]int, n+k)
	dp := make([]int, n+k)

	for i := 0; i < n; i++ {
		fmt.Scan(&h[i])
	}

	for i := 1; i < n; i++ {
		dp[i] = 10000000000
	}

	for i := 0; i < n-1; i++ {
		for j := 1; j < k+1; j++ {
			dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
		}
	}

	fmt.Println(dp[n-1])
}


Measured memory_bytes: 5504
n, y = map(int, input().split())
for i in range(n+1):
    for j in range(n+1-i):
        if 10000*i + 5000*j + 1000*(n-i-j) == y:
            print(i, j, n-i-j)
            exit()
print('-1 -1 -1')

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using namespace std;

int main() {
    fastIO;
    string s;
    cin >> s;
    for (size_t i = 0; i < s.size() - 1; i++) {
        if (s.at(i) == s.at(i + 1)) {
            cout << "Bad";
            return 0;
        }
    }
    cout << "Good";
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<cstdlib>

using namespace std;

int main(){
	
	int n;
	int m;
	long int a[100];
	long int b[100];
	long int c[100];
	long int d[100];
	int i,j;
	long int min;
	int ans;
	
	cin>>n;
	cin>>m;
	
	for(i=1;i<=n;i++){
		cin>>a[i];
		cin>>b[i];
	}
	
	for(j=1;j<=m;j++){
		cin>>c[j];
		cin>>d[j];
	}

	for(i=1;i<=n;i++){
		min=999999999;
		ans=0;
		for(j=1;j<=m;j++){
			if(abs(a[i]-c[j])+abs(b[i]-d[j])<min){
				ans=j;
				min=abs(a[i]-c[j])+abs(b[i]-d[j]);
			}
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T, class U> void chmax(T& a, U b) { if (a < b) a = b; }
const int MAX_N = 110;
const int MAX_W = 11000;
const int INF = 1e9;

int main() {
    int n, w;
    cin >> n >> w;
    long long dp[MAX_W] = {0};
    vector<int> val(n), wei(n);
    for (int i = 0; i < n; i++) cin >> val[i] >> wei[i];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < MAX_W; j++) {
            if (j + wei[i] < MAX_W) chmax(dp[j+wei[i]], dp[j] + val[i]);
        }
    }
    
    cout << dp[w] << endl;
    return 0;
}


Measured memory_bytes: 3196
# https://atcoder.jp/contests/abc134/tasks/abc134_e

import bisect

N = int(input())
A = []
for _ in range(N):
    a = int(input())
    A.append(a)

A.reverse()
INF = float('inf')
dp = [INF for _ in range(N)]

for a in A:
    target_index = bisect.bisect_right(dp, a)
    # print(a, target_index)
    dp[target_index] = a

# print(dp)
print(bisect.bisect_left(dp, INF))


Measured memory_bytes: 58712
#include <iostream>
#include <string>

using namespace std;

int main() {
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  for (int i = 0; i < n; i++) {
    cout << s[i] << t[i];
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256