akhauriyash/Code-Regression huggingface dataset:
object Main {
  def main(args: Array[String]): Unit = {
    io.Source.stdin.getLines foreach (n => println(pi(n.toInt)))
  }
  val primes: Vector[Int] = (2 #:: Stream.from(3,2).filter(n=> Primes.miller_rabin_test(n))).take(1000).toVector
  val pi_cache: Array[Option[Int]] = Array.fill(1000000)(None)
  val phi_cache: collection.mutable.Map[(Int, Int), Int] = collection.mutable.Map.empty
  def pi(x: Int): Int = pi_cache(x) match {
    case None => {
      if (x < 16) (primes takeWhile(_ <= x)).length
      else {
        val a = pi(Math.sqrt(Math.sqrt(x)).toInt)
        val b = pi(Math.sqrt(x).toInt)
        val c = pi(Math.cbrt(x).toInt)

        var result = phi(x, a) + ((b + a - 2) * (b - a + 1)) / 2
        for (i <- a + 1 to b) {
          val w = x / primes(i - 1)
          val b_i = pi(Math.sqrt(w).toInt)
          result -= pi(w)
          if (i <= c)
            for (j <- i to b_i)
              result = result - pi(w / primes(j - 1)) + j - 1
        }
        pi_cache(x) = Some(result)
        result
      }
    }
    case Some(n) => n
  }
  def phi(x: Int, a:Int): Int =
    phi_cache.getOrElseUpdate(
      (x,a),
      {
        if (a == 1) (x + 1) / 2
        else phi(x, a - 1) - phi(x / primes(a - 1), a - 1)
      }
    )
  object Primes {
    private def mod_exp(x: Int, n: Int, m: Int): Int = {
      def loop(x: Int, n: Int, acc: Int): Int = {
        if (n == 0) acc
        else loop (
          (x * x) % m,
          n >> 1,
          if ((n & 1) == 1) (acc * x) % m else acc
        )
      }
      loop(x,n,1)
    }
    private def div_pow_2(d: Int, s: Int = 0): (Int, Int) ={
      if ((d % 2) != 0) (d,s)
      else div_pow_2(d/2, s+1)
    }
    private def miller_rabin(n: Int, a: Int): Boolean = {
      val (d,s): (Int, Int) = div_pow_2(n-1)
      val a_exp_d: Int = mod_exp(a,d,n)
      def double(x: Int): Int = mod_exp(x,2,n)
      def loop(e: Int, i: Int): Boolean = {
        if (i == 0) false
        else if (e == n-1) true
        else loop(double(e), i-1)
      }
      a_exp_d == 1 || loop(a_exp_d, s)
    }
    def miller_rabin_test(n: Int, k: Int = 20): Boolean = {
      def loop(i: Int): Boolean = {
        if (i == 0) true
        else {
          val a = scala.util.Random.nextInt(n-1)+1
          if (miller_rabin(n,a)) loop(i-1)
          else false
        }
      }
      if (n < 2) false
      else loop(k)
    }
  }
}

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

#define ff first
#define ss second
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define endl "\n"      // Comment in INTERACTIVE(there just use endl which flushes output , no need of fflush(sdtout)).
//  for counting setbits -> __builtin_popcountll(x)
// for counting zerobits -> __builtin_ctzll(x)
#define fastio() ios_base::sync_with_stdio(false);        cin.tie(NULL); //(unties i/o buffer).
            // DON'T USE SCANF/PRINTF WITH IT (c/c++ -> seperates buffer).

const int mod = 1000000007;
const int inf = 1000000009;
const int N = 2*(1e5) + 2;
// int arr[N];
int memo[N];

int jump(int i,vi &h,int k){
    if(memo[i] != -1)
        return memo[i];
        
    if(i == 1)
        return 0;

    int cnt = inf;
    for(int j = 1;j <= k; ++j){
        if(i - j <= 0)
            continue;
        cnt = min(cnt, jump(i - j,h , k) + abs(h[i] - h[i - j]));
    }

    return memo[i] = cnt;
}

int32_t main(){
    fastio();

    // #ifndef ONLINE_JUDGE
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    // #endif

     // ***** AC_chahiye EK BAR MEIN

     // BEGIN CODE HERE
    memset(memo,-1 , sizeof(memo));
    int n , k;
    cin>>n>>k;
    vi h(n+1);
    for(int i = 1;i <= n; ++i)
        cin>>h[i];
    vi dp(n+1,inf);

    dp[1] = 0;
    // for(int i = 3;i <= n; ++i)
    //     dp[i] = min(dp[i - 1] + abs(h[i] - h[i-1])  ,  dp[i - 2] + abs(h[i] - h[i - 2]));
    for(int i = 1;i <= n; ++i){
        for(int j = 1;j <= k ; ++j){
            if(i+j > n)
                continue;
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i] - h[i+j]));
        }
    }
    // cout<<dp[n]<<'\n';
    cout<<jump(n,h,k)<<'\n';
    //getch();
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=acos(-1.0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}
ll gya[1000010];
ll kai[1000010];

