akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<queue>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

typedef long long ll;
const ll INF = 1e17;
const int BIG = 1000000007;




int main() {

	string s;
	cin >> s;
	int n = s.size();

	int mod[200000][13] = {};//上n桁を13で割った余りの場合の数

	mod[0][0] = 1;

	char t;

	for (int i = 1; i <= n; i++) {
		t = s[i - 1];

		

		if (t != '?') {

			t = t - 48;
			for (int j = 0; j < 13; j++) {
				mod[i][((10 * j) + t) % 13] = mod[i - 1][j];
			}
		}

		else {
			for (int j = 0; j < 13; j++) {
				for (int k = 0; k < 10; k++) {
					mod[i][((10 * j) + k) % 13] += mod[i - 1][j];
					mod[i][((10 * j) + k) % 13] %= BIG;
				}
			}

		}

		
	}

	cout << mod[n][5];

	system("PAUSE");

}


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

int n;
int ans;
void dfs(int x, int depth) {
    if(depth == 0) {
        if(x <= n) {
            map<int, bool> mp;
            while (x) {
                for (int i = 3; i < 8; i+=2) {
                    if(x%10 == i) {
                        mp[i] = 1;
                        break;
                    }
                }
                x /= 10;
            }
            int cnt = 0;
            for (auto p : mp) {
                cnt += p.second;
            }
            if(cnt == 3) {
                ans++;
            }
        }
        return;
    }

    x *= 10;
    for (int i = 3; i < 8; i += 2) {
        dfs(x + i, depth - 1);
    }
}
void solve () {
    cin >> n;
    string s = to_string(n);
    int sz = (int) s.size();
    for (int j = 2; j < sz; j++) {
        for (int i = 3; i < 8; i+= 2) {
           dfs(i, j);
        }
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3660
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int[] a = new int[3];
		for (int i = 0; i < 3; i++) {
			a[i] = stdIn.nextInt();
		}
		
		Arrays.sort(a);
		
		System.out.println(a[0] + " " + a[1] + " " + a[2]);
		
	}
}

Measured memory_bytes: 17304
import sys
import numpy as np 

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n = I[0]
t = I[1:1+n]
m = I[1+n]
p, x = I[2+n:].reshape(m, 2).T 

def main():
    default = np.sum(t)
    res = default + (x - t[p-1])
    return res

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
const int N = 105, K = 100005, MOD = 1000000007;
int n, k, dp[N][K], a[N];
int getsum(int idx, int l, int r)
{
	int ans = dp[idx][r];
	if (l)
		ans = (1LL * ans - dp[idx][l - 1] + MOD) % MOD;
	return ans;
}
int main(int argc, char const *argv[])
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	dp[0][k] = 1;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j < K; ++j)
		{
			dp[i - 1][j] = (1LL * dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
		}
		for (int j = 0; j <= k; ++j)
		{
			dp[i][j] = getsum(i - 1, j, min(j + a[i], k));
		}
	}
	cout << dp[n][0];
	return 0;
}

Measured memory_bytes: 41216
macro_rules! check {
    ($b:expr) => {
        if !$b {
            println!("-1");
            return;
        }
    };
}

const ALL1: u64 = u64::max_value();

