akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;
 
public class Main {
 
    void solve() throws IOException {
        int N = ni();
        long D = nl();
        long ans = 0;
        for (int i = 0; i < N; i++) {
            long x = nl();
            long y = nl();
            if(D*D >= (x*x + y*y)) ans ++;
        }
        out.println(ans);
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);
    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 55252
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;

ll x[10],y[10];
int main(){
    ll n;
    ld ans=0;
    cin>>n;
    rep(i,0,n)cin>>x[i]>>y[i];
    rep(i,0,n){
      rep(j,0,n){
        ans+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
      }
    }

  cout<<fixed<<setprecision(12)<<ans/n;
}

Measured memory_bytes: 256
let n = Scanf.scanf " %d" (+) 0
let a_s = Array.init n @@ fun _ -> Scanf.scanf " %d" (+) 0
let ds = Array.init n @@ fun i -> Scanf.scanf " %d" @@ fun b -> a_s.(i) - b
let sl, nl = Array.fold_left (fun (s, n) d -> if d < 0 then s + abs d, n + 1 else s, n) (0, 0) ds
let s = ref 0
let f n = Printf.printf "%d\n" n; exit 0
let _ = if sl = 0 then f 0 else Array.(sort (fun x y -> y - x) ds; iteri (fun i d -> if d > 0 then (s := !s + d; if !s >= sl then f @@ nl + i + 1) else f ~-1) ds)

Measured memory_bytes: 6144
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, mod = 1e9 + 7;
vector<int> G[maxn];
int f[maxn];
ll dp[maxn][2];
void add(int u, int v){
    G[u].push_back(v);
    G[v].push_back(u);
}
void dfs(int u){
    for(auto v:G[u]){
        if(v == f[u])continue;
        f[v] = u;
        dfs(v);
    }
}
ll DP(int u, int s){
    if(dp[u][s])return dp[u][s];
    dp[u][0] = dp[u][1] = 1;
    for(auto v:G[u]){
        if(v == f[u])continue;
        dp[u][0] = (dp[u][0] * (DP(v,0) + DP(v,1))) % mod;
        dp[u][1] = (dp[u][1] * DP(v,0)) % mod;
    }
    return dp[u][s];
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n-1; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    dfs(1);
    cout<<(DP(1, 0) + DP(1, 1)) % mod<<endl;
    return 0;
}


Measured memory_bytes: 14592
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
const int INF = 1e9;
using namespace std;
typedef long long ll;


int main()
{
    ll n;
    cin >> n;
    ll a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ll sum = 0,ans1 = 0,ans2 = 0;
    for(ll i = 0; i < n; i++){
        sum += a[i];
        if(i % 2 == 0 && sum <= 0){
            ans1 += (1 - sum);
            sum = 1;
        }else if(i % 2 == 1 && sum >= 0){
            ans1 += sum + 1;
            sum = -1;
        }
    }
    sum = 0;
    for(ll i = 0; i < n; i++){
        sum += a[i];
        if(i % 2 == 1 && sum <= 0){
            ans2 += (1 - sum);
            sum = 1;
        }else if(i % 2 == 0 && sum >= 0){
            ans2 += sum + 1;
            sum = -1;
        }
    }
    cout << min(ans1,ans2) << endl;
}

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

using namespace std;
typedef long long ll;

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

