akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int partition(auto a[], int p, int r)
{
    int x = a[r].first;
    int i = p - 1;

    for(int j = p; j < r; j++) {
        if (a[j].first <= x) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r]);

    return i + 1;
}

void quicksort(auto a[], int p, int r)
{
    if (p < r){
        int q = partition(a, p, r);
        quicksort(a, p, q - 1);
        quicksort(a, q + 1, r);
    }
}

bool comp(pair<int, char> a, pair<int, char> b)
{
    return a.first < b.first;
}

int main()
{
    int n;
    cin >> n;

    pair<int, char> a[n], b[n];
    for(int i = 0; i < n; i++) cin >> a[i].second >> a[i].first, b[i] = a[i];

    quicksort(a, 0, n - 1);

    stable_sort(b, b + n, comp);

    bool f = true;
    for(int i = 0; i < n; i++) {
        // cerr << b[i].second << " " << b[i].first << " " << a[i].second << " " << a[i].first << endl;
        if(b[i] != a[i]) f = false;
    }
    cout << (f ? "Stable" : "Not stable") << endl;
    for(int i = 0; i < n; i++) {
        cout << a[i].second << " " << a[i].first << endl;
    }

    return 0;
}



Measured memory_bytes: 5072
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

string turn1(string S)
{
	return S.substr(1, S.size() - 1) + S[0];
}

string turn2(string S)
{
	return S[S.size() - 1] + S.substr(0, S.size() - 1);
}

string turn3(string S)
{
	string T;

	if (S.size() % 2 == 1)
	{
		T = S.substr(S.size() / 2 + 1, S.size() / 2) + S[S.size() / 2] + S.substr(0, S.size() / 2);
	}
	else
	{
		T = S.substr(S.size() / 2, S.size() / 2) + S.substr(0, S.size() / 2);
	}

	return T;
}

string turn4(string S)
{
	reverse(S.begin(), S.end());

	return S;
}

string turn5(string S)
{
	for (int i = 0; i < S.size(); i++)
	{
		if (isdigit(S[i]))
		{
			if (S[i] == '9')
			{
				S[i] = '0';
			}
			else
			{
				S[i]++;
			}
		}
	}

	return S;
}

string turn6(string S)
{
	for (int i = 0; i < S.size(); i++)
	{
		if (isdigit(S[i]))
		{
			if (S[i] == '0')
			{
				S[i] = '9';
			}
			else
			{
				S[i]--;
			}
		}
	}

	return S;
}

int main()
{
	int n; string S, T;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> S >> T;

		for (int i = S.size() - 1; i >= 0; i--)
		{
			switch (S[i])
			{
				case 'C': T = turn1(T); break;
				case 'J': T = turn2(T); break;
				case 'E': T = turn3(T); break;
				case 'A': T = turn4(T); break;
				case 'M': T = turn5(T); break;
				case 'P': T = turn6(T); break;
			}
		}

		cout << T << endl;
	}

	return 0;
}

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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = 1e9+7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


ll  fct[200200], inv[200200];
void finit(int cmx, ll mod){
	auto bin_pows =[](ll x, ll n, ll mod){
		ll res = 1LL;
		for(; n > 0; n >>=1, x = x*x %mod) if(n & 1) res = res * x %mod;
		return res;
	};
	fct[0] = fct[1] = inv[1] = 1;
	for(int i=2;i<cmx+3;i++) fct[i] = fct[i-1] * i % mod;
	inv[cmx] = bin_pows(fct[cmx], mod-2, mod);
	for(int i=cmx;i>=1;i--) inv[i-1] = inv[i] * i % mod;
}
ll nPk(ll n, ll k, ll mod = MD) {
	if(k > n) return 0;
	return fct[n] * inv[n-k] % mod;
}

int main(){
	cin.tie(0); ios_base::sync_with_stdio(false);
	finit(200010, MD);
	int n, k;
	cin >>n >>k;
	vector<VI> r(n);
	rep(i, n-1){
		int a,b;
		cin >>a >>b;
		r[a-1].push_back(b-1);
		r[b-1].push_back(a-1);
	}
	
	const ll inf = 1LL<<60;
	VL dd(n, inf);
	queue< int > que;
	que.push(0);
	 dd[0] = nPk( k , sz(r[0])+1);
	while(!que.empty()){
		int cy = que.front();
		que.pop();
		for(auto u: r[cy]) if(dd[u]==inf){
				que.push(u);
				dd[u] = nPk( k-2 , sz(r[u])-1);
		}
	}
	ll ans =1;
	for(auto x: dd) (ans *= x) %=MD;
	cout << ans <<"\n";
	return 0;
 }