fn main() {
    proconio::input! {
        n: usize,
        s: [u8; n],
        t: [u8; n],
        u: [u64; n],
        v: [u64; n],
    }
    let s: Vec<_> = s.iter().map(|&i| i == 1).collect();
    let t: Vec<_> = t.iter().map(|&i| i == 1).collect();
    let mut mat = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            mat[i][j] = u[i] & v[j];
            if !s[i] {
                mat[i][j] |= u[i];
            }
            if !t[j] {
                mat[i][j] |= v[j];
            }
            check!(!s[i] || mat[i][j] & !u[i] == 0);
            check!(!t[j] || mat[i][j] & !v[j] == 0);
        }
    }
    for i in 0..n {
        check!(s[i] || mat[i].iter().fold(ALL1, |a, &b| a & b) & !u[i] == 0);
    }
    for j in 0..n {
        check!(t[j] || (0..n).map(|i| mat[i][j]).fold(ALL1, |a, b| a & b) & !v[j] == 0)
    }
    for i in 0..n {
        if !s[i] {
            continue;
        }
        let mut ok = !u[i] | (0..n).map(|j| mat[i][j]).fold(0, |a, b| a | b);
        for j in 0..n {
            if t[j] {
                continue;
            }
            mat[i][j] |= !v[j] & !ok;
            mat[i][j] &= v[j] | !(0..n).map(|i| mat[i][j]).fold(ALL1, |a, b| a & b);
            ok |= mat[i][j];
        }
        check!(ok == ALL1)
    }
    for j in 0..n {
        if !t[j] {
            continue;
        }
        let mut ok = !v[j] | (0..n).map(|i| mat[i][j]).fold(0, |a, b| a | b);
        for i in 0..n {
            if s[i] {
                continue;
            }
            mat[i][j] |= !u[i] & !ok;
            mat[i][j] &= u[i] | !(0..n).map(|j| mat[i][j]).fold(ALL1, |a, b| a & b);
            ok |= mat[i][j];
        }
        check!(ok == ALL1)
    }
    for i in 0..n {
        println!(
            "{}",
            mat[i]
                .iter()
                .map(|&x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    }
}


Measured memory_bytes: 7564
#pragma region

#ifdef LOCAL
#define debug cout
#else
#define debug \
    if (0) cout
#endif

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using ll = long long;

template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[ ";
    for (auto e : v) os << e << " ";
    return os << "]";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, set<T, V> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V, typename S>
ostream& operator<<(ostream& os, map<T, V, S> v) {
    os << "{ ";
    for (auto e : v) os << e << " ";
    return os << "}";
}

template <typename T, typename V>
ostream& operator<<(ostream& os, pair<T, V> x) {
    return os << "( " << x.first << ", " << x.second << " )";
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}

template <typename T, typename V>
istream& operator>>(istream& is, pair<T, V>& x) {
    return is >> x.first >> x.second;
}

void solve();

int main() {
#ifdef LOCAL
    freopen("data.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
}

#pragma endregion

void solve() {
    int n;
    cin >> n;
    vector<int> h(n);
    cin >> h;
    vector<int> dp(n);
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < n; ++i) dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
    cout << dp[n - 1] << "\n";
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
#include <iomanip>
using namespace std;
 
#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ans=0;llfor;///////////////////////////////////////////////////////////
int digit(int n){
   if(n < 10)  return n;
   return digit(n/10) + n%10;
}
int main(){
  int A,B,C;
  cin>>A>>B>>C;
  int i=0;
  while(A>=B){
    i++;
    B*=2;
  }
  while(B>=C){
    i++;
    C*=2;
  }
  int K;
  cin>>K;
  
  if(i<=K) cout<<"Yes";
  else cout<<"No";
  
return 0;}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    int a, b, m;
    cin >> a >> b >> m;
    vi ap(a), bp(b);
    vector<tuple<int, int, int>> mp(m);
    int mina = 1001001001, minb = 1001001001;
    rep(i, a) {
        cin >> ap[i];
        if (ap[i] < mina) mina = ap[i];
    }
    rep(i, b) {
        cin >> bp[i];
        if (bp[i] < minb) minb = bp[i];
    }
    rep(i, m) {
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        mp[i] = make_tuple(x, y, c);
    }
    int minc = 1001001001;
    rep(i, m) {
        int sum = ap[get<0>(mp[i])] + bp[get<1>(mp[i])] - get<2>(mp[i]);
        if (sum < minc) minc = sum;
    }
    int ans = min(minc, mina + minb);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 2176
#include <stdio.h>
 
int main() {
 
  int a,N,i,j,A[100],count;
 
  while(1) {
    scanf("%d",&N);
    if(N<1 || 100<N) printf("error\n");
    else break;
  }
 
  while(1) {
    count = 0;
    for(i=0; i<N; i++) scanf("%d",&A[i]);
    for(i=0; i<N; i++) if(A[i]<0 || 100<A[i]) count++;
    if(count==0) break;
    else printf("error\n");
  }
 
  for(i=0; i<N-1; i++) {
    for(j=N-1; j>=0; j--) {
      if(A[j] < A[j-1]) {
        a = A[j];
        A[j] = A[j-1];
        A[j-1] = a;
        count++;
      }
    }
  }
 
  for(i=0; i<N; i++) {
    printf("%d",A[i]);
    if(i!=N-1) printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
 
  return 0;
}

Measured memory_bytes: 604
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	int answer = 0;
	for(int i = 0; i < n; ){
		int j = i;
		while(j < n && a[i] == a[j]){ ++j; }
		const int k = j;
		while(j < n && (a[j] == a[j - 1] || (a[i] > a[k]) == (a[j - 1] > a[j]))){
			++j;
		}
		i = j;
		++answer;
	}
	cout << answer << endl;
	return 0;
}



Measured memory_bytes: 640
N=int(input())
A=list(map(int,input().split()))

ans=1
tmp=-1
#単調増加:1 単調非増加:0
chk=-1
flag=True
for i in range(N):
    if i==0:
        tmp=A[0]
        continue
    if flag:
        if A[i]>tmp:
            tmp=A[i]
            chk=1
            flag=False
        elif A[i]<tmp:
            tmp=A[i]
            chk=0
            flag=False
        else:
            tmp=A[i]
        continue
    if chk:
        if tmp<A[i]:
            tmp=A[i]
        elif tmp>A[i]:
            ans+=1
            flag=True
            chk=-1
            tmp=A[i]
    else:
        if tmp<A[i]:
            ans+=1
            flag=True
            chk=-1
            tmp=A[i]
        else:
            tmp=A[i]
        
print(ans)

Measured memory_bytes: 62704
from collections import defaultdict
N,K=map(int,input().strip().split())
A=[0]+list(map(int,input().strip().split()))

G=defaultdict(list)
prev=1

visited=set()
visited.add(1)

next=A[1]
while(not next in visited):
    G[prev].append(next)
    prev=next
    visited.add(next)
    next=A[next]
G[prev].append(next)
#loop starts from next
#calculate length = number of nodes in loop from next to prev

origin=next
next=G[origin][0]
cnt=0 ##length of loop
while(next!=origin):
    cnt+=1
    next=G[next][0]
##get Distance require to travel from town 1 to origin.
cnt+=1
origin1=1
next=G[1][0]
dist=0
while(next!=origin):
    dist+=1
    next=G[next][0]
dist+=1
if K<dist:
    cnt =0
    origin=1
    next=origin
    while(cnt!=K):
        cnt+=1
        next=G[next][0]
    print(next)
else:
    K=K-dist
    N=K%cnt
#travel N nodes from origin i.e start of the loop
    cnt=0
    next=origin
    while(cnt!=N):
        cnt+=1
        next=G[next][0]
    print(next)

Measured memory_bytes: 60244
#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
	int a,b,ans;
	cin >> a >> b;
  if (a == b) {
    ans = 0;
    cout << ans << endl;
  } else if ((a + b) % 2 == 0) {
    ans = (a + b) /2;
    cout << ans << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

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

typedef long long ll;
 
using tpl = tuple<int, int, int>;
typedef pair<double,int> pii;

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

int N;
int X[1010];
int Y[1010];
int R[1010];

double costs[1010][1010];
double d[1010];

double dist(int p1, int p2){
    return sqrt(pow(1.0 * X[p1] - X[p2], 2) + pow(1.0 * Y[p1] - Y[p2], 2));
}

int main(){

    for(int i = 0; i < 2; i++){
        cin >> X[i] >> Y[i];
        R[i] = 0;
    }
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> X[i + 2] >> Y[i + 2] >> R[i + 2];
    }
    N += 2;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            // 円と円の距離を計算する
            double tmp = dist(i, j);
            costs[i][j] = max(0.0, tmp - (R[i] + R[j]));
        }
    }
    for(int i = 0; i < N; i++)
        d[i] = 1e+17;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push(pii(0.0, 0));
    d[0] = 0;
    while(pq.size()){
        pii p = pq.top(); pq.pop();
        double ccost = p.first;
        int cpos = p.second;
        if(d[cpos] < ccost) continue;
        for(int i = 0; i < N; i++){
            double ncost = ccost + costs[cpos][i];
            int npos = i;
            if(d[npos] > ncost){
                d[npos] = ncost;
                pq.push(pii(ncost, npos));
            }
        }
    }

    printf("%.10f\n", d[1]);

    return 0;
}


Measured memory_bytes: 13808
#from random import randint

def f(h,w,m,ins):
    yp = [0]*h
    xp = [0]*w
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1] += 1
        xp[wi-1] += 1
    ypm = max(yp)
    xpm = max(xp)
    yps = [i for i in range(h) if yp[i] == ypm]
    xps = [i for i in range(w) if xp[i] == xpm]
    ans = ypm+xpm
    for ypsi in yps:
        for xpsi in xps:
            if not (ypsi,xpsi) in s:
                return ans
    return ans-1

