akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

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

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int a,b,c,d,e,f;
	cin >>a>>b>>c>>d>>e>>f;


	double con = 0.0;
	int water = 0,sugar = 0;
	for(int w = 0; w <=30; w++){
		for(int x = 0; x <= 30; x++){
			for(int y = 0; y <= ceil((double)f/c); y++){
				for(int z = 0; z <= ceil((double)f/d); z++){
					int water_weight = a*w+b*x, sugar_weight = c*y+d*z;
					int total = 100*water_weight + sugar_weight;
					if(total <= f && sugar_weight <= water_weight*e){
						if(con < (double)sugar_weight/total){
							con = (double)sugar_weight/total;
							water = 100*water_weight;
							sugar = sugar_weight;
						}
					}
				}
			}
		}
	}
 	if(con == 0) water = 100*a;

	cout << water+sugar << " " << sugar << endl;

	return 0;
}


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

void roll(char ch, int d[]) {
    int tmp;
    if(ch == 'S'){
        tmp = d[0];
        d[0] = d[4];
        d[4] = d[5];
        d[5] = d[1];
        d[1] = tmp;
    }
    else if(ch == 'W'){
        tmp = d[0];
        d[0] = d[2];
        d[2] = d[5];
        d[5] = d[3];
        d[3] = tmp;
    }
    else if(ch == 'E'){
        tmp = d[0];
        d[0] = d[3];
        d[3] = d[5];
        d[5] = d[2];
        d[2] = tmp;
    }
    else if(ch == 'N'){
        tmp = d[0];
        d[0] = d[1];
        d[1] = d[5];
        d[5] = d[4];
        d[4] = tmp;
    }
    else if(ch == 'L'){
        tmp = d[1];
        d[1] = d[3];
        d[3] = d[4];
        d[4] = d[2];
        d[2] = tmp;
    }
    else{
        tmp = d[1];
        d[1] = d[2];
        d[2] = d[4];
        d[4] = d[3];
        d[3] = tmp;
    }
}

int Count(int d[]){
    int cnt = 0, i, j;
    for (i = 0; i < 5; i++) {
        for (j = i + 1; j < 6; j++)
            if (d[i] == d[j]) ++cnt;
    }
    return cnt;
}

string isIdentical(int d1[], int d2[]){
    string ans = "No";
    if (Count(d1) >= 10)
        cout << "Yes" << endl;
    if (d1[0] == d2[0]);
    else if (d1[1] == d2[0]) roll('N', d1);
    else if (d1[2] == d2[0]) roll('W', d1);
    else if (d1[3] == d2[0]) roll('E', d1);
    else if (d1[4] == d2[0]) roll('S', d1);
    else if (d1[5] == d2[0]){
        roll('N', d1);
        roll('N', d1);
    }
    
    if (d1[1] == d2[1]);
    else if (d1[2] == d2[1]) roll('R', d1);
    else if (d1[3] == d2[1]) roll('L', d1);
    else if (d1[4] == d2[1]){
        roll('L', d1);
        roll('L', d1);
    }
    
    for (int i = 3; i < 6; i++) {
        if (d1[i] != d2[i]) break;
        if (i==5) ans = "Yes";
    }
    return ans;
}

int main() {
    int d1[6], d2[6];
    for (int i = 0; i < 6; i++) cin >> d1[i];
    for (int i = 0; i < 6; i++) cin >> d2[i];
    
    string ans = "No";
    if (Count(d1) >= 10) ans = "Yes";
    else ans = isIdentical(d1,d2);
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 3204
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) memset(arg,n,sizeof(arg))
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,pi> plpi;
typedef vector<int> vi;
typedef set<int> si;
typedef string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
int N,M;
int u[100010],v[100010];
int S,T;
vi g[100010];
ll d[100010][3];
void add_edge(int from,int to){
  g[from].push_back(to);
}
void rec(int i,int j,ll m){
  if(d[i][j]<=m) return ;
  d[i][j]=m;
  rep(k,g[i].size()){
    int t=g[i][k];
    rec(t,(j+1)%3,m+1);
  }
}
void dijkstra(int s){
  priority_queue<plpi,vector<plpi>,greater<plpi> > q;//pair(コスト、頂点)としてコストの小さい順に並ぶ
  d[s][0]=0;
  q.push(mp(0,mp(s,0)));
  while(!q.empty()){
    plpi p = q.top();q.pop();
    pi w=p.second;//最新の確定した頂点
    int x=w.first,y=w.second;
    if(d[x][y]<p.first) continue;//取り出した頂点のコストが最短コストより長かったら破棄
    for(int i=0;i<g[x].size();i++){//取り出した頂点と隣接した頂点を調べる
      int t=g[x][i];
      if(d[t][(y+1)%3]>d[x][y]+1){//頂点tまでの暫定最短距離よりwまでの最短距離+w→tのコストが小さければ更新
	d[t][(y+1)%3]=d[x][y]+1;
	q.push(mp(d[t][(y+1)%3],mp(t,(y+1)%3)));
      }
     }
  }
}



