akhauriyash/Code-Regression huggingface dataset:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = (int) 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

void precalc() {
}


const int maxn = (int) 2e5 + 10;
char s[maxn];
int n, k;

int read() {
  if (scanf("%d%d%s", &n, &k, s) < 3) {
    return 0;
  }
  return 1;
}

char A = 'A' - 1;
char B = 'B' - 1;

void process() {
  if (!k) {
    return;
  }

  if (n == 1) {
    if (k & 1) {
      s[0] ^= 1;
    }
    return;
  }

  int pos = 0;

  int it = 0;
  while (k) {
    //eprintf("k = %d, pos = %d, it = %d\n", k, pos, it);
    if ((s[pos] ^ it) == A) {
      --k;
      s[pos] ^= 1;
      continue;
    }
    it ^= 1;
    --k;
    pos = (pos + 1) % n;
    if (pos == 0 && !it) {
      {
        string q = s;
        for (int i = 0; i < n; ++i) {
          q[i] ^= it;
          q[i] += 1;
        }
        //eprintf("%s\n", q.c_str());
      }
      for (int i = 0; i < n; ++i) {
        assert((it ^ s[n - 1 - i]) == A + (i & 1));
      }
      k %= 4;
    }
  }
  rotate(s, s + pos, s + n);
  if (it) {
    for (int i = 0; i < n; ++i) {
      s[i] ^= 1;
    }
  }
}

void solve() {
  for (int i = 0; i < n; ++i) {
    --s[i];
  }
  process();
  for (int i = 0; i < n; ++i) {
    ++s[i];
  }
  printf("%s\n", s);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 700
n = int(input())
ret = 0
bin_strlist = list(bin(n)) # 0b... ...のところに2進数の数字iの文字列が続く
bin_list = bin_strlist[2:]
if bin_list.count("0") == 0:
    print(len(bin_list))
else:
    print(len(bin_list)-1)


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int mx = max({a, b, c});
    int x = 3 * mx - (a + b + c);
    int y = 3 * (mx + 1) - (a + b + c);
    if (x % 2 == 0) cout << x / 2 << endl;
    else cout << y / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define INF = numeric_limits<long long>::max();
#define intf int_fast64_t
int main(){
    intf n,k,cnt=0;
    cin >>n >>k;

    vector<bool> an(n,true);
    rep(i,k){
        intf d;
        cin >>d;
        rep(h,d){
            intf a;
            cin >>a;
            a-=1;
            an[a]=false;
        }
    }

    rep(j,n){
        if(an[j]){
            cnt++;
        }
    }
    cout << cnt <<endl;

}

Measured memory_bytes: 3632
N = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

d = make_divisors(N)

out = 10
t = 0
while t<=len(d)-1:
    A = N//d[t]
    B = N//A
    X = max(len(str(B)),len(str(A)))
    if X<out:
        out = X
    t+=2
print(out)

Measured memory_bytes: 39152
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vll vector<ll>
#define pb push_back
#define x first
#define y second

int main()
{
	ll n;
	cin>>n;
	ll h[n+1],c[n+1],i,j;
	for(i=1;i<=n;i++)
		cin>>h[i];
	c[1]=0;
	c[2]=abs(h[2]-h[1]);
	for(j=3;j<=n;j++)
		c[j]=min(c[j-1]+abs(h[j]-h[j-1]),c[j-2]+abs(h[j]-h[j-2]));
	cout<<c[n];
	return 0;
}

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

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

#define debug(arr) cout << #arr << " = " << arr << '\n'
#define debug2(a,b) cout << "[" << #a << "," << #b << "] = " << "[" << a << "," << b << "]" << '\n'
template<class T> ostream &operator << (ostream& out, const vector<T>& arr) {
	cout << "{";
	for (int i = 0; i < arr.size(); i++)cout << (!i ? "" : ", ") << arr[i];
	cout << "}";
	return out;
}
template<class T> ostream &operator << (ostream& out, const vector<vector<T> >& arr) {
	cout << "{\n";
	for (auto& vec : arr)cout << "  " << vec << ",\n";
	cout << "}";
	return out;
}
template<class T> istream &operator >> (istream& in, vector<T>& arr) {
	for (auto& i : arr)cin >> i; return in;
}

#define chmin(a,b) (a) = min((a),(b))

#define maxn 1010
#define maxx 5050
#define INF 1e9

int n;
vector<int> g[maxn];
ll X[maxn];

void read() {
	cin >> n;
	for (int i = 1; i < n; i++) {
		int p; cin >> p;
		p--;
		g[p].push_back(i);
	}
	REP(i, n)cin >> X[i];
}

ll dp[maxx];

ll dfs(int x, int pre) {
	vector<vector<ll> > dp2(2, vector<ll>(maxx, INF));
	dp2[0][0] = 0;
	for (int i = 0; i < g[x].size(); i++) {
		int v = g[x][i];
		ll a = X[v], b = dfs(v, x);
		//cout << x << ' ';debug2(a,b);
		for(int j=0;j< maxx;j++) dp2[(i%2)^1][j] = INF;
		for (int j = 0; j <= X[x]; j++) {
			if (j + a <= X[x]) chmin(dp2[(i%2) ^ 1][j + a], dp2[i%2][j] + b);
			if (j + b <= X[x]) chmin(dp2[(i%2) ^ 1][j + b], dp2[i%2][j] + a);
		}
	}
	ll res = 1e9;
	for(int i=0;i<=X[x];i++) chmin(res,dp2[g[x].size()%2][i]);
	//debug2(x,res);
	if(res == INF){
		cout << "IMPOSSIBLE" << '\n';
		exit(0);
	}else{
		return dp[x] = res;
	}
}

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

	read();
	dfs(0,-1);
	//debug(X);
	//debug(dp);
	cout << "POSSIBLE" << '\n';
}


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