if __name__ == "__main__":
    if False:
        while True:
            h,w = randint(1,10**5*3),randint(10**5,10**5*3)
            m = randint(1,min(h*w,10**5*3))
            ins = [(randint(1,h),randint(1,w)) for i in range(m)]
            ans = f(h,w,m,ins)
            print(ans)
    else:
        h,w,m = map(int,input().split())
        ans = f(h,w,m,[list(map(int,input().split())) for i in range(m)])
        print(ans)


Measured memory_bytes: 138456
#include<stdio.h>

int main()
{
	int a;
	int b;
	int c;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(c>=a && c<=b)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
		
	return 0;
}

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

int main(void) {
	int a, b ,c;
	cin >> a >> b >> c;
	int sum = a + b + c;
	int maxN = max(a, max(b, c));
	int ans = -1;
	if (sum % 2 == 3*maxN % 2) {
		ans = (3*maxN - sum) / 2;
	} else {
		ans = (3*(maxN + 1) - sum) / 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
  public static void Main(string[] args)
  {
    int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
    if ((s[0] * s[1]) % 2 == 0) Console.WriteLine("Even");
    else Console.WriteLine("Odd");
  }
}


Measured memory_bytes: 11220
#include <iostream>
#include <vector>
#include <string>

using namespace std;



int main()
{
    int a,b;
    cin>>a>>b;
    if(b%a==0)
    {
        cout<<a+b;
    }
    else
    {
        cout<<b-a;
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int arr[MAX];
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    map<int,int>mp;
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)
     mp[s[i]]=1;
    for(int i='a';i<='z';i++){
        if(mp[i]==0){
            cout<<(char)i<<endl;
            return 0;
        }
    }
    cout<<"None"<<endl;
    return 0;
}


Measured memory_bytes: 3780
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<iterator>
#include<stack>
#include<queue>
#include<utility>
#include<functional>
#include<bitset>
#include<numeric>
#include<cstring>
#include<tuple>
using namespace std;

int p, q, r;

int main( void )
{
	ios :: sync_with_stdio( 0 );
	cin.tie( 0 );
	
	cin >> p >> q >> r;
	cout << min( { p + q, r + q, p + r } ) << "\n";	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

int main(){
    ll n,k;
    cin>>n>>k;
    ll dp[k+1],ans=0;
    for(ll i=k;i>=1;i--){
        dp[i]=power(k/i,n);
        for(ll j=2*i;j<=k;j+=i) dp[i]-=dp[j];
        ans=(ans+i*dp[i]%mod)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}


Measured memory_bytes: 4372
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
typedef long long int ll;
// #define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FRE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define debug(x) cout << #x << " is: " << (x) << endl;
#define debugx(x) cout << #x << " is: " << (x) << endl; exit(0);
#define f(i,n) for(ll i=0;i<n;i++)
#define fa(i,a,n) for(ll i=a;i<n;i++)
#define loop(i,a, n) for(ll i = a; i <= n; i++)
#define loopb(i,a, n) for(ll i = a; i >= n; i--)
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define setmem(x, k) memset(x, k, sizeof(x))
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define MOD 1000000007
#define INF 1000111000111000111LL
#define endl "\n"
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<vector<ll>> matrix;
ll dx[] = {0, 1, 0, -1};
ll dy[] = {-1, 0, 1, 0};
const ll N = 5e5+5;
// ll a[N], b[N], dp[N], level[N], vis[N], in[N], out[N];
// vl g[N];
ll n, m;

ll a[N];

bool check(ll mid, ll k) {
    ll res = 0;
    f(i, n) {
        res += (a[i] - 1) / mid;
    }
    return res <= k;
}

void solve() {
    ll k;
    cin >> n >> k;
    ll mx = 0;
    f(i, n) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }

    ll l = 1, r = mx;
    while(l < r) {
        ll mid = (l + r) >> 1;
        if(!check(mid, k)) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    cout << l << endl;
}   
 
int32_t main() {
    IOS
    clock_t begin = clock();
    ll T = 1;
    // cin >> T;
    while(T--)
    solve();
    cerr<<"Time elapsed : "<<(clock()-begin)*1000.0/CLOCKS_PER_SEC<<"ms"<<'\n';
    return 0;
}

Measured memory_bytes: 5344
#include<iostream>
using namespace std;
typedef long long ll;

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

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

int main(){
    int n;
    cin >> n;
    int x[n];
    for(int i = 0; i < n; i++)  cin >> x[i];
    int ans = 0;
    for(int i = 1; i < 1<<n; i++){
        ll tmp = 1;
        for(int j = 0; j < n; j++)  if((i>>j)&1)    tmp = lcm(tmp, x[j]);
        bool valid = true;
        for(int j = 0; j < n; j++)  if(((i>>j)&1) == 0) valid &= tmp%x[j]!=0;
        if(valid)   ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3108
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int X,k,r[100010],Q;
struct node{int t,a,id;
}q[100010];int ans[100010];
bool cmp(node x,node y) {return x.t<y.t;}
int pls(int x,int y){return max(0,min(X,x+y));}
int main()
{
    scanf("%d%d",&X,&k);
    for (int i=1;i<=k;i++) scanf("%d",&r[i]);
    scanf("%d",&Q);
    for (int i=1;i<=Q;i++) 
    {
        scanf("%d%d",&q[i].t,&q[i].a);q[i].id=i;
    }
    sort(q+1,q+Q+1,cmp);
    int topr=0,topq=1,sum=0,down=0,up=X,add=0,js=-1;
    int cnt;
    while (topq<=Q)
    {
        if (r[topr+1]<q[topq].t&&topr<k)
        {
            topr++;
            add=js*(r[topr]-r[topr-1]);
            down=pls(down,add);up=pls(up,add);
            sum+=add;js=-js;
        } else
        {
            cnt=q[topq].t-r[topr];
            ans[q[topq].id]=pls(max(down,min(up,q[topq].a+sum)),js*cnt);
            topq++;
        }
    }
    for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);
    
}

Measured memory_bytes: 3200
# ABC_086_C_Traveling
N = int(input())
txy = [map(int, input().split()) for _ in range(N)]
t, x, y = [list(i) for i in zip(*txy)]
t.insert(0, 0)
x.insert(0, 0)
y.insert(0, 0)
can = True
distX = [0]*(N)
distY = [0]*(N)
dist = [0]*(N)
time = [0]*(N)

# distance
for i in range(N):
	distX[i] = abs(x[i]-x[i+1])
	distY[i] = abs(y[i]-y[i+1])
	dist[i] = distX[i]+distY[i]
	time[i] = t[i+1]-t[i]
	if dist[i] > time[i]:
		can = False
		break

# parity
for i in range(N):
	if (dist[i]-time[i]) % 2 == 1:
		can = False
		break

if can == True:
	print("Yes")
else:
	print("No")


Measured memory_bytes: 123036
#include <cstdio>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

int n, m;
int a[5003];
ll a_acc[5003];
int b[5003][203];
int b_best[203];
int main() {
    scanf("%d%d", &n, &m);
    repeat (i,n-1) scanf("%d", &a[i]);
    repeat (i,n-1) a_acc[i+1] = a_acc[i] + a[i];
    repeat (i,n) repeat (j,m) scanf("%d", &b[i][j]);
    ll ans = 0;
    repeat (l,n) {
        repeat (j,m) b_best[j] = 0;
        ll b_acc = 0;
        repeat_from (r,l,n) { // [l,r]
            repeat (j,m) {
                if (b_best[j] < b[r][j]) {
                    b_acc += - b_best[j] + b[r][j];
                    b_best[j] = b[r][j];
                }
            }
            ans = max(ans, b_acc - (a_acc[r] - a_acc[l]));
        }
    }
    printf("%lld\n", ans);
    return 0;
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main()
{
    lli n, m, tmp;
    cin >> n >> m;
    lli a, b;
    vector<int> vect(n);

    for(lli i=0; i<m; i++){
        cin >> a >> b;
        tmp = vect[a-1];
        tmp = tmp + 1;
        vect.at(a-1) = tmp;

        tmp = vect[b-1];
        tmp = tmp + 1;
        vect.at(b-1) = tmp;
    }
    for(auto it=vect.begin(); it!=vect.end(); it++)
        cout << *it << endl;
    return 0;
}

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

using namespace std;

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

    int n;
    cin >> n;
    long long one = 1, two = 1;

    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;

        long long up = max((one + a - 1) / a, (two + b - 1) / b);

        one = a * up;
        two = b * up;
    }
    cout << one + two << '\n';
    return 0;
}

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

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 


int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif 
    ll n;
    cin >> n;
    vll a(n) ;
    for(auto &x : a) cin >> x;
    ll cur = INT_MAX;
	bool foo = true;
    for(ll i = n-1; i >= 0; i--) {
         if(a[i] <= cur) {
         	cur = a[i] ;
         }
         else if(a[i]-1 <= cur) {
         	cur = a[i]-1; 
         }
         else {
         	foo = false;
         }
    }
    if(foo) cout << "Yes" ;
    else cout << "No" ;
  return 0;
} //good night.

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 
  
#define ll long long
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int MOD = (int)1e9 + 7;
const int MX = (int)1e5 + 10;

void add_self(int &x, int y, int md = MOD){x += y; if(x >= md) x -= md;}
void sub_self(int &x, int y, int md = MOD){x -= y; if(x < 0) x += md;}
void mul_self(int &x, int y, int md = MOD){x = x * 1LL * y % md;}
inline int mul(int x, int y, int md = MOD){return x * 1LL * y % md;}
inline int add(int x, int y, int md = MOD){x += y; if(x >= md) x -= md; return x;}
inline int sub(int x, int y, int md = MOD){x -= y; if(x < 0) x += md; return x;}

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

vector<int> read(int n, int k){
	vector<int> vec(n);
	for(int i = 0; i < k; ++i) cin >> vec[i];
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for(int i = k; i < n; ++i)
		vec[i] = (a * 1ll * vec[i - 2] + b * 1ll * vec[i - 1] + c) % d;
	return vec;
}

int n;
int dp[(int)1e6 + 10][2][2];

int check(int idx, int ok1, int ok2){
	if(idx == n) return ok1 && ok2;
	int& res = dp[idx][ok1][ok2];
	if(res != -1) return res;
	res = 0;
	for(int i = 0; i < 10; ++i){
		add_self(res, check(idx + 1, ok1 | (i == 0), ok2 | (i == 9)));
	}
	return res;
}

void solve(){

	cin >> n;

	// if(n == 1){
	// 	cout << 0 << "\n";
	// 	return;
	// }

	// int res = (n * (n - 1LL)) % MOD;
	// // mul_self(res, (n * (n - 1LL) / 2) % MOD);

	// for(int i = 1; i <= n - 2; ++i){
	// 	// mul_self(res, 10);
	// 	res = (res * 10LL) % MOD;
	// }

	memset(dp, 0xff, sizeof dp);
	cout << check(0, 0, 0) << '\n';
	// cout << res << "\n";

	return;
}

int main(){

	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);

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

	int t;
	t = 1;
	// cin >> t;
	// pre();
	for(int i = 1; i <= t; ++i){
		// cout << "Case #" << i << ": ";
		solve();
		// cout << '\n';
		// cout << endl;
	}

	return 0;
}


Measured memory_bytes: 112940
#include<bits/stdc++.h>
// Useful constants
#define INF  (int)1e9
#define EPS   1e-9
#define MOD 1000000007ll
#define PI 3.14159
// for input-output
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
// iteration macros: have advantage of auto-casting and not recomputing arguments
#define REP(i, a, b) \
for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
#define TRvi(c, it) \
for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for (vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for (msi::iterator it = (c).begin(); it != (c).end(); it++)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
// input macro
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}
//output macro
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
// shortcut for data type
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define vvii vector<vii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define uset unordered_set
#define umap unordered_map
//--namespace
using namespace std;
//--useful function
ll gcd(ll a, ll b){ll temp;while (b > 0){temp = a%b;a = b;b = temp;} return a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
// --clock funtion
clock_t time_p=clock();
void TimeTaken()
{
    time_p=clock()-time_p;
    cerr<<"Completion time : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
// --solve function
void solve() {

}
//--main function
int main(){
	int a,b,flag=0;
	cin>>a>>b;
	string s;
	cin>>s;
	REP(i,0,a+b)
	{
		if(i==a)continue;
		if(isdigit(s[i]) && s[a]=='-')
			flag=0;
		else{
			flag=1;
			break;
		}
	}
	if(flag==0)cout<<"Yes";
	else cout<<"No";
	return 0;

//   TimeTaken();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; 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 INF 2e9
#define MOD 1e9+7
#define ALL(v) v.begin(), v.end()

int main()
{
    ll X, Y;
    cin >> X >> Y;
    
    ll Z = Y / X;
    ll ans = 0;
    while (Z > 0) {
        ans++;
        Z /= 2;
    }

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

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

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

    ll ans = 100000000000;

    for(int bit = 0; bit < (1 << n-1); bit++){
        ll d = 0;
        ll b[n];
        for(int i = 0; i < n; i++){
            b[i] = a[i];
        }
        vector<int> bit_iter(n, 0);
        int bit_cnt = 0;
        for(int j = 0; j < n-1; j++){
            if(bit & (1 << j)){
                bit_iter[j+1] = 1;
                bit_cnt++;
            }
        }
        if(bit_cnt != k-1){
            continue;
        }
        ll max_b = b[0];
        for(int j = 0; j < n-1; j++){
            max_b = max(max_b, b[j]);
            if(bit_iter[j+1] == 1 && max_b >= b[j+1]){
                b[j+1] = max_b + 1;
            }
        }
        for(int i = 0; i < n; i++){
            d += b[i] - a[i];
        }
        ans = min(ans, d);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const double pi = 3.14159265358979323846;
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main()
{
  speed;
  
  ll n,a=0,w=0,t=0,r=0;
  string s;
  cin>>n;
  
  for(int i=0;i<n;i++)
  {
    cin>>s;
    if(s[0]=='A')a++;
    else if(s[0]=='W')w++;
    else if(s[0]=='T')t++;
    else if(s[0]=='R')r++;
  }
  
  cout<<"AC x "<<a<<"\n";
  cout<<"WA x "<<w<<"\n";
  cout<<"TLE x "<<t<<"\n"<<"RE x "<<r;
  
  return 0;
  
}
  

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main(){
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}

Measured memory_bytes: 3472
#include "bits/stdc++.h"
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
using namespace std;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
#define pb push_back
template<class T> void print(const T& x){cout << x << endl;}
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
typedef long long ll;
const int inf = 1000000001;
const ll INF = 1e18 * 4;

int main(){
    string b; cin >> b;
    string ans;
    if(b=="A") ans = "T";
    if(b=="T") ans = "A";
    if(b=="C") ans = "G";
    if(b=="G") ans = "C";
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define REP(i, n) for (LL i = 0; i < (LL)(n); i++)
#define REP2(i, n) for (LL i = 1; i <= (LL)(n); i++)
#define FOR(i, m, n) for (LL i = m; i < n; i++)
#define SORT(x) sort(x.begin(), x.end())
#define REVE(x) reverse(x.begin(), x.end())
#define ALL(x) (x).begin(), (x).end()
#define SUM(x) accumulate(x.begin(), x.end(),0)
#define vLL(v,n) vector<LL> v(n); REP(i,n)cin>>v[i];
#define vstr(v,n) vector<string> v(n); REP(i,n)REP(i,n)cin>>v[i];
LL INF = 1e9 + 1;
LL MOD = 1e9+7;
  LL a,b,c,d,e,n,m,l,k,r,x,y,z,ans=0,ans2=0;
string s,S,t;
int main() {
ios_base::sync_with_stdio(false);
  cin >> n;
  REP2(i,n){
   ans+=(n/i)*(n/i+1)*i/2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3612
list=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k=int(input())
print(list[k-1])


Measured memory_bytes: 2940
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    import itertools
    n=int(input())
    l=list(map(int,input().split()))
    sum=0
    for i in range(n):
        for j in range(i+1,n):
                sum+=l[i]*l[j]
    print(sum)
resolve()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma optimize("JARU SOSISONI")

using namespace std;

#define int long long
#define fast cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define geometry cout.setf(ios::fixed); cout.precision(15);
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;

const int INF = 1e9 + 100;
const int MOD1 = 998244353;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int nul = 0;
const int SIZE = 1e6 * 3;



signed main() {
#ifdef parasha
    freopen("A.in", "r", stdin);
#endif // parasha
    fast;
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> smth(n);
    for (int &i : smth) cin >> i;
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if ((smth[i + 1] - smth[i]) * a < b) {
            ans += (smth[i + 1] - smth[i]) * a;
        } else ans += b;
    }
    cout << ans << endl;
}












Measured memory_bytes: 3956
#include<bits/stdc++.h>
#define __STDC_LIMIT_MACROS
#include <stdint.h>
using namespace std;
#define int             long long
#define endl '\n'	 
bool isPrime(int n)
{
	if (n <= 1)
		return false;
	if (n <= 3)
		return true;
	if (n % 2 == 0 || n % 3 == 0)
		return false;
	for (int i = 5; i * i <= n; i += 6)
	{
		if (n % i == 0 || n % (i + 2) == 0)
			return false;
	
	}
	return true;
}
 
void c_p_c()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
 
}
bool how(pair<int,int> a, pair<int, int>b)
{
	return a.second<b.second;
}
 
int32_t main()
 
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	c_p_c();
	char c;
	cin>>c;
	if(c==toupper(c))
	{
		cout<<"A"<<endl;
	}
	else
		cout<<"a"<<endl;
}

Measured memory_bytes: 3648
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

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

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 1e9+7;
const int MAXN =(int) 5e5+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
LL N,K;
set<LL> st;

void work(){
    scanf("%lld",&N);
    st.insert(N);
    if(N-1>1) st.insert(N-1);
    for(int i=2;(LL)i*i<=N;i++){
        if(N%i==0){
            LL j=N/i,tmpN;
            tmpN=N;
            while(tmpN>1&&tmpN%i==0) tmpN/=i;
            if((tmpN-1)%i==0) st.insert(i);
            tmpN=N;
            while(tmpN>1&&tmpN%j==0) tmpN/=j;
            if((tmpN-1)%j==0) st.insert(j);
        }
    }
    LL M=N-1;
    for(int i=2;(LL)i*i<=M;i++){
        if(M%i==0){
            st.insert(i);
            st.insert(M/i);
        }
    }
    printf("%d\n",st.size());
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}







Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    char b;

    b = getchar();

    switch(b){
        case 'A':
            printf("T\n");
            break;
        case 'T':
            printf("A\n");
            break;
        case 'C':
            printf("G\n");
            break;
        case 'G':
            printf("C\n");
            break;
    }

    return 0;
}

Measured memory_bytes: 128
n, k = map(int, (input().split()))
arr = [0] * 100100
for i in range(n):
    a, b = map(int, input().split())
    arr[a] += b

cur = 0
for i in range(100100):
    cur += arr[i]
    if cur >= k:
        print(i)
        break

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

using namespace std;

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

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

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
	set<string> s;
	int n;
	cin>>n;
	rep(i,n){
		string q;
		string x;
		cin>>q>>x;
		if(q=="insert"){
			s.insert(x);
		}else{
			cout<<(s.count(x)?"yes":"no")<<endl;
		}
	}
	return 0;
}


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

using namespace std;

using ll=long long;
const ll MOD = 998244353;

ll N,K;
ll T[500000];


void update(uint32_t i, ll val)
{
    for(T[i+=N] = val; i>>=1; )
    {
        T[i] = (T[i<<1]+T[i<<1^1])%MOD;
    }
}
ll get(int l, int r)
{
    ll sum = 0;
    
    if(l>=N)return 0;
    l+=N;
    if(r>N)r = N;
    r+=N;
    while(l<r)
    {
        if(l&1) sum+=T[l++];
        if(r&1) sum+=T[--r];
        l>>=1;
        r>>=1;
        sum%=MOD;
    }
    return sum;
}

int main() {
    cin >> N >> K;
    vector<pair<ll,ll>> V(K);
    for(int i = 0; i < K; ++i)
    {
        cin >> V[i].first >> V[i].second;
    }
    update(N-1,1);
    for(int32_t i = N-2; i>=0; --i)
    {
        ll sum = 0;
        for(auto j = 0; j < K; ++j)
        {
            sum += get(i+V[j].first, i+V[j].second+1);
            sum%=MOD;
        }
        update(i,sum);
    }
    std::cout << T[N] << std::endl;
}

Measured memory_bytes: 6756
#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <math.h>
#include <queue>
#include <string.h>
#include <map>
#include <set>
#include <cstdlib>

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

char ToUpper(char cX) { return toupper(cX); }
char Tolower(char cX) { return tolower(cX); }

const long long INF = 1LL << 60;
const long long MOD = 1000000007;

using namespace std;
typedef unsigned long long ull;
typedef  long long ll;



vector<vector<ll>> dp;


int main()
{
	ll n, m;
	cin >> n >> m;
	vector<ll> c(m, 0);
	for (ll i = 0; i < m; i++) {
		cin >> c[i];
	}
	dp.resize(n + 1);
	for (ll i = 0; i <= n; i++) {
		dp[i] = vector<ll>(m + 1, INF);
	}
	dp[0][0] = 0;
	for (ll i = 0; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			//cout << i << " " << j << endl;
			if (i - c[j] >= 0) {
				chmin(dp[i][j], dp[i - c[j]][j] + 1);
			}
			if (j + 1 <= n)
				chmin(dp[i][j + 1], dp[i][j]);
		}
	}

	cout << dp[n][m] << endl;

	return 0;
}



Measured memory_bytes: 12564
<?php
$inputSecond = trim(fgets(STDIN));
$hour = floor($inputSecond / 3600);
$minutes = floor(($inputSecond - $hour * 3600) / 60);
$second = floor($inputSecond - $hour * 3600 -$minutes * 60);
echo $hour.':'.$minutes.':'.$second, PHP_EOL;

Measured memory_bytes: 15224
#include<iostream>

using namespace std;

void selectionSort(int A[100], int n){

    int i, j, minj, counter = 0, tmp;

    for(i=0;i<n;i++){
        minj = i;
        for(j=i;j<n;j++){
            if(A[j] < A[minj]){
                minj = j;
            }
        }
        if(i != minj){
            A[i] = A[i] + A[minj];
            A[minj] = A[i] - A[minj];
            A[i] = A[i] - A[minj];
            counter++;
        }
    }

    for(j=0;j<n;j++){
        if(j == 0){
            cout << A[j];
        }else{
            cout << " " << A[j];
        }
    }

    cout << endl << counter << endl;

}

int main(){

    int i, n;
    int A[100] = {0};

    cin >> n;

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

    selectionSort(A, n);

    return 0;
}


Measured memory_bytes: 3108
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a); i<(b);++i)
#define rep(i, n) FOR(i, 0, n)

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

// solve
vector<P> vec;

template <typename T>
struct Graph_ {
  int n;
  vector<vector<pair<int, T> > > edge;
  vector<T> dis;
  Graph_(int ns) {
    n = ns;
    edge.resize(n);
    dis.resize(n);
  }
  void dijkstra(int s){
    dijkstra(s, 0);
  }
  T dijkstra(int s, int t){
    // initialize
    fill(dis.begin(), dis.end(), -1);
    vector<bool> used;
    used.resize(n);
    fill(used.begin(), used.end(), false);
    dis[s] = 0;
    // dijkstra
    priority_queue<pair<T, int>, vector<pair<T, int> >, greater<pair<T, int> > > q;
    q.push(make_pair(0, s));
    while(!q.empty()){
      pair<T, int> p = q.top(); q.pop();
      int at = p.second;
      T distance = p.first;
      if(used[at])continue;
      used[at] = true;
      for(auto itr = edge[at].begin(); itr != edge[at].end(); ++itr){
        int to = (*itr).first;
        T cost = (*itr).second;
        if(used[to])continue;
        if(dis[to] == -1 || dis[to] > distance + cost){
          q.push(make_pair(distance + cost, to));
          dis[to] = distance + cost;
        }
      }
    }
    return dis[t];
  }
  void adde(int at, int to, T cost){
    edge[at].push_back(make_pair(to, cost));
  }
  [[deprecated("This function takes O(edge[at].size()).")]]
  void remove(int at, int to){
    int index = -1;
    for(int i = 0; i < edge[at].size(); i++){
      if(edge[at][i].first == to){
        index = i;
        break;
      }
    }
    edge[at].erase(edge[at].begin() + index);
  }
};

typedef struct Graph_<int> GraphI;
typedef struct Graph_<ll> GraphL;
typedef struct Graph_<double> GraphD;

int main(int argc, char const* argv[])
{
  int n, k;
  cin >> n >> k;
  GraphI graph(n);
  rep(i, n - 1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    graph.adde(a, b, 1);
    graph.adde(b, a, 1);
    vec.pb(mk(a, b));
  }
  int res = inf;
  if(k % 2 == 0){
    rep(i, n){
      int tmp = 0;
      graph.dijkstra(i);
      rep(j, n){
        if(graph.dis[j] > k / 2)tmp++;
      }
      res = min(res, tmp);
    }
  }else{
    rep(i, n - 1){
      int tmp = 0;
      int a = vec[i].first;
      int b = vec[i].second;
      graph.dijkstra(a);
      vector<int> dis(n);
      rep(j, n)dis[j] = graph.dis[j];
      graph.dijkstra(b);
      rep(j, n){
        dis[j] = min(dis[j], graph.dis[j]);
        if(dis[j] > (k - 1) / 2)tmp++;
      }
      res = min(res, tmp);
    }
  }
  cout << res << endl;
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll =  long long;
ll gcd(ll b, ll c){
    return c ? gcd(c, b % c) : b;
}
 
ll lcm(ll b, ll c){
    return b / gcd(b, c) * c;
}
 
ll func(ll a, ll b, ll c)
{
	ll s =a;
  	s-= a/b;
  	s-= a/c;
  	s+=a/lcm(b,c);
	return s;
}
int main()
{
ll A,B,C,D;
cin >> A >> B >> C >> D;
ll ans = func(B,C,D) - func(A-1,C,D);
cout << ans << endl;
return 0;
}

Measured memory_bytes: 256