akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

class Main {

	int a,b;

	String op;

	public void si() {

		Scanner sc = new Scanner(System.in);

		boolean sw = true;

		while(sw == true) {

			a = sc.nextInt();

			op = sc.next();

			b = sc.nextInt();

			if(op.equals( "+" )){

				System.out.println(a + b);

			} else if(op.equals ( "-" )) {

				System.out.println(a - b);

			} else if(op.equals ( "*" )) {

				System.out.println(a * b);

			} else if(op.equals ( "/" ) ) {

				if(b > 0) {

					System.out.println(a / b);

				}

			} else if(op.equals( "?" )) {

				sw = false;

			}

		}

	}

	public static void main(String[] args){

		new Main().si();

	}

}

Measured memory_bytes: 26348
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; 
const int N = 1e7+10, mod = 2e9+10;

void solve() {
    int n; cin >> n;

    vector<ll> a(N);
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j * i <= n; ++j) {
            ++a[i * j];
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += a[i] * i;
    }
    cout << ans << endl;
}

int main(void) {
    int t = 1; 
    while (t--) solve();
    return 0;
}

Measured memory_bytes: 81376
#include<bits/stdc++.h>
using namespace std;
int main(){

  long long int X;
  cin >> X;
  
  long long A = X / 500LL * 1000LL;
  
  X = X - (A / 1000LL * 500);
  
  long long B = X / 5LL * 5LL;
  
  cout << A + B << endl;
  
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

int main(void)
{
  char x[1001];
  char END[2]={0};
  int i,l,num;
  int sum=0;

  for(;;){
    scanf("%s", x);
    if(x[0]=='0') break;

    l=strlen(x);

    for(i=0;i<l;i++){
      num=x[i]-'0';
      sum=sum+num;
    }
  
    printf("%d\n", sum);
    sum=0;
  }

  return 0;
}


Measured memory_bytes: 968
import sys
input = sys.stdin.readline
 
n = int(input())
robots = []
for i in range(n):
    x, l = [int(item) for item in input().split()]
    robots.append((x+l, x-l))
 
robots.sort()
 
cnt = 0
node = -10**12
for end, start in robots:
    if start >= node:
        node = end
        cnt += 1
print(cnt)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); 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; }
const ll MOD = 1e9+7;

int main(){
    int A, B;
    cin >> A >> B;

    cout << max(A-2*B, 0) << endl;
    return 0;
}


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (Int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) {
            if (not(a[i] % 3 == 0 or a[i] % 5 == 0)) {
                dump("DENIED");
                return 0;
            }
        }
    }
    dump("APPROVED");
    return 0;
}


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

int main() {
    init();

    ll a, b, n; cin >> a >> b >> n;
    if (b - 1 <= n)cout << (b - 1) * a / b << "\n";
    else cout << n * a / b << "\n";
}

Measured memory_bytes: 3636
from operator import itemgetter
N = int(input())

L = [[] for _ in range(N)]
for i in range(N):
    s,p = [j for j in input().split()]
    L[i] = (s,int(p),i+1)

L.sort()
j = 0
p = L[0][0]
ans = [[] for _ in range(N)]
for i in range(N):
    if L[i][0] == p:
        ans[j].append([L[i][1], L[i][2]])
    else:
        j += 1
        p = L[i][0]
        ans[j].append([L[i][1], L[i][2]])


for i in range(j+1):
    z = sorted(ans[i], reverse=True)
    [print(j[1]) for j in z]


Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int x1 = Integer.parseInt(sa[0]);
		int y1 = Integer.parseInt(sa[1]);
		int x2 = Integer.parseInt(sa[2]);
		int y2 = Integer.parseInt(sa[3]);
		br.close();

		int x3 = x2 + y1 - y2;
		int y3 = y2 + x2 - x1;
		int x4 = x3 + x1 - x2;
		int y4 = y3 + y1 - y2;
		System.out.println(x3 + " " + y3 + " " + x4 + " " + y4);
	}
}


Measured memory_bytes: 21204
def examC():
    S = SI()
    K = I()
    d = set()
    for i in range(len(S)):
        for j in range(5):
            s = S[i:(i+j+1)]
            d.add(s)
    d = list(d)
    d.sort()
    print(d[K-1])

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


Measured memory_bytes: 4976
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <utility>
#include <functional>
#include <map>
#include <string>

using namespace std;

class UnionFind {
  private:
    // 各頂点vの親を表すリスト.
    // v自身が親ならば、-(vを含む集合の要素数)に設定する
    vector<int> parent;

  public:
    // 頂点数Nの親を-1に初期化することで、バラバラを表現する.
    UnionFind(int N) {
      parent = vector<int>(N, -1);
    }

