akhauriyash/Code-Regression huggingface dataset:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def enc(s):
  return [(1 if c == 'A' else 2) for c in s]

S = enc(input())
T = enc(input())

psumS = [0] + list(accumulate(S))
psumT = [0] + list(accumulate(T))

q = read()
for _ in range(q):
  a, b, c, d = reads()
  ms = psumS[b] - psumS[a-1]
  mt = psumT[d] - psumT[c-1]
  ans = (ms - mt) % 3 == 0
  print("YES" if ans else "NO")

Measured memory_bytes: 57664
import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while (t != 0) {
            int n = scan.nextInt();
            int a = 0;

            for (int i = 0; i < n; i++) {
                int s = scan.nextInt();
                int f = scan.nextInt();
                a += f - s;
            }
            if (a >= t) {
                System.out.println("OK");
            } else {
                System.out.println(t - a);

            }
            t = scan.nextInt();
        }
    }
}



Measured memory_bytes: 31280
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
 
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int64_t N, K, Q;
  cin >> N >> K >> Q;
  int64_t A[Q+1], B[N+1] = {};
  for(int i=1;i<=Q;i++){
    cin >> A[i];
    B[A[i]]++;
  }
  for(int i=1;i<=N;i++){
    if(Q - B[i] < K){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define forN(i, n) for(int i = 0; i <n ; ++i)
#define endl "\n"
typedef long long ll;
using namespace  std;
const ll INF = 1e18;
const ll MOD = 1000000007;
const int N = 2e5 + 5;
ll n , A[N] , ans;

int main(){
    fastIO;
    cin>>n;
    for(int i = 0 ; i<n ; i++){
        cin>>A[i];
    }
    for(int i = 1 ; i<n ; i++){
        if(A[i]<A[i-1]){
            ans+= A[i-1] - A[i];
            A[i] += A[i-1] - A[i];
        }
    }
    cout<<ans;
}


Measured memory_bytes: 5192
#include <stdio.h>
#include <stdlib.h>

#define MAX 100001
#define LEN 11

static int head = 0;
static int tail = 0;
static int queue[MAX];

void enqueue(int x);
int dequeue(void);
int isEmpty(void);
int isFull(void);


int main(void){
  int i, x, n, q, *time, sum = 0;
  char **name;

  scanf("%d%d", &n, &q);
  name = (char **)malloc(sizeof(char *) * n);
  time = (int *)malloc(sizeof(int) * n);
  for(i = 0; i < n; i++){
    name[i] = (char *)malloc(sizeof(char) * LEN);
    scanf(" %s%d", name[i], &x);
    time[i] = x;
    enqueue(i);
  }

  while(!isEmpty()){
    i = dequeue();
    if(time[i] > q){
      time[i] -= q;
      sum += q;
      enqueue(i);
    }else{
      sum += time[i];
      printf("%s %d\n", name[i], sum);
    }
  }
  
  for(i = 0; i < n; i++){
    free(name[i]);
  }
  free(name);
  return 0;
}


void enqueue(int x){
  if(isFull()){
    printf("?????????????????????\n");
    exit(1);
  }
  queue[tail] = x;
  tail = (tail + 1) % MAX;
}


int dequeue(void){
  int x;
  if(isEmpty()){
    printf("??¢??????????????????\n");
    exit(1);
  }
  x = queue[head];
  head = (head + 1) % MAX;
  return x;
}


int isEmpty(void){
  return head == tail;
}


int isFull(void){
  return head == (tail + 1) % MAX;
}

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

int main(void){
    // Your code here!
   char a, b;
   cin >> a >> b;
   if(a == 'H'){
       if(b == 'H'){
           cout << "H" << endl;
       } else {
           cout << "D" << endl;
       }
   } else {
       if(b == 'H'){
           cout << "D" << endl;
       } else {
           cout << "H" << endl;
       }
   }
}


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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(int i=x;i<y;i++)
#define frr(i,x,y) for(int i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
string s;
bool check(ll idx)
{
    string tmp="";
    fr(j,0,5)
    {
        tmp+=s[idx+j];
    }
    if(tmp=="erase")
        return true;
    else
        return false;
}
void solve()
{
    map<string,ll>mp;
    mp["dream"]=4;
    mp["dreamer"]=6;
    mp["erase"]=4;
    mp["eraser"]=5;
    cin>>s;
    bool fg=true;
    fr(i,0,SZ(s))
    {
        if(s[i]=='e'||s[i]=='d')
        {
            //cout<<i<<" ";
            ll up=-1;
            string tmp="";
            fr(j,0,10)
            {
                if(s[i+j]=='e')
                {
                    if(check(i+j)&&j!=0)
                        break;
                }
                tmp+=s[i+j];
                if(mp.count(tmp))
                {
                    //cout<<tmp<<endl;
                    up=i+mp[tmp];
                }
            }
            //cout<<up<<endl;
            if(up==-1)
            {
                fg=false;
            }
            else
            {
                i=up;
            }
        }
        else
        {
            fg=false;
        }
    }
    if(fg)
    {
        cout<<"YES\n";

    }
    else
    {
        cout<<"NO\n";
    }
    return;
}
int main()
{
    IOS;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define  rep(i,n) for(li i=0;i<(n);i++)
using namespace std;
typedef vector<int> vi;
typedef long int li;
typedef unsigned long long ull;


int main(int argc,char* argv[])
{
	int a,b,c;
	cin>>a>>b>>c;
	if(a+b==c||b+c==a||c+a==b)cout<<"Yes\n";
	else cout<<"No\n";

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
struct node{
	int val;
	int index;
	int b;
}a[200000];
bool comp1(node a,node b){
	return a.val < b.val;
}
bool comp2(node a,node b){
	return a.index < b.index;
}
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a[i].val);
		a[i].index = i;
	}
	sort(a+1,a+n+1,comp1);
	for(int i = 1;i <= n;i ++){
		a[i].b = i;
	}
	sort(a+1,a+n,comp2);
	int cnt[2] = {0,0};
	for(int i = 1;i <= n;i ++){
		if((a[i].index & 1) == (a[i].b & 1)){
			continue;
		}
		else {
			cnt[(a[i].index & 1)] ++;
		}
	}
	printf("%d",max(cnt[0],cnt[1]));
	return 0;
}

Measured memory_bytes: 1408
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[LEN+1];
int head, tail, n;

void enqueue(P);
P dequeue();
int min(int,int);
  
int main(){
  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }

  head = 1;
  tail = n+1;

  while(head != tail) {

    u = dequeue();
    c = min(q,u.t);

    u.t -= c;
    elaps += c;

    if(u.t > 0) enqueue(u);
    else printf("%s %d\n",u.name,elaps);
    
  }
  
  
  return 0;
  
}