Measured memory_bytes: 10488
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
const int N=200001;
const int mod=1e9+7;
int n,f[N],F[N+1];
void inc(int&a,int b){a+=b;if(a>=mod)a-=mod;}
void upd(int x,int s){for(x++;x>=1;x-=x&-x)inc(F[x],s);}
int ask(int x){int s=0;for(x++;x<=n+1;x+=x&-x)inc(s,F[x]);return s;}
struct xint{int x,y;}s[N],p[N];
bool cmpx(xint a,xint b){return a.x<b.x;}
bool cmpy(xint a,xint b){return a.y<b.y;}
int main(){
	scanf("%d",&n);
	ref(i,1,n)scanf("%d%d",&s[i].x,&s[i].y);
	sort(s+1,s+n+1,cmpy);
	ref(i,1,n)s[i].y=i;
	sort(s+1,s+n+1,cmpx);
	p[1].y=s[1].y;
	ref(i,2,n)p[i].y=max(p[i-1].y,s[i].y);
	p[n].x=s[n].y;
	def(i,n-1,1)p[i].x=min(p[i+1].x,s[i].y);
	f[0]=1;upd(0,1);
	int ans=0;
	ref(i,1,n){
		f[i]=ask(p[i].x-1);
		upd(p[i].y,f[i]);
		if(p[i].y==n)inc(ans,f[i]);
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 4992
import java.io.PrintWriter;
import java.util.*;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int n = in.nextInt();
        int[] d = new int[n];
        for (int i=0; i < n; i++)
            d[i] = in.nextInt();

        Arrays.sort(d);

        out.println(d[n/2] - d[n/2-1]);
    }

}


Measured memory_bytes: 50308
import java.lang.StringBuilder

fun main() {
    var n = nextLong()
    val res = StringBuilder()
    while (n > 0) {
        var m = n % 26
        n /= 26
        if (m == 0L) {
            m = 26
            n--
        }
        res.insert(0, m.plus(96).toChar())
    }
    println(res.toString())
}

// # Utils
// ## Input
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map(String::toInt)
fun nextLongList() = next().split(" ").map(String::toLong)
fun nextDoubleList() = next().split(" ").map(String::toDouble)

// ## Array
inline fun <reified T> sizedArray(size: Int, default: T) = Array(size) { default }


Measured memory_bytes: 34508
//by Top1
#include <bits/stdc++.h>
          
#define f first
#define s second
#define int long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define pll pair <long, long>
#define mp make_pair
#define pb push_back
#define pf push_front
#define pp pop_back
#define cerr cout
#define rev reverse
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define boost ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0);
#define nxtp next_permutation
#define pvtp prev_permutation
#define KZ return 
#define x1 x21212121
#define y1 y21212121
#define sqr(x) x * x 
      
const int inf = (1e18) + 1;
const int mod = 479001599;
const int maxn = 1e5 + 111;
        
using namespace std;          

int n, m, a[maxn], k = 1;

void solve(){
	cin >> n >> m;

    for (int i = 1; i <= n; i++){
    	cin >> a[i];
    	k = k * a[i] / (__gcd(a[i], k));
    }

    int h = k / 2;
    
    for (int i = 1; i <= n; i++){
    	a[i] /= 2;
    	if ((h / a[i]) % 2 == 0){
    		cout << 0;
    		return;
    	}
    }

    cout << m / h - m / k;                                               
}   
      
main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

    boost;
    
    int q = 1;

    //cin >> q;

    while (q--){
        solve();
    }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb emplace_back
#define inf (int)1e9
#define ff first
#define ss second
#define ll long long
#define sp(n) cout << setprecision(n) << fixed
#define hellcat ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define give(x) cout << #x << " " << x << endl
#define debug cout << "dddd" << '\n'
#define debarr(a, n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

template <class S, class T>
inline S smax(S &l, T r) {
  return l = max(l, (S)r);
}
template <class S, class T>
inline bool smin(S &l, T r) {
  return l = min(l, (S)r);
}

const int MAXN = 2e5 + 10;
int a[MAXN];
pair<ll, int> p[MAXN << 1];

int32_t main () {
  hellcat;

	int n;
	cin >> n;

	for (int i = 1; i <= n; ++i) cin >> a[i];

	int tol = 0;
	for (int i = 1; i <= n; ++i) {
		p[tol].ff = i + a[i];
		p[tol].ss = 1;
		p[tol + 1].ff = i - a[i];
		p[tol + 1].ss = 2;
		tol += 2;
	}

	sort(p, p + tol);

	int st = 0;
	for (int i = 0; i < tol; ++i)
		if (p[i].ss == 1) {
			st = i;
			break;
		}
	ll now = p[st].ff, ans = 0;
	int sz = 1;
	for (int i = st + 1; i < tol; ++i) {
		if (p[i].ff == now && p[i].ss == 1)
			sz++;
		else if (p[i].ff == now)
			ans += sz;
		else if (p[i].ff != now && p[i].ss == 2)
			continue;
		else if (p[i].ff != now) {
			sz = 1;
			now = p[i].ff;
		}
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 10688
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    string SS, T;
    cin >> SS >> T;
    string C = "|";
    for (int j = 0; j < (SS.length() - T.length() + 1); j = j + 1)
    {
        int satisfy = 1;
        for (int i = 0; i < T.length(); i = i + 1)
        {
            if (SS[i + j] != T[i] && SS[i + j] != '?')
            {
                satisfy = 0;
                break;
            }
        }
        if (satisfy == 0)
            continue;
        string S;
        for (int s = 0; s < SS.length(); s = s + 1)
        {
            if (SS[s] != '?')
            {
                S += SS[s];
            }
            else
            {
                S += 'a';
            }
        }
        for (int t = 0; t < T.length(); t = t + 1)
        {
            S[j + t] = T[t];
        }
        if (S < C)
        {
            C = "";
            for(int n = 0; n < S.length(); n = n + 1)
            {
                C += S[n];
            }
        }
    }
    if (C == "|")
    {
        C = "UNRESTORABLE";
    }
    cout << C << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
		string[] input = Console.ReadLine().Split(' ');//Splitで区切り文字を指定して複数個受け取る。
		long n = long.Parse(input[0]);
		long s = long.Parse(input[1]);
    long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    long answer = long.MaxValue;
    long sumMemo = 0;//総和
    long leftMemo = 0;//左の何番目を入れるか

    for(long i = 0; i < n; i++) sumMemo += nums[i];
    if(sumMemo < s) answer = 0;//要素の和をS以上にできない
    else
    {
      sumMemo = 0;
      for(long i = 0; i < n; i++)
      {
        sumMemo += nums[i];
        while(sumMemo >= s)
        {
          answer = Math.Min(answer, (i+1)-leftMemo);
          sumMemo -= nums[leftMemo];
          leftMemo++;
        }
      }
    }
    
		Console.WriteLine(answer);
	}
}


