akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


	/* constants */
	#define inf (int)1e+9
	#define VIS 1
	#define UNVIS 0
	#define null NULL
	#define MAX (int)1e+6
	#define MIN -(int)1e+6
	
// ------------------------------------------------------------------------

int n;
vector<int> v;
vector<int> memo((int)1e5+5,-1);

int minCost(int k) {

	if (memo[k]!=-1)
		return memo[k];

	if (k==(n-1)) 
		return 0;

	if (k==n) 
		return inf;


	int a=minCost(k+1)+abs(v[k]-v[k+1]);
	int b=minCost(k+2)+abs(v[k]-v[k+2]);

	memo[k]=min(a, b);
	return memo[k];
}

int main()
{
	
	cin.tie(NULL);
	cout.tie(NULL);

	/*Start*/
	

	int x;
	scanf("%d",&n);
	v.resize(n);

	for (int i=0; i<n; i++) {
		scanf("%d",&x);
		v[i]=x;
	}

	cout<<minCost(0)<<endl; 
    return 0;
}


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

long long int x;

long long int l[87];
long long int lucas(long long int n)
{
    for (int i = 2; i <= n; i++)
        l[i] = l[i - 1] + l[i - 2];
    return l[n];
}

int main()
{
    l[0] = 2;
    l[1] = 1;
    cin >> x;
    cout << lucas(x) << endl;
    return 0;
}


Measured memory_bytes: 256
from functools import reduce
from itertools import product


def helper(dx,dy):
  if (dx,dy) == (0,0):
    return 'LR',0,0
  elif (dx,dy) == (0,1):
    return 'DD',0,1
  elif (dx,dy) == (0,2):
    return 'UU',0,0
  elif (dx,dy) == (1,0):
    return 'LL',1,0
  elif (dx,dy) == (1,1):
    return 'RU',0,0
  elif (dx,dy) == (1,2):
    return 'DR',0,1
  elif (dx,dy) == (2,0):
    return 'RR',0,0
  elif (dx,dy) == (2,1):
    return 'LU',1,0
  elif (dx,dy) == (2,2):
    return 'LD',1,1

def validate(D,solution):
  x,y = 0,0
  for d,m in zip(D,solution):
    if m == 'L':
      x -= d
    elif m == 'R':
      x += d
    elif m == 'D':
      y -= d
    else:
      y += d
  return x,y

def solve(x,y,n):

  result = []
  for i in range(n):
    xx = x%3
    yy = y%3

    s,a,b = helper(xx,yy)
    result.append(s)
    x = (x-xx)//3 + a
    y = (y-yy)//3 + b

  result = ''.join(result)
  return result,x,y


N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

#check
even = all(sum(p) % 2 == 0 for p in points)
odd = all(sum(p) % 2 == 1 for p in points)
if not even and not odd:
  print(-1)
  exit()



if even:
  D = sum(([3**i,3**i] for i in range(20)), list())
  print(len(D))
  print(' '.join(map(str, D)))
  for x,y in points:
    solution,_,_ = solve(x, y, 20)
    # print(validate(D,solution))
    print(solution)
else:
  D = sum(([3**i,3**i] for i in range(20)), list())[:-1]
  print(len(D))
  print(' '.join(map(str, D)))

  for x,y in points:
    solution,x,y = solve(x, y, 19)
    if (x,y) == (1,0):
      solution += 'R'
    elif (x,y) == (-1,0):
      solution += 'L'
    elif (x,y) == (0,1):
      solution += 'U'
    else:
      solution += 'D'
    # print(validate(D,solution))
    print(solution)



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

int a[100000],b[100000];
int main(){
	int n,k;scanf("%d%d",&n,&k);
	rep(i,n)scanf("%d%d",&a[i],&b[i]);
	ll Max=0;
	rep(i,n){
		if((k|a[i])==k)Max+=b[i];
	}
	rep(i,30){
		if(!(k>>i&1))continue;
		ll sum=0;
		int c=(k^(1<<i))|((1<<i)-1);
		rep(j,n){
			if((c|a[j])==c)sum+=b[j];
		}
		Max=max(Max,sum);
	}
	cout<<Max<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
    int N,K,X,Y;
    cin>>N>>K>>X>>Y;

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


Measured memory_bytes: 3600
def resolve():
    import math
    n, k = map(int, input().split())
    ans = 0
    for i in range(1, n+1):
        if k <= i:
            coin = 0
        else:
            coin = math.ceil(math.log(k/i,2))
        ans += (1/n)*(1/(2**coin))
    print(ans)
resolve()

Measured memory_bytes: 38640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

// template from zscoder

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  string s;
  cin >> s;
  s[3]='8';
  cout << s;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)

	sum := make(map[int]int)
	sum[0] = 0
	for i := 1; i < n; i++ {
		if string(s[i]) == "E" {
			sum[0]++
		}
	}
	for i := 1; i < n; i++ {
		sum[i] = sum[i-1]
		if string(s[i]) == "E" {
			sum[i]--
		}
		if string(s[i-1]) == "W" {
			sum[i]++
		}
	}

	min := n
	for _, v := range sum {
		if v < min {
			min = v
		}
	}
	fmt.Println(min)
}