void nckinit(ll n,ll md){
  kai[0]=1;
  kai[1]=1;
  for(int i=2;i<=n;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=md;
  }
  gya[n]=gyaku(kai[n],md);
  for(ll i=n-1;i>=1;i--){
    gya[i]=gya[i+1]*(i+1);
    gya[i]%=md;
  }
  gya[0]=1;
}
ll nck(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0||n==k)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  ret*=gya[k];
  ret%=md;
  return ret;
}
ll npk(ll n,ll k,ll md){
  if(k<0)return 0;
  if(k==0)return 1;
  ll ret=kai[n];
  ret*=gya[n-k];
  ret%=md;
  return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll n,a,b,c,d;cin>>n>>a>>b>>c>>d;
    ll dp[n+1][n+1];
    memset(dp,0,sizeof dp);
    nckinit(n+1,mod);
    dp[a-1][0]=1;
    rep(i,a,b+1){
        rep(j,0,n+1){
            if(dp[i-1][j]==0)continue;
            (dp[i][j]+=dp[i-1][j])%=mod;
            ll now=j;
            ll sum=1;
            if(j+i*c>n)continue;
            rep(k,0,c){
                sum*=nck(n-now,i,mod);
                sum%=mod;
                now+=i;
            }
            ll g=c;
            for(;;){
                (dp[i][now]+=(dp[i-1][j]*sum)%mod*gya[g])%=mod;
                if(now+i>n)break;
                if(now+i>j+i*d)break;
                sum*=nck(n-now,i,mod);
                sum%=mod;
                now+=i;
                g++;
            }
        }
    }
    cout<<dp[b][n]<<endl;
}


Measured memory_bytes: 10112
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	if( (n-(n%100))/100 == n%10 ) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    ll a[110];
    cin >> N;
    rep(i,0,N){
        cin >> a[i];
    }
    double ave = 0;
    rep(i,0,N){
        ave += a[i];
    }
    ave /= N;
    ll ans = 0;
    double min_val = 1e9;
    rep(i,0,N){
        if(min_val > abs(ave - a[i])){
            ans = i;
            min_val = abs(ave - a[i]);
        }
    }
    print(ans);

}


Measured memory_bytes: 256
def gcd(v1, v2)
  if v1 < v2
    v1, v2 = v2, v1
  end

  m = v1 % v2
  if m == 0
    r = v2
  else
    r = gcd(v2, m)
  end

  return r
end

n = gets.chomp.to_i
t = gets.chomp.split(' ').map {|v| v.to_i}

vn = gcd(t[0], t[1])
for i in 2...t.length do
  vn = gcd(t[i], vn)
end

puts "#{vn}"


