akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#define int long long
signed main() {
    int n;
    cin >> n;
    int i;
    int sum = 0;
    for(i=1;i<=n;i++)
        sum+=(i*(n/i)*((n/i)+1)/2);
    cout << sum;    
}

Measured memory_bytes: 3576
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
signed main() {
	int n,t;
	cin>>n>>t;
	int s=0,b=0,d;
	cin>>b;
	for(int i=1;i<n;i++){
		cin>>d;
		s+=min(t,d-b);
		b=d;
	}
	s+=t;
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 256
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const N = Number(input[0][0]);

  const T: { [key: number]: number | undefined } = {};

  for (let x = 1; x * x <= N; x++) {
    for (let y = 1; y * y <= N; y++) {
      for (let z = 1; z * z <= N; z++) {
        const n = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x;

        T[n] = (T[n] || 0) + 1;
      }
    }
  }

  const F: number[] = [];

  for (let i = 1; i <= N; i++) {
    F.push(T[i] || 0);
  }

  return F.join("\n");
};

console.log(main(read()));


Measured memory_bytes: 34744
N_setup_data = input().split()
N_sunuke_number = int(N_setup_data[0])
K_snack_number = int(N_setup_data[1]) - 1
K_snack_number = int(N_setup_data[1])
N_sunuke_pocket = [0] * N_sunuke_number


for j in range(K_snack_number):
	N_A_sunuke_pocket = [0] * (N_sunuke_number + 1)
	N_B_sunuke_pocket = [0] * (N_sunuke_number + 1)
	d = input()
	N_A_sunuke_pocket = input().split()
#	print(N_A_sunuke_pocket)
	for i in N_A_sunuke_pocket:
		N_B_sunuke_pocket[int(i) - 1] += 1
#	print(N_B_sunuke_pocket, i)
	j = 0

	for i in N_B_sunuke_pocket:
		if i != 0:
			N_sunuke_pocket[j] += 1
		j += 1
#		print(N_sunuke_pocket)
def calc_area():
	Out_Area = 0
	for i in N_sunuke_pocket:
		if i == 0:
			Out_Area += 1
	return Out_Area

print(calc_area())


Measured memory_bytes: 9204
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <stack>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右下左上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, 1, 0, -1, -1, 1, 1, -1 };

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

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; ++i) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t szi, szj;
        inp(std::size_t _szi = 1, std::size_t _szj = 1) : szi(_szi), szj(_szj) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(szi); for (std::size_t i = 0; i < szi; ++i) std::cin >> a[i]; return a; }
        template <typename T> operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i) for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j]; return a;
        }
    };
    inp inp1;
}

int main() {

    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;

    int h = h2 - h1;
    int m = m2 - m1;

    int len = m + h * 60;

    Cout(len - k);

    return 0;
}


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

using namespace std;

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

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

void solve(int test_case) {
	ull a,b,x,cnt=0;
	cin>>a>>b>>x;
	cnt = (b/x)-(a/x);
	if(a%x==0)cnt++;
	cout<<cnt;
}

int main() {
	
	////// FILE BASED IO////
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
}	


Measured memory_bytes: 3644
#include <iostream>
using namespace std;
int main(){
	int H,W;
	while(1){
	cin >> H >> W;
	if(H==0 && W==0) return 0;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++) cout << "#";
		cout << endl;
	}
 	cout << endl;  
}
}

Measured memory_bytes: 1156
from itertools import chain
from bisect import bisect_left, bisect_right

H, W, M = map(int, input().split())
YX = [list(map(int, input().split())) for _ in range(M)]
# H, W, M = 3*10**5, 3*10**5, 3*10**5
# YX = [[(i*100)//W, (i*100)%W] for i in range(M)]

X_sets = [[] for _ in range(W+1)]
Y_sets = [[] for _ in range(H+1)]
for y, x in YX:
    X_sets[x].append(y)
    Y_sets[y].append(x)

[s.sort() for s in X_sets]
[s.sort() for s in Y_sets]

# print(X_sets, Y_sets)

X_set_max_len = max(map(len, X_sets))
Y_set_max_len = max(map(len, Y_sets))

# print("ppp", X_set_max_len, Y_set_max_len)

# for s in X_sets:
#     print(s)

X_list = set(i for i, s in enumerate(X_sets) if len(s) == X_set_max_len)
Y_list = set(i for i, s in enumerate(Y_sets) if len(s) == Y_set_max_len)

score = X_set_max_len + Y_set_max_len - 1
# print("b", score, X_list, Y_list)
for x in X_list:
    for y in Y_list:
        c = bisect_right(X_sets[x], y) - bisect_left(X_sets[x], y)
        # print(x, y, c)
        if c == 0:
            score += 1
            print(score)
            exit()

print(score)

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

