akhauriyash/Code-Regression huggingface dataset:
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC diagnostic error "-std=c++14"

#define isNum(a) (a>='0'&&a<='9')
#define SP putchar(' ')
#define EL putchar('\n')
#define ri register int

template<class T>
inline void in(T&);
template<class T>
inline void out(const T&);

typedef long long ll;
using std::min;
using std::max;
using std::abs;
using std::sort;
using namespace std;

int n,l=1;
string s[200005];
struct Node{
	int sum;
	string s;
}a[200005];

inline bool cmp(Node q,Node p)
{
	if (q.sum!=p.sum) return q.sum>p.sum;
	else return q.s<p.s;
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    in(n);
    for (ri i=1;i<=n;++i) cin>>s[i];
    sort(s+1,s+n+1);
    a[1].sum=1;a[1].s=s[1];
    for (ri i=2;i<=n;++i)
    {
    	if (s[i]!=s[i-1]) a[++l].sum=1,a[l].s=s[i];
    	else a[l].sum++;
    }
    sort(a+1,a+l+1,cmp);
    for (ri i=1;i<=l;++i)
    {
    	if (a[i].sum==a[1].sum) cout<<a[i].s<<endl;
    	else break;
    }
    return 0;
}

template<class T>
void in(T &Re)
{
    T k=0;
    char ch=getchar();
    int flag=1;
    while (!isNum(ch))
	{
        if (ch=='-')
		{
            flag=-1;
        }
        ch=getchar();
    }
    while (isNum(ch))
	{
        k=(k<<1)+(k<<3)+ch-'0';
        ch=getchar();
    }
    Re=flag*k;
}

template<class T>
void out(const T &Wr)
{
    if (Wr<0)
	{
        putchar('-');
        out(-Wr);
    }
	else
	{
        if (Wr<10)
		{
            putchar(Wr+'0');
        }
		else
		{
            out(Wr/10);
            putchar((Wr%10)+'0');
        }
    }
}




Measured memory_bytes: 17408
N = int(input())
V = list(map(int,input().split(" ")))
C = list(map(int,input().split(" ")))
ans = []
for i in range(N):
    ans.append(V[i]-C[i])
total = 0
for i in ans:
    if i>=1:
        total+=i
print(max(total,0))

Measured memory_bytes: 3060
N, K = map(int, input().split())
A = input().split()
A = [int(A[i]) for i in range(len(A))]
for i in range(N-K):
    #print('{}{}'.format(A[i],A[i+K]))
    if A[i] < A[i+K]:
        print('Yes')
    else:
        print('No')

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

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

  int n;
  cin >> n;

  vector<int> p(n), q(n), d(n);
  for (int i = 0; i < n; ++i) cin >> p[i];
  for (int i = 0; i < n; ++i) cin >> q[i];

  int x, y, cnt = 0;
  for (int i = 0; i < n; ++i) d[i] = i+1;

  do {
    if (p == d) x = cnt;
    if (q == d) y = cnt;

    ++cnt;
  } while (next_permutation(d.begin(), d.end()));

  cout << abs(x - y) << '\n';

  return (0);
}

Measured memory_bytes: 3628
#include <stdio.h>

