akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

 
//typedef tuple <int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<ll> vll;
 
#define siz(x) (int)(x).size()
#define Y second
#define X first
#define IN insert
#define PB push_back
#define P pop_back
#define PU push
#define PO pop
//#define F find
#define ED end()
#define MP( a, b) make_pair( a, b )
 
//#define MOD 1000000007ll
#define INF 1000000000
#define endl "\n"
#define rep(a,i,b) for (ll i = (a); i < (b); ++i)
#define reps(a,i,b) for (ll i = (a); i <= (b); ++i)
#define repd( num, i, ed ) for(ll (i)= (num)-1; (i) >= ed; --(i))
#define repkt( bg, i, num, kt ) for(ll (i)= (bg); (i) < (num) && (kt); ++(i))
#define repchar( i ) for(char (i)= 48; (i) <= 122; (i)++)   
#define in(n) scanf("%lld", &n)
#define out(n) printf("%lld\n", n)
#define outS(s) printf("%s\n", s)
#define setA(a,n) for(ll i= 0, j= sizeof(a)/sizeof(a[0]); i < j; ++i) a[i]= n;
#define repe(num,i,ed) for(ll (i)= (num); (i) >= ed; --(i))
// const int INF=0x3f3f3f3f;
const db PI=acos(-1);
const ll mod=1e9+7;
const ll N=2e6+5,K=105;
const int si=(1<<20);
const ll add=1e4;
const ll M=100+5;
const double INFdb=1e10;

int n;
vector<pair<int,int>> ans;

struct rollingHash
{
    int hash_mod=1000000007;
    int hash=10007;
    vi ha;
    vi pow_hash;
    rollingHash(const vi& s)
    {
        int nn=(int)s.size();
        ha.assign(nn+1,0);
        pow_hash.assign(nn+1,1);
        for(int i=0;i<nn;++i)
        {
            ha[i+1]=((ll)ha[i]*hash+s[i])%hash_mod;
            pow_hash[i+1]=((ll)pow_hash[i]*hash)%hash_mod;
        }
    }
    int get(int l,int r)
    {
        return (ha[r]+hash_mod-((ll)ha[l]*pow_hash[r-l])%hash_mod)%hash_mod;
    }
};

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    	// freopen("input.txt", "r", stdin);
    	// freopen("out.txt", "w", stdout);
    // #endif
    cin>>n;
    vi a(n),b(n);
    vi xor_a(n*2),xor_b(n);
    for(int i=0;i<n;++i) cin>>a[i];
    for(int i=0;i<n;++i) cin>>b[i];
    for(int i=0;i<n;++i)
    {
        xor_a[i]=a[i]^a[(i+1)%n];
    }
    for(int i=0;i<n;++i)
    {
        xor_b[i]=b[i]^b[(i+1)%n];
    }
    for(int i=0;i<n;++i) xor_a[i+n]=xor_a[i];
    // for(int i=0;i<n;++i) cout<<xor_a[i]<<" ";
    rollingHash hash_a(xor_a),hash_b(xor_b);
    for(int i=0;i<n;++i)
    {
        // cout<<hash_a.get(i,i+n)<<endl;
        if(hash_a.get(i,i+n)==hash_b.get(0,n))
        {
            int x=a[i]^b[0];
            ans.emplace_back(i,x);
        }
    }
    for(pair<int,int> x:ans)
    {
        cout<<x.X<<" "<<x.Y<<endl;
    }
    cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";                                                                          
    return 0;
}

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

#define endl '\n'

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

  int n, k;
  int d;
  map<int,int> m;
  cin >> n >>k;
  while(n--){
    m[n+1] = 0;
  }

  for(int i = 0;i<k;i++){
    cin>>d;
    int snuke;
    for(int j=0;j<d;j++){
      cin>>snuke;
      if(m.count(snuke))
        m[snuke]++;
      else
        m[snuke] = 1;
    }
  }
  int ans = 0;
  for(auto e:m){
    // cout<<e.second<<endl;
    if(e.second==0)
      ans += 1;
  }

  cout<<ans<<endl;

  return 0;

}


Measured memory_bytes: 3664
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>