Measured memory_bytes: 9476
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = scan.nextInt();
		}
		Arrays.sort(a);
		int ans = 0;
		for (int i = a.length-1; i > 0; i--) {
			ans = ans + (a[i]-a[i-1]);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21332
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
int tra[10][10];
int ten[4] = { 1000,100,10,1 };
int trans(int n) {
	int res = 0;
	res = tra[res][n / 1000];
	res = tra[res][n / 100 - 10*(n / 1000)];
	res = tra[res][n / 10 - 10*(n / 100)];
	res = tra[res][n - 10*(n / 10)];
	return res;
}
int main() {
	rep(i, 10) {
		rep(j, 10) {
			cin >> tra[i][j];
		}
	}
	int x[10000];
	rep(i, 10000) {
		x[i] = trans(i);
	}
	int cnt = 0;
	rep(i, 10000) {
		int y[4];
		rep(j, 4) {
			y[j] = i / ten[j]-10*(i/(10*ten[j]));
		}
		bool f = false;
		rep(j, 4) {
			rep(k, 10) {
				if (k == y[j])continue;
				int r = i;
				r -= ten[j] * (r / ten[j]-10*(r/(10*ten[j])));
				r += k * ten[j];
				if (tra[x[r]][x[i]]==0) {
					f = true;
				}
				if (f)break;
			}
			if (f)break;
		}
		rep(j, 10) {
			if (x[i] == j)continue;
			if (tra[x[i]][j] == 0)f = true;
		}
		if (y[0] != y[1]) {
			int r = i;
			r %= 100;
			r += 100 * y[0] + 1000 * y[1];
			if (tra[x[r]][x[i]]==0)f = true;
		}
		if (y[1] != y[2]) {
			int r = i;
			r %= 10;
			r += 100 * y[2] + 10 * y[1] + 1000 * y[0];
			if (tra[x[r]][x[i]] == 0)f = true;
		}
		if (y[2] != y[3]) {
			int r = 1000 * y[0] + 100 * y[1] + 10 * y[3] + y[2];
			if (tra[x[r]][x[i]] == 0)f = true;
		}
		if (y[3] != x[i]) {
			int memo = y[3];
			int r = i - memo + x[i];
			if (tra[x[r]][memo] == 0)f = true;
		}
		if (f)cnt++;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3128
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<set>
#include<cctype>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long INF=1LL<<60;

int main(void){
	ios::sync_with_stdio(false); cin.tie(0);
	
	string a;
	cin>>a;
	if(a[0]=='1')a[0]='9';
	else a[0]='1';
	if(a[1]=='1')a[1]='9';
	else a[1]='1';
	if(a[2]=='1')a[2]='9';
	else a[2]='1';
	cout<<a<<endl;
	
	return 0;
}

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

char bd[12][12];

void del(int y, int x) {
    if (0 <= y && y < 12 && 0 <= x && x < 12 && bd[y][x] == '1') {
        bd[y][x] = '0';
        del(y-1, x);
        del(y+1, x);
        del(y, x-1);
        del(y, x+1);
    }
}

int main() {
    while (cin >> bd[0][0]) {
        for (int i=0; i<12; ++i) {
            for (int j=0; j<12; ++j) {
                if (i == 0 && j == 0) continue;
                cin >> bd[i][j];
            }
        }
        int cnt = 0;
        for (int i=0; i<12; ++i) {
            for (int j=0; j<12; ++j) {
                if (bd[i][j] == '1') {
                    del(i, j);
                    cnt ++;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 1144
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    s = SS()

    # 文字同士のindexの隙間の最大値の最小値

    len_s = len(s)

    # 文字毎のindex
    idx = [[] for _ in range(26)]
    for i in range(len_s):
        idx[ord(s[i]) - ord('a')].append(i)

    # 文字毎のindexの間の文字数
    idx_gap = [[] for _ in range(26)]
    for i in range(26):
        if len(idx[i]) >= 1:
            idx_gap[i].append(idx[i][0])
            idx_gap[i].append(len_s - idx[i][-1] - 1)
            if len(idx[i]) >= 2:
                for j in range(len(idx[i]) - 1):
                    idx_gap[i].append(idx[i][j+1] - idx[i][j] - 1)

    print(min([max(i) for i in idx_gap if i]))

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9856
#include <bits/stdc++.h>
#define f first
#define s second
#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)
#define pb push_back
#define all(s) begin(s), end(s)
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(s) int(s.size())
#define ENDL '\n'
using namespace std;
typedef long double ld;
typedef long long lli;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<bool> vb;
#define deb(x) cout << #x": " << (x) << endl;

const int N = 1e3+5;
const lli INF = 1e18;
const lli MOD = 1e9+7;

bool mm[N];
vi primes(1,2);
ld nk[N][N];
void sieve(){
	for(int i = 4; i<N; i+=2)mm[i]=1;
	for(int i = 3; i*i<=N; i+=2)if(!mm[i])for(int j = i*i; j<N; j+=i)mm[j]=1;
	for(int i = 3; i<N; i+=2)if(!mm[i])primes.pb(i);
}

void pascal(){
	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;
	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];
}

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

lli lcm(lli a, lli b){
	if(a<b)swap(a,b);
	lli c = gcd(a,b);
	a/=c;
	return a*b;
}

int popcount(lli x) { return __builtin_popcountll(x); }

lli poww(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = res * a;
		a = a*a;
		b/=2;
	}
	return res;
}

lli powm(lli a, lli b){
	lli res =1;
	while(b){
		if(b&1) res = (res * a)%MOD;
		a = (a*a)%MOD;
		b/=2;
	}
	return res;
}

bool isPrime(lli x){
	if(x==1)return 0;
	for(auto i:primes){
		if(i*i>x)return 1;
		if(x%i==0)return 0;
	}
	return 1;
}

// ---- コーディングはここから！ ('-')7

struct SS{
	int x,y,z;
	SS(int x,int y, int z):x(x),y(y),z(z){}
};
int main(){
	int n,m,k; cin>>n>>m>>k;
	int sx,sy,tx,ty; cin>>sx>>sy>>tx>>ty;
	sx--;sy--;tx--;ty--;
	vector<string>s(n);
	fore(i,0,n)cin>>s[i];
	queue<SS>q;
	vi pos,st;
	pos=st=vi(n*m*4,0);
	auto W = [&](int a, int b, int c){return (a*m+b)*4+c;};
	auto valid = [&](int x, int y){return x>=0 and y>=0 and x<n and y<m and s[x][y]!='@';};
	fore(i,0,4){
		pos[W(sx,sy,i)]=1;
		q.emplace(sx,sy,i);
	}
	int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
	int tt = 0;
	while(!q.empty()){
		queue<SS>co;
		while(!q.empty()){
			auto [x,y,z]=q.front(); q.pop();
			if(st[W(x,y,z)])continue;
			st[W(x,y,z)]=1;
			fore(i,0,k){
				x+=dx[z];
				y+=dy[z];
				if(!valid(x,y))break;
				if(pos[W(x,y,z)])break;
				fore(j,0,4) if(j!=z or i==k-1)co.emplace(x,y,j);
			}
		}
		while(!co.empty()){
			auto [x,y,z]=co.front(); co.pop();
			if(pos[W(x,y,z)])continue;
			q.emplace(x,y,z);
			pos[W(x,y,z)]=1;
		}
		tt++;
		fore(i,0,4)if(pos[W(tx,ty,i)]){cout<<tt<<ENDL; return 0;}

	}
	cout<<-1<<ENDL;

}


Measured memory_bytes: 41936
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
string s;
void solve(){
    stack<char> st;
    int i = 0, n = s.length();
    for(i = 0; i < n; i++){
        if(s[i] == 'S')
            st.push(s[i]);
        else{
            if(st.size() > 0 && st.top() == 'S')
                st.pop();
            else
                st.push(s[i]);
        }
    }
    cout << st.size() << "\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> s;
    solve();
    return 0;
}

Measured memory_bytes: 720
#include <stdio.h>

int main()
{
    char x, y;

    scanf("%c %c", &x, &y);

    if( x > y ) 
        printf( ">\n" );
    else if( x < y ) 
        printf( "<\n" );
    else 
        printf( "=\n" );
    return 0;
}


Measured memory_bytes: 128
import java.io.*;
import java.util.*;

public class Main {
    static int[] height;
    static int[] dp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        height = new int[n+1];
        dp = new int[n+1];
        for(int x = 1; x<=n; x++){
            height[x] = sc.nextInt();
        }
        Arrays.fill(dp, Integer.MAX_VALUE);
        System.out.println(frog(n));
        //System.out.println(Arrays.toString(dp));


    }

    public static int frog(int i){
        if(dp[i] != Integer.MAX_VALUE)
            return dp[i];
        if(i == 2){
            return dp[i] = Math.abs(height[2] - height[1]);
        }
        if(i == 1)
            return dp[i] = 0;
        return dp[i] = Math.min(frog(i-1) + Math.abs(height[i] - height[i-1]), frog(i-2)+ Math.abs(height[i] - height[i-2]));

    }
}


Measured memory_bytes: 73084
#include <stdio.h>
int main(){
	int n, m;
	scanf("%d", &n);
	if(n % 2 == 0){
		m = n;
		printf("%d\n", m);
	}
	else{
		m = n * 2;
			printf("%d\n", m);
	}	
	return 0;
}

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

void solve() {
	int h, w, m; cin >> h >> w >> m;
	map<pair<int, int> , bool> mapp;
	vector<int> row(h), col(w);
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		row[a]++; col[b]++;
		mapp[ {a, b}] = 1;
	}
	int mxrow = *max_element(row.begin(), row.end());
	int mxcol = *max_element(col.begin(), col.end());
	vector<int> roww, coll;
	for (int i = 0; i < h; i++) {
		if (row[i] == mxrow)roww.push_back(i);
	}
	for (int i = 0; i < w; i++) {
		if (col[i] == mxcol)coll.push_back(i);
	}
	for (int i : roww)for (int j : coll) {
			if (!mapp[ {i, j}]) {cout << mxrow + mxcol; return ;}
		}
	cout << mxrow + mxcol - 1 << endl; return ;



}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	// int t; cin >> t;
	// while (t--)
	solve();

}

Measured memory_bytes: 28388
# coding: utf-8
# Your code here!
n=int(input())
def dfs(s):
    if len(s)==n:
        print(s)
    else:
        for i in range(ord("a"),ord(max(s))+1+1): #"a"スタートで、max(s)+1("a"の分)+1(右端)
            dfs(s+chr(i))
dfs("a")


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

cn = 0
SUM = 0

for i in range(len(A)):
    SUM = SUM + A[i]
    
for i in range(len(A)):
    if A[i] >= (SUM / 4 / M):
        cn = cn + 1
    else:
        continue

if cn >= M:
    print('Yes')
else:
    print('No')

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

using namespace std;
using ll = long long;

int maxN = 5000;
vector<ll> dp1(maxN + 10);
vector<ll> dp2(maxN*maxN + 10);

int main() {
	ll N;
	cin >> N;
	vector<ll> A(3), B(3);
	for (int i = 0; i < 3; ++i) { cin >> A[i]; }
	for (int i = 0; i < 3; ++i) { cin >> B[i]; }

	dp1[0] = N;
	for (int i = 1; i <= N; ++i) {
		dp1[i] = dp1[i - 1];
		for (int j = 0; j < 3; ++j) {
			if (i - A[j] >= 0) {
				dp1[i] = max(dp1[i], dp1[i - A[j]] - A[j] + B[j]);
			}
		}
	}

	int n = *max_element(dp1.begin(), dp1.end());
	dp2[0] = n;
	for (int i = 1; i <= n; ++i) {
		dp2[i] = dp2[i - 1];
		for (int j = 0; j < 3; ++j) {
			if (i - B[j] >= 0) {
				dp2[i] = max(dp2[i], dp2[i - B[j]] - B[j] + A[j]);
			}
		}
	}

	cout << dp2[n] << endl;

	return 0;
}


Measured memory_bytes: 195584
/// Author : HASEBUL HASSAN TANIM ///
#include <bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define pb push_back
#define pp pop_back
#define scan(t) scanf("%d",&t)
#define sscan(t) scanf("%lld",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define LL long long
#define ull unsigned long long
#define rock(cont) cont.begin(), cont.end()
#define roll(a,n) arr,arr+n
#define rep(i,n) for(int i=0 ; i<n ; i++)
#define repp(i, n) for(int i=1 ; i<=n ; i++)
#define print(t) printf("%d",t)
#define pprint(t) printf("%lld",t)
#define co(x) cout<<x
#define nl printf("\n")
#define el cout<<endl
#define INF (int)1e9

const int RT = 10000000;

vector<int>prime;
vector<LL>factor;
bitset<10000003> status;



int gcd(LL a,LL b){ return b==0 ? a: gcd(b,a%b);}
int lcm(LL a,LL b) { return a* (b/gcd(a,b));}

vector<int> Divisors(int n)
{
    vector<int> v;
    int limit=sqrt(n);
    for (int i=1; i<=limit; i++)
    {
        if (n%i==0)
        {
            if (n/i == i)
                v.push_back(i);
            else
            {
                v.push_back(i);
                v.push_back(n/i);
            }
        }
    }
    return v;
}

void sieve()
{
    int rt = sqrt(RT);
    //for(int i = 4; i <= rt; i+=2) status[i]=true;
    for(int i = 3; i <= rt; i+=2)
        if(!status[i])
            for(int j = i*i; j < RT; j+=(i<<1))
                status[j] = true;

    prime.push_back(2);

    for(int i = 3; i <= RT; i+=2)
        if(!status[i])
            prime.push_back(i);
}

LL primefac(LL n)
{
    int pf_idx=0,pf=prime[pf_idx],SIZE=prime.size();
    LL ANS=1,step=0;
    while(pf*pf<=n&&pf<SIZE)
    {
        if(n%pf==0)
        {
            while(n%pf==0) {n/=pf;}
            ANS=pf;
            step++;
        }
        pf=prime[++pf_idx];
        //cout<<pf<<" "<<n<<" "<<ANS<<endl;
    }
    if(n!=1) { ANS=max(ANS,n); step++; }
    if(step>1)
    {
      return ANS;
    }
    else
    {
        return -1;
    }
}

int main()
{
    int n,m,x,sum=0;
    scan(n);
    scan(m);
    repp(i,m)
    {
        scan(x);
        sum+=x;
    }
    if(sum>n)
    {
        print(-1);
        el;
    }
    else
    {
        print(n-sum);
        el;
    }
}


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

#define fore(i, a, b) for(int i = a; i < b; i++)
#define forn(i, n) fore(i, 0, n)
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ford(i, n) for(int i = n - 1; i >= 0; i--)

using namespace std;

typedef long long ll;

const int N = 100005;

int main(){

	int n, x;
	map<int, int> cnt;

	scanf("%d", &n);

	forn(i, n) scanf("%d", &x), cnt[x]++;

	int ans = 0;

	for(auto w : cnt){
		if(w.ff > w.ss) ans += w.ss;
		else ans += w.ss - w.ff;
	}
	printf("%d\n", ans);


    return 0;
}


Measured memory_bytes: 4736
#include <stdio.h>
#include <string.h>
int main(void){
  int l,r,n,d;
  n=0;
  scanf("%d %d %d",&l,&r,&d);
  for(int i=0;i<r-l+1;i++){
    if((l+i)%d==0){
      n++;
    }
  }
  printf("%d",n);
  return 0;
}

Measured memory_bytes: 1684
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        char[] s = sc.next().toCharArray();
        char[] ans = new char[n];
        if (isCorrect('S', 'S', ans, s)) {
            System.out.println(String.valueOf(ans));
            return;
        }
        if (isCorrect('S', 'W', ans, s)) {
            System.out.println(String.valueOf(ans));
            return;
        }
        if (isCorrect('W', 'S', ans, s)) {
            System.out.println(String.valueOf(ans));
            return;
        }
        if (isCorrect('W', 'W', ans, s)) {
            System.out.println(String.valueOf(ans));
            return;
        }
        System.out.println(-1);
    }

    private static boolean isCorrect(char c1, char c2, char[] ans, char[] s) {
        ans[0] = c1;
        ans[1] = c2;
        boolean isOK = false;
        for (int i = 1; i < s.length; i++) {
            int idx = i + 1;
            if (i == s.length - 1) {
                idx = 0;
            }
            if (ans[i] == 'S') {
                if (s[i] == 'o') {
                    ans[idx] = ans[i - 1];
                } else if (s[i] == 'x' && ans[i - 1] == 'S') {
                    ans[idx] = 'W';
                } else if (s[i] == 'x' && ans[i - 1] == 'W') {
                    ans[idx] = 'S';
                }
            } else if (ans[i] == 'W') {
                if (s[i] == 'o' && ans[i - 1] == 'S') {
                    ans[idx] = 'W';
                } else if (s[i] == 'o' && ans[i - 1] == 'W') {
                    ans[idx] = 'S';
                } else if (s[i] == 'x') {
                    ans[idx] = ans[i - 1];
                }
            }
            if (i == s.length - 1) {
                if (ans[0] == 'S') {
                    if (s[0] == 'o' && ans[i] == ans[1] && ans[0] == c1) {
                        isOK = true;
                    } else {
                        isOK = (s[0] == 'x' && ans[i] != ans[1] && ans[0] == c1);
                    }
                } else if (ans[0] == 'W') {
                    if (s[0] == 'o' && ans[i] != ans[1] && ans[0] == c1) {
                        isOK = true;
                    } else {
                        isOK = (s[0] == 'x' && ans[i] == ans[1] && ans[0] == c1);
                    }
                }
            }
        }
        return isOK;
    }
}

Measured memory_bytes: 25564
#include <stdio.h>

int main(){
    int i,j,k,n;
    scanf("%d",&n);
    int a[n];
    for (int i = 0; i <n ; ++i) {
        scanf("%d",&a[i]);
    }
    int count,temp,check;
    count=0;
    check=1;
    for (int j = 0; j < n; j++) {
        if(check==0) break;
        check=0;
        for (int k = (n-1); j < k;k--) {
            
            if (a[k]<a[k-1]){
                temp=a[k-1];
                a[k-1]=a[k];
                a[k]=temp;
                count++;
                check=1;

            }
        }
    }
    for(i=0;i<n;i++){

    if(i==(n-1))printf("%d",a[i]);
    else {printf("%d",a[i]);printf(" ");}
    }

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


Measured memory_bytes: 2048
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
use std::cmp::{max,min};
fn main(){
    input!{
        w:i64,
        h:i64,
        x:i64,
        y:i64,
    }
    let s = (w * h) as f64/2.;

    println!("{:.6} {}",s,if x*2 == w && y*2 == h{1}else{0});
}

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

int n, k, m;
int nx[10000], pv[10000];
bool f[10000];

int main()
{
	while (scanf("%d %d %d", &n, &k, &m), n){
		memset(f, 0, sizeof(f));
		for (int i = 0; i < n; i++){
			nx[i] = (i + 1) % n;
			pv[i] = (i - 1 + n) % n;
		}
		
		int p = m - 1;
		for (int i = 0; i < n - 1; i++){
			f[p] = true;
			nx[pv[p]] = nx[p];
			pv[nx[p]] = pv[p];
			for (int j = 0; j < k; j++){
				p = nx[p];
			}
		}
		
		for (int i = 0; i < n; i++){
			if (!f[i]) printf("%d\n", i + 1);
		}
	}
}

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

int main()
{
    long long int n;
    cin >> n;
    map<string,long long int> mp;
    long long int k=0;
    for(long long int i=0;i<n;i++)
    {
        string s;
        cin >> s;
        mp[s]++;
        if(mp[s]>k)
        {
            k=mp[s];
        }
    }
    //cout << k << endl;
    vector<pair<long long int,string> > v;
    for(auto it=mp.begin();it!=mp.end();it++)
    {
        string z;
        long long int p;
        p=it->second;
        z=it->first;
        v.push_back(make_pair(p,z));
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        if(v[i].first==k)
        {
            cout << v[i].second << endl;    
        }
    }
}

Measured memory_bytes: 29680
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <random>
#include <chrono>
using namespace std;

const int maxn = 2e5 + 5;

int a[maxn], b[maxn];
int c[maxn], d[maxn];
int n;

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        scanf("%d", &a[i]);
    } 
    for(int i = 1;i <= n;i++){
        scanf("%d", &b[i]);
    }
    long long ans = 0;
    for(int j = 0;j <= 28;j++){
        int mask = (1 << (j + 1)) - 1;
        int l1 = (1 << j);
        int r1 = mask;
        int l2 = (1 << (j + 2)) - (1 << j);
        int r2 = (1 << (j + 2)) - 1;
        for(int i = 1;i <= n;i++){
            c[i] = a[i] & mask; 
            d[i] = b[i] & mask;
        }
        sort(d + 1, d + 1 + n);
        long long count = 0;
        for(int i = 1;i <= n;i++){
            count += upper_bound(d + 1, d + 1 + n, r1 - c[i]) - lower_bound(d + 1, d + 1 + n, l1 - c[i]);
            count += upper_bound(d + 1, d + 1 + n, r2 - c[i]) - lower_bound(d + 1, d + 1 + n, l2 - c[i]);
        }
        if(count & 1){
            ans |= (1 << j);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define ld double
#define ll long long
#define pb emplace_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) x.begin(),x.end()
ll power(ll a, ll b) {ll res = 1; a = a % mod; while (b) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b /= 2;} return res;}
ll invmod(ll a) {return power(a, mod - 2);}
int main(void)
{
	FIO
	int t = 1;
	// cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		ll arr[n];
		for (auto &i : arr) cin >> i;
		k = min(n, k);
		ll dp[n];
		dp[0] = 0;
		dp[1] = abs(arr[0] - arr[1]);
		// cout << dp[0] << " " << dp[1] << " ";
		for (int i = 2; i < n; i++) {
			dp[i] = 1e18;
			for (int j = max(0, i - k); j < i; j++) {
				dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]));
			}
			// cout << dp[i] << " ";
		}
		// cout << "\n";
		cout << dp[n - 1] << "\n";
	}
	return 0;
}

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