    // 頂点vを含む木のrootを返す.
    int root(int v) {
      // v自身が親
      if (parent[v] < 0) {
        return v;
      }
      else {
        // vを含む木のrootをvの親とする。
        // (言い換え)vを含む集合の代表をvの親とする。
        return parent[v] = root(parent[v]);
      }
    }

    // 頂点vの所属する集合の要素数.
    int size(int v) {
      return -parent[root(v)];
    }

    // 頂点vとwが同じ集合に含まれているかどうかを示す.
    bool isSame(int v, int w) {
      return root(v) == root(w);
    }

    // 頂点v, wを同じグループにする。
    bool connect(int v, int w) {
      v = root(v);
      w = root(w);

      // vとwは同じ集合に属しているならば、この操作は必要ない。
      if (v == w) {
        return false;
      }

      // size(v) <= size(w)という想定。
      if (size(v) > size(w)) {
        swap(v, w);
      }

      // サイズが小さい集合を大きい集合にマージする。
      // サイズが小さい集合のrootの親は、大きい集合のrootとする。
      parent[w] += parent[v];
      parent[v] = w;

      return true;
    }

    string printP() {
      string str;
      str += "parent : ";

      for (int i = 0; i < parent.size(); i++) {
        str += (to_string(parent[i]) + ", ");
      }

      return str;
    }
};

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

  int N, M;
  cin >> N >> M;

  int a[M], b[M];
  for (int i = M - 1; i >= 0; i--) {
    cin >> a[i] >> b[i];
    a[i]--;
    b[i]--;
  }

  vector<long> ans = vector<long>(M);
  ans[0] = (long) N * (N - 1) / 2;

  UnionFind uni = UnionFind(N);

  for (int i = 0; i < M - 1; i++) {
    if (!uni.isSame(a[i], b[i])) {
      // a[i], b[i]は違うグループ
      ans[i + 1] = ans[i] - (long)(uni.size(a[i]) * uni.size(b[i]));
      // cout << ans[i + 1] << ", " << ans[i] << endl;
      uni.connect(a[i], b[i]);
    }
    else {
      ans[i + 1] = ans[i];
    }
  }

  for (int i = M - 1; i >= 0; i--) {
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 3328
#include <ios>
#include <iomanip>
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;
 
int main()
{
    ll N, A;
    cin >> N >> A;
    vector<ll> x(N);
    rep(i, N) {
        cin >> x[i];
        x[i] -= A;
    }
    ll X = max(*max_element(all(x)), A);
    ll NX = N * X;
    ll dp[55][5010];
    memset(dp, 0, sizeof(dp));
    dp[0][NX] = 1;

    for(ll i = 0; i < N; ++i) {
        for(ll j = 0; j <= 2*NX; ++j) {
            dp[i+1][j] += dp[i][j];
            if (j >= x[i]) dp[i+1][j] += dp[i][j-x[i]];
        }
    }
    print(dp[N][NX]-1);

    return 0;
}

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


int n,a[100005];



int main(){

    cin >> n;
    map<int, int > mp;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        mp[x]++;
    }
    int ans = 0;
    for(map<int,int> ::iterator it = mp.begin();it!= mp.end();it++){
        int cnt = it->second, val = it->first;
        if(val>cnt){
            ans += cnt;
        } else {
            ans += cnt - val;
        }
    }
    cout << ans << endl;



}


Measured memory_bytes: 4736
# B - Trick or Treat
n,k = map((int),(input().split()))

sunuke = [0]*n

for i in range(0, k):
    d = (int)(input())
    a = list(map(int,(input().split())))
    for j in range(0, d):
        sunuke[a[j] - 1] = 1

sum = 0
for k in sunuke:
    if k == 0:
        sum += 1

print(sum)

Measured memory_bytes: 9196
#define _GLIBCXX_DEBUG
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int x, y, z;
  scanf("%d %d %d", &x, &y, &z);
  printf("%d %d %d", z, x, y);
}

Measured memory_bytes: 256
[<EntryPoint>]
let main argv =
    let a: int [,] = Array2D.zeroCreate 3 3
    let checks = Array2D.create 3 3 false
    let index = [| 0; 1; 2 |]

    let a0 =
        stdin.ReadLine().Split(' ') |> Array.map int

    index |> Array.iter (fun i -> a.[0, i] <- a0.[i])

    let a1 =
        stdin.ReadLine().Split(' ') |> Array.map int

    index |> Array.iter (fun i -> a.[1, i] <- a1.[i])

    let a2 =
        stdin.ReadLine().Split(' ') |> Array.map int

    index |> Array.iter (fun i -> a.[2, i] <- a2.[i])

    let n = stdin.ReadLine() |> int
    let b = Array.zeroCreate n
    for i in [ 0 .. n - 1 ] do
        b.[i] <- (stdin.ReadLine() |> int)

    a
    |> Array2D.iteri (fun i j v1 ->
        b
        |> Array.iteri (fun k v2 -> if v1 = v2 then checks.[i, j] <- true else ()))

    (Array.reduce (&&) (index |> Array.map (fun i -> checks.[0, i]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[1, i]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[2, i]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[i, 0]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[i, 1]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[i, 2]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[i, i]))
     || Array.reduce (&&) (index |> Array.map (fun i -> checks.[2 - i, i])))
    |> fun x -> if x then "Yes" else "No"
    |> printfn "%s"

    0