int main()
{
    long long n,m,sum;
    scanf("%lld%lld",&n,&m);
    if(n == (m / 2))
        sum = n;
    else if (n > (m / 2))
        sum = (m / 2);
    else if (n < (m / 2))
    {
        sum = n + ((m/2)-n) / 2;
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 128
K,A,B=map(int,input().split())

if 1>=B-A:
    print(1+K)
    exit()


if (K-(A-1))%2==0:
    print(A+(B-A)*(K-(A-1))//2)
else:
    print(1+A+(B-A)*((K-A)//2))


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <random>
#include <queue>

using namespace std;

using Graph = vector<vector<int> >;

vector<int> seen;

int main()
{
	const int V_MAX = 1e5;
	int N;

	cin >> N;
	/*
	map<int, int> Os;
	map<int, int> Es;
	*/

	vector<pair<int, int> > Os(V_MAX, make_pair(0, 0) );
	vector<pair<int, int> > Es(V_MAX, make_pair(0, 0) );


	int a;
	for (int ni = 0; ni < N / 2; ni++) {
		cin >> a;
		Os[a] = make_pair(Os[a].first + 1, a);
		cin >> a;
		Es[a] = make_pair(Es[a].first + 1, a);
	}

	sort(Os.rbegin(), Os.rend());
	sort(Es.rbegin(), Es.rend());


	int o,e,o2,e2;
	int ans;
	if (Os[0].second != Es[0].second) {
		o = N / 2 - Os[0].first;
		e = N / 2 - Es[0].first;
		ans = o + e;
	}
	else {
		o = N / 2 - Os[0].first;
		e = N / 2 - Es[0].first;
		o2 = N / 2 - Os[1].first;
		e2 = N / 2 - Es[1].first;
		ans = min(o + e2, e + o2);
		if (ans == 0) ans = N / 2;
	}


	//printf("%b", ans);

	cout << ans;
	

	return 0;
}



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

template <typename _tp> inline void read(_tp&x){
	char ch=getchar(),ob=0;x=0;
	while(ch!='-'&&!isdigit(ch))ch=getchar();if(ch=='-')ob=1,ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(ob)x=-x;
}

const int N = 203, mod = 998244353;

struct pnt {
	int x, y;
	inline void in() {read(x), read(y);}
	friend inline pnt operator - (const pnt&A, const pnt&B) {return (pnt) {A.x - B.x, A.y - B.y};}
	friend inline int operator * (const pnt&A, const pnt&B) {return A.x * B.y - A.y * B.x;}
} p[N];

inline bool con(const pnt&A, const pnt&B, const pnt&C) {
	return (C - A) * (B - A) == 0;
}

int n;
int bin[N];
bool vs[N];
ll Ans;

int main() {
	read(n);
	bin[0] = 1;
	for(int i=1;i<=n;++i) bin[i] = (bin[i-1] << 1)%mod;
	for(int i=1;i<=n;++i) p[i].in();
	for(int i=1;i<n;++i) {
		for(int j=1;j<=n;++j) vs[j] = false;
		
		for(int j=i+1;j<=n;++j)
			if(!vs[j]) {
				bool flg = true;
				for(int k=1;k<i;++k)
					if(con(p[i], p[j], p[k]))
						flg = false;
				int ct = 2;
				for(int k=j+1;k<=n;++k)
					if(con(p[i], p[j], p[k]))
						vs[k] = true, ++ct;
				if(flg) Ans += bin[ct] - ct - 1;
			}
	}
	Ans = ((ll)mod*mod - Ans - n - 1 + bin[n])%mod;
	printf("%lld\n", Ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
#define $ ios::sync_with_stdio(0);
#define endl '\n'
using namespace std;
using ll = long long int;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 112345;
int last1[MAXN], last0[MAXN];
int main() {
    int n, m, k;
    cin >> n >> m >> m >> m >> m >> k;
    if (m-n > k) puts(":(");
    else puts("Yay!");
}


Measured memory_bytes: 256
n = gets.chomp.split("").map(&:to_i)
ans = false
ans = true if n[0] == n[1] && n[1] == n[2] && n[2] == n[0]
ans = true if n[1] == n[2] && n[2] == n[3] && n[3] == n[1]
puts ans ? "Yes" : "No"

Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
  
int main(void){
    int n;
    cin >> n;
    
    int x[100];
    int max_val = 0;
    for(int i=0; i<n; i++){
        cin >> x[i];
        if (x[i] > max_val)  max_val = x[i];
        //cout << "x[i] = " << x[i] << endl;
        //cout <<"max_val = " << max_val << endl;
    }
    
    ll ans = 2500000;
    int tmp_ans = 2500000;
    int tmptmp_ans = 0;
    for(int j=1; j<=max_val; j++){
        tmptmp_ans = 0;
        for(int i=0; i<n; i++){
            tmptmp_ans += (x[i] - j) * (x[i] - j);
        }
        //cout << "tmptmp_ans = " << tmp_ans << endl << endl;
        if (tmptmp_ans < tmp_ans) tmp_ans = tmptmp_ans;
    }
    ans = tmp_ans;
    cout << ans << endl;
    return 0;
}

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

int main() {
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  
 if(A+B>C+D){
   cout<<"Left"<<endl;
 }
 else if(A+B<C+D){
   cout<<"Right"<<endl;
 }
  else{
    cout<<"Balanced"<<endl;
  } 
}


Measured memory_bytes: 3640
// Problem: https://codeforces.com/contest/1285/problem/E
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
 
#define ford(i, a, b, c)        for(int i=(a); i<(b); i+=(c))
#define fori(i, a, b)           ford(i,a,b,1)
#define rep(i, n)               fori(i,0,n)
#define ifor(i, a, b)           for(int i=(a); i>=(b); i--)
#define si(x)                   ((int)x.size())
#define SS                      ({int x;scanf("%d",&x);x;})
#define pb                      push_back
#define mp                      make_pair
#define all(a)                  a.begin(),a.end()
#define inf                     (int)1e9
#define linf                    (long long)1e18
#define V                       vector
#define S                       string
#define XX                      first
#define YY                      second
#define P(x)                    cout<<x<<"\n"
#define PVI(v)                  rep(i, si(v)) cout<<v[i]<<" "; puts("")
#define PPI(p)                  cout<<"("<<p.first<<", "<<p.second<<")\n"
#define PVPI(v)                 rep(i, si(v)) cout<<"("<<v[i].first<<", "<<v[i].second<<")"<<(i==si(v)-1?"":", ");puts("")
#define PA(arr1, arr2)          for(auto it = arr1; it != arr2; it++) cout<<*it<<" "; puts("");
typedef V<int> vi;
typedef V<S> vs;
typedef long long ll;
typedef pair<int,int> pii;
const int MOD7 = 1000000000+7;
const int MOD9 = 1000000000+9;
/* ################### Program Body starts here ################ */


int power(int a, int b, int c) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * (long long)a % c;
        a = a * (long long)a % c;
        b /= 2;
    }
    return ans;
}


int f[100000];
int ncr(int n, int r) {
    return (f[n] * (ll)power(f[r], MOD7-2, MOD7)%MOD7) * power(f[n-r], MOD7-2, MOD7) % MOD7;
}

int main() {
    int n = SS, k = SS;
    f[0] = 1;
    fori(i, 1, n) f[i] = f[i-1]*(ll)i%MOD7;
    vi a(n);
    rep(i, n) a[i] = SS;
    sort(all(a));
    int ans = 0;
    fori(i, k-1, n) {
        ans += (a[i]*(ll)ncr(i, k-1) + MOD7*(ll)MOD7)% MOD7;
        ans %= MOD7;
    }
//    cout<<ans<<"\n";
    rep(i, n-k+1) {
        ans -= (a[i]*(ll)ncr(n-i-1, k-1) + MOD7*(ll)MOD7)%MOD7;
        if (ans < 0) ans += MOD7;
        else ans %= MOD7;
    }
    cout<<ans<<"\n";
    
}


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

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; ++i){ cin >> a[i]; }
	int answer = 0;
	for(int i = 0, last = 0; i + 3 <= n; ++i){
		if(a[i] > a[i + 1] && a[i + 1] > a[i + 2]){
			if(last != 0){
				swap(a[i], a[i + 1]);
				swap(a[i + 1], a[i + 2]);
			}else{
				swap(a[i + 1], a[i + 2]);
				++answer;
			}
			last = -1;
		}else if(a[i] < a[i + 1] && a[i + 1] < a[i + 2]){
			if(last != 0){
				swap(a[i], a[i + 1]);
				swap(a[i + 1], a[i + 2]);
			}else{
				swap(a[i + 1], a[i + 2]);
				++answer;
			}
			last = 1;
		}else{
			last = 0;
		}
	}
	cout << answer << endl;
	return 0;
}




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

int main() {
int  N;
    cin >> N ;
  vector<int> A(N);
for (int i = 0; i < N; i++) {
  cin >> A.at(i);
}
    sort(A.begin(), A.end()); 
  cout << A[N-1]-A[0] << endl;  
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	a, b := nextInt(), nextInt()
	if (a%3)*(b%3)*((a+b)%3) == 0 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}
}


Measured memory_bytes: 640
N = int(input())
H= [int(s) for s in input().split()]

#print(N,H)

t=0
k=0

for i in range(1,N):
  if H[i]-H[i-1]<=0:
    k=k+1
    if k > t:
      t=k
  else:
    k=0
    continue
    
print(t)


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

int main(){
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n;i++){
        cin >> a[i];
    }
    bool flag = true;
    int count = 0;
    while (flag)
    {
        for (int i = 0; i < n; i++)
        {
            if ((a[i]%2)!=0){
                flag = false;
            }
            a[i] = a[i] / 2;
        }
        count++;
    }
    cout << count-1 << endl;
    return 0;
}

Measured memory_bytes: 256
from heapq import heapify, heappush, heappop

def max2(x, y): return x if x >= y else y

def solve(As, Bs):
    for A, B in zip(As, Bs):
        if A > B:
            return -1

    PQ = [(-B, i) for i, (A, B) in enumerate(zip(As, Bs)) if A != B]
    heapify(PQ)
    ans = 0
    while PQ:
        B, i = heappop(PQ)
        A, B = As[i], -B
        sumNeib = Bs[i-1] + Bs[(i+1)%N]

        if B <= sumNeib or B-sumNeib < A:
            return -1
        num = (B - max2(A, sumNeib)) // sumNeib
        B -= sumNeib * num
        if B-sumNeib >= A:
            B -= sumNeib
            num += 1

        if A != B:
            heappush(PQ, (-B, i))
        Bs[i] = B
        ans += num

    return ans


N = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

ans = solve(As, Bs)
print(ans)


Measured memory_bytes: 124892
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i= a ; i < b ; ++i)
#define rep(i,n) fo(i,0,n)
#define pln(n) printf("%lld",n)
#define sll(n) scanf("%lld",&n)
#define ss(n) scanf("%s",n)
#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define dbg3(x,y,z) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) <<" , "<< #z <<": "<<(z)<<endl; }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vvvll vector<vector<vector<ll>>>
#define si set<int>
#define tr(c, it) \
for(decltype(c.begin()) it = c.begin(); it!= c.end(); it++)
#define pis pair<int,string>
#define present(c, x) (c.find(x) != c.end())
#define cpresent(c, x) (find(all(c),x) != c.end())
#define  ones(x)  __builtin_popcount(x)
using namespace std;
vector<int> adj[100010];