int main(){
  cin>>N>>M;
  rep(i,M){
    cin>>u[i]>>v[i];
    u[i]--;v[i]--;
  }
  cin>>S>>T;
  S--;T--;
  rep(i,M) add_edge(u[i],v[i]);
  rep(i,N){
    rep(j,3){
      d[i][j]=INFLL;
    }
  }
  dijkstra(S);
  prin((d[T][0]!=INFLL?d[T][0]/3:-1));
  return 0;
}


Measured memory_bytes: 8960
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
 
using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;

int main(void) {
    Int d;
    cin >> d;
    cout << "Christmas";
    for (Int i = 24; i >= d; --i) {
        cout << " Eve";
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3568
fn walk_on_multiplication_table() -> Result<u64, &'static str> {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input)
        .map_err(|_| "input error")?;
    let n = input.trim_right().parse::<f64>()
        .map_err(|_| "parse error")?;

    let m = n.sqrt().ceil() as u64;
    let n = n as u64;
    let mut sum = n;

    for a in 1..(m + 1) {
        let s = n / a;
        if s * a != n {
            continue;
        }
        if s + a - 2 < sum {
            sum = s + a - 2;
        }
    }
    Ok(sum)
}

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

Measured memory_bytes: 4352
import math as mt
from collections import defaultdict
  
MAXN = 10**6
  
spf = [0 for i in range(MAXN)] 
  
def sieve(): 
    spf[1] = 1
    for i in range(2, MAXN): 
        spf[i] = i 
    for i in range(4, MAXN, 2): 
        spf[i] = 2
  
    for i in range(3, mt.ceil(mt.sqrt(MAXN))): 
        if (spf[i] == i): 
            for j in range(i * i, MAXN, i):  
                if (spf[j] == j): 
                    spf[j] = i 
  
# A O(log n) function returning prime  
# factorization by dividing by smallest  
# prime factor at every step 
def getFactorization(x): 
    d = defaultdict(int)
    while (x != 1): 
        #ret.append(spf[x])
        d[spf[x]] += 1 
        x = x // spf[x] 
    #return Counter(ret)
    ans = 1
    for i in d:
        ans *= (d[i]+1)
    return ans
sieve()

n = int(input())
ans = 0
for i in range(1, n):
    ans += getFactorization(i)
print(ans)

Measured memory_bytes: 48816
n,m,s = map(int, input().split())
uvab=[list(map(int,input().split())) for i in range(m)]
cd=[list(map(int,input().split())) for i in range(n)]
chg=10**5

from collections import defaultdict
link = defaultdict(list)
for node in range(n):
    cmai,dmin = cd[node]

    for frm in range(2600):
        link[node*chg + frm].append([node*chg + frm+cmai, dmin])

for i in range(m):
    u,v,a,b = uvab[i]
    u-=1
    v-=1
    for sil in range(2600):
        link[u*chg + sil+a].append([v*chg + sil,b])
        link[v*chg + sil+a].append([u*chg + sil,b])

from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
def dks(g,start):
    INF=float('inf')
    visited = set()
    hq = []
    heappush(hq, (0,start))

    cost = defaultdict(lambda: float("inf"))
    while hq:
        shortest, i = heappop(hq)
        if i in visited:
            continue
        visited.add(i)
        cost[i] = shortest
        for j, t in g[i]:
            if j in visited:
                continue
            heappush(hq, (shortest + t, j))
    return cost

f_sil = min(s,2555)
res=dks(link,f_sil)

for node in range(1,n):
    ans=float("inf")
    for sil in range(2600):
        ans=min(ans,res[node*chg + sil])
    print(ans)


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

#define N 100005

int L[N], R[N], C[N];

int n, m;

using ll = long long;
ll a[N];

vector <int> v[N];

const ll inf = 0x3f3f3f3f3f3f3f3f;

void give(int k, ll v) {
    k = n + 1 -  k;
    a[k] = v;
}
ll calc(int k) {
	k = n + 1 - k;
    ll res = inf;
    for ( ; k; k -= k & -k) res = min(res, a[k]);
    return res;
}
void update(int k, ll val) {
	k = n + 1 - k;
	for ( ; k <= n; k += k & -k) a[k] = min(a[k], val);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i ++) scanf("%d %d %d", &L[i], &R[i], &C[i]), v[L[i]].push_back(i);
    for (int i = 1; i <= n; i ++) give(i, inf);
    give(1, 0);
    for (int i = 1; i <= n; i ++) {
        ll val = calc(i);
        for (auto x : v[i]) {
            int r = R[x], c = C[x];
            update(r, val + c);
        }
    }
    ll ans = calc(n);
    if (ans == inf) ans = -1;
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 10984
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
#define vcin(a)                          \
    for (int i = 0; i < (a).size(); i++) \
        cin >> (a)[i];

ll factorial(ll n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main()
{
    int K, S;
    cin >> K >> S;
    ll ans = 0;
    rep2(x, 0, K + 1)
    {
        rep2(y, 0, K + 1)
        {
            int z = S - (x + y);
            if (z <= K and z >= 0)
                ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
int main(){
    int A,B,C,K;
    cin >> A >> B >> C >> K;
    int tmp = max({A,B,C});
    int ans = A+B+C-tmp;
    for(int i=0; i<K; i++){
        tmp *= 2;
    }
    cout << ans + tmp << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 200010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
struct edge{
	int to,nxt;
}e[4*maxn];
int fir[4*maxn],in[4*maxn];
int q[4*maxn];
char s[maxn];
int n,m,tot;
inline void add_edge(int x,int y){++in[y]; e[tot].to=y; e[tot].nxt=fir[x]; fir[x]=tot++;}
int main()
{
	n=read(); m=read();
	scanf("%s",s+1);
	memset(fir,255,sizeof(fir));
	memset(in,0,sizeof(in));
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		if(s[x]=='A'&&s[y]=='A')add_edge(x+3*n,y),add_edge(y+3*n,x);
		else if(s[x]=='B'&&s[y]=='B')add_edge(x+n,y+2*n),add_edge(y+n,x+2*n);
		else add_edge(x,y+n),add_edge(y,x+n),add_edge(x+2*n,y+3*n),add_edge(y+2*n,x+3*n);
	}
	int h=1,t=0;
	for(int i=1;i<=4*n;i++)
		if(!in[i])q[++t]=i;
	while(h<=t){
		int now=q[h++];
		for(int i=fir[now];~i;i=e[i].nxt){
			--in[e[i].to];
			if(!in[e[i].to])q[++t]=e[i].to;
		}
	}
	if(t==4*n)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 14464
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"
 
using namespace std;

int main() {
  int N, L; cin >> N >> L;
  vector<string> S(N);
  for (auto &i : S) cin >> i;
  
  sort(S.begin(), S.end());
  cout << accumulate(S.begin(), S.end(), string()) << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

A = list(input())
N = len(A)
D = defaultdict(int)

for i in A:
    D[i] += 1

ans = 1 + int(N * (N - 1) / 2)

for i in D:
    ans -= int(D[i] * (D[i] - 1) / 2)

print(ans)

Measured memory_bytes: 5220
import itertools
N, Q = map(int, input().split())
S = input()
LR = [[int(x) for x in input().split()] for _ in range(Q)]

reg = [0]*N
for i in range(N-1):
#     print(S[i:i+2])
    if S[i:i+2]=='AC':
        reg[i] += 1
        
regcum = [0] + list(itertools.accumulate(reg))

for l, r in LR:
    print(regcum[r-1] - regcum[l-1])

Measured memory_bytes: 26928
#include <stdio.h>
    int main()
    {
    	char a[4], s = '\0', k = '\0';
    	gets(a);
    	s = a[0];
    	for (int i = 1; i < 4; i++)
    	{
    		if (a[i] != s && k == '\0')
    			k = a[i];
    		else if (a[i] != s && a[i] != k)
    		{
    			printf("No");
    			return 0;
    		}
     
    	}
    	if (k == '\0')
    	{
    		printf("No");
    	}
     
    	else
    	{
    		printf("Yes");
    	}
     
    }

Measured memory_bytes: 128
#include <cstdio>
#include <iostream>

int main() {
  int N, P[200000];
  
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &P[i]);
  }
  int min = N;
  int count = 0;
  for (int i = 0; i < N; i++) {
    if (P[i] <= min) {
      count++;
      min = P[i];
    }
  }
  printf("%d", count);
  return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define per(i,n) for(int i = (n)-1; i >= 0; --i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

int main() {
    string s, t; cin >> s >> t;
    if (s == t.substr(0,s.length())) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n,k;
    cin >> n >> k;
    cout << n-k+1 << endl;
    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,w;
    cin>>n>>w;
    int a[103],b[103];
    int dp[2][100004];
    for(int i=0;i<n;i++)cin>>a[i]>>b[i];
    for(int i=0;i<2;i++)for(int j=0;j<100004;j++)dp[i][j]=mod;
    dp[0][0]=0;
    for(int i=0;i<n;i++)for(int j=0;j<100004;j++){
        if(j>=b[i])dp[(i+1)&1][j]=min(dp[i&1][j],dp[i&1][j-b[i]]+a[i]);
        else dp[(i+1)&1][j]=dp[i&1][j];
    }
    
    int res=0;
    for(int j=0;j<100004;j++)if(dp[n&1][j]<=w)res=j;
    cout<<res<<endl;
    
    return 0;
}


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

int main() {
    int i = 0, x;
    while (true) {
        cin >> x;
        if (x == 0) break;
        printf("Case %d: %d\n", ++i, x);
    }
    
/**
    int W, H, x, y, r;
    scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

    if (x + r > W || y + r > H) {
        printf("No");
    } else if (x - r < 0 || y - r < 0) {
        printf("No");
    } else {
        printf("Yes");
    }
    printf("\n");

    return 0;
    **/
}

Measured memory_bytes: 1144
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = ['']*N

    for i in range(N):
        B[A[i]-1] = str(i + 1)
    
    print(' '.join(B))


if __name__ == '__main__':
    main()

Measured memory_bytes: 15524
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int H,W;
int main(){
    cin >> H >> W;
    char s[H+1][W+1];
    rep1(i,H) rep1(j,W) cin >> s[i][j];
    bool flag = true;
    
    rep1(i,H) rep1(j,W){
        bool check = s[i][j] == '#';
        rep(k,4) check = check && s[i+dx[k]][j+dy[k]] != '#'; 
        if(check) flag = false;
    } 
    if(flag) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val s = (1..n).map { sc.nextInt() }
    val dp = Array(10002) {false}
    dp[0] = true

    for (i in 0 until n) {
        for (j in 10000 downTo 0) {
            if (!dp[j]) {
                continue
            }
            dp[j + s[i]] = true
        }
    }

    for (i in 10000 downTo 0) {
        if (dp[i] && i % 10 != 0) {
            println(i)
            return
        }
    }
    println(0)
}

Measured memory_bytes: 31648
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    n, s = MI()
    aa = LI()
    dp = [0] * (s + 1)
    ans = 0
    for a in aa:
        dp[0] += 1
        for i in range(s, a - 1, -1):
            dp[i] += dp[i - a]
            dp[i] %= md
        ans += dp[s]
        ans %= md
    print(ans)

main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 3e5+5;
const ll mod =   1e9+7;

int main()
{  fast
int x;
cin>>x;
int arr[8]={599,799,999,1199,1399,1599,1799,1999};
int y=0;
while(arr[y]<x)y++;
cout<<(8-y)<<endl;
}


Measured memory_bytes: 3656
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define rep(i,a,n) for(int i=(a);i<(n);i++)
using namespace std;

int main() {
	string s;
	int n;
	cin >> n;
	cin >> s;
	vector<int> e(n,0),w(n,0);
	rep(i, 1, n) {
		if (s[i-1] == 'E')e[i]++;
		e[i] += e[i - 1];
	}
	for (int i = n - 2; i >= 0; i--) {
		if (s[i+1] == 'W')w[i]++;
		w[i] += w[i+1];
	}
	int ans = 300001;
	rep(i, 0, n) {
		ans = min(ans, n - w[i] - e[i]-1);
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvd = vector<vd>;
using vvvi = vector<vvi>;
using vvvll = vector<vvll>;
using vvvd = vector<vvd>;

const double pi=3.141592653589793;
const ll MOD=1e9+7;

vector< int64_t > divisor(int64_t n) {
    vector< int64_t > ret;
    for(int64_t i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
sort(begin(ret), end(ret));
return (ret);
}

int main() {
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    map<int,int> ddd;
    for (int i=1;i<k+1;i++){
        ddd[i]=1;
    }
    for (int i=k;i>=1;i--){
        ll num=k/i;
        vll bi2;
        //num^nをしたい
        bitset<23> s(n);
        bi2.push_back(num);
        rep(j,23){
            bi2.push_back((bi2[j]*bi2[j])%MOD);
        }
        ll ans1=1;
        rep(j,23){
            if (s.test(j)){
                ans1*=bi2[j];
                ans1%=MOD;
            }
        }

        for (int j=2;j*i<k+1;j++){
            ans1-=ddd[j*i];
            ans1=(ans1+MOD)%MOD;
        }


        ans+=i*ans1;
        ans%=MOD;

        ddd[i]=ans1;

        /*auto d=divisor(i);
        for (auto x:d){
            if (x==i){
                continue;
            }
            else{
                ll ans2=1;
                ans2=x*ans1;
                if (ddd[x])
                ans+=ddd[x]*ans2;
                ddd[x]*=-1;
                ans=(ans%MOD)%MOD;
            }
        }*/



    }
    cout<<ans<<endl;


    return 0;
}

Measured memory_bytes: 8244
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;
#define FIX cout << fixed << setprecision(15)

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

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

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN(n);
  Vi A(n);
  VIN(A)
  bool flg = true;
  REP(i,n){
    if(A[i]%2==0){
      if(A[i]%3!=0 && A[i]%5!=0){
        flg = false;
      }
    }
  }
  if(flg){
    OUT("APPROVED");
  } else {
    OUT("DENIED");
  }
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <iomanip>
#include <random>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using std::cin;
using std::cerr;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
using std::stack;
using std::string;
using std::unordered_map;
using std::unordered_set;
using std::vector;
using std::lower_bound;
using std::upper_bound;

int main(int argc, char* argv[]) {
  string s;
  cin >> s;
  int q;
  cin >> q;
  bool rev = false;
  string before;
  string after;
  for (int i = 0; i < q; ++i) {
    int op;
    cin >> op;
    if (op == 1) {
      rev = !rev;
    } else {
      int f;
      char c;
      cin >> f >> c;
      if ((f == 1 && !rev) || (f == 2 && rev)) {
        before.append(1, c);
      } else {
        after.append(1, c);
      }
    }
  }
  if (rev) {
    std::reverse(after.begin(), after.end());
    std::reverse(s.begin(), s.end());
    cout << after << s << before;
  } else {
    std::reverse(before.begin(), before.end());
    cout << before << s << after;
  }
  return 0;
}


Measured memory_bytes: 1088
#include<iostream>
#include<atcoder/all>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int main(){
  int n,q; cin >>n >>q;
  atcoder::fenwick_tree<li> bit(n);
  rep(i,n){
    li a; cin >>a;
    bit.add(i,a);
  }
  rep(_,q){
    li t,p,x; cin >>t >>p >>x;
    if(t==0) bit.add(p,x);
    else{
      print(bit.sum(p,x));
    }
  }
}


Measured memory_bytes: 8212
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define PB(a,n) FOR(i,0,n){ll buf; scanf("%lld",&buf); a.pb(buf); }
#define LOWER(a,x) lower_bound(ALL(a), x) - a.begin() - 1;
#define COUNT(a,x)  upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
#define MCOUNT(a,x,y) upper_bound(ALL(a), y) - lower_bound(ALL(a), x);
#define INF 111111111111111111
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool flag, ok;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[8] = { 1,-1,0,0,1,1,-1,-1 }, ddy[8] = { 0,0,1,-1,1,-1,1,-1 };
#pragma endregion
#define MAX 111111


#define NOT 0
#define VIS 1
#define COMP 2

map<pll, ll> mp;
ll stt[MAX];
ll mini[MAX];
vector<pll> edge[MAX];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void dijkstra(ll start) {
  pll mi;
  ll k;
  FOR(i, 1, n + 1) {
	stt[i] = NOT;
	mini[i] = INF;
  }
  mini[start] = 0;
  pq.push(make_pair(0, start));

  while (!pq.empty()) {
	mi = pq.top();
	pq.pop();
	m = mi.second;
	stt[m] = COMP;

	if (mini[m] < mi.first) continue;

	FOR(i, 0, edge[m].size()) {
	  k = edge[m][i].first;
	  if (stt[k] != COMP) {
		if (edge[m][i].second + mini[m] < mini[k]) {
		  mini[k] = edge[m][i].second + mini[m];
		  stt[k] = VIS;
		  pq.push(make_pair(mini[k], k));
		}
	  }
	}
  }
}


int main(void) {
  ll a, b, c;
  cin >> n >> m;

  FOR(i, 0, m) {
	cin >> a >> b >> c;
	edge[a].push_back(make_pair(b, c));
	edge[b].push_back(make_pair(a, c));
	mp[pll(a, b)]++;
	mp[pll(b, a)]++;
  }

  FOR(i, 1, n + 1) {
	dijkstra(i);
	FOR(j, 0, edge[i].size()) {
	  if (mini[i] + edge[i][j].S == mini[edge[i][j].F]) {
		mp[pll(i, edge[i][j].F)] = 0;
		mp[pll(edge[i][j].F, i)] = 0;
	  }
	}
  }

  for (auto it : mp) {
	if (it.second) ans++;
  }
  cout << ans / 2 << endl;

  return 0;
}

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

const int N = 2e5 + 10 ;

int main() {
    char a , ch , b ;
    scanf("%c%c%c" , &a , &ch , &b ) ;
    if( a > b ) cout << ">" << endl ;
    else if( a < b ) cout << "<" << endl ;
    else cout << "=" << endl ;
    return 0 ;
}


Measured memory_bytes: 256
function Main(input) {
    input = input.split("\n");
    var a = parseInt(input[0]);
    var s = input[1];
    if(a >= 3200){
        console.log( s );
    }else {
        console.log('red');
    }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <iostream>

using namespace std;

int n, a, b[101], m[4][4];
bool mf[4][4];

bool rezolva () {
  if (mf[1][1] and mf[1][2] and mf[1][3])
    return true;
  if (mf[2][1] and mf[2][2] and mf[2][3])
    return true;
  if (mf[3][1] and mf[3][2] and mf[3][3])
    return true;
  if (mf[1][1] and mf[2][1] and mf[3][1])
    return true;
  if (mf[1][2] and mf[2][2] and mf[3][2])
    return true;
  if (mf[1][3] and mf[2][3] and mf[3][3])
    return true;
  if (mf[1][1] and mf[2][2] and mf[3][3])
    return true;
  if (mf[1][3] and mf[2][2] and mf[3][1])
    return true;
  return false;
}

int main()
{
  for (int l = 1; l <= 3; l++)
    for (int c = 1; c <= 3; c++)
      cin >> m[l][c];
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a;
    b[a]++;
  }
  for (int l = 1; l <= 3; l++)
    for (int c = 1; c <= 3; c++)
      if (b[m[l][c]] > 0)
        mf[l][c] = true;
  if (rezolva ())
    cout << "Yes";
  else
    cout << "No";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int f(int x) {
    int div = 0;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            div++;
            if (i != x / i) div++;
        }
    }
    return div;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i += 2) {
        if (f(i) == 8) cnt++;
    }
    cout << cnt << endl;
}

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

typedef long long ll;

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

    ll N, K;
    cin >> N >> K;
    vector<ll> x(N);
    for (int i = 0; i < N; i++){
        cin >> x[i];
    }

    ll res = 0;

    for (int i = 0; i < N; i++){
        if(x[i] <= K / 2){
            res += x[i] * 2;
        }else{
            res += (K - x[i]) * 2;
        }
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>

#define INF 10000000100
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<long long(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

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

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

#define int long long

const int MAX_V = 600010;

struct edge{int to,cost;};
typedef pair<int,int> P;

int V;
vector<edge>G[MAX_V];
int d[MAX_V];

void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P> > que;
  fill(d,d+V,LINF);
  d[s]=0;
  que.push(P(0,s));

  while(!que.empty()){
    P p=que.top();que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;
    for(int i=0;i<(int)G[v].size();i++){
      edge e=G[v][i];
      if(d[e.to]>d[v]+e.cost){
	d[e.to]=d[v]+e.cost;
	que.push(P(d[e.to],e.to));
      }
    }
  }
}

signed main(){
  int n,m,s,t;
  int a,b,c,D;
  cin>>n>>m>>s>>t;
  s--;t--;
  V=n;
  for(int i=0;i<m;i++){
    cin>>a>>b>>c>>D;
    a--;b--;c--;
    edge e = {b,D};
    G[a].pb(edge(e));
    
     e = {c,D};
    G[a].pb(edge(e));
    
     e = {c,D};
    G[b].pb(edge(e));
   
    e = {a,D};
    G[b].pb(edge(e));
    
    e = {a,D};
    G[c].pb(edge(e));
    
     e = {b,D};
    G[c].pb(edge(e));
    
  }
  dijkstra(s);
  cout<<d[t]<<endl;
  return 0;
}



Measured memory_bytes: 35560
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n, m;
    cin >> n >> m;

    ll create = min(n, (m/2));

    create += (m-create*2)/4;

    cout << create;

}

Measured memory_bytes: 256
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    TA = in_nl2(N)

    t_score, a_score = 1, 1
    for i in range(N):

        t, a = TA[i]

        if t == a:
            t_score = max(t_score, a_score)
            a_score = t_score
        else:
            t_s = -(-t_score // t) * t
            a_s = (t_s // t) * a
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s
                continue

            a_s = -(-a_score // a) * a
            t_s = (a_s // a) * t
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s

    print(t_score + a_score)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9332
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        k: u64,
    }

    if k == 1 || k == 7 {
        println!("1");
        return;
    }

    let mut s = 7;
    let mut ans = 1;
    while s > 0 {
        s = (10 * s + 7) % k;
        ans += 1;
        if ans > k {
            println!("-1");
            return;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2172
def read_input():
    r, d, x = map(int, input().split())
    return r, d, x


def submit():
    r, d, x = read_input()

    for i in range(10):
        new_x = r*x - d
        print(new_x)
        x = new_x

    return

if __name__ == '__main__':
    submit()


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int N;
   cin >> N;
   vector<int> bar(N);
   for (int i=0; i<N; i++){
       cin >> bar.at(i);
   }
   sort(bar.begin(), bar.end());
   int count=0;
   for (int i=0; i<N; i++){
       for (int j=i+1; j<N; j++){
           for (int k=j+1; k<N; k++){
               if (bar.at(i)+bar.at(j)>bar.at(k)){
                   count += 1;
               }else{
                   break;
               }
           }
       }
   }
   cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
void main(){
	char c = _scan!char();
	(c+1).to!char.writeln();
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2692
#include<stdio.h>
#include<math.h>
int solve(int A,int B){
    int ans=ceil((double)A*12.5);
    while(ans/10 != B){
        ans++;
        if(floor(ans/12.5) != A){ ans = -1; break;}
    }
    return ans; 
}

int main(){
    int  a,b;
    scanf("%d %d",&a,&b);
    printf("%d",solve(a,b));
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }

vector<int> sssp(const vector<vector<int>> &G, int s) {
    const int INF = 1e9;
    vector<int> res(G.size(), INF); res[s] = 0;
    vector<bool> seen(G.size(), false);
    queue<int> que; que.emplace(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        seen[v] = true;
        for (auto u : G[v]) if (!seen[u]) {
            res[u] = res[v] + 1;
            que.emplace(u);
        }
    }
    return res;
}

int main() {
    int N, s, g;
    cin >> N >> s >> g; s--; g--;
    vector<vector<int>> G(N);
    for (int i = 0; i < N-1; i++) {
        int a, b; cin >> a >> b; a--; b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    
    vector<int> taka = sssp(G, s);
    vector<int> aoki = sssp(G, g);
    
    int ans = -1;
    for (int i = 0; i < N; i++) {
        int dist = aoki[i] - taka[i];
        if (dist > 0) chmax(ans, aoki[i]);
    }
    cout << ans-1 << endl;
    return 0;
}

Measured memory_bytes: 6656
let _ = Int(readLine()!)!
let LN = readLine()!.split(separator: " ").compactMap { Int($0) }.sorted()

var result = 0
for i in 0..<LN.count {
    let c = LN[LN.count - 1 - i]

    for j in (i+1)..<LN.count {
        let b = LN[LN.count - 1 - j]

        for z in (j+1)..<LN.count {
            let a = LN[LN.count - 1 - z]

            if a != b, b != c, a + b > c {
                result += 1
            }
        }
    }
}

print(result)


Measured memory_bytes: 8396
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    long long int i,o,t,j,l,s,z;
    cin>>i>>o>>t>>j>>l>>s>>z;
    cout<<o+(i>0&&j>0&&l>0?max(i/2*2+j/2*2+l/2*2,(i-1)/2*2+(j-1)/2*2+(l-1)/2*2+3):i/2*2+j/2*2+l/2*2)<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define all(a)  (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  string s; cin >> s;
  int n = s.size();
  string ans = "AC";
  if(s[0] != 'A') ans = "WA";

  int cnt = 0;
  for (int i = 2; i < n-1; i++) {
    if(s[i] == 'C') cnt++;
  }
  if(cnt != 1) ans = "WA";

  cnt = 0;
  for (int i = 0; i < n; i++) {
    if(s[i]-'a' < 0 ) cnt++;
  }
  if(cnt != 2) ans = "WA";

  std::cout << ans << '\n';
}


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

long long N;
string Xstr;

long long ups[200005];
long long downs[200005];


long long modpow(long long ori, long long po, long long div){
	long long res = 1;
	while(po > 0){
		if(po&1){
			res *= ori;
			res %= div;
		}
		ori *= ori;
		ori %= div;
		po >>= 1;
	}
	return res;
}

long long countbit(long long n) {
	long long ans = 0;
	while(n) {
		if((n&1) == 1){
			ans++;
		}
		n >>= 1;
	}
	return ans;
}


long long cal(long long n) {
	if(n == 0){
		return 0;
	}
	long long ans = cal(n%countbit(n));

	return ans + 1;
}

int main(){
	cin >> N;
	cin >> Xstr;
	long long onecount = 0; 
	for(long long i = 0; i < Xstr.length(); i++) {
		if(Xstr[i] == '1') {
			onecount++;
		}
	}

	long long onecountup = onecount+1; 
	long long onecountdown = onecount-1; 

	//cout << "onecountup = " << onecountup << endl;
	//cout << "onecountdown = " << onecountdown << endl;

	long long uppop = 0;
	long long downpop = 0;
	

	//up
	if(onecountup > 0) {
	for(long long i = 0; i < N; i++) {
		long long po = N-i-1;
		ups[i] = modpow(2, po, onecountup);
		if(Xstr[i] == '1') {
			uppop += ups[i];
			uppop %= onecountup;
		}
	}
	}

	//down
	if(onecountdown > 0) {
	for(long long i = 0; i < N; i++) {
		long long po = N-i-1;
		downs[i] = modpow(2, po, onecountdown);
		if(Xstr[i] == '1') {
			downpop += downs[i];
			downpop %= onecountdown;
		}
	}
	}

	//for(long long i = 0; i < N; i++) {
	//	cout << "ups[" << i << "] = " << ups[i] << endl;
	//}
	//cout << "uppop = " << uppop << endl;

	//for(long long i = 0; i < N; i++) {
	//	cout << "downs[" << i << "] = " << downs[i] << endl;
	//}
	//cout << "downpop = " << downpop << endl;


	for(long long i = 0; i < N; i++) {
		if(Xstr[i] == '1') {
			if(onecountdown == 0){
				cout << 0 << endl;
			}else{
			//down
			long long tmp = (downpop - downs[i] + onecountdown) % onecountdown;
			//cout << "tmp = " << tmp << endl;
			cout << cal(tmp) + 1 << endl;
			}
		} else {
			if(onecountup == 0){
				cout << 1 << endl;
			}else{
			//up
			long long tmp = (uppop + ups[i] + onecountup) % onecountup;
			//cout << "tmp = " << tmp << endl;
			cout << cal(tmp) + 1 << endl;
			}
		}
	}
}

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

int main() {
    double r; cin >> r;
    double ans = 2.0*r*3.141592;
    cout << fixed << setprecision(10);
    cout << ans << endl;
}


Measured memory_bytes: 3784
#include  <bits/stdc++.h>
using namespace std;
#define SYNC ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define io(a) freopen(a".inp","r",stdin),freopen(a".out","w",stdout)
#define pb push_back
#define mp make_pair
#define aln(x,n) (x)+1,(x)+1+(n)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define times_used   cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<"\n"
#define task " "
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef unsigned long long ull;
mt19937 mrand(random_device{}());
const ll mod = 1000000007;
int rnd(int x) { return mrand() % x;}
ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b));}
ll mulmod(ll a,ll b,ll MOD){if (b==0) return 0;if (b==1) return a; ll t=mulmod(a,b/2,MOD);t=(t+t)%MOD;return (b&1 ? (t+a)%MOD : t);}
ll powmod(ll a, ll k, ll MOD) {if (k <= 0) return 1; ll res = 1; a = a % MOD; if (a == 0) return 0; while (k > 0) {if (k & 1) res = mulmod(res, a, MOD); k >>= 1; a = mulmod(a, a, MOD);} return res;}
ll Pow(ll a, ll k) {ll res = 1; while (k > 0) {if (k & 1) res *= a; k >>= 1; a *= a;}; return res;}
//head
const int N=100005;
ll dp[N],n,a[N];
int main()
{
	//SYNC;
	//io("task");
    cin>>n;
    for (int i=1;i<=n;i++)
         cin>>a[i];
    dp[2]=abs(a[1]-a[2]);
    dp[1]=0;
    for(int i=3;i<=n;i++)
        dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i]-a[i-1]));
    cout<<dp[n];
	//times_used;
	return 0;
}



Measured memory_bytes: 5172
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    int l[n];
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    sort(l, l+n);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int k = i + 2;
        for (int j = i + 1; j < n; j++) {
            k = max(k, j + 1);
            while (k < n && l[k] < l[i] + l[j]) {
                k++;
            }
            ans += k - j - 1;
        }
    }

    cout << ans << endl;

    return 0;
}


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

typedef long long ll;
#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define int ll

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define ALL(s) (s).begin(),(s).end()
#define ALLn(s,n) s,s+n
#define F first
#define S second
#define pb push_back
#define tc(t) int t; cin >> t; while(t--)
#define _ ios_base::sync_with_stdio(false); cin.tie(NULL);
#define D1(x) { cerr << " [" << #x << ": " << x << "]\n"; }
#define D2(x) { cerr << " [" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n"; }

const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 7;
const ll INF = LONG_LONG_MAX;

int N, M;
char mat[2001][2001];
vi rows[2001], col[2001];
pii range[2001][2001];

void solve() {
	cin >> N >> M;
	F0R(i, N) F0R(j, M) cin >> mat[i][j];

	F0R(i, N) {
		rows[i].pb(-1);
		F0R(j, M) if (mat[i][j] == '#') rows[i].pb(j);
		rows[i].pb(M);

		int l = 0, r = 1, cnt = 0;
		F0R(j, M) {
			if (mat[i][j] != '#') {
				range[i][j].F = (rows[i][r] - rows[i][l]);
			}
			if (j == rows[i][r]) l = r, r++;
		}
	}

	F0R(i, M) {
		col[i].pb(-1);
		F0R(j, N) if (mat[j][i] == '#') col[i].pb(j);
		col[i].pb(N);

		int l = 0, r = 1;
		F0R(j, N) {
			if (mat[j][i] != '#') range[j][i].S = (col[i][r] - col[i][l]);
			if (j == col[i][r]) l = r, r++;
		}
	}

	int ans = 0;

	// F0R(i, N) {
	// 	F0R(j, M) {
	// 		cerr << '{' << range[i][j].F << ',' << range[i][j].S << "} ";
	// 	}
	// 	cerr << '\n';
	// }
	F0R(i, N) F0R(j, M) {if (mat[i][j] != '#') ans = max(ans, range[i][j].F + range[i][j].S);}

	cout << ans - 3;

}

int32_t main() {
	_

#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif

	// tc(t)
	solve();
	cerr << "[ Time : " << (float)clock() / CLOCKS_PER_SEC << " secs ]" << endl;
}

// 1 4 3 2 5

// 1 - 1
// 2 - 4
// 3 - 3
// 4 - 2
// 5 - 5

Measured memory_bytes: 129632