akhauriyash/Code-Regression huggingface dataset:
n = int( input() )
c = list( input() )

c = [ "R" ] + c + [ "W" ]
l = 1
r = n
ans = 0
while l < r:
    while c[ l ] == "R":
        l += 1
    while c[ r ] == "W":
        r -= 1
    if l < r:
        c[ l ] = "R"
        c[ r ] = "W"
        ans += 1

print( ans )

Measured memory_bytes: 13600
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

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

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

fn num_of_divisible(n: u64, a: u64, b: u64) -> u64 {
    (n / a) + (n / b) - (n / lcm(a, b))
}

fn main() {
    let v = read_vec::<u64>();
    let a = v[0];
    let b = v[1];
    let c = v[2];
    let d = v[3];

    println!(
        "{}",
        b - num_of_divisible(b, c, d) - (a - 1) + num_of_divisible(a - 1, c, d)
    );
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;

constexpr int MOD = 1e9+7;

namespace math { namespace integer {

template<class T> T mod_mul(T x, T k, T m) { if(k == 0) { return 0; } if(k % 2 == 0) { return mod_mul((x + x) % m, k / 2, m); } else { return (x + mod_mul(x, k - 1, m)) % m; } }
template<class T> T mod_pow(T x, T n, T mod) { if(n == 0) { return 1; } if(n % 2 == 0) { return mod_pow(mod_mul(x, x, mod) % mod, n / 2, mod); } else { return mod_mul(x, mod_pow(x, n - 1, mod), mod); } }
template<class T> T extgcd(T a, T b, T& x, T& y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x;} else { x = 1, y = 0; } return d; }
template<class T> T mod_inverse(T x, T mod) { return mod_pow(x, T(mod - 2), mod); /* use fermat */ }
template<class T> T mod_inverse_composite_num_mod(T a, ll mod) { T x, y; extgcd(a, mod, x, y); return (mod + x % mod) % mod; }

}}
using namespace math::integer;

typedef long long ll;
int const inf = INT_MAX / 2;

namespace sort_algorithm {  // not verified

long long inversion_count(int n, vector<int> const& a) {
  long long ret = 0;
  rep(i, n) REP(j, i + 1, n) {
    ret += a[i] > a[j];
  }
  return ret;
}

}

