akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
S = input()

Llist = []
Rlist = []
now = S[0]
cnt = 0

for i in range(1, N+1):
    if i < N and now == S[i]:
        cnt += 1
    else:
        if now == 'L':
            Llist.append(cnt)
        else:
            Rlist.append(cnt)
        if i < N:
            now = S[i]
            cnt = 0

length = min(len(Llist), len(Rlist))
ans = sum(Llist) + sum(Rlist)
#print(Llist, Rlist, length, ans)
if K == 0:
    print(ans)
else:
    for i in range(min(K, length)):
        length -= 1
        if len(Llist) != len(Rlist):
            ans += 2
        else:
            if length == 0:
                ans += 1
            else:
                ans += 2
    print(ans)

Measured memory_bytes: 4092
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int sum=0,n,l,r;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l>>r;
        sum+=(r-l+1);
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (long long i=0;i<(n);i++)
#define FOR(i,a,b) for (long long i=(a);i<(b);i++)
#define RREP(i,n) for(long long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl
#define dump(x)  cerr << #x << " => " << (x) << endl
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end())
#define MAX(vec) *max_element(vec.begin(), vec.end())
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり
#define IN(n,m)  (!(m.find(n) == m.end()))
#define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
#define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w)
#define EQ(a,b) (abs(a - b) < 1e-10)
using namespace std;
constexpr int dx[4] = {0,1,0,-1};
constexpr int dy[4] = {1,0,-1,0};
constexpr long double pi = M_PI;
constexpr double EPS = 1e-10;
constexpr long MOD = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL,LL> pr;
typedef vector<bool> VB;
typedef vector<pr> VP;
typedef priority_queue<pr,vector<pr>,greater<pr>> pq;


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,q;
    cin >> n;
    VI A(n);
    REP(i,n) cin >> A[i];
    cin >> q;
    VI Q(q);
    REP(i,q) cin >> Q[i];
    map<int,int> dic;
    REP(i,1<<n) {
        LL sum = 0;
        REP(bit,n) {
            if ((i >> bit) & 1) sum += A[bit];
        }
        dic[sum]++;
    }

    REP(i,q) {
        if (IN(Q[i],dic)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}




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

int main() {
    int N;
    cin >> N;
    
    vector<int> vec(N);
    for (int i = 0; i < N; i++){
        int a;
        cin >> a;
        vec.at(i) = a;
    }
    
    int alice = 0;
    int bob = 0;
    
    for (int i = 0; i < N; i++){
        
        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());
        
        if (i % 2 == 0){
          alice += vec.at(0);
        }
        
        else {
            bob += vec.at(0);
        }
        
        vector<int> vec2(vec.size()-1);
        
        for (int j = 0; j < vec.size()-1; j++){
            vec2.at(j) = vec.at(j+1);
        }
        
        vec = vec2;
    }
    
    cout << alice - bob << endl;
}


Measured memory_bytes: 256
import sys
from collections import deque
def input():return sys.stdin.readline().strip()

def main():
    H, W = map(int, input().split())

    field = "#" * (W+2)
    field += "#" + "##".join([input() for _ in range(H)]) + "#"
    field += "#" * (W+2)

    move = [-1, 1, -(W+2), W+2]
    cost = [-1] * (H+2) * (W+2)

    def dfs(s):
        q = deque()
        enqueue = q.append
        dequeue = q.popleft

        for v in s:
            cost[v] = 0
            enqueue(v)

        while q:
            now = dequeue()
            cost_now = cost[now]
            for dx in move:
                nv = now + dx
                if field[nv] == "." and cost[nv] < 0:
                    cost[nv] = cost_now + 1
                    enqueue(nv)
    
    starts = [i*(W+2)+j for j in range(1, W+1) for i in range(1, H+1) if field[i*(W+2)+j] == "#"]
    dfs(starts)

    print(max(cost))

if __name__ == "__main__":
    main()

Measured memory_bytes: 59956
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
const ld pi = acos(-1);
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n, q; cin >> n >> q;
    string s; cin >> s;

    VI cnt(n);
    FOR(i, 1, n) {
        cnt[i] += cnt[i - 1];
        if (s[i - 1] == 'A' && s[i] == 'C')++cnt[i];
    }

    FOR(i, 0, q) {
        int l, r; cin >> l >> r;
        --l, --r;
        cout << cnt[r] - cnt[l] << "\n";
    }
}


Measured memory_bytes: 1488
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)


#define huge 1000000007
typedef long long ll;