void dfs(int i, vector<int> & vis){
	vis[i] = true;
	for(int ch: adj[i]){
		if(!vis[ch]){
			dfs(ch, vis);
		}
	}
}
int main(){
//freopen("input.txt", "r", stdin);
	int n;
	cin >> n;
	int m;
	cin >> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	int ans = 0;
	vector<int> vis(n+1,0);
	for(int i = 1; i <= n; i++)
	{
		if(!vis[i])
		{
			dfs(i, vis);
			ans++;
		}
	}
	cout << ans-1 << endl;
}


Measured memory_bytes: 9568
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef vector<lld> vll;
#define pb push_back
#define rep(i,a,b) for(i=a;i<b;i++)
#define srt(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define mod 1000000007
#define pi 3.1415926535
lld a,b,c,d,e,f,g,h,i,j,k=0,l=0,m=1,n=1,o,q=0,r=0,u,v,w,x,y,z,s,t,p=0;
lld temp=0,ans=0;
double f1,f2,f3,f4,f5,f6;
char c2,c3,c4,c5,c6;
vll v11;
pair<lld,lld>p1,p2,p3;
map<lld,lld>mv;bool a12[200005],a13[200005];
bool b11[500006],c11[500006];lld a11[500006];
lld gcd(lld a, lld b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
}
void dfs(lld i,vector<lld>vg[])
{
    if(b11[i]==true)    return;
    v11.pb(i);
    p++;
    b11[i]=true;
    for(auto x11:vg[i])
    {
        if(b11[x11]==false)
        {
            dfs(x11,vg);
        }
    }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  t=1;
  //cin>>t;
  while(t--)
  {
    string s3,s1,s2;
    cin>>s1>>s2;
    //lld p1,q1,a1,b1,c1,d1;
    //lld a1[n+1]={0},b1[n],c1[n+1];vector<lld>vg[n+1];
    map<lld,lld>m1,m2;queue<lld>q2;vll v1,v2;
    //rep(i,0,n)  cin>>a1[i];
    n=s1.size();m=s2.size();q=0;
    for(i=0;i<n-m+1;i++)
    {
        p=0;k=i;
        rep(j,0,m)
        {
            if(s1[i+j]==s2[j])
            {
                p++;
            }
        }
        q=max(q,p);
        //cout<<i<<" ";
    }
    cout<<(m-q);
    cout<<endl;
  }
  return 0;
}

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