    ll n; cin >> n;
    vector<ll> a(n), b(n), c(n);
    vector<ll> bCount(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        if (b[i] > a[n - 1]) {
            if (i == 0) bCount[i] = n;
            else bCount[i] = n + bCount[i - 1];
        } else {
            int lb = 0, ub = n - 1;
            while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (a[mid] < b[i]) lb = mid;
                else ub = mid;
            }
            if (a[lb] >= b[i]) {
                bCount[i] = 0;
                continue;
            }
            if (i == 0) bCount[i] = lb + 1;
            else bCount[i] = lb + 1 + bCount[i - 1];
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int ci; cin >> ci;
        if (ci > b[n - 1]) {
            ans += bCount[n - 1];
        } else {
            int lb = 0, ub = n - 1;
            while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (b[mid] < ci) lb = mid;
                else ub = mid;
            }
            if (b[lb] >= ci) continue;
            ans += bCount[lb];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
#define lli long long int
#define pb push_back
#define rep(i,s,n) for(lli i=s;i<n;i++)
#define irep(i,n,s) for(lli i=n-1;i>=s;i--)
#define mp make_pair
#define mod 1000000007
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio;
    cin.tie(NULL);
    int i, j, k, m, n, t;
    cin >> n;
    int a[n];
    rep(i, 0, n)
    {
        cin >> a[i];
    }
    int dp[n + 1];
    dp[0] = 0;
    dp[1] = abs(a[0] - a[1]);
    rep(i, 2, n)
    {

        if (dp[i - 1] + abs(a[i - 1] - a[i])  <=  dp[i - 2] + abs(a[i - 2] - a[i]))
        {
            dp[i] = dp[i - 1] + abs(a[i - 1] - a[i]);
        }
        else
        {
            dp[i] = dp[i - 2] + abs(a[i - 2] - a[i]);
        }

    }
    cout << dp[n - 1] << "\n";

}




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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using vec_b = vector<bool>;
using vec_str = vector<string>;

#define INF (1LL << 60)
#define MOD 1000000007

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back


int main()
{
    ll N, K;
    cin >> N >> K;
    vec V(N);
    REP(i,0,N) cin >> V[i];

    deque<ll> D;
    priority_queue<ll,vec,greater<ll>> E;

    ll R = MIN(N,K), m = -INF;
    REP(i,0,R+1) {
        REP(a,0,i+1) {
            ll b = i - a;
            D.clear();
            while(!E.empty()) E.pop();
            FORR(v,V) D.pb(v);
            REP(j,0,a) {
                ll w = D.front();
                D.pop_front();
                E.push(w);
            }
            REP(j,0,b) {
                ll w = D.back();
                D.pop_back();
                E.push(w);
            }
            ll sum = 0, c = 0;
            while(!E.empty() && c < K - i) {
                ll w = E.top();
                if(w > 0) break;
                E.pop();
                ++c;
            }
            while(!E.empty()) {
                ll w = E.top();
                E.pop();
                sum += w;
            }
            m = MAX(m,sum);
        }
    }
    _PR(m);

    return 0;
}

/*



*/

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

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

int main() {
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.rbegin(), t.rend());
  if (s < t)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, a,b;
vector<int> v[2020];
int ans[2020];
void solve(){
	cin >> n >> a >> b;
	a--;b--;
	for(int i = 0; i < n; i++){
		if(i != n-1) v[i].push_back(i+1);
		if(i != 0) v[i].push_back(i-1);
	}
	v[a].push_back(b);
	v[b].push_back(a);
	
	for(int i = 0; i < n; i++){
		queue<P> q;
		q.push({0,i});
		bool used[2020] = {};
		used[i] = 1;
		while(!q.empty()){
			P p = q.front(); q.pop();
			int c = p.first, x = p.second;
			ans[c]++;
			for(int j = 0; j < v[x].size(); j++){
				int nx = v[x][j];
				if(used[nx]) continue;
				used[nx] = 1;
				q.push({c+1,nx});
			}
		}
	}
	
	for(int i = 1; i < n; i++){
		cout << ans[i]/2 << endl;
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 384
//templates
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <queue>
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define sort_key(struct_name,key_name) [](const struct_name &x, const struct_name &y){return x.key_name < y.key_name;}
#define pb(x) push_back(x)
typedef long long ll;
const long long MOD = 1e9 + 7;
using namespace std;

//main
int main(){
    int N; cin >> N;
    vector<ll> d(N);
    rep(i,N) cin >> d[i];
    ll ans = 0;
    rep(i,N){
        rep(j,N){
            if(i != j) ans += d[i]*d[j];
        }
    }
    cout << ans/2 << endl;
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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 int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;


char G[10][10];
ll h,w;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>h>>w;
  rep(i,h) rep(j,w) cin>>G[i][j];
  
  
  rep(i,h-1){
    rep(j,w-1){
      if(G[i][j]=='#'&&G[i+1][j]=='#'&&G[i][j+1]=='#'){
        cout<<"Impossible"<<endl;
        return 0;
      }
      if(G[i+1][j+1]=='#'&&G[i+1][j]=='#'&&G[i][j+1]=='#'){
        cout<<"Impossible"<<endl;
        return 0;
      }
    }
  }
  cout<<"Possible"<<endl;
  
}

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

using namespace std;
long long int n,k;

int dp[1000001];

void test()
{
    int x,y;
    cin>>x>>y;

    for(int i=0;i<x+1;i++)
    {
        int b=x-i;

        if(2*i+4*b==y)
        {
            cout<<"Yes\n";
            return ;
        }
    }

    cout<<"No\n";

}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);

    test();

    return 0;
}


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

#define FOR(i, a, b)   for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b)  for(int i = (a); i > (b); --i)

typedef long long ll;

ll N,ans=0;
void dfs(ll x,int a,int b, int c){
    if(x>N)return;
    if(a&&b&&c) ans++;
    dfs(x*10+3,1,b,c);
    dfs(x*10+5,a,1,c);
    dfs(x*10+7,a,b,1);
}

int main()
{
    cin>>N;
    dfs(0,0,0,0);



    

    cout<<ans<<endl;
}



Measured memory_bytes: 256
n = int(input())
lis = []
for i in range(n):
    lis.append(int(input()))
val = set()
i = 1
cnt =0
while True:
    #print(i)
    cnt += 1
    if lis[i-1] == 2:
        break
    if  lis[i-1] in val:
        cnt = -1
        break
    val.add(lis[i-1])
    i = lis[i-1]

print(cnt)


Measured memory_bytes: 13220
#include<stdio.h>

int main(){
	long N, M;
	long re = 0, add = 0;
	scanf("%ld %ld", &N, &M);
	if( N == M/2 ){
		re = N;
	}else if( N > M/2 ){
		re = M / 2;
	}else if( N < M/2 ){
		re = N;
		long nM = M - 2 * N;
		add = nM / (2+1+1);
	}
	printf("%ld\n", re + add);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define repin(a,n) vector<ll> a(n);rep(i,n){cin>>a[i];}
#define in(a) ll a;cin>>a;
#define ins(a) string a;cin>>a;
#define ind(a) double a;cin>>a;
template<class T>
inline void out(T a){cout<<a<<endl; }
inline void out(double a){ printf("%.10f\n", a);} 

int main()
{
    ins(s);

    rep(i,s.size()-1){
        if(s[i]==s[i+1]){
            out("Bad");
            return 0;
        }
    }

    out("Good");
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000

int parent[MAX], left[MAX], right[MAX];
int n, D[MAX], H[MAX];

int getDepth(int u){
  int d = 0;
  while(parent[u] != -1){
    u = parent[u];
    d++;
  }
  return d;
}

void setDepth(int u, int p){
  D[u] = p;
  if(right[u] != -1){
    setDepth(right[u], p+1);
  }
  if(left[u] != -1){
    setDepth(left[u], p+1);
  }
}

int setHeight(int u){
  int h1 = 0;
  int h2 = 0;
  if( right[u] != -1){
    h1 = setHeight(right[u]) + 1;
  }
  if( left[u] != -1){
    h2 = setHeight(left[u]) + 1;
  }
  return H[u] =(h1 > h2 ? h1 : h2);
}

int setSibling(int u){
  if(parent[u] == -1) return -1;
  if(left[parent[u]] != u && left[parent[u]] != -1) return left[parent[u]];
  if(right[parent[u]] != u && right[parent[u]] != -1) return right[parent[u]];
  return -1;
}

void printChildren(int u){

  int i, c;
  int deg = 0;

  printf("node %d: ", u);
  printf("parent = %d, ", parent[u]);
  printf("sibling = %d, ", setSibling(u));

  if(left[u] != -1) deg++;
  if(right[u] != -1) deg++;
  printf("degree = %d, ", deg);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);

  if(parent[u] == -1) printf("root\n");
  else if(left[u] == -1 && right[u] == -1) printf("leaf\n");
  else printf("internal node\n");
}

int main(){
  int i, d, v, l, r;
  scanf("%d", &n);
  for(i = 0 ; i < n ; i++)  parent[i] = left[i] = right[i] = -1;

  for( i = 0 ; i < n ; i++){
    scanf("%d", &v);
    scanf("%d", &l);
    scanf("%d", &d);
    left[v] = l;
    right[v] = d;
    if(l != -1 ) parent[l] = v;
    if(d != -1 ) parent[d] = v;
  }
  for(i = 0; i < n; i++){
    if( parent[i] == -1) r = i;
  }

  setDepth(r, 0);
  setHeight(r);

  for(i = 0 ;i < n; i++) printChildren(i);

  return 0;
}


Measured memory_bytes: 2104
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N, K = zz()
# if(N >= K):
#     ans = (N-K+1)/N
# else:
#     ans = 0
ans = 0.0
for n in range(1, N+1):
    # x = max(int(np.log2(K / n)) + 1, 0)
    x = 0
    while (n < K):
        n *= 2
        x += 1
    # print('n=', n, 'x=', x)
    tmp = 1/N * pow(1/2, x)
    ans += tmp
print(ans)


Measured memory_bytes: 27056
n=int(input())
a = list(map(int, input().split()))

max_a=max(a)
min_a=min(a)
max_ind=a.index(max_a)
min_ind=a.index(min_a)

ans=[]
if abs(max_a) >= abs(min_a):
    ans.append([max_ind+1,1])
    ans.append([max_ind+1,1])

    for i in range(n-1):
        ans.append([i+1,i+2])
        ans.append([i+1,i+2])
else:
    ans.append([min_ind+1,n])
    ans.append([min_ind+1,n])

    for i in reversed(range(n-1)):
        ans.append([i+2,i+1])
        ans.append([i+2,i+1])

print(len(ans))
for a in ans:
    print(*a)

Measured memory_bytes: 38384
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MMOD 998244353
#define MAX 2010101
using namespace std;
using Edge=pair<ll,ll>;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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;}
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  string S,T;
  ll Q;
  cin>>S>>T>>Q;
  
