akhauriyash/Code-Regression huggingface dataset:
code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
cpdef inline vector[int] readInt(int n) nogil:
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline void printLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void printLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import readInt, FenwickTree, printLongN

n, q = readInt(2)
bit = FenwickTree(n)
*map(bit.add, range(n), readInt(n)),
res = []
for i in range(q):
    t, u, v = readInt(3)
    if t: res.append(bit.sum(u, v))
    else: bit.add(u, v)
printLongN(res, len(res))

Measured memory_bytes: 63156
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    REP(i, 3) REP(j, 3) {
        char c; cin >> c;
        if (i == j) cout << c;
    }

    cout << endl;
    
}


Measured memory_bytes: 3556
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#define	MOD  1000000007;
#define PI = 3.14159265358979323846;
using namespace std;

int main()
{
	int X, Y, Z;
	cin >> X >> Y >> Z;

	cout << (X - Z) / (Z + Y) << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <vector>
int main(){
  int m,n;
  while(true){
    cin >> m;
    if(m == 0)break;
    cin >> n;
    vector<int> d(n*2);
    vector<vector<int> >p(n*3,vector<int>(n*3,0));
    for(int i = 0; i < 2*n; i++)d[i] = 0;
    for(int i = 1; i <= n; i++)cin >> d[i];
    
    for(int i = 0; i <= n; i++){
      for(int j = 1; j <= m; j++){
	int pp= i+j+d[i+j];
	if(pp < 0)pp = 0;
	if(pp > n+1)pp = n+1;
	p[i][pp] = 1;
      }
    }
    
 
    for(int j = 0; j <= n+1; j++){
      for(int i = 0; i <= n+1; i++){
	for(int k = 0; k <= n+1; k++){
	  if(p[j][i]&&p[i][k]) p[j][k] = 1;
	}
      }
    }

      
    int ans = true;
    for(int i = 0;i < n+1; i++){
      if(p[0][i]==1&&p[i][n+1] == 0)ans = false;
    }
    if(ans)cout << "OK" << endl;
    else cout << "NG" << endl;
  }
}



Measured memory_bytes: 4896
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<vector<P> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

//Warshall-floyd
ll dp[310][310];//dpテーブルには辺がないところにはINF、i==jには０を入れておく
void warshallfloyd(ll n){
    rep(k,n){
        rep(i,n){
            rep(j,n){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
            }
        }
    }
}

//入力
ll n,m,r;
vector<ll>machi;



int main(){
    cin >> n >> m >> r;
    machi.resize(r);
    rep(i,r){
        cin>>machi[i];
        machi[i]--;
    }
    rep(i,n)rep(j,n)dp[i][j]=INF;
    rep(i,n)dp[i][i]=0;
    rep(i,m){
        ll a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        dp[a][b]=c;
        dp[b][a]=c;
    }
    warshallfloyd(n);//ここまで全点間最短距離を求める
    ll ans = INF;
    vector<ll>one_case;
    rep(i,r){
        one_case.emplace_back(i);
    }
    do{
        ll res = 0;
        rep(i,r-1){
            ll now = one_case[i];
            ll nx = one_case[i+1];
            ll from = machi[now];
            ll to = machi[nx];
            res += dp[from][to];
        }
        chmin(ans,res);
    } while (next_permutation(one_case.begin(),one_case.end()));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;

int i;
string s;

int main() {
cin >> s;
for (i=0;i<s.size();i++) if ((i % 2 == 0 && s[i] != 'h') || (i % 2 == 1 && s[i] != 'i')) {
	printf("No\n");
	return 0;
}
if (s.size() % 2 == 1) printf("No\n"); else printf("Yes\n");
return 0;
}

Measured memory_bytes: 256
N = gets.to_i
A = gets.split.map(&:to_i)
A.unshift nil

hash = Hash.new { |h, k| h[k] = 0 }
res = 0
1.upto(N) do |idx|
  res += hash[idx - A[idx]]
  hash[A[idx] + idx] += 1
end

puts res


Measured memory_bytes: 46976
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>	

using namespace std;

int main() {
	int X, A;
	cin >> X >> A;
	if (X < A) {
		cout << 0 << endl;
	}
	else if (A <= X) {
		cout << 10 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=(ll)(1e9+7);
ll run();

int main() {
#ifdef home
    freopen("i", "r", stdin);
    freopen("d", "w", stderr);
#endif
    cout.precision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    run();
    return 0;
}
const ll inf = (1e9+5);
void max_self(ll &a, ll b) {
    a = max(a, b);
}
void min_self(ll &a, ll b) {
    a = min(a, b);
}
void mul(ll &a, ll b) {
    a = (a * b) % mod;
}
void add_self(ll &a, ll b){
    a+=b;
    if(a>=mod)
        a-=mod;
}
ll gcd(ll a, ll b){
    return b?gcd(b,a%b):a;
}


ll run() {
    int n, m;
    cin >> n >> m;
    vector<int> adj[n + 1];
    int ind[n + 1] = {0};
    int dp[n + 1] = {0};

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        ind[y]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!ind[i])
            q.push(i);
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y: adj[x]) {
            ind[y]--;
            if (!ind[y])
                q.push(y);

            dp[y] = max(dp[y], dp[x] + 1);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);

    cout << ans;


    return 0;
}















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

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

const long long MOD = 1000000007;

bool check(string s) {
  char prev = s[0];
  bool f = true;
  for(auto c : s)
    f = f and c==prev;
  return f;
}

int main(){
  string s;
  cin>>s;
  int a = 0;
  int n = s.size();
  int ans = 1001001001;
  vector<int> v(26,0);
  for(auto c : s)
    v[c-'a']++;
  rep(i,26) {
    if(v[i]==0) continue;
    string t = s;
    int cnt = 0;
    while(!check(t)) {
      string tmp = "";
      for(int j=0; j+1<t.size(); j++) {
	if((int)t[j+1]==('a'+i))
	  tmp.push_back(t[j+1]);
	else
	  tmp.push_back(t[j]);
      }
      t = tmp;
      cnt++;
    }
    ans = min(ans, cnt);
  }
  std::cout << ans << std::endl;
  return 0;
}


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

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

    if(a%3 == 0 || b%3 == 0 || (a + b)%3 == 0){
        cout << "Possible" << endl;
    }
    /*
    else if(c%3 == 0){
        cout << "Yes" << endl;
    }
    */
    else{
        cout << "Impossible" << endl;
    }
}

Measured memory_bytes: 256
def main():
    n = int(input())
    h = list(map(int,input().split()))

    h = list(reversed(h))
    flag = True

    for i in range(1,len(h)):
        if h[i] - h[i-1] > 1:
            flag = False
        elif h[i] - h[i-1] == 1:
            h[i] -= 1
        
    if flag:
        print('Yes')
    else:
        print('No')

main()

Measured memory_bytes: 14396
s = input()

len_s = len(s)
if len_s == 1:
  print(0)
else:
  l = len_s // 2
  top, end = s[0:l], s[::-1][0:l]
  print(sum([(0 if t == e else 1) for t, e in zip(top, end)]))


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

int main()
{
    int o=0,z=0;
   string s;
   cin>>s;
   int count=0;
   for(int i=1;i<s.size();i++)
   {
       if(s[i]==s[i-1])
       {
           if(s[i]=='1')
           s[i]='0';
           else
           s[i]='1';
           count++;
       }
   }
  
       cout<<count;
       
 
   
}


Measured memory_bytes: 512
class A {
    static func solve() {
        let xs = readLine()!.split(separator: " ")
        if xs[0] != "1" {
            print("1")
        } else if xs[1] != "2" {
            print("2")
        } else if xs[2] != "3" {
            print("3")
        } else if xs[3] != "4" {
            print("4")
        } else if xs[4] != "5" {
            print("5")
        }
    }
}

A.solve()


Measured memory_bytes: 7672
#include <iostream>

using namespace std;

int main(void) {

  int N = 0;
  cin >> N;
  int sum = 0;
  int temp_l, temp_r;
  for(int i = 0; i < N; i++) {
    cin >> temp_l >> temp_r;
    sum += temp_r - temp_l + 1;
  }
  cout << sum;
  return 0;
}

Measured memory_bytes: 256
import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l][::-1])), r - l, xs[r:]

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