int main(void) {
  int n;
  cin >> n;
  set<string> S;
  vector<bool> ans(n); int k = 0;

  
  for (int i = 0; i < n; i++) {
    string com, str;
    cin >> com >> str;

    if (com == "insert") {
      S.insert(str);
    } else {
      ans.at(k) = (S.count(str));
      k++;
    }
  }

  for (int i = 0; i < k; i++)
  {
    if (ans.at(i)) {
      cout << "yes" << endl;
    } else {
      cout << "no" << endl;
    }
  }
  
}


Measured memory_bytes: 32252
# Your code here!

input = gets.split
start = input[0].to_i
finish = input[1].to_i

count = 0
for i in start..finish
	tmp = i.to_s
	tmp_r = tmp.reverse
#	puts "#{tmp} #{tmp_r}"
	if tmp == tmp.reverse
      count = count + 1
    end
end

puts count


Measured memory_bytes: 1916
#pragma GCC optimize("Ofast")

// #define _GLIBCXX_DEBUG

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

#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
// #define NP next_permutation;
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
// typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
// using vvvi=vector<vvi>;
/*
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double pi=3.14159265358979323846;
*/
template<class T> bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
// template<class T> void decimal(T a){cout<<fixed<<setprecision(a);}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
/*
void YesNo(bool a){if(a) out("Yes"); else out("No");}
void yesno(bool a){if(a) out("yes"); else out("no");}
void YESNO(bool a){if(a) out("YES"); else out("NO");}
ll GCD(ll a,ll b){ll c; while(b!=0){c=a%b; a=b; b=c;} return a;}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){ll c=1; while(b>0){if(b&1){c=a * c%mod;} a=a * a%mod; b>>=1;} return c;}
vi calc(ll x){vi res; while(x>0){res.pb(x%10); x/=10;} reverse(all(res)); return res;}
*/
void solve() {
  int n,ans=1; cin>>n;
  string slime; cin>>slime;
  rep(i,n-1){
    if(slime[i]!=slime[i+1]){
      ans++;
    }
  }
  out(ans);
}

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


Measured memory_bytes: 512
#include<iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include<map>
#include<cstring>
#include<iomanip>
#include <string>
#include <vector>	
#include<unordered_map>
#include<unordered_set>
using namespace std;


typedef long long unsigned llu;
typedef long double ld;
#define ll long long
#define PI 3.14159265358979323846
#define For(i, a, b) for (int i = a, sz = (int)b; i < sz; i++)
#define rFor(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fill(a, b) memset(a, b, sizeof(a))
#define IO ios_base::sync_with_stdio(false), cin.tie(0),cout.tie(0)
const int mod = 1000000007;
const ll inf = 1000000000009;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);}

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdoutn

int main()
{
	IO;
	int n{};
	cin>>n;
	if(!(n%1000))cout<<"0\n";
	else cout<<(((n/1000)+1)*1000)-n<<'\n';
//	system("pause");
	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<queue<ll>> A(N);
  for (ll i = 0; i < N; ++i) {
    for (ll j = 0; j < N - 1; ++j) {
      ll a;
      cin >> a;
      A.at(i).push(a - 1);
    }
  }
  ll ans = 0;
  bool change = true;
  queue<ll> pos;
  for (ll i = 0; i < N; ++i) {
    pos.push(i);
  }
  while (change) {
    change = false;
    vector<ll> already(N, false);
    queue<ll> next_pos;
    while (!pos.empty()) {
      ll i = pos.front();
      pos.pop();
      if (already.at(i) || A.at(i).empty()) {
        continue;
      }
      ll opp = A.at(i).front();
      if (already.at(opp) || A.at(opp).empty()) {
        continue;
      }
      if (A.at(opp).front() == i) {
        A.at(i).pop();
        A.at(opp).pop();
        change = true;
        already.at(i) = true;
        already.at(opp) = true;
        next_pos.push(i);
        next_pos.push(opp);
      }
    }
    pos = next_pos;
    if (change) {
      ans += 1;
    }
  }
  for (ll i = 0; i < N; ++i) {
    if (!A.at(i).empty()) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 8960
#include <bits/stdc++.h>
using namespace std;
int main() 
{
  string S;
  cin >> S;
  int cont= 0;
    for(int i = 0; i< S.size()/2;i++)
    {
      if(S[i] == S[S.size()-1-i])
      {
        cont = cont;
      }
      else
      {
        cont++;
      }
    }
  cout << cont;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> v[100001];
int n, k;
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        ll t, d;
        cin >> t >> d;
        v[t].push_back(d);
    }
    // 種類数が増えない
    vector<ll> ans0;
    // 種類数が増える
    vector<ll> ans1;
    for (int i = 0; i <= n; i++)
    {
        if (v[i].empty())
        {
            continue;
        }
        sort(v[i].begin(), v[i].end(), greater<ll>());
        ans1.push_back(v[i][0]);
        for (int j = 1; j < v[i].size(); j++)
        {
            ans0.push_back(v[i][j]);
        }
    }
    sort(ans0.begin(), ans0.end(), greater<ll>());
    sort(ans1.begin(), ans1.end(), greater<ll>());
    ll ans = 0LL;
    for (ll i = 1; i <= k; i++)
    {
        if (ans0.size() < k - i)
        {
            continue;
        }
        if (ans1.size() < i)
        {
            continue;
        }
        ll t = accumulate(ans1.begin(), ans1.begin() + i, 0LL) + accumulate(ans0.begin(), ans0.begin() + k - i, 0LL) + i * i;
        ans = max(ans, t);
    }
    cout << ans << endl;
}


Measured memory_bytes: 6904
N = int(input())
arr = sorted(list(map(int, input().split())),reverse=True)
arr2 = [arr[0]]

for i in range(1,N,1):
    arr2.append(arr[i])
    arr2.append(arr[i])


ans = 0
for i in range(N-1):
    ans += arr2[i]

print(ans)



Measured memory_bytes: 125528
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		while(true){
			String str = br.readLine();
			String[] s = str.split(" ");

			int shiken1 = Integer.parseInt(s[0]);
			int shiken2 = Integer.parseInt(s[1]);
			int saishiken = Integer.parseInt(s[2]);

			int sum = shiken1 + shiken2;

			if((shiken1 == -1)&&(shiken2 == -1)&&(saishiken == -1)){
				break;
			}
			if((shiken1 == -1)||(shiken2 == -1)){
				System.out.println("F");
				continue;
			}else if(80 <= sum){
				System.out.println("A");
				continue;
			}else if((65 <= sum)&&(sum <= 79)){
				System.out.println("B");
				continue;
			}else if((50 <= sum)&&(sum <= 64)||(50 <= saishiken)){
				System.out.println("C");
				continue;
			}else if((30 <= sum)&&(sum <= 49)){
				System.out.println("D");
				continue;
			}else if(sum <= 29){
				System.out.println("F");
				continue;
			}
		}
	}
}