  ll NS=(ll)S.size(),NT=(ll)T.size();
  ll CS[NS+1]={},CT[NT+1]={};
  
  REP(i,NS) CS[i+1]=(CS[i]+S[i]-'A'+1)%3;
  REP(i,NT) CT[i+1]=(CT[i]+T[i]-'A'+1)%3;
  
  REP(q,Q){
    ll A,B,C,D,ans=0;
    cin>>A>>B>>C>>D;
    if((CS[B]-CS[A-1]-CT[D]+CT[C-1])%3==0) COYE;
    else CONO;
  }
  return 0;
}

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

using namespace std;
long long N, K, D;


int main(){
    cin>>N>>K>>D;
    if (abs(N)/D>K) cout<<abs(N)-K*D;
    else {
        long long m=K-abs(N)/D;
        if (m%2==0) cout<<abs(N)%D;
        else cout<<abs(abs(N)%D-D);
    }
}



Measured memory_bytes: 3628
// abc066_b
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    string S;
    cin >> S;
    int N = S.size();

    int x = N % 2 == 0 ? N/2-1 : N/2;
    REPN_REV(i, 1, x+1){
        if (S.substr(0, i) == S.substr(i, i)){
            print(2*i);
            break;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define test int t ; cin>>t ; while(t--)
#define ll long long
#define inp(n) cin>>n;
#define loopp(i,a,b) for(ll i=a;i<b;i++)
#define loopn(i,a,b) for(ll i=a;i>=b;i--)

int main()
{
    int n;inp(n);
    ll arr[n];ll ans=0;
    loopp(i,0,n)
    inp(arr[i]);
    sort(arr,arr+n,greater<int>());
    map<int,int> mp;
    map<ll,int>pos;
    loopp(i,0,n)
        mp[arr[i]]=i;
    //int pos[n]={0};
    pos[arr[0]]=1;
    ll c=arr[0];
    //cout<<arr[0]<<" GH"<<c<<endl;
    loopp(i,1,n)
    {
        if(c==arr[i])
        {
            pos[arr[i]]+=1;
            ans+=c;
            //cout<<"DD: "<<ans<<endl;
        }
        else
        {
            pos[c]-=1;
            ans+=c;
            pos[arr[i]]+=2;
            if(pos[c]==0)
            {
                int j=mp[c];
                if(j+1<n)
                    c=arr[j+1];
            }
            //cout<<"EE: "<<ans<<endl;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 26984
#include <bits/stdc++.h>
using namespace std;
vector<int> notes = {10000, 5000, 1000};
int main(){
	int n, k;
	cin>>n>>k;
	for(int i = 0; i <= n; ++i){
		for(int j = 0; j <=n; ++j){
			long val = k - (notes[0] * i + notes[1] * j);
			if(val < 0)continue;
			if(k % 1000 == 0 && k >= 1000){
				int res = val / 1000;
				if(i + j + res == n){
					cout<<i<<" "<<j<<" "<<res<<endl;
					return 0;
				}
			}
		}
	}
	cout<<-1<<" "<<-1<<" "<<-1<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <cstdio>      /* printf, scanf, puts, NULL */
#include <cstdlib>     /* srand, rand */
#include <ctime>       /* time */
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>

using namespace std;

long long n;

int numDigits(long long number) {
    int digits = 0;
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

int getMinNumber(int res, long long a, long long b) {
    int r1 = numDigits(a);

    if (numDigits(b) > r1) {
        r1 = numDigits(b);
    }

    return std::min(r1,res);
}

int main() {

    std::ios::sync_with_stdio(false);
	// freopen("test.txt", "r", stdin);

    cin >> n;

    int res = numDigits(n);

    long long m = 1;

    while (m*m <= n) {

        if (n%m == 0) {
            res = getMinNumber(res, m, n/m);
        }

        m++;
    }
    cout << res;

    return 0;
}



Measured memory_bytes: 256
/*author - Ashutosh Chitranshi*/
#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;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 1000000007
#define ordered_set tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
void dfs(vl adj[],ll u,bool vis[])
{
    vis[u] = true;
    for(ll x : adj[u])
    {
        if(!vis[x])
            dfs(adj,x,vis);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,m;
    cin >> n >> m;
    vl adj[n+1];
    for(int i=0;i<m;i++)
    {
        ll u,v;
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    ll count = 0ll;
    bool vis[n+1];
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(adj,i,vis);
            count++;
        }
    }
    cout << count-1 << nl;
    return 0;
}

Measured memory_bytes: 11680
#include<bits/stdc++.h>
#define ll long long int
#define vi vector< int >
#define vii vector< pair< int,int > >
#define vc vector< char >
#define vvi vector < vector< int > >
#define vvl vector < vector< ll > >
#define vvc vector < vector< char > >
#define vl vector< ll >
#define vll vector< pair< ll,ll > >
#define pii pair< int, int >
#define pll pair<ll, ll>
#define pf push_front
#define pb push_back
// #define range(c) c.begin(), c.end()
// #define ranger(c) c.rbegin(), c.rend()
#define all(c) c.begin(), c.end()
#define allr(c) c.rbegin(), c.rend()
#define forn(i, n) for(ll i = 0; i < n; ++i)
#define fornr(i, n) for(ll i = n-1; i >= 0; --i)
#define foro(i, n) for(ll i = 1; i <= n; ++i)
#define foror(i, n) for(ll i = n; i >= 1; --i)
#define endl '\n'
#define MOD 998244353
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pr(a) for(auto it :a) cout << (it) << " "; cout << endl;
#define pr2(a) for(int i = 0; i<a.size(); ++i){ for(int j = 0; j<a[i].size(); ++j) cout << a[i][j] << ' '; cout << endl;}
#define test ll T; cin >> (T); while(T--)

#define present(container, element) (container.find(element) != container.end())
// for set and maps
#define cpresent(container, element) (find(all(container),element) != container.end())
// for vectors

using namespace std;

bool comp(pii &a, pii &b) {		// if returns false, then swap occurs
	return (a.first < b.first) || ((a.first == b.first) && a.second > b.second);
}

int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("/home/shivam/input.txt", "r", stdin);
// 	freopen("/home/shivam/output.txt", "w", stdout);
// 	freopen("/home/shivam/error.txt", "w", stderr);
// #endif

	FIO;

	int n, w;
	cin >> n >> w;
	// vi w(n), v(n);
	vector< pii > wv(n);		// weight, value
	forn(i, n)
	cin >> wv[i].first >> wv[i].second;

	sort(all(wv), comp);

	// pr(w);
	// pr(v);
	// forn(i, n) {
	// 	cout << wv[i].first << ' ' << wv[i].second << endl;
	// }

	vvl dp(n, vl(w + 1, 0));

	for (int j = 0; j <= w; ++j) {
		if (j >= wv[0].first)
			dp[0][j] = wv[0].second;
		else
			dp[0][j] = 0;
	}

	for (int i = 1; i < n; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (j >= wv[i].first)	//can take this item
				dp[i][j] = max(dp[i - 1][j - wv[i].first] + wv[i].second, dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}

	// pr2(dp);
	cout << dp[n - 1][w] << endl;

	return 0;
}


Measured memory_bytes: 82212
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define rep(i,n) for(int i=0;i<n;i++)
#define INF (1<<30)
#define LLINF (1LL<<60)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
    int n,a[200005];
    ll k;
    cin>>n>>k;
    rep(i,n){
        cin>>a[i];
        a[i]--;
    }
    int check[200005]={},nowtown=0,count=1;//check[i]:1回目に町iを通るときのカウント
    int roop;
    int before;
    int roopstart;
    check[0]=1;
    while(1){
        count++;
        nowtown=a[nowtown];
        if(check[nowtown]!=0){
            roop=count-check[nowtown];
            before=check[nowtown]-1;
            roopstart=nowtown;
            break;
        }
        else{
            check[nowtown]=count;
        }
    }

    if(k<=before){
        int t=0;
        for(int i=0;i<k;i++){
            t=a[t];
        }
        cout<<t+1;
    }
    else{
        k-=before;
        k%=roop;
        int t=roopstart;
        for(int i=0;i<k;i++){
            t=a[t];
        }
        cout<<t+1;
    }
    return 0;
}


Measured memory_bytes: 5084
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define REP(i,n) for(int i = 0 ; i < n ; i ++) 
#define ms(a,c) memset(a,c,sizeof a)
void min_self(int&x , int y) {
    x = min(x,y);
}
int n , k , *a ;
int dp[100001] ;
int f(int i) {
    if(i==n-1){
        return 0;
    }
    int &ret = dp[i] ;
    if(ret!=-1)return ret;
    ret = INT_MAX;
    int j = 1;
    while(j <= k and i + j < n) {
        min_self(ret, abs(a[i] - a[i+j]) + f(i+j));
        j++;
    }
    return ret ;
}
int32_t main() {
    cin >> n >> k;
    a = new int[n] ;
    REP(i,n) {
        cin >> a[i] ;
    }
    ms(dp,-1);
    cout << f(0) << endl ;
    return 0;
}

Measured memory_bytes: 8064
#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;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

// template from zscoder

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    ll n,a,b;
    cin >> n >> a >> b;
    ll c = a+b;
  	if(c%2==1)cout << "Borys" << endl;
  	else cout << "Alice" << endl;
}

Measured memory_bytes: 384
N, X, Y = gets.chomp.split.map(&:to_i)
d = Array.new(N).map{Array.new(N, 0)}
(N-1).times do |i|
  (i+1..N-1).each do |j|
    d[i][j] = j - i
  end
end

MOVE = [[0, -1], [1, 0], [0, 1], [-1, 0]]
d[X-1][Y-1] = 1
que = [[X-1, Y-1]]
until que.empty?
  i, j = que.shift
  MOVE.each do |mi, mj|
    ni = i + mi
    nj = j + mj
    if 0 <= ni && ni < N && 0 <= nj && nj < N
      nd = d[i][j] + 1
      if nd < d[ni][nj]
        d[ni][nj] = nd
        que << [ni, nj]
      end
    end
  end
end

h = Hash.new(0)
N.times do |i|
  N.times do |j|
    next if d[i][j].zero?

    h[d[i][j]] += 1
  end
end
1.upto(N-1) do |k|
  puts h[k]
end


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

using namespace std;

const int N = 12345;

int n, a[N], b[N];
vector<int> adj[N];
bool visit[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1, x, y; i < n; ++i) {
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n, greater<int>());
  queue<int> q;
  q.push(1);
  visit[1] = true;
  b[1] = a[1];
  int answer = 0, t = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto y : adj[x]) {
      if (!visit[y]) {
        visit[y] = true;
        q.push(y);
        answer += (b[y] = a[++t]);
      }
    }
  }
  cout << answer << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << b[i] << " \n"[i == n];
  }
  return 0;
}

Measured memory_bytes: 1152
e1,e2,e3,e4=map(int,input().split())
if e1==e2==e3==e4:
    print("yes")
elif e1==e2 and e3==e4:
    print("yes")
elif e1==e3 and e2==e4:
    print("yes")
elif e1==e4 and e2==e3:
    print("yes")
else:
    print("no") 


Measured memory_bytes: 5596
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define MOD 1000000007
int main(){
  ll n,m;
  cin>>n>>m;
  vector<ll> a(m),b(m-1);
  for(int i=0;i<m;i++) cin>>a[i];
  if(n>=m){
    cout<<0;
    return 0;
  }
  sort(a.begin(),a.end());
  for(int i=0;i<m-1;i++) b[i]=a[i+1]-a[i];
  sort(b.begin(),b.end());
  ll c=0;
  for(int i=0;i<m-n;i++) c+=b[i];
  cout<<c;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

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

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int N;
  cin >> N;
  vector<int> A(N);
  int odd = 0;
  rep(i, N) {
    cin >> A[i];
    odd += (A[i] % 2);
  }

  if (odd % 2)
    cout << "NO\n";
  else
    cout << "YES\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include <iostream>
#include <set>
 
int main(void){
  int n;cin >> n;
  vector<int> d(n);for(int i=0;i<n;i++) cin >> d[i];
  set<int> s;
  for(int i=0;i<n;i++){
    s.insert(d[i]);
  }
  cout << s.size() <<endl;
  return 0;
}

Measured memory_bytes: 3556
def readinput():
    n,x,m=map(int,input().split())
    return n,x,m

def main(n,x,m):
    ans_list=[]
    hist=[0]*m
    val=x
    count=0
    while hist[val]==0 and count<n:
        ans_list.append(val)
        hist[val]+=1
        val=(val*val)%m
    if count==n:
        loop_start=0
        loop_len=n
    else:
        i=0
        while ans_list[i] != val:
            i+=1
        loop_start=i
        loop_len=len(ans_list)-i 
    # print(ans_list)
    # print(loop_start)
    # print(loop_len)
    ans=sum(ans_list[:loop_start])
    ans+=sum(ans_list[loop_start:])*((n-loop_start)//loop_len)
    ans+=sum(ans_list[loop_start:loop_start+(n-loop_start)%loop_len])
    # ans=sum(ans_list)*(n//loop_len) + sum(ans_list[:n%loop_len])
    return ans

if __name__=='__main__':
    n,x,m=readinput()
    ans=main(n,x,m)
    print(ans)

Measured memory_bytes: 12148
#include <iostream>
#include <cstring>
using namespace std;
string s;
bool flag;
int main()
{
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(i%2)
		{
			if(s[i]=='L' || s[i]=='U' || s[i]=='D')
				continue;
			else
			{
				flag=true;
				break;
			}
		}
		else
		{
			if(s[i]=='R' || s[i]=='U' || s[i]=='D')
				continue;
			else
			{
				flag=true;
				break;
			}
		}
	}
	if(flag)
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    int v[n], c[n];
    for (int i = 0; i < n; i++)
        cin >> v[i];
    for (int i = 0; i < n; i++)
        cin >> c[i];
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] > c[i]) {
            ans += v[i] - c[i];
        }
    }
    cout << ans << endl;
}

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