int main() {
  ll N, K; cin >> N >> K;
  vector<int> A(N); rep(i, N) cin >> A[i];
  // X: A 上の転倒数
  // Y_i: A_i -> A で転倒数
  // X * K + Σ_{l=0}^{N-1} Y_i * (Σ_{k=1}^{K-1} k)

  ll ans = mod_mul(sort_algorithm::inversion_count(N, A), (ll)K, (ll)MOD);

  rep(i, N) {
    vector<int> B;
    ll Y = 0;
    rep(j, N) Y += A[i] > A[j];
    ans += mod_mul((ll)Y, mod_mul(((K - 1) % 2 ? K - 1 : (K - 1) / 2), (K % 2 ? K : K / 2), (ll)MOD), (ll)MOD);
    ans %= MOD;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2019-12-15 04:54:00
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>

using namespace std;

using int64 = long long;
template<class T> ostream& operator<<(ostream& os, vector<T>& _) { os << '{'; for (T& x : _) { os << x; if (&x != &_.back()) os << ','; } os << '}'; return os; }
template<class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif

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

  int64 k, a, b; cin >> k >> a >> b;
  if (a <= b) {
    if (k <= a) {
      cout << 1 << endl;
    } else {
      cout << -1 << endl;
    }
  } else {
    if (k <= a) {
      cout << 1 << endl;
    } else {
      cout << (k - a + (a - b) - 1LL) / (a - b) * 2LL + 1LL << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 256
#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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    cout<<n/3<<endl;
    return 0;
}


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

if abs(A - B) % 2 == 0:
  print(int(abs(A - B) // 2))
else:
  s = min(N - A, A - 1)
  t = min(N - B, B - 1)
  print(int(abs(A - B) // 2) + 1 + min(s, t))



Measured memory_bytes: 3316
#include <stdio.h>

int main(void) {
	int h, n;
	int i, a;
	int sum = 0;
	scanf("%d %d", &h, &n);
	for(i = 0; i < n; i++) {
		scanf("%d", &a);
		sum += a;
	}
	if(sum >= h) {
		printf("Yes\n");
	} else {
		printf("No\n");
	}
	return 0;
}


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

int main()
{
    string hoge;
    getline(cin, hoge);
    int len = hoge.size();
    for (int i=0; i<len; i++)
    {
        char fuga = hoge.at(i);
        if (isupper(fuga))
        {
            hoge.at(i)=tolower(fuga);
        }
        else if (islower(fuga))
        {
            hoge.at(i)=toupper(fuga);
        }
    }
    cout << hoge << endl;
}


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

int main() {
  int n, r;
  cin >> n >> r;
  cout << r + 100 * max(10 - n, 0) << endl;
  return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

template <typename T>
struct Dijkstra {
  private:
    struct edge{
      int to;
      T cost;
      edge(int to,T cost):to(to),cost(cost){}
      bool operator<(const edge &e)const{return cost>e.cost;}
    };
    int n;
    vector<vector<edge> > G;
    vector<T> dist;
    vector<int> preV;
  public:
    Dijkstra(int n_):n(n_),G(n_){};
    void add_edge(int u, int v, T c) {
      assert(u < n);
      assert(v < n);
      G[u].emplace_back(v,c);
    }
    void build(int s) {
      dist.assign(n,numeric_limits<T>::max());
      preV.assign(n,-1);
      dist[s] = 0;
      priority_queue<edge> que;
      que.push(edge(s,0LL));
      while(!que.empty()) {
        auto p = que.top(); que.pop();
        int v = p.to;
        if (dist[v] < p.cost) continue;
        for (auto e:G[v]) {
          if (dist[e.to] > dist[v]+e.cost) {
            dist[e.to] = p.cost+e.cost;
            preV[e.to] = v;
            que.push(edge(e.to,dist[e.to]));
          }
        }
      }
    }
    vector<int> get_path(int to) { 
      vector<int> path;
      for(; to != -1; to = preV[to]){
        path.emplace_back(to);
      }
      reverse(path.begin(), path.end());
      return path;
    }
    T operator[](int k){
      assert(k < n);
      return dist[k];
    }
};

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, m;
  cin >> n >> m;
  Dijkstra<ll> dijkstra(n);
  rep(i,n-1) {
    dijkstra.add_edge(i+1, i, 0);
  }
  rep(i,m) {
    int l,r;
    ll c;
    cin >> l >> r >> c;
    l--; r--;
    dijkstra.add_edge(l,r,c);
  }
  dijkstra.build(0);
  if (dijkstra[n-1] > 1LL<<60) cout << -1 << endl;
  else cout << dijkstra[n-1] << endl;
  return 0;
}

Measured memory_bytes: 10496
/******************************************************************************
 
рассвет. 
 
*******************************************************************************/
#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define rapgame ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define vlli vector <lli>
#define vulli vector <ulli>
#define vchar vector <char>
#define vstr vector <string>
#define vb vector <bool>
#define fst first
#define sec second
#define all(a) (a).begin(),(a).end()
#define srt(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define vpii vector <pair <int,int> >
#define pii pair <int,int> 
#define pll pair <lli,lli> 
#define vplli vector <pair <lli,lli> >
#define vvi vector <vector <int> >
#define vvlli vector <vector <lli> >
#define vvpii vector <vector <pair <int,int>> >
#define fr(i,n) for (int i = 0; i < (n); ++i)
#define frbig(i,n) for (lli i = 0; i < (n); ++i)
#define fra(i,a,n) for (lli i = a; i < (n); ++i)
#define run(c,s) for(auto c:s) 
#define read(n) int n; cin >> n;
#define readchar(n) char n; cin >> n;
#define readstr(n) string n; cin >> n;
#define readarr(a,n) fr(i,n) cin >> a[i];
#define read2(x,y) int x,y; cin >> x >> y;
#define read2ll(x,y) long long int x,y; cin >> x >> y;
#define readll(n) lli n; cin >> n;
#define watch(x) cout << (#x) << " is " << (x) << endl
#define print_array(x) fr(i,x.size()) cout << x[i] << " ";
using namespace std;
 
const lli MOD=1e9+7;
const lli MAXN=2e6;
const lli INF=2e18;
const ld PI=acos(-1);
 
int main(){
    rapgame
    //freopen("brokeday.in", "r", stdin);
    //freopen("richday.out", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--){
        read2(n,m);
        readll(k);
        vlli a(n),b(m),prefa(n+1,0),prefb(m+1,0);
        int ans=0;
        fr(i,n){
            cin >> a[i];
            prefa[i+1]=prefa[i]+a[i];
        }
        fr(i,m){
            cin >> b[i];
            prefb[i+1]=prefb[i]+b[i];
        }
        fr(i,n+1){
            lli cur=k-prefa[i];
            if(cur>=0){
                int j=lower_bound(all(prefb),cur)-prefb.begin();
                if(j!=m+1 && prefa[i]+prefb[j]<=k) ans=max(ans,j+i);
                else ans=max(ans,i+j-1);
            }
        }
        cout << ans;
    }
    return 0;
}

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

const int INF = 1e9 + 5;

int main()
{
    int n, k;
    cin >> n >> k;
    int h[n];
    for (int i = 0; i < n; i++) cin >> h[i];
    vector<int> value(n, INF);
    value[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j <= i+k; j++)
        {
            value[j] = min(value[j], value[i] + abs(h[i] - h[j]));
        }
    }
    cout << value[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstdlib>

int main() {
  std::int_fast64_t n, k;
  std::cin >> n >> k;
  std::vector<std::pair<std::int_fast64_t, std::int_fast64_t>> queries(n);
  for (std::pair<std::int_fast64_t, std::int_fast64_t>& query : queries) {
    std::cin >> query.first >> query.second;
  }
  std::sort(queries.begin(), queries.end(), [](const std::pair<std::int_fast64_t, std::int_fast64_t>& lhs, const std::pair<std::int_fast64_t, std::int_fast64_t>& rhs) {
    return lhs.first < rhs.first;
  });
  for (const std::pair<std::int_fast64_t, std::int_fast64_t>& query : queries) {
    k -= query.second;
    if (k <= 0) {
      std::cout << query.first << std::endl;
      return 0;
    }
  }
  return EXIT_FAILURE;
}

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

int che(int x) {
    int num = 0;
    for (int i = 1; i <= x; i++) if (x % i == 0) {
        num++;
    }
    return num;
}

int main() {
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i += 2) if (che(i) == 8) {
        ans++;
        // cout << i << endl;
    }

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

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cnt;
int n,s;

void dfs(int left,int sum,int idx){
	if(left==0){
		if(sum==s)
			cnt++;
		return;
	}
	else if(sum > s)
		return;

	for(int i = idx+1; i <= 9; i++){
		dfs(left-1,sum+i,i);
	}
}

int main(){

	while(cin>>n>>s&&!(n==0&&s==0)){
		cnt=0;
		dfs(n,0,-1);
		cout<<cnt<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

constexpr int MAX_N = 100000;
constexpr int LIMIT = 50;

int main() {
	vector<double> get_p(LIMIT);
	for(int i = 0; i < LIMIT; ++i) {
		get_p[i] = pow(0.5, i);
	}

	vector<vector<double>> dp(MAX_N + 1, vector<double>(LIMIT + 1, 0.0));
	vector<double> ans(MAX_N + 1, 0.0);
	dp[0][0] = 1.0;

	for(int i = 0; i < MAX_N; ++i) {
		double cnt = 0.0;
		for(int j = 0; j < LIMIT; ++j) {
			dp[i + 1][j + 1] += get_p[j] * dp[i][j];
			dp[i + 1][0] += (1.0 - get_p[j]) * dp[i][j];
			cnt += get_p[j] * dp[i][j];
		}
		ans[i + 1] = ans[i] + cnt;
	}

	for(int n; scanf("%d", &n) == 1 && n;) printf("%.10lf\n", ans[n]);

	return EXIT_SUCCESS;
}

Measured memory_bytes: 44824
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

//関数宣言
//int func(int x, int y);

int main(void){

  //スカラー入力
  int M,N;

  scanf("%d %d", &M, &N);

  if(M>=13){
    printf("%d\n",N);
  }else if(M<=5){
    printf("0\n");
  }else{
    printf("%d\n",N/2);
  }

  return 0;
}


Measured memory_bytes: 128
N, *A = map(int, open(0).read().split())
rising_terms = []
tmp = []
for i in range(N - 1):
    if A[i] < A[i + 1]:
        tmp.append(A[i])
    elif tmp:
        rising_terms.append(tmp + [A[i]])
        tmp = []
if A[N - 2] < A[N - 1]:
    rising_terms.append(tmp + [A[N - 1]])
ans = 1000
for rising_term in rising_terms:
    stock, r_money = divmod(ans, rising_term[0])
    ans = r_money + stock * rising_term[-1]
print(ans)


Measured memory_bytes: 9204
n,m = map(int, input().split())
s_c = [tuple(map(int, input().split())) for _ in range(m)]

ans = -1

for num in range(1000):
    if len(str(num)) != n: continue

    for s,c in s_c:
        if str(num)[s-1] != str(c):
            break
    else:
        ans = num
        break

print(ans)


Measured memory_bytes: 9136
#include<bits/stdc++.h>
#define N (409)
#define LL long long
#define MOD (1000000007)
using namespace std;

LL n,c,a[N],b[N],f[N][N],p[N][N],sum[N][N];

void Init()
{
	for (int i=1; i<=400; ++i)
	{
		p[i][0]=1; sum[i][0]=1;
		for (int j=1; j<=400; ++j) p[i][j]=p[i][j-1]*i%MOD;
	}
	for (int i=1; i<=400; ++i)
		for (int j=0; j<=400; ++j)
			sum[i][j]=(sum[i-1][j]+p[i][j])%MOD;
}

int main()
{
	Init();
	cin>>n>>c;
	for (int i=1; i<=n; ++i) cin>>a[i];
	for (int i=1; i<=n; ++i) cin>>b[i];
	f[0][0]=1;
	for (int i=1; i<=n; ++i)
		for (int j=0; j<=c; ++j)
			for (int k=0; k<=j; ++k)
			{
				LL t=(sum[b[i]][k]-sum[a[i]-1][k]+MOD)%MOD;
				(f[i][j]+=f[i-1][j-k]*t)%=MOD;
			}
	cout<<f[n][c]<<endl;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define pi 3.14159265358979323846264338327950L
using namespace std;

int main() {
  int64_t N, ans=0;
  cin >> N;
  vector<int64_t> a(N);
  vector<int64_t> b(N);
  for (int64_t i=0; i<N; i++) {
    cin >> a[i];
    b[i]=0;
  }
  for (int64_t i=0; i<N; i++) {
    for (int64_t j=1; j<31; j++) {
      if (a[i]%2==0) {
        a[i]=a[i]/2;
        b[i]++;
      }
      else {
        break;
      }
    }
    ans=ans+b[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 3768
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <stack>
#include <queue>
#include <set>

#define mod 1000000007
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    string S;
    cin >> S;
    if(S[0] == S[1] && S[1] == S[2] && S[0] == 'R') cout << 3;
    else if(S[0] == S[1] && S[1] == S[2] && S[0] == 'S') cout << 0;
    else if(S[0] == S[1] && S[1] == 'R' || (S[2] == S[1] &&  S[2] == 'R')) cout << 2;
    else cout << 1;
    return 0;
}

Measured memory_bytes: 3620
n = input()
m = n.split()

a = [input() for l in range(0,1)]
b = a[0].split()


for i in range(0, len(b)):
    b[i] = int(b[i])

c = sorted(b, reverse=True)

p = 0
for i in range(int(m[0]) - int(m[1]),int(m[0])):
    p = p + int(c[i])
print(int(p))

Measured memory_bytes: 9164
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/doubling.hpp"
#include <cmath>
#include <vector>

#ifndef DOUBLING
#define DOUBLING
// ダブリングを行う、最初の要素が入った配列を渡すとダブリングしたものを返す
// no_valueには存在しない場合何を入れればいいのかを入れておく
template <class T> std::vector<std::vector<T>> doubling(std::vector<T> &init, T no_value) {
  int size = init.size();
  int doubling_size = std::floor(std::log2(size) + 1);
  std::vector<std::vector<T>> ret(doubling_size, std::vector<T>(size));

  for (int i = 0; i < size; i++) {
    ret[0][i] = init[i];
  }

  for (int k = 0; k < doubling_size - 1; k++) {
    for (int i = 0; i < size; i++) {
      if (ret[k][i] == no_value) {
        ret[k + 1][i] = no_value;
      } else {
        ret[k + 1][i] = ret[k][ret[k][i]];
      }
    }
  }
  return ret;
}
#endif
#line 1 "/mnt/c/Users/leafc/dev/compro/lib/template.hpp"


#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
#define MM << " " <<

using namespace std;

template <class T> void say(bool val, T yes = "Yes", T no = "No") { cout << (val ? yes : no) << "\n"; }

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

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


#line 3 "tmp.cpp"

bool f(int a, int b, int mid, vector<vector<int>> &db) {
  int cur = a;
  int cnt = 0;
  while (mid > 0) {
    if (mid % 2 == 1) {
      cur = db[cnt][cur];
    }
    if (cur >= b)
      return true;
    cnt++;
    mid /= 2;
  }
  return false;
}

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

  int n;
  cin >> n;
  vi x(n + 1);
  REP(i, n) { cin >> x[i]; }
  int l;
  cin >> l;

  x[n] = 1e9 + 1;
  vi next(n, n);
  REP(i, n) { next[i] = upper_bound(ALL(x), x[i] + l) - x.begin() - 1; }
  auto db = doubling(next, n);

  int q;
  cin >> q;
  REP(i, q) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (a > b)
      swap(a, b);
    int ok = n;
    int ng = 0;
    while (abs(ok - ng) > 1) {
      int mid = (ok + ng) / 2;
      if (f(a, b, mid, db)) {
        ok = mid;
      } else {
        ng = mid;
      }
    }
    cout << ok << endl;
  }
  return 0;
}


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

int main(){
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    int ans = 1001001001;
    for(int ab = 0; ab <= 2*x || ab <= 2*y; ab += 2){
        int coans = ab*c;
        if((x-ab/2)*a > 0) coans += (x-ab/2)*a;
        if((y-ab/2)*b > 0) coans += (y-ab/2)*b;
        if(ans > coans) ans = coans;
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;
vector<int> a, b, c, d;

void memorize(int aa, int bb, int cc, int dd) {
  a.push_back(aa + 1);
  b.push_back(bb + 1);
  c.push_back(cc + 1);
  d.push_back(dd + 1);
}

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>> av(h, vector<int>(w));
  rep(i, h)rep(j, w) cin >> av[i][j];
  int cur = 0;

  rep(i, h) {
    cur %= 2;
    if(i % 2 == 0) {
      for (int j = 0; j < w; ++j) {
        if(i == h - 1 && j == w - 1) break;
        cur += av[i][j];
        if(!(cur % 2)) continue;
        if(j == w - 1) {
          memorize(i, j, i + 1, j);
        } else {
          memorize(i, j, i, j + 1);
        }
      }
    } else {
      for (int j = w - 1; j >= 0; --j){
        if(i == h - 1 && j == 0) break;
        cur += av[i][j];
        if(!(cur % 2)) continue;
        if(j == 0) {
          memorize(i, j, i + 1, j);
        } else {
          memorize(i, j, i, j - 1);
        }
      }
    }
  }

  cout << a.size() << endl;
  rep(i, a.size()) {
    cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << endl;
  }
}

Measured memory_bytes: 5224
// ######      ###      #######    #######    ##     #     #####        ###     ##### //
// #     #    #   #          #        #       # #    #    #     #      #   #     ###  //
// #     #   #     #        #         #       #  #   #   #       #    #     #    ###  //
// ######   #########      #          #       #   #  #   #           #########    #   //
// #     #  #       #     #           #       #    # #   #    ####   #       #    #   //
// #     #  #       #    #            #       #     ##   #    #  #   #       #        //
// ######   #       #   #######    #######    #      #    #####  #   #       #    #   //

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(ll i=0;i<(n);++i)
#define FOR(i,a,b) for(ll i=(a);i<=(b);++i)
#define FORD(i,a,b) for(ll i=(a);i>=(b);--i)
#define cases ll T=0;cin>>T;while(T--)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define END "\n"
#define pb push_back
#define go(c,itr) for(auto itr=(c).begin(); itr!=(c).end(); ++itr)
#define back(c,itr) for(auto itr=(c).rbegin(); itr!=(c).rend(); ++itr)
#define PI 3.14159265359
#define inf 9e18
#define MOD 1000000007
#define MODU 998244353
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAXN 1000005
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const ll N = 1e9;
ll binexp(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
void task(bool flag)
{
	if (flag)
		cout << "YES\n";
	else
		cout << "NO\n";
}
string s, t;
ll dp[3005][3005];
ll lcs(ll i, ll j)
{
	if (i >= s.length() || j >= t.length())
		return 0;
	if (dp[i][j] != -1)
		return dp[i][j];
	if (s[i] == t[j])
		return dp[i][j] = 1 + lcs(i + 1, j + 1);
	else
	{
		ll left = lcs(i + 1, j);
		ll right = lcs(i, j + 1);
		return dp[i][j] = max(left, right);
	}
}
queue<char> ans;
void solve(ll i, ll j)
{
	if (i >= s.length() || j >= t.length())
		return;
	if (s[i] == t[j])
	{
		ans.push(s[i]);
		solve(i + 1, j + 1);
		return;
	}
	else
	{
		if (lcs(i + 1, j) > lcs(i, j + 1))
			solve(i + 1, j);
		else
			solve(i, j + 1);
	}
}
signed main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	fast
	memset(dp, -1, sizeof(dp));
	cin >> s >> t;
	solve(0, 0);
	// cout << ans.size() << END;
	while (!ans.empty())
		cout << ans.front() , ans.pop();



// #ifndef ONLINE_JUDGE
// 	cout << "\nTime Elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " sec\n";
// #endif
	return 0;
}


Measured memory_bytes: 71040
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let q: usize = sc.read();

    let mut s = sc.chars();
    let mut queries = (0..q)
        .map(|_| (sc.chars()[0], sc.chars()[0]))
        .collect::<Vec<_>>();

    let left = solve(&queries, &s);
    queries = queries
        .into_iter()
        .map(|(t, d)| (t, if d == 'R' { 'L' } else { 'R' }))
        .collect();
    s.reverse();
    let right = solve(&queries, &s);
    let rest = n as i32 - (left + 1) - (right + 1);
    println!("{}", rest);
}

fn solve(queries: &Vec<(char, char)>, s: &Vec<char>) -> i32 {
    let n = s.len();
    let mut ok: i32 = -1;
    let mut ng: i32 = n as i32;
    while ng - ok > 1 {
        let m = (ok + ng) / 2;
        assert!(m >= 0);
        let mut cur = m;
        for &(t, d) in queries.iter() {
            if s[cur as usize] == t {
                match d {
                    'R' => {
                        cur += 1;
                    }
                    'L' => {
                        cur -= 1;
                    }
                    _ => unreachable!(),
                }
            }
            if cur < 0 || cur >= n as i32 {
                break;
            }
        }
        if cur < 0 {
            ok = m;
        } else {
            ng = m;
        }
    }
    ok
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 8444
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MN 200005
using namespace std;
typedef long long ll;
int n,q;
ll mk[MN<<2];
struct node{
	ll mi[4];
	friend node operator+(node x,node y){
		node z;
		for(int i=1;i<=3;i++)z.mi[i]=min(x.mi[i],y.mi[i]);
		return z;
	}
}T[MN<<2];
void uadd(int v){for(int i=1;i<=3;i++)T[1].mi[i]+=v;mk[1]+=v;}
void pushdown(int k,int l,int r){
	mk[k<<1]+=mk[k],mk[k<<1|1]+=mk[k];
	for(int i=1;i<=3;i++)T[k<<1].mi[i]+=mk[k],T[k<<1|1].mi[i]+=mk[k];mk[k]=0;
}
void update(int l,int r,int a,int k,ll ad){
	if(l==r)return (void)(T[k].mi[1]>ad?(T[k].mi[1]=ad,T[k].mi[2]=ad-l,T[k].mi[3]=ad+l):0);if(mk[k])pushdown(k,l,r);int mid=(l+r)>>1;
	if(a<=mid)update(l,mid,a,k<<1,ad);else update(mid+1,r,a,k<<1|1,ad);T[k]=T[k<<1]+T[k<<1|1];
}
ll que1(int l,int r,int a,int b,int k){
	if(l==a&&r==b)return T[k].mi[2];if(mk[k])pushdown(k,l,r);int mid=(l+r)>>1;
	if(b<=mid)return que1(l,mid,a,b,k<<1);if(a>mid)return que1(mid+1,r,a,b,k<<1|1);
	return min(que1(l,mid,a,mid,k<<1),que1(mid+1,r,mid+1,b,k<<1|1));
}
ll que2(int l,int r,int a,int b,int k){
	if(l==a&&r==b)return T[k].mi[3];if(mk[k])pushdown(k,l,r);int mid=(l+r)>>1;
	if(b<=mid)return que2(l,mid,a,b,k<<1);if(a>mid)return que2(mid+1,r,a,b,k<<1|1);
	return min(que2(l,mid,a,mid,k<<1),que2(mid+1,r,mid+1,b,k<<1|1));
}
void build(int l,int r,int k){
	if(l==r)return (void)(T[k].mi[1]=T[k].mi[2]=T[k].mi[3]=1e18);int mid=(l+r)>>1;
	build(l,mid,k<<1);build(mid+1,r,k<<1|1);T[k]=T[k<<1]+T[k<<1|1];
}
int main(){
	int a,b;scanf("%d%d%d%d",&n,&q,&a,&b);build(1,n,1);
	update(1,n,b,1,0);
	int lst=a,x;
	for(int i=1;i<=q;i++){
		scanf("%d",&x);
		ll tmp=min(que1(1,n,1,x,1)+x,que2(1,n,x,n,1)-x);
		uadd(abs(x-lst));update(1,n,lst,1,tmp);lst=x;
	}printf("%lld\n",T[1].mi[1]);
}

Measured memory_bytes: 24704
#include <stdio.h>
#include <math.h>

int main() {
  int i, n, num, min=1000000, max=-1000000;
  long long int sum=0;
  scanf("%d", &n);
  for(i=0; i < n; i++) {
    scanf("%d", &num);
    min = fmin(min, num);
    max = fmax(max, num);
    sum += num;
  }
  printf("%d %d %lld\n", min, max, sum);
  return 0;
}


Measured memory_bytes: 2140
#include<stdio.h>


int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    int a[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 0, j = k; j < n; i++, j++) {
        if(a[i] < a[j]) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
}

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

///******************************** C o n t a i n e r ********************************///

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

///*********************************** C o n s t ***********************************///

const int       N=1e6+3;
const double    PI = acos(-1);

ll dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
ll dy[] = {0, +1, 0, -1, +1, -1, +1, -1};

///********************************** M a r c o ***********************************///

#define pb push_back
#define F first
#define S second
#define test int tc; cin>>tc; while(tc--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) x.size()
#define el <<'\n'

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(0); cout.setf(ios::fixed,ios::floatfield);

///*********************************** F u n c t i o n ***********************************///

ll powmod(ll a,ll b){if(!a) return 0;ll pr=1;while(b>0){if(b&1){pr*=a;--b;}a*=a;b/=2;}return pr;}
bool isPrime(ll n){ if(n<=1)return false;if(n<=3)return true;if(n%2==0 or n%3==0)return false;for(ll i=5;i*i<=n;i+=6){if(n%i==0 or n%(i+2)==0)return false;}return true;}
///**************************************************** C o d e ****************************************************///
///-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=///
bool a[1000005]; vl v;
void seive(){
    ll mx=sqrt(1000005),ii,jj;
    for(ii=3;ii<=mx;ii+=2)
        if(!a[ii])
            for(jj=ii*ii;jj<1000004;jj+=2*ii) a[jj]=true;
    v.pb(2);
    for(ii=3;ii<1000004;ii+=2)if(!a[ii]) v.pb(ii);
}



void _case()
{
    ll n,i,ans=0,y;
    cin>>n;
    y=sz(v);
    map<ll,ll> m;
    m[1]++;
    for(i=0;i<y and v[i]<=n;i++){
        if(n%v[i]==0){
            ll cnt=0,j=v[i];
            while(n%j==0){
                cnt++;
                n/=j;
            }
            ans+=(-1+sqrt(1+8*cnt))/2;
        }
    }
    if(!m[n]) ans++;
    cout<<ans el;
}

main()
{
    seive();
        _case();

}


///Thank you.


///Brainless_Loco Terminates Here!


Measured memory_bytes: 5068
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265359

//階乗
ll factorial(ll num){ll sum = 1; for(ll i=1;i<=num;i++) sum*=i; return sum;}
//素数判定
bool isPrime(ll num){if(num<2){return false;}else if(num==2){return true;}else if(num%2==0){return false;} double sqrtNum=sqrt(num);for(int i=3;i<=sqrtNum;i+=2){if(num%i==0)return false;}return true;}

int main(){
  ll a,b;
  cin >> a >> b;
  
  ll tap = 1;
  ll ans = 0;
  while(tap<b){
    tap += a-1;
    ans++;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3680
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n; rd(n);
  struct P{int x, y, idx;}
  auto ps=new P[](n);
  foreach(i; 0..n){
    rd(ps[i].x, ps[i].y);
    ps[i].idx=i;
  }

  struct E{int u, v; long cost;}
  E[] edges;
  sort!((l, r)=>(l.x==r.x ? l.y<r.y : l.x<r.x))(ps);
  import std.math;
  for(int i=1; i<n; i++){
    auto d=min((ps[i-1].x-ps[i].x).abs, (ps[i-1].y-ps[i].y).abs);
    edges~=E(ps[i-1].idx, ps[i].idx, d);
  }
  sort!((l, r)=>(l.y==r.y ? l.x<r.x : l.y<r.y))(ps);
  for(int i=1; i<n; i++){
    auto d=min((ps[i-1].x-ps[i].x).abs, (ps[i-1].y-ps[i].y).abs);
    edges~=E(ps[i-1].idx, ps[i].idx, d);
  }
  sort!((l, r)=>(l.cost<r.cost))(edges);
  auto uf=new UnionFind(n);
  long tot=0;
  foreach(e; edges){
    if(uf.same(e.u, e.v)==false){
      uf.unite(e.u, e.v);
      tot+=e.cost;
    }
  }
  writeln(tot);
}

class UnionFind{
  int[] par;
  this(int n){
    par.length=n;
    foreach(i; 0..n) par[i]=i;
  }
  int find(int i){
    return par[i]=(i==par[i] ? par[i] : find(par[i]));
  }
  void unite(int i, int j){
    par[find(i)]=find(j);
  }
  bool same(int i, int j){
    return find(i)==find(j);
  }
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x) e=l[i].to!(typeof(e));
}


Measured memory_bytes: 12028
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(r, &n)
	as := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &as[i])
	}

	// 山1に降った量/2を固定する（算出する）
	x := 0
	for i := 0; i < n; i++ {
		if i%2 == 0 {
			x += as[i]
		} else {
			x -= as[i]
		}
	}

	ans := make([]int, n)
	ans[0] = x / 2
	for i := 0; i < n-1; i++ {
		ans[i+1] = as[i] - ans[i]
	}
	for i := 0; i < n; i++ {
		ans[i] *= 2
	}

	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	for i := 0; i < n; i++ {
		fmt.Fprintf(w, "%d ", ans[i])
	}

}


Measured memory_bytes: 5760
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;

vector<long long > yakusuu (long long x) {
  vector<long long> answer;
  for (long long i = 1; i <= (long long) sqrt(x); i++) {
    if (x % i == 0) {
      answer.push_back(i);
      if (i != x / i) {
        answer.push_back(x / i);    
      }
    }  
  }  
  return answer;
}

set<long long > yakusuu_ (long long x) {
  set<long long> answer;
  for (long long i = 1; i <= (long long) sqrt(x); i++) {
    if (x % i == 0) {
      answer.insert(i);
      if (i != x / i) {
        answer.insert(x / i);    
      }
    }  
  }  
  return answer;
}


int main () {
    vector<long long> N;
    set<long long> M;
    long long n, m;
    long long sub_n, sub_m;
    cin >> n >> m;
    N = yakusuu(n);
    M = yakusuu_(m);
    // string S, T;
    char S[n];
    char T[m];
    cin >> S >> T;
    long long pp = n * m;
    sub_n = n;
    sub_m = m;
    if (sub_n < sub_m) {
      long long tmp = sub_n;
      sub_n = sub_m;
      sub_m = tmp;  
    }
    long long r = sub_n % sub_m;
    while(r!=0) {
      sub_n = sub_m;
      sub_m = r;
      r = sub_n % sub_m;
    } 
    long long answer = pp / sub_m;
    map<long long, char> last;
    for (long long i = 0; i < n; i++) {
      last[i * answer / n] = S[i];    
    }
    for (long long i = 0; i < m; i++) {
      if (last[i * answer / m] > 0) {
        if (last[i * answer / m] == T[i]) {
          //ok 
        }  
        else {
          cout << -1 << endl;
          return 0;  
        }
      }  
      if (i == m - 1) {
        cout << answer << endl;  
      }
    }

}

Measured memory_bytes: 10752
import sys

N, K = map(int, input().split())
B = list(map(int, sys.stdin.readline().rsplit()))

res = 10 ** 18
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        # print(bin(i), bin(i >> j))
        if (i >> j) & 1:
            cnt += 1
    # print(cnt)
    if cnt != K:
        continue
    
    A = B[::]
    cnt = 0
    maxi = A[0] - 1
    for j in range(N):
        if (i >> j) & 1:
            if A[j] <= maxi:
                cnt += (maxi + 1) - A[j]
                A[j] = maxi + 1

        maxi = max(maxi, A[j])

    res = min(res, cnt)

print(res)
# print(A)


Measured memory_bytes: 9188
#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<queue>
#include<set>
#include<stack>
#include<map>

using namespace std;

int main(){
    int N,M;
    int sum=0;
    map<int,int> mp;//keyは0以上M未満の整数，値はその数が出てきた回数
    cin>>N>>M;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        if(i>0){
            sum=(sum+a)%M;
        }else{
            sum=a%M;
        }
        auto it=mp.find(sum);
        if(it != mp.end()){
            mp[sum]++;
        }else{
            mp.insert(make_pair(sum,1));
        }
    }
    /*
    for(auto it=mp.begin();it!=mp.end();it++){
        cout << "key = " << it->first << ", val = " << it->second << endl;
    }
     */
    long long ans=0;
    for(auto it=mp.begin();it!=mp.end();it++){
        int key=it->first;
        int val=it->second;
        ans += (long long) val*(val-1)/2;
        if(key==0) ans += (long long) val;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3200
//2018.11.25
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

int main() {
    int n, m;
    int p[100100], y[100100];
    vector<int> yd[100100];
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> p[i] >> y[i];
        yd[p[i]].push_back(y[i]);
    }

    for (int i = 0; i < n; i++) {
        sort(yd[i + 1].begin(), yd[i + 1].end()); //pは１以上だから
    }

    for (int i = 0; i < m; i++) {
        cout << setfill('0') << right << setw(6) << p[i] << setfill('0') << right << setw(6) << (int)(lower_bound(yd[p[i]].begin(), yd[p[i]].end(), y[i]) - yd[p[i]].begin()) + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 7808
#include<bits/stdc++.h>
#include<map>
#include<bitset>
#define MOD 1000000007
#define md 998244353
#define INF LLONG_MAX
#define F first
#define S second
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define sz(x) (long long)x.size()
#define vi vector<int>
#define vll vector<long long>
#define vpl vector<pair<long long,long long> >
#define vpi vector<pair<int,int> >
#define pb push_back
#define debug(x) cerr<<#x<<"= "<<x<<endl
#define all(v) v.begin(),v.end()
#define TT ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define SORTA(v) sort(v.begin(),v.end())
#define SORTD(v) sort(v.begin(),v.end(),greater<int>())
#define REV(v) reverse(v.begin(),v.end())
#define MAXN 200005
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)
typedef long long ll;
typedef long double ld;
using namespace std;

ll BigMod(ll base,ll pow,ll mod)
{
    if(pow==0||base==1)return 1;
    else if(pow==1)return base;
    else if(pow%2)return BigMod(base,pow-1,mod)*base%mod;
    else {ll x=(BigMod(base,pow/2,mod)%mod);x=(x*x)%mod;return x;}
}

ll isprime(ll prime)
{
	ll cnt=0;
	for(int i=2;i*i<=prime;i++)
	{
		if(prime%i==0)return false;
		
	}
	return true;
}

   void DBG() { cerr << "]" << '\n'; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h;
    if (sizeof...(t)) cerr << ", ";
    DBG(t...);
}
 
#ifdef LOCAL // compile with -DLOCAL
    #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
    #define dbg(...) 0
#endif 

//***************** GRAPH VISITED *****************************************************
const int dx[]={+1,-1,+0,+0};
const int dy[]={+0,+0,+1,-1};
const int f1x[]={+0,+0,+1,-1,-1,+1,-1,+1};   /// Kings Move
const int f1y[]={-1,+1,+0,+0,+1,+1,-1,-1};  /// Kings Move
const int f2x[]={-2, -2, -1, -1,  1,  1,  2,  2};  /// Knights Move
const int f2y[]={-1,  1, -2,  2, -2,  2, -1,  1}; /// Knights Move

const int maX=1e3+10;
ll vis[maX][maX];
ll n,m;
void DFS(ll x, ll y)
{
	cout<<x<<' '<<y<<endl;
	vis[x][y]=1;
	
	for(ll i=0;i<4;i++)
	{
		ll d=x+dx[i];
		ll dd=y+dy[i];
		
		if(d>=1 && d<=n && dd>=1 && dd<=m && vis[d][dd] !=1) DFS(d,dd);
	}
   	
	for(ll i=x;i<=n;i++)if(vis[i][y] ==0) DFS(i,y);
	for(ll i=x-1;i>=1;i--)if(vis[i][y]==0)DFS(i,y);
	for(ll i=y;i<=m;i++)if(vis[x][i]==0)DFS(x,i);
	for(ll i=y-1;i>=1;i--)if(vis[x][i]==0)DFS(x,i);
	 
 
	
}

void solve()
{
    ll n,i,j,cc=0,l,r;
    cin>>l>>r;
    if(l==r){
        cout<<0<<endl;
        return;
    }
    j=l^r;
    while(j){
        cc++;
        j >>=1;
    }
    ll ans=0;
    while(cc){
        ans<<=1;
        ans++;
        cc--;
    }
    cout<<ans<<endl;
}

 
//**********************************MAIN_FUNCTION ************************************************************
int main( ) {
 
      ll n,m,i,j,k,len=0,e,p,q,a,b,c,d;
    string str;
    int t;
     ll cnt=0;
        cin>>a>>b>>c;
        if(a<b)cout<<c<<endl;
        else
        {
        	if(a%b==0)cout<<(a/b)*c<<endl;
        	else cout<<((a/b)+1)*c<<endl;
		}
      
	return 0;
}
 

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

int main() {
  string S; cin >> S;
  bool flag = true;
  rep(i,S.size()) {
    if ((i+1)%2!=0 && S[i]=='L') flag = false;
    if ((i+1)%2==0 && S[i]=='R') flag = false;
  }

  cout << (flag ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int a,b,c,d,l,s,k,r;
	scanf("%d%d%d%d%d",&l,&a,&b,&c,&d);
	k=a/c;
	s=b/d;
	if(a%c!=0){
		k++;
	}
	if(b%d!=0){
		s++;
	}
	if(k>s){
		r=l-k;
	}else{
		r=l-s;
	}
	printf("%d\n",r);
	return 0;
}

Measured memory_bytes: 596
using System;
using System.Collections;
using System.Collections.Generic;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		while(true){
			int N=ri();
			if(N==0)return;
			List<int> L=new List<int>();
			for(int i=0;i<N;i++)L.Add(ri());
			L.Sort();
			int sum=0;
			for(int i=1;i<N-1;i++)sum+=L[i];
			Console.WriteLine(sum/(N-2));
		}
		
	}

	public Sol(){
	}




	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<char> vec(H*W);

  for (int i = 0; i < H*W; i++) {
      char a;
      cin >> a;
      vec.at(i) = a;
    }
  int h = 0, w = 0;
  for (int i = H-1; i >= 0; i--) {
    for (int j = W-1; j >= 0; j--) {
      if (vec.at(i*W + j) == '#')
        break;
      else if (vec.at(i*W + j) == '.' && j > 0)
        continue;
      for (int k = 0; k < W; k++)
        vec.erase(vec.begin() + i*W + (W-k-1));
      h++;
    }
  }
    
  for (int j = W-1; j >= 0; j--) {
    for (int i = H-h-1; i >= 0; i--) {
      if (vec.at(j + i*(W-w)) == '#')
        break;
      else if (vec.at(j + i*(W-w)) == '.' && i > 0)
        continue;
      for (int k = 0; k < H-h; k++)
        vec.erase(vec.begin() + j + (H-h-1-k)*(W-w));
      w++;
    }
  }
        
  for (int i = 0; i < H-h; i++) {
    for (int j = 0; j < W-w; j++) {
      if (j != W-w-1)
        cout << vec.at(j+i*(W-w));
      else if (j == W-w-1)
        cout << vec.at(j+i*(W-w)) << endl;
    }
  }
}


Measured memory_bytes: 3608
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            var Ai = Sarray();
            var rui = new long[N + 1];
            for (var i = 1; i < N + 1; ++i)
                rui[i] = rui[i - 1] + Ai[i - 1];
            var ans = Abs((rui[N] - rui[1]) - rui[1]);
            for (var i = 1; i < N; ++i)
                ans = Min(ans, Abs((rui[N] - rui[i]) - rui[i]));
            WriteLine(ans);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 35580
use std::io::*;
use std::str::FromStr;
use std::f32;

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")
}

fn main() {
	let k: i32 = read();
	let a: i32 = read();
	let b: i32 = read();
	if f32::ceil(a as f32/k as f32)*(k as f32) <= (b as f32) {
		println!("OK");
	} else {
		println!("NG");
	}
}


Measured memory_bytes: 2604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[110][110];

int main(){
	ll n;
	string s;
	cin>>n>>s;
	ll ans=0;
	for(int i=0;i<1000;i++){
		bool f[3]={};
		char c[3];
		c[0]='0'+i/100;
		c[1]='0'+(i/10)%10;
		c[2]='0'+i%10;
		for(int j=0;j<n;j++){
			if(!f[0]&&s[j]==c[0]){
				f[0]=1;
				continue;
			}
			if(!f[1]&&f[0]&&s[j]==c[1]){
				f[1]=1;
				continue;
			}
			if(!f[2]&&f[1]&&s[j]==c[2])f[2]=1;
		}
		if(f[2]){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
import math
N=int(input())
end=int(math.sqrt(N)//1+1)
def func(i):
    d,m=divmod(N,i)
    if m==0:
        return i+d
    else:
        return 10**12+1
ret=min([func(i) for i in range(1,end)])-2
print(int(ret))



Measured memory_bytes: 10904
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int n;
int arr[110];
int ord[110];

void pung() {
    puts("-1\n");
    exit(0);
}
int main() {
    int i, j;

    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d",&arr[i]);
    for (i=0;i<n;i++) if (arr[i]>i+1) pung();
    vector<int> vec;
    for (j=0;j<n;j++) {
        int c = 0, t = -1;
        for (i=0;i<n;i++) {
            if (arr[i]<0) c++;
            else if (arr[i]==c+1) t=i;
        }
        if (t<0) pung();
        vec.push_back(arr[t]);
        arr[t]=-1;
    }
    for (int &v : vec) printf("%d\n",v);

    return 0;
}


Measured memory_bytes: 256
h,w = map(int,input().split())
ans = 0
a1 = -(-w//2)

if w == 1 or h == 1:
    print(1)
else:
    if w%2 == 0:
        a2 = a1
    else:
        a2 = a1-1
    if h%2 == 0:
        ans += (a1 + a2) * h//2
    else:
        ans += (a1 + a2) * (h-1)//2 + a1
    print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
typedef long long int ll;
using namespace std;
using Graph = vector<vector<int>>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S, T;
    cin >> N;
    cin >> S >> T;
    string ans = "";

    rep(i, N)
    {
        ans += S[i];
        ans += T[i];
    }
    cout << ans << endl;
    //system("pause");
    return 0;
}

Measured memory_bytes: 256