ans *= 2 ** n0
ans += 2 ** n0 - 1

print(ans)

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)

const int MAX = 1e5+10;

int N, K, A[MAX];
vi child[MAX];

ii dnf(int n) {
    if (child[n].size() == 0) return ii(1, 0);
    ll d = 0, r = 0;

    FORE (c, child[n]) {
        ii res = dnf(c);
        if (res.first == K && n != 0) {
            r++;
            res.first = 0;
        }
        CHMAX(d, res.first);
        r += res.second; 
    }
    return ii(d+1, r);
}

ll solve() {
    FOR (i, 1, N) child[A[i]].push_back(i);
    return dnf(0).second + (A[0] > 0);
}

int main() {
    cin >> N >> K;
    REP (i, N) {
        cin >> A[i];
        A[i]--;
    }
    cout << solve() << endl;
}

Measured memory_bytes: 10752
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;
int main() {
	int i;
	int j = 1;
	int N, D, X;
	int A[200];
	int S[200] = {};
	int sum=0;
	cin >> N;
	cin >> D >> X;
	for (i = 0; i < N; ++i) {
		cin >> A[i];
	}
	//cout << endl;
	for (i = 0; i < N; ++i) {
		while (S[i] < D) {
			S[i] = A[i] * j + 1;
			if (S[i] <= D) {
				//cout << S[i] << endl;
				++sum;
			}


			++j;
		}
		//cout << endl;
		j = 1;
	}
	cout << sum+X+N << endl;


}

Measured memory_bytes: 256
def solve():
    from sys import stdin
    f_i = stdin
    
    n = f_i.readline()
    A = f_i.readline().split()
    q = int(f_i.readline())
    
    ans = []
    for i in range(q):
        b, e, k = f_i.readline().split()
        ans.append(str(A[int(b):int(e)].count(k)))
    
    print('\n'.join(ans))