int main(){
  int N;
  cin >>N;
  int h[N];
  int ma=0;
  for(int i=0;i<N;i++){
    cin >>h[i];
    ma=max(ma,h[i]);
  }
  int ans=0;
  for(int x=0;x<ma;x++){
    int y=0,z=0;
    for(int i=1;i<N;i++){
      if(h[i]>x && h[i-1] <= x){
        y++;
      }
    }
    for(int i=0;i<N-1;i++){
      if(h[i] > x && h[i+1] <= x){
        z++;
      }
    }
        if(z == y && h[0] > x) y++;
    if(z != y) y=max(z,y);

    //cout << x << " " << y  << endl;
    ans += y;
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
     
    while(true){
        int H,W;
        cin >> H >> W;
        if(H == 0 && W == 0){
            break;
        }
         
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(i == 0 || i == H-1 || j == 0 || j == W -1){
                    cout << "#";
                }
                else{
                    cout << ".";
                }
                 
            }
            cout << endl;
        }
         
        cout << endl;
    }
     
    return 0;
}

Measured memory_bytes: 1156
#include<stdio.h>
#include<string.h>

int main(void)
{
	char str1[11], str2[22] = {0};
	int n,i,j,k,res=0,len=0;
	scanf("%s",str1);
	scanf("%d",&n);
	for (i = 0; i < n; i++) {
		k = 0;
		scanf("%s",str2);
		len = strlen(str2);
		for (j = len; j < len * 2; j++)str2[j] = str2[k++];
		if (strstr(str2, str1) != NULL)res++;
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 604
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
using namespace std;

int main() {
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	//cout << fixed << setprecision(10);
	long long int  n, m, a[20000], b, c, d, k, h, w, left = 1, right = 0;
	long long int sc, sr, num2, no[1005][1005] = {}, res = 999999999, count = 0, now = 0, mi = 9999999999;

	string str, t;

	cin >> n;
	while (1) {
		res = 0; 
		now = 0;
		if (n == 0) { return 0; }
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			now += a[i];
			a[i] *= n;
		}
		for (int i = 0; i < n; i++) {
			if (a[i]<=now) {
				res++;
			}
		}
		cout << res << endl;

		cin >> n;
	}
	
}



Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}