Measured memory_bytes: 22400
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string O,E;cin>>O>>E;
  string ans;
  repeat(i,E.length()){
    ans += O[i];
    ans += E[i];
  }
  if(O.length()>E.length())ans+=O.back();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>


using namespace std;

int main()
{
	int N;
	cin>>N;
	map<string,int> dict;
	int maxCount = 1;
	for(int i = 0; i < N; i++){
		string str;
		cin>>str;
		if( dict.count(str) == 0){
			dict.insert(make_pair(str,1));
		}else{
			dict[str] = dict[str] + 1;
			maxCount = max(maxCount,dict[str]);
		}
	}
	vector<string> strArray;
	for( auto itr = dict.begin(); itr != dict.end(); itr++){
		//cout<<itr->first<<" "<<itr->second<<endl;
		if(itr->second == maxCount){
			strArray.push_back(itr->first);
		}
	}
	sort(strArray.begin(),strArray.end());
	for(int i = 0; i < strArray.size(); i++){
		cout<<strArray[i]<<endl;
	}
	
	return 0;
}



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

int main(){
    int sx,sy,tx,ty;
    vector<char> route;
    cin >> sx >> sy >> tx >> ty;
    for(int x=sx+1;x<=tx;x++) route.emplace_back('R');
    for(int y=sy+1;y<=ty;y++) route.emplace_back('U');
    for(int x=sx+1;x<=tx;x++) route.emplace_back('L');
    for(int y=sy+1;y<=ty;y++) route.emplace_back('D');
    route.emplace_back('D');
    for(int x=sx+1;x<=tx+1;x++) route.emplace_back('R');
    for(int y=sy;y<=ty;y++) route.emplace_back('U');
    route.emplace_back('L');
    route.emplace_back('U');
    for(int x=sx;x<=tx;x++) route.emplace_back('L');
    for(int y=sy;y<=ty;y++) route.emplace_back('D');
    route.emplace_back('R');
    for(int i=0;i<route.size();i++) cout << route[i];
    cout << endl;
    return 0;
}

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

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

using namespace std;

int main(){
  int n;cin>>n;
  rep(i,50000){
    if((int)floor(i*1.08)==n){
      cout<<i;
      return 0;
    }
  }

  cout<<":(";

  return 0;
}


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

int main(void){
	int n,sum=0;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i];
		sum+=v[i];
	}
	for(int i=1;i<n;i+=2) sum-=2*v[i];
	vector<int> ans(n);
	ans[0]=sum;
	for(int i=1;i<n;i++){
		ans[i]=(v[i-1]-(ans[i-1]/2))*2;
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

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

using namespace std;

int N, K;
int A[200000];

void solve() {
    int res[200001] = {0};
    for (int i = 0; i < N; ++i) {
        res[A[i]]++;
    }
    sort(res, res + 200001, greater<>());
    int num = 0;
    for (int i = K; i < 200001; ++i) {
        num += res[i];
    }
    printf("%d\n", num);
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    solve();
    return 0;
}

Measured memory_bytes: 5240
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

bool solve(){
  ll n;cin>>n;
  vector<ll>a(n);
  rep(i,n)cin>>a[i];

  ll dp[n+1][n+1];
  rep(i,n+1)dp[i][i]=0;

  for(int w=1;w<=n;w++){
    for(int l=0;l+w<=n;l++){
      int r=l+w;
      if((r-l)%2==n%2){
        dp[l][r]=max(dp[l+1][r]+a[l],dp[l][r-1]+a[r-1]);
      }else{
        dp[l][r]=min(dp[l+1][r]-a[l],dp[l][r-1]-a[r-1]);
      }
    }
  }

  cout<<dp[0][n]<<endl;

  return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


Measured memory_bytes: 70528
import java.util.*;

public class Main {
	public static void main(String[] arg){
		Scanner in = new Scanner(System.in);
		while(in.hasNext()) {
            String buf = in.nextLine();
            if(buf.equals("0 0")){
            	break;
			}
            String[] num = buf.split(" ");
            if(Integer.parseInt(num[0]) < Integer.parseInt(num[1])){
            	System.out.println(num[0]+" "+num[1]);
            }else{
            	System.out.println(num[1]+" "+num[0]);
            }
        }
	}
}

Measured memory_bytes: 37212
A,B,Q = map(int,input().split())
import bisect
s=[]
t=[]
for _ in range(A):
    s.append(int(input()))
for _ in range(B):
    t.append(int(input()))
s = [-10**20] + s + [10**20]
t = [-10**20] + t + [10**20]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = 10**20
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)


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

using namespace std;
int n,res=0,m,r,MAXX=1e9,d[10],ans=1e9;
long long a[222][222],f[222][222];
int main()
{
   // freopen("in.txt","r",stdin);
    int x,y,c;
   cin>>n>>m>>r;
   for (int i=0;i<r;i++) cin>>d[i];
   sort(d,d+r);
   for (int i=0;i<m;i++) {
        cin>>x>>y>>c;
        f[x-1][y-1]=c;
        f[y-1][x-1]=c;
   }

   for (int i=0;i<n;i++)
   for (int j=0;j<n;j++){
        if (f[i][j])
            a[i][j]=f[i][j];
        else a[i][j]=MAXX;
        //P[i][j]=-1;
   }

   for (int k=0;k<n;k++){
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
        if (a[i][j]>a[i][k]+a[k][j]){
            a[i][j]=a[i][k]+a[k][j];
            //p[i][j]=k;
        }
   }
   do{
        res=0;
        for (int i=1;i<r;i++){
            res+=a[d[i-1]-1][d[i]-1];
        }
        if (res<ans) ans=res;
   }
   while (next_permutation(d,d+r));
   cout<<ans;
    return 0;
}


Measured memory_bytes: 896
from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd,numbers)