int main(void) {
	
	ll N = 0;
	ll K = 0;
	ll X = 0;
	ll Y = 0;

	cin >> N >> K >> X >> Y;

	
	if(N-K>0)
	cout << K*X+(N-K)*Y << endl;
	else
		cout << N*X<< endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = (int)1e9;

const int N = 18;
const int V = 50;
int dp[1 << N][V+1];
int as[N];
int bs[N];
int off[N][N];

void cap(int& v, int off) {
	if (v > off) v = off;
}

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

	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> as[i];
	for (int i = 0; i < n; ++i) cin >> bs[i];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			off[i][j] = (i % 2 == j % 2) ? as[j] : bs[j];
		}
	}

	int h = 1 << n;
	for (int m = 0; m < h; ++m) {
		for (int j = 0; j <= V; ++j) dp[m][j] = INF;
	}
	dp[0][0] = 0;
	
	for (int m = 0; m < h; ++m) {
		int i = __builtin_popcount(m);
		for (int v = 0; v <= V; ++v) {
			int d = 0;
			for (int j = 0; j < n; ++j) {
				if (m & (1 << j)) continue;
				if (off[i][j] >= v) cap(dp[m | (1 << j)][off[i][j]], dp[m][v] + d);
				++d;
			}
		}
	}

	int res = INF;
	for (int v = 0; v <= V; ++v) res = min(res, dp[h-1][v]);
	cout << (res >= INF ? -1 : res) << '\n';
}


Measured memory_bytes: 52480
m,d=map(int, input().split())
count = 0
for i in range(m):
    for j in range(d):
        d10 = int((j+1)/10)
        d1 = (j+1)%10
        if d10 < 2 or d1 < 2: continue
        if (i+1) == d1*d10:
            count += 1
print(count)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long

int ans(string S,int check,int sum){
    if(S.size()==1){
        return (S[0]-'0')+check+sum;
    }
    check+=(S[0]-'0');
    return ans(S.substr(1),0,sum+check)+ans(S.substr(1),check*10,sum);
}

signed main(){
    string S;
    cin >>S;
    cout <<ans(S,0,0)<<endl;
}

Measured memory_bytes: 256
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {//223
	int n;
	cin>>n;
	int mi=INT_MAX,mx=INT_MIN;
	while(n--) {
		int val;
		cin>>val;
		mi=min(mi,val);
		mx=max(mx,val);
	}
	cout<<mx-mi;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3640
fn AB() -> Result<i32, &'static str> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .map_err(|_| "input error")?;
    let ab: Vec<i32> = input.trim_right().split_whitespace()
        .filter_map(|s| s.parse::<i32>().ok())
        .collect();
    let a = ab[0];
    let b = ab[1];
    if b % a == 0 {
        Ok(a + b)
    }
    else {
        Ok(b - a)
    }
}

fn main() {
    println!("{}", AB().unwrap());
}

Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
int main(void){
	int n,m,X,Y,i,ma,mi;
	cin>>n>>m>>X>>Y;
	int x,y;
	for(i=0;i<n;i++){
		cin>>x;
		if(i==0)ma=x;
		ma=max(ma,x);
	}
	for(i=0;i<m;i++){
		cin>>y;
		if(i==0)mi=y;
		mi=min(mi,y);
	}
	for(i=X+1;i<=Y;i++){
		if(ma<i&&mi>=i){
          cout<<"No ";
		break;
        }
	}
	cout<<"War\n";
}
/*reveres begin end
cout<<"\n";
  m.insert(std::make_pair('c', 30));
*/


Measured memory_bytes: 256
#import heapq
import itertools
#import math
#import numpy as np
import sys

N = int(input())
S = input()
#D = list(map(int, input().split()))
#S = [input() for _ in range(H)]
#T = [list(map(int,input().split())) for _ in range(N)]
#sys.exit()
a = S[0:int(N/2)]
b = S[int(N/2):N]
if a == b :
    print('Yes')
else :
    print('No')


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define FOR(NAME, START, NUM) for (ll NAME = START; NAME < (NUM); NAME++)
#define REP(NAME, NUM) for (ll NAME = 0; NAME < (NUM); NAME++)
#define BREP(NAME, NUM) for (ll NAME = (NUM)-1; NAME >= 0; NAME--)
#define ALL(NAME) (NAME).begin(), (NAME).end()
const ll INF =1000000000000000;