solve()


Measured memory_bytes: 5732
#include <iostream>
using namespace std;
int nedan(int a,int i,int price){
    int E;
    if (a%i!=0){
        E=((int)((a/i)+1))*price;
    }else{
        E=(int)(a/i)*price;
    }
    return E;
}
int main(){
    int N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;
    if(nedan(N,A,B)<nedan(N,C,D)){
        cout<<nedan(N,A,B)<<endl;
    }else{
        cout<<nedan(N,C,D)<<endl;
    }
}


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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

k=int(input())

from queue import Queue
que=Queue()
for i in range(1,10):
    que.put(str(i))
cnt=0
while True:
    a=que.get()
    cnt+=1
    #print(a)
    if cnt==k:
        print(a)
        sys.exit()
    if a[-1]=="0":
        que.put(a+"0")
        que.put(a+"1")
    elif a[-1]=="9":
        que.put(a+"8")
        que.put(a+"9")
    else:
        #ac=int(a[-1])
        que.put(a+chr(ord(a[-1])-1))
        que.put(a+a[-1])
        que.put(a+chr(ord(a[-1])+1))
    

Measured memory_bytes: 22892
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;

#define MAX 256

int f(int x){
	if (x == 2)return 1;
	if (x % 2 == 0)return 0;
	for (int i = 3; i <= (int)sqrt(x); i += 2){
		if (x%i == 0)return 0;
	}
	return 1;
}

int main(void){

	int a;
	scanf("%d", &a);
	int count = 0, b;

	for (int i = 0; i < a; i++){
		scanf("%d", &b);
		count += f(b);
	}

	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 3180
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll INF=1e18;
#define PI 3.14159265358979323846
const int MAX = 510000;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

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


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

    int K;
    cin >> K;

    string S;
    cin >> S;

    if (S.length() <= K) {
        cout << S << '\n';
    } else {
        cout << S.substr(0, K) << "..." << '\n';
    }

    return 0;
}

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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int A[n][m];
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			cin >> A[i][j];
			--A[i][j];
		}
	}

	int ans = n;
	int gone[m];
	int nxt[n];
	int cnt[m];
	memset(nxt, 0, sizeof nxt);
	memset(gone, 0, sizeof gone);

	for(int i = 0; i < m; ++i){
		memset(cnt, 0, sizeof cnt);
		int mxcnt = 0;
		int mxit = 0;

		for(int j = 0; j < n; ++j){
			while(gone[A[j][nxt[j]]] == 1) nxt[j]++;
			if(++cnt[A[j][nxt[j]]] > mxcnt) {
				mxcnt = cnt[A[j][nxt[j]]];
				mxit = A[j][nxt[j]];
			}
		}

		ans = min(mxcnt, ans);
		gone[mxit] = 1;
	}
	cout << ans << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int nPr(int n, int r) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++)
		sum *= i;
	return sum;
}
//int nCr(int n, int r)
int nCr2(int n, int r) {
	return FACT(n) / (FACT(r) * FACT(n - r));
}
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
inline bool PRIMEOR (int x) {
	if (x ==1)
		return false;
	if (x == 2)
		return true;
	if (x%2==0)
		return false;
	double sqrtx = sqrt(x);
	for (int i = 3; i <= sqrtx; i += 2) {
		if (x % i == 0)
			return false;
	}
	return true;
}

using namespace std;
#pragma endregion
signed main() {
	int A, B, M, p, q, r;
	cin >> A >> B >> M;
	vector <int> a(A), b(B), x(M);
	rep(i, A)
		cin >> a[i];
	rep(i, B)
		cin >> b[i];
	rep(i, M) {
		cin >> p >> q >> r;
		x[i] = a[p-1] + b[q-1] - r;
	}
	sort(ALL(a));
	sort(ALL(b));
	sort(ALL(x));
	cout << min(a[0] + b[0], x[0]);
}

Measured memory_bytes: 2560
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)

    val k = sc.nextInt()
    val x = sc.nextInt()
    println(if (500 * k >= x) "Yes" else "No")

}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}





Measured memory_bytes: 31268
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = long long;
using ldb = long double;
using pa = pair < ll, ll >;
using vec = vector < ll >;
 
template < typename T > using index_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
template < typename T > using MinPriorityQueue = priority_queue < T, vector < T >, greater < T > >;

#define pb push_back
#define po pop_back
#define mp make_pair
#define mt make_tuple
#define F  first
#define S  second
#define f(i,x,n) for(ll i=x;i<n;i++) 
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))
#define all(c) c.begin(),c.end()
#define str string
#define edl "\n"
#define add insert
#define cot continue
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


const int MOD = 1e9 + 7, INF = INT_MAX, N = 1e5 + 10;
const double PI = acos(-1);
const ll LINF = LLONG_MAX;