N = int(input())
A = list(map(int,input().split()))

res1 = [gcd(A[-1],a) for a in A]

min_res = min(res1)
index = res1.index(min_res)

res1 = [A[i] for i in range(N) if i != index]
res2 = A[:N-1]

res1 = gcd_list(res1)
res2 = gcd_list(res2)

print(max(res1,res2))

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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

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

	int n, m, k; cin >> n >> m >> k;
	REPU(a, 0, n + 1) REPU(b, 0, m + 1) {
		int x = a * m + b * n - 2 * a * b;
		if (x == k) {
			puts("Yes"); return 0;
		}
	}
	puts("No");

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

int main(void)
{
  int N;
  cin >> N;
  
  vector<int> x(N);
  vector<int> y(N);  
  
  for(int i=0;i<N;i++) cin >> x[i] >> y[i];

  double sum=0;
  for(int i=0;i<N-1;i++)
  {
    for(int j=i+1;j<N;j++)
    {
      sum += (double)sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2) );
//      cout <<"i="<< i << ",j=" << j <<",";
//      cout << "sum=" << sum <<endl;
    }
  }
  
  double ret;
  ret = sum/((double)N/2);

  cout << setprecision(20) << ret;
  
  return 0;
}

  

Measured memory_bytes: 256
#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int p[5002];
LLI num[5002][5002],dp[5002];
int x[5002][5002];
int main() {
    int i;
    int N,A,B;
    scanf("%d %d %d",&N,&A,&B);
    for (i = 1; i <= N; i++) scanf("%d",&p[i]);
    p[0] = 0,p[N+1] = N+1,N += 2;

    int j;
    for (i = 0; i < N; i++) {
        int c = 0;
        for (j = i; j < N; j++) {
            if (p[j] < p[i]) c++;
            num[i][j] += (LLI) B*c,x[i][j] += c;
        }
    }
    for (i = 0; i < N; i++) {
        int c = 0;
        for (j = i; j >= 0; j--) {
            if (p[j] > p[i]) c++;
            num[j][i] += (LLI) A*c,x[j][i] += c;
            if (x[j][i] != i-j-1) num[j][i] = 1e18;
        }
    }
    for (i = 0; i < N; i++) {
        dp[i] = num[0][i];
        for (j = 0; j < i; j++) {
            if (p[j] < p[i]) dp[i] = min(dp[i],dp[j]+num[j][i]);
        }
    }
    printf("%lld\n",dp[N-1]);

    return 0;
}



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

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef vector<int> VI;
typedef long long LL;

double distance_p(VI x, VI y, int n, int p)
{
    LL result = 0;
    rep(i, n)
    {
        result += pow(abs(x[i] - y[i]), p);
    }
    return pow(result, 1. / p);
}

double distance_8(VI x, VI y, int n)
{
    LL result = 0;
    rep(i, n)
    {
        result = max(result, (LL)abs(x[i] - y[i]));
    }
    return result;
}

int main()
{
    int n;
    cin >> n;
    VI x(n), y(n);

    rep(i, n)
    {
        cin >> x[i];
    }
    rep(i, n)
    {
        cin >> y[i];
    }

    rep(i, 3)
    {
        printf("%.6f\n", distance_p(x, y, n, i + 1));
    }
    printf("%.6f\n", distance_8(x, y, n));
}



Measured memory_bytes: 3404
#include <bits/stdc++.h>
#include <iostream>
#include <bitset>
using namespace std;
int N, Q;
string S;
int character[500005];
int tree[2000005];

void build(int node, int s, int e){
    if (s == e) tree[node] = (1<<character[s]);
    else {
        int m = (s+e)/2;
        build(2*node, s, m);
        build(2*node+1, m+1, e);
        tree[node] = tree[2*node] | tree[2*node+1];
    }
}

void update(int node, int s, int e, int idx, int val){
    if (s == e) {
        tree[node] = (1<<val);
    }
    else {
        int m = (s+e)/2;
        if (s <= idx && idx <= m) update(2*node, s, m, idx, val);
        else update(2*node+1, m+1, e, idx, val);
        tree[node] = tree[2*node] | tree[2*node+1];
    }
}

int query(int node, int s, int e, int l, int r){
    if (s > r || e < l) return 0;
    if (l <= s && e <= r) return tree[node];
    else {
        int m = (s+e)/2;
        return query(2*node, s, m, l, r) | query(2*node+1, m+1, e, l, r);
    }
}

int main() {
    cin >> N >> S >> Q;
    for (int i=1; i<=N; i++){
        character[i] = S[i-1]-'a';
    }
    build(1, 1, N);
    int a, b;
    for (int i=1; i<=Q; i++){
        scanf("%d %d", &a, &b);
        if (a == 1){
            char c;
            scanf(" %c", &c);
            update(1, 1, N, b, c-'a');
        }
        else {
            int c;
            scanf("%d", &c);
            int ans = query(1, 1, N, b, c);
            printf("%d\n", __builtin_popcount(ans));
        }
    }
    return 0;
}