#define rep(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define irep(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define rrep(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    int sumx = 0;
    rep(i, 0, n) {
        int l, r;
        cin >> l >> r;
        sumx += (r - l + 1);
    }
    cout << sumx << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int a[100][100];
    int b[100];
    int c[100]={0};
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++){
            scanf("%d", &a[i][j]);
        }
    }
    for (int j=0;j<m;j++){
        scanf("%d", &b[j]);
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            c[i] += a[i][j] * b[j];
        }
    }
 
    for (int i=0;i<n;i++) {
        printf("%d\n", c[i]);
    }
    return 0;
}



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

struct dat {
  long long k, l, r;
  bool operator<(const dat &rd) const {
    if (k != rd.k) return k < rd.k;
    return l > rd.l;
  }
};

long long n;
vector<dat> v, lv, rv;

long long solve();

int main() {
  long long T;
  cin >> T;
  while (T--) {
    cin >> n;
    v.resize(n);
    for (auto &p : v) cin >> p.k >> p.l >> p.r;
    cout << solve() << endl;
  }
  return 0;
}

long long solve() {
  long long res = 0, sum = 0;
  lv.clear();
  rv.clear();
  for (int i = 0; i < n; ++i) {
    sum += v[i].r;
    v[i].l -= v[i].r;
    v[i].r = 0;
    if (v[i].l > 0)
      lv.push_back(v[i]);
    else if (v[i].l != 0)
      rv.push_back(v[i]);
  }
  sort(lv.begin(), lv.end());
  priority_queue<long long, vector<long long>, greater<long long>> pql;
  int len = lv.size();
  for (int i = 0; i < len; ++i) {
    pql.push(lv[i].l);
    while (pql.size() > lv[i].k) pql.pop();
  }
  while (pql.size()) {
    res += pql.top();
    pql.pop();
  }
  priority_queue<long long> pqr;
  sort(rv.begin(), rv.end());
  reverse(rv.begin(), rv.end());
  len = rv.size();
  for (int i = 0; i < len; ++i) {
    rv[i].k = n - rv[i].k;
    pqr.push(rv[i].l);
    while (pqr.size() > rv[i].k) {
      res += pqr.top();
      pqr.pop();
    }
  }
  return res + sum;
}

Measured memory_bytes: 15196
package main

import (
  "fmt"
  "strings"
)