Measured memory_bytes: 30660
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0)
#define END return EXIT_SUCCESS
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR(I,0,N)
#define ALL(C) (C).begin(),(C).end()
#define INPUT(P) std::cin>>(P)
#define INPUT2(P1,P2) std::cin>>(P1)>>(P2)
#define INPUT3(P1,P2,P3) std::cin>>(P1)>>(P2)>>(P3)
// #define INPUTS(I,A,B,V) FOR(I,A,B)cin>>V[I]
#define INPUTS(I,N,V) REP(I,N) std::cin>>V[I]
#define OUTPUT(P) std::cout<<P<<std::endl
#define OUTPUT2(P1,P2) std::cout<<P1<<P2<<std::endl
#define OUTPUT3(P1,P2,P3) std::cout<<P1<<P2<<P3<<std::endl
// #define OUTPUTS(I,A,B,V) FOR(I,A,B)cout<<V[i]<<endl
#define OUTPUTS(I,N,V) REP(I,N) std::cout<<V[i]<<std::endl
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ul;
const int MOD = 1000000007;
const ll INF = 1e18;
using namespace std;
int i,j,k;
int N;
int x[100];
int y[100];
int h[100];
int t;
int H;
int X,Y;
bool flag;
inline void solve(){
  INPUT(N);
  REP(i,N){
    cin>>x[i]>>y[i]>>h[i];
    if(h[i]>0){
      t=i;
    }
  }
  REP(X,101)REP(Y,101){
    H=h[t]+abs(x[t]-X)+abs(y[t]-Y);
    flag=true;
    REP(i,N){
      if(i==t)continue;
      if(h[i]!=max(H-abs(x[i]-X)-abs(y[i]-Y),0)){
        flag=false;
        break;
      }
    }
    if(flag){
      printf("%d %d %d\n",X,Y,H);
      return;
    }
  }
}

int main(int argc,char**argv){
  BEGIN;
  solve();
  END;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
#隣接リスト
graph=[[0]*n for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  graph[a-1][b-1]=1
  graph[b-1][a-1]=1


def dfs(v,visited):
  #print("v",v,"visited",visited)
  if not False in visited:
    #print("visited",visited,"end")
    return 1
  count=0
  for i in range(n):
    if not graph[v][i]:continue
    if visited[i]:continue
    
    visited[i]=True
    count+=dfs(i,visited)
    visited[i]=False
  return count

# 到達したかどうかlist（Falseは未到達、Trueは到達済み）
visited=[False] *(n)
visited[0]=True
print(dfs(0,visited))
#print("visited",visited)
#print("graph",graph)


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

int main() {
	int N, A, B, R;
	cin >> N >> A >> B;
	R = N*A;
	if (R > B) {
		cout << B << endl;
	}
	else if(B=R) {
		cout << B << endl;
	}
	else {
		cout << R << 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(0);
    
    int n;
    string s;
    cin >> n >> s;

    map<char, set<int>> m;
    ll ans=0;

    for (int i=0; i<s.size(); i++) {
        m[s[i]].insert(i);
        if (s[i] == 'R') {
            ans += m['B'].size() * m['G'].size();
            for (int e : m['G']) {
                ans -= m['B'].count(2*e-i);
                if ((i-e)%2 == 0) {
                    ans -= m['B'].count((i+e) / 2);
                }
            }
        } else if (s[i] == 'G') {
            ans += m['R'].size() * m['B'].size();
            for (int e : m['R']) {
                ans -= m['B'].count(2*e-i);
                if ((i-e)%2 == 0) {
                    ans -= m['B'].count((i+e) / 2);
                }
            }
        } else if (s[i] == 'B') {
            ans += m['R'].size() * m['G'].size();
            for (int e : m['R']) {
                ans -= m['G'].count(2*e-i);
                if ((i-e)%2 == 0) {
                    ans -= m['G'].count((i+e) / 2);
                }
            }
        }  
    }
    cout << ans << "\n";
}


Measured memory_bytes: 3816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
inline ll read(){
	ll res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
	return res*f;
}
void write(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10|'0');
}
const int N=1e5+7;
int n,w;
int W[N],v[N],ans,f[N];
signed main(){
	n=read(),w=read();
	memset(f,0x3f3f,sizeof f);
	for(int i=1;i<=n;i++) W[i]=read(),v[i]=read();
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1e5;j>=v[i];j--){
			f[j]=min(f[j],f[j-v[i]]+W[i]);
			if(f[j]<=w)ans=max(ans,j);
		}
		
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {

            var NC = Sarray();
            var N = NC[0];
            var C = NC[1];
            var x = new long[N];
            var v = new long[N];
            for (var i = 0; i < N; ++i)
            {
                var xv = Sarray();
                x[i] = xv[0];
                v[i] = xv[1];
            }
            var ruiVCw = new long[N + 1];
            var ruiVCcw = new long[N + 1];
            var maxVCw = new long[N + 1];
            var maxVCcw = new long[N + 1];
            for (var i = 1; i <= N; ++i)
            {
                ruiVCw[i] = ruiVCw[i - 1] + v[i - 1];
                ruiVCcw[i] = ruiVCcw[i - 1] + v[N - i];
                maxVCw[i] = Max(maxVCw[i - 1], ruiVCw[i] - x[i - 1]);
                maxVCcw[i] = Max(maxVCcw[i - 1], ruiVCcw[i] - (C - x[N - i]));
            }

            var maxCw2Ccw = maxVCw.Max();
            var maxCcw2Cw = maxVCcw.Max();
            for (var i = 1; i <= N; ++i)
            {
                maxCw2Ccw = Max(maxCw2Ccw, ruiVCw[i] - 2 * x[i - 1] + maxVCcw[N - i]);
                maxCcw2Cw = Max(maxCcw2Cw, ruiVCcw[i] - 2 * (C - x[N - i]) + maxVCw[N - i]);
            }
            WriteLine(Max(maxCw2Ccw, maxCcw2Cw));
        }
    }
}

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