int par[20000];
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unite(int x,int y){
	x=find(x);y=find(y);
	par[x]=y;
}
struct st{
	int a,b;double c;
};
int x[20000],y[20000];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	rep(i,n){
		scanf("%d%d",&x[i],&y[i]);
	}
	vector<st>v;
	double sum=0;
	rep(i,m){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		double d=sqrt(pow(x[p]-x[q],2)+pow(y[p]-y[q],2));
		sum+=d;
		v.push_back({p,q,d});
	}
	sort(v.begin(),v.end(),[](st a,st b){
		return a.c>b.c;
	});
	rep(i,n)par[i]=i;
	for(st&p:v){
		if(find(p.a)==find(p.b))continue;
		sum-=p.c;
		unite(p.a,p.b);
	}
	printf("%.12lf\n",sum);
}


Measured memory_bytes: 3600
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define lli long long int
using namespace std;
#define S second
#define F first
#define pb push_back 
#define M1 1000000007
#define M2 998244353
#define plli pair<lli,lli>
#define setit set<lli>::iterator seti
#define mapit map<lli,lli> ::iterator mapi
#define MP make_pair
#define MT make_tuple
// map      iterator->first  iterator.first
// map      mp[key]=value
// set      *s.begin()
// vector   v[j]=value
// pair     p.first p.second
// vector of pairs v[j].first v[j].second
// tuple    get<index>(tuple_name)
// vector of tuples get<index>(v[j])  sort(v.begin(),v.end())
//priority queue .top() .pop() .push()
// __gcd(x,y)
#define fr(j,a,b) for(j=a;j<b;j++)