int main(){
  ll n;
  cin >> n;
  vector<ll> a(n+5,INF);
  REP(i,n)cin >> a.at(i);
  sort(a.begin(),a.end());
  ll ans = 0;
 
  ll cnt = 1;
  REP(i,n){
    if(a.at(i) != a.at(i+1)){
      if(cnt >= a.at(i))ans+=cnt-a.at(i);
      else ans+=cnt;
      cnt = 1;
    }
    else cnt++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main{
  
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    
    int ab = b-a;
    int bc = c-b;
    int ca = c-a;
    
    ab = Math.abs(ab);
    bc = Math.abs(bc);
    ca = Math.abs(ca);
    
    if(ab <= d && bc <= d){
      System.out.println("Yes");
    }else if((a == b && b == c && c == a) || a == c){
      System.out.println("Yes");
    }else if(ca <= d){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
    
  }
  
}

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

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string a, b, c;
  cin >> a >> b >> c;
  if ((a.back() == b.at(0)) and (b.back() == c.at(0))) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[1000000],s1[1000000];
map<char,char>mp;
int main(){
	gets(s+1);
	mp['b']='d';mp['d']='b';mp['p']='q';mp['q']='p';
	int l=strlen(s+1);
	for(int i=1;i<=l;i++)
	s1[l-i+1]=mp[s[i]];
	if(strcmp(s+1,s1+1)==0)puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() /4;
const ll linf = numeric_limits<ll>::max() /4;
const ull ulinf = numeric_limits<ull>::max()/4;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.end(), v.begin());
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - a) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - a) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

//ll ncr[100][100];
//ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

//ll npr[100][100]={};
//ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

//ll nHr(int n,int r){ret nCr(n+r-1,r);}

///////////////////////////////////////////////////////////////////////////

struct boll{
    int r = 0;
    int w = 1;
    int n = 1;
};

int n,m;
boll b[100005] = {};

int main(){

    cin >> n >> m;
    b[1].r = 1;
    b[1].w = 0;
    
    rep(i,0,m){
        int x,y;
        cin >> x >> y;
        
        if(b[x].w > 0){
            if(b[x].r > 0){
                b[x].w --;
                b[y].r ++;

                b[x].n --;
                b[y].n ++;
            }else{
                b[x].w --;
                b[x].n --;
                b[y].w ++;
                b[y].n ++;
            }
        }else{
            b[x].r --;
            b[x].n --;
            b[y].r ++;
            b[y].n ++;
        }
    }
    int ans = 0;
    rep(i,1,n+1){
        if(b[i].r > 0)ans++;
    }
    P(ans);
	
	return  0;
}