int main() 
{

    fast();
      
    // #ifndef ONLINE_JUDGE
    //         freopen("input.txt", "r", stdin);
    //         freopen("output.txt","w",stdout);
    // #endif
    cout<<setprecision(5)<<fixed;
    ll n;
    cin>>n;
    vector<ldb>q(n);
    ldb s=0;
    f(i,0,n)
    {
      cin>>q[i];
      
    }
    sort(all(q));
    
    f(i,1,n)
    {
      q[i]=(q[i]+q[i-1])*1.0/2;
    }
    // f(i,0,n)
    // {
    //   cout<<q[i]<<edl;
    // }
    cout<<q[n-1];



  

    cerr << "Time taken: " << int((clock() * 1000.) / CLOCKS_PER_SEC) << "ms\n";
    return 0;
}


Measured memory_bytes: 256
import numpy as np

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i, val in enumerate(h):
    if i > 0:
        p = max(i-k, 0)
        dp[i] = min(j + abs(l - val) for j, l in zip(dp[p:i], h[p:i]))

print(dp[-1])

Measured memory_bytes: 23200
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
#include <tuple>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rep1(i, n) for(int i=1; i<=n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
#define countof(array) (sizeof(array) / sizeof(array[0]))
typedef long long ll;

#define MAX_N 200000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

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

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