int power(int x, unsigned int y, int p)  
{    int res = 1;    
     x = x % p;
     if (x == 0) return 0;
     while (y > 0)  
     {  if (y & 1)  
        res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
     }  
    return res;  
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lli t,i,j,n,x,a,b,c,d,k;
    cin>>k>>a>>b;
    c=a/k;
    d=b/k;
    if(a%k!=0&&b%k!=0&&d-c<1){
        cout<<"NG";
    }
    else{
        cout<<"OK";
    }
}


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

int main(int argc, char const *argv[]) {
  string s;
  int cnt_0 = 0, cnt_1 = 0;
  int ans;
  cin >> s;

  // 0101...
  for (int i = 0; i < s.size(); ++i) {
    if (i % 2 == 0) {
      if ('0' != s[i]) cnt_0++;
    } else {
      if ('1' != s[i]) cnt_0++;
    }
  }

  // 1010...
  for (int j = 0; j < s.size(); ++j) {
    if (j % 2 == 0) {
      if ('1' != s[j]) cnt_1++;
    } else {
      if ('0' != s[j]) cnt_1++;
    }
  }

  ans = min(cnt_0, cnt_1);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			String a = reader.readLine();
			String[] b = a.split(" ");
			int c = Integer.parseInt(b[0]);
			int d = Integer.parseInt(b[1]);
			String[] e = new String[d];
			int[][] f = new int[c][d];
			for (int g = 0; g < c; g++) {
				a = reader.readLine();
				e = a.split(" ");
				for (int h = 0; h < d; h++) {
					f[g][h] = Integer.parseInt(e[h]);
				}
			}
			
			int[] i = new int[d];
			for (int j = 0; j < d; j++) {
				a = reader.readLine();
				i[j] = Integer.parseInt(a);
			}
			int k = 0;
			for (int l = 0; l < c; l++) {
				for (int m = 0; m < d; m++) {
					k += f[l][m] * i[m];
				}
				System.out.println(k);
				k = 0;
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

}

Measured memory_bytes: 27232
fun main(args: Array<String>){
    val N = nextInt()
    val A = listOfLong().toLongArray()
    val B = listOfLong().toLongArray()
    var ans = 0L
    for (n in 0 until N) {
        var x = A[n]
        A[n] = x - Math.min(A[n], B[n])
        x -= A[n]
        var y = A[n + 1]
        A[n + 1] = y - Math.min(A[n + 1], B[n] - x)
        y -= A[n + 1]
        ans += x + y
    }
    println(ans)
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun listOfString() = next().split(" ")
fun listOfLong() = listOfString().map(String::toLong)

Measured memory_bytes: 66540
h, w = map(int, input().split())
S=[]
S.append(["."] * (w + 2))
for i in range(h):
  S.append(["."] + list(input()) + ["."])
S.append(["."] * (w + 2))
 
 
for i in range(1, h+1):
  for j in range(1, w+1):
    counter = 0
    if S[i][j] == ".":
      if S[i-1][j-1] == "#":
        counter += 1
      if S[i-1][j] == "#":
        counter += 1
      if S[i-1][j+1] == "#":
        counter += 1
      if S[i][j-1] == "#":
        counter += 1
      if S[i][j+1] == "#":
        counter += 1
      if S[i+1][j-1] == "#":
        counter += 1
      if S[i+1][j] == "#":
        counter += 1
      if S[i+1][j+1] == "#":
        counter += 1
      S[i][j] = counter
 
for i in range(1,h+1):
  for j in range(1, w+1):
    print(S[i][j], end="")
  print()

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

const int N=1005;
const ll INF=1e18;
int n,m;
vector<P> adj;
vector<int> nxt[N],rev[N];
ll c[N][N],d[N],dp[N];
vector<int> topo;
bool neg[N];

void neg_cycle(){
	for(int i=1;i<=n;++i)
		d[i]=INF;
	d[1]=0;
	for(int i=0;i<n-1;++i){
		for(auto it:adj){
			int u=it.first;
			int v=it.second;
//			if(d[u]==INF) continue;
			if(d[u]+c[u][v]<d[v]) 
				d[v]=d[u]+c[u][v];
		}
	}
	for(int i=0;i<n-1;++i){
		for(auto it:adj){
			int u=it.first;
			int v=it.second;
//			if(d[u]==INF) continue;
			if(d[u]+c[u][v]<d[v]){
				d[v]=d[u]+c[u][v];
				neg[v]=true;
			}
//			neg[v]|=neg[u];
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;++i){
		int u,v;
		ll w;
		cin>>u>>v>>w;
		c[u][v]=-w;
		adj.emplace_back(u,v);
	}
	neg_cycle();
	if(neg[n]) cout<<"inf\n";
	else cout<<-d[n]<<'\n';
}




Measured memory_bytes: 8828
fn main() {
    proconio::input!(n: u32, d: [usize]);
    let ok = d.iter().fold(vec![true; 10], |mut ok, &d| {
        ok[d] = false;
        ok
    });
    let ans = (n..)
        .find(|n| n.to_string().bytes().all(|b| ok[(b - b'0') as usize]))
        .unwrap();
    println!("{}", ans);
}


Measured memory_bytes: 2164
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

from functools import lru_cache


def main(): 
    S = SI()

    print(S[:3] + '8' + S[4:])




main()

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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define pll pair<ll, ll>
#define vll vector<ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  ll N;
  scanf("%lld", &N);

  if (N == 3 || N == 5 || N == 7) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
long long a[MAXN];
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld",a+i);
	long long mn=2,mx=2;
	for(int i=n;i>0;--i){
		mn=(mn-1)/a[i]*a[i]+a[i];
		mx=mx/a[i]*a[i]+a[i]-1;
		if(mn>mx){
			puts("-1");
			return 0;
		}
	}
	cout<<mn<<" "<<mx<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include<vector>
#include<algorithm>
#include<iostream>
#include<utility>
#include<functional>
#include<queue>

using namespace std;

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

int N,M;
vector<pair<int,int> > job;

int main()
{
	cin>>N>>M;

	rep(i,N) {
		int a,b; cin>>a>>b;
		job.push_back(pair<int,int>(a, b));
	}

	sort(begin(job), end(job));

	long long ans = 0;
	priority_queue<int> q;

	int cur = 0;
	for (int d = 1; d <= M; ++d) {
		while (cur < N and job[cur].first <= d) {
			q.push(job[cur].second);
			cur++;
		}
		if (not q.empty()) {
			int a = q.top();
			q.pop();

			ans += a;
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 1908
//テンプレ
#include <bits/stdc++.h>
#define int long long
#define REP(i,n) for(int i = 0; i < (n); ++i)
#define FOR(i,a,b)  for(int i = (a); i <= (b); ++i)
#define ALL(v) (v).begin(),(v).end()

using namespace std;
constexpr int MOD = 10e9+7;
constexpr int INF = 1LL << 60;
template <class T> inline bool chmin(T& a, T b){if(a > b){ a = b; return 1;} return 0;}  
template <class T> inline bool chmax(T& a, T b){if(a < b){ a = b; return 1;} return 0;}  
//




signed main (){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N,A,B;
    cin >> N >> A >> B;
    int P[N];
    REP(i,N) cin >> P[i];
    int a=0,b=0,c=0;
    REP(i,N){
        if(P[i] <= A){
            a++;
        } else if(A +1 <= P[i] && P[i] <= B){
           b++; 
        } else {
            c++;
        }
    }  
    cout << min({a,b,c}) <<endl;
}

Measured memory_bytes: 256
/*
    1) Notice the range of data;
    2) while(scanf) format need to init;
    3) Enough maxn;
    4) delete the freopen;
    5) remember to read this before submit;
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int gcd(int a,int b){if (b == 0) return a; return gcd(b , a%b);}
int lcm(int a, int b){ return a/gcd(a,b)*b;}
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10;
int iszero[maxn];
int all[maxn],tot = 0;
int main(){
    int n = read(),k = read();
    string s;
    cin >> s;
    int cnt = 1;
    for(int i=0; i<s.size()-1; i++){
        if (s[i] == s[i+1]){
            cnt++;
        }else{
            if (s[i] == '0') iszero[tot] = 1;
            all[tot++] = cnt;
            cnt = 1;
        }
    }   
    if (s[s.size()-1] == '0') iszero[tot] = 1;
    all[tot++] = cnt;
    int l = 0, r = 0; cnt = 0;
    int sum = 0,ans = 0;
    while(cnt < k && r < tot){
        if (iszero[r]) cnt++;
        sum += all[r++];
    }
    if (r < tot) sum += all[r];
    ans = sum;
    while(r < tot){
        while(!iszero[l] && l < tot){
            sum -= all[l++];
        }
        sum -= all[l++];
        while(!iszero[r] && r < tot){
            sum += all[r+1]; r++;
        }
        sum += all[r+1]; r++;
        ans = max(ans,sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1666666
int arr[N];
signed main(){
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=8000;i++){
        int t1=floor(i*0.08);
        int t2=floor(i*0.1);
        if(t1==min(n,m)&&t2==max(n,m)){
            cout<<i;return 0;
        }
    }
    cout<<"-1";

    return 0;
}

/*
))((())(

*/

Measured memory_bytes: 256
use std::io::Read;

fn gcd(a : i64, b: i64) -> i64 {
    return if a%b == 0 { b } else { gcd(b, a%b) }
}

fn check(a: i64, b: i64, c: i64, d: i64) -> bool {
    if a < b { return false }
    if d < b { return false }
    if c >= b - 1 { return true }
    let s = a % b;
    if s > c { return false }
    if d%b == 0 { return true }
    let m = gcd(b, d);
    b - m + s%m <= c
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let t = it.next().unwrap().parse::<usize>().unwrap();
    for _ in 0..t {
        let a = it.next().unwrap().parse::<i64>().unwrap();
        let b = it.next().unwrap().parse::<i64>().unwrap();
        let c = it.next().unwrap().parse::<i64>().unwrap();
        let d = it.next().unwrap().parse::<i64>().unwrap();
        println!("{}", if check(a, b, c, d) { "Yes" } else { "No" });
    }
}


Measured memory_bytes: 4352
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
    read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
    match n {
        0 => a,
        _ => {
            a.push(read::<T>());
            read_n_logic(n - 1, a)
        }
    }
}

use std::cmp::{max, min};

fn main() {
    let mut n: i64 = read();
    if n % 2 == 1 {
        println!("{}", 0);
        return;
    }

    let mut ans: i64 = 0;
    let mut x = 10;

    while x <= n {
        ans += n / x;
        x *= 5;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<cstdio>
#include<algorithm>
using std::swap;
typedef long long ll;
//(2^n-1-C(a,n)-C(b,n)) mod 1e9+7
namespace QiFeng233{
	const ll mod=1e9+7;
	ll n,a,b,ans; 
	ll ksm(ll x,ll y){
		ll res=1,tmp=x;
		while(y){
			if(y&1){
				res*=tmp;
				res%=mod;
			}
			tmp*=tmp;
			tmp%=mod;
			y>>=1;
		}
		return res;
	}
	ll lc(ll x,ll y){
		ll res=1;
		for(ll i=x;i<=y;++i){
			res*=i;
			res%=mod;
		}
		return res;
	}
	void solve(){
		scanf("%lld%lld%lld",&n,&a,&b);
		ans=ksm(2,n)-1;
		while(ans<0)ans+=mod;
		ans%=mod;
		ans=ans*lc(1,b);
		ans%=mod;
		ll xa=lc(a+1,b);
		ll ya=lc(n-a+1,n);
		ll ansa=(xa*ya)%mod;
		ans-=ansa;
		while(ans<0)ans+=mod;
		ans%=mod;
		ll ansb=lc(n-b+1,n);
		ans-=ansb;
		while(ans<0)ans+=mod;
		ans%=mod;
		ans*=ksm(lc(1,b),mod-2);
		ans%=mod;
		printf("%lld\n",ans);
	}
}
signed main(){
	QiFeng233::solve();
	return 0;
}

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

int main()
{
    int N = 200001;
    int n;
    cin >> n;;
    int arr[n], hash[N]={0};
    for(int i = 0; i < n ;i++)
    {
        cin >> arr[i];
        hash[arr[i]]++;
    }
    long ans=0;
    for(int i = 0; i < N; i++)
    {
        ans += (long)hash[i] * ((long)hash[i]-1)/2;
    }
    for(int i = 0; i < n; i++)
    {
        cout << ans - (long)(hash[arr[i]])*(hash[arr[i]]-1)/2 +  (long)(hash[arr[i]]-1)*(hash[arr[i]]-2)/2<<endl;
    }
}


Measured memory_bytes: 4096
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;


int main() {
    struct timeval start,end;
    long long span;
    string s;

    gettimeofday(&start,NULL);

    std::cin >> s;
    bool flag = true;
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] == 'A' && s[i+1] == 'C') {
            std::cout << "Yes" << std::endl;
            flag = false;
            break;
        }
    }
    if (flag) {
        std::cout << "No" << std::endl;
    }

    gettimeofday(&end,NULL);
    span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
    std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
    return 0;
}


Measured memory_bytes: 256