Measured memory_bytes: 24504
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define x             first
#define y             second
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define PI            3.14159265358979
#define N             200005

bool v2[N];
vector<int> v[N];
int dp[N];

void dfs(int x){
    v2[x]=1;
    for(int i:v[x]){
        if(!v2[i]){
            dfs(i);
        }
        dp[x]=max(dp[x],dp[i]+1);
    }
}

int solve(){
    int n,m; cin>>n>>m;
    for (int i = 0; i < m; ++i)
    {
        int x,y; cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1; i<=n; i++){
        if(!v2[i])
            dfs(i);
    }
    int ans=0;
    for(int i=1; i<=n; i++)
        ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 14892
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<int, int>;
using P = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
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; }
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
int fact(int x) {
	int res = x;
	for (int i = x - 1; i > 0; i--) res *= i;
	return res;
}
int main() {
	int n;
	cin >> n;
	int i;
	vector<double> x(n + 1);
	vector<double> y(n + 1);
	for (i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
	}
	V per(n);
	for (i = 0; i < n; i++) per[i] = i + 1;
	double ans = 0;
	do {
		for (i = 0; i < n - 1; i++) {
			ans += sqrt(pow(x[per[i]] - x[per[i + 1]], 2) + pow(y[per[i]] - y[per[i + 1]], 2));
		}
	} while (next_permutation(per.begin(), per.end()));
	cout << fixed << setprecision(8) << ans / (double)fact(n) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define whole(x) (x).begin(), (x).end()
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
 
const int N = int(2e5) + 2;
const int LG = 20;
const ll mod = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const ll linf = 1e18; 
const ld pi = acos(-1);
const int base = 10;
const ld EPS = 1e-9;

int n;
int main (){
    scanf ("%d", &n);
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        int cnt = 0, x = i;
        while (x){
            cnt++;
            x /= 10;
        }
        ans += (cnt & 1);
    }
    return !printf ("%d\n", ans);
}

Measured memory_bytes: 256
#include <stdio.h>

int sum[222222];

