akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"fmt"
)

func main() {
	var ans int
	for i := 0; i < 5; i++ {
		var x int
		fmt.Scan(&x)
		if x == 0 {
			ans = i + 1
		}
	}
	fmt.Println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


Measured memory_bytes: 1748
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include <iomanip>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
using namespace std;
 
#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ans=0;llfor;///////////////////////////////////////////////////////////
int main(){
  int N,K;
  cin>>N>>K;
  vector<double> p(N+1);  
  p.at(0)=0;
  double P;
  for(int i=1;i<=N;i++){
    cin>>P;
    p.at(i)=p.at(i-1)+(1+P)/2;
  }
  double M=0;
  for(int i=K;i<=N;i++) M=max(M,p.at(i)-p.at(i-K));
  cout<<fixed<<setprecision(10)<<M;
return 0;}

Measured memory_bytes: 4696
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <typeinfo>
#include <math.h>

using namespace std;
using ll = long long;

int main() {

	int n, x,count=1,sm=0;
	cin >> n >> x;
	vector<int> l(n);
	for (int i = 0; i < n; i++)
		cin >> l[i];

	for (int i = 0; i < n; i++)
	{
		sm += l[i];
		if (sm <= x)
			count++;
	}
	cout << count << endl;

	//cin >> x;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "ctime"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

bool Search(vector<vector<pair<int, long long int>>>&edge, vector<vector<pair<long long int, long long int>>>&comb, int node, long long int mid) {
	if (edge[node].empty()) {
		comb[node].push_back({ 0,0 });
		return true;
	}
	Search(edge, comb, edge[node].front().first, mid);
	Search(edge, comb, edge[node].back().first, mid);
	auto cn = edge[node].front().first;
	auto c = edge[node].front().second;
	auto ccn = edge[node].back().first;
	auto cc = edge[node].back().second;
	int index = 0;
	if (comb[cn].size() > comb[ccn].size()) {
		swap(cn, ccn);
		swap(c, cc);
	}
	vector<pair<long long int, long long int>>a;
	for (auto i : comb[cn]) {
		long long int border = mid - c - cc - i.second;
		while (index + 1 < comb[ccn].size() && comb[ccn][index + 1].first <= border)index++;
		if (comb[ccn][index].first <= border) {
			a.push_back({ c + i.first,cc + comb[ccn][index].second });
		}
	}
	index = 0;
	vector<pair<long long int, long long int>>b;
	for (auto i : comb[cn]) {
		long long int border = mid - c - cc - i.first;
		while (index<comb[ccn].size() && comb[ccn][index].second > border)index++;
		if (index<comb[ccn].size()&&comb[ccn][index].second <= border) {
			b.push_back({ cc + comb[ccn][index].first,c + i.second });
		}
	}
	int indexb = 0;
	index = 0;
	while (index < a.size() || indexb < b.size()) {
		int aa = 1;
		if (index == a.size()) aa = 0;
		else if (indexb == b.size())aa = 1;
		else if (a[index] < b[indexb])aa = 1;
		else aa = 0;
		if (aa) {
			if (comb[node].empty())comb[node].push_back(a[index]);
			else if (comb[node].back().second > a[index].second)comb[node].push_back(a[index]);
			index++;
		}
		else {
			if (comb[node].empty())comb[node].push_back(b[indexb]);
			else if (comb[node].back().second > b[indexb].second)comb[node].push_back(b[indexb]);
			indexb++;
		}
	}
	return !(comb[node].empty());
}

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

	cin >> N;
	vector<vector<pair<int,long long int>>>edge(N + 1);
	for (int i = 2; i <= N; i++) {
		cin >> L >> K;
		edge[L].push_back({ i,K });
	}
	L = -1;
	R = 1LL << 35;
	vector<vector<pair<long long int, long long int>>>comb(N + 1);
	while (R - L > 1) {
		long long int mid = (R + L + 1) / 2;
		if (Search(edge, comb, 1, mid))R = mid;
		else L = mid;
		for (auto &i : comb) {
			if (!i.empty())i.clear();
		}
	}
	cout << R << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
const int N=2e6+10;
const int MOD=1e9+7;

ll fac[N],rev[N],revfac[N];

ll A(int n,int k){
        if (k>n||k<0) return 0;
        return fac[n]*revfac[n-k]%MOD;
}
ll C(int n,int k){
        if (k>n||k<0) return 0;
        return A(n,k)*revfac[k]%MOD;
}
void prepare(){
        fac[0]=1;
        for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
        rev[1]=1;
        for(int i=2;i<N;i++) rev[i]=MOD-(MOD/i)*rev[MOD%i]%MOD;
        revfac[0]=1;
        for(int i=1;i<N;i++) revfac[i]=revfac[i-1]*rev[i]%MOD;
}
int main(){
        prepare();
        int n;
        cin>>n;
        if (n==2){
                cout<<1;
                return 0;
        }
        ///last move
        n--;
        ll ans=fac[n];
        for(int i=1;i<=n;i++) {
                ///no left tail and no right tail
                ans=(ans+A(n-2,i)*fac[n-i])%MOD;
                ///no left or no right tail
                ans=ans+2*A(n-2,i-1)*i%MOD*fac[n-i]%MOD;
        }
        for(int i=1;i<=n;i++){
                ///force to have both head and tail
                ll way=A(n-2,i-2)*fac[n-i]%MOD*A(i,2)%MOD;
                ///minus some states
                way=(way-fac[i]*C(i-1,n-i)%MOD*fac[n-i])%MOD;
                ans=(ans+way)%MOD;
        }
        cout<<(ans+MOD)%MOD;
}


Measured memory_bytes: 47232
import Data.List

main :: IO ()
main = do
  (n:x:_) <- map read . words <$> getLine :: IO [Int]
  as <- sort . map read . words <$> getLine
  let (left, right) = span (<= x) $ scanl1 (+) as 
      sm = sum as
      len = length left
      ans = if null right && sm < x then len-1 else len 
  putStrLn $ show $ ans


Measured memory_bytes: 1020
#include <cstdio>
#include <iostream>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define inver(a) power(a, mod - 2)
#define F(x, y) C(x - 1 + y, y)
using namespace std;
inline char nc()
{
    return getchar();
	static char buf[100000], *l = buf, *r = buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
	x = 0; int f = 1, ch = nc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=nc();}
	x *= f;
}
typedef long long ll;
const int mod = 998244353;
const int maxn = 2000050;
int n, m;
int fac[maxn];
int fac_inv[maxn];
inline int dec(int x) {return x < 0 ? x + mod : x;}
inline ll C(int x, int y)
{
    return (ll)fac[x] * fac_inv[y] % mod * fac_inv[x - y] % mod;
}
ll power(ll x, ll y)
{
    ll re = 1;
    while(y)
    {
        if(y & 1) re = re * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return re;
}
void init(int n)
{
    fac[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        fac[i] = (ll)fac[i - 1] * i % mod;
    }
    fac_inv[n] = inver(fac[n]);
    for(int i = n; i >= 1; --i)
    {
        fac_inv[i - 1] = (ll)fac_inv[i] * i % mod;
    }
}
int cal(int x, int y)
{
    int re = F(n, x);
    re = dec(re - y * F(n, x - m) % mod);
    if(x > m) re = dec(re - (n - y) * F(n, x - m - 1) % mod);
    return re;
}
int solve()
{
    int an = 0;
    for(int i = 0; i <= min(m, n); ++i)
    {
        if((3 * m - i) & 1) continue;
        an = (an + cal((3 * m - i) >> 1, i) * C(n, i)) % mod;
    }
    return an;
}
int main()
{
    read(n), read(m);
    init(n + (m << 1));
    printf("%d\n", solve());
    return 0;
}


Measured memory_bytes: 15872
import string
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


a = I()
print(a + a ** 2 + a ** 3)


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

using namespace std;

#define MAX 1000

int main(){
  int N, Num[MAX], P[MAX], Q[MAX], R[MAX], Cal[MAX];

  while(cin >> N, N){
    int p, q, r, c;
    for(int i = 0 ; i < N ; i++){
      cin >> Num[i] >> P[i] >> Q[i] >> R[i];
      Cal[i] = P[i]*4 + Q[i]*9 + R[i]*4;
    }

    vector<int> ans;
    cin >> p >> q >> r >> c;
    for(int i = 0 ; i < N ; i++){
      if(P[i] <= p && Q[i] <= q && R[i] <= r && Cal[i] <= c){
        ans.push_back(Num[i]);
      }
    }
    int size = ans.size();
    if(size){
      for(int i = 0 ; i < size ; i++){
        cout << ans[i] << endl;
      }
    }else{
      cout << "NA" << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 1244
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000001;
const ll LMAX=1000000000000001;
ll gcd(ll a,ll b){if(a<b)swap(a,b);while((a%b)!=0){a=b;b=a%b;}return b;}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};


int main(){
  char a,b; cin>>a>>b;
  if(a=='H'){
    if(b=='H')
    puts("H");
    else
    puts("D");
  }else{
    if(b=='H')
    puts("D");
    else
    puts("H");
  }

  return 0;
}


Measured memory_bytes: 256
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
a = A1*T1-B1*T1
b = A2*T2-B2*T2

if a<0:
    if b<0:
        print(0)
    elif b==0:
        print(0)
    elif b>0:
        if a<-b:
            print(0)
        elif a==-b:
            print('infinity')
        else:
            d = a+b
            
            if a%d==0:
                n = (-a)//d-1
                print(2*n+2)
            else:
                n = (-a)//d
                print(2*n+1)
elif a==0:
    if b<0:
        print(1)
    elif b==0:
        print('infinity')
    elif b>0:
        print(1)
elif a>0:
    if b<0:
        if a>-b:
            print(0)
        elif a==-b:
            print('infinity')
        else:
            d = -a-b
            
            if a%d==0:
                n = a//d-1
                print(2*n+2)
            else:
                n = a//d
                print(2*n+1)
    elif b==0:
        print(0)
    elif b>0:
        print(0)

Measured memory_bytes: 38384
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF INT_MAX
#define LLINF LLONG_MAX
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007
#define MODB  998244353 

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

int main() {
	ll ans = 0;
	ll tmp = 0;
	int n; cin >> n;
	bool ch = false;
	REP(i, n){
		int x, y;
		cin >> x >> y;
		if(x==y) tmp++;
		else tmp = 0;
		if (tmp >=3) ch = true;
	}
	if (ch) cout << "Yes" << endl;
	else cout << "No" << endl;
	//cout << ans << endl;
}

Measured memory_bytes: 3636
def solve(nums):
  while len(nums) > 1:
    nums = [nums[i] + nums[i + 1] for i in range(len(nums) -1)]
  return nums[0] % 10

while True:
  try:
    s = list(map(int, list(input())))
    print(solve(s))

  except EOFError:
    break



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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);

int main() {
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        ret %= MOD;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count))%MOD;
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}



Measured memory_bytes: 3628
from collections import deque
N = int(input())
A = [int(x) for x in input().split()]
d = deque()
for i in range(N):
    d.append(A[i])
ans = 0
index = 1
if min(A) != 1:
    print(-1)
else:
    for i in range(N):
        left = d.popleft()
        if left == index:
            index += 1
        else:
            ans += 1
    print(ans)


Measured memory_bytes: 26772
#2.find ans
def calc_ans(n,x,m):
    ans = 0
    #2. make one
    ones = sum(m)
    x = x-ones
    ans = ans + len(m)

    #3. sort min and divide
    m.sort(reverse=False)
    for price in m:
        ans = ans + (x//price)
        x = x % price
        
    return ans

def main():
    #1.input
    n,x = map(int, input().split())
    m = []
    for _ in range(n):
        m.append(int(input()))
    
    ans = calc_ans(n,x,m)
    print(ans)

if __name__ == "__main__":
    main()
    

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

int n, m, num, ans = 0;
vector<vector<int>> g(200010);
bool vis[200010];

void dfs(int v) {
	vis[v] = true;
	num++;
	for(int i = 0; i < g[v].size(); i++) {
		if(!vis[g[v][i]]) {
			dfs(g[v][i]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	int a, b;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			num = 0;
			dfs(i);
			ans = max(ans, num);
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 23456
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
using namespace std;

typedef pair<int,int> P;

#define rep(i,s,e) for(int i = (s);i <= (e);i++)
#define NO cout << "Impossible" << endl;return 0;
int n;
int a[110];
int cou[110];

vector<int> vec;
int main()
{
	cin >> n;
	rep(i,1,n) cin >> a[i];
	rep(i,1,n) vec.push_back(a[i]);
	rep(i,1,n) cou[a[i]]++;
	sort(vec.rbegin(),vec.rend());

	int s = vec.front();

	int minus = 0;

	for(int i = s;i >= 0;i--)
	{
		if(i - minus < 0)
		{
			if(cou[i] > 0)
			{
				//cout << 1;
				NO
			}
		}
		else if(i - minus == 0)
		{
			if(cou[i] > 1)
			{
				//cout << 2;
				NO
			}
		}
		else if(i - minus == 1)
		{
			if(cou[i] != 2)
			{
				//cout << 3;
				NO
			}
		}
		else
		{
			if(cou[i] < 2)
			{
				//cout << 4;
				NO
			}
		}	
		minus++;
	}
	cout << "Possible" << endl;
	return 0;
}




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

int main()
{
	int n, m, l;
	cin >> n >> m >> l;
	static long A[100][100],B[100][100],C[100][100];
	for(int i=0;i<n;++i)
		for (int j = 0; j < m; ++j) {
			cin >> A[i][j];
		}
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < l; ++j) {
			cin >> B[i][j];
		}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < l; ++j) {
			for (int k = 0; k < m; ++k) {
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < l; ++j) {
			if (j == 0)
				cout << C[i][j];
			else
				cout << " " << C[i][j];
		}
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 3248
#include <stdio.h>

int main(void) {
	int N;
	int H[20];
	int i,max,cnt=0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d",&H[i]);
	}

	for (i = 0; i < N; i++) {
		if (i == 0) {
			max = H[i];
			cnt++;
		}
		else {
			if (max <= H[i]) {
				cnt++;
				max = H[i];
			}
		}
	}

	printf("%d", cnt);
}

Measured memory_bytes: 128
package main

import (
	"fmt"
	"sort"
)

func battle(h int, attack int, arrB []int) int {
	var cnt = 0
	for i := range arrB {
		if arrB[i] < attack {
			break
		}
		h -= arrB[i]
		cnt++
		if h <= 0 {
			break
		}
	}
	if h <= 0 {
		return cnt
	}

	if h%attack > 0 {
		return cnt + h/attack + 1
	}
	return cnt + h/attack
}

func main() {
	var n, h int
	fmt.Scan(&n, &h)
	arrB := make([]int, n)
	var attack = 0
	for i := 0; i < n; i++ {
		var a int
		fmt.Scan(&a, &arrB[i])
		if a > attack {
			attack = a
		}
	}
	sort.Sort(sort.Reverse(sort.IntSlice(arrB)))

	fmt.Println(battle(h, attack, arrB))
}


Measured memory_bytes: 5504
#include<iostream>
#include<string>
using namespace std;
int main()
{
   string s,t;
   cin>>s>>t;
   int c=0;
   int l=s.size(),k=t.size();
   if(l+1==k)
   {
       for(int i=0;i<l;i++)
       {
           if(s[i]!=t[i])
           {
               c++;
           }


       }
                  if(c>0)
           {
               cout<<"No"<<endl;
           }
           else{cout<<"Yes"<<endl;
           }
   }
   else{
    cout<<"No"<<endl;
   }




    return 0;

}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define endl "\n"
using namespace std;

const int mod = 1e9 + 7;
int32_t main() {

    fast
    int k;
    cin >> k;

    if(k % 2 == 0)cout << -1 << endl;
    else {
        int ans = 1;
        int x = 7;
        while(x % k != 0 && ans <= k) {
            x = x * 10;
            x += 7;
            x %= k;
            ans++;
        }
        if(x % k != 0)cout << -1 << endl;
        else
            cout << ans << endl;

    }


    return 0;
}



Measured memory_bytes: 3632
#include <stdio.h>
#include <ctype.h>
#include <string.h>


int main() {
        int K;
        char str[101];
        scanf("%d", &K);
        int j=0;
        scanf("%s",str);


        int i;

        for (i = 0; str[i] != '\0'; ++i);

//printf("%d%d",i,K);
if (K >= i)printf("%s", str);
        else {
                for (j = 0; j < K; j++) {
                        printf("%c", str[j]);
                }
                printf("...");

        }
        return 0;
}

Measured memory_bytes: 1732
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

//Test Case Tweaking
public class Main{

	class E{
		int t, c;
		public E(int t, int c) {
			this.t = t;
			this.c = c;
		}
	}
	
	int[][] d;
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		int INF = 1<<29;
		for(;;){
			int n = sc.nextInt(), m = sc.nextInt(), C = sc.nextInt();
			if((n|m|C)==0)break;
			List<E>[] e = new List[n+1];
			for(int i=1;i<=n;i++)e[i]=new ArrayList<E>();
			while(m--!=0){
				int s = sc.nextInt(), t = sc.nextInt(), c = sc.nextInt();
				e[s].add(new E(t, c));
			}
			d = new int[n+1][n+1];
			for(int[]a:d)Arrays.fill(a, INF);
			PriorityQueue<int[]> q = new PriorityQueue<int[]>(n, new Comparator<int[]>() {
				public int compare(int[] o1, int[] o2) {
					return d[o1[0]][o1[1]] - d[o2[0]][o2[1]];
				}
			});
			d[1][0] = 0;
			q.add(new int[]{1, 0});
			while(!q.isEmpty()){
				int[] V = q.poll();
				int v = V[0], K = V[1];
				for(E r:e[v]){
					if(d[v][K]+r.c < d[r.t][K]){
						d[r.t][K] = d[v][K]+r.c; q.add(new int[]{r.t, K});
					}
					if(K+1<=n && d[v][K] < d[r.t][K+1]){
						d[r.t][K+1] = d[v][K]; q.add(new int[]{r.t, K+1});
					}
				}
			}
			for(int k=0;k<=n;k++)if(d[n][k]<=C){
				System.out.println(k); break;
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 16000
N,K,Q = (int(i) for i in input().split())
A = []
X = []
for i in range(Q):
    a = int(input())
    A.append(a)

for i in range(N):
    X.append(0)

for i in range(Q):
    x = A[i]
    X[x-1] += 1

for i in range(N):
    if Q - X[i] < K:
        print('Yes')
    else:
        print('No')
    

Measured memory_bytes: 8644
import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
c = sorted(list(map(int, input().split())))
ans = 0

for i in b:
    an = bisect.bisect_left(a, i)
    cn = bisect.bisect_right(c, i)
    ans += an*(n - cn)

print(ans)

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

using i64 = int64_t;

int main(){
  int n;
  cin >> n;
  vector<int> a, b, c;
  for(int i=0;i<n;++i){
    int tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
  for(int i=0;i<n;++i){
    int tmp;
    cin >> tmp;
    b.push_back(tmp);
  }
  for(int i=0;i<n-1;++i){
    int tmp;
    cin >> tmp;
    c.push_back(tmp);
  }
  
  int ans = 0;
  for(int i=0;i<n;++i){
    ans += b[a[i]-1];
    if(i > 0 && a[i] == a[i-1] + 1){
      ans += c[a[i-1]-1];
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
struct elem
{
    int p,y,index;
};
elem v[100002];
int w[100002],id[100002],sol[20];

inline bool cmp(const elem &a,const elem &b)
{
    if(a.p==b.p)
        return a.y<b.y;
    return a.p<b.p;
}

void afis(int i)
{
    int a=v[i].p,b=id[i];
    for(i=1;i<=12;i++)
        sol[i]=0;
    i=12;
    while(b!=0)
    {
        sol[i]=b%10;
        b/=10;
        i--;
    }
    i=6;
    while(a!=0)
    {
        sol[i]=a%10;
        a/=10;
        i--;
    }
    for(i=1;i<=12;i++)
        cout<<sol[i];
    cout<<'\n';
}

int main()
{
    int n,m,i,j;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>v[i].p>>v[i].y;
        v[i].index=i;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++)
        w[v[i].index]=i;
    i=1;
    while(i<=m)
    {
        j=1;
        id[i]=j;
        while(v[i].p==v[i+1].p)
        {
            j++;
            i++;
            id[i]=j;
        }
        i++;
    }
    for(i=1;i<=m;i++)
        afis(w[i]);
    return 0;
}


Measured memory_bytes: 3456
#include <iostream>
using namespace std;
int main()
{
int n,a,b;
cin>>n>>a>>b;
int c = 0;
for (int i=0;i<n;i++)
{
int x;cin >> x;
if (a<=x&&x<b) c++;
}
cout << n-c << endl;
return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sa = sorted(a)
l = sa[N // 2 - 1]
r = sa[N // 2]
for i in range(N):
  if a[i] <= l: print(r)
  else: print(l)

Measured memory_bytes: 85972
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll   long long int
void fast()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
}

int main(void)
{
  fast();
  ll n;
  cin>>n;

  map<string,ll> m;
  ll ans=INT_MIN;
  for(ll i=0;i<n;i++)
  {
  	 string s;
  	 cin>>s;
  	 m[s]++;
  	 ans = max(ans,m[s]);
  }

  vector<string> v;

  for(auto it=m.begin();it!=m.end();it++)
  {
  		if(it->second==ans)
  		{
  			v.push_back(it->first);
  		}
  }
 for(int i=0;i<v.size();i++)
 {
     cout<<v[i]<<endl;
 }
}

Measured memory_bytes: 25584
#include<iostream>
#include<vector>

class UnionFind {
  public:
    std::vector<int> rank, p;
    UnionFind() {}
    UnionFind(int size) {
      rank.resize(size, 0);
      p.resize(size, 0);
      for(int i = 0; i < size; i++) {
        makeSet(i);
      }
    }
    
    void makeSet(int x) {
      p[x] = x;
      rank[x] = 0;
    }

    bool isSame(int x, int y) {
      return find(x) == find(y);
    }
    
    void unite(int x, int y) {
      link(find(x), find(y));
    }

    void link(int x, int y) {
      if(rank[x] > rank[y]) {
        p[y] = x;
      } else if(rank[x] < rank[y]) {
        p[x] = y;
      } else {
        p[x] = y;
        rank[y]++;
      }
    }

    int find(int x) {
      if(x != p[x]) {
        p[x] = find(p[x]);
      }
      return p[x];
    }
};

int main() {
  int n, q;
  int com, x, y;

  std::cin >> n >> q;
  UnionFind uf = UnionFind(n);
  
  for(int i = 0; i < q; i++) {
    std::cin >> com >> x >> y;
    if(com == 0) {
      uf.unite(x, y);
    } else if(com == 1) {
      printf("%d\n", uf.isSame(x, y) ? 1 : 0);
    }
  }
  return 0;
}
      



Measured memory_bytes: 3304
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int h = sc.nextInt();
		int w = sc.nextInt();
		int m = sc.nextInt();

		int bombH[] = new int[m];
		int bombW[] = new int[m];
		int bombCol[] = new int[h];
		int bombRow[] = new int[w];
		RowInfo rowInfo[] = new RowInfo[w];

		int colMax = 0;
		int rowMax = 0;

		HashSet<String> set = new HashSet<String>();
		for(int i = 0; i < m; i++){
			bombH[i] = sc.nextInt() - 1;
			bombW[i] = sc.nextInt() - 1;

			set.add(bombW[i]+ " " +bombH[i]);

			bombCol[bombH[i]]++;
			bombRow[bombW[i]]++;

			colMax = Math.max(colMax, bombCol[bombH[i]]);
			rowMax = Math.max(rowMax, bombRow[bombW[i]]);
		}

		for(int i = 0; i < w; i++){
			rowInfo[i] = new RowInfo(bombRow[i], i);
		}

		Arrays.sort(rowInfo);

//		System.out.println(colMax+ " "+rowMax);

		int result = 0;

		for(int i = 0; i < h; i++){
			if(bombCol[i] < colMax){
				continue;
			}

			for(int j = 0; j < w; j++){
				if(rowInfo[j].count < rowMax){
					break;
				}

				int tmpResult = bombCol[i] + rowInfo[j].count;

				if(set.contains(rowInfo[j].oldIndex + " " + i)){
					tmpResult--;
				}

				result = Math.max(result, tmpResult);

				if(result == colMax + rowMax){
					System.out.println(result);
					return;
				}
			}
		}

		System.out.println(result);
	}
}

class RowInfo implements Comparable<RowInfo>{
	int count = 0;
	int oldIndex;

	RowInfo(int count, int oldIndex){
		this.count = count;
		this.oldIndex = oldIndex;
	}

	@Override
	public int compareTo(RowInfo r) {
		// TODO 自動生成されたメソッド・スタブ
		return r.count - this.count;
	}


}


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

#define MAX 1000

int main() {
  char s[MAX] = {};
  char ans[MAX] = {};
  int w;
  scanf("%s", s);
  scanf("%d", &w);

  int l;
  l = strlen(s);

  for(int i = 0; i < strlen(s); i += w){
    printf("%c", s[i]);
  }

  return 0;
}

Measured memory_bytes: 128
g = [[-1 for _ in range(15)] for _ in range(15)]#証言格納用
n = int(input())
ans=0
for i in range(n):
  m = int(input())
  for j in range(m):
    x,y = map(int, input().split())
    g[i][x-1] = y#i番目の人の証言を格納、人の番号xは0始まり
for i in range(1<<n):#Bit全探索
  honests = [0 for _ in range(n)]#正直者フラグ、後で1で人数計算
  for j in range(n):#n人を一人ずつ、チェックする
    if (i>>j) &1:#Bitが立っているかを1で表す
      honests[j] = 1#Bitが立っていれば、j番目は正直と仮定 
  ok = True#矛盾が無い仮定で、Bit全探索を開始する
  for j in range(n):#n人を一人ずつ、チェック(j番目の人を見る)
    if honests[j]:#j番目が、もし正直なら証言を確認(不正直の証言は無視)
      for k in range(n):#k番目の人に対する証言を確認
        if g[j][k] == -1: continue#証言していなければ、飛ばす
        if g[j][k] != honests[k]: ok = False#証言とフラグ仮定が不一致
  if ok:#矛盾がないケースについて調べる
    ans = max(ans, honests.count(1))#正直であるフラグ1が立っている数
print(ans)
'''
・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、
その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。
ある人に対して矛盾する二つの証言があるとき、
どちらか一方の証言は必ず仮定に矛盾する。したがって、
この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、
正直者が最も多い組の正直者の人数を求めれば良い。
人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で
格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため
0から始めるものとする。
・人xが人yに対して正直者であると証言するとき、
二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき
二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、
二次元配列g[x][y]を-1にする。
・入力よりNの最大が15なので、
15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。
人iが「人xはyである」と証言しているときg[i][x]=yである。
（入力で受け取る「人の番号」は1から始まるため、
コードでは受け取った値から1引いている。）
g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y
二次元配列gの作成と入力の受け取りは以上である。
次に問題を解く中心となるコードを実装していく。
まず、全ての正直者の組を表現するために二進数表記を用いることを考える。
二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
作り出した正直者の組それぞれに対して何らかの処理を行うため、
これは全bit探索である。
「正直者の組を作りだす」部分のコード。
・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。
for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
honests[j]が1であることは,人jは正直者であると仮定することに対応する。
次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち
正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。
・求める値「N人のうち正直者であり得る最大人数」を格納するための
変数ansをデフォルト値0で用意しておく。
求める値は0以上の値であり以下のループ処理によって、
より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値
Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。
honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので
変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を
数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。
'''

Measured memory_bytes: 9084
def bubbleSort c, n
    for i in 1...n
        for j in (i...n).to_a.reverse
            if c[j][1] < c[j - 1][1]
                temp = c[j]
                c[j] = c[j - 1]
                c[j - 1] = temp
            end
        end
    end
end
 
def selectionSort c, n
    for i in 0...n
        minj = i
        for j in i...n
            minj = j if c[j][1] < c[minj][1]
        end
        temp = c[i]
        c[i] = c[minj]
        c[minj] = temp
    end
end
 
def checkOrder arr
    strings = Array.new(11){""}
    arr.each{|card| strings[card[1].to_i] += card[0]}
    return strings
end
 
n = gets.to_i
arr = gets.chomp.split
 
arr2 = arr.dup
bubbleSort(arr2, n)
puts arr2.join(" ")
puts (checkOrder(arr) == checkOrder(arr2)) ? "Stable" : "Not stable"
 
arr2 = arr.dup
selectionSort(arr2, n)
puts arr2.join(" ")
puts (checkOrder(arr) == checkOrder(arr2)) ? "Stable" : "Not stable"

Measured memory_bytes: 8748
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <functional>
#include <utility>
#include <cctype>
#include <fstream>

using namespace std;

#define ll long long
#define MOD 1000000007
#define INF 2000000000
#define LINF 9000000000000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define du(x) cout<<#x<<'='<<x<<endl
#define du2(x,y) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<'\n'<<endl
#define du3(x,y,z) cout<<#x<<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<'\n'<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl
#define ddarr(arr,a,b) rep(i,a){rep(j,b){cout<<*(arr+i*b+j)<<' ';}cout<<endl;}
#define ddd ifstream in("Text.txt");cin.rdbuf(in.rdbuf());

int h[200];

int main() {
    int N;
    cin >> N;
    rep(i, N)cin >> h[i];

    int cnt = 1;
    int ma = h[0];
    for(int i=1;i<N;i++){
        if (ma <= h[i]) {
            cnt++;
            ma = h[i];
        }
    }


    cout << cnt << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lli = long long int;
using ulli = unsigned long long int;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl


namespace atcoder {
	template<typename T>
	T ncr(T left, T right) {
		right = min(left - right, right);
		T ans = 1;
		for (T i = 1; i <= right; i++) {
			ans = ans * (left - right + i) / i;
		}
		return ans;
	}

	const int LIMIT = 1000000007;
	const int tenfive = 100000;
}

using namespace atcoder;

int main() {
	lli k, a, b;
	cin >> k >> a >> b;
	if (a+1 >= b || k <= a) {
		cout << k + 1 << endl;
		return 0;
	}
	k -= (a - 1);
	lli c = a;
	lli sub = b - a;

	c = sub * (k / 2) + k % 2 + a;
	cout << c << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
        int a[3], i, j, temp;
        scanf("%d%d%d", &a[0], &a[1], &a[2]);
        
        for (i = 0; i < 2; i++) {
                for (j = 0; j < 2; j++) {
                        if (a[j] > a[j+1]) {
                                temp = a[j];
                                a[j] = a[j+1];
                                a[j+1] = temp;
                        }
                }
        }
        
        printf("%d %d %d\n", a[0], a[1], a[2]);

        return 0;
}

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

int main(){
  long double a, b, c;
  long double eps = 1.0E-14;
  cin >> a >> b >> c;
  //cout << sqrt(a) << ' ' << sqrt(b) + eps<< ' ' << sqrt(c) << endl;
  if(sqrt(a) + sqrt(b) + eps < sqrt(c)) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <math.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
using namespace std ;
#define ld long double
#define int long long
#define ii pair<int,int>
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL); clock_t beg = clock()
#define dbg(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
//const int N = 3e5+7 ;
//const int INF = 1e18 ;
//const int MOD = 1e9 + 7 ;

int __gcd(int a,int b){
	if(b==0) return a ;
	return __gcd(b,a%b) ;
}

int g(int a ,int b , int c){
	return __gcd(a,__gcd(b,c)) ;
}	
int add(int a ,int b){
	return a+b ;
}
void solve(){
	int k ;
	cin >> k ;
	int ans  = 0 ;
	for(int i = 1 ; i <= k ; i++){
		for(int j = 1 ; j <= k ; j++){
			for(int b = 1 ; b <= k ; b++){
				ans = add(ans, g(i,j,b)) ;
			}
		}
	}
	cout << ans ;
}

int32_t main(){
	FAST_IO ;
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}
    cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
}


Measured memory_bytes: 3648
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int k = sc.nextInt();
		int[] n = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};


		// 出力
		System.out.println(n[k-1]);
	}
}

Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int a[100010];
  for (int i = 0; i < 100010; i++) a[i] = 0;
  for (int i = 0; i < n; i++) {
    int l, r;
    cin >> l >> r;
    for (int j = l; j <= r; j++) a[j]++;
  }
  int sum = 0;
  for (int i = 0; i < 100010; i++) sum += a[i];
  cout << sum << endl;
}

Measured memory_bytes: 640
S = str(input())

ff = int(S[0])*10 + int(S[1])
bb = int(S[2])*10 + int(S[3])

if ff <= 12 and ff >= 1 and bb <= 12 and bb>= 1:
  print('AMBIGUOUS')
elif ff <= 12 and ff >= 1:
  print('MMYY')
elif bb <= 12 and bb >= 1:
  print('YYMM')
else:
  print('NA')
  

Measured memory_bytes: 3060
S = input()
T = input()

con = 0

ans = "Yes"

for i in range(0,len(S)):
  for j in range(0,i):
    if T[i] == T[j]:
      if S[i] != S[j]:
        ans = "No"
        break
      break
    if S[i] == S[j]:
      if T[i] != T[j]:
        ans = "No"
        break
      break


print(ans)



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

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  if (a[a.length() - 1] == b[0] && b[b.length() - 1] == c[0])
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

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

using ll= long long;
const ll INF=1LL<<60;
const ll MOD=1e9+7;

int main(){
    while(1){
        int n, x;
        ll res=0;
        cin >> n >> x;
        if(n==0 && x==0) break;
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                for(int k=j+1; k<=n; k++){
                    if(i+j+k == x) res++;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}


Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}
int a[N];
bool solve()
{
	int n=read(),Max=0,Min=n,s1=0,s2=0;
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) Max=max(Max,a[i]);
	for (int i=1;i<=n;i++) Min=min(Min,a[i]);
	if (Max-Min>1) return 0;
	if (Max==Min) return a[1]==n-1||a[1]<=n/2;
	for (int i=1;i<=n;i++) if (a[i]==Min) s1++;
	for (int i=1;i<=n;i++) if (a[i]==Max) s2++;
	return 0<Max-s1&&Max-s1<=s2/2&&(s1+1<=Max||Max<=s1+s2/2);
}

int main()
{
	puts(solve()?"Yes":"No");

	return 0;
}

Measured memory_bytes: 640
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * m
c = [0] * m
bc = []
for i in range(m):
    b[i],c[i] = map(int,input().split())
    bc.append([b[i],c[i]])
aa = []

for i in range(n):
    aa.append([1,a[i]])
all = aa + bc

all.sort(key = lambda x:x[1],reverse = True)
nok = n
ans = 0
for i in range(n):
    if all[i][0] <= nok:
        ans += all[i][0] * all[i][1]
        nok -= all[i][0]
    else:
        ans += nok * all[i][1]
        break

print(ans)


Measured memory_bytes: 40888
from collections import Counter
N = int(input())
a = Counter(list(map(int, input().split())))
b = set(a.values())
if a[0] == N:
    print('Yes')
elif N % 3 == 0:
    if len(b) == 1:
        c = [x for x in a.keys()]
        if len(c) == 3:
            if c[0] ^ c[1] ^ c[2] == 0:
                print('Yes')
            else:
                print('No')
        else:
            print('No')
    elif len(b) == 2:
        if a[0] == N // 3:
            if (N*2) // 3 in b:
                print('Yes')
            else:
                print('No')
        else:
            print('No')
    else:
        print('No')
else:
    print('No')

Measured memory_bytes: 14468
N = int(input())
A = list(map(int, input().split()))
res = [0] * N
for i in range(N, 0, -1):
    tmp = 0
    for j in range(i * (N // i), i, -i):
        tmp += res[j - 1]
    if A[i - 1] != (tmp + res[i - 1]) % 2:
        res[i - 1] ^= 1
print(sum(res))
ans = [i + 1 for i, v in enumerate(res) if v == 1]
if ans:
    print(*ans)


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

int main(void){
    char B;
    scanf("%c", &B);
    if(B=='A') printf("T\n");
    if(B=='T') printf("A\n");
    if(B=='C') printf("G\n");
    if(B=='G') printf("C\n");
    return 0;
}


Measured memory_bytes: 128
n, m = map(int, input().split())
req = [list(map(int, input().split())) for _ in range(m)]
for i in range(1000):
    num = str(i)
    if len(num) != n:
        continue
    ok = True
    for s, c in req:
        if int(num[s - 1]) != int(c):
            ok = False
    if ok:
        print(num)
        exit()
print(-1)


Measured memory_bytes: 3060
#include<string>
#include<iostream>
#include<set>

struct SubStringTopIndex{
	size_t index;//参照するインデックス
	const std::string * const pStr;//元の文字列
	SubStringTopIndex(const std::string *i_pStr,size_t i):index(i),pStr(i_pStr){}
	bool operator<(const SubStringTopIndex &otherobj)const{
		size_t ts=this->pStr->size()-this->index,os=otherobj.pStr->size()-otherobj.index;
		size_t max;
		if(ts<os){
			max=ts;
		} else{
			max=os;
		}
		for(size_t i=0;i<max;i++){
			char tc=this->pStr->at(this->index+i),oc=otherobj.pStr->at(otherobj.index+i);
			if(tc<oc){
				return true;
			} else if(tc>oc){
				return false;
			}
		}
		//ここに着くのはthisまたはotherobjがもう一方の部分文字列である場合
		if(max!=os){
			return true;
		} else{
			return false;
		}
	}
};

int main(){
	//入力機構
	std::string s;
	int K;
	std::cin>>s>>K;
	//処理機構
	//最小の文字をsから探す
	std::set<SubStringTopIndex> ssSet;
	for(size_t i=0,size=s.size();i<size;i++){
		ssSet.insert(SubStringTopIndex(&s,i));
	}
	//ssSetの先頭が最初の文字列。ここからK個SubStringを探す
	bool endflag=false;
	std::set<std::string> sslist;//既に見つけた文字列のリスト
	for(SubStringTopIndex ssti:ssSet){
		//ssSetが表す場所からすべての文字列を出力してsslistに格納
		for(size_t i=1,size=ssti.pStr->size();i+ssti.index<=size;i++){
			std::string str=ssti.pStr->substr(ssti.index,i);
			if(sslist.find(str)==sslist.end()){
				sslist.insert(str);
			}
			if(sslist.size()==K){
				endflag=true;
				break;
			}
		}
		if(endflag){
			break;
		}
	}
	//出力機構
	std::set<std::string>::iterator it=sslist.begin();
	for(int i=1;i<K;i++){
		it++;
	}
	std::cout<<(*it)<<std::endl;

	return 0;
}


Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(void)
{
	while(1)
	{
		double xa1,ya1,xa2,ya2,xb1,yb1,xb2,yb2;
		cin>>xa1>>ya1>>xa2>>ya2>>xb1>>yb1>>xb2>>yb2;
		if(cin.eof())break;
		if(xa1<=xb2&&xa2>=xb1&&ya1<=yb2&&ya2>=yb1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

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

#define rep(var, start, end)  for(int var = start; var <= end; ++var)
#define drep(var, start, end) for(int var = start; var >= end; --var)

typedef long long ll;

using namespace std;

int main() {

    string S, T, tmp= "";
    string t[4] = {
        "dream",
        "erase",
        "eraser",
        "dreamer"
    };

    cin >> S;

    while(S.size() > T.size()) {
        rep(i, 0, 3) {
            tmp = t[i] + tmp;
            if (S.find(tmp, S.size() - tmp.size()) != string::npos) {
                T = tmp;
                break;
            } else {
                tmp = T;
                if (i == 3) {
                    cout << "NO" << endl;
                    return 0;
                }
                continue;
            }
        }
    }

    if (S == T) {
        cout << "YES";
    } else {
        cout << "NO";
    }

    cout << endl;
    
    return 0;
}

Measured memory_bytes: 512
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long N, L;
    scan(N, L);
    auto A = aryread();
    foreach (i; 0 .. N - 1)
    {
        if (L <= A[i] + A[i + 1])
        {
            writeln("Possible");
            auto ans = new long[](N - 1);
            long ptr;
            ans[ptr++] = i;
            foreach (j; i + 1 .. N - 1)
            {
                ans[ptr++] = j;
            }
            foreach_reverse (j; 0 .. i)
            {
                ans[ptr++] = j;
            }
            foreach_reverse (a; ans)
            {
                writeln(a + 1);
            }
            return;
        }
    }
    writeln("Impossible");
}


Measured memory_bytes: 7508
D,N = map(int,input().split())
ans = 0

if D == 0:
  ans = N
  if N == 100:
    ans = 101
elif D == 1:
  ans = N * 100
  if N == 100:
    ans = 10100
elif D == 2:
  ans = N * 10000
  if N == 100:
    ans = 1010000
print(ans)

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

const int N = 200005;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, x, t, a[N];
long long ans;
string s;

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
	int cur = 0;
	for(int i = 0; i < n; ++i)
		if(a[i] < cur)
			ans += cur - a[i];
		else cur = a[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4536
import java.math.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        String tmp = "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51";
        String[] h = tmp.split(", ");
        System.out.println(h[k-1]);
    }
}


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

int main() {
    string str;
    cin >> str;
    int q;
    cin >> q;
    string order, x;
    int a, b;

    for(int i=0; i<q; i++) {
        cin >> order;
        cin >> a >> b;
        if(order == "replace") {
            cin >> x;
            for(int j=0; j<x.length(); j++) {
                str[a + j] = x[j];
            }
        } else if(order == "reverse") {
            for(int j=0; j<(b-a+1)/2; j++) {
                char temp;
                temp = str[a + j];
                str[a + j] = str[b - j];
                str[b - j] = temp;
            }
        } else {
            for(int j=0; j<(b-a+1); j++) {
                cout << str[a + j];
            }
            cout << endl;
        }
    }
}

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

using namespace std;
typedef long long lint;

#define RPT(i, b, e) for (int i = ((int)b); i <= ((int)e); i++)
#define RPT0(i, n) RPT(i, 0, ((int)n) - 1)
#define RPT1(i, n) RPT(i, 1, (n))
#define EACH(it, v) for (const auto& it : v)
#define ALL(v) v.begin(), v.end()

void resolve()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    string ans;
    while (A > 0 && C > 0) {
        C -= B;
        if (C <= 0) {
            ans = "Yes";
            break;
        }

        A -= D;
        if (A <= 0) {
            ans = "No";
            break;
        }
    }

    cout << ans << endl;
}

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


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int a;
    cin>>a;
    int ans=0;
    int aa=1;
    rep(i,3){
        aa*=a;
        ans+=aa;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3588