akhauriyash/Code-Regression huggingface dataset:
def main():

    n, k = (int(i) for i in input().split())
    tel = [int(i) - 1 for i in input().split()]

    # take one step with our 'slo' walker
    slo = tel[0]
    fas = tel[slo]
    k -= 1

    while k != 0 and slo != fas:
        slo = tel[slo]
        fas = tel[tel[fas]]
        k -= 1

    if k == 0:
        print(slo + 1)
        return

    cyc = 0
    while k != 0:
        slo = tel[slo]
        cyc += 1
        k -= 1
        if fas == slo:
            break

    k = k % cyc

    for i in range(k):
        slo = tel[slo]

    print(slo + 1)


main()


Measured memory_bytes: 32276
# 12:
# 12
# 3 9
# 4 8
# 5 7
# 6 6
# 7 5
# 8 4
# 9 3
# sum[3<=k<=n-3] f(k) + 1


def mpower(a, b, n):
    if b == 0:
        return 1
    if b == 1:
        return a % n
    a1 = a
    k = 1
    while a1 < n and k < b:
        a1 = a1 * a
        k = k + 1

    a1 = a1 % n
    b1 = b // k
    a2 = a
    b2 = b % k
    return (mpower(a1, b1, n) * mpower(a2, b2, n)) % n


def msum(m, tbl):
    ret = 0
    for i in tbl:
        ret = (ret + i) % m
    return ret


class DPTable:
    def __init__(self):
        self.table = [0, 0, 1, 1, 1]

    def solve(self, n, m):
        if n <= 0:
            return 0
        already_solved = len(self.table)
        if n <= already_solved:
            return self.table[n - 1]
        self.table += [0] * (n - already_solved)
        for i in range(already_solved + 1, n + 1):
            self.table[i - 1] = (
                msum(m, (self.table[j - 1] for j in range(3, i - 3 + 1))) + 1
            ) % m
        return self.table[n - 1]


m = 10 ** 9 + 7
n = int(input())
t = DPTable()
print(t.solve(n, m))


Measured memory_bytes: 9252
// Author : Sarthak Kapoor
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define repba(i,b,a) for(int i=b;i>=a;--i)
#define repab(i,a,b) for(int i=a;i<b;++i)
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define msi map<string,int>
#define mii map<int,int>
#define viip vector<pair<int,pair<int,int> > > 
#define mp make_pair
#define vip vector<pair<int,int> >
#define pb push_back 
#define po pop_back
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define s(v) v.size()
ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//use rng()%n for numbers in range [0,n-1]
ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}
ll fastexp(ll x,ll a){
    ll res = 1;
    while(a>0){
        if(a&1){
            res = (res*x)%mod;
        }
        a=a>>1;
        x=(x*x)%mod;
    }
    return res;
}
ll inverse(ll n){
    return fastexp(n,mod-2);
}
void add(int &a,int b){
	a += b;
	if(a >= mod){
		a-=mod;
	}
}
void sub(int &a, int b){
	a -= b;
	if(a < 0){
		a += mod;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n,k;
	cin>>n>>k;
	vi v(n);
	rep(i,n)cin>>v[i];
	vector<int> dp(k+1,0);
	dp[0] = 1;
	rep(i,n){
		vector<int> temp(k+1,0);
		repr(j,k+1){
			int l = j+1;
			int r = j+min(k-j,v[i]);
			if(l <= r){
				add(temp[l],dp[j]);
				if(r+1 <= k)sub(temp[r+1],dp[j]);
			}
			// repa(m,l,r+1){
			// 	add(dp[m],dp[j]);
			// }
		}
		int sum = 0;
		rep(i,k+1){
			add(sum,temp[i]);
			add(dp[i],sum);
		}
	}
	cout<<dp[k];
	return 0;
}

Measured memory_bytes: 1024
n = int(input())
l = []
for i in range(n):
    x,y = map(int,input().split())
    l.append([x,y,i])

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]

    def same(self,x,y):
        return self.find(x) == self.find(y)

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
s = set()
u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if not u.same(i[1],i[2]):
        u.union(i[1],i[2])
        s.add(i[1])
        s.add(i[2])
        count += i[0]
print(count)


Measured memory_bytes: 59060
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.*;
import java.math.RoundingMode;


public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        BigDecimal a = sc.nextBigDecimal();
        BigDecimal b = sc.nextBigDecimal();

        System.out.println(b.multiply(a).setScale(0, RoundingMode.DOWN).longValue());

        // out.println("Hello World");
        out.flush();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 37600
#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

int main(){
    int X, N, p;
    cin >> X >> N;
    if(N == 0){
        cout << X << endl;
        return 0;
    }
    set<int> table;
    for(int i = 0; i < N; ++i){
        cin >> p;
        table.insert(p);
    }

    int index = 1000, absv = 1000;
    for(int i = -1; i <= 101; ++i){
        if(table.find(i) != table.end()) continue;
        if(absv > abs(i-X)){
            absv = abs(i-X);
            index = i;
        }
    }
    cout << index << endl;

    return 0;
}

Measured memory_bytes: 3640
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/30 09:38:34 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

