akhauriyash/Code-Regression huggingface dataset:
// Coached by rainboy
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000, A = 1000000;

int aa[N], kk[A + 1];

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int i = 0; i < n; i++)
		kk[aa[i]]++;
	for (int a = A; a >= 1; a--)
		for (int b = a + a; b <= A; b += a)
			kk[b] += kk[a];
	int k = 0;
	for (int i = 0; i < n; i++)
		if (kk[aa[i]] == 1)
			k++;
	cout << k << '\n';
	return 0;
}


Measured memory_bytes: 8296
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>



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

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)










int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    cout << min(a * n, b) << endl;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;
const int inf = 1000000000; //10^9
const ll MOD = 1e9 + 7;
//加算代入演算子は+=！！！！！
//int 2^31 10^9まで
int main()
{
    string n;
    cin >> n;
    bool ans = false;
    rep(i, 3) {
        if(n[i] == '7') {
            ans = true;
        }
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e5;
const ll MX=1e18+5;
int N,W,w[200],v[200],ans=0;
ll dp[103][M+4];
int main()
{
	cin>>N>>W;
	for(int i=1;i<=N;i++) cin>>w[i]>>v[i];
	for(int i=0;i<=N;i++)
	{
		for(int j=0;j<=M;j++)
		{
			if(j==0)
			dp[i][j]=0;
			else
			dp[i][j]=MX;
		}
	}
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=v[i])
			dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i]);
		}
	}
	for(int i=0;i<=M;i++)
	{
		if(dp[N][i]<=W)
		ans=max(ans,i);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 80128
#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 ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	int n;
	cin >> n;
	cout << (n + (1000 - n % 1000) % 1000) - n;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef long long ll;
const int MAXN = 1e7 + 5;
const int MAXD = 1e4 + 5;
const int MOD = 1e9 + 7;
const long double EPS = 1e-4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll rand(ll a, ll b) {ll c = rng(); return a+((ll)abs(c))%(b-a+1);}

int d[MAXN];

int main(){

        ios::sync_with_stdio(0);
        cin.tie(0);
         ll Ans = 0;
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
           for(int j = i; j <= n ; j+=i)
               d[j]++;
        

        for(ll i = 1 ; i <= n ; i++)
            Ans+=i * (ll)d[i];
         
     cout << Ans << '\n';      

       
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a,b,c;
    
    cin >> a >> b >> c;
    
   int five = 0, seven = 0;
   
   if(a==5)
    five++;
   else 
     seven++;
     
   if(b == 5)
    five++;
   else
    seven++;
    
   if(c == 5)
    five++;
   else 
     seven++;
     
  if(five == 2 && seven == 1)
   {
       cout<<"YES"<<"\n";
   }
   else
   {
       cout<<"NO"<<"\n";
   }
    
    return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const ll mod = 1000000007;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool prime(ll n) {
  if (n == 1) {
    return false;
  } else {
    for (ll i = 2; i <= (ll)pow(n, 0.5); i++) {
      if (n%i == 0) return false;
    }
  }
  return true;
}
ll RepeatSquaring(ll n, ll p, ll m) {
  if (p == 0) return 1;
  if (p%2 == 0) {
    ll t = RepeatSquaring(n, p/2, m);
    return (t*t)%m;
  }
  return (n*RepeatSquaring(n, p-1, m))%m;
}

int main() {
  ll n;
  cin >> n;
  vector <ll> v(n);
  rep(i, n) v.at(i) = i+1;
  do {
    rep(i, n) {
      if (i) {
        cout << ' ' << v.at(i);
      } else {
        cout << v.at(i);
      }
    }
    cout << endl;
  } while (next_permutation(v.begin(), v.end()));
}


Measured memory_bytes: 3112
package main

import (
    "fmt"
)


func main() {
	var  a, b int
	var flag bool
	flag = false
	fmt.Scan(&a, &b)
	for i := 0.0; i < 1101; i++ {
		if int(i*0.08) == a && int(i*0.1) == b {
			fmt.Println(i)
			flag = true
			break
		}
	}

	if !flag {
		fmt.Println(-1)
	}
}


Measured memory_bytes: 512
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n, m = rm()
stu = [rl() for _ in range(n)]
poi = [rl() for _ in range(m)]
for lis in stu:
    x, y = lis
    min_ = inf
    ans = ''
    for idx, li in enumerate(poi, 1):
        x1, y1 = li
        t = abs(x1-x)+abs(y1-y)
        if min_ > t:
            min_ = t
            ans = idx
    print(ans)









Measured memory_bytes: 27004
#include <iostream>

using namespace std;
typedef long long ll;

const int MAX = 2e5;
const int MOD = 1e9+7;

string A;
int N;
ll count[30];
ll count_[30];

int main() {
    cin >> A;
    N = A.size();
    for (int i = 0; i < N; ++i) count[A[i]-'a']++;
    for (int i = 26; i >= 0; --i) count_[i] += count[i+1]+count_[i+1];
    ll ans = 1;
    for (int i = 0; i < 26; ++i) {
        ans += count[i] * count_[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
	int H,W,i,j;
	while(1) {
		scanf("%d %d",&H,&W);
		if(H==0 && W==0) break;
		for (i=1; i<=H; i++) {
			for (j=1; j<=W; j++) {
				if( (i+j)%2 == 0 ) printf("#");
				else printf(".");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 572
#include<stdio.h>

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

	if (a < b)
	{
		printf("a < b\n");
	}
	else if (a > b)
	{
		printf("a > b\n");
	}

	else if (a==b)
	{
		printf("a == b\n");
	}
	return 0;
}


Measured memory_bytes: 2052
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();
        int a[] = new int[11];
        a[0] = x;
        for (int i = 0 ; i < 10 ; i++) {
            a[i + 1] = r * a[i] - d;
        }

        for (int i = 1 ; i < 11 ; i++) {
            System.out.println(a[i]);
        }
    }

}


Measured memory_bytes: 21076
#include<bits/stdc++.h>
using namespace std ; 
#define ll long long
typedef pair<ll,ll> pr;
typedef vector<ll> vc;
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
#define test  ll ll int tcase ; cin>>tcase ; while(tcase--) 
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main() {
    io ; 
   
  int k ; 
  cin>>k ; 
  int a,b ; 
  cin>>a>>b ; 
  int i ; 
  for( i = a; i<=b ; i++){
      if(i%k==0){
          cout<<"OK" ; 
          break ; 
      }
  }
  if(i==b+1){
      cout<<"NG" ; 
  }

   
}


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

using namespace std;

typedef long long int li;
typedef long double ld;
typedef vector<li> vi;
typedef pair<li,li> pi;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define f(i,l,r) for(li i=l;i<=r;++i)
#define fr(i,l,r) for(li i=l;i>=r;--i)
#define u_map unordered_map
#define endl "\n"

li fastpow(li base,li exp,li M) 
{
    li res=1;
    while(exp>0) {
        if(exp&1)
            res=(res*base)%M;

        base=(base*base)%M;
        exp>>=1;
    }
    return res;
}

vi par,sz,vis,dis;
vector<vi> graph;
vector<vector<pair<li,li>>> wgraph;

void init(li n)
{
    par.resize(n);
    sz.resize(n);
    wgraph.resize(n);
    dis.resize(n);
    vis.resize(n);
    graph.resize(n);

    f(i,0,n-1)
    {
        par[i]=i;
        sz[i]=1;
        dis[i]=1e18;
    }
}

li root(li a)
{
    while(a!=par[a])
    {
        par[a]=par[par[a]];
        a=par[a];
    }

    return a;
}

void unio(li a,li b)
{
    li r_a=root(a);
    li r_b=root(b);

    if(par[r_a]!=r_b)
    { 
        if(sz[r_a]<sz[r_b])
        {
            par[r_a]=par[r_b];
            sz[r_b]+=sz[r_a];
            sz[r_a]=0;
        }
        else
        {
            par[r_b]=par[r_a];
            sz[r_a]+=sz[r_b];
            sz[r_b]=0;
        }
    }
}

int main()
{    
    

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

    li n;

    cin>>n;

    cout<<n/2+n%2;

    return 0;
}

Measured memory_bytes: 256
s = input().strip()
ss = s.split()
d = int(ss[0])
n = int(ss[1])
i = 1
while 1:
	x = i
	c = 0
	while x % 100 == 0:
		x //= 100
		c += 1
	if c == d:
		n -= 1
		if n == 0:
			print(i)
			break
	i += 1


Measured memory_bytes: 3060
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
if n == 0:
    print(0)
else:
    def f(x):
        q, r = divmod(x, -2)
        return (q+1, 1) if r == -1 else (q, r)

    m = n
    ans = ''
    while m:
        m, r = f(m)
        ans = str(r) + ans
    print(ans)

Measured memory_bytes: 3060
main :: IO ()
main = do
  ls <- getContents
  let ls' = map (map (read :: String -> Float)) (map words (lines ls))
      ans = map format (foldl check [(0,0),(0,0),(0,0),(0,0)] ls')
  mapM_ putStrLn ans

checkl :: [(Int,Int)] -> [Float] -> [(Int,Int)]
checkl [pa,pb,pc,pd] [l,r]
  | l >= 1.1 = [(((fst pa)+1),(snd pa)),pb,pc,pd]
  | l >= 0.6 = [pa,(((fst pb)+1),(snd pb)),pc,pd]
  | l >= 0.2 = [pa,pb,(((fst pc)+1),(snd pc)),pd]
  | otherwise = [pa,pb,pc,(((fst pd)+1),(snd pd))]

checkr :: [(Int,Int)] -> [Float] -> [(Int,Int)]
checkr [pa,pb,pc,pd] [l,r]
  | r >= 1.1 = [((fst pa),((snd pa)+1)),pb,pc,pd]
  | r >= 0.6 = [pa,((fst pb),((snd pb)+1)),pc,pd]
  | r >= 0.2 = [pa,pb,((fst pc),((snd pc)+1)),pd]
  | otherwise = [pa,pb,pc,((fst pd),((snd pd)+1))]

check :: [(Int,Int)] -> [Float] -> [(Int,Int)]
check lt lf = checkr (checkl lt lf) lf

format :: (Int,Int) -> String
format (a,b) = (show a) ++ " " ++ (show b)

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

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

using namespace std;

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

int wa(int n) {
	int i;
	i = 0;
	while (n > 0) {
		i += n % 10;
		n /= 10;
	}

	return i;
}

int main() {
	int i, j, k, l, m, n;

	cin >> n;
	m = -1;
	l = n / 2;

	for (i = 1; i <= l; i++) {
		j = n - i;
		k = wa(i) + wa(j);
		if (m == -1 || m > k) {
			m = k;
		}
	}

	cout << m;

	return 0;
}

Measured memory_bytes: 256
/*
 *  Author  : StelaYuri
 * Language : GNU G++ 14
 */

//#pragma comment(linker,"/STACK:1024000000,1024000000")
//#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<string>
#include<utility>
#include<functional>
#include<iomanip>
//#include<unordered_map>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define pb push_back
#define eb emplace_back
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const double angcst=PI/180.0;
const ll mod=998244353;
ll max_3(ll a,ll b,ll c){if(a>b&&a>c)return a;if(b>c)return b;return c;}
ll min_3(ll a,ll b,ll c){if(a<b&&a<c)return a;if(b<c)return b;return c;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}



void solve()
{
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max(max(a*c,a*d),max(b*c,b*d))<<'\n';
}
int main()
{
    closeSync;
    //multiCase
    {
        solve();
    }
    return 0;
}


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

using namespace std;

int str2num(char *str) {
	int sum = 0;
	int tmp = 1;
	for (int i = 0; str[i] != '\0'; i++) {
		switch (str[i]) {
			case 'm':
				sum += tmp * 1000;
				tmp = 1;
				break;
			case 'c':
				sum += tmp * 100;
				tmp = 1;
				break;
			case 'x':
				sum += tmp * 10;
				tmp = 1;
				break;
			case 'i':
				sum += tmp * 1;
				tmp = 1;
				break;
			default:
				tmp = str[i] - '0';
				break;
		}
	}
	//cout << sum << endl;
	return sum;
}

void num2str(char *dst, int num) {
	//cout << "num2str::" << num << endl;
	int i = 0;
	if (num >= 2000) {
		//cout << "num2str::debug::2000" << endl;
		dst[i++] = (num / 1000) + '0';
		num %= 1000;
		dst[i++] = 'm';
	} else if (num >= 1000) {
		//cout << "num2str::debug::1000" << endl;
		num %= 1000;
		dst[i++] = 'm';
	}
	if (num >= 200) {
		//cout << "num2str::debug::200" << endl;
		dst[i++] = (num / 100) + '0';
		num %= 100;
		dst[i++] = 'c';
	} else if (num >= 100) {
		//cout << "num2str::debug::100" << endl;
		num %= 100;
		dst[i++] = 'c';
	}
	if (num >= 20) {
		//cout << "num2str::debug::20" << endl;
		dst[i++] = (num / 10) + '0';
		num %= 10;
		dst[i++] = 'x';
	} else if (num >= 10) {
		//cout << "num2str::debug::10" << endl;
		num %= 10;
		dst[i++] = 'x';
	}
	if (num >= 2) {
		//cout << "num2str::debug::2" << endl;
		dst[i++] = (num / 1) + '0';
		num %= 1;
		dst[i++] = 'i';
	} else if (num >= 1) {
		//cout << "num2str::debug::1" << endl;
		num %= 1;
		dst[i++] = 'i';
	}
	dst[i] = '\0';
}

void solve(char *str1, char *str2) {
	//cout << str1 << ':' << str2 << endl;
	int
		i1 = str2num(str1),
		i2 = str2num(str2);
	int sum = i1 + i2;
	char sout[15];
	num2str(sout, sum);
	cout << sout << endl;
}

int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char s1[15], s2[15];
		scanf("%s %s", s1, s2);
		solve(s1, s2);
	}
}

Measured memory_bytes: 1180
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
#define mkpr make_pair
const int MGN = 10;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>;
using vc = vector<char>; using vvc = vector<vc>;
using vb = vector<bool>; using vvb = vector<vb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using psl = pair<string, ll>;


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


  ll H, W; cin>>H>>W;
  if (H == 1 || W == 1) {
    cout << 1 << endl;
    return 0;
  }

  ll  ans = (H*W + 1)/2;
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long a[] = new long[n];
    HashMap<Long, Long> num1 = new HashMap<Long, Long>();
    HashMap<Long, Long> num2 = new HashMap<Long, Long>();
    for(int i = 0 ; i < n ; ++i){
      a[i] = sc.nextInt();
      if(!num1.containsKey(a[i])){
        num1.put(a[i],(long)1);
      }else{
        num1.put(a[i],num1.get(a[i])+1);
      }
    }
    long sum = 0;
    long ans = 0;
    
    for(long i : num1.keySet()){
      num2.put(i, num1.get(i) * (num1.get(i)-1) / 2);
      sum += num1.get(i)*(num1.get(i)-1)/ 2;
    }
    for (int i = 0 ; i < n ; ++i) {
      ans = sum-num2.get(a[i])+(num1.get(a[i])-1)*(num1.get(a[i])-2)/2;
      System.out.println(ans);
    }
  }
}

Measured memory_bytes: 82472
import sys
input = sys.stdin.readline
from collections import deque
def main():
    L, R = map(int, input().split())
    ans = 2019
    if R - L >= 2019:
        for i in range(L,L+2019):
            for j in range(L+1,L+2020):
                mod = i*j%2019
                ans = min(ans, mod)
    else:
        for i in range(L,R):
            for j in range(L+1,R+1):
                mod = i*j%2019
                ans = min(ans, mod)
    print(ans) 

if __name__ == '__main__':
    main()

Measured memory_bytes: 38896
#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <math.h>
#define ll long long
using namespace std;

int A[222222];
int M[222222][18];
int INVPOW[222222];


int RMQ(int i, int j) {
    if (i > j)
        return 0;
    int k=INVPOW[j-i+1];
    return min(A[M[i][k]],A[M[j-(1<<k)+1][k]]);
}


int main() {
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>A[i];
    
    for(int i=1;i<222222;i++) {
        int k=0;
        while((1<<(k+1))<=i) {
            k++;
        }
        INVPOW[i]=k;
    }
    
    
    for (int i = 0; i < N; i++)
        M[i][0] = i;
    for (int j = 1; (1 << j) <= N; j++) {
        for (int i = 0; i + (1 << j) - 1 < N; i++) {
            if (A[M[i][j - 1]] <= A[M[i + (1 << (j - 1))][j - 1]])
                M[i][j] = M[i][j - 1];
            else
                M[i][j] = M[i + (1 << (j - 1))][j - 1];
        }
    }


    
    ll answer = 0;
    for(int i=0;i<N;i++) {
        int low = i;
        int high = N-1;
        while(low < high) {
            int mid = (low + high + 1)/2;
            if (RMQ(i,mid)==A[i]) {
                low = mid;
            } else {
                high = mid-1;
            }
        }
        int up = low;
        
        low = 0;
        high = i;
        while(low < high) {
            int mid = (low + high)/2;
            if (RMQ(mid,i)==A[i]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        answer += (ll)(i-low+1)*(ll)(up-i+1)*(ll)A[i];
        
        
    }
    cout << answer << endl;
    
    
    
}

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

long long gcd(long long a, long long b){
  if(b == 0) return a;
  return gcd(b, a%b);
}

int main(){
  int n; cin >> n;
  long long ans;
  cin >> ans;
  for(int i = 1; i < n; i++){
    long long a; cin >> a;
    ans = a / gcd(ans, a) * ans;
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 256
public class Main {


  private static void solve() {
    int n = ni();
    char[] s = ns();
    
    int ret = Integer.MAX_VALUE;
    
    int[] a = new int[n + 1];
    for (int i = n - 1; i >= 0; i --) {
      a[i] = a[i + 1] + (s[i] == '.' ? 1 : 0);
    }
    
    int cnt = 0;
    for (int i = 0; i <= n; i ++) {
      ret = Math.min(a[i] + cnt, ret);
      
      if (i < n && s[i] == '#') {
        cnt ++;
      }
    }
    System.out.println(ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 26836
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <deque>
using namespace std;
#define  ll long long 
#define  N  200009
#define  gep(i,a,b)  for(int  i=a;i<=b;i++)
#define  gepp(i,a,b) for(int  i=a;i>=b;i--)
#define  gep1(i,a,b)  for(ll i=a;i<=b;i++)
#define  gepp1(i,a,b) for(ll i=a;i>=b;i--)	
#define  mem(a,b)  memset(a,b,sizeof(a))
int n,a[N];
ll sum[N],b[N];
int  main()
{
	scanf("%d",&n);
	gep(i,1,n) {
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
		b[i]=b[i-1]^a[i];
	}
	int l=1;
	ll ans=0;
	gep(r,1,n){
		for(;sum[r]-sum[l-1]!=(b[r]^b[l-1]);l++);
		ans+=(r-l+1);
	}
	printf("%lld\n",ans);
	return  0;
}

Measured memory_bytes: 4096
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    string s;
    cin >> s;

    s[0] = '2';
    s[1] = '0';
    s[2] = '1';
    s[3] = '8';
    cout << s << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define infi INT_MAX
#define rinfi INT_MIN
#define inf LLONG_MAX
#define rinf LLONG_MIN
#define ff first
#define ss second
#ifndef ONLINE_JUDGE
#define line cout<<"here - "<<__LINE__<<"\n";
#define dbg(a) cout<<#a<<" --> "<<(a)<<"\n";
#else
#define line
#define dbg(a)
#endif
using namespace std;
main()
{
    //fast
    int tc=1,i,j,k;
    while(tc--)
    {
        int a,b;
        cin>>a>>b;
        int aa[a];
        int ans=0;
        for(i=0;i<a;i++)
            cin>>aa[i],ans=max(ans,aa[i]);
        int low=1,high=ans;
        while(low<=high)
        {
            int mid=(low+high)/2;
            int s=0;
            for(i=0;i<a;i++)
            {
                s+=(aa[i]/mid);
                if(aa[i]%mid==0)
                    s--;
            }
            if(s<=b)
            {
                ans=mid;
                high=mid-1;
            }
            else low=mid+1;
        }
        cout<<ans<<endl;
    }
}




Measured memory_bytes: 5048
#include <iostream>
#define LEFT 0
using namespace std;

int N;
long long int DP[3001][3001]={};
long long int a[3001]={};

long long int solve(int l,int r,int turn){
	if(l>r) return 0;
	if(DP[l][r]) return DP[l][r];
	long long int ret=0;
	
	if(!turn){
		ret=max(a[l]+solve(l+1,r,turn^1),a[r]+solve(l,r-1,turn^1));
	}else{
		ret=min(solve(l+1,r,turn^1)-a[l],solve(l,r-1,turn^1)-a[r]);
	}
	
//	printf("DP[%d][%d]=%d\n",l,r,ret);
	return DP[l][r]=ret;
}

int main(){
	cin>>N;
	for(int i=0;i<N;i++)
		cin>>a[i];
	cout<<solve(0,N-1,0)<<"\n";
	return 0;
}

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

int main() {
  	long long int N;
  	cin >> N;
  
  	long long int res = 0;
  
    for (long long i = 2; i <= N; ++i) {
        if (N % i == 0) {
          	long long int count = 0;
          	while (N % i == 0) {
              	N /= i;
              	count++;
            }
          	for (int i = 0; i < count; i++){
              	res++;
              	count -= i + 1;
            }
        }
      	else if (i * i >= N) {
          	res++;
          	break;
        }
    }
  
  	cout << res << endl;
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Collections;
import java.io.Serializable;

public class Main {
	public static void main(final String[] args){
    
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();

        if(a >= 10 || b >= 10){
            System.out.println(-1);
        }else{
            System.out.println(a*b);
        }
        

        


    }
}

Measured memory_bytes: 21844
# coding: utf-8
# Your code here!
import math
a,b = map(int,input().split())
kou = []
ans = 0
for i in range(10):
    kou.append(b*10 + i)
for i in range(10):
    if (kou[i] * 8)//100 == a:
        print(kou[i])
        ans = 1
        break

if ans == 0:
    print("-1")

Measured memory_bytes: 3060
#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<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 1147483647
#define ll_INF 	9223372036854775807
#define MOD 100000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
using namespace std;

int isGood(int i, int j, vvi& vec){
  int height = pint_INF;
  for(int times; times < 2;times++){
    for(int p = 0; p < vec.size(); p++){
      int temp = vec[p][2] + abs(i-vec[p][0]) + abs(j-vec[p][1]);
      temp < height ? height = temp:1;

      if(temp > height and vec[p][2] != 0){
        return false;
      }
    }
  }

  return height;
}

int main(){
  int N; cin >> N;
  vvi vec(N,vi(3));

  rep(i,N){
    cin >> vec[i][0] >> vec[i][1] >> vec[i][2];
  }
  vi ans(3);
  for(int i = 0; i < 101; i++){
    for(int j = 0; j < 101; j++){
      if(isGood(i,j,vec)){
        if(isGood(i,j,vec) > ans[2]){
          ans = {i,j,isGood(i,j,vec)};
        }
      }
    }
  }

  loopend:

  cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;

}



Measured memory_bytes: 256
unittest
{
	assert( [ "3", "())" ].parse.expand.solve == "(())" );
	assert( [ "6", ")))())" ].parse.expand.solve == "(((()))())" );
	assert( [ "8", "))))((((" ].parse.expand.solve == "(((())))(((())))" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto s = input.front;
	return tuple( s );
}

auto solve( string s )
{
	// ペアが揃っている括弧を消す
	auto d = s.dup;
	auto i = 0L;
	while( i + 1 < d.length )
	{
		if( d[ i ] == '(' && d[ i + 1 ] == ')' )
		{
			d = d[ 0 .. i ] ~ d[ i + 2 .. $ ];
			if( 0 < i ) i--;
		}
		else
		{
			i++;
		}
	}
	
	// 余った')'と'('の数を数える
	auto l = 0L;
	auto r = 0L;
	foreach( c; d )
	{
		if( c == ')' ) l++;
		else           r++;
	}
	
	// 両端に足りない'('と')'を追加
	return '('.repeat( l ).array ~ s ~ ')'.repeat( r ).array;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define IOS                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0);                                                                  \
  cout.tie(0)
#define ll long long int
#define ld long double
#define el '\n'
#define PI (ld)3.141592653589793238462643383279502884197169399375105820974944
#define inf (ll)1000000000
#define mod (ll)1000000007
#define mod1 (ll)998244353
#define fo(i, n) for (long long i = 0; i < int(n); i++)
#define pll pair<ll, ll>
#define mll map<ll,ll>
#define vli vector<pair<ll,int>>
#define vpl vector<pll>
#define vvl vector<vector<ll> >
#define vvpl vector< vector<pll> >
#define ff first
#define ss second
#define pqueue priority_queue< ll >
#define pdqueue priority_queue< ll,vl ,greater< ll > >
#define mem(a,b) memset(a,b,sizeof(a));
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sz(a) (ll)a.size()
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define vl vector<ll>
//#define x ff
//#define y ss
#define pt(a) for(auto it:a)cout<<it<<" ";cout<<endl;
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;

double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }

/*vector<int> parent, rak;

void make_set(int f){
    fo(i,f+1)parent.pb(f);
    rak.assign(f+1,1);
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rak[a] < rak[b])
            swap(a, b);
        parent[b] = a;
        rank[a]+=rank[b];
    }
}*/

long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1;
    ll ans =extend_gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;

    return ans;
}
ll inverse(ll a,ll m){
    ll x,y;
    extend_gcd(m,a,x,y);
    y%=m;
    y+=m;
    y%=m;
    return y;
}

/*const int N = 1000001;
int lp[N+1];
vector<int> pr;
void s(){
for (int i=2; i<=N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back (i);
        }
        for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}*/


ld kv;
ll t,n,x,y,h,k,z,p,q,w;
string s;
//vvl v;
//vl vis,d;

int main() {
    IOS;
    cin>>s;
    fo(i,s.size())kv+=s[i]=='1';
    cout<<sz(s)-abs(2*kv-sz(s));
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

int main(){
    ll N,M;cin>>N>>M;
    vector<ll> d(N+1,0);
    
    for(int i=0;i<N;i++){
        ll x; cin>>x;
        d.at(i+1)=(d.at(i)+x)%M;
    }

    sort(d.begin(),d.end());
    ll memory=0, count=1, ans=0;
    for(int i=1;i<=N;i++){
        if(memory==d.at(i)) count++;
        else{
            ans+=(count-1)*count/2;
            memory=d.at(i);
            count=1;
        }
    }
    ans+=(count-1)*count/2;
    cout<<ans<<endl;
}

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

namespace Contest20191030
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] i = Console.ReadLine().Split().Select(int.Parse).ToArray();

            if (i[0] < 6)
                Console.WriteLine(0);

            else if (i[0] >= 6 && i[0] < 13)
                Console.WriteLine(i[1] / 2);

            else
                Console.WriteLine(i[1]);

        }
    }
}


Measured memory_bytes: 13268
/* Simplicity and Goodness */
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 2e5+2;

void solve()
{
    int n;
    scn(n);

    vi fa(n+1, 0);

    rep(i, 0, n-1) {
        int val;
        scn(val);
        fa[val] ++;
    }

    rep(i, 1, n+1) {
        prin(fa[i]);
    }
}

int main()
{
    int t = 1;
    // scn(t);

    while(t --) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4020
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#define MOD 998244353
#define forn(a, n) for(int a = 0; a<(int) (n); ++a)
#define dforn(a, n) for(int a = (n)-1; a>=0; --a)
#define forall(a, all) for(__typeof(all.begin()) a = all.begin(); a != all.end(); ++a)
#define EPS 0.000000000001
using namespace std;
typedef long long tint;
typedef pair<tint, tint> pii;
typedef vector<tint> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;

int gcd(int a, int b) {
	return b ? gcd(b, a%b) : a;
}

int solvedp(int voy, int k, int tengo, string &s, vvvi &dp) {
	if(voy == -1) {
		return tengo == 0;
	}
	
	if(dp[voy][k][tengo] != -1) {
		return dp[voy][k][tengo];
	}
	
	int next = voy-1;
	while(next >= 0 && s[next] == '1') next--;
	
	tint ans = 0;
	if(s[voy] == '0') {
		forn(i, tengo+1) {
			if(i) {
				ans += solvedp(next, k, tengo-i, s, dp);
				ans %= MOD;
			} else {
				ans += solvedp(voy-1, k, tengo, s, dp);
				ans %= MOD;
			}
		}
	} else {
		if(k) {
			ans += solvedp(voy-1, k-1, tengo+1, s, dp);
			ans %= MOD;
		}
		ans += solvedp(next, k, tengo, s, dp);
		ans %= MOD;
	}
	//cout << voy << " " << k << " " << tengo << " " << next << " " << ans << endl;
	dp[voy][k][tengo] = ans;
	return ans;
}

int main()
{
	string s;
	tint k;
	cin >> s >> k;
	tint n = s.size();
	k = min(k, n);
	
	vvvi dp(n, vvi(k+1, vi(k+1, -1)));
	
	cout << solvedp(n-1, k, 0, s, dp) << endl;
}


Measured memory_bytes: 217720
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
const int mod = 1e9+7;
const int mx = INT_MAX;
const long double pi = 4*atan((long double)1);
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
#define file "gen"
const int mxN=1e5+100;
vi G[mxN];
int val[mxN],n,k;
bool djikstra()
{
	for(int i=0;i<mxN;i++)
		val[i]=-1e18;
	priority_queue<pii> pq;
	for(int i=1;i<=k;i++)
	{
		int v,p;
		cin>>v>>p;
		val[v]=p;
		pq.push(mp(p,v));
	}
	bool check=true;
//	cout<<"here";
	while(!pq.empty())
	{
		int p=pq.top().fi;
		int u=pq.top().se;
		pq.pop();
//		cout<<u<<" "<<p<<endl;
		if(p != val[u])
			continue;
		for(auto v:G[u])
		{
			if(val[v]!=-1e18)
			{
				if(abs(val[v]-p)!=1)
					check=false;
				continue;
			}
			val[v]=p-1;
			pq.push(mp(val[v],v));
		}
	}
	return check;
}
signed main()
{
//    freopen(file".txt","r",stdin);
//    freopen(file".out","w",stdout);
//    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int u,v;
    	cin>>u>>v;
    	G[u].eb(v);
    	G[v].eb(u);	
	}
	cin>>k;
	if(!djikstra())
		return cout<<"No",0;
	cout<<"Yes\n";
	for(int i=1;i<=n;i++)
		cout<<val[i]<<"\n";
}


Measured memory_bytes: 12352
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
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;
}
using namespace std;
int main(){
   int a,b,m;
   cin>>a>>b>>m;
   vector<int> x(a);
   vector<int> y(b);
   int karix=100000,karib=100000;
   rep(i,a){
       cin>>x[i];
       karix=min(x[i],karix);
   }
   rep(i,b){
       cin>>y[i];
       karib=min(karib,y[i]);
   }
   int ans=karix+karib;

   rep(i,m){
       int p,q,r;
       cin>>p>>q>>r;
       int k=x[p-1]+y[q-1]-r;
       ans=min(ans,k);
   }
   cout<<ans;

   
return 0;
}


Measured memory_bytes: 1024
from functools import lru_cache

@lru_cache(maxsize=1<<10)
def solve(p,q,a,n):
  def _solve(num,dem,d,m,s):
    if num==0:
      return 1
    if d == 0:
      return 0
    if num * a //m < dem:
      return 0
    return sum((_solve(num*i-dem, dem*i, d-1, m*i, i) for i in range(s, min(dem*n//num, a//m)+1)),0)
  return _solve(p,q,n,1,1)
ans=[]
while True:
  p,q,a,n=map(int,input().split())
  if p==0:
    break
  ans.append(solve(p,q,a,n))
print(*ans, sep="\n")



Measured memory_bytes: 6576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
#define lb lower_bound
#define ub upper_bound
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);ios::sync_with_stdio(false);



signed main(){
  string s;cin>>s;
  vector<bool> v(4,false);

  rep(i,siz(s)){
    if(s[i]=='N'){
      v[0]=true;
    }else if(s[i]=='S'){
      v[1]=true;
    }else if(s[i]=='W'){
      v[2]=true;
    }else{
      v[3]=true;
    }
  }

  if(v[0]!=v[1] || v[2]!=v[3]){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
  }
}

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

using namespace std;

int main()
{
    int n,a[105];
    cin >> n;
    string s[105];
    map<string,int> mp;
    int cnt = 0,cnt1 = 0;
    for(int i = 0 ; i < n ; i ++){
        cin >> a[i];
        if(a[i] < 400){
            s[i] = "gray";
        }
        else if(a[i] < 800){
            s[i] = "brown";
        }
        else if(a[i] < 1200){
            s[i] = "green";
        }
        else if(a[i] < 1600){
            s[i] = "cyan";
        }
        else if(a[i] < 2000){
            s[i] = "blue";
        }
        else if(a[i] < 2400){
            s[i] = "yellow";
        }
        else if(a[i] < 2800){
            s[i] = "orange";
        }
        else if(a[i] < 3200){
            s[i] = "red";
        }
        else{
            cnt ++;
            s[i] = "a";
        }
        cnt1 += (mp[s[i]] == 0 && s[i] != "a");
        mp[s[i]] ++;
    }
    if(cnt == n){
        cout << 1 << " " << cnt1 + cnt << endl;
        return 0;
    }
    cout << cnt1 << " " << cnt1 + cnt << endl;
    return 0;
}


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

using namespace std;
using ll = long long;

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> L(N + 1);
    int ans = 1;
    for (int i = 1; i <= N; ++i) {
        cin >> L[i];
        L[i] += L[i - 1];

        if (L[i] <= X) {
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 0;

ll n, k, d, a[105], x;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
	
	cin >> n >> k;
	for(ll i = 1; i <= k; i++){
		cin >> d;
		for(ll j = 1; j <= d; j++){
			cin >> x;
			a[x]++;
		}
	}
	ll cnt = 0;
	for(ll i = 1; i <= n; i++){
		if(a[i] == 0){
			cnt++;
		}
	}
	cout << cnt << '\n';
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main(){
    ll n, k;
    cin >> n >> k;
    ll m = n%k;

    if (abs(m-k) < m) cout << abs(m-k) << endl;
    else cout << m << endl;


}

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

class Point{
public:
  double x, y;
  Point(double x=0, double y=0) : x(x), y(y) {}
  Point operator -(Point p) {
    return Point(x-p.x, y-p.y);
  }
};

typedef Point Vector;

double cross(Vector v1, Vector v2) {
  return v1.x*v2.y-v1.y*v2.x;
}

int getL(Point p1, Point p2) {
  return int(abs(p1.x-p2.x) + abs(p1.y-p2.y));
}

bool isEqualOre(double c1[], int l1[], double c2[], int l2[], int cnt) {
  bool flag = true;
  for(int i = 0; i < cnt-2; i++) {
    if(c1[i] != c2[i]) {
      flag = false;
      break;
    }
  }
  if(flag) {
    flag = true;
    for(int i = 0; i < cnt-1; i++) {
      if(l1[i] != l2[i]) {
	flag = false;
	break;
      }
    }
    if(flag) return true;
  }

  for(int i = 0; i < cnt-2; i++) {
    if(c1[i] != -c2[cnt-2-i-1]) {
      return false;
    }
  }
  for(int i = 0; i < cnt-1; i++) {
    if(l1[i] != l2[cnt-1-i-1]) {
      return false;
    }
  }
  return true;
}

main() {
  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;
    int moto_m;
    double moto_cro[10];
    int moto_l[10];
    for(int i = 0; i < n+1; i++) {
      int m;
      double cro[10];
      int l[10];
      cin >> m;
      for(int j = 0; j < m; j++) {
	static Point bfrbfr, bfr;
	Point p;
	cin >> p.x >> p.y;
	if(j >= 1) {
	  if(i == 0)  moto_l[j-1] = getL(p, bfr);
	  else        l[j-1] = getL(p, bfr);
	}
	if(j >= 2) {
	  double tmp = cross(bfr-bfrbfr, p-bfr);
	  //cout << tmp << endl;
	  if(i == 0) moto_cro[j-2] = tmp;
	  else       cro[j-2] = tmp;
	}
	bfrbfr = bfr;
	bfr = p;
      }
      //cout << endl;
      if(i == 0) {
	moto_m = m;
      } else {
	if(moto_m == m && isEqualOre(moto_cro, moto_l, cro, l, m)) cout << i << endl;
      }
    }
    cout << "+++++" << endl;
  }
}

Measured memory_bytes: 0
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

k = int(input())
s = list(input())

if len(s) > k:
    for i in range(k):
        print(s[i], end="")
    print("...")
else:
    s = ''.join(s)
    print(s)

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

using namespace std;

const unsigned long long MOD = 1000000007LL;
long long GCD(long long a, long long b){return b == 0 ? a : GCD(b, a % b);}
long long fast_exp(long long base, long long exp) {
    long long tot = 1;
    for(;exp > 0;exp >>= 1) {
       if((exp & 1) == 1) tot = tot * base % MOD;
       base = base * base % MOD;
    }
    return tot;
}

vector<int> arr;
vector<pair<int, int>> op;

int main(){

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

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

    int n; cin >> n;

    for(int i = 0; i < n; ++i){
        int j; cin >> j;
        arr.push_back(j);
    }

    sort(arr.begin(), arr.end());

    int low = 1, high = arr.size() - 2;

    long long mini = arr[0], maxi = arr[arr.size() - 1];

    while(low <= high){

        if(arr[low] < 0){
            op.push_back(make_pair(maxi, arr[low]));
            maxi -= arr[low++];
        } else {
            op.push_back(make_pair(mini, arr[high]));
            mini -= arr[high--];
        }

    }

    cout << maxi - mini << "\n";

    for(auto i : op){
        cout << i.first << " " << i.second << "\n";
    }

    cout << maxi << " " << mini << "\n";

    return 0;

}


Measured memory_bytes: 3188
#include<cstdio>
using namespace std;
int T,a,b,l,r;
int solve(int l,int r){int s1=(l-1)/(r+1)+1,s2=(r-1)/(l+1)+1;if(s1<s2)s1=s2;return s1?s1:1;}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d",&a,&b,&l,&r);
		int as=solve(a,b);
		int lb=0,rb=1e9,as1=0;
		while(lb<=rb)
		{
			int mid=(lb+rb)>>1,fg=1;
			if(1ll*as*mid>a||mid>b)fg=0;
			if(fg&&solve(a-as*mid,b-mid+1)>as)fg=0;
			if(fg)as1=mid,lb=mid+1;
			else rb=mid-1;
		}
		int tp=as1*(as+1);
		if(l<=tp)for(int i=l;i<=r&&i<=tp;i++)printf("%c",i%(as+1)?'A':'B');
		a-=as*as1,b-=as1;
		l-=tp,r-=tp;if(l<1)l=1;
		lb=0,rb=as,as1=0;
		while(lb<=rb)
		{
			int mid=(lb+rb)>>1,fg=1;
			if(mid>a)fg=0;
			if(fg&&solve(a-mid,b)>as)fg=0;
			if(fg)as1=mid,lb=mid+1;
			else rb=mid-1;
		}
		if(l<=as1)for(int i=l;i<=r&&i<=as1;i++)printf("A");
		a-=as1;l-=as1,r-=as1;if(l<1)l=1;
		lb=0,rb=as,as1=0;
		while(lb<=rb)
		{
			int mid=(lb+rb)>>1,fg=1;
			if(mid>b)fg=0;
			if(fg&&solve(a,b-mid)>as)fg=0;
			if(fg)as1=mid,rb=mid-1;
			else lb=mid+1;
		}
		if(l<=as1)for(int i=l;i<=r&&i<=as1;i++)printf("B");
		b-=as1;l-=as1,r-=as1;if(l<1)l=1;
		int las=b-a*as;
		for(int i=l;i<=las&&i<=r;i++)printf("B");
		r-=las;l-=las;if(l<1)l=1;
		for(int i=l;i<=r;i++)printf("%c",i%(as+1)==1?'A':'B');
		printf("\n");
	}
}//

Measured memory_bytes: 256