#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << n * (n + 1) / 2 << endl;
  return 0;
}


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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  
  if ( K <= A ){
    cout << K << endl;
  }
  else if ( K > A && K <= A+B ){
    cout << A << endl;
  }
  else {
    K = K - A - B;
    cout << A - K << endl;
  }
  return 0;
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] W = new int[N];
		for(int i = 0; i < N; i++) {
			W[i] = sc.nextInt();
		}
		int result = 0;
		for(int T = 1; T < N; T++) {
			int S1 = 0;
			int S2 = 0;
			for(int i = 0; i < N; i++) {
				if(i <= T - 1) {
					S1 += W[i];
				}else {
					S2 += W[i];
				}
			}
			if(T == 1) {
				result = Math.abs(S2 - S1);
			}
			result = Math.min(result, Math.abs(S2 - S1));
		}
		sc.close();
		System.out.println(result);
	}
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
typedef long long ll;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using mci = map<char, ll>;
using mcc = map<char, char>;
const int INF = 1 << 30;
const ll INFll = 1ll << 60;
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main() {
  ll n, k;
  cin >> n >> k;
  ll r, s, p;
  cin >> r >> s >> p;
  string T;
  cin >> T;
  mci P;
  P['r'] = r;
  P['s'] = s;
  P['p'] = p;
  mcc win;
  win['r'] = 'p';
  win['s'] = 'r';
  win['p'] = 's';

  ll ans = 0;
  rep(K, k) {
   char prev = 'e';
    for (ll i = K; i < n; i += k) {
      if (win[T[i]] == prev) {
        prev = 'e';
      } else {
        ans += P[win[T[i]]];
        prev = win[T[i]];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric>
#include <iomanip>

using namespace std;


long long n;
const long long N = 100 * 1000 + 5;

pair<long long, long long> a[N];

bool cmp(pair<long long, long long> x, pair<long long, long long> y)
{
	return x.first + x.second < y.first + y.second;
}


int main() 
{
	cin >> n;
	long long one = 0;
	long long two = 0;
	for (long long i = 0; i < n; i++)
	{	
		long long x, y;
		cin >> x >> y;
		a[i] = {x, y};
	}
	sort(a, a + n, cmp);
	reverse(a, a + n);
	for (long long i = 0; i < n; i++)
	{
		if (i % 2 == 0)
		{
			one += a[i].first;
		}
		else
		{
			two += a[i].second;
		}
	}
	cout << (one - two);






}































Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    void run() {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        int w = scan.nextInt();
        for (int i = 0; i < s.length(); i += w)
            System.out.print(s.charAt(i));
        System.out.println();
    }
    public static void main(String[] args) {
        new Main().run();
    }
}


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

int n,m,a[105];
int f[100005];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;cin>>a[i++]);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			if(i>=a[j])
				f[i] |= f[i-a[j]]^1;
	cout<<(f[m]==1 ? "First\n" : "Second\n");
	
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int x,a,b;
    cin>>x>>a>>b;
    if(abs(x-a)>abs(x-b))
    	cout<<"B";
    if(abs(x-a)<abs(x-b))
    	cout<<"A";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int i,j,u,k,v,n,a[100][100];
  scanf("%d",&n);

  for(i = 0;i < n;i++) {
    for(j = 0;j < n;j++) {
      a[i][j] = 0;
    }
  }

    for ( i = 0; i < n; i++ ) {
    scanf("%d%d", &u, &k);
    for ( j = 0; j < k; j++ ) {
      scanf("%d", &v);
      a[u - 1][v - 1] = 1;
    }
  }
 
  for ( i = 0; i < n; i++ ) {
    for ( j = 0; j < n; j++ ) {
      printf("%d", a[i][j]);
      if ( j < n - 1 ) printf(" ");
    }
    printf("\n");
  }
 
  return 0;
}

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

int main() {
  int a,b;
  string s;
  cin>>a>>b>>s;
  string ans="Yes";
  for(int i=0;i<a;i++){
    if(s[i]=='-') ans="No";
  }
  if(s[a]!='-') ans="No";
  for(int i=0;i<b;i++){
    if(s[a+1+i]=='-') ans="No";
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

int main(){
    int N;cin>> N;
    vector<int> H(N);
    rep(i,N)cin >> H[i];
    int res=0,tmp=0;
    for(int i=0;i<N-1;i++){
        if(H[i]>=H[i+1])tmp++;
        else tmp=0;
        res=max(res,tmp);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 640
import math

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

A=[]
B=[]
for i in range(x):
    A.append(ab[i][0])
    B.append(ab[i][1])

A.sort()
B.sort()

if x%2==1:
    min=A[x//2]
    max=B[x//2]
    ans=max-min+1
else:
    min=(A[x//2-1]+A[x//2])/2
    max=(B[x//2-1]+B[x//2])/2
    ans=(max-min)*2+1

print(int(ans))

Measured memory_bytes: 49208
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string> 
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g;}
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

int gen_popcount(int n, int a)
{
	int res = 0;
	while (n>0)
	{
		res += n % a;
		n /= a;
	}
	return res;
}

int main()
{
	int n;
	cin >> n;
	int ans = n;
	rep(i, n + 1)
	{
		int tmp = gen_popcount(i, 6) + gen_popcount(n - i, 9);
		chmin(ans, tmp);
	}
	co(ans);
	return 0;
}


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

int main(){
    int n;
    cin >> n;
    double v[n];
    for(int i=0;i<n;i++) cin >> v[i];

    sort(v,v+n);
    double temp=0;
    for(int i=0;i<n-1;i++){
        temp = (v[i]+v[i+1])/2;
        v[i+1]=temp;
    }
    cout << temp;
}

    

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"
int main() {
	while (1) {
		int N; cin >> N;
		if (!N)break;
		const int ro = 16 * 9 * 5 * 7*11;
		vector<vector<int>>specials(4);
		specials[0].resize(13);
		specials[1].resize(17);
		specials[2].resize(19);
		specials[3].resize(23);
		vector<vector<int>>access;
		for (int i = 0; i < N; ++i) {
			int d, t; cin >> d >> t;
			vector<int>v(d);
			for (int j = 0; j < d; ++j) {
				cin >> v[(j + d - t) % d];
			}
			vector<int>av;
			if (ro%d) {
				const int num = *max_element(v.begin(), v.end());
				for (int j = 0; j < d; ++j) {
					 int p;
					if (d == 13) {
						p = 0;
					}
					else if (d == 17) {
						p = 1;

					}
					else if (d == 19) {

						p = 2;
					}
					else if (d == 23) {
						p = 3;

					}
					specials[p][j] += v[j];
				}
			}
			else {
				for (int j = 0; j < ro / d; ++j) {
					av.insert(av.end(), v.begin(), v.end());
				}
			}
			access.push_back(av);
		}
		int ans = 0;
		for (int i = 0; i < ro; ++i) {
			int sum = 0;
			for (int j = 0; j < N; ++j) {
				if (!access[j].empty()) {
					sum += access[j][i];
				}
			}
			ans = max(ans, sum);
		}
		for (int i = 0; i < 4; ++i) {
			ans += *max_element(specials[i].begin(), specials[i].end());
		}
		cout << ans << endl;
	}
	return 0;
}

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

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

using namespace std;

int main(){
  int n;cin>>n;
  string s;cin>>s;
  map<int, int> m;

  int c=0;
  rep(i,10){
    rep(j,10){
      rep(k,10){
        int d = 0;
        rep(l,s.size()){
          if(d==2 && stoi(s.substr(l,1))==k)d++;
          if(d==1 && stoi(s.substr(l,1))==j)d++;
          if(d==0 && stoi(s.substr(l,1))==i)d++;
        }
        if(d==3)c++;
      }
    }
  }
  cout<<c;

  return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce
MOD = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = list(map(int, input().split()))

num = lcm_list(a)
ans = 0
for i in a:
    ans += num // i

ans %= MOD
print(ans)

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

lst = [1, 6, 9, 6**2, 9**2, 6**3, 9**3, 6**4, 9**4, 6**5, 6**6, 9**5]
dp = [N+1] * (N+1)
dp[0] = 0
for i in range(1, N+1):
    for j in lst:
        if j <= i:
            # print(i, j, i-j)
            dp[i] = min(dp[i], dp[i-j]+1)
print(dp[-1])

Measured memory_bytes: 9504
N,M=map(int,input().split())
L=[]
R=[]
for m in range(M):
    Lm,Rm=map(int,input().split())
    L.append(Lm)
    R.append(Rm)
maxL=max(L)
minR=min(R)
print(max(minR-maxL+1,0))

Measured memory_bytes: 11052
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, L, R, Q;
	string SL, SR, SQ;
	cin >> N;
	L = 0, R = N;
	cout << 0 << endl;
	cin >> SL;
	if (SL == "Vacant") goto END;
	SR = SL;
	while (1) {
		Q = (L + R) / 2;
		cout << Q << endl;
		cin >> SQ;
		if (SQ == "Vacant") goto END;
		if ((SQ == SL && (Q - L) % 2 == 1) || (SQ != SL && (Q - L) % 2 == 0)) R = Q, SR = SQ;
		else L = Q, SL = SQ;
	}
END:;
}

Measured memory_bytes: 852
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private class CacheEntry {
        public int target;
        public int startIdx;
        public int endIdx;

        public CacheEntry (int t, int s, int e) {
            target = t;
            startIdx = s;
            endIdx = e;
        }

        @Override
        public boolean equals(Object that) {
            if (!(that instanceof CacheEntry)) {
                return false;
            }
            CacheEntry thatCache = (CacheEntry) that;
            return (target == thatCache.target) &&
                    (startIdx == thatCache.startIdx) &&
                    (endIdx == thatCache.endIdx);
        }

        @Override
        public int hashCode() {
            return Integer.hashCode(target) * Integer.hashCode(startIdx) * Integer.hashCode(endIdx);
        }
    }

    private Map<CacheEntry, Long> cache = new HashMap<>();

    public long waysForSum(int target, int[] elems, int startIdx, int endIdx) {
        if (startIdx > endIdx) {
            if (target == 0) {
                return 1;
            }
            else {
                return 0;
            }
        }

        long result = 0;
        CacheEntry cacheKey = new CacheEntry(target, startIdx, endIdx);
        if (cache.containsKey(cacheKey)) {
            result = cache.get(cacheKey);
        }
        else {
            result += waysForSum(target + elems[startIdx], elems, startIdx + 1, endIdx);
            result += waysForSum(target, elems, startIdx + 1, endIdx);
            cache.put(cacheKey, result);
        }
        return result;
    }

    private void solve(int n, int a, int[] cards) {
        int[] diffs = new int[n];
        for (int i = 0; i < n; i++) {
            diffs[i] = cards[i] - a;
        }
        System.out.println(waysForSum(0, diffs, 0, n - 1) - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = sc.nextInt();
        int[] cards = new int[n];
        for (int i = 0; i < n; i++) {
            cards[i] = sc.nextInt();
        }

        Main main = new Main();
        main.solve(n, a, cards);
    }
}


Measured memory_bytes: 26288
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
#define modulo 1000000007 // 10^9 + 7
#define MAX 1000000000 // 10^9


int main() {
	int N, K;
	cin >> N >> K;
	int x[N];
	for (int i = 0; i < N; i++) cin >> x[i];

	ll ans = MAX;

	for (int i = 0; i + K - 1 < N; i++) {
		ll dis1 = abs(x[i]) + x[i + K - 1] - x[i];
		ll dis2 = abs(x[i + K - 1]) + x[i + K - 1] - x[i];

		ans = min(ans, dis1);
		ans = min(ans, dis2);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
"use strict";
function I(s,f){this._s=s.split("\n");this._c=0;this._l=0;this._f=f||Number}I.prototype.a=function(){var l=this._s[this._l];if(!l)return;var t=l.trim().split(" ");var a=t[this._c];this._c++;if(t.length===this._c){this._c=0;this._l++}return this._f(a)};I.prototype.l=function(){var l=this._s[this._l];if(!l)return;this._c=0;this._l++;return l.split(" ").map(this._f)};module.exports=I;

function main(input) {
  const o = new I(input);

  const N = o.a();

  let x = [];
  let y = [];
  let h = [];
  for (let i = 0; i < N; i++) {
    x.push(o.a());
    y.push(o.a());
    h.push(o.a());
  }

  let firstNotZero = 0;
  for (let k = 0; k < N; k++) {
    if (h[k] !== 0) {
      firstNotZero = k;
      break;
    }
  }

  let flag;
  for (let i = 0; i<= 100; i ++) {
    for (let j = 0; j<= 100; j++) {
      flag = true;

      let base = Math.abs(i - x[firstNotZero]) + Math.abs(j - y[firstNotZero]);
      let H = h[firstNotZero] + base;


      for (let k = 0; k < N; k++) {
        let temp = Math.abs(i - x[k]) + Math.abs(j - y[k]);
        let result = H - temp > 0 ? H - temp : 0;
        if (result !== h[k]) {
          flag = false;
          break;
        }
      }

      if (flag) {
        console.log(i, j, H);
        break;
      }
    }
    if (flag) {
      break;
    }
  }

}


main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7756
import bisect
import copy
import heapq
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    S = 0
    for n in range(1, N + 1):
        if n % 3 == 0 or n % 5 == 0:
            continue
        S += n
    print(S)


if __name__ == "__main__":
    main()


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

#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0);
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(ll x=j;x<n;x++)
#define repr(x,j,n)for(ll x=j;x>n;x--)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
const int N=2e6+7;

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
    if(b&1)
    r=(r*a)%m;
    b=b/2;
    a=(a*a)%m;
    }
    return r%m;
}
int main()
{


    ll n,k;
    cin>>n>>k;

    ll ans=0;
    ll l=0,r=n;
    ll ms=0,mas=0;
    rep(i,1,n+2)
    {
        ms+=l;
        mas+=r;
       if(i>=k) ans+=(mas-ms+1)%mod;
        ans=ans%mod;
        l++;
        r--;
    }
    //ans=(ans*f[n+1])%mod;
    ans=ans%mod;
    cout<<ans;








}


Measured memory_bytes: 3636
from collections import deque

def main(H,W):
  area = [[] for i in range(H)]
  island = []
  
  for _ in range(H):
    h = list(map(int,input().split()))
    area[_] = h
    for i in range(W):
      if h[i] == 1:
        island.append([_,i])
  
  visited = [[0] * W for i in range(H)]
  
  def dfs(area, visited,sh,sw):
    stack = deque([[sh,sw]])
    visited[sh][sw] = 1
    while stack:
      h,w = stack.pop()
      for j in range(-1,2):
        for k in range(-1,2):
          new_h, new_w = h + j, w + k
          if new_h < 0 or new_h >= H or \
            new_w < 0 or new_w >= W:
              continue
          elif area[new_h][new_w] == 1 and \
            visited[new_h][new_w] == 0:
            visited[new_h][new_w] = 1
            stack.append([new_h, new_w])
    return 
  
  ans = 0
  
  for i in island:
    sh,sw = i[0],i[1]
    if visited[sh][sw] == 0:
      dfs(area,visited,sh,sw)
      ans += 1
  
  print(ans)
  
while True:
  W,H = map(int,input().split())
  if H == 0 and W == 0:
    break
  else:
    main(H,W)



Measured memory_bytes: 6284
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n, m;
  cin >> n >> m;
  vector<pair<i64, i64>> b(n);
  for (i64 i = 0; i < n; i++)
    cin >> b[i].first >> b[i].second;
  sort(b.begin(), b.end());
  i64 ans = 0, t = 0;
  priority_queue<i64> que;
  for (i64 i = 0; i <= m; i++)
  {
    while (t < n && b[t].first <= i)
    {
      que.push(b[t].second);
      t++;
    }
    if (que.size() != 0)
    {
      ans += que.top();
      que.pop();
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

set<int> s;
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		s.insert(a);
	}
	cout << s.size() << endl;
	return 0;
}

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

using namespace std;

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define INF INT_MAX
#define PI 3.141592653
#define inf 1000007
#define pll pair<ll,ll>
#define pii pair<int,int>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }

int main(){
    ll x,y,A,B,C,ans=0;
    cin>>x>>y>>A>>B>>C;
    vector <ll> a(A),b(B),c(C),f;
    pan(i,A)
        cin>>a[i];
    pan(i,B)
        cin>>b[i];
    pan(i,C)
        cin>>c[i];
    sort(a.begin(),a.end(),greater<ll>());
    sort(b.begin(),b.end(),greater<ll>());
    sort(c.begin(),c.end(),greater<ll>());
    pan(i,x)
        f.pb(a[i]);
    pan(i,y)
        f.pb(b[i]);
    sort(f.begin(),f.end());
    int n=(C>f.size()) ? f.size():C;
    pan(i,n){
        if(c[i]-f[i]>0)
            f[i]=c[i];
    }
    pan(i,(int)f.size())
        ans+=f[i];
    cout<<ans;
}

Measured memory_bytes: 4724
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			int N = scan.nextInt();
			int[] A = new int[N];//生徒配列
			int[] jun= new int[N];//junban配列1,2,3,4,5番号
			
			for(int i = 0;i<N;i++) {
				A[i] = scan.nextInt();
				jun[A[i]-1]=i+1;
			}
			
			
			for(int i =0;i<N;i++) {
			System.out.print(jun[i]);
			System.out.print(" ");
			}
			
			
			
			
			
			
			
			
			
			
			
			
		}
		
		
	}
		

}


Measured memory_bytes: 63540
import java.util.Scanner;

public class Main {

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

	    long n=gl();
	    long a=gl();
	    //int b=gi();


        System.out.println(n*n-a);
//        if (n%10==9 || n>=90 ) {
//        	System.out.print("Yes");
//        }else {
//            System.out.print("No");
//        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
}

Measured memory_bytes: 35616
/* *
 *
 * Author: Hamkor
 *
 * */
 
#include <bits/stdc++.h>

using namespace std;

/* * * *   * * *   	* * * */
typedef long long ll;
const int oo = 1e9;
const ll mod = 100000000;
typedef complex<ll> P;
#define X real()
#define Y imag()
/* * * *   * * *   	* * * */

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	long double n, k, c = 0.0; cin>>n>>k;
	if((int)n<(int)k){
		for (int i=1; i<=(int)n; ++i){
			int l = 0, j = i; 
			while (j<(int)k){j = j<<1; l++;}
			c+=(1.0/n)*(1.0/(1<<l));
		}
		printf("%.9Lf", c);
	}else {
		for (int i=1; i<(int)k; ++i){
			int l = 0, j = i; 
			while (j<(int)k){j = j<<1; l++;}
			c+=(1.0/n)*(1.0/(1<<l));
		}
		c+=(1.0/n)*(n-k+1.0);
		printf("%.9Lf", c);
	}
	return 0;
}


Measured memory_bytes: 256
import math
import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())

counter = collections.Counter(prime_factorize(N))
#print(counter)

ans = 0
for key in counter.keys():
    num = counter[key]
    i = 1
    while num >= i:
        num -= i
        ans += 1
        i += 1

print(ans)


Measured memory_bytes: 9484
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>
#include <stack>
#include <cstdlib>

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

typedef long long ll;

using namespace std;

int main() {
    
    int n;
    cin >> n;
    
    //int n1,n10,n100;
    /*
    if(n <= 999){
        n100 = n/100;
        n10 = (n - n100*100)/10;
        n1 = (n - n100*100-n10*10);
        
        cout << "ABC" << n100 << n10 << n1 << endl;
    }else{
        n = n-999;
        n100 = n/100;
        n10 = (n - n100*100)/10;
        n1 = (n - n100*100-n10*10);
        cout << "ABC" << n100 << n10 << n1 << endl;
    }
    */
    
    if(n<=999){
        cout << "ABC" << endl;
    }else{
        cout << "ABD" << endl;

    }
    
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		while(true) {
			int n = sc.nextInt();
			int min = sc.nextInt();
			int max = sc.nextInt();
			if (n == 0) return;
			int a[] = new int[n];

			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}

			int m = 0, mi = 0;
			for (int i = min-1; i < max; i++) {
				if (a[i]-a[i+1] >= m) {
					m = a[i] - a[i+1];
					mi = i + 1;
				}
			}

			System.out.println(mi);
		}
	}
}


Measured memory_bytes: 56432
import math
N,K=map(int,input().split())
p=[0 for i in range(20)]
for i in range(20):
  M=K
  for j in range(i):
    M=M/2
  p[i]=math.ceil(M)
t=N+1
i=0
A=0
ans=0
while p[i]>N:
  i+=1
while p[i]!=1:
  s=p[i]
  ans+=((t-s)/2**i)/N
  t=s
  i+=1
s=p[i]
ans+=((t-s)/2**i)/N
print(ans)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Circle
{
    class Program
    {
        static void Main(string[] args)
        {
            double r = double.Parse(Console.ReadLine());

            Console.WriteLine("{0:f6} {1:f6}", Math.PI * r * r, 2 * Math.PI * r);
        }
    }
}



Measured memory_bytes: 18008
using System;
using System.Collections.Generic;
using System.Linq;
class abc165_a{
  public static void Main(){
    int k = int.Parse(Console.ReadLine());
    bool flag = false;
    int[] range = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
    for(int i=range[0]; i<=range[1] && !flag; i++){
      if(i%k == 0){
        flag = true;
      }
    }
    if(flag)
      Console.WriteLine("OK");
    else
      Console.WriteLine("NG");
  }
}


Measured memory_bytes: 19092
#include <bits/stdc++.h>
//#include <algorithm>
//#include <iostream>
//#include <cstring>
//#include <set>

using namespace std;
const int MAX_R = 15,  MAX_C = 10005;
const int inf = 1e+9;

int R, C;
bool G[MAX_R][MAX_C];
int res;
//int a[MAX_C];

void dfs(int i){
    if(i == R){
        int rest = 0;
        for(int i = 0;i < C;i++){
            int sum = 0;
            for(int j = 0;j < R;j++){
                sum+= G[j][i];
            }
            rest += max(sum, R-sum);
        }
        res = max(rest, res);
        return;
    }

    dfs(i+1);

    for(int j = 0;j < C;j++){
           G[i][j] ^= 1;
    }

    dfs(i+1);

    for(int j = 0;j < C;j++){
        G[i][j] ^= 1;
    }
}

void solve(){
    dfs(0);
    printf("%d\n", res);
}
int main(){
    while(~scanf("%d %d", &R, &C)){
        if(R == 0&& C == 0) break;
        for(int i = 0;i < R;i++){
            for(int j = 0;j < C;j++){
                scanf("%d", &G[i][j]);
            }
        }
        solve();
    }

    return 0;
}

/*
1
 1
 */


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

long long mod = 998244353;

int main() {
  
  string S;
  long long K,N;
  cin >> S >> K;
  
  N = S.size();
  
  long long now = 0;
  long long n1 = 0;
  
  vector<long long> S_1(300,0);
  
  for (int i=0; i<N; i++) {
    if (S[i] == '0') {
      now++;
    }
    else {
      S_1[now]++;
      n1++;
    }
  }
  
  if (S[N-1] == '1') {
    now++;
  }
  
  K = min(n1,K);
  
  vector<vector<vector<long long>>> dp(now+1,vector<vector<long long>> (K+1,vector<long long> (K+1,0)));
  
  dp[now][K][0] = 1;
  
  
  n1 = 0;
  
  for (int i=now-1; i>=0; i--) {
    n1 += S_1[i];
    for (int j=max(0ll,K-n1); j<=K; j++) {
      for (int l=0; l<=n1; l++) {
        if (j+l > K) break;
        for (int m=l; j+m <= K; m++) {
          dp[i][j][l] += dp[i+1][j][m];
          dp[i][j][l] %= mod;
        }
        for (int m=1; m<=S_1[i]; m++) {
          if (j+m > K) break;
          if (l < m) break;
          dp[i][j][l] += dp[i+1][j+m][l-m];
          dp[i][j][l] %= mod;
        }
      }
    }
  }
  
  long long ans = 0;
  
  for (int i=0; i<=K; i++) {
    ans += dp[0][i][0];
    ans %= mod;
  }
  
  cout << ans << endl;
  
  return 0;
  
}

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

int main(){
  int n,k,c=1;
  cin>>n>>k;
  fr(i,n){
    if(c>k) c+=k;
    else c*=2;
  }
  cout<<c<<endl;
}


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

int N;

int main(){
    cin>>N;
    int a[N],c[100005]={},ans=1;
    for(int i=0;i<N;i++){
        cin>>a[i];
        c[a[i]]++;
    }
    for(int i=1;i<100000;i++){
        int count=c[i-1]+c[i]+c[i+1];
        ans=max(ans,count);
    }
    cout<<ans<<endl;
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define set0(k,n) for(int nn=0;nn<(n);nn++){ (k).push_back(0); }
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define vecsize(b,size) vector<int> (b)((size));
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsl(s) vector<pair<ll,ll>> (s);
#define pairss(s) vector<pair<string,string>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairspl(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsps(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define pairsREV(s) (s).push_back(make_pair(bb,aa));
#define pairslREV(s) (s).push_back(make_pair(bb,aa));
#define pairssREV(s) (s).push_back(make_pair(bb,aa));
#define MOD 1000000007

int main()
{
	map<pair<string,int>, int> R;
	vector<pair<string, int>> E;
	int N;
	cin >> N;
	fx(N) {
		string s;
		int a;
		cin >> s >> a;
		R[make_pair(s,200-a)] = x + 1;
		pb(E, make_pair(s, 200-a))
	}
	sorts(E)
	fx(N) {
		ce(R[E.at(x)])
	}
    return 0;
}



Measured memory_bytes: 256
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def resolve():
    import sys
    input = sys.stdin.readline

    n, a, b = [int(x) for x in input().rstrip().split(" ")]

    if a > n - b + 1:
        tmp = a
        a = n - b
        b = n - tmp
    else:
        a = a - 1
        b = b - 1

    if (b - a) % 2 == 0:
        print(abs(a - b) // 2)
    else:
        count = a + 1 + ((b - a - 1) // 2)
        print(count)



if __name__ == "__main__":
    resolve()


Measured memory_bytes: 61908
import sys
input = sys.stdin.readline
 
n = int(input())
a =[int(xi) for xi in input().split()]
b =[int(yi) for yi in input().split()]
 
cnt, prev_cnt = 0, -1
while cnt != prev_cnt:
    prev_cnt = cnt
    for i in range(n):
        
        adj_sum = b[i - 1] + b[(i + 1) % n]
        k = (b[i] - a[i]) // adj_sum
        if k > 0:
            b[i] -= k * adj_sum
            cnt += k
 
print(cnt if a == b else -1)

Measured memory_bytes: 105592
fun main(args: Array<String>){
    val (H, W) = readLine()!!.split(" ").map { it.toInt() }
    val A = Array(H) { readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
    val opList = mutableListOf<Operation>()

    var x = 0
    var y = 0
    var now = false
    var counter = 0
    while (counter < H * W - 1) {
        val xNext =
            if (x == W - 1 && y % 2 == 0) {
                x
            } else if(x == 0 && y % 2 == 1) {
                x
            } else if (y % 2 == 0) {
                x + 1
            } else {
                x - 1
            }
        val yNext =
            if (x == W - 1 && y % 2 == 0) {
                y + 1
            } else if(x == 0 && y % 2 == 1) {
                y + 1
            }else {
                y
            }
        if (A[y][x] % 2 == 1 && now) {
            now = false
        } else if (A[y][x] % 2 == 1 && !now) {
            now = true
            opList.add(Operation(y, x, yNext, xNext))
        } else if (A[y][x] % 2 == 0 && now){
            opList.add(Operation(y, x, yNext, xNext))
        }
        x = xNext
        y = yNext
        counter++
    }
    println(opList.size)
    opList.forEach { op -> println("${op.y1 + 1} ${op.x1 + 1} ${op.y2 + 1} ${op.x2 + 1}") }
}

class Operation(
    val y1: Int,
    val x1: Int,
    val y2: Int,
    val x2: Int
)

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

vector<int> graph[100005];
bool visit[100005];

vector<int> path;
vector<int> path2;

void dfs(int t){
  visit[t] = true;
  path.push_back(t);
  for (int nxt : graph[t]){
    if (!visit[nxt]){
      dfs(nxt);
      return;
    }
  }
}

int main(){
  cin.sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for(int i = 0; i < m; i++){
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);

  }

  dfs(1);
  swap(path, path2);
  dfs(1);

  // printf("%zd\n", path2.size());
  // for (int i = (int)path2.size() - 1; i >= 0; i--)
  // {
  //     printf("%d ", path2[i]);
  // }

  printf("%zd\n", path.size() + path2.size() - 1);
  for (int i = (int)path2.size() - 1; i >= 1; i--)
  {
    printf("%d ", path2[i]);
  }
  for (int t : path) printf("%d ", t);
  printf("\n");

}


Measured memory_bytes: 9720
#include <iostream>
#include <cstring>

using namespace std;

const int INF=1000000000;
int times[10001];
int dp[2][10001][2];
int n;

int main(){
	cin>>n;
	for(int i=0;i<n-1;i++)cin>>times[i];
	for(int pos=n;pos>=1;pos--){
		for(int len=(n/2)+1;len>=0;len--){
			for(int prv=0;prv<2;prv++){
				int res=INF;
				int cur=(pos+1)%2;
				int nxt=pos%2;
				if(pos==n){
					if(len==n/2)res=0;
					else res=INF;
				}
				else if(len>n/2)res=INF;
				else{
					if(prv==0)res=min(res,dp[cur][len+1][prv]);
					else res=min(res,dp[cur][len+1][!prv]+times[pos-1]);
					if(prv==1)res=min(res,dp[cur][len][prv]);
					else res=min(res,dp[cur][len][!prv]+times[pos-1]);
				}
				dp[nxt][len][prv]=res;
			}
		}
	}
	int res=min(dp[1][1][0],dp[1][0][1]);
	cout<<res<<endl;
	return 0;
}

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

int main() {
    array<int, 4> counter = {0,0,0,0};

    int a, b;
    // input
    for (size_t i = 0; i < 3; i++) {
        cin >> a >> b;
        counter[a-1] += 1;
        counter[b-1] += 1;
    }

    // size 2 counter
    int two_count = 0;
    for (auto itr = counter.begin(); itr != counter.end(); ++itr) {
        if (*itr == 2) two_count += 1;
    }
    
    if (two_count == 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  string s;
  cin >> s;
  
  uint64_t K;
  cin >> K;
  
  set<string> t;
  for (uint64_t left = 0; left < s.size(); ++left) {
    for (uint64_t length = 1; length <= K; ++length) {
      t.insert( s.substr(left, length) );
    }
  }
  
  auto itr = t.begin();
  advance(itr, K - 1);
  cout << *itr << endl;
  
  return 0;
}

Measured memory_bytes: 1664
/*
   0 1 2 3 4 5 6 7 8 910
1: 1 1------------
2: 1 2 1----------
3: 1 3 3 1--------
4: 1 4 6 4 1------
5: 1 51010 5 1--
6: 1 6152015 6 1-----
7: 1 721353521 7 1

*/
#include <iostream>
#include <cmath>
#include <algorithm>
#define NMAX 100005
using ll=long long;
using namespace std;
ll n;
ll a[NMAX];
int main(){
  cin >> n;
  for(int i=0;i < n; ++i){
    cin >> a[i];
  }
  sort(a, a + n);
  int i=1, j = 0;
  for(i=2;i < n; ++i){
    while(abs(a[i]/2.0 - a[j]) > 
       abs(a[i]/2.0 - a[j+1]))
      ++j;
  }
  cout << a[--i] << " " << a[j] << endl;
  return 0;
}


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

const long long MOD = 1000000007;
const long long MAX = 2000000;

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

int main()
{
    string S;
    cin>>S;
    for(int i=0;i<(int)S.size();i++){
        if(S[i]=='?'){
            S[i]='D';
        }
    }
    cout<<S<<endl;
    



    
    

}


Measured memory_bytes: 3752
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(int)(n);++i)
using namespace std;

int main(){
    int n;cin>>n;
    int a[100];rep(i,n)cin>>a[i];
    sort(a,a+n);
    rep(i,n)a[i] /= 400;
    int color[9];rep(i,9)color[i] = 0;
    rep(i,n){
        if(a[i] < 8)++color[a[i]];
        else ++color[8];
    }
    int ans=0;
    rep(i,8)if(color[i] > 0)++ans;
    if(ans != 0)printf("%d %d\n",ans,ans+color[8]);
    else printf("%d %d\n",1,ans+color[8]);
}

Measured memory_bytes: 256
def resolve():
    N = int(input())
    H = list(map(int, input().split()))
    c = 0
    d = c
    for i in range(N-1):
        if H[i] >= H[i+1]:
            c += 1
        else:
            d = max([c, d])
            c = 0
            
    print(max([c, d]))

resolve()

Measured memory_bytes: 15020
n,y = map(int, input().split())
for i in range(n+1):
    for j in range(n-i+1):
        if i*10000 + j*5000 + (n-j-i)*1000 == y:
            print(i, j, n-i-j)
            exit()
print("-1 -1 -1")

Measured memory_bytes: 2940
fun main(args: Array<String>) {
  val N = readInt()
  val AN = readInts()
  val dp = Array(100002) { 0 }
  AN.forEach { a ->
    dp[a]++
    dp[a + 1]++
    dp[a + 2]++
  }
  println(dp.max())
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }
fun readLong() = readString().toLong()
fun readLongs() = readStrings().map { it.toLong() }


Measured memory_bytes: 56132
import java.io.*;
 
public class Main {
 
	public static void main(String args[]) {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		try {
			String str = in.readLine();
			Integer n = Integer.valueOf(str.split(" ")[0]);
			Integer t = Integer.valueOf(str.split(" ")[1]);
			int max = Integer.MAX_VALUE;
			for(int i=0;i<n;i++) {
				str = in.readLine();
				Integer cost = Integer.valueOf(str.split(" ")[0]);
				Integer time = Integer.valueOf(str.split(" ")[1]);
				if(time<=t) {
					if(cost<max) {
						max = cost;
					}
				}
			}
			if(max == Integer.MAX_VALUE) {
				System.out.println("TLE");
			}
			else {
				System.out.println(max);
			}
		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}
	}
 
}

Measured memory_bytes: 22868
(defun solve (N)
  (let ((digits (length (write-to-string N))))
    (cond
     ((= digits 5) (- N 9090))
     ((= digits 4) 909)
     ((= digits 3) (- N 90) )
     ((= digits 2) 9)
     ((= digits 1) N)
     (t 90909))
    ))
(princ (solve (read)))

Measured memory_bytes: 3556
def main():
    n,m = map(int,input().split())
    lines = [[] for _ in range(n)]
    for i in range(m):
        l,r,d = map(int,input().split())
        lines[l-1].append([r-1,d])
        lines[r-1].append([l-1,-d])

    from collections import deque
    # from heapq imort heappush, heappop
    inf = 10**18
    dist = [inf]*n

    for i in range(n):
        if dist[i] != inf:
            continue
        dist[i] = 0
        q = deque()
        q.append([i,0])
        while q:
            now,cnt = q.popleft()
            for nxt,nd in lines[now]:
                if dist[nxt] == inf:
                    dist[nxt] = cnt+nd
                    q.append([nxt,cnt+nd])
                    continue
                if dist[nxt] != cnt+nd:
                    print('No')
                    return 0
    print('Yes')

if __name__ == '__main__':
    main()



Measured memory_bytes: 108960
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
    int x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
    return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 2007, inf = 0x3f3f3f3f;
int n, ans = inf;
int son[N]; char s[N];
vector<int>G[N];
struct data {int L, R;}t[N];
data operator +(data a, data b) {
	data res;
	res.R = a.R + b.R;
	if(a.L > b.L) swap(a, b);
	if(a.R <= b.L) res.L = b.L - a.R;
	else res.L = res.R & 1;
	return res;
}
void dfs(int u, int fa) {
	son[u] = s[u] == '1';
	t[u] = (data){0, 0};
	for(auto v:G[u]) if(v ^ fa) {
		dfs(v, u);
		son[u] += son[v];
		t[v].L += son[v];
		t[v].R += son[v];
		t[u] = t[u] + t[v];
	}
}
int main() {
#ifdef fwat
#endif
	n = gi();
	scanf("%s", s + 1);
	rep(i, 1, n - 1) {
		int x = gi(), y = gi();
		G[x].pb(y);
		G[y].pb(x);	
	}
	rep(i, 1, n) {
		dfs(i, 0);
		if(t[i].L == 0) Min(ans, t[i].R / 2);
	}
	printf("%d\n", ans == inf ? -1 : ans);
	return 0;
}

Measured memory_bytes: 512
import java.util.*;

class Main {
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  List<Integer> num = new ArrayList<>();
  for (int i=0; i<3; i++) {
   num.add(Integer.parseInt(sc.next()));
  }
  sc.close();

  num.sort(null);

  System.out.println(num.get(0) + " " + num.get(1) + " " + num.get(2));
 }
}


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

int main(){
  int M1,D1,M2,D2;
  cin >> M1 >> D1 >> M2 >> D2;
  if(M1==M2){cout << 0 << endl;}
  else{cout << 1 << endl;}
}

Measured memory_bytes: 256
/**In the name of Allah, the Most Merciful, the Most Merciful.**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 9223372036854775806
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 2*acos(0.0)
#define EPS 1e-9
ll max(ll a,ll b) {if(a>b) return a; else return b;}
ll min(ll a,ll b) {if(a<b) return a; else return b;}

int main()
{
    string s;
    cin>>s;
    if(s.back()=='s') cout<<s<<"es"<<endl;
    else cout<<s<<"s"<<endl;

    return 0;
}




Measured memory_bytes: 3632
#include <iostream>
#include "stdio.h"
using namespace std;

void func(int x, int y, int z)
{
  if(x < y)
  {
    if(y < z)
    {
      std::cout << "Yes" << '\n';
      return;
    }
  }
  std::cout << "No" << '\n';
}

int main()
{
	int x,y,z;
  scanf("%d%d%d",&x,&y,&z );
  func(x,y,z);
  return 0;
}



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


int number(char c) {
  int num = 0;
  num = (int)(c - '0');
  return num;
}

int main() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> a(n);
  for(int i = 0; i < n; i++) {
    a[i] = number(s[i]);
  }
  int ans = 0;
  for(int i = 0; i <= 999; i++) {
    int tmp[3] = {i / 100, (i % 100) / 10, i % 10};
    int j = 0;
    for(int k = 0; k < 3; k++) {
      while(j < n && tmp[k] != a[j]) {
        j++;
      }
      if(k < 2) {
        j++;
      }
    }
    if(j < n) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S,T;
  cin >>S>>T;
  int ans = 0;
  for(int  i =  0;i<3;i++){
    if(S.at(i)==T.at(i)){
      ans++;
    }
  }
  cout <<ans<<endl;
}

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

using namespace std;

int main(){
    int t,n,m,d[100000],k[10000];
    d[0]=0;
    while(cin>>t,t){
        cin>>n>>m;
        for(int i=1;i<n;++i) cin>>d[i];
        sort(d,d+n);
        int sum=0;
        for(int i=0;i<m;++i){
            cin>>k[i];
            int cur = lower_bound(d,d+n,k[i])-d;
            sum += min((d[(cur)%n]-k[i]+t)%t,abs((d[(cur+n-1)%n]-k[i]-t))%t);
        }
        cout<<sum<<endl;
    }
    return 0;
}

Measured memory_bytes: 3484
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, t))
        cur += 1
    ans = -1
    while len(q) > 0:
        x, t = q[0]
        if d <= t:
            ans = x
            break
        else:
            heappop(q)
    print(ans)



Measured memory_bytes: 137436