string as = {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"};
string ab = {"abcdefghijklmnopqrstuvwxyz"};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

void yes() {
  cout << "Yes" << endl;
}

void no() {
  cout << "No" << endl;
}

void print_array(int array[], int len) {

  for(int i=0; i<len; ++i) {
    cout << array[i] << endl;
  }

}

ll absolute(ll x) {
  return (x<0)? (-1)*x : x;
}

//g++ AtCoder.cpp -o AtCoder
//AtCoder

//--------------------------
int main() {

  string s, t;
  cin >> s >> t;
  cout << t+s << endl;

  return 0;
}


Measured memory_bytes: 256
//Depth First Search
#include <stdio.h>
int Adj[101][101],n,discover[101],finish[101],time;
char color[101];//'w'->white  'g'->gray  'b'->brack

void Dfs_initialization(){
  int i;
  for(i=1;i<=n;i++)
    color[i]='w';
  time=0;
}

void Dfs_search(int element){
  int i=1;
  color[element]='g';
  discover[element]=++time;

  while(i<=n){
    if(Adj[element][i]==0){
      i++;
      continue;
    }
    if(color[i]=='w')
      Dfs_search(i);

    i++;
  }

  color[element]='b';
  finish[element]=++time;
}

void Dfs_print(){
  int i;
  for(i=1;i<=n;i++)
    printf("%d %d %d\n",i,discover[i],finish[i]);
}

void Dfs_set(){
  int i;
  Dfs_initialization();

  for(i=1;i<=n;i++)
    if(color[i]=='w')Dfs_search(i);

  Dfs_print();
}


void Initialization(){
  int i,j;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      Adj[i][j]=0;
}

int main(){
  int i,j,element,number,key;
  scanf("%d",&n);
  Initialization();

  for(i=0;i<n;i++){
    scanf("%d%d",&element,&number);
    for(j=0;j<number;j++){
      scanf("%d",&key);
      Adj[element][key]=1;
    }
  }

  Dfs_set();

  return 0;
}



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

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

const int MAX { 100010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

vector<ii> adj[MAX];

void dfs(int u, int p, int color, int& maxc, vector<int>& ans)
{
    int c = 0;

    for (auto q : adj[u])
    {
        auto v = q.first, e = q.second;

        if (v == p)
            continue;

        if (c + 1 == color)
            ++c;

        ans[e] = ++c;

        dfs(v, u, c, maxc, ans);
    }

    maxc = max(maxc, c);
}

pair<int, vector<int>> solve(int N)
{
    int maxc = 0;
    vector<int> ans(N - 1, 0);

    dfs(1, 0, -1, maxc, ans);

    return { maxc, ans };
}

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

    int N;
    cin >> N;

    for (int i = 0; i < N - 1; ++i)
    {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(ii(b, i));
        adj[b].push_back(ii(a, i));
    }

    auto ans = solve(N);

    cout << ans.first << endl;

    for (auto x : ans.second)
        cout << x << '\n';

    return 0;
}


Measured memory_bytes: 10368
n,m = map(int, input().split())
a = list(map(list, [input().split() for i in range(n)]))
b = list(map(int, [input() for i in range(m)]))
for i in range(n):
    ans = 0
    for j in range(m):
        ans += int(a[i][j])*b[j]
    print(ans)


Measured memory_bytes: 6340
N = int(input())
T = [0] * (N+1)
X = [0] * (N+1)
Y = [0] * (N+1)
flag = True
for i in range(1, N+1):
    T[i], X[i], Y[i] = list(map(int, input().split()))
for i in range(N):
    DIST = abs(X[i+1] - X[i]) + abs(Y[i+1]- Y[i])
    DIFF = T[i+1] - T[i]
    if (DIFF - DIST) % 2 == 1 or DIFF < DIST:
        flag = False
if flag:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 11764
#include <bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int MAX_V=200;
#define int long long
signed main(){

  for(;;){
  int v,m,s[3];
  cin>>v>>m;
  for(int i=0;i<3;i++) cin>>s[i];
  s[0]--;
  s[1]--;
  s[2]--;

  if(!v) break;

  int G[MAX_V][MAX_V];

  for(int i=0;i<v;i++) for(int j=0;j<v;j++) G[i][j]=1e9;
  for(int i=0;i<v;i++) G[i][i]=0;

  for(int i=0;i<m;i++){
    int b1,b2,c;
    cin>>b1>>b2>>c;
    b1--,b2--;
    G[b1][b2]=c;
  }

  for(int k=0;k<v;k++)
    for(int i=0;i<v;i++)
      for(int j=0;j<v;j++) G[i][j]=min(G[i][j],G[i][k]+G[k][j]);

  int r=1e9;

  for(int i=0;i<v;i++) r=min(r,G[s[0]][i]+G[i][s[1]]+G[i][s[2]]);

  cout<<r<<endl;

  }
  return 0;

}



Measured memory_bytes: 3132
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;


int main()
{
    int n,k;
    cin>>n>>k;
    bool snack[n+1];
    for(int i=1;i<=n;i++){
        snack[i]=false;
    }
    for(int i=1;i<=k;i++){
        int d;
        cin>>d;
        for(int j=0;j<d;j++){
            int snuke;
            cin>>snuke;
            snack[snuke]=true;
        }
    }
    int ans =0;
    for(int i=1;i<=n;i++){
        if(!snack[i])ans++;
    }
    cout<<ans;
    return 0;
}


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

vector<ll> v0, v1, v2, v3;

int main(){
    ll n, W; cin >> n >> W;
    int e = 1, f = 0, g = 0, h = 0; 
    ll minw, midv;
    cin >> minw >> midv;
    v0.push_back(midv);
    for(int i = 1; i < n; i++){
        ll w, mid;
        cin >> w>> mid;
        if(w == minw){
            e++;
            v0.push_back(mid);
        }else if(w == minw+1){
            f++;
            v1.push_back(mid);
        }else if(w == minw+2){
            g++;
            v2.push_back(mid);
        }else if(w == minw+3){
            h++;
            v3.push_back(mid);
        }
    }
    sort(v0.begin(), v0.end(), greater<ll>());
    sort(v1.begin(), v1.end(), greater<ll>());
    sort(v2.begin(), v2.end(), greater<ll>());
    sort(v3.begin(), v3.end(), greater<ll>());
    //cout<< e << f << g << h << endl;
    ll ans = 0;
    for(int a = 0; a < e+1; a++){
        for(int b = 0; b < f+1; b++){
            for(int c = 0; c < g+1; c++){
                for(int d = 0; d < h+1; d++){
                    //cout << a << b << c << d<< endl;
                    if(a*minw +b*(minw+1) + c*(minw+2) + d*(minw+3) <= W){
                        ll dd = 0;
                        for(int aa = 0; aa < a; aa++){
                            dd += v0[aa];
                        }
                        for(int aa = 0; aa < b; aa++){
                            dd += v1[aa];
                        }
                        for(int aa = 0; aa < c; aa++){
                            dd += v2[aa];
                        }
                        for(int aa = 0; aa < d; aa++){
                            dd += v3[aa];
                        }
                        //cout << dd << endl;
                        ans = max(dd, ans);
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
	long long a,b,k;
	cin >> a >> b >> k;
	for(long long i = 0;i < k;i++){
		if(i%2 == 0){
			a = a/2;
			b += a;
		}else{
			b = b/2;
			a += b;
		}
	}
	cout << a << " " << b << endl;
	return 0;
}

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

int main() {

  int N, K;
  cin >> N >> K;

  vector<vector<int>> td(N);
  for (int i = 0; i < N; i++) {
    int t, d;
    cin >> t >> d;
    t--;
    td[t].push_back(d);
  }

  vector<pair<int,int>> p;
  for (int i = 0; i < N; i++) {
    if (0 < td[i].size()) {
      sort(td[i].begin(), td[i].end());
      for (int j = 0; j < td[i].size(); j++) {
        p.push_back(make_pair(td[i][j], j == (td[i].size() - 1)));
      }
    }
  }

  sort(p.begin(),p.end());

  priority_queue<int, vector<int>, greater<int>> que;

  int kind = 0;
  int choose = 0;
  long long sum = 0;
  long long answer = 0;

  for (int i = p.size() - 1; 0 <= i; i--) {
    int d = p[i].first;
    int v = p[i].second;
    sum += d;
    choose++;
    kind += v;
    if (!v) {
      que.push(d);
    }
    if (choose > K) {
      if (!que.size()) {
        break;
      }
      sum -= que.top();
      que.pop();
      choose--;
    }
    if (choose == K) {
      answer = max(answer, sum +(long long) kind * kind);
    }
  }
  
  cout << answer << endl;

  return 0;

}

Measured memory_bytes: 6904
using System;
using System.Linq;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] str=Console.ReadLine().Split(' ');
      int H=int.Parse(str[0]);
      int W=int.Parse(str[1]);
      for(int i=1;i<=H;i++){
        string row=Console.ReadLine();
        Console.WriteLine(row);
        Console.WriteLine(row);
      }
    }
    
  }

}


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

int main(){ 
int S,W;
cin >> S >> W;

if (S <= W) cout << "unsafe" << endl;
else cout << "safe" << endl;
}

Measured memory_bytes: 3672
#include<stdio.h>
int main()
{
    int a,b,c,k,i,t;
    scanf("%d%d%d%d",&a,&b,&c,&k);
    if(a<b)
    {
       t=a;
            a=b;
            b=t;
    }
    if(a<c)
    {
         t=a;a=c;c=t;
    }

    for(i=1;i<=k;i++)
    {
        a=a*2;
    }
    printf("%d",a+b+c);
    return 0;
}


Measured memory_bytes: 128
n = int(input())
ns = list(map(int, input().split()))[::-1]
lis = []
count = 0
for i in range(n-1):
    if ns[i] <= ns[i+1]:
        count += 1
    else:
        count = 0
    lis.append(count)
if n == 1:
    print(0)
else:
    print(max(lis))


Measured memory_bytes: 14228
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

char s[800][801];
int d[800][800];
int main() {
	MEM_1(d);
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	fup(i,0,n-1,1)scanf("%s",s[i]);
	int x,y;
	fup(i,0,n-1,1)fup(j,0,m-1,1)if(s[i][j]=='S')x=i,y=j;
	d[x][y]=0;
	queue<Pi> q;
	q.push(mp(x,y));
	while(!q.empty())
	{
		int xx,yy;
		tie(xx,yy)=q.front();
		q.pop();
		fup(i,0,3,1)
		{
			int nx=xx+dx[i],ny=yy+dy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<m&&s[nx][ny]!='#'&&d[nx][ny]==-1)
			{
				d[nx][ny]=d[xx][yy]+1;
				q.push(mp(nx,ny));
			}
		}
	}
	int ans=INF;
	fup(i,0,n-1,1)fup(j,0,m-1,1)
	{
		if(d[i][j]!=-1 && d[i][j]<=k)
		{
			int t=min({i,n-i-1,j,m-j-1});
			if(t>0)t=(t-1)/k+1;
			ans=min(ans,t);
		}
	}
	printf("%d",ans+1);
}

Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int fr[] = {0,-1,0,0,-1,0,0,-1,0,-1};

int main(){

    int a,b,c,d;

    cin >> a >> b >> c >> d;

    fr[a]++;
    fr[b]++;
    fr[c]++;
    fr[d]++;

    for(int x:fr){
        if(x != 0){
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";

    return 0;
}


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

struct RA {
	using type1 = int;
	using type2 = int;
	static type1 id1() { return 0; }
	static type2 id2() { return 0; }
	static type1 op1(const type1& l, const type1& r) { return l + r; }
	static type1 op2(const type1& l, const type2& r) { return l + r; }
	static type2 op3(const type2& l, const type2& r) { return l + r; }
};

template <typename M>
class LazySegmentTree {
	using T1 = typename M::type1;
	using T2 = typename M::type2;
	const int n;
	vector<T1> data;
	vector<T2> lazy;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	void push(int node) {
		if (lazy[node] == M::id2()) return;
		if (node < n) {
			lazy[node * 2] = M::op3(lazy[node * 2], lazy[node]);
			lazy[node * 2 + 1] = M::op3(lazy[node * 2 + 1], lazy[node]);
		}
		data[node] = M::op2(data[node], lazy[node]);
		lazy[node] = M::id2();
	}
	void suc(int l, int r, int node, int lb, int ub, T2 val) {
		if (ub <= l || r <= lb) return;
		if (l <= lb && ub <= r) {
			lazy[node] = M::op3(lazy[node], val);
			return;
		}
		push(node);
		int c = (lb + ub) / 2;
		suc(l, r, node * 2, lb, c, val);
		suc(l, r, node * 2 + 1, c, ub, val);
		data[node] = M::op1(M::op2(data[node * 2], lazy[node * 2]), M::op2(data[node * 2 + 1], lazy[node * 2 + 1]));
	}
	T1 sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return M::id1();
		if (l <= lb && ub <= r) return M::op2(data[node], lazy[node]);
		push(node);
		int c = (lb + ub) / 2;
		return M::op1(sub(l, r, node * 2, lb, c), sub(l, r, node * 2 + 1, c, ub));
	}
public:
	LazySegmentTree(int n_) : n(size(n_)), data(n * 2, M::id1()), lazy(n * 2, M::id2()) {}
	void update(int l, int r, T2 val) {
		suc(l, r + 1, 1, 0, n, val);
	}
	T1 find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q, type, s, t, x;
	cin >> n >> q;
	LazySegmentTree<RA> lst(n);
	while (q--) {
		cin >> type;
		if (type) {
			cin >> x; x--;
			printf("%d\n", lst.find(x, x));
		}
		else {
			cin >> s >> t >> x; s--, t--;
			lst.update(s, t, x);
		}
	}
	return 0;
}

Measured memory_bytes: 4964
#include<bits/stdc++.h>
using namespace std;
int n;
char a[2222222];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	int l=-1,r=n;
	int ans=0;
	while(l<r){
		l++;
		while(a[l]!='W'&&l<n)
			l++;
		r--;
		while(a[r]!='R'&&r>=0)
			r--;
		ans++;
	}
	cout<<ans-1<<endl;
	return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
#define OO 1e9
using namespace std;



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int>v;
    vector<int>dp;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        v.push_back(t);
    }
    dp.push_back(0);
    dp.push_back(abs(v[0]-v[1]));
    for(int i=2;i<n;i++){
        dp.push_back(min(dp[i-1]+abs(v[i-1]-v[i]),dp[i-2]+abs(v[i-2]-v[i])));
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1400
using System;
 
    class Program
    {
        static void Main(string[] args)
        {int r, c, i, j;
            int subTotal = 0;
            int total = 0;

            string[] str = Console.ReadLine().Split(' ');
            r = int.Parse(str[0]);
            c = int.Parse(str[1]);
 
            //2次元配列
            int[,] array = new int[r, c];
 
            for (i = 0; i < r; i++)
            {
                string[] str2 = Console.ReadLine().Split(' ');
 
                for (j = 0; j < c; j++)
                {
                    array[i, j] = int.Parse(str2[j]);
                }
            }
 
            //Console.WriteLine("-------------");
 
            //横の計算
            for (i = 0; i < r; i++)
            {
                for (j = 0; j < c; j++)
                {
                    subTotal += array[i, j];
                    Console.Write(array[i, j] + " ");
                }
                Console.Write(subTotal);
                subTotal = 0;
                Console.WriteLine("");
            }
 
            //縦の計算
            for (j = 0; j < c; j++)
            {
                for (i = 0; i < r; i++)
                {
                    subTotal += array[i, j];
                }
                Console.Write(subTotal + " ");
                total += subTotal;
                subTotal = 0;
            }
            Console.WriteLine(total);
        }
}


Measured memory_bytes: 15828
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144 * 4LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll
string Cipher(State &a);
string String(State &a);
string Letter(State &a);

string Cipher(State &a) {
	string s;
	for (;*a != ')'&&*a != ']';) {
		s += String(a);
	}
	return s;
}

string String(State &a) {
	string ans;
	if (*a == '[') {
		a++;
		ans = Cipher(a);
		a++;
		reverse(ALL(ans));
	}
	else {
		ans = Letter(a);
	}
	return ans;
}

string Letter(State& a) {
	string b;
	int now = 0;
	while (!((*a >= 'A' && *a <= 'Z')||(*a == '?'))) {
		if (*a == '+')now++;
		else now--;
		a++;
	}
	now += 2600;
	now += *a - 'A';
	now %= 26;
	if (*a == '?') {
		now = 0;
	}
	a++;
	b.push_back(now + 'A');
	return b;
}

void solve(){
	while (true) {
		string s;
		cin >> s;
		if (s == ".") return;
		s.push_back(')');
		State begin = s.begin();
		cout << Cipher(begin) << endl;
	}
}

#undef int

int main() {
	init();
	solve();
}


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

struct Node{
    int a;
    int b;
}node[100007];

int tmp[100007]; //临时空间
int tmp_length = 0; //临时空间长度

//重新排序
void sort(int idx){
    int left = idx*2+1;
    int right = idx*2+2;
    int max = idx;
    if(left < tmp_length && tmp[left] >= tmp[max]) max = left;
    if(right < tmp_length && tmp[right] >= tmp[max]) max = right;
    if(max != idx){
        //交换元素
        tmp[max]^=tmp[idx];
        tmp[idx]^=tmp[max];
        tmp[max]^=tmp[idx];
        sort(max);  //重新调整
    }
}

//压入一个数字
void push(int num){
    tmp[tmp_length++] = num;
    int i,idx;
    for(i = tmp_length-1; i > 0; i = idx){
        idx = (i-1)/2;
        sort(idx); //重新调整
    }
}

//弹出元素
int pop(){
    int ret = 0;
    if(tmp_length > 0){
        ret = tmp[0];
        tmp[0] = tmp[--tmp_length];
        sort(0);
    }
    return ret;
}

//判断是否为空
int empty(){
    return tmp_length == 0;
}

int cmp(const void * a,const void * b){
    return ((struct Node*)a)->a > ((struct Node*)b)->a;
}

int main(){
    int N,M;
    int i,j;
    int sum,max,idx;

    while(~scanf("%d%d",&N,&M)){
        for(i = 0; i < N; i++)
            scanf("%d%d",&node[i].a,&node[i].b);
        qsort(node,N,sizeof(struct Node),cmp);

        sum = 0;
        tmp_length = 0;
        idx = 0;
        for(i = 1; i <= M; i++){
            while(idx < N && node[idx].a <= i){
                push(node[idx++].b);  //压入一个数字
            }
            if(!empty()){
                sum+=pop();
            }
        }
        printf("%d\n",sum);
    }
}


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

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

struct edge {
  int from, to, cost;
  edge() {}
  edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

struct UnionFind {
  int n;
  vector<int> rank, par;
  UnionFind() {}
  UnionFind(int n) : n(n), rank(n, 1), par(n) {
    iota(par.begin(), par.end(), 0);
  }
  int root(int x) {
    return par[x] == x ? x : par[x] = root(par[x]);
  }
  void merge(int x, int y) {
    if ((x = root(x)) == (y = root(y))) return;
    if (rank[x] < rank[y]) swap(x, y);
    rank[x] += rank[y];
    par[y] = x;
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return rank[root(x)];
  }
};

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n, m;
  while (cin >> n >> m, n) {
    vector<edge> es;
    for (int i = 0; i < m; i++) {
      int a, b, w;
      cin >> a >> b >> w;
      a--, b--;
      es.emplace_back(a, b, w);
    }
    sort(es.begin(), es.end(), [&](edge a, edge b) {
      return a.cost < b.cost;
    });

    int ans = 1 << 30;
    for (int i = 0; i < m; i++) {
      UnionFind uf(n);
      int mn = 1 << 30, mx = 0;
      for (int j = i; j < m; j++) {
        if (!uf.same(es[j].from, es[j].to)) {
          uf.merge(es[j].from, es[j].to);
          mn = min(mn, es[j].cost);
          mx = max(mx, es[j].cost);
        }
      }
      if (uf.size(0) == n) ans = min(ans, mx - mn);
    }
    if (ans == 1 << 30) cout << -1 << endl;
    else cout << ans << endl;
  }


  return 0;
}


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

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s-x-0.5, 1, x)) # start construction
    events.append((t-x-0.5, -1, x)) # end construction