int main() {

    string N;

    cin >> N;

    string ans = "pon";
    int i = N.size()-1;

    if (N.at(i) == '2' || N.at(i) == '4' || N.at(i) == '5' || N.at(i) == '7' || N.at(i) == '9') {
        ans = "hon";
    } else if (N.at(i) == '3') {
        ans = "bon";
    }
    
    

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

Measured memory_bytes: 3624
from collections import  *
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
a,b,c=io()
def cal(a,b,x):
    print(((a * x) // b) - (a * (x//b)))
if c>b:
    x=c-(c%b)-1
    cal(a,b,x)
elif b==c:
    cal(a,b,b-1)
else:
    cal(a,b,c)

Measured memory_bytes: 9440
n = int(input())

ab = [list(map(int, input().split())) for _ in range(n)]

ab = sorted(ab, key=lambda x:x[1])

flag = True
t = 0
for i in range(n):
    t += ab[i][0]
    if t>ab[i][1]:
        flag = False
        break

if flag:
    print('Yes')
else:
    print('No')

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

int main()
{
    int r,c;
    cin >> r >> c;
    int suma[r];
    int sumb[c];
    int s[r][c];
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin >> s[i][j];
        }
    }
    for(int i=0;i<r;i++)
    {
        int tmp=0;
        for(int j=0;j<c;j++)
        {
            tmp+=s[i][j];
        }
        suma[i]=tmp;
    }
    for(int i=0;i<c;i++)
    {
        int tmp=0;
        for(int j=0;j<r;j++)
        {
            tmp+=s[j][i];
        }
        sumb[i]=tmp;
    }
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cout << s[i][j] << " ";
        }
        cout << suma[i] << endl;
    }
    for(int i=0;i<c;i++)
    {
        cout << sumb[i] << " ";
    }
    int tmp=0;
    for(int i=0;i<c;i++)
    {
        tmp+=sumb[i];
    }
    cout << tmp << endl;
}


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

struct UnionFind {
    vector<int> data;
    int sz;
    UnionFind(int sz) : data(sz, -1), sz(sz) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) == (y = root(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y]; data[y] = x; sz--;
        return true;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    int size() { return sz; }
};