Measured memory_bytes: 10756
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
A = [int(i) for i in input().split()]
Q = int(input())
BC = [[int(i) for i in input().split()] for _ in range(Q)]

S = sum(A)
C = Counter(A)
for b, c in BC:
    if b in C:
        if c not in C:
            C[c] = 0
        C[c] += C[b]
        S += (c-b)*C[b]
        C[b] = 0
    print(S)

Measured memory_bytes: 100148
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
signed main()
{
   SPEED;
   int a,b,n;
   cin>>a>>b>>n;
   if(n>=b-1)
   {
       cout<<(a*(b-1))/b;
   }
   else
   {
       cout<<(a*n)/b;
   }
}

Measured memory_bytes: 3620
s = input()
def allsum(x):
    ans = int(x)
    if len(x) < 2:
        ans += 0
    else:
        for i in range(1, len(x)):
            ans += int(x[:i])*2**(len(x)-i-1) + allsum(x[i:])
    return ans
print(allsum(s))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<algorithm>
//#define int long long 
#define mod 1000000007
using namespace std;
int cnt =0;
void add(vector<int>adj[],int u,int v){
	adj[u].push_back(v);
	adj[v].push_back(u);
}
void dfs(vector<int>adj[],int s,vector<bool> &vis){
	vis[s] = true;
	for(auto i:adj[s]){
		if(!vis[i]){
			dfs(adj,i,vis);
		}
	}
}
int main(){
//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m,u,v;cin>>n>>m;
vector<int>adj[n];
vector<bool>vis(n);
for(int i =0;i<n;i++) vis[i] = 0;
while(m--){
cin>>u>>v;
u--;v--;
	add(adj,u,v);
}
  for(int i =0;i<n;i++){
        if (!vis[i]) {
            dfs(adj,i, vis); 
            cnt++;
        }
}
cout<<cnt-1<<endl;
}



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

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

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

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        s: [String; n],
    }
    let chars = vec!["M", "A", "R", "C", "H"];
    let mut count = vec![0u64; 5];
    for i in 0..5 {
        for sj in s.iter() {
            if sj.starts_with(chars[i]) {
                count[i] += 1;
            }
        }
    }
    let mut ans = 0;
    for i in 0..5 {
        for j in 0..i {
            for k in 0..j {
                ans += count[i] * count[j] * count[k];
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 8572
#include <math.h>
float x=0,y=0;
main(a,b)
{
  float r = 90 * M_PI / 180.0;
  while(1)
    {
      scanf("%d,%d",&a,&b);
      //printf("%f\n%f\n%f\n",sin(r),cos(r),tan(r));
      if(!a)
	break;
      // printf("r=%d cos(r)=%f sin(r)=%f\n",r,cos(r),sin(r));
      x+=a*cos(r);
      y+=a*sin(r);
      r-=b * M_PI / 180.0;   
      //  printf("x=%f y=%f\n",x,y);
    }
  //  printf("%f\n%f\n",x,y);
  printf("%d\n%d\n",(int)x,(int)y);
  exit(0);

}

Measured memory_bytes: 0
import heapq
N = int(input())
A = list(map(int, input().split()))


# L = heapq.heapify(A[:N])
# R = heapq.heapify(A[2*N:]) この記法ないらしい
# BC125C の累積GCDの直後にやっているので、似たやり方で解いてみる
L = A[:N]
R = [-a for a in A[2*N:]]
L_sum, R_sum = sum(L), sum(R)
heapq.heapify(L)
heapq.heapify(R)

L_acc = [L_sum]
R_acc = [R_sum]
for i in range(N, 2*N):
    if L[0] >= A[i]:
        if i > N:
            L_acc.append(L_acc[-1])
        elif i == N:
            pass
    else:
        heapq.heappush(L, A[i])
        out = heapq.heappop(L)
        L_acc.append(L_acc[-1] - out + A[i])
    #print(L_acc)

for i in range(2*N-1, N-1, -1):
    if R[0] >= -A[i]:
        if i <= 2*N-1:
            R_acc.append(R_acc[-1])
        elif i == 2*N-1:
            pass
    else:
        heapq.heappush(R, -A[i])
        out = heapq.heappop(R)
        R_acc.append(R_acc[-1] - out - A[i])
    #print(R_acc)

ans = -float('inf')
for i in range(len(L_acc)):
     ans = max(ans, L_acc[i]+R_acc[-(i+1)])

print(ans)

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 a;
    string fb;
    cin >> a >> fb;
    i64 b = (fb[0] - '0') * 100 + (fb[2] - '0') * 10 + (fb[3] - '0');
    cout << a * b / 100 << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 3640
#include<iostream>
#include<string>

using namespace std;

int main() {
  int a = 1, b = 2, c = 3;
  string s;
  while (cin >> s) {
    if (s == "A,B") {
      int tmp = a;
      a = b;
      b = tmp;
    } else if (s == "A,C") {
      int tmp = a;
      a = c;
      c = tmp;
    } else if (s == "B,A") {
      int tmp = b;
      b = a;
      a = tmp;
    } else if (s == "B,C") {
      int tmp = b;
      b = c;
      c = tmp;
  } else if (s == "C,A") {
    int tmp = c;
    c = a;
    a = tmp;
} else if (s == "C,B") {
  int tmp = c;
  c = b;
  b = tmp;
}
}
if (a == 1) {
  cout << "A" << endl;
} else if (b == 1) {
  cout << "B" << endl;
} else if (c == 1) {
  cout << "C" << endl;
}
return 0;
}



Measured memory_bytes: 3132
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
//ranker
using namespace std;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using psi = pair<string, int>;
using D = double;


int main(){
  int n, sum=100000;
  int i, j, k;
  int tot, ans, num;

  cin >> n;
  for(i=0; i<n; i++){
    sum *= 1.05;
    if(sum%1000 != 0) sum = (sum/1000+1)*1000;
  }
  cout << sum << endl;
  return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000
#define MOD 1000000007
#define EPS 1e-12

#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())

// bitmask operations
#define SETBIT(S, j) S |= (1 << j)
#define CLEARBIT(S, j) S &= ~(1 << j)
#define ISSET(S, j) S & (1 << j)
#define FLIPBIT(S, j) S ^= (1 << j)
#define LSBIT(S) (S & (-S))

// debug
#define DEBUGSTR(S) cout << "(" << S << ")\n";

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  
  int N, K;
  string s;

  cin >> N >> K >> s;

  s[K-1] = tolower(s[K-1]);

  cout << s << endl;
  
  return 0;
}


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

#define M 2000001
#define V 10000

int main(){
 unsigned short *A,*B;

  int C[V+1];
  int n,i,j;

  scanf("%d",&n);

  A=malloc(sizeof(short)*n+1);
  B=malloc(sizeof(short)*n+1);

  for( i=0; i<=V; i++ ){
    C[i]=0;
  }
  
  for( i=0; i<n; i++ ){
    scanf("%hd",&A[i+1]);
    C[A[i+1]]++;
  }

  for( i=1; i<=V; i++ ){
    C[i]=C[i]+C[i-1];
  }
  
  for( j=1; j<=n; j++ ){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  for( i=1; i<=n; i++ ){
    if(i>1){
      printf(" ");
    }
    printf("%d",B[i]);
  }
  printf("\n");

  return 0;
}
		 



Measured memory_bytes: 9584
#define _CRT_SECURE_NO_WARNINGS

/* include ***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/* define *************************/
//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define FOR(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)
#define RFOR(i,s,n) for(int i=(int)(n)-1,i##_len=(int)(s);i>=i##_len;i--)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTL(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9
#define MOD 2019

typedef long long ll;
typedef unsigned long long ull;

int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};
//今回の変数
int a[200001];
int ans[200001];
int prime[100000] = { 0 };
int idx;

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int  a, int  b) {
	return (a) > (b) ? (a) : (b);
}
ll Minl(ll a, ll b) {
	return (a)<(b) ? (a) : (b);
}
ll Maxl(ll a, ll b) {
	return (a)>(b) ? (a) : (b);
}


int main() {
	int n;
	/*
	n=2e5;
	//REPS(i, n)a[i] = 1;
	a[n] = 1;
	//a[n/2] = 0;
	/*/
	scanf("%d", &n);
	REPS(i, n) {
		scanf("%d", &a[i]);
	}
	//*/
	int m = 0;
	RFOR(i,n/2+1, n+1) {
		if (a[i] != ans[i]) {
			ans[i]++;
			m++;
		}
	}

	RREPS(i, n / 2) {
		int cnt = 0;
		REPS(j, n) {
			if (i*j > n)break;
			cnt += ans[i*j];
		}
		cnt %= 2;
		if (a[i] != cnt) {
			ans[i]++;
			m++;
		}
	}

	PRINTD(m);
	if (m) {
		int f = 0;
		REP(i, n+1) {
			if (ans[i] == 1) {
				if (f)printf("%c", ' ');
				printf("%d", i);
				f = 1;
			}
		}
	}
}


Measured memory_bytes: 2304
#!/usr/bin/env python
# -*- coding:utf-8 -*-
from __future__ import division,print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def walk(index,tm,L,d,f):
    tm+=1
    d[index]=tm
    for i in L[index]:
        if not d[i-1]:
            tm=walk(i-1,tm,L,d,f)
    tm+=1
    f[index]=tm
    return tm
 
def main():
    num=int(sys.stdin.readline())
    L=[]
    for _ in range(num):
        L.append([int(s) for s in sys.stdin.readline().split()[2:]])
    d=[0]*num
    f=[0]*num
    tm=0
    for i in range(num):
        if not d[i]:
            tm=walk(i,tm,L,d,f)
    for i in range(num):
        print(i+1,d[i],f[i])
 
main()

Measured memory_bytes: 6796
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000000000000
#define mod 1000000007

/*

求める数は、    (一つの塊での転倒数)*k + Σ(i:0->n-1){(k*(k-1)/2)*smaller[i]}

Σの項の中の、smaller[i]は,一つの塊(配列a)の中でa[i]より小さい数の個数
			k(k-1)/2*smaller[i]は、上式の第一項以外でa[i]より小さい数の総和
*/

int main(){
	ll n,k;cin>>n>>k;
	vector<ll> a(n),smaller(n,0);
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}

	ll ans=0;
	for(ll i=0;i<n-1;i++){
		for(ll j=i+1;j<n;j++){
			if(a[i]>a[j]){ans++;}
		}
	}

	ans=(ans*k)%mod;//一つの塊で転倒数はans個

	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			if(a[i]>a[j]){smaller[i]++;}//a[i]より小さい数の個数
		}
		ans+=(smaller[i]*((k*(k-1)/2)%mod))%mod;
		ans%=mod;
	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main()
{
    char s[11],cpy[11];
    int i=0,j=0,cnt;;
    scanf("%s",s);
    for(i=0;i<strlen(s);i++){
        if(s[i]=='B'){
            if(i==0||j==0){
                continue;
            }
            j--;
            
        }else{
            cpy[j]=s[i];
            j++;
    }
    }
    for(i=0;i<j;i++){
        printf("%c",cpy[i]);
    }
    return 0;
}


Measured memory_bytes: 128
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())
score = {'r': P, 'p': S, 's': R}
ans = 0