int main(void)
{
	int n, k, i, a, max = 0;

	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		sum[i] = sum[i - 1] + (a + 1);
	}

	for (i = k; i <= n; i++)
		if (max < sum[i] - sum[i - k])
			max = sum[i] - sum[i - k];

	printf("%.8lf", max / 2.0);
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
char a[maxn][maxn];
int v[maxn][maxn];
int n,m;
int ans;
struct Node{
	int x;
	int y;
	int d;
};
queue<Node>q;
int main(){	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]=='#'){
				v[i][j]=1;
				q.push((Node){i,j,0});
			}
	while(!q.empty()){
		int x=q.front().x;
		int y=q.front().y;
		int d=q.front().d;
		ans=d;
		q.pop();
		for(int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m) continue;
			if(v[xx][yy]) continue;
			if(a[xx][yy]=='#') continue;
			v[xx][yy]=1;
			q.push((Node){xx,yy,d+1});
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 17296
#include <cstdio>
#include <cstring>
using namespace std;

int N;
int adj[100005], gto[200005], gnxt[200005], e;
int pre[100005], size[100005];
int nim[100005];

void add_edge(int u, int v) {
    gto[e] = v; gnxt[e] = adj[u]; adj[u] = e++;
}

void dfs(int s) {
    size[s] = 1;
    if (!~adj[s]) {
        return;
    }
    for (int e = adj[s]; ~e; e = gnxt[e]) {
        if (gto[e] != pre[s]) {
            pre[gto[e]] = s;
            dfs(gto[e]);
            size[s] += size[gto[e]];
        }
    }
}

int dfs2(int s) {
    if (!~adj[s]) {
        return nim[s] = 0;
    }
    for (int e = adj[s]; ~e; e = gnxt[e])
        if (gto[e] != pre[s]) {
            nim[s] ^= dfs2(gto[e]) + 1;
        }
    return nim[s];
}

int main() {
    memset(adj, -1, sizeof adj);
    scanf("%d", &N);
    for (int i = 1; i != N; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        add_edge(x, y); add_edge(y, x);
    }
    dfs(1); dfs2(1);
    puts(nim[1] ? "Alice" : "Bob");
    return 0;
}

Measured memory_bytes: 6400
import sys
input = sys.stdin.readline
inputt = lambda: range(int(input()))
inputn = lambda n = 1: range(n)
inputi = lambda: map(int, input().split())
inputl = lambda: list(inputi())
from math import *
from heapq import *
from bisect import *
from operator import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
from builtins import *

def factor(n):
    i, l = 2, []
    while i * i <= n:
        if not n % i:
            l.append(i)
            n //= i
        else:
            i += 1
    l.append(n)
    return l

def T(n, k):
    while not n % k:
        n //= k
    return n % k == 1

N, = inputi()
R = reduce(mul, [v + 1 for v in Counter(factor(N - 1)).values()], 1) - 1
D = {1}
for n in factor(N):
    D |= {d * n for d in D}
for d in D:
    if d != 1 and T(N // d, d):
        R += 1
if N == 2:
    print(1)
else:
    print(R)


Measured memory_bytes: 4408
n, m = map(int, input().split())
cnt = [0 for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    cnt[a] = (cnt[a] + 1) % 2
    cnt[b] = (cnt[b] + 1) % 2
if 1 in cnt:
    print("NO")
else:
    print("YES")


Measured memory_bytes: 9820
using System;

namespace atcoder
{
    class Atcoder170
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(" ");
            for(int i = 0; i < input.Length; i++) {
                if (input[i] == "0")
                {
                    Console.WriteLine((i + 1).ToString());
                    break;
                }
            }
        }
    }
}


Measured memory_bytes: 25720
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mem(x, y) memset(x, y, sizeof(x))
#define pii pair<int, int>
#define pli pair<LL, int>
#define mkp make_pair
const int N = 100005;
int n, a[N], A, B;

bool check(int cnt) {
    LL extra = 0;
    for(int i = 0; i < n; i++) {
        if(1LL * cnt * B >= a[i]) continue;
        LL need = a[i] - 1LL * cnt * B;
        extra += (need % (A - B)) ? (need / (A - B) + 1) : (need / (A - B));
    }
    return extra <= cnt;
}

int main()
{
    scanf("%d%d%d", &n, &A, &B);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int l = 1, r = 1e9;
    while(l < r) {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}



Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out)) {

          int n = Integer.parseInt(in.readLine());

          int a[] = new int[n];
          String line = in.readLine();
          char regex = ' ';
          boolean isContinue = true;
          for(int i=0,m=0, offset=0,next=0; isContinue; i++, offset = ++next) {
            if((next = line.indexOf(regex,offset)) == -1) {
              next = line.length();
              isContinue = false;
            }
            a[i] = Integer.parseInt(line.substring(offset,next));
          }

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

          double ave = sum / (double)n;

          int ans=0;
          double d=0.0, min = 100000.0;
          for(int i=0; i<n; i++) {
            d = Math.abs(ave - a[i]);
            if(min > d) {
              min = d;
              ans = i;
            }
          }
          System.out.println(ans);
      }
      catch(IOException e) {
        System.err.println(e);
      }
  }
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

void solve()
{
  ll n;
  cin >> n;
  n++;
  vector<ll> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> a[i];
  }

  vector<ll> b(a);
  reverse(ALL(b));
  for(int i = 1; i < n; ++i)
  {
    b[i] += b[i - 1];
  }
  reverse(ALL(b));

  ll next_branch = 1;  
  ll ans = 0;
  for(int i = 0; i < n; ++i)
  {
    b[i] = min(b[i], next_branch);
    next_branch = min((next_branch - a[i]) * 2, (1LL << 62));
    if (next_branch < 0){
      cout << -1;
      return;
    }
    ans += b[i];
  }

  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 4728
N, Y = map(int, input().split())


def greedy(Y):
    res = Y
    yukichi = 0
    ichiyo = 0
    hideyo = 0
    while res >= 10000:
        res -= 10000
        yukichi += 1
        
    while res >= 5000:
        res -= 5000
        ichiyo += 1
        
    while res > 0:
        res -= 1000
        hideyo += 1
        
    return yukichi, ichiyo, hideyo
    

def confirm_N(N,Y,yukichi,ichiyo,hideyo):
    bill = yukichi+ichiyo+hideyo
    if N<bill:
        return [-1,-1,-1]
    elif N == bill:
        return [yukichi, ichiyo, hideyo]
    
    while yukichi >= 0:
        if bill == N:
            return [yukichi, ichiyo, hideyo]
        
        while ichiyo > 0:
            bill += 4
            hideyo += 5
            ichiyo -= 1
            if bill == N:
                return [yukichi, ichiyo, hideyo]
        
        yukichi -= 1
        ichiyo = (Y-yukichi*10000) // 5000
        hideyo = (Y-yukichi*10000-ichiyo*5000) // 1000
        
        bill = yukichi+ichiyo+hideyo
    
    return [-1,-1,-1]

#1.まず貪欲

yukichi, ichiyo, hideyo = greedy(Y)

bill = yukichi+ichiyo+hideyo