using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
const int maxn = 1e5 + 50;
const int mod = 1e9 + 7;

inline void upd( int & x , int v ){
	x += v;
	if( x >= mod )
		x -= mod;
}

long long N;

int dp[80][2][2][8] , val[7] = {-3,-2,-1,0,1,2,3};


int main( int argc , char * argv[] ){
	cin >> N;
	dp[61][0][0][3] = 1;
	for(int i = 61 ; i >= 1 ; -- i)
		for(int f1 = 0 ; f1 < 2 ; ++ f1)
			for(int f2 = 0 ; f2 < 2 ; ++ f2)
				for(int f3 = 0 ; f3 <= 7 ; ++ f3)
					if( dp[i][f1][f2][f3] ){
						int ed1 = f1 ? 1 : ( ( N >> (i - 1) ) & 1 );
						int ed2 = f2 ? 1 : ( ( N >> (i - 1) ) & 1 );
						for(int ad1 = 0 ; ad1 <= ed1 ; ++ ad1)
							for(int ad2 = 0 ; ad2 <= ed2 ; ++ ad2){
								if( ad1 == 1 && ad2 == 1 )
									continue;
								int newf1 = f1 | ( ad1 < ed1 );
								int newf2 = f2 | ( ad2 < ed2 );
								if( f3 == 7 )
									upd( dp[i - 1][newf1][newf2][f3] , dp[i][f1][f2][f3] );
								else{
									int nxtval = val[f3] + (N >> (i - 1) & 1) - ad1 - ( ad2 << 1 );
									nxtval <<= 1;
									if( nxtval < -3 )
										continue;
									int newf3 = 7;
									if( nxtval <= 3 ) newf3 = nxtval + 3;
									upd( dp[i - 1][newf1][newf2][newf3] , dp[i][f1][f2][f3] );
								}
							}
					}
	int ans = 0;
	for(int f1 = 0 ; f1 < 2 ; ++ f1)
		for(int f2 = 0 ; f2 < 2 ; ++ f2)
			for(int f3 = 3 ; f3 <= 7 ; ++ f3)
				upd( ans , dp[0][f1][f2][f3] );
	printf( "%d\n" , ans );
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<limits>

int main(){
	int n, k;
	long long mod= 1000000007;
	std::vector<int> aList;
	std::vector<std::vector<long long>> dpList; 

	std::cin>>n>>k;

	aList.resize(n);
	dpList.resize(n+1);
	for(int i=0; i<n+1; i++)
		dpList[i].resize(k+1, 0);

	for(int i=0; i<n; i++)
		std::cin>>aList[i];

	dpList[0][0]=1;
	int curMax=0;

	for(int i=0; i<n; i++){
		std::vector<long long> cumSum(curMax+1, 0);
		cumSum[0]= dpList[i][0];

		for(int j=1; j<=curMax; j++)
			cumSum[j] = (cumSum[j-1] + dpList[i][j])%mod;

		for(int j=0; j<=k; j++){
			int maxIdx= std::min(j, curMax);
			int minIdx= std::max(-1, j-aList[i]-1);

			if(maxIdx-minIdx>=0){
				dpList[i+1][j]= cumSum[maxIdx];

				if(minIdx>=0)
					dpList[i+1][j]= dpList[i+1][j] - cumSum[minIdx];

				if(dpList[i+1][j]< 0)
					dpList[i+1][j]+=mod;
			}
		}

		curMax= std::min(curMax+aList[i] , k);
	}

	std::cout<<dpList[n][k]<<std::endl;

	return 0;
}

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

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

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<P> vp;
typedef vector<ll> vll;

const int INF = 99999999;
const int MAX_V = 100000;

struct edge { int to, cap, cost, rev; };

int V, E, F;
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V]; // privious vertex, edge