// TOP
void	Main()
{
	int	n;
	cin >> n;
	vector<int>	V(n);
	vector<int>	dp(n, INT_MAX);
	dp.at(0) = 0;
	rep(i, n)
		cin >> V.at(i);
	rep2(i, 1, n)
	{
		rep2(j, max(0, i - 2), i)
			dp.at(i) = min(dp.at(i), dp.at(j) + abs(V.at(i) - V.at(j)));
	}
	cout << dp.back() << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 1024
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

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

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

int main()
{
    double W, H, x, y;
    cin >> W >> H >> x >> y;

    int ans;
    if (H == 2*y && W == 2*x) ans = 1;
    else ans = 0;
    cout << H*W/2.0 << " " << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<list>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1000000007;
const int INF = 1 << 28;
const double EPS = 1e-10;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

int n;
ull k;
ull a[100005];

int main()
{
	cin >> n >> k;
	ull ret = 0;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		ret += a[i];
	}
	if (k == 0) {
		cout << ret << endl;
		return 0;
	}

	int con;
	ull mask = 1;
	ull ans = 0;

	for (int i = 0;i < 42;i++) {
		con = 0;
		for (int j = 0;j < n;j++) {
			if ( (a[j] & mask) > 0) con++;
		}
		if (2 * con < n ) {
			ans = ans | mask;
		}
		mask = mask << 1;
	}

	while (k < ans) {
		//cout << k << "-" << ans << endl;
		mask = 1LL << 45;
		while (mask) {
			//cout << mask << endl;
			if ( ((k & mask) == 0) && ((ans & mask) > 0) ) {
				ans = ans - mask;
				break;
			}
			mask = mask >> 1;
		}
	}
	
	ret = 0;
	for (int i = 0;i < n;i++) {
		ret += ans ^ a[i];
	}
	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 1024
import sys
from string import ascii_lowercase

lim = 10**5 + 100
mod = 10**9 + 7


def main():
    n, m = map(int, input().split())

    f = [1]*(lim + 1)
    for i in range(2, lim + 1):
        f[i] = (i * f[i-1]) % mod
    rf = [1]*(lim + 1)
    rf[lim] = pow(f[lim], mod - 2, mod)
    for i in range(lim - 1, 1, -1):
        rf[i] = ((i+1) * rf[i+1]) % mod

    def comb(n, k):
        return f[n] * rf[k] * rf[n-k] % mod

    divs = factorize(m)

    ans = 1

    for p, c in divs:
        ans *= comb(n - 1 + c, n - 1)
        ans %= mod

    print(ans)


def factorize(n):
    res = []
    for i in range(2, n + 1):
        if i*i > n:
            break
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        res.append((i, cnt))

    if n > 1:
        res.append((n, 1))

    return res


if __name__ == '__main__':
    main()


Measured memory_bytes: 12132
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#include <string>
#include <cmath>
#include <set>
#include <map>
#define Rep(i, x, y) for (int i = x; i <= y; i ++)
#define Dwn(i, x, y) for (int i = x; i >= y; i --)
#define RepE(i, x) for (int i = pos[x]; i; i = g[i].nex)
#define ev g[i].y
#define eps 1e-10
#define u t[x]
#define Lc t[ x << 1 ]
#define Rc t[ x << 1 | 1 ]
#define flc x << 1, l, mid
#define frc x << 1 | 1, mid + 1, r
#define inf (1ll << 60)
using namespace std;
typedef long long ll;
typedef double db;
const int N = 200010;
int n, m, a[N], q;
ll t[N * 4][2], f[N], res, ans = inf, dt;
void qry(int x, int l, int r) {
//	cout <<x<<" "<<l<<" "<<r<<" "<<u[0] + q<<" "<<u[1] - q<<endl;
	if (r <= q) { res = min(res, u[0] + q); return ; }
	if (q <= l) { res = min(res, u[1] - q); return ; }
	int mid = (l + r) >> 1;
	qry(flc), qry(frc);
}
void modify(int x, int l, int r) {
	if (l == r) {
		u[0] = min(u[0], f[l] - l);
		u[1] = min(u[1], f[l] + l);
		// cout << l<<" "<<u[1]<<endl;
		return ;
	}
	int mid = (l + r) >> 1;
	if (q <= mid) modify(flc);
	else modify(frc);
	u[0] = min(Lc[0], Rc[0]);
	u[1] = min(Lc[1], Rc[1]);
}
void build(int x, int l, int r) {
	u[0] = u[1] = inf;
	if (l == r) return ;
	int mid = (l + r) >> 1;
	build(flc), build(frc);
}
void get(int x, int l, int r) {
	if (l == r) {
		ans = min(ans, u[0] + l);
		return ;
	}
	int mid = (l + r) >> 1;
	get(flc), get(frc);
}
int main()
{
	scanf ("%d%d%d%d", &n, &m, &a[0], &a[1]);
	Rep(i, 1, n) f[i] = inf;
	f[ a[0] ] = 0;
	build(1, 1, n);
	q = a[0];
	modify(1, 1, n);
	Rep(i, 2, m + 1) {
		scanf ("%d", &q);
		a[i] = q;
		res = inf;
		qry(1, 1, n);
		q = a[i - 1];
		res += dt;
		// cout << res<<endl;
		dt += abs(a[i] - a[i - 1]);
		f[q] = min(f[q], res - dt);
		modify(1, 1, n);
	}
	get(1, 1, n);
	printf("%lld\n", ans + dt);

	return 0;
}

Measured memory_bytes: 13056
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <list>
#include <sys/timeb.h>
#include <fstream>
#include <set>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	/*
	int d, n;
	cin >> d >> n;
	if (d == 0) {
		if (n == 100) {
			cout << 101;
		}
		else {
			cout << n << endl;
		}

	}
	else if(d == 1){
		if (n == 100) {
			cout << 10100 << endl;
		}
		else {
			cout << n * 100 << endl;
		}

	}
	else {
		if (n == 100) {
			cout << 1010000 << endl;
		}
		cout << n * 10000 << endl;
	}
	*/
	int n;
	cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];

	int ans = 0;
	rep(i, n) {
		int t = 0;
		while ((a[i] % 2) == 0) {
			t++;
			a[i] /= 2;
		}
		ans += t;
	}

	cout << ans << endl;
	return 0;
}



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