ans_lst = confirm_N(N, Y, yukichi, ichiyo, hideyo)

print(*ans_lst)




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

int main(){
  int N;cin>>N;
  vector<int> S(N);
  for(int i=0;i<N;i++) cin>>S.at(i);
  sort(S.begin(),S.end());
  int sum=0;
  for(int i=0;i<N;i++) sum+=S.at(i);
  int ans;
  if(sum%10==0){
    ans=0;
    for(int j=0;j<N;j++){
      int X=sum-S.at(j);
      if(X%10!=0){
        ans=X;
        break;
      }
    }
  }
  else ans=sum;
  cout<<ans<<endl;
}
  

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

int main()
{
    string n;
    cin >> n;
    
    long long maxc=0;
    

    for(int cc = 0;cc<n.size();++cc)
    {
        long long c=0;
        
        for(int i = cc;i<n.size();++i)
        {
            if((n[i] == 'A') || (n[i] == 'C') || (n[i] == 'G') || (n[i] == 'T'))
            {
                c++;
            }
            else
            {
                break;    
            }
        }
        
        if(c > maxc)
        {
            maxc = c;
        }
    }
    
    
    cout << maxc<< endl;

    return 0;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mod= 1e9+7;
typedef long long ll;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define what_is(x) cerr << #x << " is " << x << endl;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;

    if (a==b && a==c)
        cout<<"No\n";
    else
    {
        if (a==b || a==c || b==c)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }

}


Measured memory_bytes: 256
from itertools import product

H, W = map(int, input().split())
S = [[x for x in input()] for _ in range(H)]

T = [[0 for _ in range(W)] for _ in range(H)]
for i, j in product(range(H), range(W)):
    if S[i][j] == '.':
        continue
    for di, dj in product([-1, 0, 1], [-1, 0, 1]):
        if di == 0 and dj == 0:
            T[i][j] = '#'
        else:
            if 0 <= i + di < H and 0 <= j + dj < W:
                if T[i + di][j + dj] != '#':
                    T[i + di][j + dj] += 1
for i in range(H):
    print(''.join([str(x) for x in T[i]]))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    int N, ans=0;
    cin >> N;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    while(true){
        bool flag = false;
        rep(i, N){
            if(a[i]%2==0){
                a[i]/=2;
                flag = true;
            }
            if(flag) break;
        }
        if(!flag){
            cout << ans << endl;
            return 0;
        }
        ans++;
    }
    return 0;
}


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

// 23:25-23:43
int main(void){
    int n = 0; 
    int tmp = 0;
    int min = 1000000001;
    int max = 0;

    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &tmp);
        if(min >= tmp){
            min = tmp;
        }
       // else をつけてたからWAだった
        if(max <= tmp){
            max = tmp;
        }
    }

    printf("%d\n", max - min);

    return 0;

} 


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