for i in range(K):
    flag = True

    while i < N:
        if i >= K and T[i] == T[i-K]:
            flag = not flag
        else:
            flag = True

        if flag:
            ans += score[T[i]]

        i += K

print(ans)

Measured memory_bytes: 4084
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<cstring>
#include<cstdint>
#include<cstddef>
using namespace std;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using usize = uint_fast64_t;
#define rep(i, n) for (usize i = 0; i < (usize)(n); i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using P = pair<i64,i64>;
usize dp[55][2501][55];
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    i64 n,a;
    cin >> n >> a;
    usize x[n];
    rep(i,n){
        cin >> x[i];
    }
    memset(dp,0,sizeof(dp));
    dp[0][0][0] = 1;
    rep(i,n){
        rep(j,n * a + 1){
            rep(k,n + 1){
               if(dp[i][j][k] == 0)continue;
               dp[i + 1][j][k] += dp[i][j][k];
               dp[i + 1][j + x[i]][k + 1] += dp[i][j][k];
            }
        }
    }
    i64 ans = 0;
    for(i32 i = 1; i <= n; i++){
        ans += dp[n][i * a][i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 62728
#include <iostream>
#include <string>
#define llint long long

using namespace std;

llint N;
llint L;
llint tree[100005][2];

llint dfs(llint v, llint depth)
{
	llint ret = 0;
	for(int i = 0; i < 2; i++){
		if(tree[v][i] == 0) ret ^= (L - depth) & (depth - L);
		else ret ^= dfs(tree[v][i], depth+1);
	}
	return ret;
}

int main(void)
{
	cin >> N >> L;
	
	int next = 2;
	string s;
	for(int i = 0; i < N; i++){
		cin >> s;
		int pos = 1;
		for(int j = 0; j < s.size(); j++){
			if(tree[pos][s[j]-'0'] == 0){
				tree[pos][s[j]-'0'] = next;
				next++;
			}
			pos = tree[pos][s[j]-'0'];
		}
	}
	
	llint grundy = dfs(1, 0);
	
	if(grundy == 0) cout << "Bob" << endl;
	else cout << "Alice" << endl;
	return 0;
}

Measured memory_bytes: 6656
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        
        if(a.equals(b.substring(0,b.length()-1))) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
    }
}