using namespace std;

int main(){
  int N;
  cin >> N;
  int X[N+1],Y[N+1];
  int m=N/2,i;
  for (i=1;i<=N;++i) {
    cin >> X[i];
    Y[i]=X[i];
  }
  sort(Y+1, Y+(N+1));
  //Y[m]かY[m+1]
  for (i=1;i<=N;++i) {
    if (X[i]<=Y[m]) {
      cout << Y[m+1] << endl;
    } else {
      cout << Y[m] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main()
{
    int N;
    vector<int> a;

    cin >> N;

    int sum = 0;
    a = vector<int>(N);
    for (int i = 0; i < N; i++){
        cin >> a[i];
        sum += a[i];
    }

    double average = (double)sum / N;

    double min_dist = abs(average - a[0]);
    int min_i = 0;
    for (int i = 1; i < N; i++){
        double dist = abs(average - a[i]);

        if (dist < min_dist){
            min_dist = dist;
            min_i = i;
        }
    }

    cout << min_i << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n,a,b,count1=0,count2=0,count3=0;
	cin >> n >> a >> b;
	vector<int> p(n);
	for(int i=0;i<n;i++){
		cin >> p[i];
		if(p[i] <= a)count1++;
		else if(p[i] >= a+1 && p[i] <= b)
			count2++;
		else if(p[i] >= b+1)count3++;
	}
	
	cout << min(count1,min(count2,count3)) << endl;
	return 0;
}

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

int main() {
  int n, q;
  std::cin >> n >> q;

  std::vector<std::vector<int>> tree(n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    std::cin >> a >> b;
    tree[a - 1].push_back(b - 1);
    tree[b - 1].push_back(a - 1);
  }

  std::vector<int> counter(n, 0);
  for (int i = 0; i < q; ++i) {
    int p, x;
    std::cin >> p >> x;
    counter[p - 1] += x;
  }

  std::queue<int> parents;
  parents.push(0);

  std::vector<bool> is_searched(n, false);

  while (!parents.empty()) {
    const auto parent = parents.front();
    parents.pop();

    is_searched[parent] = true;
    const auto c = counter[parent];
    const auto& children = tree[parent];

    for (const auto node : children) {
      if (!is_searched[node]) {
        counter[node] += c;
        parents.push(node);
      }
    }
  }

  for (auto&& c : counter) std::cout << c << ' ';
  std::cout << std::flush;
}

Measured memory_bytes: 15604
H, W, K = map(int, input().split())
S = [[0] * (W + 2)] + [[0] + [int(a) for a in input()] + [0] for _ in range(H)]
for i in range(1, H + 1):
    for j in range(1, W + 2):
        S[i][j] += S[i][j-1]
for i in range(1, H + 1):
    for j in range(1, W + 2):
        S[i][j] += S[i-1][j]

mi = 1 << 20
for i in range(1 << H - 1):
    X = []
    l = 0
    ii = i
    pc = 0
    while ii:
        a = ii & -ii
        ii -= a
        r = a.bit_length()
        X.append((l, r))
        l = r
        pc += 1
    X.append((l, H))
    Y = [0] * (pc + 1)
    l = 0
    cnt = 0
    r = l + 1
    ngflg = 0
    while r <= W + 1:
        for a, b in X:
            if S[b][r] - S[b][l] - S[a][r] + S[a][l] > K:
                if r == l + 1:
                    ngflg = 1
                    break
                l = r - 1
                cnt += 1
                break
        else:
            r += 1
        if ngflg: break
    if ngflg: continue
    mi = min(mi, pc + cnt)

print(mi)

Measured memory_bytes: 42220
N = int(input())
h = list(map(int, input().split()))
For = abs(h[1] - h[0])
Back = 0
for i in range(2, N):
  For, Back = min(Back + abs(h[i]-h[i-2]), For + abs(h[i]-h[i-1])), For
print(For)

Measured memory_bytes: 13980
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type Row []string

type Data []Row

func main() {
	nextReader = newScanner()
	A := nextInt()
	B := nextInt()
	C := nextInt()
	D := nextInt()
	a := C / B
	if C%B != 0 {
		a += 1
	}
	b := A / D
	if A%D != 0 {
		b += 1
	}
	// fmt.Println(a, b)
	if a <= b {
		fmt.Printf("Yes")
		return
	}
	fmt.Printf("No")
}

var nextReader func() string

func newScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	// r.Split(bufio.ScanLines)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func CustomScan(data []byte, atEOF bool) (advance int, token []byte, err error) {
	for i := 0; i < len(data); i++ {
		if data[i] == ' ' {
			return i + 1, data[:i], nil
		}
	}
	fmt.Println(data)
	return 0, data, bufio.ErrFinalToken
}

func nextStrings() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	// r.Split(bufio.ScanWords)
	r.Split(CustomScan)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextInt64s(n int) []int64 {
	r := make([]int64, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt64()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}


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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

int main(){
    ll N;
    cin >> N;
    
    int cnt = 1;
    while(1) {
        N -= pow(26,cnt);
        if (N<=0) {
            N+= pow(26,cnt);
            break;
        }
        cnt ++;
    }
    vector<int> A;
    N--;
    rep(i,cnt) {
        int tmp = N%26;
        A.push_back(tmp);
        N /= 26;
    }

    rep(i,cnt) {
        int idx = A[A.size()-i-1];
        char ans = 'a' + idx;

        cout << ans;
        }

    cout << endl;

} 


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

int main() {
  int N;
  cin >> N;
  
  string S;
  cin >> S;
  
  int an = 1;
  
  for(int i=0;i<S.size()-1;)
  {
	if(S[i]==S[i+1])
    {
        S.erase(S.begin()+i+1);
    }
    else 
    {
      an ++;
      i ++;
    }
  }
  
  cout << an << endl;
  
}


Measured memory_bytes: 640
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;

int main(){
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2];
    if((a[0] < a[2] && a[2] < a[1])||(a[1] < a[2] && a[2] < a[0])){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
a = Hash.new
n.times do |i|
  x = gets.chomp.to_i
  a[x] = i % 2
end

ans = 0
a.keys.sort.each_with_index do |x, i|
  ans += 1 if a[x] != i % 2
end
puts ans / 2


Measured memory_bytes: 10872
n,m = map(int,raw_input().split())
mat = []
for k in range(n):
    mat.append(map(int,raw_input().split()))
b = []
for j in range(m):
    b.append(int(raw_input()))

for k in range(n):
    ans = 0
    for j in range(m):
        ans += mat[k][j]*b[j]
    print ans

Measured memory_bytes: 4548
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

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

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
class lazy_segment_tree{
    private:
        static int calc_size(int n){
            int m = 1;
            while(m < n){
                m *= 2;
            }
            return m;
        }

        void eval(int i, int l, int r){
            if(lazy[i] != -1){
                node[i] = lazy[i];
                if(r - l > 1){
                    lazy[i * 2 + 1] = lazy[i];
                    lazy[i * 2 + 2] = lazy[i];
                }
                lazy[i] = -1;
            }
        }

        void update(int s, int t, int x, int i, int l, int r){
            eval(i, l, r);

            if(t <= l || r <= s){
                return ;
            }

            if(s <= l && r <= t){
                lazy[i] = x;
                eval(i, l, r);
                return;
            }

            int m = l + (r - l) / 2;
            update(s, t, x, 2 * i + 1, l, m);
            update(s, t, x, 2 * i + 2, m, r);
            node[i] = f(node[2 * i + 1], node[2 * i + 2]);
        }

        T query(int s, int t, int i, int l, int r){
            eval(i, l, r);

            if(t <= l || r <= s){
                return init;
            }

            if(s <= l && r <= t){
                return node[i];
            }

            int m = l + (r - l) / 2;
            T vl = query(s, t, i * 2 + 1, l, m);
            T vr = query(s, t, i * 2 + 2, m, r);
            return f(vl, vr);
        }

    public:
        int n;
        vector<T> node, lazy;
        T init;
        function<T(T, T)> f;

        lazy_segment_tree(int n, T init, function<T(T, T)> f)
            : n(calc_size(n)), node(calc_size(n) * 2, init) , lazy(calc_size(n) * 2, -1), init(init), f(f) {}

        T query(int s, int t){
            return query(s, t, 0, 0, n);
        }

        void update(int s, int t, int x){
            update(s, t, x, 0, 0, n);
        }
};

signed main(){
    int n, q;
    cin >> n >> q;

    lazy_segment_tree<int> lst(n, (1LL << 31)-1, [](int a, int b){return min(a, b);});

    rep(i, q){
        int que, s, t;
        cin >> que >> s >> t;

        if(que == 0){
            int x;
            cin >> x;
            lst.update(s, t+1, x);
        }else{
            cout << lst.query(s, t+1) << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 7068
n = int(input())
x = list(map(int,input().split()))

ctn = 0
for i in range(0,len(x)):
    if i+2 <= len(x)-1:
        if min(x[i:i+3:2]) <= x[i+1] and x[i+1] <= max(x[i:i+3:2]):
            ctn +=1
print(ctn)

Measured memory_bytes: 3060
N = int(input())
sX = input()

origin_count = sX.count('1')
one_r_count = origin_count -1
zero_r_count = origin_count +1

one_mod = 0
zero_mod =0
for b in sX:
    if one_r_count != 0:
        one_mod = (one_mod * 2 + int(b) )% one_r_count
    zero_mod = (zero_mod * 2  + int(b) )% zero_r_count

f = [0] * 220000
pop = [0]* 220000

for i in range(1,220000):
    pop[i] = pop[i//2] + i % 2
    f[i] = f[i % pop[i]] + 1

onepow = [1] * 220000
zeropow = [1]* 220000

for i in range(1,220000):
    if one_r_count != 0:
        onepow[i] = onepow[i-1] * 2 % one_r_count
    zeropow[i] = zeropow[i-1] * 2 % zero_r_count

for i in range(1,N+1):
    if sX[i-1] == '1':
        if one_r_count != 0:
            Xi_n = one_mod - onepow[N-i]
            Xi_n %= one_r_count
            print(f[Xi_n]+1)
        else:
            print(0)
    if sX[i-1] == '0':
        Xi_n = zero_mod + zeropow[N-i]
        Xi_n %= zero_r_count
        print(f[Xi_n]+1)


Measured memory_bytes: 30212
let cnt = ref 0

let merge a l m r =
  let ai = Array.make (m - l + 1) max_int in
  for i = 0 to m - l - 1 do
    ai.(i) <- a.(l + i)
  done;
  let aj = Array.make (r - m + 1) max_int in
  for i = 0 to r - m - 1 do
    aj.(i) <- a.(m + i)
  done;
  let i = ref 0 in
  let j = ref 0 in
  for k = l to r - 1 do
    incr cnt;
    if ai.(!i) <= aj.(!j) then begin
      a.(k) <- ai.(!i);
      incr i;
    end else begin
      a.(k) <- aj.(!j);
      incr j;
    end
  done

let rec merge_sort a l r =
  if (l + 1) >= r then () else
  let m = (l + r) / 2 in
  merge_sort a l m;
  merge_sort a m r;
  merge a l m r

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> Scanf.scanf "%d " (fun i -> i)) in
  merge_sort a 0 n;
  print_int a.(0);
  for i = 1 to n - 1 do
    print_string " ";
    print_int a.(i);
  done;
  print_newline ();
  print_int !cnt;
  print_newline ()

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

using namespace std ;

#define sz(v) (int)v.size()
#define ll long long
#define all(v)  v.begin() , v.end()
#define rall(v)  v.rbegin() , v.rend()
#define pf push_front
#define pb push_back
#define fast FastInputOutput() ;
#define Clear( container , value ) memset( container , value , sizeof container )
#define PI acos( -1.0 )
#define forn( t , v , be , n ) for( t v = be ; v < n ; v++ )
#define fore( x , j ) for( auto x : j )
#define se second
#define fr first
//#define c_b fflush(stdin);

const ll Long_max = numeric_limits < ll > :: max() ;
const int Int_max = numeric_limits < int > :: max() ;

void File_input( string pathIn ) {
    freopen( pathIn.c_str(), "r", stdin ) ;
}

void File_output( string pathOut ) {
    freopen( pathOut.c_str(), "w", stdout ) ;
}

int msg() {
    srand( time( 0 ) ) ;
    vector < string > st = {
        "Wish everyone high ratings!",
        "Good luck!",
        "Have fun!",
        "Please, read all the problems!",
        "Go Go fight!"
    } ;
    cerr << st[ rand() % sz( st ) ] ;
    return 0 ;
}

void FastInputOutput() {
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}

int n ;

int main() {
  cin >> n ;
  cout << ( 24 - n ) + 24 ;
  return 0 ;
}


Measured memory_bytes: 256
ruijo_memo = [1]
100.times do |i|
  ruijo_memo[i + 1] = ruijo_memo[i] * 2
end
n = gets.to_i
nums = gets.split.map(&:to_i)
memo = Hash.new(0)
nums.each do |num|
  (0...31).each do |i|
    if num[i] == 1
      memo[i] += 1
    end
  end
end
ans = []
nums.each do |num|
  tmp = 0
  (0...31).each do |i|
    if (num[i] == 1 && memo[i].even?) || (num[i] == 0 && memo[i].odd?)
      tmp += ruijo_memo[i]
    end
  end
  ans << tmp
end
puts ans.join(' ')


Measured memory_bytes: 37452
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <limits>
#include <map>
#include <numeric>

#define ll long long
using namespace std;
static ll imin = std::numeric_limits<ll>::min();
static ll imax = std::numeric_limits<ll>::max();
#define rep(i, n) for(int i = 0; (i)<(n); ++(i))
#define rep1(i, n) for(int i = 1; (i)<(n); ++(i))
#define rev_rep(i, n) for(int i = (n) - 1; (i) >= 0; --(i))
#define range(a, i, b) for(int i = (a); (i) < (b); ++(i))
#define dump(x) cout << #x << ":" << x << "\n";
#define all(v) v.begin(), v.end()
#define readl(N) ll N; cin >> N
#define readlv(N, vec) vector<ll> vec(N); rep(i, N){cin >> vec[i];}
#define greater_than [](ll l, ll r){return l > r;}
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair);
template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec);
template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::pair<T1, T2>& pair){
  os << '(' << pair.first << ',' << pair.second << ')';
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::vector<T>& vec){
  std::size_t n = vec.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(ll i = 0; i<n - 1; ++i){
    os << vec[i] << " ";
  }
  os << vec[n - 1];
  os << std::endl;
  return os;
}

template<class T1, class T2>
std::ostream& operator << (std::ostream& os, std::map<T1, T2>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

template<class T>
std::ostream& operator << (std::ostream& os, std::set<T>& mp){
  std::size_t n = mp.size();
  if(n == 0){
    return os;
  }
  os << " ";
  for(auto && x:mp){
    os << x << " ";
  }
  os << std::endl;
  return os;
}

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

#ifndef BOOST_TEST_MAIN
int main(int const argc, char const** argv){
  double x, t;
  cin >> t >> x;
  cout << t/x;
}
#endif


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));


#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl
#define dv(name, value) cerr << (name) << " is " << (value) << endl
#define da(itr, v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl

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

  vector<int> v(N+1, -1);
  REP(x, M) {
    int s, c; cin >> s >> c;

    if(v.at(s) == -1){
      v.at(s) = c;
    } else if(v.at(s) != c) {
      cout << -1 << endl;
      dl(30);
      return 0;
    }
  }

  if (N != 1 && v.at(1) == 0){
    dl(36);
    da(itr, v);
    cout << -1 << endl;
    return 0;
  }

  FOR(i, 1, (ll)v.size()) {
    if (N == 1) {
      if (v.at(i) == -1) v.at(i) = 0;
    } else if (i == 1) {
      if (v.at(i) == -1) v.at(i) = 1;
    } else if(v.at(i) == -1) {
      v.at(i) = 0;
    }
  }

  FOR(i, 1, (ll)v.size()) {
    cout << v.at(i);
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
ll a[100010], mod=1e9+7;
int mem[2010][2010];
ll fct[100010], ifct[100010];
ll dp(ll i, ll j){
    if(i+j==0){
        return 0;
    }
    if(mem[i][j]!=-1){
        return mem[i][j];
    }
    ll res=0;
    if(i>0){
        res+=fct[i-1+j];
        res+=(i)*dp(i-1, j);
        res%=mod;
    }
    if(j>0){
        res+=j*dp(i, j-1);
        res%=mod;
    }
    mem[i][j]=res;
    return res;
}
ll pwr(ll x, ll e){
    if(e==0)
    return 1;
    ll tmp=pwr(x, e/2);
    tmp*=tmp;
    tmp%=mod;
    if(e%2){
        tmp*=x;
        tmp%=mod;
    }
    return tmp;
}
int main(){
    int n;
    fct[0]=1;
    for(ll i=1; i<=100000; ++i){
        fct[i]=fct[i-1]*i;
        fct[i]%=mod;
        ifct[i]=pwr(fct[i], mod-2);
    }
    while(cin>>n){
        ll ans=0;
        for(int i=0; i<n; ++i){
            scanf("%lld",a+i);
        }
        memset(mem, -1, sizeof mem);
        ll tmp1=1, tmp2, tmp=1;
        ans+=(a[1]-a[0])*fct[n-1];
        ans%=mod;
        for(int i=1; i+1<n; ++i){
            tmp=tmp*(i+1)+tmp1;
            tmp%=mod;
            tmp2=tmp*fct[n-1];
            tmp2%=mod;
            tmp2*=ifct[i+1];
            tmp2%=mod;
            // cout<<i<<" "<<dp(i+1, n-2-i)<<" "<<tmp<<" "<<tmp1<<" "<<tmp2<<endl;
            ans+=(a[i+1]-a[i])*tmp2;
            ans%=mod;
            tmp1*=(i+1);
            tmp1%=mod;
        }
        cout<<ans<<endl;
    }
  return 0;
}




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

using ll = long long;
#define f first
#define s second

#ifndef LOCAL
	#define cerr if(0) cerr
#endif

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	unordered_map<string,int> freq;
	while (n--) {
		string s;
		cin >> s;
		freq[s]++;
	}

	cout << "AC x " << freq["AC"] << "\n";
	cout << "WA x " << freq["WA"] << "\n";
	cout << "TLE x " << freq["TLE"] << "\n";
	cout << "RE x " << freq["RE"] << "\n";
}


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

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

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  int N; cin >> N;
  vector<int> a(N); rep(i, N) cin >> a[i];

  vector<ll> que;
  rep(i, N){
    ll tot = 0;
    while (i < N && a[i] != 0) tot += a[i], ++i;
    que.push_back(tot);
  }
  ll ans = 0;
  rep(i, que.size()) ans += que[i] / 2;
  cout << ans << endl;
}


Measured memory_bytes: 1784
n, a, b, c = list(map(int, input().split()))
goals = [a, b, c]
bamboos = []
for _ in range(n):
    bamboos.append(int(input()))

def get_best(li, goal):
    bam_mp_lis = {0: (-10, tuple())}
    li.sort()
    for i, v in enumerate(li):
        tmp = bam_mp_lis.copy()
        for bam, (mp, lis) in tmp.items():
            b0 = bam + v
            m0 = mp + 10
            l0 = lis + (i,)
            if b0 not in bam_mp_lis or m0 < bam_mp_lis[b0][0]:
                bam_mp_lis[b0] = (m0, l0)
    del bam_mp_lis[0]
    best = 10 ** 9
    for bam, (mp, lis) in bam_mp_lis.items():
        cost = mp + abs(goal - bam)
        if cost < best:
            best = cost
            beslis = lis
    return best, beslis

ans = 10 ** 9
from itertools import permutations
for junjo in permutations(goals):
    tmp = 0
    bambooo = bamboos.copy()
    for ju in junjo:
        if len(bambooo) == 0:
            tmp = 10 ** 9
            break
        be, beli = get_best(bambooo, ju)
        beli = sorted(beli, reverse=True)
        for beli0 in beli:
            del bambooo[beli0]
        tmp += be
    if tmp < ans:
        ans = tmp

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1000000007;
int n,a,b;
int maxxadd=-2e9-15,minnadd=2e9+15,maxxsub=-2e9-15,minnsub=2e9+15,ans;
inline int read()
{
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++){
		a=read();b=read();
		maxxadd=max(maxxadd,a+b);
		minnadd=min(minnadd,a+b);
		maxxsub=max(maxxsub,a-b);
		minnsub=min(minnsub,a-b);
		ans=max(ans,max(maxxsub-minnsub,maxxadd-minnadd));
	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 3628
def main():
        
    N = int(input())

    S = [input() for _ in range(N)]

    """
    あるA,Bを決めたときに、A+1,B+1と比べると、全ての文字が右下にずれるので、(A,B)と(A+1,B+1)の結果は同じになる
    """
    S2 = [["" for _ in range(N)]  for _ in range(N)]
    cnt = 0
    for a in range(N):
        
        for i in range(N):
            for j in range(N):
                if 0 <= i + a <= N-1:
                    y = i + a
                else:
                    y = (i + a) - N
                S2[y][j] = S[i][j]
        
        flag = True
        for i in range(N):
            if not flag:
                break
            for j in range(N):
                if i == j:
                    continue
                if S2[i][j] != S2[j][i]:
                    flag = False
                    break
        if flag:
            cnt += 1

    print(cnt * N)


if __name__ == "__main__":
    main()

Measured memory_bytes: 134076
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
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;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

#ifndef TEMPLATE_USED
#include "../template/template.hpp"
#endif

template<int m>
struct MInt{
    //static int m;

    ll x;
    MInt(ll x=0):x((x%m+m)%m){}

    MInt operator-()const{return MInt(-x);}
    MInt operator+(const MInt &p)const{return MInt(*this)+=p;}
    MInt operator-(const MInt &p)const{return MInt(*this)-=p;}
    MInt operator*(const MInt &p)const{return MInt(*this)*=p;}
    MInt operator/(const MInt &p)const{return MInt(*this)/=p;}

    MInt &operator+=(const MInt &p){
        if((x+=p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator-=(const MInt &p){
        if((x+=m-p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator*=(const MInt &p){
        (x*=p.x)%=m;
        return *this;
    }
    MInt &operator/=(const MInt &p){
        return *this*=p.inv();
    }

    MInt pow(ll n)const{
        MInt ret(1),mul(x);
        while(n){
            if(n&1)ret*=mul;
            mul*=mul;
            n>>=1;
        }
        return ret;
    }
    MInt inv()const{
        //return pow(m-2);
        int a=x,b=m,u=1,v=0,t;
        while(b){
            t=a/b;
            swap(a-=t*b,b);
            swap(u-=t*v,v);
        }
        return MInt(u);
    }

    friend ostream& operator<<(ostream& os,const MInt& a) {return os<<a.x;}
};
//int MInt::m=0;
using mint=MInt<1000000007>;

void solve(){
    string l;cin>>l;
    ll n=l.size();

    mint ans=0;
    ll cnt=0;
    rep(i,n){
        if(l[i]=='0')continue;
        mint tmp=mint(3).pow(n-1-i);
        tmp*=mint(2).pow(cnt);
        ans+=tmp;
        ++cnt;
    }
    ans+=mint(2).pow(cnt);
    cout<<ans<<endl;
}

Measured memory_bytes: 592
#include<stdio.h>
#include<stdlib.h>
typedef struct{
  int parent;
  int l,r;    // child
}node;
int sibling(int);
int degree(int);
int depth(int);
int height(int);
node *T;
int h_count;
int main(){
  int n, x, y, z, a, i, j;
  scanf("%d",&n);
  T = (node *)malloc(sizeof(node) * n);
  for(i=0; i<n; i++) T[i].parent = -1;
  for(i=0; i<n; i++){
    scanf("%d",&x);
    scanf("%d%d",&T[x].l,&T[x].r);
    T[T[x].l].parent = x;
    T[T[x].r].parent = x;
  }
  for(i=0; i<n; i++){
    h_count = 0;
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
	   i,T[i].parent,sibling(i),degree(i),depth(i),height(i));
    if(T[i].parent == -1) printf("root\n");
    else if(T[i].l == -1 && T[i].r == -1) printf("leaf\n");
    else printf("internal node\n");
  }
  free(T);
  return 0;
}

int sibling(int x){
  if(T[x].parent == -1) return -1;
  if(T[T[x].parent].l == x) return (T[T[x].parent].r);
  else return (T[T[x].parent].l);
}

int degree(int x){
  int count=2;
  if(T[x].l == -1) count--;
  if(T[x].r == -1) count--;
  return count;
}

int depth(int x){
  int d_count = 0;
  while(T[x].parent != -1){
    x = T[x].parent;
    d_count++;
  }
  return d_count;
}

int height(int x){
  int y,z;
  if(T[x].l != -1) y = height(T[x].l) + 1;
  else y = 0;
  if(T[x].r != -1) z = height(T[x].r) + 1;
  else z = 0;
  if(y < z) return z;
  else return y;
}

Measured memory_bytes: 612
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
    constexpr ll mod = 1e9 + 7;

    int n; cin >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];
    
    map<int, int> mp;
    
    ll ans = 1LL;
    REP(i, n) {
        if (a[i] == 0) {
            ans *= (3 - mp[0]);
        } else {
            ans *= (mp[a[i] - 1] - mp[a[i]]);
        }

        ans %= mod;
        mp[a[i]]++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5376
import * as fs from 'fs';

namespace AtCoder.abc095 {
    class ProgramB {
        args: string[];

        // 3 1000
        // 120
        // 100
        // 140
        //
        // 6
        constructor(args: string[]) {
            this.args = args;
        }

        main() {
            const _args = this.args;
            let [n, x]: number[] = _args[0].split(' ').map(Number);
            _args.shift();
            const m: number[] = _args.map(Number);
            m.sort((a: number, b: number) => a - b);

            let ans: number = m.reduce((acc: number, cuu: number) => {
                if (x >= cuu) {
                    acc++;
                    x -= cuu;
                }
                return acc;
            }, 0);

            while (x > 0 && x >= m[0]) {
                ans++;
                x -= m[0];
            }

            console.log(ans);
        }
    }

    const args: string[] = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    new ProgramB(args).main();
}

Measured memory_bytes: 7500
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a;
    cin>>a;
    int ar[a],i,j;
     for(i=0;i<a;i++)
        cin>>ar[i];
    for(i=0;i<a;i++)
    {
        for(j=0;j<a-1;j++)
        {
            if(ar[j]>ar[j+1])
            swap(ar[j],ar[j+1]);
        }
    }
    float d1,d;
    d1=ar[0];
    for(i=1;i<a;i++)
     {

         d=d1+ar[i];
         d1=d/2;

     }
     cout<<d1<<endl;

}




Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  lint a,b,x;
  cin>>a>>b>>x;
  if(a==0)cout<<b/x+1<<endl;
  else cout<<(b/x-(a-1)/x)<<endl;
  return 0;
}


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

int main() {
    long long a[100000];
    long long sum=1;
    int n;
    int i;
    scanf("%d", &n);
    for (i=0;i<n;i++) {
        scanf("%lld", &a[i]);
        if (a[i]==0) {
            printf("0\n");
            return 0;
        }
    }
    for (i=0;i<n;i++) {
        if (a[i]<=1000000000000000000/sum) {
            sum*=a[i];
        }
        else {
            printf("-1\n");
            return 0;
        }
    }
    printf("%lld\n", sum);
    return 0;
}

Measured memory_bytes: 2440
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Linq.Enumerable;
using static System.Math;

class Program
{
    static void Main()
    {
        var (H, W) = ReadLine().Split(' ').Select(int.Parse).ToArray();
        var s = Range(0, H).Select(i => ReadLine()).ToArray();

        var ans = "Yes";
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                if (s[i][j] == '.')
                    continue;

                if ((0 <= i - 1 && s[i - 1][j] == '#') ||
                    (0 <= j - 1 && s[i][j - 1] == '#') ||
                    (i + 1 < H && s[i + 1][j] == '#') ||
                    (j + 1 < W && s[i][j + 1] == '#'))
                    continue;
                else
                {
                    ans = "No";
                    break;
                }
            }
        }

        WriteLine(ans);
    }
}

static class ArrayDeconstructExtensions
{
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2) => (i1, i2) = (a[0], a[1]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3) => (i1, i2, i3) = (a[0], a[1], a[2]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4) => (i1, i2, i3, i4) = (a[0], a[1], a[2], a[3]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4, out T i5) => (i1, i2, i3, i4, i5) = (a[0], a[1], a[2], a[3], a[4]);
}


Measured memory_bytes: 28344