ll contest = 26;



int main(){
    ll d; cin >> d;
    vector<ll> c(contest), t(d);
    vector<vector<ll>> s(d, vector<ll>(contest));
    rep(i, contest) cin >> c[i];
    rep(i, d) rep(j, contest) cin >> s[i][j];
    rep(i, d) cin >> t[i];
    
    ll m; cin >> m;
    rep(h, m){
        ll v = 0;
        vector<ll> last(contest, 0);

        ll dd, q; cin >> dd >> q;
        t[dd-1] = q;
        
        rep(i, d){
            v += s[i][t[i]-1];
            last[t[i]-1] = i+1;
            rep(j, contest){
                if(t[i]-1 == j) continue;
                v -= c[j]*((i+1)-last[j]);
            }
        }
        cout << v << endl;
    }    

    return 0;
}

Measured memory_bytes: 3716
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn];
map<int,int>M1,M2;
vector<pair<int,int> >P1 , P2;
int main()
{
  int n;
  scanf("%d",&n);
  for(int i = 0 ; i < n ; i++)
  {
    scanf("%d",&a[i]);
  }
  int t1 = 0 , t2 = 0;
  for(int i = 0 ; i < n ; i += 2)
  {
    M1[a[i]]++;
  }
  for(int i = 1 ; i < n ; i += 2)
  {
    M2[a[i]]++;
  }
  int MAX1 = 0 , MAX2 = 0 , p1 , p2 ;
  for(auto i : M1)
  {
    P1.push_back(make_pair(i.second,i.first));
  }
  P1.push_back(make_pair(0,0));
  P2.push_back(make_pair(0,0));
  for(auto i : M2)
  {
    P2.push_back(make_pair(i.second,i.first));
  }
  sort(P1.begin(),P1.end(),[](pair<int,int>A,pair<int,int>B)
  {
    return A.first > B.first;
  });
  sort(P2.begin(),P2.end(),[](pair<int,int>A,pair<int,int>B)
  {
    return A.first > B.first;
  });
  if(P1[0].second != P2[0].second)
  {
    cout<<n - P1[0].first - P2[0].first<<endl;
  }
  else 
  {
    cout<<min(n - P1[0].first - P2[1].first , n -  P1[1].first - P2[0].first)<<endl;
  }
}

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