Measured memory_bytes: 22628
//
// Created on 2020/08/02.
//


#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
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; }
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;



int main() {

    int n;
    int k;
    cin>>n>>k;
    vector<double>a(n);
    for (int i = 0; i < n; ++i) {
        cin>>a[i];
    }
    double ok = INF;
    double ng = 0;
    double mid = (ok + ng) / 2;
    while(0.1 < abs(ok - ng)){
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += (int)((a[i] + (mid - 1))/mid)-1;
        }
        if(cnt <= k){
            ok = mid;
        }else{
            ng = mid;
        }
        mid = (ok + ng) / 2;
    }
    int ans = ceil(ok);
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 4844
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<cctype>
#include<climits>
#include<bitset>
#include<stack>

using namespace std;

typedef long long ll;

const int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
const int MAX = 19;
int W, H, fld[10][10];
int P, sx, sy;
map<pair<pair<int, int>, int>, int> memo;

inline int CountBit(int s)
{
	int res = 0;
	for (int i = 0; i < P; i++) res += (s >> i) & 1;
	return res;
}

inline bool IsInside(int x, int y)
{
	return 0 <= x && x < W && 0 <= y && y < H;
}

inline bool CanDown(int x, int y, int s, int noBits)
{
	if (x == sx && y == sy && noBits == P) return true;
	if (fld[y][x] == -1) return false;
	return ((s >> fld[y][x]) & 1) == 0;
}

int DFS(int x, int y, int s)
{
	int cnt = CountBit(s);
	if (x == sx && y == sy && cnt == P) return 1;
	pair<pair<int, int>, int> state = make_pair(make_pair(x, y), s);
	if (cnt < MAX)
	{
		map<pair<pair<int, int>, int>, int>::iterator itr = memo.find(state);
		if (itr != memo.end()) return itr->second;
	}
	int sum = 0;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		while (IsInside(nx, ny) && !CanDown(nx, ny, s, cnt))
			nx += dx[i], ny += dy[i];
		if (!IsInside(nx, ny)) continue;
		sum += DFS(nx, ny, s | (1 << fld[ny][nx]));
	}
	if (cnt < MAX && !(cnt >= 19 && sum == 0)) memo[state] = sum;
	return sum;
}

signed main()
{
	while (cin >> W >> H, W || H)
	{
		memo.clear();
		P = 0;
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> fld[i][j];
				if (fld[i][j] == 0) fld[i][j] = -1;
				else if (fld[i][j] == 1) fld[i][j] = P++;
				else sx = j, sy = i, fld[i][j] = -1;
			}
		}
		printf("%d\n", DFS(sx, sy, 0));
	}
	return 0;
}

Measured memory_bytes: 65176
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007


int main()
{
   ll n,m;
   cin>>n>>m;
   ll broken[n+1]{};
   ll temp;
   for(ll i=0;i<m;i++)
   {
      cin>>temp;
      broken[temp]++;
   }
   ll ways[n+1]{};
   ways[0] = 1;

   if(broken[1] == 0)
      ways[1] = 1;

   for(ll i=2;i<=n;i++)
   {
      if(broken[i] == 0)
      {
         ways[i] = ways[i-1] + ways[i-2];
         ways[i]%=mod;
      }
   }
   cout<<ways[n];
   return 0;
}


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

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
const int N = 100100;

ll binpow(ll a, ll p) {
    ll s = 1;
    while (p) {
        if (p & 1) {
            s = s * a % M;
        }
        a = a * a % M;
        p >>= 1;
    }
    return s;
}