int main() {
    int n, m; cin >> n >> m;
    UnionFind uf(n * 2);
    for (int i = 0; i < m; i++) {
        int x, y, z; cin >> x >> y >> z; x--, y--;
        if (z % 2) {
            uf.unionSet(x, y + n);
            uf.unionSet(x + n, y);
        } else {
            uf.unionSet(x, y);
            uf.unionSet(x + n, y + n);
        }
    }
    cout << uf.size() / 2 << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()

const long long INFLL = 1LL << 60;
const int INFINT = 1 << 30;
const long long MOD = 1e9 + 7;

template <class T> void vecout(T V) {
    auto t = V.begin();
    while(t != V.end()) {
        cout << *t++;
        if(t != V.end()) cout << " ";
    }
    cout << endl;
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // int n;
    // cin >> n;
    set<int> s;
    int q, a, b;
    cin >> q;
    rep(i, q) {
        cin >> a >> b;
        if(a == 0) {
            s.insert(b);
            cout << s.size() << "\n";
        } else if(a == 1) {
            cout << (s.find(b) != s.end()) << "\n";
        } else {
            s.erase(b);
        }
    }
}



Measured memory_bytes: 12480
#pragma region 宣言部分
#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define rep(i,m,n) for(int i = (m);i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
#define Vec(a) vector <int> a
const int INF = 1 << 20;
const int MOD = 1e9+7;

#pragma endregion



int main(){
    int n,k;
    cin >> n >> k;
    vector <int> a;
    REP(i,n){
        int x;
        cin >> x;
        a.pb(x);
    }
    sort(a.begin(),a.end());
    ll m = 0;
    REP(i,k){
        m += a[i];
    }
    cout << m << endl;
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int main(){
	int x,y,pre,box[200];
	while(cin>>x>>y){
		pre=0;
		for(int i=0;i<=100;i++)
		box[i]=0;
		box[x-1]++;
		box[y-1]++;
		while(cin>>x>>y,x||y){
			box[x-1]++;
			box[y-1]++;
		}
		for(int i=0;i<10;i++){
		if(box[i]!=0){
			if(box[i]%2==1)
			pre++;
		}
		}
		if(pre>2||box[0]%2!=1||box[1]%2!=1)
		cout<<"NG"<<endl;
		else cout<<"OK"<<endl;
		
		
		
	}
	
	return 0;
}

Measured memory_bytes: 0
n = int(input())
s = list(input())
cr = [0] * n
cg = [0] * n
cb = [0] * n
for i in range(n):
    if i == 0:
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
    else:
        cr[i] = cr[i-1]
        cg[i] = cg[i-1]
        cb[i] = cb[i-1]
        if s[i] == 'R':
            cr[i] += 1
        elif s[i] == 'G':
            cg[i] += 1
        else:
            cb[i] += 1
ans = 0
for i in range(n-2):
    a = s[i]
    for j in range(i+1, n-1):
        b = s[j]
        if a == b:
            continue
        diff = j - i
        c = list({'R', 'G', 'B'} - {a, b})[0]
        if c == 'R':
            ans += cr[-1] - cr[j]
        elif c == 'G':
            ans += cg[-1] - cg[j]
        else:
            ans += cb[-1] - cb[j]
        if j + diff < n:
            if s[j + diff] == c:
                ans -= 1
print(ans)


Measured memory_bytes: 69168
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define FIND(x, target) find(x.begin(),x.end(),target)
#define pb(x) push_back(x)
#define int long long

#define NUM 1000000007

struct _chunk {
	int name;
	int nextNum;
	vector<int> next;
};

int factorial(int num1, int num2){
    int sum = 1;
    for (int i = num1 + 1; i <= num1 + num2; ++i)
    {
        sum *= i;
    }

    for (int i = num2; i >= 1; --i) {
    	sum /= i;
    }
    return sum;
}

signed main(void) {
  int N;
  cin >> N;
  int A[N];
  int ans[N];
  int sum = 0;
  int sum_m = 0;
  rep(i, N) {
  	cin >> A[i];
  	sum += A[i];
  	if (i%2 == 0 && i!= N-1) {
  		sum_m += A[i] * 2;
  	}
  }

  ans[N-1] = sum - sum_m;
  for (int i=N-2; i>=0; i--) {
  	ans[i] = A[i]*2 - ans[i+1];
  }

  rep(i, N) {
  	cout << ans[i] << " ";
  }
  cout << endl;


  return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define MOD 100000007
#define PI 3.141592653589793238
#define pb push_back
#define ALL(V) (V).begin(), (V).end()
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long long int lint;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
ll gcd(ll a, ll b) { return (a % b == 0 ? b : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll char_to_ll(char c) { return (int)(c - '0'); }
ll string_to_ll(string s) { return char_to_ll(atoi(s.c_str())); }
bool is_prime(ll x){ if(x <= 1) return false; for(ll i = 2; sqrt(i) <= x; i++) if(x % i == 0) return false; return true; }

int main(){
    string S;
    cin >> S;
    string A = S.substr(0, (S.length() - 1) / 2);
    string B = S.substr((S.length() + 3) / 2 - 1);

    if(A == B) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sys/types.h>
#include <unistd.h>

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

template<typename T> vector<T> make_vector(size_t sz){
	return vector<T>(sz);
}

template<typename T,typename... Ts> 
auto make_vector(size_t sz, Ts... ts){
	return vector<decltype(make_vector<T>(ts...))>(sz, make_vector<T>(ts...));
}

template<typename T,typename U,typename... V> 
typename enable_if<is_same<T, U>::value!=0>::type 
fill_value(U &u, const V... v){
	u=U(v...);
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_value(U &u, const V... v){
	for(auto &e:u){
		fill_value<T>(e,v...);
	}
}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

const int limit = 100010;
int nxt[limit];

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

	using pii = pair<int, int>;


	vector<pii> aary;
	rep(i, n) aary.push_back(pii(a[i], i));
	sort(begin(aary), end(aary));

	vector<pii> bary;
	rep(i, n) bary.push_back(pii(b[i], i));
	sort(begin(bary), end(bary));

	rep(i, n){
		nxt[aary[i].second] = bary[i].second;
	}

	bool ok = true;
	rep(i, n){
		if(aary[i].first > bary[i].first){
			ok = false;
		}
	}

	bool ok2 = false;
	int pos = nxt[0], cnt = 1;
	while(pos) {
		pos = nxt[pos];
		cnt++;
	}

	if(cnt < n) ok2 = true;

	rep(i, 1, n){
		if(aary[i].first <= bary[i - 1].first){
			ok2 = true;
		}
	}

	puts((ok & ok2) ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define int long long
#define double long double
#define all(a) a.begin(), a.end()
#define debug(x) cout << #x << " = " << x << endl;
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; }
using namespace std;

signed main(void){
    
    int N, Q; cin >> N >> Q;
    vector<char> s(N + 2), t(Q), d(Q);
    rep(i, N)cin >> s[i + 1];
    rep(i, Q)cin >> t[i] >> d[i];
    s[0] = s[N + 1] = '*';

    int ll = 0, lr = N + 1;
    while(lr - ll > 1){
        int m = (ll + lr) / 2;
        int pos = m;
        rep(i, Q){
            if(t[i] == s[pos]){
                if(d[i] == 'R')pos++;
                else pos--;
            }
        }
        if(pos == 0)ll = m;
        else lr = m;
    }

    int rl = 0, rr = N + 1;
    while(rr - rl > 1){
        int m = (rl + rr) / 2;
        int pos = m;
        rep(i, Q){
            if(t[i] == s[pos]){
                if(d[i] == 'R')pos++;
                else pos--;
            }
        }
        if(pos == N + 1)rr = m;
        else rl = m;
    }

    cout << rl - lr + 1<< endl;
    return 0;
    
}

Measured memory_bytes: 896
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Integer> inputList = new ArrayList<>();

		try {
			while (input.ready()) {
				inputList.add(Integer.valueOf(input.readLine()));
			}
		} catch (IOException e) {
			e.printStackTrace();
		}

		for (int each : inputList) {
			System.out.println(getFactorial(each));
		}
	}

	public static long getFactorial(int num) {
		long ans = 1;
		for (int i = num; i > 1; i--) {
			ans *= i;
		}
		return ans;
	}
}

Measured memory_bytes: 24132
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

bool DEBUG = false;


int u[100000], v[100000];
long long s[100000];
bool eflag[100000];
bool pflag[100000];
bool mflag[100000];

long long pls[100000];
long long mis[100000];

vector<int> edge[100000];

int dfs(int n){
   if(DEBUG) cout <<"n:" << n << endl;

   for(int e: edge[n]){
      if(eflag[e])
         continue;

      eflag[e] = true;

      int dist;
      if(u[e] == n)
         dist = v[e];
      else
         dist = u[e];

     if(DEBUG)  cout <<"dist:" << dist << endl;

      if(pflag[n]){
         if(mflag[dist]){
            if(mis[dist] != s[e] - pls[n]){
               return -1;
            }
         }else{
            mflag[dist] = true;
            mis[dist] = s[e] - pls[n];
         }
      }

      if(mflag[n]){
         if(pflag[dist]){
            if(pls[dist] != s[e] - mis[n]){
               return -1;
            }
         }else{
            pflag[dist] = true;
            pls[dist] = s[e] - mis[n];
         }
      }

      int res = dfs(dist);
      if(res == -1)
         return -1;
   }
   return 0;
}


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

   for(int i=0; i<n; i++){
      pflag[i] = false;
      mflag[i] = false;
   }


   for(int i=0; i<m; i++){
      cin >> u[i] >> v[i] >> s[i];
      u[i]--;
      v[i]--;

      edge[u[i]].push_back(i);
      edge[v[i]].push_back(i);
      eflag[i] = false;
   }

   pls[0] = 0;
   pflag[0] = true;

   if(dfs(0) < 0){
      cout << "0\n";
      return 0;
   }

   long long upper = 1E15;
   long long lower = 0;

   long long answer = 0;

   for(int i=0; i<n; i++){
      if(DEBUG) {
         cout<<i<<endl;
         if(pflag[i]){
            cout<<"  "<<pls[i] << " + X" <<endl;
         }
         if(mflag[i]){
            cout<<"  "<<mis[i] << " - X" <<endl;
         }
      }

      if(pflag[i] && mflag[i]){
         if((pls[i] + mis[i]) % 2 || mis[i] - pls[i] <= 0){
            cout << "0\n";
            return 0;
         }else{
            if(answer && 2*answer != mis[i] - pls[i]){
               cout << "0\n";
               return 0;
            }
            answer = (mis[i] - pls[i]) / 2;
         }
      }
      if(pflag[i]){
         lower = max(lower, -pls[i]);
      }
      if(mflag[i]){
         upper = min(upper, mis[i]);
      }
   }

   if(DEBUG) cout<<"answer:"<<answer<<endl;
   if(DEBUG) cout<<"upper:"<<upper<<endl;
   if(DEBUG) cout<<"lower:"<<lower<<endl;

   if(answer){
      if(lower < answer && answer < upper)
         cout << "1\n";
      else
         cout << "0\n";
   }else{
      if(DEBUG) cout<<"upper:"<<upper<<endl;
      if(DEBUG) cout<<"lower:"<<lower<<endl;

      if(upper - lower - 1 > 0)
         cout << upper - lower - 1 << endl;
      else
         cout << "0\n";
   }

   return 0;
}


Measured memory_bytes: 16896
#include<bits/stdc++.h>
using namespace std;
int main(void){
int n,k;cin>>n>>k;
string s;cin>>s;
char x[n+1];
strcpy(x,s.c_str());
x[k-1]=char(int(x[k-1])+32);
string t="";
for(int i=0;i<n;i++)
    t+=x[i];
cout<<t<<endl;
return 0;}


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

int main(){
    int A,B,K;
    cin>>A>>B>>K;
    for(int i=1;i<=K;i++){
        if((i%2)==1){
            if((A%2)==1){A=(A-1)/2;B=B+A;}
            else{A=A/2;B=B+A;}
        }
        else{
            if((B%2)==1){B=(B-1)/2;A=A+B;}
            else{B=B/2;A=A+B;} 
        }
    }
    cout<<A<<" "<<B;    
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"

using namespace std;
using LL = long long;

constexpr int N = 1e5 + 5;
constexpr LL MOD = 998244353;

int cnt[N];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        
        if (i == 0) {
            if (h) {
                cout << 0;
                return 0;
            }
        }

        cnt[h]++;
    }

    if (cnt[0] != 1) cout << 0, exit(0);

    LL res = 1;

    for (int i = 1; i < n; i++) {
        if (cnt[i] && cnt[i - 1] == 0) cout << 0, exit(0);
        if (cnt[i] == 0) continue;

        for (int j = 0; j < cnt[i]; j++) (res *= cnt[i - 1]) %= MOD;
    }

    cout << res << endl;
}

Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	int p[n];
	for(int i = 0; i < n; i++)
		cin >> p[i];
	
	int count = 1;
	int min = p[0];
	for(int i = 1; i < n; i++)
		if(p[i] < min) {
			min = p[i];
			count++;
		}

	cout << count;
}


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<stack> 
#include<queue>
#include<cmath>
#include<map>
#define LL long long
#define N 100100
#define M 1010
#define MOD 1000000007
#define FOR(i,l,r) for (int i = (l); i <= (r); i ++)
#define CLR(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define X first
#define Y second
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	int c1 = 0,c2 = 0;
	FOR(i,1,n){
		int x;
		scanf("%d",&x);
		if (x & 1) c1 ++;
		if (x % 4 == 0) c2 ++;
	}
	if (c1 <= c2 || (c1 + c2 == n && c1 - 1 <= c2)) printf("Yes\n");
	else printf("No\n");
}

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

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

string S;
int N;
int rn[2019];

int main(){
	cin>>S; N = S.size();
	memset(rn, 0, sizeof(rn));
	int r = S[N-1] - '0';
	rn[0] = 1;
	int r10 = 1;
	rn[r] = 1;
	ll res = 0;
	for(int i=N-2; i>=0; i--){
		r10 = (r10 * 10) % 2019;
		r = (r + (S[i] - '0') * r10) % 2019;
		//cout<<i<<" "<<r<<" "<<rn[r]<<endl;
		res += rn[r];
		rn[r]++;
	}

	cout<<res<<endl;
	return 0;
}


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


void solve(long long A, long long B, long long C){
  cout << (B+ min(A+B+1, C)) << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
  scanf("%lld",&A);
  long long B;
  scanf("%lld",&B);
  long long C;
  scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 3716
def solve():
    N = int(input())
    a = list(map(int, input().split()))
    ans = float("inf")
    for i in range(min(a),max(a)+1):
        cost = 0
        for a_i in a:
            cost += abs(i-a_i)**2
        ans = min(ans, cost)
    print(ans)
    
solve()


Measured memory_bytes: 2940
//ThakurAnurag
//TemplateCode

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

#define ll long long int
#define ull unsigned long long int
#define fo(i,a,n) for(ll i=a;i<n;i++)
#define fo2(i,a,n) for(ll i=n;i>=a;i--)
#define endl "\n"
#define sp " "
#define f first
#define s second
#define pb push_back
#define buffer ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define lower(str) transform(str.begin(), str.end(), str.begin(), ::tolower);
#define upper(str) transform(str.begin(), str.end(), str.begin(), ::toupper);
#define init(arr,val) memset(arr,val,sizeof(arr))
#define vecl(v) vector<ll> v
#define vecs(v) vector<string> v
#define vecp(v) vector < pair <ll,ll> > v

int main()
{
	ll d,n;
	cin>>d>>n;
	if(d==0){
		if(n==100)
			cout<<"101"<<endl;
		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;
		else
			cout<<n*100*100<<endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    int t = (int)(N / 1.08);
    for(int i = t; (int)(i * 1.08) <= N; ++i) {
        if((int)(i * 1.08) == N) {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<array>
#include<vector>
#include<numeric>
#include <algorithm>
#include <functional>

using ll = long long;
using std::cin;
using std::cout;
using std::endl;


int main(){
    cout.precision(10);
    int N;
    std::vector<ll> A;
    cin>>N;
    for(int i=0;i<N;++i){
        int a;
        cin>>a;
        A.push_back(a);
    }
    std::sort(A.begin(), A.end());
    double sum;
    for(int i=N-1;i>=0;i--){
        sum+=1.0/A.at(i);
    }
    cout<<1./sum<<endl;
}

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

int main() {
  int X;
  cin >> X; 
  
  if (X/100 * 5 >= X%100) {
    cout << 1 << endl;
  } else {
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,n) for (int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
int gcd(int a,int b){
	return a%b==0? b:gcd(b,a%b);
}
int g,m=0,a[100005];
int main()
{
	int n,k;
	cin>>n>>k;
	scanf("%d",&a[1]);
	g=m=a[1];
	for (int i=2;i<=n;i++){
		scanf("%d",&a[i]);
		g=gcd(max(a[i],g),min(a[i],g));
		m=max(m,a[i]);
	}
	if (k<=m&&k%g==0) cout<<"POSSIBLE";
	else cout<<"IMPOSSIBLE";
}

Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

vector<int> a;
vector<int> b;
int id=2;
int N;
int yukuri(int n,int m){
  if(n<m) swap(n,m);
  while(m>0){
    int tmp = n%m;
    n=m;
    m=tmp;
  }
  return n;
}

void add_ab(){
  ++id;
  while(yukuri(id,26)!=1) id++;
  for(int i=0;i<26;i++){
    a.push_back(id);
    b.push_back(i);
  }
}
int F(char y,int id){
  return ((int)(y-'a')*a[id]+b[id])%26;
}
string change(string s,int id){
  for(int i=0;i<(int)s.size()-1;i++){
    if(s[i]==' ') continue;
    s[i]=(char)F(s[i],id)+'a';
  }
  return s;
}

int main(){
  scanf("%d",&N);
  add_ab();

  getchar();
  for(int i=0;i<N;i++){
    char buf[258];
    fgets(buf,sizeof(buf),stdin);
    string s = buf;
    for(int i=0;i<(int)a.size();i++){
      s=change(s,i);
      if(0<=(int)s.find("that") || 0<=(int)s.find("this")){
	printf("%s",s.c_str());
	break;
      }
      //      printf("ng:: %s",s.c_str());
      s=buf;
      if(i==(int)a.size()-1){
	add_ab();
      }
    }
  }
}

Measured memory_bytes: 1264
#include<bits/stdc++.h>
using namespace std;
long long a[200001];

void write_128(__int128 a) 

{

    if(a < 0) putchar('-'), a *= -1;

    if(a >= 10) write_128(a / 10);

    putchar(a % 10 + '0');

}
int main()
{
	int n;
	cin>>n;
    __int128 sum=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=1;i<=n;i++)
		ans+=a[i]*(sum-a[i]);
	write_128((ans/2)%(unsigned long long)1000000007);
	return 0;
}

Measured memory_bytes: 5092
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
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; }
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }

struct Edge {
    ll from, to, weight;
    Edge() : from(0), to(0), weight(0) {}
    Edge(ll f, ll t, ll w) : from(f), to(t), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &g, ll a, ll b, ll w = 1){
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}

vector<ll> dijkstra(Graph &g, ll s){
    vector<ll> dist(g.size(), INF);
    priority_queue<P, vector<P>, greater<P>> que;
    dist[s] = 0;
    que.emplace(dist[s], s);
    
    while(!que.empty()){
        ll cost, idx;
        tie(cost, idx) = que.top();
        que.pop();
        if(dist[idx] < cost) continue;
        for(auto &e : g[idx]){
            auto next_cost = cost + e.weight;
            if(dist[e.to] <= next_cost) continue;
            dist[e.to] = next_cost;
            que.emplace(dist[e.to], e.to);
        }
    }
    return dist;
}

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

    ll N;
    cin >> N;
    Graph G(N);
    rep(i, N - 1){
        ll u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        add_edge(G, u, v, w);
    }
    vector<ll> d = dijkstra(G, 0);

    rep(i, N) print(d[i] % 2);

    return 0;
}

Measured memory_bytes: 10112
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

const int MAX_N = (int)1e5 + 5;

int p[MAX_N];

class UNION_FIND{
public:
	vector<int> a;
	UNION_FIND(int n){
		a.clear();
		a.resize(n, -1);
	}

	~UNION_FIND(){
		a.clear();
	}

	int find(int x){
		if (a[x] < 0){
			return x;
		}else{
			return (a[x] = find(a[x]));
		} // end if
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if (x != y){
			a[x] += a[y];
			a[y] = x;
		} // end if
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}

	int size(int x){
		return -a[find(x)];
	} // end if
};


int main()
{
	memset(p, -1, sizeof(p));
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M; cin >> N >> M;
	rep (i, N){
		cin >> p[i];
		--p[i];
	} // end rep
	
	UNION_FIND uf(N);
	rep (i, M){
		int x, y; cin >> x >> y;
		--x, --y;
		uf.unite(x,y);
	} // end rep

	int res = 0;
	rep (i, N){
		if (uf.same(i, p[i])){
			++res;
		} // end if
	} // end rep

	cout << res << endl;

	return 0;
}

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

int n,m,x,total1=0,total2=0,a[101];

int main(){
    cin>>n>>m>>x;
    total1=0;
    total2=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        if(a[i]<x){
            total1++;
        }else if(a[i]>x){
            total2++;
        }
    }
    if(total1>total2){
        cout<<total2<<endl;
    }else{
        cout<<total1<<endl;
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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; }

long long N,middle,ans=0,temp=0;

int main(){
    cin>>N;
    long long A[N];
    rep(i,N){
        cin>>A[i];
        A[i]-=i+1;
    }
    sort(A,A+N);
    middle=A[(N-1)/2];
    rep(i,N){
        ans+=abs(A[i]-middle);
    }
    out(ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
ll digits(ll x){
  ll length = 0;
  while (x > 0){
    x /= 10;
    length++;
  }
  return length;
  if (x == 0) return 0;
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
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;
}

int main(){
  cout << fixed << setprecision(15);

  string s; cin >> s;

  ll ans = 0;
  //string ans;

  rep(i, s.size() / 2) if (s[i] != s[s.size() - 1 - i]) ans++;

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

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

using namespace std;

#define ll long long
#define ld long double
#define P pair<ll, ll>

#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

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

#define sortAl(v) sort(all(v))
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())

#define cout(n) cout << fixed << setprecision(n)

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

template <class T>
inline void chmax(T &a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T &a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
#define INF LLONG_MAX

// 最小公倍数
ll lcm(ll a, ll b) {
  ll r, x;

  // a >= b
  if (a < b) {
    swap(a, b);
  }

  x = a * b;

  // ユークリッドの互除法
  r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }

  return x / b;
}

ll a, b;

//倍数の数
ll num_m(ll v) {
  ll first = v * (a / v);
  if (first < a) {
    first += v;
  }
  ll last = v * (b / v);

  if (last >= first) {
    return (last - first) / v + 1;
  } else {
    return 0;
  }
}

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

  ll c, d;
  cin >> a >> b >> c >> d;

  ll l = lcm(c, d);

  cout << (b - a + 1 - num_m(c) - num_m(d) + num_m(l)) << endl;

  return 0;
}


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N;
double dp[310][310][310];

double solve(int A, int B, int C) {
    double &val = dp[A][B][C];
    if(val >= 0) return val;
    if(A == 0 and B == 0 and C == 0) return val = 0;

    // 出るまで引くやつ
    double add = 1.0 * N / (A + B + C);

    val = 0;
    if(A) {
        val += (solve(A-1, B+1, C) + add) * A / (A + B + C);
     }
    if(B) {
        val += (solve(A, B-1, C+1) + add) * B / (A + B + C);
    }
    if(C) {
        val += (solve(A, B, C-1) + add) * C / (A + B + C);
    }
    return val;
}

signed main() {
    cin >> N;

    int cnt[3] = {};
    for(int i=0; i<N; i++) {
        int val; cin >> val;
        val--;
        cnt[val]++;
    }

    fill(dp[0][0], dp[305][0], -1);
    printf("%.12f\n", solve(cnt[2], cnt[1], cnt[0]));
    return 0;
}


Measured memory_bytes: 229632
//  main.cpp
//  CppTest

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    
    /////////////////////
    // Write code below /
    /////////////////////
    string a, b, c;
    cin >> a >> b >> c;
    cout << "A" << b.at(0) << "C" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#define strtok_r strtok_s
#endif

#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)            __typeof__((c).rbegin())
#define RFOREACH(it, c)     for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)           REPEAT(i, 0, n)
#define RREP(i, n)          RREPEAT(i, 0, n)
#define REPEAT(i, k, n)     for(int i = (k); i < ((k)+(n)); ++i)
#define RREPEAT(i, k, n)    for(int i = (k)+(n)-1; i >= (k); --i)
#define FROMTO(i,f,t)       for(int i = f; i < t; i++)
#define ALL(c)              (c).begin(), (c).end()
#define LLPOW(p1,p2)        ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)          (sizeof(A)/sizeof((A)[0]))
#define CIN_NO_SYNC         do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)           fgets((p), sizeof(p), stdin)
#define CHOMP(p)            do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n' || *_q == '\r') *_q = 0; } while(0)
#define FILL(m,v)           memset(m, v, sizeof(m))
#define mp                  make_pair
#define pb                  push_back
template<class _T> _T MAX(_T p1,_T p2){return (p1>p2)?p1:p2;} 
template<class _T> _T MIN(_T p1,_T p2){return (p1<p2)?p1:p2;} 
template <class _Tv> inline string join(const _Tv &v,string sep=" "){
    ostringstream s;FOREACH(it,v){if(it!=v.begin())s<<sep;s<<*it;};return s.str();
}

typedef long long ll;
typedef unsigned long long ull;
typedef double D;
typedef complex<D> P;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define X real()
#define Y imag()
#define EPS (1e-9)
#define DEQ(p1,p2) (abs((p1)-(p2)) < EPS)

#ifdef _DEBUG
template<class _Tv> inline void _prfe(const char *_n,const _Tv _c,bool _p=false){
    ITER(_c) _it=_c.begin();
    if(_p){cout<<_n<<" = ["<<endl;for(;_it!=_c.end();++_it)cout<<"    "<<*_it<<endl;cout<<"]"<<endl; }
    else{cout<<_n<<" = [ "<<*_it++;for(;_it!=_c.end();++_it)cout<<", "<<*_it;cout<<" ]"<<endl; }
}
#define pf printf
#define pr(n) do{cout<<#n" = "<<(n)<<endl;}while(0)
#define prfe(n) _prfe(#n, n)
#define prfep(n) _prfe(#n, n, true)
#define dbgchk(n) do{if(n)throw;}while(0)
#else
#define pf(...) /* */
#define pr(...) /* */
#define prfe(...) /* */
#define prfep(...) /* */
#define dbgchk(...) /* */
#endif

int main(){
    int n;
    while(cin >> n && n){
        double min = 1e9; int id = -1;
        REP(i,n){
            int n, h, w;
            cin >> n >> h >> w;
            double bmi = abs(22 - 10000.0 * w / (h*h));
            if(min > bmi || (abs(min-bmi) < EPS && id > n)){
                min = bmi; id = n;
            }
        }
        cout << id << endl;
    }
    return 0;
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cn1=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        int cn2=0;
        for(int j=2;j<=sqrt(x);j++){
            if(x%j==0) cn2++;
        }
        if(cn2==0) cn1++;
    }
    cout<<cn1<<endl;
}


Measured memory_bytes: 3076
N = int(raw_input())
S = raw_input()
slist = []
for i in range(0, N):
	slist.append(S[i])
min = slist.count('E')
if slist[0] == 'E':
	min = min - 1
cnt = min
for i in range(1, N):
	if slist[i] == 'E':
		cnt = cnt - 1
	if slist[i-1] == 'W':
		cnt = cnt + 1
	if cnt < min:
		min = cnt

print min

Measured memory_bytes: 14908
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <functional>

using lint = long long;

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

void solve() {
    int n;
    std::cin >> n;
    std::vector<lint> xs(n);
    for (auto& x : xs) std::cin >> x;

    std::vector<int> idxs(n);
    std::iota(idxs.begin(), idxs.end(), 0);
    std::sort(idxs.begin(), idxs.end(),
              [&](int i, int j) { return xs[i] > xs[j]; });

    auto dp = vec(n, vec(n, -1LL));
    std::function<lint(int, int)> dfs =
        [&](int l, int r) -> lint {
        if (l + r == n) return 0;

        auto& ret = dp[l][r];
        if (ret != -1) return ret;

        int i = idxs[l + r],
            li = l, ri = n - 1 - r;

        ret = std::max(dfs(l + 1, r) + xs[i] * std::abs(i - li),
                       dfs(l, r + 1) + xs[i] * std::abs(i - ri));
        return ret;
    };

    std::cout << dfs(0, 0) << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 34884
s = gets.to_i; arr = []; ans = 0
arr[0] = s; i = 1
while ans == 0 do
  if arr[i-1].even?
    arr[i] = arr[i-1]/2
  elsif arr[i-1].odd?
    arr[i] = arr[i-1]*3+1
  end
  0.upto(i-1) do |j|
    if arr[j] == arr[i]
      ans = i + 1
    end
  end
  i += 1
end
puts ans


Measured memory_bytes: 1788
#写経
#https://atcoder.jp/contests/abc172/submissions/14794920

MOD = 10**9 + 7

def resolve():
    N,M = map(int,input().split())
    a = 1
    d = [1]
    for i in range(N):
        d.append(((M-N+i)*d[i]+i*d[i-1])%MOD)
        a=a*(M-i)%MOD
    print(a*d[-1]%MOD)
resolve()

Measured memory_bytes: 28708
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readIntList() = readLine()!!.split(" ").map(String::toInt)
fun readLongList() = readLine()!!.split(" ").map(String::toLong)
fun <T> Array<Array<T>>.print() {
    this.forEach {
        println(it.joinToString(" "))
    }
}

fun main() {
    val s = readString()
    val t = readString()
    var cnt = 0
    for (i in s.indices) {
        if (s[i] != t[i]) cnt++
    }
    println(cnt)
}

Measured memory_bytes: 39832
use std::io;

#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

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

#[allow(dead_code)]
fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

fn main() {
    let (x,a,b):(usize,usize,usize);
    input!(x);
    input!(a);
    input!(b);
    p((x-a)%b);
}

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

int diff(char x, char y, char z) {
    if (x == y) {
        if (y == z) return 0;
        else return 1;
    }

    if (x == z) return 1;
    if (y == z) return 1;
    return 2;
}
int main() {
    int N;
    vector<string> strs;

    cin >> N;
    for (int i = 0; i < 3; i++) {
       string temp;
       cin >> temp;
       strs.push_back(temp);
    }

    int min = 0;
    for (int i = 0; i < N; i++) {
        min += diff(strs[0][i], strs[1][i], strs[2][i]);
    }
    cout << min << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
        int n, x, result;

        while(1){
                scanf("%d %d", &n, &x);

                if(n == 0 && x == 0) break;

                result = 0;

                for(int i=1; i <= n; i++){
                        for(int j=i+1; j <= n; j++){
                                for(int k=j+1; k <= n; k++){
                                        if((i + j + k) == x){
                                                result++;
                                        }
                                }
                        }
                }

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

        }
        return 0;
}


Measured memory_bytes: 2104
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;



int main()
{
	int s, count = 1;
	cin >> s;

	while (1)
	{
		if (s == 4 || s == 2 || s == 1)break;

		if (s % 2 == 0) s = s / 2;
		else s = 3 * s + 1;
		count++;
	}

	cout << count + 3 << endl;
}

Measured memory_bytes: 256