Measured memory_bytes: 1408
#include<iostream>
using namespace std;
bool l,r,b;
int n,ans;
string s;
int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    ans=l=r=b=0;
    for(int i=0;i<n;i++){
      cin>>s;
      if(s=="lu")l=true;
      else if(s=="ru")r=true;
      else if(s=="ld")l=false;
      else if(s=="rd")r=false;
      if(l==r&&l!=b){
	b=l;
	ans++;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1208
import sys
sys.setrecursionlimit(10**7)
L = []
def lunlun(x, cnt, c):
  if cnt == 10:
    L.append(int(x))
    return
  e = int(x[-1])
  if c:
    for i in range(max(e-1, 0), min(e+2, 10)):
      lunlun(x+str(i), cnt+1, 1)
  else:
    lunlun(x+"0", cnt+1, 0)
    for i in range(1, 10):
      lunlun(x+str(i), cnt+1, 1)
lunlun("0", 1, 0)
for i in range(1, 10):
  lunlun(str(i), 1, 1)

k = int(input())
ans = L[k]
print(ans)

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

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

    int n,k;cin>>n>>k;
    int x=1;
    for (int i=0;i<n;i++){
        x=min(2*x,x+k);
    }cout<<x<<endl;
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
if m > 0:
    a = {int(input()): None for i in range(m)}
else:
    a = {}
dp = [0] * (n + 1)
dp[0] = 1
MOD = 10 ** 9 + 7
if m == 0 or 1 not in a:
    dp[1] = 1
for i in range(2, n + 1):
    if i - 1 not in a:
        dp[i] += dp[i - 1]
    if i - 2 not in a:
        dp[i] += dp[i - 2]
    dp[i] %= MOD
print(dp[-1])


Measured memory_bytes: 15068
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INTINF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

//つねに10億7などの剰余をとる構造体
//参考: https://www.youtube.com/watch?v=L8grWxBlIZ4&t=9858
//参考: https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#4-%E7%B4%AF%E4%B9%97-an
int mod  = MODA;
struct modint {
	ll x;
	modint (ll x):x(x%mod){}
	modint& operator+=(const modint a){
		(x += a.x ) %= mod;
		return *this;
	}
	modint& operator-=(const modint a){
		(x -= a.x ) %= mod;
		if (x < 0) x += mod;
		return *this;
	}
	modint& operator*=(const modint a){
		(x *= a.x ) %= mod;
		return *this;
	}
	modint& operator/=(modint a){
		ll exp = mod - 2;
		while(exp > 0){
			if(exp & 1) *this *= a.x;
			a *= a.x;
			exp >>= 1;
		}
		return *this;
	}
	modint operator+(const modint a) const{
		modint res(*this);
		return res+=a;
	}
	modint operator-(const modint a) const{
		modint res(*this);
		return res-=a;
	}
	modint operator*(const modint a) const{
		modint res(*this);
		return res*=a;
	}
	modint operator/(const modint a) const{
		modint res(*this);
		return res/=a;
	}
};
modint modpow(modint x, ll n){
	modint res=1;
	while(n > 0){
		if(n & 1) res = res * x.x;
		x = x * x;
		n >>= 1;
	}
	return res;
}

int main() {
	modint ans = 1;
	int tmp;
	int n;
	cin >> n;
	vector< pair<int, ll>> lo(200001);
	REP(i, 200001) lo[i] = make_pair(-1, (ll) 0);
	int prec = 0, c;
	REP(i, n){
		cin >> c;
		if(lo[c].first != i-1 && lo[c].first != -1) ans += lo[c].second;
		lo[c] = make_pair(i, ans.x); 
	}
	cout << ans.x << endl;
}

Measured memory_bytes: 3456
let () = Scanf.scanf "%d\n" @@ fun n ->
  let array = Array.make 4 0 in
  for i=1 to n do
    Scanf.scanf " %s" @@ fun s ->
      if s = "AC" then array.(0) <- array.(0) + 1
      else if s = "WA" then array.(1) <- array.(1) + 1
      else if s = "TLE" then array.(2) <- array.(2) + 1
      else array.(3) <- array.(3) + 1
  done;
  Printf.printf "AC x %d\n
                WA x %d\n
                TLE x %d\n
                RE x %d\n" array.(0) array.(1) array.(2) array.(3); 

Measured memory_bytes: 5904
from collections import deque

N, M, K = map(int, input().split())
friend = [list(map(int, input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]

f = [set() for _ in range(N + 1)]
b = [set() for _ in range(N + 1)]

for i, j in friend:
    f[i].add(j)
    f[j].add(i)
for i, j in block:
    b[i].add(j)
    b[j].add(i)

stack = deque()
ans = [0] * (N + 1)
visited = [0] * (N + 1)

for i in range(1, N + 1):
    if visited[i]:
        continue
    # setは{}で書く
    link = {i}
    stack.append(i)
    visited[i] = 1
    while stack:
        n = stack.pop()
        # nのフレンド全員について
        for j in f[n]:
            if visited[j] == 0:
                stack.append(j)
                visited[j] = 1
                # link(set)に追加
                link.add(j)
    for i in link:
        # 全体-既にフレンドの人数-ブロックした人数-自分自身
        # set同士で積集合をとる
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1

print(*ans[1:])


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

int main(){
  int a,b;
  cin >> a >> b;
  if(a==1){
    a=14;
  }
  if(b==1){
    b=14;
  }
  if(a>b){
    cout << "Alice" << endl;
  }
  else if(a<b){
    cout << "Bob" << endl;
  }
  else{
    cout << "Draw" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;

int main() {
  string S;
  cin >> S;
  if (S[2]==S[3]&&S[4]==S[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

typedef long long ll;
const int MAX=1e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;

struct DOT{
    int x,y;
    int operator- (const DOT&p)const{
        int dx=x-p.x,dy=y-p.y;
        if(dx<0) dx=-dx;
        if(dy<0) dy=-dy;
        return dx+dy;
    }
    bool operator< (const DOT&p)const{
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
}people[55],check[55];

void Scan(const int &n,DOT* dot){
    for(int i=0;i<n;i++){
        cin>>dot[i].x>>dot[i].y;
    }
}

void solve(const int &n,const int &m){
    for(int i=0;i<n;i++){
        int ans=0;
        for(int j=1;j<m;j++){
            int x=people[i]-check[j];
            int y=people[i]-check[ans];
            if(x<y||x==y&&check[j]<check[ans])
                ans=j;
        }
        cout<<ans+1<<endl;
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        Scan(n,people);
        Scan(m,check);
        solve(n,m);
    }
    return 0;
}


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

int main() {

  int y, m, d;
  char c1, c2;
  cin >> y >> c1 >> m >> c2 >> d;
  if (m <= 4) {
    cout << "Heisei" << endl;
  }
  else {
    cout << "TBD" << endl;
  }

}


Measured memory_bytes: 256
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

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

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;

int main(){
  int n;
  double d;
  double x;
  cin>>n>>d>>x;
  d-=x;
  double res=0;
  while(n>1){
    res+=(d+x+d+x*(2*n))/2;
    double nd=d*(n+1)/n+3*x/(2*n);
    double nx=(2*n*x+4*x)/(2*n);

    d=nd;
    x=nx;
    --n;
  }
  res+=(d+d+x)/2+x;
  printf("%.10f\n",res);
  return 0;
}





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

int main(){
  int n;
  cin>>n;
  if(n==0)cout<<1<<endl;
  else cout<<0<<endl;
}

Measured memory_bytes: 3616
#include <iostream>
using namespace std;
const int SIZE=2000000;
const int INFTY=2000000050;

int A[SIZE+1];
int H;//heapsize

void maxheap(int u)
{
	int l=u*2,r=u*2+1,lar;
	int sto;
	
	if(l<=H&&A[l]>A[u])lar=l;
	else lar=u;
	if(r<=H&&A[r]>A[lar])lar=r;
	
	if(lar!=u)
	{
		sto=A[u];
		A[u]=A[lar];
		A[lar]=sto;
		maxheap(lar);
	}
	return;
}

void buildmaxh()
{
	for(int i=H/2;i>=1;i--)maxheap(i);
	return;
}

int extract()
{
	if(H<1)return -INFTY;
	int maxv=A[1];
	A[1]=A[H--];
	maxheap(1);
	return maxv;
}

void increasekey(int u,int key)
{
	if(key<A[u])return;
	A[u]=key;
	int sto;
	while(u>1&&A[u/2]<A[u])
	{
		sto=A[u];
		A[u]=A[u/2];
		A[u/2]=sto;
		u/=2;
	}
	return;
}

void insert(int key)
{
	A[++H]=-INFTY;
	increasekey(H,key);
	return;
}

int main() {
	string s;int n;
	while(cin>>s&&s!="end")
	{
		if(s=="insert")
		{
			cin>>n;
			insert(n);
		}
		else if(s=="extract")cout<<extract()<<endl;
	}
	return 0;
}

Measured memory_bytes: 7044
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t a,b,c;
  cin >> a >> b >> c;
  bool ans=false;
  if(c-a-b >= 0 && a*a+b*b+c*c+2*a*b-2*b*c-2*c*a > 4*a*b) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
)

func main() {
	sc := NewScanner()

	n := sc.NextInt()
	a := make([]int, n)
	b := make([]int, n)

	for i := 0; i < n; i++ {
		a[i] = sc.NextInt()
	}
	for i := 0; i < n; i++ {
		b[i] = sc.NextInt()
	}
	ans := 0
	for i := 0; i < n; i++ {
		if a[i] > b[i] {
			ans += a[i] - b[i]
		}
	}
	fmt.Printf("%v\n", ans)
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 640
function Main(input) {
    var N = parseInt(input[0], 10);
    var A = input.slice(1).map(a => parseInt(a, 10));

    for (var i = 0; i < N; i++) {
        if (A[i] % 2 === 0 && !(A[i] % 3 === 0 || A[i] % 5 === 0)) {
            return console.log('DENIED');
        }
    }

    return console.log('APPROVED');
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

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

int const MAX = 300005;
long long a[MAX];
long long b[MAX];

int main() {
	long long n, k;
	cin >> k >> n;
	if (k % 2 == 0) {
		cout << k / 2;
		for (int i = 2; i <= n; i++) {
			cout << " " << k;
		}
		cout << endl;
	}
	else {
		for (int i = 1; i <= n; i++) {
			a[i] = k / 2 + 1;
		}
		int keta = n;
		long long hiku;
		hiku = k / 2 + 1 + n - 1 - ((n - 1 + k) / 2 + (n - 1 + k) % 2);
		for (int i = 1; i <= hiku; i++) {
			if (a[keta]==1) {
				keta--;
			}
			else {
				a[keta]--;
				for (int j = keta + 1; j <= n; j++) {
					a[j] = k;
				}
				keta = n;
			}
		}
		cout << a[1];
		for (int i = 2; i <= keta; i++) {
			cout << " " << a[i];
		}
		cout << endl;
	}
}

Measured memory_bytes: 4992
/*                        _
                       _oo0oo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                      0\  =  /0
                   ____/`---'\____
                  /  \\|     |//  \
                 / \\||| /:\ |||// \
                / _||||| -:- |||||- \
               |   | \\\ \-/ /// |   |
               | \_|  ''\---/''  |_/ |
               \  .-\__  '-'  ___/-. /
            ____'. .'  /--.--\  `. .'_____
          /"" '<  `.___\_<|>_/___.' >' "" \
         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
         \  \ `_.   \_ __\ /__ _/   .-` / _/
          `-.____`.___ \_____/___.-`___.-'

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 JENISH MONPARA S.    IIT PATNA    I_LOVE_ADITI_GOEL
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double DEL = 1e-12;
const int mod =  1000000007;
const int LIM = 100005;


#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mpq priority_queue<int,vector<int>,greater<int>>
#define deb(a) cerr << #a << ": " << a << endl
#define ftt cin>>t;for(int tt=1;tt<=t;++tt)
#define forr(i,n) for((i)=1;(i)<=(n);(i)++)
#define Rev(v) reverse(v.begin(),v.end())
#define Sort(v) sort(v.begin(),v.end())
#define mem(a,b) memset(a,b,sizeof(a))
#define umii unordered_map<int,int>
#define all(a) a.begin() , a.end()
#define vvi vector<vector<int>>
#define pq priority_queue<int>
#define sqr(a) (((a) * (a)))
#define double long double
#define dbg cout<<"\nhi\n"
#define pii pair<int,int>
#define mii map<int,int>
#define vb vector<bool>
#define eb emplace_back
#define vi vector<int>
#define nl cout<<"\n"
#define pb push_back
#define int long long
#define sp <<" "<<
#define se second
#define fi first
 
int fpow(int x, int n){
    int res = 1;
    while(n){
          if(n&1){
                res = res * x % mod;
          }
          x = x * x % mod;
          n>>=1;
    }
    return res;
}
int gcd(int a,int b){
    if(b == 0)return a;
    return gcd(b,a % b);
}
void sieve(int n){
     bool prime[5*LIM];
     memset(prime, true, sizeof(prime));
      int rootn = (int)sqrt(n);
     for (int p = 2; p <= rootn; p++)
          if (prime[p] == true)
               for (int i = p*p; i <= n; i += p)
                    prime[i] = false;
     prime[1] = 0;

}

int cnt, sum, mid, mx = -1e17, mn = 1e17, a[2*LIM];
int n, m, d, t, i, j, k, l, r, x, y, z;
bool f, f1, f2;
string s;

//******************************************* CHECK CONSTRAINTS **************************************************


int32_t main()
{     fio;
      cin>>n>>k;
      
      vb canfirstwin(k+k+2,false);
      forr(i,n){
            cin>>a[i];
            canfirstwin[a[i]]=1;
      }
      forr(i,k){
            if(canfirstwin[i]){
                  continue;
            }
            forr(j,n){
                  canfirstwin[i+a[j]]=1;
            }
      }
      if(canfirstwin[k]){
            cout<<"First";
      }else{
            cout<<"Second";
      }
     
}


Measured memory_bytes: 3692
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

if N == 0:
    print(0)
    exit()

N = -N
ans = ''
while N != 0:
    if N % -2 == 0:
        ans += '0'
    else:
        ans += '1'
    N //= -2
print(ans[::-1])


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

int main() {
    ll n,k;
    cin >> n >> k;
    vector<int> p(n);
    vector<int> c(n);
    rep(i,n){
        cin >> p[i];
        p[i]--;
    }
    rep(i,n) cin >> c[i];
    ll ans=-1e18;
    if(n>=k){
        rep(i,n){
            ll now=i;
            ll sc=0;
            rep(j,k){
                now=p[now];
                sc+=c[now];
                ans=max(ans,sc);
            }
        }
    }
    else{
        rep(i,n){
            ll now=i;
            ll sc=0;
            ll a=0;
            rep(j,n){
                now=p[now];
                sc+=c[now];
                ans=max(ans,sc);
                if(now==i){
                    a=j+1;
                    break;
                }
            }
            if(sc>=0){
                ll now2=i;
                ll sc2=sc*(k/a-1);
                ans=max(ans,sc2);
                ans=max(ans,sc2-c[now2]);
                rep(i,k%a+a){
                    now2=p[now2];
                    sc2+=c[now2];
                    ans=max(ans,sc2);
                }
                
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3668
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        long[][] pos = new long[n][2];
        for (int i = 0; i < n; i++) {
            pos[i][0] = scanner.nextInt();
            pos[i][1] = scanner.nextInt();
        }

        Arrays.sort(pos, Comparator.comparingLong(a -> a[0]));
        long ans = Long.MAX_VALUE;

        for (int x1 = 0; x1 < n; x1++) {
            for (int x2 = x1 + 1; x2 < n; x2++) {
                List<Integer> ry = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if (pos[x1][0] <= pos[i][0] && pos[i][0] <= pos[x2][0]) {
                        ry.add(i);
                    }
                }

                ry.sort(Comparator.comparingLong(i -> pos[i][1]));

                for (int i = 0; i < ry.size(); i++) {
                    for (int j = i + 1; j < ry.size(); j++) {
                        int y1 = ry.get(i), y2 = ry.get(j);
                        if (j - i == k - 1 && pos[y2][1] >= Math.max(pos[x1][1], pos[x2][1]) && pos[y1][1] <= Math.min(pos[x1][1], pos[x2][1])) {
                            ans = Math.min(ans, (pos[x2][0] - pos[x1][0]) * (pos[y2][1] - pos[y1][1]));
                        }
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

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

int main() {
  
  int D;
  cin >> D;
  
  if(D == 25) cout << "Christmas" << endl;
  else if(D == 24) cout << "Christmas Eve" << endl;
  else if(D == 23) cout << "Christmas Eve Eve" << endl;
  else cout << "Christmas Eve Eve Eve" << endl;

}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;

#define rep(i,beg,end)   for (auto i=(beg);i<(end);i++)
#define rep2(name,container) for(auto name=begin(container); name != end(container);name++)
#define all(cont)           begin(cont), end(cont)
#define rall(cont)           rbegin(cont), rend(cont)
using ll = long long;
using vi = vector<ll>;
const ll INFMAX = LLONG_MAX;
const ll INFMIN = LLONG_MIN;
const ll MOD = 1000000007;


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

	string s;
	cin >> s;
	ll misses = 0;
	const ll slen = s.length();
	for (ll n = 0; n < slen/2; n++) {
		if (s[n] != s[slen - n - 1]) misses++;
	}
	cout << misses << endl;
	return 0;
}


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

int main() {
	string a,b,c;
	int count,counter;
	count=0;counter=1;
	cin >>a>>b;
	for(int i=0;i<a.size()+b.size();i++){
		if(i%2==0){c+=a[i-count];count+=1;}
		else{c+=b[i-counter];counter+=1;}
		
	}
	cout<<c<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
    using System.Text;
    using System.Collections.Generic;
    using static System.Math;
    using System.Linq;
    using static System.Array;
    
    namespace ConsoleApp2
    {
    class Program
    {
        static string S;
        static void Main(string[] args)
        {

            //var N = long.Parse(Console.ReadLine());
            var NK = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            var N = NK[0];
            var K = NK[1];

            var H = new long[N];
            for (int i = 0; i < N; i++)
            {
                H[i] = long.Parse(Console.ReadLine());
            }

            Sort(H);

            var ans = long.MaxValue;
            for (int i = 0; i+K-1 < N; i++)
            {
                ans = Min(ans, Abs(H[i + K-1] - H[i]));
            }


            Console.WriteLine(ans);
            
            

            
        }
    }
}


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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int n; cin >> n;
    vector<ll> ts(n), as(n);
    for (int i = 0; i < n; i++) cin >> ts[i] >> as[i];
    
    ll mt = 1, ma = 1;
    for (int i = 0; i < n; i++) {
        ll t = ((mt + ts[i] - 1) / ts[i]);
        ll a = ((ma + as[i] - 1) / as[i]);
        mt = ts[i] * max(t, a), ma = as[i] * max(t, a);
    }
    cout << mt + ma << endl;
    return 0;
}


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

class Main {
    static Scanner scanner = new Scanner();
    static long mod = 1000000007;

    public static void main(String[]$) {
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long gcd = gcd(a, b);
        System.out.println(getPrimeFactors(gcd).size() + 1);
    }

    static long gcd(long a, long b) {
        return 0 < b ? gcd(b, a % b) : a;
    }

    static Map<Long, Integer> getPrimeFactors(long n) {
        Map<Long, Integer> primeFactors = new HashMap<>();
        long c = n;
        for (long i = 2; i * i <= n && c > 1; i++) {
            int count = 0;
            while (c % i == 0) {
                count++;
                c /= i;
            }
            if (count > 0) {
                primeFactors.put(i, count);
            }
        }
        if (c > 1) {
            primeFactors.put(c, 1);
        }
        return primeFactors;
    }

    static class Scanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}


Measured memory_bytes: 22356
s=gets.chomp
k=gets.to_i
zord="z".ord
ret=""
s.each_char do |c|
    need=(zord-c.ord+1)%26
    if k >= need
        ret+="a"
        k-=need
    else
        ret+=c
    end
end
ret[-1]=(ret[-1].ord + k%26).chr
puts ret


Measured memory_bytes: 167388
def d_pairs():
    # 参考: https://maspypy.com/atcoder-参加感想-2019-02-16abc-155
    import numpy as np
    N, K = [int(i) for i in input().split()]
    A = np.array([int(i) for i in input().split()], np.int64)

    A = np.sort(A)
    zero = A[A == 0]
    positive = A[A > 0]
    negative = A[A < 0]

    def f(c):
        """数列 A から 2 要素を選んで積を取ったとき、c 以下となるようなペアの選び方"""
        count_pair = 0

        # a (数列の要素) == 0 かつ c >= 0 なら、a * x <= c となる x は数列の任意の要素
        if c >= 0:
            count_pair += len(zero) * N
        # a > 0 の場合
        count_pair += np.searchsorted(A, c // positive, side='right').sum()
        # a < 0 の場合 (全体から引くようにすると、見通しがよい)
        count_pair += (N - np.searchsorted(A, (-c - 1) // (-negative), side='right')).sum()
        # 添字の順序に制約があることを反映する
        count_pair -= np.count_nonzero(A * A <= c)  # 「添字が同じ要素を 2 度選んだ場合」を引く
        return count_pair // 2

    # 数列から要素を 2 個選んで積を取ったとき、制約からあり得る値の範囲
    lower, upper = -10 ** 18, 10 ** 18
    while upper - lower > 1:
        x = (lower + upper) // 2
        if f(x) >= K:
            upper = x
        else:
            lower = x
    return upper

print(d_pairs())

Measured memory_bytes: 32316
#include <iostream>

#include <cstring>

#include <string>
#include <vector>
#include <algorithm>

#include <queue>

using namespace std;

#define SZ(a) int((a).size())
#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)

typedef long long llong;
typedef vector<int> VI;
typedef vector<VI> VVI;

int R, C;
int N;
int A[100*100 + 4];

int B[104][104];
void solve() {
   queue<int> q;
   FOR(i, 1, N) {
      REP(t, A[i])
         q.push(i);
   }

   FOR(r, 1, R) {
      if (r & 1) {
         FOR(c, 1, C) {
            B[r][c] = q.front();
            q.pop();
         }
      }
      else {
         for (int c = C; c >= 1; --c) {
            B[r][c] = q.front();
            q.pop();
         }
      }
   }
}

int main(int argc, char* argv[]) {
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);

   cin >> R >> C;
   cin >> N;
   FOR(i, 1, N)
      cin >> A[i];

   solve();

   FOR(r, 1, R) {
      FOR(c, 1, C) {
         if (c > 1) cout << ' ';
         cout << B[r][c];
      }
      cout << '\n';
   }

   return 0;
}


Measured memory_bytes: 384
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 3e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e5 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;


int x[MAXN];
int up[MAXN][LOG];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    int L;
    cin >> L;

    for (int i = 1; i <= n; ++i) {
        if (abs(x[n] - x[i]) <= L) {
            up[i][0] = n;
        } else {
            int id = lower_bound(x + 1, x + n + 1, x[i] + L + 1) - x;
            up[i][0] = id - 1;
        }
    }
    for(int j=1;j<LOG;++j){
        for(int i=1;i<=n;++i){
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }

    int q;
    cin >> q;
    while(q--){
        int a,b;
        cin>> a>> b;
        if(a  > b)
            swap(a,b);
        int ans = 0;
        for(int i = LOG-1;i>=0;--i){
            if(up[a][i] < b){
                a = up[a][i];
                ans+=(1<<i);
            }
        }
        cout << ans+1<<"\n";
    }


}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;
    while (t--)
        solve();
    dout << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n, m; std::cin >> n >> m;
  string s; std::cin >> s;
  int pos = s.size()-1;
  vi nums;
  while(pos > 0) {
    int npos = pos - m;
    while (npos < 0 || s[npos] == '1')
      npos++;
    if (npos == pos) pos = -1;
    else nums.pb(pos - npos), pos = npos;
  }
  if (pos == -1) std::cout << -1 << "\n";
  else drep(i, nums.size()) std::cout << nums[i] << (i-1 >= 0 ? " " : "\n");
}


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

int main () 
{
    int n;
    std::cin >> n;
    
    int a[n];
    
    for (int i = 0; i < n; i++) 
    {
        std::cin >> a[i];
    }
    
    for (int i = n-1; i >= 0; i--) 
    {
        std::cout << a[i];
        if (i != 0) std::cout << " ";
    }
    std::cout << std::endl;
    
    return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace  std;
int main()
{
    int n;
    cin>>n;
    vector <int > vec;

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        vec.push_back(x);

    }
    int min=1e9;
    for(auto it=vec.rbegin();it!=vec.rend();it++)
    {
        if(*it<=min)
        {
            min=*it;
        }
        else
        {
            if(*it-1!=min)
            {
                cout<<"No";
                return 0 ;
            }
        }

    }
    cout<<"Yes";



}


Measured memory_bytes: 892
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    long long W, H, x, y;
    cin >> W >> H >> x >> y;
    double S = 0.50 * W * H;
    bool deg = (2 * x == W) && (2 * y == H);
    cout << S << " " << deg << endl;
    return 0;
}


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

int in(){int x;cin>>x;return x;}

int main(){
	int N,D,X; cin>>N>>D>>X;
	int ans = X;
	while(N--) ans += (D-1)/in() + 1;
	cout<< ans <<endl;
}

Measured memory_bytes: 256