void add_edge(int from, int to, int cap, int cost) {
    G[from].emplace_back((edge){to, cap, cost, (int)G[to].size()});
    G[to].emplace_back((edge){from, 0, -cost, (int)G[from].size() - 1});
}

// get min cost flow from s to t
// if we can flow not at all, then return -1
int min_cost_flow(int s, int t, int f) {
    int res = 0;
    while (f > 0) {
        fill(dist, dist + V, INF);
        dist[s] = 0;
        bool update = true;
        while (update) {
            update = false;
            rep(v, V) {
                if (dist[v] == INF) continue;
                rep(i, G[v].size()) {
                    edge &e = G[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        update = true;
                    }
                }
            }
        }

        if (dist[t] == INF) {
            // no more flow
            return -1;
        }

        // flow as much as possible along minimum path from s to t
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, (int)G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * dist[t];
        for (int v = t; v != s; v = prevv[v]) {
            edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return res;
}

signed main() {
    cin >> V >> E >> F;
    rep(i, E) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        add_edge(u, v, c, d);
    }

    cout << min_cost_flow(0, V - 1, F) << endl;
}

Measured memory_bytes: 5564
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a=1, s=0, M=0, m=0, N, n;
  cin >> N;
  n=N;
  while (n>0){
    n/=10;
    M++;
  }
  for (int i=0; i<M; i++) {
    a*=10;
    s+=(N%a-N%(a/10))/(a/10);
  }
  int f;
  f=N%s;
  if (f) {
    cout <<"No";
  }
  if (!(f)) {
    cout <<"Yes";
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] <= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) left = mid;
		else right = mid;
	}
	/* left は条件を満たす最大の値、right は条件を満たさない最小の値になっている */
	return left;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
long long int dp[100030] = {};
long long int nokori[100030] = {};
long long int MOOD = 998244353;
int main() {
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>>p;
	for (int i = 0; i < k; i++) {
		int l, r;
		cin >> l >> r;
		p.push_back(make_pair(l, r));
	}
	vector<long long int> ruiseki;
	ruiseki.push_back(0);
	ruiseki.push_back(1);
	for (int i = 2; i <= n; i++) {
		long long int sum = 0;
		for (int j = 0; j < p.size(); j++) {
			int first = i-  p[j].first;
			int second = i - p[j].second-1;
			if (first < 0) {
				first = 0;
			}
			if(second < 0) {
				second = 0;
			}
			sum = (sum + ruiseki[first] - ruiseki[second]) % MOOD;
		}
		//cout << sum<<endl;
		ruiseki.push_back((sum+ruiseki[i-1])%MOOD);
	}
	if (ruiseki[n] - ruiseki[n - 1] < 0) {
		cout << MOOD + (ruiseki[n] - ruiseki[n - 1]);
	}
	else {
		cout << ruiseki[n] - ruiseki[n - 1];
	}
}

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

int main() {
    string S;
    cin >> S;

    int maxSeq = 0;

    for(int i = 0; i < 3; i++) {
        if(S.at(i) == 'R') {
            if(i != 0 && S.at(i - 1) == 'R') {
                maxSeq++;
            } else {
                maxSeq = 1;
            }
        }
    }

    cout << maxSeq << endl;

    return 0;
}


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

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll k, s;
	cin >> k >> s;
	ll ans = 0;
	REP(i, k+1){
		REP(j, k+1){
			if (s >= i+j && s-(i+j) <= k){ ans++; }
		}
	}
	cout << ans << endl;
}


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

int main(){
    double a, b, h, m;
    cin >> a>> b>>h>>m;
    double ka,kb;
    double ksum = 0;
    double s = 0;
    double PI = 3.141592653589793238;

    ka = 30 * h + (double)30/60*m;
    kb = 6 * m;
    ksum = max(ka,kb) - min(ka,kb);




if(ksum > 180) ksum = 360 - ksum;


    s = a*a+b*b-2*a*b*(double)cos(ksum / 180 * PI);

    s = sqrt(s);

    cout <<setprecision(21)<< s << endl;


}