Measured memory_bytes: 27016
import itertools
import math

N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)]

ans = 0
for perm in itertools.permutations([i for i in range(N)]):
    for i in range(N - 1):
        ans += ((P[perm[i]][0] - P[perm[i+1]][0]) ** 2
                + (P[perm[i]][1] - P[perm[i+1]][1]) ** 2) ** 0.5

print(ans / math.factorial(N))


Measured memory_bytes: 3064
#include <stdio.h>

int main()
{
	int a[100], ip, n, i;
	scanf("%d", &ip);

	for (i = 0; i < ip; i++)
	{
		scanf("%d", &n);
		a[i] = n;
	}
	for (int j = 0; j < ip; j++)
	{
		if (j == ip - 1)
		{
			printf("%d", a[ip - j - 1]);
		}
		else
		{
			printf("%d ", a[ip - j - 1]);
		}
	}
	printf("\n");
}


Measured memory_bytes: 2100
import java.util.Scanner;
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 X=sc.nextInt();
        int l=0;
        for(int i=0;i<=A;i++){
            for(int j=0;j<=B;j++){
                for(int k=0;k<=C;k++){
                    if(X==500*i+100*j+50*k){
                        l++;
                    }
                }
            }
            if(i==A){
                System.out.println(l);
            }
        }
        

        


    }
}


Measured memory_bytes: 21716
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();
        long[] aSum = new long[n+1];
        long[] bSum = new long[m+1];

        aSum[0] = 0;
        bSum[0] = 0;
        for (int i = 1; i <= n;++i) aSum[i] = aSum[i-1] + sc.nextLong();
        for (int i = 1; i <= m;++i) bSum[i] = bSum[i-1] + sc.nextLong();

        int maxBooks = 0;
        int bBestInd = bSum.length-1;
        for (int i = 0;i<=n;++i)
        {
            long remaining = k - aSum[i];
            //System.err.println(i+":"+remaining+"(bBestInd = "+bBestInd+")");
            if (remaining < 0) break;
            int books = i;

            for (int j = bBestInd;j >= 0;--j)
            {
                if (remaining-bSum[bBestInd] >= 0)
                {
                    bBestInd = j;
                    books += j;
                    //System.err.println(i+":"+j+"(time = "+(remaining+aSum[i])+")");
                    break;
                }else
                {
                    --bBestInd;
                }
            }

            if (maxBooks < books) maxBooks = books;
        }
        //System.err.println(sumTime);
        System.out.println(maxBooks);
        sc.close();
    }
}