func main() {
  str := "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
  slice := strings.Split(str, ", ")
  var d int
  fmt.Scan(&d)
  fmt.Println(slice[d-1])
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

int main() {
  int K, A, B;
  std::cin >> K >> A >> B;
  for (int i: range(A, B + 1)) {
    if (i % K == 0) {
      std::cout << "OK\n";
      return 0;
    }
  }
  std::cout << "NG\n";
  return 0;
}


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

int main() {
    int i, x;
    i = 1;
    while (1) {
        cin >> x;
        if (x == 0) { 
          break;
        }
        else {
          cout << "Case " << i << ": " << x << endl;  
        }
        i += 1;
    }
    return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
//main
signed main(){

  int N;cin>>N;
  std::vector<int> v(N);
  for(int i=1;i<N;i++){cin>>v[i];v[i]--;}

  std::vector<int> w(N,0);
  for(int i=1;i<N;i++)w[v[i]]++;
  queue<int> que;
  for(int i=0;i<N;i++)if(w[i]==0)que.push(i);
  std::vector<int> r(N,0);
  std::vector<int> s[N];
  while(que.size()){
    int p=que.front();que.pop();
    s[v[p]].push_back(r[p]);
    if(s[v[p]].size()==w[v[p]]){
      int res=0,c=1;
      sort(s[v[p]].rbegin(),s[v[p]].rend());
      for(int a:s[v[p]])res=max(res,a+c++);
      r[v[p]]=res;
      if(v[p])que.push(v[p]);
    }
  }
  cout<<r[0]<<endl;
}


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

int main(){
    string S;
    string sample="FESTIVAL";
    cin>>S;
    int find_fes=S.rfind(sample);
    for(int i=0;i<find_fes;i++)cout<<S[i];
    cout<<endl;
    return 0;
}

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

// #define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define FI ios_base::sync_with_stdio(0); cin.tie(NULL);

#define LL long long

const int MOD = 1e9 + 7;
const int INF = 1e9 + 9;
const int MX = 1e5 + 5;

int r,c,k;
LL inp[3005][3005];
LL dp[3005][3005][4];

LL solve(int i, int j, int p) {
	if(i == r-1 && j == c-1) {
		if(p < 3) {
			return inp[i][j];
		}
		return 0;
	}

	LL &ret = dp[i][j][p];
	if(ret != -1) {
		return ret;
	}

	ret = -1;
	if(i+1 < r && j < c) {
		if(inp[i][j] > 0) {
			//value
			if(p < 3) {
				//can pick
				//pick
				ret = max(ret, inp[i][j] + solve(i+1,j,0));
			}
			//don't pick
			ret = max(ret, solve(i+1,j,0));
		}
		else {
			//no value
			ret = max(ret, solve(i+1,j,0));
		}
	}
	if(i < r && j+1 < c) {
		if(inp[i][j] > 0) {
			//value
			if(p < 3) {
				//can pick
				//pick
				ret = max(ret, inp[i][j] + solve(i, j+1, p+1));
			}
			//don't pick
			ret = max(ret, solve(i, j+1, p));
		} else {
			//no value
			ret = max(ret, solve(i, j+1, p));
		}
	}
	return ret;
}	

int main() {
	memset(inp, 0, sizeof inp);
	memset(dp, -1, sizeof dp);
	cin >> r >> c >> k;
	int r1,c1,v1;
	for(int i=0;i<k;i++) {
		cin >> r1 >> c1 >> v1;
		r1--;
		c1--;
		inp[r1][c1] = v1;
	}
	LL ans = solve(0,0,0);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 356860
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define N 1000002
struct edge{int to,nxxt;}e[N];
int n,k,a[N],ans,head[N],cnt=1;
int len[N];
bool vis[N];
inline void ins(int u,int v){e[cnt].to=v;e[cnt].nxxt=head[u];head[u]=cnt++;}
void df5(int te,int la)
{len[te]=1;
	for(int i=head[te];i;i=e[i].nxxt)
	{
		int j=e[i].to;if(j==la)continue;
		df5(j,te);if(vis[j])continue;
		if(len[j]+1>len[te])len[te]=len[j]+1;
	}
	if(te!=1&&la!=1&&len[te]>=k)vis[te]=1;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	if(a[1]^1)ans++;
	for(int i=2;i<=n;i++)ins(a[i],i);
	df5(1,1);for(int i=2;i<=n;i++)ans+=vis[i];
	printf("%d\n",ans);
}


Measured memory_bytes: 11520
#include <iostream>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

// 素因数分解
// 因数, 個数のmapを返す
map<int, int> prime_factorization(int N) {
  map<int, int> mp;
  int n = N;
  if (n == 1) {
    mp[n]++;
  }

  // 2で割り切れるだけわる
  while (n != 1 && n % 2 == 0) {
    mp[2]++;
    n /= 2;
  }

  for (int i = 3; i * i <= n; i += 2) {
    while (n % i == 0) {
      mp[i]++;
      n /= i;
    }
  }
  if (n != 1) mp[n]++;
  
  return mp;
}

int main() {
  map<int, int> mp;
  int N;
  cin >> N;
  for (int i = 1; i <= N; i++) {
    map<int, int> returned_map;
    returned_map = prime_factorization(i);
    for (auto p: returned_map) {
      mp[p.first] += p.second;
    }
  }
  ll result = 1;
  for (auto p: mp) {
    if (p.first == 1) continue;
    result = result % MOD * (p.second + 1);
  } 
  cout << result % MOD  << endl;
}


Measured memory_bytes: 256
A,B = map(int,input().split())
 
K=(A+B)/2
 
def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False
 
if is_integer_num(K)==False:
  print("IMPOSSIBLE")
else:
  print(int(K))

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

using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define FORR(i,a,b) for(int i=(b)-1; i>=(a); i--)

#define ALL(v) (v).begin(), (v).end()
#define CHMAX(a,b) a=max(a,b)
#define CHMIN(a,b) a=min(a,b)

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl

int n;
int key[125];
char s[125];

int main(){
    while(true){
        scanf("%d",&n);
        if(n==0)break;
        REP(i,n)scanf("%d",key+i);
        fill(s,s+125,'\0');
        scanf("%s",s);
        int len = strlen(s);
        REP(i,len){
            int k = key[i%n];
            int id = 0;
            if(isupper(s[i])){
                id = s[i] - 'A';
            }else{
                id = s[i] - 'a' + 26;
            }
            id = (id + 52 - k) % 52;
            if(id < 26){
                putchar('A'+id);
            }else{
                putchar('a'+(id-26));
            }
        }
        puts("");
    }
    return 0;
}


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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 1e5 + 5;
vector<int> adj[MAX];
char str[MAX];

void die() {
    puts("-1");
    exit(0);
}

int main() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    if(str[1] != '1' || str[n] == '1') {
        die();
    }
    fori(i, 1, n) {
       if(str[i] != str[n - i]) {
           die();
       }
    }
    int cur_node = 2, next_node = 3;
    adj[1].push_back(2);
    int size = 2;
    while(next_node <= n) {
        adj[cur_node].push_back(next_node);
        if(str[size] == '0') {
        }
        else {
            cur_node = next_node;
        }
        next_node++;
        size++;
    }
    fori(i, 1, n + 1) {
        for(auto &each : adj[i]) {
            printf("%d %d\n", i, each);
        }
    }
    return 0;
}


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

int main(void) {
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;
  vector<int> L(Q), R(Q);
  REP(i, 0, Q) cin >> L[i] >> R[i], L[i]--;

  vector<int> x(N);
  REP(i, 0, N - 1) {
    if (S[i] == 'A' && S[i + 1] == 'C') {
      x[i] = 1;
    }
  }

  vector<int> sum(N + 1);
  REP(i, 0, N) sum[i + 1] = sum[i] + x[i];

  REP(i, 0, Q) {
    cout << sum[R[i] - 1] - sum[L[i]] << endl;
  }
}

Measured memory_bytes: 2688
#include<stdio.h>
#include<math.h> 
int main()
{
	int a1,a2,a3;
	while(scanf("%d%d%d",&a1,&a2,&a3)!=EOF)
	{
		int t; 
		if(a1>a2)
		{t=a1;a1=a2;a2=t;}
		if(a1>a3)
		{t=a1;a1=a3;a3=t;}
		if(a2>a3)
		{t=a2;a2=a3;a3=t;}
		int x,y,s; 
		x=fabs(a2-a1);
		y=fabs(a3-a2);
		s=x+y;
		printf("%d\n",s);		 
	} 
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

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

        int s = scanner.nextInt();

        for (int i = 1; i <= 100; i *= 10) {
            if (s / i % 10 == 1) {
                count++;
            }
        }

        System.out.println(count);
    }
}

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

int f(int n){
    if(n%2 == 0) return n/2;
    else return 3 * n + 1;
}

int main(){
    int s;
    cin >> s;
    int res = 1;
    if(s == 1 || s == 2 || s == 4){
        cout << 4 << endl;
        return 0;
    }
    else{
        while(1){
          	res++;
            s = f(s);
            if(s == 1 || s == 2 || s == 4){
                cout << res + 3 << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで
// g++ hoge.cpp -std=c++17 -I . でコンパイルできる
// -fsanitize=undefinedでオーバーフロー検出
#include <bits/stdc++.h>
//#include <atcoder/all>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
//using namespace atcoder;
typedef pair<ll,ll> P;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll a,b,c,d,m,n,k,x,y,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>n;
    if(n) cout<<0<<endl;
    else cout<<1<<endl;

    return 0;
}


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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll 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;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
const int MAX_N=55;
int par[MAX_N];
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
    }
}
int root(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=root(par[x]); 
    }
}
bool same(int x,int y){
    return root(x)==root(y);
}
void unite(int x,int y){
    x=root(x);
    y=root(y);
    if(x==y){
        return;
    }else{
        par[x]=y;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N=in();
    int M=in();
    int ans;ans=0;
    vector<pair<int,int>> path;
    int a;int b;
    REP(i,M){
        cin>>a>>b;
        path.push_back(make_pair(a-1,b-1));
    }
    REP(i,M){
        init(N);
        REP(j,M){
            if(j!=i){
                unite(path[j].first,path[j].second);
            }
        }
        if(!same(path[i].first,path[i].second))ans++;
    }
    print(ans);
    return 0;
}

Measured memory_bytes: 256
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>a>>b>>c;
    for(ll i=a;i<=b;i++){
        if(i%c==0) sum++;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3612
/*
* Author : Omkar
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(v) v.begin(), v.end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define pb push_back
#define intvect vector<int>
#define ld long double
#define ull unsigned long long
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);
void solve()
{
    int n;
    cin >> n;
    int ans = 1;
    intvect a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(all(a));
    for (int i = 0; i < n; i++)
    {
        int tp = ans;
        ans *= a[i];
        if (a[i] == 0)
        {
            ans = 0;
            break;
        }
        if ((ans > (int)1e18 or a[i] > (int)1e18) or (ans < tp and a[i] != 0))
        {
            ans = -1;
            break;
        }
    }
    cout << ans << endl;
}
int32_t main()
{
    // #ifndef ONLINE_JUDGE
    //     if (fopen("input.txt", "r"))
    //     {
    //         freopen("input.txt", "r", stdin);
    //         freopen("output.txt", "w", stdout);
    //     }
    // #endif
    fast;
    int t;
    // cin >> t;
    // while (t--)
    solve();
}

Measured memory_bytes: 3984
//BECAUSE ONE TRUTH PREVAILS
#include<bits/stdc++.h>
using namespace std;
#define LL unsigned long long int
string convert(LL  A)
{
    string Ans="";
    while(A)
    {
        LL x=(A%26?A%26:26)+96;
        Ans=(char)x+Ans;
        if(x==122)
        {
        A=(A/26)-1;
        }
        else
        {
        A=A/26;
        }
    }
    return Ans;
}
int main() {
    LL n;
    cin>>n;
    cout<<convert(n)<<endl;
}


Measured memory_bytes: 3628
def inpl():
    return list(map(int, input().split()))


N, K = inpl()
A = inpl()

if K == 0:
    print(sum(A))
    exit()

t = len(bin(K)) - 2
oneCounter = [0 for _ in range(t)]
# print(t)
sumA = 0
for a in A:
    sumA += a
    tmp = bin(a)[2:]
    # print(tmp)
    for i, x in enumerate(reversed(tmp)):
        # print(i, x)
        if i >= t:
            break
        elif x == "0":
            continue
        oneCounter[i] += 1
    # print(a, zeroCounter)

# print(oneCounter)
nibeki = [2**i for i in range(t)]
ans = sumA
orK = bin(K)[2:]
# print(orK)
tmp = 0
for j in range(len(orK)):
    if orK[j] == "0":
        continue
    tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
ans = max(ans, sumA + tmp)

for i in range(len(orK)):
    if orK[i] == "0":
        continue

    tmp = 0
    for j in range(i):
        if orK[j] == "0":
            continue
        tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    # print(tmp)

    for j in range(i + 1, t):
        if 2 * oneCounter[t - 1 - j] < N:
            # print(i, oneCounter[i])
            tmp += nibeki[t - 1 - j] * (N - 2 * oneCounter[t - 1 - j])
    # print(orK, i, ans, tmp)
    ans = max(ans, sumA + tmp)
print(ans)


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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX;
const int INF = INT_MAX;

inline int sqr(int x) { return (x * x); }
inline void printd(double x) { printf("%.10lf\n", x); }
inline void upsort(VI& x) { sort((x).begin(), (x).end()); }
inline void downsort(VI& x) { sort((x).begin(), (x).end(), greater<int>()); }
inline int absdiff(int a, int b) { return (a - b)*(1|((a - b)>>(8*sizeof(int))));}
int gcd(int a, int b) { // 最大公約数
	if (a < b) return gcd(b, a);
	int r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
inline int lcm(int a, int b) { return a * b / gcd(a, b); } // 最小公倍数

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

	VI A(M);
	rbf(a, A) cin >> a;

	int sum = 0;
	rbf(a, A) {
		sum += a;
	}

	int day = N - sum;
	if (day < 0) COL(-1);
	else COL(day);
	
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
using pp=pair<int,pair<int,int>>;
#define MAX 200003
#define MOD 1000000007
#define INF 1000000000000000000

int main(){
  int n,q;
  cin>>n>>q;
  int k=sqrt(n);
  int l=(n+k-1)/k;

  vector<ll> a(n,0);
  vector<ll> b(l,0);

  vector<ll> ans;
  for(int i=0;i<q;i++){
    int c;
    cin>>c;
    if(c==0){
      int s,t;
      ll x;
      cin>>s>>t>>x;
      s--;
      while(s<t&&s%k>0){
        a.at(s)+=x;
        s++;
      }
      while(s<t&&t%k>0){
        t--;
        a.at(t)+=x;
      }
      while(s<t){
        b.at(s/k)+=x;
        s+=k;
      }
    }else{
      int x;
      cin>>x;
      x--;
      ans.push_back(a.at(x)+b.at(x/k));
    }
  }

  for(int i=0;i<ans.size();i++){
    cout<<ans.at(i)<<endl;
  }
}



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

int gcd(int n, int m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

int main()
{
    int n, k;
    cin >> n >> k;
    int a[100002];
    cin >> a[0];
    int lar = a[0];
    for(int i = 1; i < n; i++){
        cin >> a[i];
        lar = max(lar, a[i]);
        a[i] = gcd(a[i - 1], a[i]);
    }
    if(k % a[n - 1] == 0 && k <= lar) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <stdarg.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

#define ll long long

using namespace std;

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

  vector<ll> h(n+2, 0);
  for (int i=1; i<=n; i++) cin>>h[i];

  vector<vector<ll>> dp(n+2, vector<ll>(n+2, 1e18));
  for (int i=0; i<n+2; i++) dp[0][i] = 0;

  for (int end=1; end<=n+1; end++) 
    for (int level=0; level<=n; level++) {
      for (int i=0; i<=level; i++) {
        if (end-1-i < 0) continue;
        dp[end][level] = min(dp[end][level], dp[end-1-i][level-i] + max(0ll, h[end] - h[end-1-i]));
      }
    }

  cout<<dp[n+1][k]<<endl;
  return 0;
}


Measured memory_bytes: 1024
open String
open List



let rec my_split_on_char ?(list=[]) char string =
 try let n = index string char in
  my_split_on_char ~list:((sub string 0 n) :: list) char (sub string (n + 1) ((String.length string) - n - 1))
 with Not_found -> rev (string :: list);;


let read_list () =
 my_split_on_char ' ' (read_line ());;

let read_list_int () =
 map int_of_string (read_list ());;

let rec read_input_list ?(list=[]) t = match t with
   0 -> list
 | _ -> read_input_list ~list:((read_list_int ()) :: list) (t - 1);;



let rec solve input k n = match input with
   [] -> k
 | [p; c] :: input ->
           if (n - k + 1 <= c) then
            solve input (k - p + 1) n
           else if (n - k + 1 <= (c + p - 1)) then
            solve input (k + c) n
           else
            solve input k n
 | x -> exit 0;;

let rec c_solve () =
 let list = read_list_int () in match list with
   [n; r] ->
       if (n == 0) then ()
       else
        let input = read_input_list r in
         (print_int (solve input n n); print_newline (); c_solve ())
 | x -> exit 0;;

c_solve ();;



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

int main(){
  int N;
  cin >> N;
  vector<int> v(N);
  int sum = 0;
  int tsum = 0;
  int tsum1, tsum2;

  for(int i = 0; i < N; i++){
    cin >> v.at(i);
    sum += v.at(i);
  }

  for(int i = 0; i < N; i++){
    if(tsum + v.at(i) >= sum / 2){
      tsum1 = tsum;
      tsum2 = tsum + v.at(i);
      break;
    }
    tsum += v.at(i);
  }

  cout << min((sum - tsum1) - tsum1, tsum2 - (sum - tsum2)) << endl;

  return 0;
}


Measured memory_bytes: 256
N = int(input())

pattern = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]

INF = 10**6
dp = [INF] * (N+1)
dp[0] = 0

for i in range(N+1):
  for p in pattern:
    if i + p <= N:
      dp[i+p] = min(dp[i+p], dp[i]+1)

print(dp[N])

Measured memory_bytes: 3828
n = gets.strip.to_i
l = gets.split.map(&:to_i).combination(3).to_a
cnt = 0
l.each do |l0, l1, l2|
  next if l0 == l1 || l1 == l2 || l2 == l0
  cnt += 1 if l0 + l1 > l2 && l1 + l2 > l0 && l2 + l0 > l1
end
p cnt


Measured memory_bytes: 22780
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    int a;
    int cnt5=0,cnt7=0;
    rep(i,3){
        cin>>a;
        if(a==5) ++cnt5;
        else if(a==7) ++cnt7;
    }
    if(cnt5==2&&cnt7==1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256
n, c, k = map(int, input().split())
arrivals = [int(input()) for i in range(n)]
arrivals.sort()
 
res = 0
room = c
bus_start = None
 
for t in arrivals:
 
    previous_bus_has_left = bus_start is not None and bus_start + k < t
    if previous_bus_has_left:
        res += 1
        room = c
 
    if room == c:
        bus_start = t
 
    room -= 1
 
    if room == 0:
        res += 1
        room = c
        bus_start = None
 
if room < c:
    res += 1
 
print(res)

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

template <typename T> T mod_sub (T a, T b, T m);

int main() {
	uint32_t N, K;
	cin >> N >> K;
	
	vector<vector<uint64_t>> dp(2, vector<uint64_t>(K+1));
	dp[1][0] = 1;
	
	uint32_t tmax = 0;
	uint64_t mod = pow(10, 9) + 7;
	
	for(uint32_t i=0; i<N; i++) {
		uint32_t a;
		cin >> a;
	
		tmax = min(tmax + a, K);
		
		bool ic = i & 1;
		bool ip = !ic;
		uint64_t tsum = 0;
		
		for(uint32_t j=0; j<=K && j<=tmax; j++) {
			tsum = (tsum + dp[ip][j]) % mod;

			if(j > a) tsum = mod_sub(tsum, dp[ip][j-a-1], mod);

			dp[ic][j] = tsum;
		}
	}
		
	cout << dp[(N-1)&1][K];
	return 0;
}

template <typename T> T mod_sub (T a, T b, T m) {
	return (a == b) ? 0 : (a > b) ? (a - b) % m : m + a - b;
}

Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
        }

        Arrays.sort(s);
        System.out.println(String.join("", s));
    }
}


Measured memory_bytes: 23124
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# N, M = map(int, input().split())
# As = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    ac = 0
    wa = 0
    tle = 0
    re = 0

    for i in range(N):
        s = input()
        if s == 'AC':
            ac += 1
        elif s == 'WA':
            wa += 1
        elif s == 'TLE':
            tle += 1
        elif s == 'RE':
            re += 1

    print(f'AC x {ac}')
    print(f'WA x {wa}')
    print(f'TLE x {tle}')
    print(f'RE x {re}')


def main():
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 9188
import itertools
n, m = map(int, input().split())
ab = {}
for i in range(n+1):
    ab[i] = []
for i in range(m):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

count = 0
 
for values in list(itertools.permutations(range(2, n+1))):
    pre = 1
    for i, v in enumerate(values):
        if(v not in ab[pre]):
            break
        if i == n-2:
            count += 1
        pre = v

print(count)

Measured memory_bytes: 3572
N = int(input())
a = [int(input()) for i in range(N)]
ans = 0
turn = 1
while True:
    if a[turn-1] == 2:
        ans += 1
        break
    if a[turn-1] == 0:
        ans = -1
        break
    next_turn = a[turn-1]
    a[turn-1] = 0
    ans += 1
    turn = next_turn

print(ans)

Measured memory_bytes: 7084
import itertools
n,k = map(int, input().split())
di = [0] * k
Ai_di = []
for i in range(k):
    di[i] = int(input())
    Ai_di.append(list(map(int, input().split())))
ans_set = set(list(itertools.chain.from_iterable(Ai_di)))
print(n - len(ans_set))

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)

typedef long long ll;
typedef pair<ll,ll> P;


int main(){
	
	ll n,m;cin >> n >> m;
	vector<ll> v(m);
	REP(i,m)cin >> v[i];
	
	sort(ALL(v));
	vector<ll> seica;
	REP(i,m-1)seica.PB(v[i+1] - v[i]);
	sort(ALL(seica));
		
	ll ans = 0;
	REP(i,m-n)ans += seica[i];
	
	cout << ans << endl;
	
	
	return 0;
}


Measured memory_bytes: 2168
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef struct{
	char mark;
	int value;
}TRAMP;

void PRINT(TRAMP* A,int Len){
    for(int i = 0;i<Len-1;i++){
        printf("%c%d ",A[i].mark,A[i].value);
    }
    printf("%c%d\n",A[Len-1].mark,A[Len-1].value);
    return;
}

void BubbleSort(TRAMP* C,int N){
    for(int i = 0;i<N;i++){
        for(int j = N-1;j >= i+1;j--){
            if(C[j].value < C[j-1].value){
                TRAMP buff = C[j];
                C[j] = C[j-1];
                C[j-1] = buff;
            }
        }
    }
    return;
}

void SelectionSort(TRAMP* C,int N){
    for(int i = 0;i<N;i++){
        int minj = i;
        for(int j = i;j < N;j++){
            if(C[j].value < C[minj].value)
                minj = j;
        }
        TRAMP buff = C[i];
        C[i] = C[minj];
        C[minj] = buff;
    }
    return;
}

bool CheckStable(TRAMP* A,TRAMP* B,int Len){
    for(int i = 0;i<Len-1;i++){
        if(B[i].value == B[i+1].value){
            int a,b;
            for(int j = 0;j<Len;j++){
                if(A[j].value == B[i].value && A[j].mark == B[i].mark){
                    a = j;
                }
            }
            for(int j = 0;j<Len;j++){
                if(A[j].value == B[i+1].value && A[j].mark == B[i+1].mark){
                    b = j;
                }
            }
            if(a > b){
                return false; //notStable
            }
        }
    }
    return true; //Stable
}

int main(){
    int Len;
    scanf("%d",&Len);
    TRAMP cards[Len],buff[Len];
    for(int i = 0;i<Len;i++){
        char Input[3];
        scanf("%s",Input);
        cards[i].mark = Input[0];
        cards[i].value = (int)(Input[1] - '0');
        buff[i] = cards[i];
    }
    BubbleSort(buff,Len);
    PRINT(buff,Len);
    if(CheckStable(cards,buff,Len)){
        printf("Stable\n");
    }else{
        printf("Not stable\n");
        
    }

    for(int i = 0;i<Len;i++){
        buff[i] = cards[i];
    }
    SelectionSort(buff,Len);
    PRINT(buff,Len);
    if(CheckStable(cards,buff,Len)){
        printf("Stable\n");
    }else{
        printf("Not stable\n");
        
    }



    return 0;
}



Measured memory_bytes: 2724
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let n: usize = read_as_vec()[0];
    let mut v: Vec<i32> = read_as_vec();

    v.sort();

    let mut v: Vec<f64> = v.into_iter().map(|x| x as f64).collect();

    let mut ans = (v[0]+v[1])/2.0;
    for i in 2..n{
        ans = (ans+v[i])/2.0;
    }

    println!("{}", ans);
}


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

static const int N = 1e+5;
vector<int> fr[N], bl[N];
int n, group[N], color = 0, conn[N];

void dfs(int s){
    bool visited[N];
	rep(i, n){
		visited[i] = false;
		conn[i] = 0;
	}

    function<void(int)> rec = [&](int u){
        visited[u] = true;
        group[u] = color;
        conn[color]++;
        rep(i, fr[u].size()){
            if(visited[fr[u][i]]) continue;
            rec(fr[u][i]);
        }
        return;
    };

	rep(i, n){
		if(visited[i]) continue;
		rec(i);
		color++;
	}
	return;
}

int main(){
	int m, k, x, y;
	cin >> n >> m >> k;
	rep(i, m){
		cin >> x >> y;
		fr[x-1].push_back(y-1);
		fr[y-1].push_back(x-1);
	} rep(i, k){
		cin >> x >> y;
		bl[x-1].push_back(y-1);
		bl[y-1].push_back(x-1);
	}
	
	dfs(0);
	
	int cnt[n];
	rep(i, n){
		cnt[i] = 0;
		rep(j, bl[i].size()){
			if(group[i] != group[bl[i][j]]) cnt[i]++;
		}
	}
	rep(i, n){
        if(i) cout << " ";
		cout << conn[group[i]] 
            - fr[i].size()- bl[i].size() + cnt[i] - 1;
	}
    cout << endl;
	return 0;
}

Measured memory_bytes: 13568
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

x=int(input())
div=make_divisors(x)
def depth_limited(x,div):
    depth=-50
    while True:
        depth+=50
        for t in div:
            for b in range(depth,depth+50):
                if x==t*(5*b**4+10*b**3*t+10*b**2*t**2+5*b*t**3+t**4):
                    return (b+t,b)
                b=-b
                if x==t*(5*b**4+10*b**3*t+10*b**2*t**2+5*b*t**3+t**4):
                    return (b+t,b)
ans=depth_limited(x,div)
print(str(ans[0])+' '+str(ans[1]))

Measured memory_bytes: 9380
D, G = [int(str) for str in input().strip().split()]
PC = [[int(str) for str in input().strip().split()] for _ in range(D)]

ans = 10 ** 4

for bits in range(2 ** D + 1):
    num, score = 0, 0
    for i in range(D):
        if (0x01 << i) & bits:
            score += PC[i][0] * (i + 1) * 100 + PC[i][1]
            num += PC[i][0]
    
    i = D - 1
    pnum = 0
    while score < G and i >= 0:
        if not (0x01 << i) & bits:
            score += (i + 1) * 100
            num += 1
            pnum += 1
            if pnum >= PC[i][0]:
                pnum = 0
                i -= 1
        else:
            i -= 1
    
    if score >= G:
        ans = min(ans, num)

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define int long long
using namespace std;
    int fib[100];
    main(){
        int n;
        cin >> n;
        fib[0] = 2;
        fib[1] = 1;
        for(int i = 2 ; i <= n;i++){
            fib[i] = fib[i-1] + fib[i-2];
        }
        cout << fib[n];



    }


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll n,m;
  cin >> n>> m;
  vector<pair<ll,ll>> v;
  for(int i=0;i<n;i++){
    ll a,b;
    cin >> a >> b;
    v.push_back(make_pair(a,b));
  }
  sort(v.begin(),v.end());
  

  ll s=0;
  ll ite=0;
  for(int i=0;i<m;i++){
    if(v[ite].second==0)ite++;
    s+=v[ite].first;
    v[ite].second--;
  }
  cout << s << endl;

}

Measured memory_bytes: 5308
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }
//    val list = (1..n).map { readLine()!!.toInt() }
    val ans = solve(list)
    print(ans)
}

fun solve(nums: List<Int>): Int {
    val n = nums.size
    val sum = nums.sum()
    val squareSum = nums.map { pow(it) }.sum()

    val p = calculateP(sum, n)
    val upperP = Math.ceil(p).toInt()
    val downerP = Math.floor(p).toInt()

    val upperMin = min(squareSum, sum, n, upperP)
    val downerMin = min(squareSum, sum, n, downerP)

    return if (upperMin < downerMin) {
        upperMin
    } else {
        downerMin
    }
}

fun calculateP(sum: Int, n: Int): Double {
    return sum.toDouble() / n.toDouble()
}


fun min(nums: List<Int>, p: Int): Int {
    val n = nums.size

    return n * pow(p) - 2 * p * nums.sum() + nums.map { pow(it) }.sum()
}

fun min(squareSum: Int, sum: Int, n: Int, p: Int): Int {
    return n * pow(p) - 2 * p * sum + squareSum
}

fun pow(num: Int): Int {
    return num * num
}



Measured memory_bytes: 37988
S = list(input())
ans = 0
n_ans = 0
for i in range(len(S)):
  if(S[i]=='A' or S[i]=='C' or S[i]=='G' or S[i]=='T'):
    n_ans += 1
  else:
    ans = max(ans, n_ans)
    n_ans = 0
ans = max(ans, n_ans)
print(ans)

Measured memory_bytes: 9128
/*input

*/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <climits>

using namespace std; 

int GCD(int x,int y){return y?GCD(y,x%y):x;}
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,n) for(int i=0;i<(n);i++)
#define repl(i,a,b) for(int i=(a);i<(b);i++)
#define repm(i,a,b) for(int i=(a);i>(b);i--)
#define rept(v) for(auto it=v.begin();it<v.end();it++)
#define all(v) v.begin(),v.end()
const int INF = 1<<30;
typedef long long ll;
typedef pair<int,int> pii;


int n, k;
int p[5005], c[5005];
ll ans = LLONG_MIN;

void check(int i) {
	// DEBUG(i)
	unordered_map<int, int> cycle;
	int iter = 0, cur = i;
	ll sum = 0;
	vector<ll> best;
	while(iter<k) {
		if(cycle[cur]) break;
		sum += c[p[cur]];
		// DEBUG(sum)
		if(best.empty()) best.push_back(sum);
		else best.push_back(max(best.back(), sum));
		cycle[cur]++;
		cur = p[cur];
		iter++;
	}
	// DEBUG(sum)
	// DEBUG(iter)
	// rept(best) cout << *it << " ";
	// cout << endl;
	ans = max(ans, best.back());
	int mleft = k-iter, kleft = k%iter;
	if(mleft) ans = max(ans, (ll)(sum*(k/iter-1)
		+ (kleft ? max(sum + best[kleft - 1], best.back()) : best.back())));
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(0);
	cin >> n >> k;
	rep(i, n) {cin >> p[i]; --p[i];}
	rep(i, n) cin >> c[i];
	rep(i, n) {
		check(i);
	}
	cout << ans;
	return 0;
}
// 29507023469

Measured memory_bytes: 3876
#include<bits/stdc++.h>
using namespace std;
 
#define FAST ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define endl "\n"
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
 
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pp;
typedef pair<ll,pair<ll,ll> > ppp;
 
const ll N    = 5e5+5;
const ll INF  = 1e9;
const ll mod  = 1e9+7;


  
int LongestIncreasingSubsequenceLength(std::vector<int>& v) 
{ 
    if (v.size() == 0) 
        return 0; 
  
    std::vector<int> tail(v.size(), 0); 
    int length = 1; // always points empty slot in tail 
  
    tail[0] = v[0]; 
    for (size_t i = 1; i < v.size(); i++) { 
  
        if (v[i] < tail[0]) 
            tail[0] = v[i]; 
  
        else if (v[i] >= tail[length - 1]) 
            tail[length++] = v[i];
        else{
            auto pos = upper_bound(tail.begin(),tail.begin()+length,v[i])-tail.begin();
            tail[pos] = v[i]; 
        }
    } 
  
    return length; 
} 

void solve()
{
    ll x,n,d;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
        cin>>x,v.push_back(x);
    
    reverse(all(v));
    cout<<LongestIncreasingSubsequenceLength(v)<<endl;
}     
 
int main(){
    FAST
    int t= 1;
    // cin>>t;
    while(t--)
        solve();
    return 0;
} 

Measured memory_bytes: 1144