Measured memory_bytes: 4260
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int n;
  cin >> n;
  while (n--) {
    int x, y, b, p;
    cin >> x >> y >> b >> p;
    cout << min(x * b + y * p, (x * max(b, 5LL) + y * max(p, 2LL)) * 4 / 5) << endl;
  }
}

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

/* using */
using namespace std;

/* main constructor */
struct Fast
{
    Fast()
    {
        std::cin.tie(0);
        ios::sync_with_stdio(0);
        //cout << fixed << setprecision(12);
    }
} fast;

/* template */
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 */
#define REP(i, x, n) for (int i = x; i < (int)(n); ++i)
#define RREP(i, x, n) for (int i = x - 1; i >= (int)(n); --i)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) REP(i, 1, n + 1)
#define rrep(i, n) RREP(i, n, 0)
#define each(i, n) for (auto &i : n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define eunique(x) (x).erase(unique(all(x)), (x).end())
#define int long long

/* function */
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); }

/* const */
const int inf = 1e9 + 7;

/* main */
signed main(void)
{
    int n, x = 0, max = 0;
    string s;
    cin >> n >> s;
    rep(i, n)
    {
        switch (s[i])
        {
        case 'I':
            x++;
            if (max < x)
            {
                max = x;
            }
            break;
        case 'D':
            x--;
            break;

        default:
            break;
        }
    }
    cout << max << endl;
    return 0;
}

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

typedef long long lint;

int main(){
    int N,M;
    cin >> N >> M;

    int cnt[100001];
    for(int i=1;i<=N;i++) cnt[i]=0;

    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]++;
    }

    for(int i=1;i<=N;i++){
        if(cnt[i]%2){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 640
def balanced_neighbors(N: int)->list:
    if N & 1:
        return balanced_neighbors(N-1) + [(i, N) for i in range(1, N)]

    res = []
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if i + j == N+1:
                continue
            res.append((i, j))
    return res


if __name__ == "__main__":
    N = int(input())
    ans = balanced_neighbors(N)

    print(len(ans))
    for a, b in ans:
        print(a, b)


Measured memory_bytes: 3996
#ライブラリインポート
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

def BFS(H, W, L, start):
	dist = [[INF for i in range(W)] for j in range(H)]
	sy, sx = start
	dist[sy][sx] = 0
	Q = queue.Queue()
	Q.put([sy, sx])
	while not Q.empty():
		y, x = Q.get()
		if y - 1 >= 0:
			if L[y - 1][x] == "." and dist[y - 1][x] > dist[y][x] + 1:
				dist[y - 1][x] = dist[y][x] + 1
				Q.put([y - 1, x])
		if y + 1 <= H - 1:
			if L[y + 1][x] == "." and dist[y + 1][x] > dist[y][x] + 1:
				dist[y + 1][x] = dist[y][x] + 1
				Q.put([y + 1, x])
		if x - 1 >= 0:
			if L[y][x - 1] == "." and dist[y][x - 1] > dist[y][x] + 1:
				dist[y][x - 1] = dist[y][x] + 1
				Q.put([y, x - 1])
		if x + 1 <= W - 1:
			if L[y][x + 1] == "." and dist[y][x + 1] > dist[y][x] + 1:
				dist[y][x + 1] = dist[y][x] + 1
				Q.put([y, x + 1])

	return dist

#処理内容
def main():
	H, W = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)

	ans = 0
	for i in range(H):
		for j in range(W):
			if L[i][j] == ".":
				BF = BFS(H, W, L, [i, j])
				for p in range(H):
					for q in range(W):
						if BF[p][q] != INF:
							ans = max(ans, BF[p][q])

	print(ans)


if __name__ == '__main__':
	main()

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

int main() {
	string S;
	cin >> S;

	int N = S.size();

	if(N % 2 == 0) {
		cout << "No" << endl;
		return 0;
	}

	bool ans = true;
	for(int i = 0; i < N; i++) {
		if(i == (N + 1) / 2)
			break;
		if(S.at(i) != S.at(N - 1 - i))
			ans = false;
	}

	int n = (N - 1) / 2;
	string s1 = S.substr(0, n);
	string s2 = S.substr((N + 3) / 2 - 1);

	for(int i = 0; i < n; i++) {
		if(i == (n + 1) / 2)
			break;
		if(s1.at(i) != s1.at(n - 1 - i))
			ans = false;
		if(s2.at(i) != s2.at(n - 1 - i))
			ans = false;
	}

	if(ans)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

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

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

  int n; cin >> n;
  int x[n];
  int ave = 0;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    ave += x[i];
  }
  ave = round(double(ave)/n);
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    sum += (x[i] - ave) * (x[i] - ave);
  }
  cout << sum << '\n';
}

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

using ll=long long; 