Measured memory_bytes: 64128
loop do
	tmp = gets.split(" ")
	break if tmp[1] == "?"
	ans = tmp[0].to_i + tmp[2].to_i if tmp[1] == "+"
	ans = tmp[0].to_i - tmp[2].to_i if tmp[1] == "-"
	ans = tmp[0].to_i * tmp[2].to_i if tmp[1] == "*"
	ans = tmp[0].to_i / tmp[2].to_i if tmp[1] == "/"
	puts ans
end

Measured memory_bytes: 8632
#include<iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;

ll L, R;
ll memo[60][2][2][2];

ll dfs(int pos, int flagX, int flagY, int flagZ) {
    if (pos == -1) return 1;
    if (memo[pos][flagX][flagY][flagZ] != -1) {
        return memo[pos][flagX][flagY][flagZ];
    }
    ll ret = 0;
    if (flagX || ((L >> pos) & 1) == 0) {
        ret = (ret + dfs(pos - 1, flagX, (((R >> pos) & 1) == 1 ? 1 : flagY), flagZ)) % MOD;
    }
    if ((flagX || ((L >> pos) & 1) == 0) && (flagY || ((R >> pos) & 1) == 1) && flagZ) {
        ret = (ret + dfs(pos - 1, flagX, flagY, flagZ)) % MOD;
    }
    if (flagY || ((R >> pos) & 1) == 1) {
        ret = (ret + dfs(pos - 1, (((L >> pos) & 1) == 0 ? 1 : flagX), flagY, 1)) % MOD;
    }
    return memo[pos][flagX][flagY][flagZ] = ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> L >> R;
    for (int i = 0; i < 60; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 2; ++l) {
                    memo[i][j][k][l] = -1;
                }
            }
        }
    }
    cout << dfs(59, 0, 0, 0) << endl;
    return 0;
}

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

int main()
{
    int n,i,lleg=0,rleg=0,bef=-1,ans=0;
    
    while(1)
    {
        //input
        cin>>n;
        if(n==0)
        {
            break;
        }
      
        string f[n]={};
        for(i=0;i<n;i++)
        {
            cin>>f[i];
        }

        for(i=0;i<n;i++)
        {
            if(f[i].compare("lu")==0)
            {
                lleg=1;
            }
            else if(f[i].compare("ru")==0)
            {
                rleg=1;
            }
            else if(f[i].compare("ld")==0)
            {
                lleg=-1;
            }
            else if(f[i].compare("rd")==0)
            {
                rleg=-1;
            }

            if(lleg==rleg&&lleg==1&&bef==-1)
            {
                ans++;
                bef=1;
            }
            else if(lleg==rleg&&lleg==-1&&bef==1)
            {
                ans++;
                bef=-1;
            }
        }
        cout<<ans<<endl;
      	lleg=0,rleg=0,bef=-1,ans=0;
    }
}


Measured memory_bytes: 3152
import sys


read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N, M = map(int, readline().split())
    M_div = divisors(M)
    for div in M_div:
        if div>=N:
            print(M//div)
            break




if __name__ == '__main__':
    main()


Measured memory_bytes: 9200
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  ll n ; cin >> n;
  ll ans = INF;
  for(ll i=1;i<=sqrtl(n);i++){
    if(n%i!=0) continue;
    ans = min(ans,(i-1)+(n/i-1));
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] data = br.readLine().split(" ");
    int a = Integer.parseInt(data[0]);
    int p = Integer.parseInt(data[1]);
    
    p += a*3;
    
    System.out.println(p/2);
  }
}

Measured memory_bytes: 21076
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	
	//最大値は1000000
	public static final int MAX_NUMBER = 1000000;
	
	public static void main(String[] args) {
		dirichlet();
		//fortune();
		
	}
	

	
	public static void dirichlet(){
		
		Scanner sc = new Scanner(System.in);
		
		boolean isNotPrime[] = new boolean[MAX_NUMBER];
		//System.out.println("aaa");
		//エラトステネスの古いにかける
		isNotPrime[0] = true;
		isNotPrime[1] = true;
		isNotPrime[2] = false;
		int n1 = 0;
		for(int i = 2; i < MAX_NUMBER; i++){
			if(isNotPrime[i] == false){
				for(int j = 2; j < MAX_NUMBER / i; j++){
					isNotPrime[i * j] = true;
				}
			}
			
			if(MAX_NUMBER < i * i){
				break;
			}
			
		}
		
		/*isNotPrime[0] = false;
		isNotPrime[1] = false;
		isNotPrime[2] = true;
		int n1 = 0;
		for(int i = 3; i < MAX_NUMBER; i += 2){
			isNotPrime[i] = true;
			for(int j = 2; j <= i/2; j++){
				if(i % j == 0){
					isNotPrime[i] = false;
					n1++;
					System.out.println(n1 + " " + i);
					break;
				}
			}
		}*/
		//System.out.println("END!!");
		//Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int d = sc.nextInt();
		int n = sc.nextInt();
		while(a != 0 || d != 0 || n != 0){
			int sum = 0;
			int num = 0;
			sum = a;
			while(num < n){
				if(isNotPrime[sum] == false){
					num++;
				}
				sum += d;
			}
			System.out.println(sum - d);
			a = sc.nextInt();
			d = sc.nextInt();
			n = sc.nextInt();
		}
		
	}

}

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