int main()
{
    auto cmp = [](const pair<string, int> &a, const pair<string, int> &b) {
        return a.second > b.second;
    };
    string str;
    int n, w, e, l;
    for (int t = 0; ; t++) {
        scanf("%d", &n);
        if (n == 0) break;
        if (t) cout << endl;
        pair<string, int> countries[n];
        for (int i = 0; i < n; i++) {
            cin >> str >> w >> l >> e;
            countries[i].first = str;
            countries[i].second = w * 3 + e;
        }
        sort(countries, countries+n, cmp);
        for (int i = 0; i < n; i++) {
            cout << countries[i].first << "," << countries[i].second << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3300
#include <bits/stdc++.h>
using namespace std;
int main(){
char c;
int n[26]={};
while(cin>>c){
c= tolower(c);
if(isalpha(c)){
n[c-'a']++;
}
}
for(int i=0;i<26;i++){
printf("%c : %d\n",i+'a',n[i]);
}
}


Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long gcd(long a, long b){
    if(a % b == 0){
        return b;
    }else if(a % b == 1){
        return 1;
    }else{
        return gcd(b, a % b);
    }
}

int main(){
    long A,B;
    cin >> A >> B;
    long C = gcd(A,B);
    cout << (A * B) / C << endl;
}

Measured memory_bytes: 256
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`)

    println(sc.next()[0].inc())
}

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: 31384
#include<bits/stdc++.h>
using namespace std;
int N,M;
typedef pair<int,int> P;
vector<int> G[5555];
P K[5555];
bool used[5555];
int dfs(int a){
  used[a] = true;
  int ret = 0;
  for(int i=0;i<(int)G[a].size();i++){
    int to = G[a][i];
    if( used[to] ) continue;
    ret += dfs(to);
  }
  return ret+1;
}
int main() {
  cin >> N >> M;
  for(int i=0;i<M;i++) {
    int a,b;
    cin >> a >> b;
    --a; --b;
    G[a].push_back(b);
  }
  for(int i=0;i<N;i++){
    memset(used,0,sizeof(used));
    used[i] = true;
    K[i].second = i+1;
    K[i].first = -dfs(i);
  }
  sort(K,K+N);
  cout << K[0].second << endl;
  bool f = false;
  for(int i=1;i<N;i++){
    if( K[i-1].first == K[i].first ) f=true;
    cout << K[i].second << endl;
  }
  cout << f << endl;
}

Measured memory_bytes: 2188
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define F first
#define s second
#define int long long		
int x[214514];
double y[214514];
string z[214514];
int sum[214514];
signed main(){
	ic(n)
	rep(0,i,n)cin>>x[i];
	sort(x,x+n);
	int sum=1;
	int ans=0;
	rep(0,i,n){
		if(x[i]==x[i+1])sum++;
		else{
			if(sum%2==1)ans++;
			sum=1;
		}
	}
	c(ans)
}			

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

#define REP(i,s,n) for(int i=s; i<n; ++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

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


int main(){

  ll a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;

  if(a + b < 2 * c){
    cout << x * a + b * y << endl;
  }else{
    if(x >= y) cout << 2 * c * min(x, y) + min(a,  2 * c) * (x - y) << endl;
    else cout << 2 * c * min(x, y) + min(b,  2 * c) * (y - x) << endl;
  }



	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, s: "List[str]"):
    x = 0
    a = 0
    b = 0
    ans2 = 0
    for i in s:
        ans2 += i.count('AB')
        if(i[0] == 'B' and i[-1] == 'A'):
            x += 1
        elif(i[-1] == 'A'):
            a += 1
        elif(i[0] == 'B'):
            b += 1
    
    
    ####   AC1   #####    
    # if(x == 0):
    #     ans1 = min(a,b)
    # else:
    #     ans1 = max(0,x-1)+min(a,b)
    #     if(a > 0 or b > 0):
    #         ans1 += 1
    
    #####    AC2   ####
    ans1 = max(0,x-1) + min(a,b)
    if((a > 0 or b >0) and x > 0):
        ans1 += 1
    
    ####   WA    #############
    # ans1 = max(0,x-1) + min(a,b)
    # if(x != 0):
    #     ans1 += 1 
    

    # ans1 = max(0,x-1) 
    # if(a == b):
    #     ans1 += min(a,b)
    #     if((a > 0 or b > 0) and x != 0):
    #         ans1 += 1
    # else:
    #     if(x == 0):
    #         ans1 += min(a,b)
    #     elif(a > 0 or b > 0):
    #         ans1 += min(a,b)+1 

    # ans2 = 0
    # for i in s:
    #     ans2 += i.count('AB')

    print(ans1+ans2)
    
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [ next(tokens) for _ in range(N) ]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3700