void solve(){
	int h,w;
	cin>>h>>w;
	vector<string> s(h);
	for(int i=0; i<h; i++)cin>>s[i];
	for(int i=0; i<h; i++){
		bool flag=false;
		for(int j=0; j<w; j++){
			flag|=(s[i][j]=='#');
		}
		if(!flag){
			for(int j=0; j<w; j++){
				s[i][j]='o';
			}
		}
	}
	for(int i=0; i<w; i++){
		bool flag=false;
		for(int j=0; j<h; j++){
			flag|=(s[j][i]=='#');
		}
		if(!flag){
			for(int j=0; j<h; j++){
				s[j][i]='o';
			}
		}
	}
	for(int i=0; i<h; i++){
		bool flag=false; 
		for(int j=0; j<w; j++){
			if(s[i][j]=='o')continue;
			cout<<s[i][j];
			flag=true;
		}
		if(flag)cout<<endl;
	}
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
  
        static void Main(string[] args)
        {
            int[] NM = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int[] A = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            int N = NM[0];
            int M = NM[1];
            int count = 0;
            int sum = A.Sum();
            for (int i = 0; i < N; i++)
            {
                if (sum <= 4 * M * A[i])
                {
                    count++;
                }
            }
            if (M <= count)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 28264
import copy

n, m = list(map(int, input().split()))
s = []

for i in range(m):
    st = list(map(int, input().split()))
    s.append([0]+st)


p = list(map(int, input().split()))
ans = 0

# 全bit探索
for i in range(2**(n)):
    lst = copy.deepcopy(s) # list のコピーにはcopy.copy()を用いる(2重配列以上はdeepcopy()を用いる)
    flag = True
    for j in range(n):
        if i >> j & 1 == 1:
            for k in lst:
                for l in range(2, k[1]+2):
                    if k[l]-1 == j:
                        k[0] += 1
    # 偶数奇数が合えば ans+=1
    for b in range(len(p)):
        if p[b] != lst[b][0]%2:
            flag = False
    if flag == True:
        ans +=1

print(ans)

Measured memory_bytes: 9264
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    cout <<  (1000+n-1)/1000*1000 - n  << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    ll a, b, x;
    cin >> a >> b >> x;
    ll cntA = a / x;
    ll cntB = b / x;
    ll ans = cntB - cntA;
    if (a % x == 0) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3540
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

ll solve(ll a, ll &c){
    if(a == 0){
        return c;
    }
    if(a == 1){
        return c+1;
    }
    ll j = __builtin_popcount(a);
    if(a%j == 0){
        return c+1;
    }else{
        c++;
        return solve(a%j, c);
    }
}

int main(){
    ll n; string x; cin >> n >> x;
    ll c = 0;
    rep(i, 0, n){
        if(x[i] == '1'){
            c++;
        }
    }
    vll mdl(n+1),mdr(n+1);
    ll l = c-1, r = c+1;
    //debug(l) debug(r)
    ll ml = 0;
    ll md = 1%l;
    if(l > 0){
    mdl[n] = md;
    if(x[n-1] == '1'){
        ml += md;
    }
    rrep(i, n-2, -1){
        md *= 2;
        md %= l;
        mdl[i+1] = md;
        if(x[i] == '1'){
            ml += md;
        }
        ml %= l;
    }
    }
    ll mr = 0;
    md = 1%r;
    mdr[n] = md;
    if(x[n-1] == '1'){
        mr += md;
    }
    rrep(i, n-2, -1){
        md *= 2;
        md %= r;
        mdr[i+1] = md;
        if(x[i] == '1'){
            mr += md;
        }
        mr %= r;
    }
    //debug(ml) debug(mr)
    rep(i, 0, n){
        ll v;
        ll b = 1;
        if(x[i] == '1'){
            if(l == 0){
                prtl(0);
            }else{
            v = (ml - mdl[i+1] + l)%l;
            prtl(solve(v, b));
            }
        }else{
            v = (mr + mdr[i+1])%r;
            prtl(solve(v, b));
        }
    }
}


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

int n;
int a[1000];

int main() {
	int i, j;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++) {
			if ((a[j] - a[i]) % (n - 1) == 0) {
				cout << a[i] << " " << a[j] << endl;
				return 0;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3156
using System;
using System.Linq;
using System.Collections.Generic;
namespace Solution
{
    class Solution
    {
        static void Main(string[] args)
        {
            int n = int.Parse(System.Console.ReadLine());
            string s = "11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721";
            int[] x = s.Split(' ').Select(Z => int.Parse(Z)).ToArray();
            for (int i = 0; i < n - 1; i++) System.Console.Write("{0} ", x[i]);
            System.Console.Write("{0}\n", x[n - 1]);
        }

    }
}


Measured memory_bytes: 13396
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//#define BZ
//#define PBDS
//#define POINT

#ifndef BZ
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("no-stack-protector")
#pragma GCC target ("tune=native")
//#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("conserve-stack")
//#pragma GCC optimize ("no-stack-limit")
#endif

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string;
using pll = pair<ll, ll>;

#ifdef POINT
using point = complex<ll>;
#define x real
#define y imag
#endif

#ifdef PBDS
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//using namespace __gnu_pbds::detail;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

#define INF 0x7fffffffffffffffLL
#define BASE 1000000007LL // 3 * 10**9 + 19 // 998244353 - rev == pow(n + m, BASE - 2)
#define MAX(type) std::numeric_limits<type>::max()
#define MIN(type) std::numeric_limits<type>::min()

#define LOG(v) cout << #v << " " << v << "\n";

#define pb push_back
#define eb emplace_back
//#define all(c) c.begin(), c.end()
//#define rall(c) c.rbegin(), c.rend()
#define F first
#define S second
#define forEach(c) for (auto &it : c)
#define loop while (true)
#define mp make_pair
#define mt make_tuple

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

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

inline ll divUp(ll a, ll b) {
	return (a + b - 1)/b;
}

ll gcd(ll a, ll b) {
	return b? gcd(b, a % b) : a;
}

void solve() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	forEach(a) cin >> it;
	ll g = 0;
	forEach(a) g = gcd(g, it);
	cout << g << "\n";
}

//#define LOCAL

int main() {
	FASTIO
#ifdef LOCAL
	auto start = std::chrono::system_clock::now();
#endif
	solve();
#ifdef LOCAL
	auto end = std::chrono::system_clock::now();
	std::chrono::duration<ld> elapsed_seconds = end - start;
	cerr << "\ntime: " << elapsed_seconds.count() << " s\n";
#endif
	return 0;
}


Measured memory_bytes: 1024
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = ReadLine().ToCharArray();
            bool isAc = false;
            if (s[0] != 'A')
            {

            }
            else
            {
                if (('A' <= s[1] && s[1] <= 'Z') || ('A' <= s[s.Length - 1] && s[s.Length - 1] <= 'Z'))
                {

                }
                else
                {
                    if (s.Where(n => n == 'C').Count() == 1)
                        isAc = true;
                }
            }
            WriteLine(isAc ? "AC" : "WA");
        }

        static int InputNum()
        {
            return int.Parse(ReadLine());
        }
        static List<int> InputNumList()
        {
            return ReadLine().Split(' ').Select(int.Parse).ToList();
        }
    }
}