int		main(void)
{
	int		N, K, X, Y;

	cin >> N >> K >> X >> Y;
	if (N < K)
	{
		cout << N * X << endl;
	}
	else
	{
		cout << (K * X) + ((N - K) * Y) << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define x real()
#define y imag()
using namespace std;
typedef complex<double> P;
typedef pair<P,P> L;
const double EPS = 1e-8;

double dot(P a, P b){ return real(conj(a)*b); }

double cross(P a, P b){ return imag(conj(a)*b); }

int ccw(P a, P b, P c){
  b -= a;
  c -= a;
  if(cross(b,c) > 0) return 1;
  if(cross(b,c) < 0) return -1;
  if(dot(b,c) < 0) return 2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

bool isIntersect(L s1, L s2){
  return ( ccw(s1.first,s1.second,s2.first) * ccw(s1.first,s1.second,s2.second) <= 0 &&
  ccw(s2.first,s2.second,s1.first) * ccw(s2.first,s2.second,s1.second) <= 0 );
}

double getDistanceSP(L s, P p){
  if(dot(s.second - s.first, p - s.first) < 0) return abs(p - s.first);
  if(dot(s.first - s.second, p - s.second) < 0) return abs(p - s.second);
  return abs(cross(s.second - s.first, p - s.first) / abs(s.second - s.first));  }

double getDistanceSS(L s1, L s2){
  if(isIntersect(s1,s2)) return 0.0;
  return min( min(getDistanceSP(s1, s2.first), getDistanceSP(s1, s2.second)),
              min(getDistanceSP(s2, s1.first), getDistanceSP(s2, s1.second)));
}


double cal(L a,L b,double h){
  double d=getDistanceSS(a,b);
  if(h>d)return d;
  return (h*h+d*d)/2/h;
}

int main(){
  int n;

  while(cin>>n,n){
    double ans=1e9;
    P s,e;
    double minx,maxx,miny,maxy,h;
    cin>>s.x>>s.y>>e.x>>e.y;
    for(int i=0;i<n;i++){
      cin>>minx>>miny>>maxx>>maxy>>h;
      if(minx<=s.x&&s.x<=maxx&&miny<=s.y&&s.y<=maxy)ans=0;
      if(minx<=e.x&&e.x<=maxx&&miny<=e.y&&e.y<=maxy)ans=0;
      ans=min(ans,cal(L(s,e),L(P(minx,miny),P(minx,maxy)),h));
      ans=min(ans,cal(L(s,e),L(P(minx,maxy),P(maxx,maxy)),h));
      ans=min(ans,cal(L(s,e),L(P(maxx,maxy),P(maxx,miny)),h));
      ans=min(ans,cal(L(s,e),L(P(maxx,miny),P(minx,miny)),h));
    }
    printf("%.8lf\n",ans);
  }
  return 0;
}

Measured memory_bytes: 3160
/*{{{*/
#include<bits/stdc++.h>

typedef long long ll;

#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define FORR(i,a,b) for(ll i=b-1;i>=a;i--)

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

int main() {
  REP(i,5){
    ll n;
    cin >> n;
    if(n==0) cout << i+1 << endl;
  }
  return 0;
}


Measured memory_bytes: 3656
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cstdio>
using namespace std;

static const int INF=100000;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    double w,h,x,y;
    cin >> w >> h >> x >> y;
    printf("%.10f ",w*h*1.0/2);
    if(x+x!=w||y+y!=h){
        cout << 0 << endl;
    }else{
        cout << 1 << endl;
    }
}


Measured memory_bytes: 256
while True:
    try:
        N = int(input())
        H = list(map(int, input().split()))
        H.reverse()
        dp = [0] * N
        for i in range(1, N):
            if H[i] >= H[i-1]:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = 0
        print(max(dp))
    except:
        break

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

void solve()
{
	ll n;
	cin>>n;
	ll a[n] = {};
	for (int i = 0; i < n-1; ++i)
	{
		ll k;
		cin>>k;
		a[k-1]++;
	}
	for (int i = 0; i < n; ++i)
	{
		cout<<a[i]<<endl;
	}
}

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 5144
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[200000],b[200000],x,y;
int main(void){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b,b+n);
	if(b[n/2]==b[n/2-1])for(int i=0;i<n;i++)cout<<b[n/2]<<endl;
	else {
		x=b[n/2-1];
		y=b[n/2];
		for(int i=0;i<n;i++)cout<<(a[i]<=x?y:x)<<endl;
	}
	return 0;
}

Measured memory_bytes: 3712
#include<cstdio>
#include<cstring>
int len,ans;
char S[200100];
int main(){
	scanf("%s",S+1);len=strlen(S+1);
	int now=1;
	while(now<=len){
		ans++,now++;
		while(S[now]!=S[now-1]&&now<=len)ans++,now++;
		if(now>=len)break;
		ans++,now+=2;
	}
	printf("%d\n",ans);
}

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

int main() {
    int k,l;
    cin>>k>>l;
    char a[51][51];
    for(int i=0;i<k;i++){
        for(int j=0;j<l;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<k;i++){
        for(int j=0;j<l;j++){
            if(a[i][j]=='#'){
                a[i][j]='#';
            }
            else{
                int count=0;
                if(a[i][j-1]=='#'){
                   count++; 
                }
                if(a[i][j+1]=='#'){
                   count++; 
                }
                if(a[i-1][j]=='#'){
                   count++; 
                }
                if(a[i+1][j]=='#'){
                   count++; 
                }
                if(a[i+1][j+1]=='#'){
                   count++; 
                }
                if(a[i-1][j-1]=='#'){
                   count++; 
                }
                if(a[i-1][j+1]=='#'){
                   count++; 
                }
                if(a[i+1][j-1]=='#'){
                   count++; 
                }
                a[i][j]=char(count+'0');
            }
        }
        
    }
    
      for(int i=0;i<k;i++){
        for(int j=0;j<l;j++){
            cout<<a[i][j];
        }
        cout<<endl;
      }
      
}



Measured memory_bytes: 256
def main():
    N = int(input())
    S = input()
    x = 0
    max_x = 0
    for i in range(N):
        if S[i] == "I": x += 1
        else: x -= 1
        max_x = max(max_x, x)
    return max_x
if __name__ == '__main__':
    print(main())

Measured memory_bytes: 3060
#!/usr/bin/env python3

def main():
    N = input()
    cnt = 0
    for n in N:
        cnt += int(n)
    if cnt % 9 == 0:
        ans = 'Yes'
    else:
        ans = 'No'
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9324
import math
n = int(input())

def div(m):
  d = {}
  temp = int(math.sqrt(m))+1
  for i in range(2, temp):
    while m%i== 0:
      m //= i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
  if d == {}:
    d[m] = 1
  else:
    if m in d:
      d[m] += 1
    elif m != 1:
      d[m] =1
  return d

from collections import Counter

d = {}
for i in range(2, n+1):
  d = dict(Counter(d)+Counter(div(i)))
#print(d)
ans = 1
for i in d.values():
  ans *= (i+1)
  ans %= 10**9+7
print(ans)



Measured memory_bytes: 41584
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int N;
  cin >> N;
  vec v;
  for (int i = 0; i < 3 * N; i++) {
    int tmp;
    cin >> tmp;
    v.pb(tmp);
  }

  sort(ALL(v), greater<int>());

  int ans = 0;
  for (int i = 0; i < 2 * N; i++) {
    if (i % 2) ans += v[i];
  }

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


Measured memory_bytes: 6384
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    AS = list(map(lambda x: -int(x), input().split()))
    heapify(AS)
    for _ in range(M):
        a = heappop(AS)
        a = -(-a//2)
        heappush(AS,a)
    print(-sum(AS))

if __name__ == '__main__':
    main()

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

print(N * (N-1) // 2 - N // 2)
M = 1 if N % 2 == 0 else 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if j == N + M - i:
            continue
        print(i,j)


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

int main() {
  for(int N; cin >> N; ) {
    int ans = 0;
    for(int a = 0; a <= 9; a++) 
      for(int b = 0; b <= 9; b++)
        for(int c = 0; c <= 9; c++)
          for(int d = 0; d <= 9; d++)
            if( N == a + b + c + d )
              ans++;
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 0