ll f[N], finv[N];

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> a[i];
    }
    f[0] = finv[0] = 1;
    for (int i = 1; i <= n + 1; ++i) {
        f[i] = f[i - 1] * i % M;
        finv[i] = binpow(f[i], M - 2);
    }
    vector<ll> ans(n + 1);
    for (int i = 0; i <= n; ++i) {
        ans[i] = f[n + 1] * finv[i + 1] % M * finv[n - i] % M;
    }
    vector<int> pos[N];
    for (int i = 0; i <= n; ++i) {
        pos[a[i]].push_back(i);
    }
    int l, r;
    for (int i = 1; i <= n; ++i) {
        if (pos[i].size() == 2) {
            l = min(pos[i][0], pos[i][1]);
            r = max(pos[i][0], pos[i][1]);
        }
    }
    int x = l + n - r;
    for (int i = 0; i <= n; ++i) {
        if (x >= i) {
            ans[i] -= f[x] * finv[i] % M * finv[x - i] % M;
        }
        ans[i] = (ans[i] + M) % M;
    }
    for (int i = 0; i <= n; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Measured memory_bytes: 9472
#include <bits/stdc++.h>
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define cinf(x,n) for(int i=0;i<(n);i++)cin>>x[i];
#define coutf(x,n) for(int i=0;i<(n);i++)cout<<x[i]<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using namespace std;

ll a[101];
ll sum;
ll ans;
ll ave;

int main(){
	ll n;
	cin >> n;
	rep(i,n){
		cin >> a[i];
		sum+=a[i];
	}
	double avetmp = static_cast<double>(sum)/n;
	if(abs(avetmp-static_cast<ll>(avetmp)<0.5))
		ave = static_cast<ll>(avetmp);
	else
		ave = static_cast<ll>(avetmp)+1;
	rep(i,n){
		ans+=(a[i]-ave)*(a[i]-ave);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3620
N, Q = map(int,input().split())
S = input()
arr = [0]*N
num = 0
for i in range(N-1):
  if (S[i]=='A')&(S[i+1]=='C'):
    num += 1
  arr[i+1] = num

for _ in range(Q):
  start,end = map(int,input().split())
  print(arr[end-1]-arr[start-1])
  

Measured memory_bytes: 6060
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>
#include <iterator> 
using namespace std;

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)

#define nl '\n'
#define ioi exit(0);


#define PI 3.14159265

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
//~ const int N= (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;

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



int main() { 
	int n; cin>> n;
	set<string> set_;
	for (int i = 0; i < n; i++) {
		string s; cin>> s;
		set_.insert(s);
	}
	cout<<(int)set_.size();
	return 0;
} 




Measured memory_bytes: 19220
#include <bits/stdc++.h>
#define el_cucuy ios_base::sync_with_stdio(0), cout.tie(0); cin.tie(0);
#define llong long long
#define pb push_back
#define bpc __builtin_popcount

const llong mxn = 1e6 + 7;
const llong mod = 1e9 + 7;
const llong inf = 1e18 + 9;

using namespace std;

llong n, a[mxn], dp[mxn];

int main(){
    el_cucuy
    cin >> n;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
    }dp[1] = 0;
    dp[2] = abs(a[1] - a[2]);
    for (int i = 3; i <= n; i ++){
        dp[i] = min(abs(a[i] - a[i - 1]) + dp[i - 1], abs(a[i] - a[i - 2]) + dp[i - 2]);
    }cout << dp[n];
    return 0;
}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
ll MM = 1000000000; ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
ll GCD(ll x, ll y){ if(y == 0) return x; else return GCD(y, x % y);}
ll LCM(ll x, ll y){ return x / GCD(x, y) * y;}
int dh[4] = {-1, 0, 0, 1};
int dw[4] = {0, -1, 1, 0}; 
using P = pair<int, int>;
const double pi = acos(-1.0);

using Graph = vector<vector<ll>>;

int main(){
  int n;
  cin>>n;
  cout<<n/3<<endl;
    
    
  return 0;
}


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

#define ll long long
#define ii pair<int, int>
#define dd pair<double, double>
#define pb(i) push_back(i)
const double PI = 3.14159265359;
const int inf = 1e9+77;
const ll mod = 1e9+7;
const double eps = 1e-7;
//int dir1[8] = {0, 0, 1, -1, 1, -1, 1, -1};
//int dir2[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dir1[4] = {0, 0, 1, -1};
int dir2[4] = {1, -1, 0, 0};

const int N = 1e6;

int main()
{
	int i, j;

	int n;
	cin >> n;

	string s;
	cin >> s;

	vector<int> w(n + 5, 0), r(n+5, 0);
	for(i = 0; i < n; i++)
	{
		w[i+1] = w[i] + ((s[i] == 'W') ? 1 : 0); 
		r[i+1] = r[i] + ((s[i] == 'R') ? 1 : 0);
	}

	int ans = inf;
	for(i = 0; i <= n; i++)
	{
		int b = (r[n]-r[i]);
		int a = w[i];
		
		ans = min(ans, a + b - min(a, b));
	}

	cout << ans << '\n';
}


Measured memory_bytes: 5240
class Power
  def initialize(n, m, mod)
    @pow = [1]
    m.times do |i| @pow << @pow[-1] * n % mod end
  end
  def query(m)
    @pow[m]
  end
end

class Combination
  def initialize(n, mod)
    @mod = mod
    @fact, @inv, @finv = Array.new(3){[1, 1]}
    2.upto(n) do |i|
      @fact[i] = (@fact[i-1] * i) % @mod
      @inv[i]  = (@inv[@mod % i] * (@mod - @mod / i) ) % @mod
      @finv[i] = (@finv[i-1] * @inv[i] ) % @mod
    end
  end
  def query(n, r)
    return 0 if (n < r) || (n < 0) || (r < 0)
    (@fact[n] * @finv[n-r] % @mod) * @finv[r] % @mod
  end
end

MOD=998244353
N,M,K=gets.split.map(&:to_i)
C=Combination.new(N,MOD)
P=Power.new(M-1,N,MOD)
p 0.upto(K).inject(0){|s,i| (s + M * P.query(N-1-i) * C.query(N-1,i)) % MOD}


Measured memory_bytes: 20944
n= int(input())
# import math
# s =input()
# n,m = map(int, input().split())
a = list(map(int, input().split()))
# a,b = map(str, input().split())
# ab = [list(map(int,input().split())) for _ in range(n)]

count = [0] *n

for i in a:
    count[i-1]+=1
for i in count:
    print(i)

Measured memory_bytes: 32368
import java.util.*;
public class Main {
	public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
      //取得
	  int N = sc.nextInt();
      int T = sc.nextInt();
      int min = 10001;
      
      for(int i=0;i<N;i++){
       int cost = sc.nextInt();
        if(sc.nextInt()<=T){
          min = Math.min(min,cost);
        }
      }
      //出力
      if(min==10001){
        System.out.println("TLE");
      }else{
        System.out.println(min);
      }
    }
}