int main(){
	int K, X; cin >> K >> X;
	if(500*K >= X) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 384
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

/*
* welcome to my code!
* ------------------------------
* author : lynmisakura(twitter : @andoreiji11)
*/

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

using ll = long long;

// macro templates

#define rep(i,n) for(int i = 0;i < n;i++)
#define dv(TYPE,VAL) TYPE VAL;cin >> VAL;
#define vi(TYPE,NAME,SIZE,INIT) vector<TYPE> NAME(SIZE,(INIT))
#define vin(TYPE,NAME,SIZE) vector<TYPE> NAME(SIZE);rep(i,SIZE)cin >> NAME[i]
#define vout(ARRAY) for(auto i : ARRAY)cout << i << ' ';cout << '\n'
#define vvi(TYPE,NAME,LOW,COL,INIT) vector<vector<TYPE>> NAME(LOW,vector<TYPE>(COL,INIT))
#define vpi(T1,T2,NAME,SIZE,I1,I2) vector<pair<T1,T2>> NAME(SIZE,make_pair(I1,I2))
#define all(x) x.begin(),x.end()

#define PY(COND) if(COND){cout << "YES" << '\n';return;}
#define PN(COND) if(COND){cout << "NO" << '\n';return;}
#define PYN(CONT) if(CONT)
#define Py(COND) if(COND){cout << "Yes" << '\n';return;}
#define Pn(COND) if(COND){cout << "No" << '\n';return;}

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pi acos(-1)
#define fi first
#define se second

#define MULTITEST; int t;cin >> t;rep(_,t)main2(cin,cout);
#define IOB; cin.tie(0);ios::sync_with_stdio(false);

template<class T> bool chmin(T& a,T b){if(a>b){a=b;return 1;}else return false;}
template<class T> bool chmax(T& a,T b){if(a<b){a=b;return 1;}else return false;}

// templates end

class BMultiplication2 {
public:
	void solve(std::istream& cin, std::ostream& cout) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        //int t;cin >> t;rep(i,t)main2(cin,cout);
        dv(int64_t ,n);
        vin(int64_t ,a,n);
        sort(all(a));

        ll m = 1e18;
        ll tmp = 1;

        rep(i,n){
            if(a[i] == 0){
                cout << 0 << '\n';
                return;
            }else if(tmp > (m / a[i])){
                cout << -1 << '\n';
                return;
            }else tmp *= a[i];
        }
        cout << tmp << '\n';
	}
	void main2(istream& cin,ostream& cout){

	}
};


int main() {
	BMultiplication2 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    string ans = "No";

    int cnt = 0;
    while(b <= a) {
        b *= 2;
        cnt++;
    }
    while(c <= b) {
        c *= 2;
        cnt++;
    }
    if (cnt <= k) {
        ans = "Yes";
    }
    cout << ans << endl;
}


Measured memory_bytes: 3592
#include<iostream>
using namespace std;
int main(){
  int n,i,count;
    cin >> n;
  int a[n];
  count = 0;
  for(i = 0;i < n;i ++){
    cin >> a[i];
    while(a[i] % 2 == 0){
      a[i] /= 2;
      count++;
    }
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define PI 3.1415926535897932384626433832795
using namespace std;

int main(){
    double a,b;
    cin>>a>>b;
    double x,y,z,w;
    x=12.5 *a;
    y=12.5 *(a+1);
    z=10 *b;
    w=10 *(b+1);

    int ans = 0;
    ans=x;
    if((int)a%2==0){
        ans = ans;
    }
    else{
        ans=ans+1;
    }
    if(x < z && y<=z){
        cout<< -1;
    }
    else if(z<x && w<=x){
        cout<< -1;
    }
    else if(x < z){
        cout<<z;
    }
    else if(x==z){
        cout<<z;
    }
    else if(ans<w){
        cout<<ans;
    }
    else if(ans>=w){
        cout<<-1;
    }
   


    return 0;
}



Measured memory_bytes: 256
H, W = [int(i) for i in input().split()]
SS = [input() for _ in range(H)]

def s(y, x):
  if x >= W or x < 0 or y >= H or y < 0:
    return 0

  return 1 if SS[y][x] == '#' else 0

for i in range(H):
  S = SS[i]
  l = []
  for j in range(W):
    c = S[j]
    if c == '.':
      l.append(str(sum([s(i-1, j-1), s(i-1, j), s(i-1, j+1), s(i, j-1), s(i, j+1), s(i+1, j-1), s(i+1, j), s(i+1, j+1)])))
    else:
      l.append('#')
  print(''.join(l))


Measured memory_bytes: 9232