void enqueue(P x) {
  
  Q[tail] = x;
  tail = (tail +1)%LEN;
  
}

P dequeue() {
  
  P x = Q[head];
  head = (head + 1)%LEN;
  
  return x;
  
}

int min(int a,int b) {
  return ( a < b ? a : b );
}


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

int main(){
	
	int w,h,x,y,r;
	cin>>w>>h>>x>>y>>r;
	if(r<=x && x<=w-r && r<=y&&y<=h-r)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	
	return 0;
}


Measured memory_bytes: 1156
import java.util.*;

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

        String s1 = scan.next();
        String s2 = scan.next();
        if(s1.length() != s2.length()){
            System.out.println("No");
            return;
        }
        int i , j;
        for(i = 0; i < s1.length(); i++){
            for(j = 0; j < s1.length(); j++){
                if(s1.charAt((i+j)%s1.length())==s2.charAt(j))
                    continue;
                break;
            }
            if(j == s1.length()){
                System.out.println("Yes");
                return;
            }
        }
        System.out.println("No");
    }
}


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

int64_t min64(int64_t x,int64_t y){
    if(x>y){
        return y;
    }else{
        return x;
    }
}
int64_t abs64(int64_t x){
    if(x>=0){
        return x;
    }else{
        return -x;
    }
}

int main(){
    int64_t x,k;
    cin >> x >> k;
    //cout << x << endl;
    int64_t p;
    int64_t ans=0;
    ans = min64(x%k,abs((x%k)-k));
    cout << ans << endl;    
}

Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

using namespace std;

int main() {
	long long n;
	cin >> n;
	vector<long long> cap(5);
	for (int i = 0; i < 5; i++)
		cin >> cap[i];

	int minidx = 0;
	for (int i = 0; i < 5; i++) {
		if (cap[i] < cap[minidx])
			minidx = i;
	}

	long long res = minidx + ((n - 1) / cap[minidx] + 1) + (4 - minidx);

	cout << res << endl;


	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))

cnt0,cnt1,cnt2 = 0,0,0

for i in range(n):
    if a[i]%4 == 0:
        cnt2 += 1
    elif a[i]%2 == 0:
        cnt1 += 1
    else:
        cnt0 += 1

if cnt1 == 0:
    if cnt0 - cnt2 <= 1:
        print('Yes')
    else:
        print('No')
else:
    if cnt0 - cnt2 <= 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 14252
import sys
input = sys.stdin.readline
import bisect
N = int(input())
A = list(map(int,input().split()))

P = A[0]
Q = A[1]
Lsum = P+Q
Ldiff = abs(P-Q)
Li = 1
Rsum = sum(A) - Lsum
R = A[2]
S = Rsum - R
Rdiff = abs(R-S)
Ri = 3
while abs(R-S+2*A[Ri]) < Rdiff:
    R += A[Ri]
    S -= A[Ri]
    Ri += 1
    Rdiff = abs(R-S)
 
def diff(x):
    x.sort()
    return x[-1] - x[0]

ans = diff([P,Q,R,S])
for i in range(3, N-1):
    Q += A[i-1]
    R -= A[i-1]
    Ldiff = abs(P-Q)
    Rdiff = abs(R-S)
    while abs(P-Q+2*A[Li]) < Ldiff:
        P += A[Li]
        Q -= A[Li]
        Li += 1
        Ldiff = abs(P-Q)
    while abs(R-S+2*A[Ri]) < Rdiff:
        R += A[Ri]
        S -= A[Ri]
        Ri += 1
        Rdiff = abs(R-S)
    ans = min(ans, diff([P,Q,R,S]))

print(ans)




    



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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<string, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF INT_MAX/3

#define MAX_N 1000