Measured memory_bytes: 13140
import collections as co
while True:
    n = int(input())
    if n == 0:
        break
    a = []
    for i in range(n):
        b = int(input())
        a.append(b)
    for j in range(10):
        c = a.count(j)
        if c == 0:
            print('-')
        else:
            print('*'*c)


Measured memory_bytes: 6072
# import sys
# input = sys.stdin.readline
# import re
import math
import itertools

def main():
    n, k, s = input_list()
    if s == 10**9:
        a = [10**9]*k + [1]*(n-k)
    else:
        a = [s]*k + [s+1]*(n-k)
    print(' '.join(map(str, a)))

# 累積和
def get_camulative(l):
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count(mazes, hc, wc):
    hc = list(hc)
    wc = list(wc)
    r = 0
    for hi, row in enumerate(mazes):
        if hi in hc:
            continue
        for wi, m in enumerate(row):
            if wi in wc:
                continue
            if m == '#':
                r += 1
    return r

def input_list():
    return list(map(int, input().split()))

def input_list_str():
    return list(map(str, input().split()))

if __name__ == '__main__':
    main()



Measured memory_bytes: 88452
N = gets.to_i
csf_list = (N - 1).times.map { gets.split.map(&:to_i) }

(0...(N - 1)).each do |i|
  c, s, f = csf_list[i]
  ans = s + c
  ((i + 1)...(N - 1)).each do |ii|
    c2, s2, f2 = csf_list[ii]
    t = [ans, s2].max
    wait = if t == s2
      0
    elsif t > s2
      if (t - s2) % f2 == 0
        0
      else
        f2 - ((t - s2) % f2)
      end
    else
      0
    end
    ans = t + wait + c2
  end
  puts ans
end
puts 0


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define fin cin
#define fout cout
#define int long long
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
#define all(x) x.begin(), x.end()
#define left vadia
#define lb lower_bound
#define right puta
using namespace std;
using namespace __gnu_pbds;
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9+7;
const int MAXN = 2e5 + 5;
const int MAXV = 1e6+5;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;

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

	int ans = 0;
	for(int i = 1; i <= n-1; i++) {
		int ini = 1, mid, best = 1, end = n-1;
		while(ini <= end) {
			mid = (ini + end)>>1;
			if(mid * i < n) {
				ini = mid + 1;
				best = max(best, mid);
			}
			else
				end = mid - 1;
		}
		ans += best;
	}

	cout << ans << endl;

}


Measured memory_bytes: 3628