Measured memory_bytes: 35744
import numpy as np

s0 = input()
s1 = s0
cnt0 = cnt1 = 0

for i in range(len(s0)):
    if (i%2 == 0) & (s0[i] == '1'):
        cnt0+=1
    elif (i%2 == 1) & (s1[i] == '0'):
        cnt0+=1

for i in range(len(s1)):
    if (i%2 == 0) & (s1[i] == '0'):
        cnt1+=1
    elif (i%2 == 1) & (s1[i] == '1'):
        cnt1+=1

print(np.minimum(cnt0,cnt1))


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

int main() {
	string a,b,c;
  	cin>>a>>b>>c;
  
	if(a.at(a.size()-1)==b.at(0) && b.at(b.size()-1)==c.at(0))
      cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main(){
    long long k, a, b;
    cin >> k >> a >> b;
    if ((b - a <= 2)||(k <= a)){
        cout << k + 1 << endl;
        return 0;
    }else{
        if (a == 1){
            cout << ((k - a + 1) / 2) * (b - a) + a + (k % 2) << endl;
            return 0;
        }else{
            cout << ((k - a + 1) / 2) * (b - a) + a + ((k - a - 1) % 2) << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
# define lson l, m, id<<1
# define rson m+1, r, id<<1|1
using namespace std;
const int maxn = 2e5+30;
const int oo = 0x3f3f3f3f;
int imin[maxn<<2], cost[maxn], dp[maxn];
void build(int l, int r, int id)
{
    if(l == r)
    {
        imin[id] = oo;
        return;
    }
    int m = l+r>>1;
    build(lson);
    build(rson);
    imin[id] = min(imin[id<<1], imin[id<<1|1]);
}
 
int query(int L, int R, int l, int r, int id)//线段树区间维护最小值。
{
    if(L<=l && r<=R) return imin[id];
    int m = l+r>>1, res = oo;
    if(L <= m) res = min(res, query(L, R, lson));
    if(R > m) res = min(res, query(L, R, rson));
    return res;
}
 
void update(int pos, int val, int l, int r, int id)
{
    if(l == r)
    {
        imin[id] = min(imin[id], val);
        return;
    }
    int m = l+r>>1;
    if(pos <= m) update(pos, val, lson);
    else update(pos, val, rson);
    imin[id] = min(imin[id<<1], imin[id<<1|1]);
}
vector<int>v[maxn];
int main()
{
    int n, q, cnt=0;
    scanf("%d",&n);
    build(1, n, 1);
    for(int i=1, j; i<=n; ++i)
    {
        scanf("%d",&j);
        cnt += !j;
        cost[i] = j?1:-1;
    }
    scanf("%d",&q);
    for(int i=0, j, k; i<q; ++i)
    {
        scanf("%d%d",&j,&k);
        v[j].push_back(k);//此处需要枚举左端点。
    }
    memset(dp, oo, sizeof(dp));
    dp[0] = 0;
    for(int i=1; i<=n; ++i)
    {
        for(auto j : v[i])
        {
            int mi = dp[i-1];
            mi = min(mi, query(max(i-1,1), j, 1, n, 1));
            if(mi < dp[j])//选择该区间的情况，★为什么可以直接取mi值呢？因为mi值所在点前面枚举时必然覆盖了i点！可以作为答案更新给dp[j]。
            {
                dp[j] = mi;
                update(j, mi, 1, n, 1);
            }
        }
        dp[i] = min(dp[i], dp[i-1]+cost[i]); //不选择该区间的情况。
    }
    printf("%d\n",dp[n]+cnt);
    return 0;
}

Measured memory_bytes: 14464
#[allow(unused_imports)]
use proconio::{fastout, input, marker::Chars, marker::Usize1};

use std::collections::HashSet;

use num_traits::Zero;
use std::clone::Clone;
use std::mem::swap;
use std::ops::RemAssign;

pub fn gcd<T>(mut a: T, mut b: T) -> T
where
    T: Zero + RemAssign<T> + Clone,
{
    while !b.is_zero() {
        a %= b.clone();
        swap(&mut a, &mut b);
    }
    a
}

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }
    let max_a = *a.iter().max().unwrap();
    let mut max_factor = vec![1; max_a + 1];
    for p in 2..max_a + 1 {
        if max_factor[p] == 1 {
            let mut j = p;
            while j <= max_a {
                max_factor[j] = p;
                j += p;
            }
        }
    }
    let mut g = 0;
    for &a in &a {
        g = gcd(g, a);
    }
    if g != 1 {
        println!("not coprime");
        return;
    }
    let pc = (|| {
        let mut ps = HashSet::new();
        for mut a in a {
            while a != 1 {
                let p = max_factor[a];
                while p == max_factor[a] {
                    a /= p;
                }
                if !ps.insert(p) {
                    return false;
                }
            }
        }
        return true;
    })();
    if pc {
        println!("pairwise coprime");
    } else {
        println!("setwise coprime");
    }
}


Measured memory_bytes: 25504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, P> P3;
const ll MOD = ll(1e9)+7;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-11;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()


int main() {
    int n, m, a;
    while(cin >> n >> m >> a, n){
        vector<int> v(n+1,0);
        v[a] = 1;
        vector<P3> ls;
        REP(i,m){
            int h, p, q;
            cin >> h >> p >> q;
            ls.push_back({-h,{p,q}});
        }
        SORT(ls);
        for(auto p : ls){
            int i = p.second.first, j = p.second.second;
            swap(v[i],v[j]);
        }
        REP(i,n+1){
            if(v[i]){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}



Measured memory_bytes: 3048
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.stream.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.function.*;

import static java.lang.System.out;


public final class Main {
	public static void main(String[] args) throws IOException {
		var istr = new InputStreamReader(System.in);
		var br = new BufferedReader(istr);
		int k = Integer.parseInt(br.readLine());
		var st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		for (int score = a; score <= b; score++) {
			if (score % k == 0) {
				out.printf("OK%n");
				return;
			}
		}
		out.printf("NG%n");
	}
}


Measured memory_bytes: 34248
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

ll gcd(ll n, ll m){
  if(n%m == 0) return m;
  return gcd(m, n%m);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ABC142D - Disjoint Set of Common Divisors
  // 最大公約数を求めて素因数分解を行い、素因数が何種類あるか求める
  ll A, B; cin >> A >> B;
  ll g = gcd(A, B);
  
  ll ans = 1;
  if(g % 2 == 0) ans++;
  while(g % 2 == 0){ // 素数2だけで分解する
    g /= 2;
  }
  for(ll i = 3; i * i <= g; i += 2){ // long long
    if(g % i == 0) ans++;
    while(g % i == 0){
      g /= i;
    }
  }
  if(g > 2) ans++; // 割り切れなかった素数
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
prime = [0]*(N+1)
ans = 1
for i in range(2,N+1):
    d = 1
    while i > 1:
        d+=1
        while i % d == 0:
            i = i//d
            prime[d]+= 1
for j in range(N+1):
    ans = ans *(prime[j]+1)%(10**9+7)
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)
int main(){
    ll n, ans = 10000000, check;
    cin >> n;
    vector<ll> X(n);
    RAP(i,n){
        cin >> X[i];
    }
    FOR(i,1,101){
        check = 0;
        RAP(j,n){
            check += pow(i-X[j], 2);
        }
        ans = min(ans, check);
    }
   
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    int n;
    cin >> n;
    vector<int> arr;
    arr.reserve(n);
    int x;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin(), arr.end());
    cout << arr.back() - arr.front() << endl;
    return 0;
}

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

int main(){
    string A, B,X;
    cin >> A >> B;
    int a,b;
    cin >> a >>b;
    cin >> X;


    if(X==A)
        a--;
    if(X==B)
        b--;

    cout << a << " " << b;

}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		long[] sizeArr = fs.nextLongArr(n);
		Arrays.sort(sizeArr);
		long[] cumlationSizeArr = new long[n];
		cumlationSizeArr[0] = sizeArr[0];
		
		int startIndex = 0;
		for(int i = 0; i < n - 1; i++) { 
			if(cumlationSizeArr[i] * 2 < sizeArr[i+1]) {
				startIndex = i+1;
			}
			
			cumlationSizeArr[i+1] = cumlationSizeArr[i] + sizeArr[i+1];
		}
		
//		System.out.println(Arrays.toString(sizeArr));
//		System.out.println(Arrays.toString(cumlationSizeArr));
//		
		System.out.println(n - startIndex);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


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

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

typedef long long ll;
const ll MOD = 1e9 + 7;

const int MAX = 2e+6 + 1;
ll fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int X, Y;
  std::cin >> X >> Y;

  if((X + Y) % 3 != 0) {
    std::cout << 0 << '\n';
    return 0;
  }

  int Q = (X + Y) / 3;
  int n = Y - Q;
  int m = - Y + 2 * Q;

  if(n < 0 || m < 0) {
    std::cout << 0 << '\n';
    return 0;
  }

  COMinit();
  std::cout << COM(n + m, n) << '\n';
}


Measured memory_bytes: 47104
function Main(input) {
  "use strict";
  const PQR = input
    .trim()
    .split(/\s/)
    .map(val => parseInt(val, 10));

  let sum = PQR.reduce((sum, currentVal) => {
    return sum + currentVal;
  }, 0);

  console.log(sum - Math.max(...PQR));
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

// in-short-use macros

#define all(c) (c).begin(),(c).end()
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define PI 3.14159265
#define sizes 1000010



//main function here

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
    int n;
    cin>>n;
    int h=n%10;
    if (h==0 || h== 6 || h==8 || h==1)
        cout<<"pon";
    else if(h==3)
        cout<<"bon";
    else
        cout<<"hon";
    return 0;
}

Measured memory_bytes: 3652
#include <iostream>

int main(int argc, const char * argv[]) {
    int a;
    int b;
    std::cin >> a >> b;
    if (a>b) {
        std::cout << "a > b" << std::endl;
    }
    else if (a<b){
        std::cout << "a < b" << std::endl;
    }
    else{
        std::cout << "a == b" << std::endl;
    }
}

Measured memory_bytes: 3076
N, K = map(int, input().split())
d = list(map(int, input().split()))

f = []
for i in range(10):		f += [False]
for i in range(K):		f[d[i]] = True

x=N-1
l=True

while l:
	
	x+=1
	
	l=False
	b=x
	while b>0:
		if f[b%10]:
			l=True
			break
		b//=10

print(x)


Measured memory_bytes: 3060
#include <stdio.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
long long int sum = 0;
 
 
void merge(int A[],int left,int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    int L[n1+1],R[n2+1];
    for(int i = 0; i < n1; i++) L[i] = A[left + i];
    for(int i = 0; i < n2; i++) R[i] = A[mid + i];
    L[n1] = R[n2] =  INT_MAX;
 
    int i = 0, j = 0;
    for(int k = left;k < right; k++){
        if(L[i] < R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
            sum += n1 - i;
        }
    }
}
 
void mergeSort(int A[],int left,int right){
    if(left+1 < right){
        int mid = (left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i = 0; i < n; i++) scanf("%d",&A[i]);
 
    mergeSort(A,0,n);
 
    printf("%lld\n",sum);
 
}


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

int main()
{
  int res = 0, a;
  char op;

  cin >> res;
  while (true){
    cin >> op;
    if (op == '=')  break;
    cin >> a;
    if (op == '+') res += a;
    else if (op == '-') res -= a;
    else if (op == '*') res *= a;
    else if (op == '/') res /= a;
  }
  cout << res << endl;
  return (0);
}

Measured memory_bytes: 1160
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 210000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long C(int a,int b){
	if(a<b||b<0)return 0;
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
// ここから編集しろ
int p[110];
int q[110];
int dp[110][110];
int calc(int a,int b){
	if(dp[a][b]!=-1)return dp[a][b];
	if(a==1)return (b==75);
	int ret=0;
	for(int i=0;i<=q[a];i++){
		if(b*(i+1)>75)continue;
		ret+=calc(a-1,b*(i+1));
	}
	return dp[a][b]=ret;
}
int main(){
	int a;scanf("%d",&a);
	p[0]=p[1]=-1;
	for(int i=2;i<=100;i++){
		if(p[i]==0){
			p[i]=1;
			for(int j=i+i;j<=100;j+=i)p[j]=-1;
		}
	}
	for(int i=1;i<=a;i++){
		if(p[i]==1){
			int tmp=a/i;
			while(tmp){
				q[i]+=tmp;
				tmp/=i;
			}
		}
	}
	for(int i=0;i<110;i++)for(int j=0;j<110;j++)
		dp[i][j]=-1;
	printf("%d\n",calc(a,1));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 163577857
#define mod1 998244353
#define Mmax 1000005
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
typedef unsigned long long int ull;
using namespace std;
bool sortbysec(const pair<li,li>&a,const pair<li,li>&b)
{
    return (a.second<b.second);
}
bool comp(pair<li,pair<li,li>>a,pair<li,pair<li,li>>b)
{
  if(a.first<b.first)
  return 1;
  else if(a.first>b.first)
  return 0;
  else
  {
    return a.second.first<b.second.first;
  }
}
li mpow(li x,li y)
{
  li ans=1;
  while(y)
  {
    if(y%2!=0)
    ans=(ans%mod)*(x%mod)%mod;
    y/=2;
    x=((x%mod)*(x%mod))%mod;
  }
  return ans;
}
li modInverse(li n)
{
    return mpow(n, mod-2);
}

li nCrModPFermat(li n, li r,li x,li y,li z)
{
   // Base case
   if (r==0)
      return 1;
    // li fac[n+1];
    // fac[0] = 1;
    // for (int i=1 ; i<=n; i++)
    //     fac[i] = fac[i-1]*i%mod;
    return (x* modInverse(y) % mod *modInverse(z) % mod) % mod;
}
void bfs(vector<li>v[],li visit[],li s,li ans[])
{
  deque<li>q;
  q.push_back(s);
  visit[s]=1;
  while(!q.empty())
  {
    li x=q.front();
    q.pop_front();
    for(auto i=v[x].begin();i!=v[x].end();i++)
    {
      if(!visit[*i])
      {
        q.push_back(*i);
        visit[*i]=1;
      }
    }
  }
}
void buildtree(int*tree,int*arr,int start,int end,int treeNode)
{
  if(start<end)
  {
    int mid=start+(end-start)/2;
    buildtree(tree,arr,start,mid,2*treeNode);
    buildtree(tree,arr,mid+1,end,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}
void update(int*tree,int*arr,int start,int end,int pos,int val,int treeNode)
{
  if(start==end)
  tree[treeNode]=val;
  else
  {
    int mid=start+(end-start)/2;
    if(pos<=mid)
    update(tree,arr,start,mid,pos,val,2*treeNode);
    else
    update(tree,arr,mid+1,end,pos,val,2*treeNode+1);
    tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
  }
}

void dfs(vector<li>v[],li visit[],li s,li c[],li ans[],map<li,li>*m,li pred[])
{
    visit[s]=1;
     (*m)[c[s]]++;
    for(auto i=v[s].begin();i!=v[s].end();i++)
      {
        if(!visit[*i])
        {pred[*i]=s;
           dfs(v,visit,*i,c,ans,m,pred);
        }
      }
      if((*m)[c[pred[s]]]==1)
    ans[s]=(*m).size()-1;
    else
    ans[s]=(*m).size();
}
vector<li>factor(li n)
{
  vector<li>v;
  if(n%2==0)
  {
    while(n%2==0)
    {n/=2;
    v.push_back(2);
    }
  }
  for(li i=3;i<=sqrt(n);i+=2)
  {
    if(n%i==0)
    {
      while(n%i==0)
      {n/=i;
      v.push_back(i);
      }
    }
  }
  if(n>1)
  v.push_back(n);
  return v;
}
int main()
{
// li t,i,j;
// cin>>t;
// while(t--)
// {
//
//   cout<<endl;
// }
li a,b,n;
cin>>a>>b>>n;
if(b<=n)
{
  li ans=(a*(b-1))/b;
  cout<<ans;
}
else
{
  cout<<(a*(n))/b;
}
return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <math.h>
int main(void){
   double q;
   while(scanf("%lf", &q)!= EOF && q != -1) {
       double x, a;      
       x=q/2;      
	while(1){
               if(fabs(x*x*x-q)<0.00001*q) break;
               x=x-((x*x*x-q)/(3*x*x));
	x = x;
           }          
           printf("%.7f\n",x);    
           }    
       return 0;
}


Measured memory_bytes: 2036
N = int(input())
S = input()
li = list("ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ")
sli = list(S)
for i in range(len(sli)):
  for j in range(26):
    if li[j] == sli[i]:
      sli[i] = li[j+N]
      break
print("".join(sli))

Measured memory_bytes: 3060
e1,e2,e3,e4=map(int,input().split())
if e1==e2 and e3==e4 :
    print("yes")
elif e1==e3 and e2==e4 :
    print("yes")
elif e1==e4 and e2==e3 :
    print("yes")
else:
    print("no")


Measured memory_bytes: 5596
n,m=map(int,input().split())
a=list(map(int,input().split()))
from fractions import gcd
for i in range(n):
	a[i]//=2
from copy import copy
b=copy(a)
c=[]

for i in range(n):
	cnt=0
	while b[i]%2==0:
		cnt+=1
		b[i]//=2
	c.append(cnt)
for i in range(n-1):
	if c[i]!=c[i+1]:
		print(0)
		exit()

a_gcd=a[0]
for i in range(1,n):
	a_gcd=a_gcd*a[i]//gcd(a_gcd,a[i])
print((m+a_gcd)//(a_gcd*2))

Measured memory_bytes: 14400
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>
 
#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")
 
#define mp make_pair
#define pb push_back
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
 mt19937 gen(34);

int a, b;

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
//	freopen("memory.in", "r", stdin);
//	freopen("memory.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> a >> b;
	cout << (b + a - 3) / (a - 1);
	return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val s = IntArray(n) { readLine()!!.toInt() }
    val sum = s.sum()
    if (sum % 10 != 0) {
        println(sum)
        return
    }
    val t = s.filter { it % 10 != 0 }.min()
    println(if (t == null) 0 else sum - t)
}


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

int Q, H, S, D;

int main() {
   cin >> Q >> H >> S >> D;
   H = min(H, 2*Q);
   S = min(S, 2*H);
   D = min(D, 2*S);
   int N; cin >> N;
   cout << (N/2)*1LL*D+(N&1)*S << endl;   
}

Measured memory_bytes: 256
open System
let readIntArray () = stdin.ReadLine().Split(' ') |> Array.map int

let [| N; A; B |] = readIntArray ()

let digSum n = 
    n
    |> string
    |> Seq.sumBy(fun c -> int c - int '0') //char to int
   
[1..N]
|> Seq.sumBy (fun v -> if (digSum v >= A) && (digSum v <= B) then v else 0)
|> printfn "%d"

Measured memory_bytes: 14300
S = input()
YYMM, MMYY = False, False
if 1 <= int(S[:2]) <= 12:
    MMYY = True
if 1 <= int(S[2:]) <= 12:
    YYMM = True

if YYMM and MMYY:
    print("AMBIGUOUS")
elif YYMM:
    print("YYMM")
elif MMYY:
    print("MMYY")
else:
    print("NA")



Measured memory_bytes: 2940
a=input()
if a == "A":
  print("A")
elif a =="B":
  print("A")
elif a =="C":
  print("A")
elif a =="D":
  print("A")
elif a =="E":
  print("A")
elif a =="E":
  print("A")
elif a =="F":
  print("A")
elif a =="G":
  print("A")
elif a =="H":
  print("A")
elif a =="I":
  print("A")
elif a =="J":
  print("A")
elif a =="K":
  print("A")
elif a =="L":
  print("A")
elif a =="M":
  print("A")
elif a =="N":
  print("A")
elif a =="O":
  print("A")
elif a =="P":
  print("A")
elif a =="Q":
  print("A")
elif a =="R":
  print("A")
elif a =="S":
  print("A")
elif a =="T":
  print("A")
elif a =="U":
  print("A")
elif a =="V":
  print("A")
elif a =="W":
  print("A")
elif a =="X":
  print("A")
elif a =="Y":
  print("A")
elif a =="Z":
  print("A")
else:
  print("a")

Measured memory_bytes: 9200
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

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

using namespace std;



int main() {
	ll n, k;
	string s;
	cin >> n >> k >> s;
	s[k - 1] -= 'A' - 'a';
	cout << s << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
int main()
{
	int n,a,count=0;
	cin>>n;
	map<int,bool>list;
	for(int x=0;x<n;x++)
	{
		cin>>a;
		if(list[a]==false)
		{
			count++;
			list[a]=true;
		}else
		if(list[a]==true)
		{
			list[a]=false;
			count--;
		}
	}
	cout<<count<<endl;
}

Measured memory_bytes: 4992