int n,q;
PPI ps[1111];

int main(){
	cin.sync_with_stdio(false);
	while(1){
		cin>>n>>q;
		if(n==0)break;
		rep(i,n){
			cin>>ps[i].fi.fi>>ps[i].fi.se>>ps[i].se;
		}
		rep(i,q){
			int a;
			cin>>a;
			bool ok=false;
			rep(i,n){
				if(ps[i].se-ps[i].fi.se<a&&a<=ps[i].se){
					ok=true;
					cout<<ps[i].fi.fi<<" "<<ps[i].fi.se-(ps[i].se-a)<<endl;
				}
			}
			if(!ok)cout<<"Unknown"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3236
#include<iostream>

using namespace std;

int main(void) {
	int N, K;
	cin >> N >> K;
	int Ans = 0;

	for (int i = 0; i < 1000000000; i++) {
		if (N / K != 0) {
			Ans += 1;
			N = N / K;

		}
		else {
			Ans += 1;
			break;
		}
	}
	cout << Ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
	string s;
	cin>>s;
	if(s[5]=='1'||s[6]>'4'){
		cout << "TBD" << endl;
	}
	else{
		cout << "Heisei" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
from collections import Counter
N=int(input())
v=list(map(int,input().split()))
even=[]
odd=[]
for n in range(N):
    if n%2==0:
        even.append(v[n])
    else:
        odd.append(v[n])
evens=Counter(even)
odds=Counter(odd)
even_value_max=max(evens.values())
odds_value_max=max(odds.values())
even_numbers=[]
odds_numbers=[]
for key,value in evens.items():
    if value==even_value_max:
        even_numbers.append(key)
for key,value in odds.items():
    if value==odds_value_max:
        odds_numbers.append(key)
if len(evens)==1 and len(odds)==1 and v[0]==v[1]:
    answer=N//2
elif len(even_numbers)>=2 or len(odds_numbers)>=2:
    answer=N-even_value_max-odds_value_max
else:
    even=even_numbers[0]
    odd=odds_numbers[0]
    if even!=odd:
        answer=N-even_value_max-odds_value_max
    else:
        evens[even]=0
        odds[odd]=0
        if max(odds.values())>=max(evens.values()):
            answer=N-max(odds.values())-even_value_max
        else:
            answer=N-max(evens.values())-odds_value_max
print(answer)


Measured memory_bytes: 105172
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n-1; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e12)
#define PI (acos(-1))

int main(){
    string res;
    char c[3];
    cin >> c;
    sort(c,c+3);
    if(c[0] == 'a' && c[1] == 'b' && c[2] == 'c') res = "Yes";
    else res = "No";
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;

int h, w, n;

int main() {
	ios::sync_with_stdio(false);
	cin >> h >> w >> n;
	int x = max (h, w);
	if (n % x == 0)
		cout << n/x << endl;
	else
		cout << n/x + 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int a,b;
string s,m,n;
int main(){
	cin>>s;
	m='C';
	n='F';
	a=s.find(m);
	if(a!=string::npos)b=s.find(n,a+1);
	else {cout<<"No"<<endl;return 0;}
	if(a!=string::npos&&b!=string::npos)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
U=10**5
is_prime=[True]*(U+1)
is_prime[0]=False
is_prime[1]=False
for p in range(2,U+1):
    if p*p>U:
        break
    if is_prime[p]:
        for j in range(p*p,U+1,p):
            is_prime[j]=False

is_2017like=[0]*(U+1)
for p in range(1,U+1):
    if (p+1)//2>U:
        break
    tmp=(is_prime[p] and is_prime[(p+1)//2])
    is_2017like[p]=is_2017like[p-1]+tmp
    
for i in range(int(input())):
    l,r=map(int,input().split())
    ans=is_2017like[r]-is_2017like[l-1]
    print(ans)


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

int main(){
  
  vector<vector<int>> vec(3, vector<int>(3));
  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++){
      cin >> vec.at(i).at(j);
    }
  }
  
  vector<int> det(3);
  det.at(0) = vec.at(0).at(0)+vec.at(1).at(1)+vec.at(2).at(2);
  det.at(1) = vec.at(0).at(1)+vec.at(1).at(2)+vec.at(2).at(0);
  det.at(2) = vec.at(1).at(0)+vec.at(2).at(1)+vec.at(0).at(2);
  
  bool f = true;
  for (int i=1; i<3; i++){
    if (det.at(0) != det.at(i)){
      f = false;
      break;
    }
  }
  
  if (f) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}

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

#define X first
#define Y second
typedef long long ll;
typedef pair<ll,ll> pll;

int main(int argc, char const *argv[])
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    string s;
    cin >> s;
    ll w = 0;
    for (ll i=0; i<s.size(); i++) if (s[i]=='o') w++;
    if (w>=8 || 15-s.size()>=8-w) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
import collections
n=int(input())
a=list(map(int,input().split()))
dic={}
for i in a:
  if i in dic:
    dic[i]+=1
  else:
    dic[i]=1
a=[0,0]
mx=0
for i in dic:
  if dic[i]>=2:
    a.append(i)
    if dic[i]>3:
      mx=max(i**2,mx)
a=sorted(a)
mx=max(a[-1]*a[-2],mx)
print(mx)


Measured memory_bytes: 67608
#include<iostream>
#include<queue>
#include<map>
#include<unordered_map>
#include<stack>
using namespace std;
const long long int bign =1000000001;
int main(){
    int n;
    cin >> n;
    long long int a[n];
    long long int inp;
    long long int allxor=0;
    for(int i=0;i<n;i++){
        cin >> inp;
        allxor=(allxor^inp);
        a[i]=inp;
    }
    for(int i=0;i<n;i++){
        a[i]=(a[i]^allxor);
        if(i!=n-1)
        cout << a[i] << " ";
        else
        {
            cout << a[i] << endl;
        }
        
    }

    
    
    return 0;

}

Measured memory_bytes: 4680
#include<stdio.h>
#include<algorithm>
#include<utility>
using namespace std;
int abs(int n){
    return (n>=0)?n:-n;
}
int main(){
    int n;
    scanf("%d",&n);
    int num[n];
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
    }
    sort(num,num+n);
    int ai=num[n-1];
    int aj=num[0];
    for(int i=0;i<n-1;i++){
        if(abs(num[i]-ai/2)<=abs(aj-ai/2))aj=num[i];
    }
    printf("%d %d\n",ai,aj);

}

Measured memory_bytes: 512
n, k = gets.split.map(&:to_i)
p = gets.split.map(&:to_i)

def expectation(n)
  (n + 1)/2.0
end

max = 0
max_index = 0
tmp = 0

(0..n-k).each.with_index do |num, i|
  sum = 0
  if tmp.zero?
    (0...k).each do |k_num|
      sum += p[i + k_num]
    end
  else
    sum = tmp - p[i - 1] + p[i + k - 1]
  end
  tmp = sum
  if sum > max
    max = sum
    max_index = i
  end
end

i = max_index

answer = 0
(0...k).each do |k_num|
  answer += expectation(p[i + k_num])
end

puts answer


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

int a[10];
 

int main() {
    ios::sync_with_stdio(false);
   // freopen("input.txt", "r", stdin);
    string s; cin >> s;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < s.size(); j++) {
            if (i+j > s.size())
                break;
            string t = s.substr(0, i);
            string m = s.substr(i+j);
            if (t+m == "keyence") {
                cout << "YES\n";
                return 0;
            }

        }
    }


    cout << "NO\n";
    
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << x2 - (y2 - y1) << ' ' << y2 + (x2 - x1) << ' ' << x1 - (y2 - y1) << ' ' << y1 + (x2 - x1) << endl;
}

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


#define ll long long
#define MOD 1000000007
#define PI 3.1415


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

    vector<ll> a(n);
    for(int i=0;i<n;i++)cin>>a.at(i);

    ll sum=0;
    for(int i=1;i<n;i++){
        sum += abs(a.at(i) - max(a.at(i-1),a.at(i)));
        a.at(i) = max(a.at(i-1),a.at(i));
    }

    cout<<sum<<endl;

}



Measured memory_bytes: 4772
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end());
typedef long long ll;

int main(){
  int n;
  cin >> n;
  cout << "ABC" << n << endl;
}

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

#define REP(i,n) for (int i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
typedef long long ll;

using namespace std;
 
int main() {
	int n;
    cin>>n;
    int h[n];
    REP(i,n){
        cin>>h[i];
    }
    int cost[n];
    REP(i,n){
        if(i==0){
            cost[i]=0;
        }else if(i==1){
            cost[i]=abs(h[1]-h[0]);
        }else{
            int t1,t2;
            t1=cost[i-1]+abs(h[i]-h[i-1]);
            t2=cost[i-2]+abs(h[i]-h[i-2]);
            if(t1>t2){
                cost[i]=t2;
            }else{
                cost[i]=t1;
            }
        }
    }
    cout<<cost[n-1];
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
static mt19937 _g(time(nullptr));
 
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

int Q;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path __p = __FILE__;
        fs::path __input, __output;
        __input = __output = __p.parent_path();
        __input += string("/input/") + string(__p.stem()) + string(".txt");
        __output += string("/output/") + string(__p.stem()) + string(".txt");
        freopen(__input.c_str(), "r", stdin);
        freopen(__output.c_str(), "w", stdout);
    #endif
    cin >> Q;
}

int solve(){
    for (int i = 0; i < Q; i++)
    {
        ll a,b; cin >> a >> b;
        if(a>b) swap(a,b);
        if((b-a)<=1) {cout << 2*(a-1) << endl;}
        else{
            ll c;
            ll ok=1,ng=b+1;
            while(ng-ok>1){
                ll mid=(ok+ng)/2;
                if(mid*mid<a*b) ok=mid;
                else ng=mid;
            }
            c = ok;
            ll ans; 
            if(c*(c+1)<a*b) ans = 2*c-1;
            else ans = 2*(c-1);
            cout << ans << endl;
        }
    }
     
    return 0;
}   

int main()
{
    input();
    solve();
    return 0;
}


Measured memory_bytes: 256
import Foundation

func solve(n: Int, aSizes: [Int], bSizes: [Int], cSizes: [Int]) -> Int {

    return bSizes
        .map {
            let lowerCases = corneredBounds(searchValue: $0, list: aSizes, policy: .lower).left + 1
            let upperCases = n - corneredBounds(searchValue: $0, list: cSizes, policy: .upper).right
            return lowerCases * upperCases
        }
        .reduce(0, +)
}

func corneredBounds(searchValue: Int, list: [Int], policy: Direction) -> (left: Int, right: Int) {

    var openedLeft = -1
    var openedRight = list.count

    while openedRight - openedLeft > 1 {

        let mid = (openedRight + openedLeft) / 2

        func midValueShouldBeInLeftSide() -> Bool {
            policy.midValueShouldBeInLeftSide(at: mid, on: list, with: searchValue)
        }

        if midValueShouldBeInLeftSide() {
            openedLeft = mid
        }
        else {
            openedRight = mid
        }
    }

    return (openedLeft, openedRight)
}

enum Direction {

    case lower
    case upper

    func midValueShouldBeInLeftSide(at index: Int, on list: [Int], with searchValue: Int) -> Bool {

        switch self {
            case .lower: return list[index] <  searchValue ? true : false
            case .upper: return list[index] <= searchValue ? true : false
        }
    }
}

let n = Int(readLine()!)!
var aSizes = readLine()!.split(separator: " ").compactMap{ Int($0) }.sorted()
var bSizes = readLine()!.split(separator: " ").compactMap{ Int($0) }
var cSizes = readLine()!.split(separator: " ").compactMap{ Int($0) }.sorted()

let answer = solve(n: n, aSizes: aSizes, bSizes: bSizes, cSizes: cSizes)
print(answer)


Measured memory_bytes: 24496
import java.util.Scanner;

public class Main {

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

		int n = in.nextInt();
		long time = in.nextLong();
		long[] t = new long[n];

		for (int i = 0; i < n; i++) {
			t[i] = in.nextLong();
		}

		long bLast = -1;
		long nTop = 0;;
		long ans = 0;
		for (int i = 0; i < n; ++i) {
			nTop = t[i];
			if(bLast >= nTop) {
				ans += nTop + time - bLast;
			} else {
				ans += time;
			}
			bLast = nTop + time;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 83288
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;
long gyaku(long a, long mod){
  long long s = 1, tmp = a, t = mod - 2;
  while(t > 0){
    if(t % 2 == 1){
      s *= tmp;
      s %= mod;
    }
    t /= 2;
    tmp *= tmp;
    tmp %= mod;
  }
  return s;
}
int main(){
  int n, k; string s; cin >> k >> s; n = s.size();
  long a = 0, b = 1e9+7;
  vector<long> v(k+1, 1), u(k+1, 1), w(n+k+1, 1), x(n+k+1, 1);
  rep(i, n+k){
    w[i+1] = w[i] * (i+1); w[i+1] %= b;
    x[i+1] = x[i] * gyaku(i+1, b); x[i+1] %= b;
  }
  rep(i, k){
    v[i+1] = v[i] * 26; v[i+1] %= b;
    u[i+1] = u[i] * 25; u[i+1] %= b;
  }
  rep(i, k+1){
    long t = v[i] * u[k-i] % b;
    t *= w[n+k-i-1]; t %= b;
    t *= x[k-i]; t %= b;
    t *= x[n-1]; t %= b;
    a += t;
    a %= b;
  }
  cout << a << "\n";
  return 0;
}

Measured memory_bytes: 51140
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import Decimal
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations
# from operator import add, mul, sub, itemgetter
# import numpy as np

import sys
sys.setrecursionlimit(10000)

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time
	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def read_int(input=None):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [int(x) for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret

def read_float(input):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [float(x) for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret
	
def read_str(input):
	if input == None:
		input = sys.stdin.readline().strip()
	ret = [x for x in input.split()]
	if len(ret) == 1:
		ret = ret[0]
	return ret
		
def read_int(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return int(read)

def read_int_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [int(x) for x in read.split()]

def read_float(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return float(read)

def read_float_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [float(x) for x in read.split()]

def read_str(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return str(read)

def read_str_n(read=None):
	if read == None:
		read = sys.stdin.readline().strip()
	return [str(x) for x in read.split()]	

@mt
def slv(*args):
	X.sort()
	
	'''
	Y = []
	for i in range(M-1):
		Y.append(X[i+1] - X[i])
	'''
	Y = [X[i+1] - X[i] for i in range(M-1)]
	Y.sort(reverse=True)
	
	ans = X[-1] - X[0]
	for y in Y[:N-1]:
		ans -= y
	
	return ans

if __name__ == '__main__':
	t = '''3 7
-10 -3 0 9 -100 2 17'''.splitlines()
	
	N, M = read_int_n()
	X = read_int_n()
	
	print(slv(N,M,X))
	

Measured memory_bytes: 14592
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int len =Integer.parseInt(sc.nextLine());
		double[] line = Stream.of(sc.nextLine().split(" ", 0)).mapToDouble(Double::parseDouble).toArray();
		Arrays.sort(line);
		double ans = line[0];
		for (int i = 1; i < len; i++) {
			ans = (ans + line[i]) / 2;
		}

		System.out.println(ans);
	}
}


Measured memory_bytes: 36292
N = int(input())
a, b = [None]*N, [None]*N
for i in range(N):
    a[i], b[i] = map(int, input().split())
c = 0
for i in range(N)[::-1]:
    r = (a[i]+c)%b[i]
    if r:
        c += b[i]-r
print(c)

Measured memory_bytes: 10868
x = int(input())

def isprime(s):
  if s>2 and s%2==0:
    return False
  else:
    flg = True
    for i in range(3, s//2+1, 2):
      if s%i == 0:
        flg = False
        break
    return flg

for i in range(x, 10**6):
  if isprime(i) == True:
    print(i)
    break

Measured memory_bytes: 9152
directions = input()
N=len(directions)
ans = [0 for _ in range(N)]

count=[0,0]
location = 0
for i in range(N-1):
    count[i%2]+=1
    if directions[i:i+2] == "RL":
        location = i
    if directions[i:i+2] == "LR":
        ans[location]=count[location%2]
        ans[location+1]=count[(location+1)%2]
        count=[0,0]
count[(N-1)%2] += 1
ans[location]=count[location%2]
ans[location+1]=count[(location+1)%2]

        
print(*ans)

Measured memory_bytes: 6408
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	cin >> N;
	map<int, int> r;
	int x = 0;
	for (int i = 0; i < N; ++i) {
		int a;
		cin >> a;
		if (a < 3200) {
			++r[a / 400];
		}
		else {
			++x;
		}
	}
	int mn = max<int>(1, r.size());
	int mx = r.size() + x;
	cout << mn << " " << mx << endl;
}


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

#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;

const int MAX = 103;
const int INF = 1 << 21;
int dp[MAX][MAX];
int p[MAX];

void solve(int n) {
  for (int i=1; i<=n; i++) {
    dp[i][i] = 0;
  }

  for (int l=2; l<=n; l++) {
    for (int i=1; i<=(n-l+1); i++) {
      int j = i + l - 1;
      dp[i][j] = INF;
      for (int k=i; k<=(j-1); k++) {
	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]);
      }
    }
  }
}

int main() {
  int n;
  cin >> n;
  for (int i=1; i<=n; ++i) {
    cin >> p[i-1] >> p[i];
  }

  solve(n);
  cout << dp[1][n] << endl;
  return 0;
}



Measured memory_bytes: 3124
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())

ans = 0
for i in range(1, n + 1, 2):
    tmp = 0
    for j in range(1, n + 1, 1):
        if i % j == 0:
            tmp += 1

    if tmp == 8:
        ans += 1

print(ans)


Measured memory_bytes: 5120
def main():
    lun_luns = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    k = int(input())

    def make_lunlun(number):
        min = str(number)[-1]
        new_lunlun = number * 10 + int(min)
        if min == "0":
            return (new_lunlun, new_lunlun + 1)
        elif min == "9":
            return (new_lunlun - 1, new_lunlun)
        else:
            return (new_lunlun - 1, new_lunlun, new_lunlun + 1)

    index = 0
    while True:
        if len(lun_luns) >= k:
            break
        num = lun_luns[index]
        lun_luns.extend(make_lunlun(num))
        index += 1
    print(lun_luns[k - 1])

if __name__ == '__main__':
    main()

Measured memory_bytes: 44396
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

signed main(){
	int n, t;
	scanf("%lld%lld", &n, &t);
	double res = 0;
	rep(i,n){
		int x, y;
		scanf("%lld%lld", &x, &y);
		res = max(res, (double)y/x);
	}
	printf("%.8lf\n", res*t);
	return 0;
}







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


int main() {
  int N;
  
  cin >> N;
  
  if((N/1000 == (N-N/1000*1000)/100)  && ((N-N/1000*1000)/100 == (N-N/100*100)/10) || ((N-N/1000*1000)/100 == (N-N/100*100)/10) && ((N-N/100*100)/10 == N-N/10*10)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
ab = []
for i in range(m):
    ab.extend(LIST())
for i in range(n):
    ans = ab.count(i + 1)
    print(ans)

Measured memory_bytes: 59628
import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

import javax.xml.crypto.Data;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder[] sb = new StringBuilder[1000];
		for(int i = 0; i < sb.length; i++) {
			sb[i] = new StringBuilder();
		}
		int len = 0;
		while(true) {
			String in = sc.nextLine();
			if(in.equals("END_OF_TEXT")) break;
			sb[len++].append(in);
		}
		boolean LF = false;
		StringBuilder buffer = new StringBuilder();
		int ci = 0;
		int cj = 0;
		while(true) {
			String in = sc.nextLine();
			if(in.equals("-")) break;
			if(in.equals("a")) {
				cj = 0;
				continue;
			}
			if(in.equals("e")) {
				cj = sb[ci].length();
				continue;
			}
			if(in.equals("p")) {
				if(ci != 0) {
					ci--;
				}
				cj = 0;	
				continue;
			}
			if(in.equals("n")) {
				if(ci+1 != len) {
					ci++;
				}
				cj = 0;
				continue;
			}
			if(in.equals("f")) {
				if(cj != sb[ci].length()) {
					cj++;
				}
				else {
					if(ci+1 != len) {
						ci++;
						cj = 0;
					}
				}
				continue;
			}
			if(in.equals("b")) {
				if(cj != 0) {
					cj--;
				}
				else {
					if(ci != 0) {
						ci--;
						cj = sb[ci].length();
					}
				}
				continue;
			}
			if(in.equals("d")) {
				if(cj != sb[ci].length()) {
					sb[ci].deleteCharAt(cj);
				}
				else {
					if(ci+1 != len) {
						sb[ci].append(sb[ci+1]);
						int now = ci+1;
						while(now+1 != len) {
							sb[now] = sb[now+1];
							now++;
						}
						len--;
					}
				}
			}
			if(in.equals("k")) {
				if(cj == sb[ci].length()) {
					if(ci+1 != len) {
						sb[ci].append(sb[ci+1]);
						int now = ci+1;
						while(now+1 != len) {
							sb[now] = sb[now+1];
							now++;
						}
						len--;
					}
					buffer = new StringBuilder();
					LF = true;
				}
				else {
					buffer = new StringBuilder(sb[ci].substring(cj, sb[ci].length()));
					sb[ci].delete(cj, sb[ci].length());
					cj = sb[ci].length();
					LF = false;
				}
			}
			if(in.equals("y")) {
				if(LF) {
					int now = len;
					while(now != ci) {
						sb[now] = sb[now-1];
						now--;
					}
					len++;
					sb[ci+1] = new StringBuilder(sb[ci].substring(cj,sb[ci].length()));
					sb[ci].delete(cj, sb[ci].length());
					ci++;
					cj = 0;
				}
				else {
					if(cj == sb[ci].length()) {
						sb[ci].insert(cj, buffer);
						cj = sb[ci].length();
					}
					else {
						sb[ci].insert(cj, buffer);
						cj += buffer.length();
					}
				}
			}
		}
		for(int i = 0; i < len; i++) {
			System.out.println(sb[i].toString());
		}
		
		
	}
}

Measured memory_bytes: 26476
import sys
# A,B,C = [int(n) for n in input().split()]
N = int(input())
x = [0]*N
u = [0]*N
ans = 0
for i in range(N):
    x[i],u[i] = [n for n in input().split()]
    if(u[i] == "JPY"):
        ans += float(x[i])
    else:
        ans += float(x[i])*380000

print(ans)


Measured memory_bytes: 3060
#include<iostream>  
#include<vector>
#include<string>  
#include<set>  
#include<map>  
#include<algorithm>  
#include<queue>  
#include<list>  
#include<stack>  
#include<cstdio>  
#include<fstream>  
#include<numeric>  
#include<functional>  
#include<utility>  
#include<memory> 
using namespace std;
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	if ((a+b)==(c+d)) cout<<"Balanced";
	if ((a+b)>(c+d)) cout<<"Left";
	if ((a+b)<(c+d)) cout<<"Right";
	return 0;
}

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

int main(){
  	int a[3][3];
	int d[3][3];
  
	rep(i, 3)rep(j, 3) cin >> a[i][j];
  	int n;
  	cin >> n;
  	rep(i, n){
    	int x;
      	cin >> x;
      	rep(i,3)rep(j,3) if(a[i][j] == x) d[i][j] = 1;
    }
  
  	bool ans = false;
  	rep(i, 3){
    	int cnt = 0;
      	rep(j, 3) cnt += d[i][j];
        if(cnt == 3) ans = true;
   	}
  	rep(i, 3){
    	int cnt = 0;
      	rep(j, 3) cnt += d[j][i];
      	if(cnt == 3) ans = true;
   	}
  	{
  		int cnt = 0;
  		rep(i, 3) cnt += d[i][i];
  		if(cnt == 3) ans = true;
    }
  	{
  		int cnt = 0;
  		rep(i, 3) cnt += d[i][2 - i];
  		if(cnt == 3) ans = true;
    }
  
  	puts(ans ? "Yes" : "No");
}

Measured memory_bytes: 256
n = int(input())
a = list(map(str, input().split()))

d = {}
t = 0
for i in a:
    if not i in d.keys():
        d[i] = 1
    else:
        d[i] += 1
    t += int(i)

q = int(input())

for _ in range(q):
    b, c = map(str, input().split())
    diff = 0
    if b in d.keys() and c in d.keys():
        diff = (int(c) - int(b)) * d[b]
        d[c] += d[b]
        d.pop(b)
    elif b in d.keys():
        diff = int(c) * d[b] - int(b) * d[b]
        d[c] = d[b]
        d.pop(b)
    t += diff
    print(t)
    

Measured memory_bytes: 22980
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int main() {
    int n;

    cin >> n;

    int ans = 1;

    while (n >= ans * 2)
    {
        ans *= 2;
    }

    cout << ans << endl;


    return 0;
} 


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t x, K;
  cin>>x>>K;
  int64_t t=0;
  if(x>K){
    t=x%K;
    if(t<K-t){
      cout<<t<<endl;
    }
    else{
      cout<<K-t<<endl;
    }
  }
  else{
    t=x;
    if(t<K-t){
      cout<<t<<endl;
    }
    else{
      cout<<K-t<<endl;
    }
  }
    
}
  

Measured memory_bytes: 3640
S = int(input())

mod = 1000000007

dp = [0] * 2001

dp[0] = 0
dp[1] = 0
dp[2] = 0
dp[3] = 1

for s in range(4, S + 1):
    total = 1
    for k in range(3, s + 1):
        total += dp[s - k] % mod

    dp[s] = total % mod

print(dp[S])


Measured memory_bytes: 9088
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def conb(n,r): 
    if n<r: return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_factorize(n):
    if n == 1:
        return [1]
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = inp()
d = defaultdict(int)
for i in range(1,n+1):
    for x in prime_factorize(i):
        d[x] += 1

valist = d.values()
c = [2,4,14,24,74]
cnt = [0] * 5
for x in valist:
    if x >= 74: cnt[4] += 1
    elif x >= 24: cnt[3] += 1
    elif x >= 14: cnt[2] += 1
    elif x >= 4: cnt[1] += 1
    elif x >= 2: cnt[0] += 1
# print(cnt)
res = 0
a = sum(cnt[1:]); b = cnt[0]
res += conb(a,3)*3 + conb(a,2)*b
a = sum(cnt[2:]); b = cnt[1]
res += a*(a-1) + a*b
a = sum(cnt[3:]); b = sum(cnt[:3])
res += a*(a-1) + a*b
res += cnt[4]
print(res)


Measured memory_bytes: 10500
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int64_t K,N;
  cin>>K>>N;
   vector<int64_t> a(N);
  for(int64_t i=0;i<N;i++){
    cin>>a.at(i);
  }
  int64_t x=0;
  for(int64_t i=0;i<N-1;i++){
    if(x > a.at(i+1) - a.at(i) ){
      continue;
    }
    else{
      x = a.at(i+1) - a.at(i);
    }
  }
  if(x < K+a.at(0)-a.at(N-1)){
    x=K+a.at(0)-a.at(N-1);
  }
  cout<<K-x<<endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define vi vector<int>
#define pb push_back
using namespace std;
int n,d;
int main()
{
	cin>>n>>d;
	cout<<n/(d*2+1)+(n%(d*2+1)!=0)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

//S is the data type that is stored in the segment tree nodes
struct S {
	modint value; //Stores the value represented by all the digits in the segment
	int digits; //Stores how many digits are in this node
};
//For example, a node for "3572" will have value = 3572 and digits = 4

//Op is the operation that merges two segments into one
S op(S l, S r) {
	//The new value will be the left value multiplied by 10^(number of digits of the right value) + the right value
	//The new number of digits is the sum of the number of digits from both segments
	return S { l.value * modint(10).pow(r.digits) + r.value, l.digits + r.digits };
}

//e is created such that op(l,e) == l and op(e,r) == e. It should not modify the other value that is not e.
//The value 0 works since it will add nothing, and digits = 0 doesn't add more digits.
S e() {
	return S { 0, 0 };
}


//F contains the attributes of the function that is applied to a segment
//The actual function is implemented in "mapping"
struct F {
	modint digit; //Stores the digit to assign to the segment
	int t; //Stores the "time" of the operation, later assignments have priority over early ones
		   //Special case when t == -1, in this case the function will act as the identity function (it will not modify the node)
};


//mapping is the function that is applied to a segment with "apply"
//This function replaces every digit in the segment
S mapping(F l, S r) {
	if (l.t == -1) {
		//Special case, do not modify the node.
		return r;
	}
	//The value has to be replaced with 'l.digit' repeated 'r.digit' times.
	//We can do that with the formula 111...1 (n times) = ((10^n)-1)/9 and multiply that by 'l.digit'
	return S { (modint(10).pow(r.digits) - 1) * modint(9).inv() * l.digit,	r.digits };
}

//composition is the way to combine two functions that were applied to the same segment.
//If we have two updates, the one with the latest time will be kept
F composition(F l, F r) {
	return F { l.t > r.t ? l : r };
}

//id should represent a function that does not modify the node.
//In this case, set t=-1 since it is the special case
F id() {
	return F { 0, -1 };
}

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

	int n;
	cin >> n;
	vector<S> arr(n, S { 1, 1 }); //Fill with '1' (also, they have 1 digit)

	lazy_segtree<S, op, e, F, mapping, composition, id> seg(arr);

	int t = 0;

	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		
		x--;
		y--;
		
		y++; //The right has to be excluded
		
		int d;
		cin >> d;
		
		//'apply' applies 'mapping' to the segment [x,y) with attributes digit=d and the time is always increased by 1
		seg.apply(x, y, F { modint(d), t++ });
		
		//all_prod gets the value of the node that represents the whole number
		cout << seg.all_prod().value.val() << "\n";
	}

}


Measured memory_bytes: 10844
Q = $stdin.gets.chomp.to_i

qp = (0...100000).to_a
qp[0] = 0; qp[1] = 0
k = 2
while true
  break if k == qp.size
  if qp[k] > 0
    kk = k
    (k+k).step(qp.size-1, k) { |kk|
      qp[kk] = 0
    }
  end
  k += 1
end


lll = []
qp.each{ |q|
  if q == 0 || qp[(q+1)/2] == 0
    lll << (lll[-1] || 0)
    next
  end
  
  lll << (lll[-1] || 0) + 1
}

#p lll

Q.times{
	l,r = $stdin.gets.chomp.split(" ").map{ |a| a.to_i }
    puts lll[r] - lll[l-1]
}



Measured memory_bytes: 3836