for i in range(q):
    d = int(input())
    events.append((d, 0, i)) # query
    
events = sorted(events)
is_stop = False
stops = set()
min_stop = float('inf')
ans = [-1]*q
for t, e, x in events: # time, event, distance/index
    if e > 0:
        stops.add(x)
        if x < min_stop:
            min_stop = x
            is_stop = True
    elif e < 0:
        stops.remove(x)
        if min_stop == x:
            is_stop = False
    elif len(stops) > 0:
        if not is_stop:
             min_stop = min(stops)
             is_stop = True
        ans[x] = min_stop
         
print('\n'.join(map(str, ans)))

Measured memory_bytes: 106796
#include <bits/stdc++.h>
using namespace std;
#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++)
typedef long long ll;

int main() {
  ll n;
  cin >> n;
  cout << n*(n-1)/2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

bool cmp(ll n, P const& p)
{
    return ((p.first > n));
}

int n;
VI a(1000100),b(1000100);
vector<vector<P>> d(5000000,vector<P>(0));
int boarder=4095;

void dfs(int v){
	if(v>=boarder||v>=n)
		return;
	if(v==0){
		d[v].push_back({b[v],a[v]});
		d[v].push_back({0,0});
	}
	else{
		for(auto p:d[(v+1)/2-1]){
			d[v].push_back({p.first+b[v],p.second+a[v]});
			d[v].push_back({p.first,p.second});
		}
	}
	if((v+1)*2<=n)
		dfs((v+1)*2-1);
	if((v+1)*2+1<=n)
		dfs((v+1)*2);
	sort(ALL(d[v]));
	ll mx=0;
	REP(i,d[v].size()){
		mx=max(mx,d[v][i].second);
		d[v][i].second=mx;
	}
}

int main(){
	cin >> n;
	REP(i,n) cin >> a[i] >> b[i];
	dfs(0);
	int q; cin >> q;
	ll v, l;
	while(q--){
		cin >> v >> l; v--;
		if(v<boarder){
			int it=upper_bound(d[v].begin(),d[v].end(),l,cmp)-d[v].begin();
			if(it==0)
				cout << 0 << endl;
			else
				cout << d[v][it-1].second << endl;
		}
		else{
			VI s(0);
			while(v>=boarder){
				s.push_back(v);
				v=(v+1)/2-1;
			}
			ll ans=0;
			REP(i,1<<s.size()){
				ll suma=0, sumb=0;
				REP(j,s.size()) if(i>>j&1){
					suma+=a[s[j]];
					sumb+=b[s[j]];
				}
				if(l-sumb<0)
					continue;
				int it=upper_bound(d[v].begin(),d[v].end(),l-sumb,cmp)-d[v].begin();
				if(it==0)
					ans=max(ans,suma);
				else
					ans=max(ans,suma+d[v][it-1].second);
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 316304
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>



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

  int m,d;
  cin>>m>>d;

  int ans=0;
  FOR(i,1,m+1){
    FOR(j,1,d+1){
      if(j/10>=2&&j%10>=2&&(j/10)*(j%10)==i) ans++;
    }
  }

  cout<<ans<<endl;

}

Measured memory_bytes: 256