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

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

const int INF = 1e9 + 7;

using namespace std;

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

	int n, k;
	cin >> n >> k;

	ll res = 0;
	if (k == 0) {
		res = (ll)n * (ll)n;
	} else {
		rep (i, k + 1, n + 1) { // b
			res += (i - k);
			ll tmp = min(2 * i, n) - min((i + k), n);
			ll x = n / i;
			res += tmp * (x - 1);
			res += max<ll>(0, n - (x * i + k - 1));
		}
	}

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


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


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

    priority_queue<int> ds;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        ds.push(tmp);
    }

    int arc, abc;
    for(int i = 0; i < n/2 + 1; i++){
        if(i == n/2 -1){
            arc = ds.top();
            ds.pop();
        }else if(i == n/2){
            abc = ds.top();
        }else{
            ds.pop();
        }
    }
    cout << arc - abc << "\n";
}


Measured memory_bytes: 892
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<queue>
#include<ctime>
#include<vector>
using namespace std;
inline int rd(){
  register char ch=getchar();
  register bool flag=false;
  register int res=0;
  while(ch<'0'||ch>'9'){flag=(ch=='-');ch=getchar();}
  while(ch>='0'&&ch<='9'){
    res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
  if(flag)res=-res;
  return res;
}
#define int long long
#define N 200010
#define INF 1000000000000000000LL
int n;
struct data{
  int a,b;
  inline void read(){
    a=rd();b=rd();
    if(a>b)swap(a,b);
  }
}dat[N];
inline int solve1(){
  int i,j,ma=dat[1].a,na=dat[1].a,mb=dat[1].b,nb=dat[1].b;
  for(i=1;i<=n;i++)
    ma=max(ma,dat[i].a),na=min(na,dat[i].a),
      mb=max(mb,dat[i].b),nb=min(nb,dat[i].b);
  // printf("solve1 %lld\n",(ma-na)*(mb-nb));
  return (ma-na)*(mb-nb);
}
bool cmp(const data &x,const data &y){
  return x.a<y.a;
}
int mb[N],na[N];
inline int solve2(){
  sort(dat+1,dat+n+1,cmp);
  /*int i,j,ha=dat[1].b,hb=dat[1].b;
  for(i=1;i<=n;i++)mb[i]=max(mb[i-1],dat[i].b);
  for(na[n+1]=na[n]=dat[n].a,i=n-1;i>=1;i--)na[i]=max(na[i+1],dat[i].a);
  for(i=1;i<=n;i++)
    ha=max(ha,dat[i].b),hb=min(hb,dat[i].b);

  int mn=INF,res=INF,sum=ha-hb;
  for(i=2;i<=n;i++){
    mn=min(mn,dat[i-1].b);//if(mn<=dat[i].a)break;//not allow
    if((max(mb[i-1],dat[n].a)-min(mn,dat[i].a))*(ha-dat[1].a)==0)continue;
    else
      res=min(res,(max(mb[i-1],dat[n].a)-min(mn,dat[i].a))*(ha-dat[1].a));}
  *///for(i=1;i<=n;i++)printf("[%lld %lld %lld]\n",dat[i].a,dat[i].b,mb[i]);
  //printf("solve2 %lld %lld[%lld %lld]\n",res,sum,ha,dat[1].a);
  int res=INF,i,j,pre,x1,x2,y1=0,y2=1e9;
  for(i=1;i<=n;i++)y1=max(y1,dat[i].b),y2=min(y2,dat[i].b);y2=dat[1].a;
  x1=max(dat[n].a,pre=dat[1].b);x2=dat[1].a;res=min(res,(y1-y2)*(x1-x2));
  // printf("ans=%lld %lld %lld %lld %lld %lld\n",res,x1,x2,y1,y2,pre);
  //printf("[%lld %lld %lld %lld]\n",x1,x2,y1,y2);
  for(i=2;i<n;i++){
    if((x2=dat[i].a)>pre)break;
    //printf("upd %lld\n",(y1-y2)*(x1-x2));  
  res=min(res,(y1-y2)*(x1-x2));
    x1=max(x1,dat[i].b);pre=min(pre,dat[i].b);
  }x2=pre;
  res=min(res,(y1-y2)*(x1-x2));
  //printf("%lld %lld %lld %lld\n",y1,y2,x1,x2);
  return res;
}
void work(){
  n=rd();
  int i,j;
  for(i=1;i<=n;i++)
    dat[i].read();
  printf("%lld\n",min(solve1(),solve2()));
}
#undef int 
int main(){
  work();
  return 0;
}


Measured memory_bytes: 4480
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int n; cin >> n&&n;) {
		vector<int> v(n);
		rep(i, 0, n) { cin >> v[i]; }
		sort(all(v), greater<int>());
		int ans = 0;
		rep(i, 0, n) { ans += v[i] * i; }
		cout << ans << endl;
	}
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  bool yes=false;
  for (int i=0; i<50; i++){
    for (int j=0; j<50; j++){
      if (i*4+j*7==N){
        yes=true;
        break;
      }
    }
  }
  if (yes){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}



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

struct Card { char suit, value; };

void bubbleSort(Card a[], int n) {
	for(int i=0; i<n; i++) {
		for(int j=n-1; j>= i+1; j--) {
			if(a[j-1].value > a[j].value) {
				Card t = a[j]; a[j] = a[j-1]; a[j-1] = t;
			}
		}
	}
}

void selectionSort(Card a[], int n) {
	for(int i=0; i<n-1; i++) {
		int minj = i;
		for(int j= i+1; j<n; j++) {
			if(a[j].value < a[minj].value)
				minj = j;
		}
		Card t = a[i]; a[i] = a[minj]; a[minj] = t;
	}
}

void print(Card a[], int n) {
	for(int i=0; i<n; i++) {
		if(i>0) cout << " ";
		cout << a[i].suit << a[i].value;
	}
	cout << endl;
}

bool isStable(Card c1[], Card c2[], int n) {
	for (int i=0; i<n; i++) {
		if(c1[i].suit != c2[i].suit) return false;
	}
	return true;
}

int main() {
	Card c1[100], c2[100];
	int n;

	cin >> n;
	for(int i=0; i<n; i++) {
		cin >> c1[i].suit >> c1[i].value;
	}

	for(int i=0; i<n; i++) c2[i] = c1[i];

	bubbleSort(c1,n);
	selectionSort(c2,n);

	print(c1,n);
	cout << "Stable" << endl;
	print(c2,n);
	if(isStable(c1,c2,n) ) {
		cout << "Stable" << endl;
	} else {
		cout << "Not stable" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3044
import math
import queue
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=qb
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
def dq():
	return queue.deque()
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1

arr = readInts()
gu_num = arr[0]%2+arr[1]%2+arr[2]%2

ans = 0

if gu_num not in [0,3]:
	ans+=1
	if gu_num==1:
		if arr[0]%2==1:
			arr[1]+=1
			arr[2]+=1
		elif arr[1]%2==1:
			arr[0]+=1
			arr[2]+=1
		else:
			arr[0]+=1
			arr[1]+=1
	else:
		if arr[0]%2==0:
			arr[1]+=1
			arr[2]+=1
		elif arr[1]%2==0:
			arr[0]+=1
			arr[2]+=1
		else:
			arr[0]+=1
			arr[1]+=1


while not(arr[0]==arr[1] and arr[1]==arr[2]):
	arr[arr.index(min(arr))]+=2
	ans+=1
print(ans)

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

int main()
{  int al[26]={0};
    while(true){


        string s;
        getline(cin,s);
        if((int)s.size()==0) break;

        for(int i=0;i<(int)s.size();i++){
           for(int j=0;j<26;++j) {if(s[i]=='a'+j||s[i]=='A'+j){
               al[j]++;
            }
           }
        }
}
    for(int i=0;i<26;++i){
        cout << char (i+'a')<<" : "<< al[i]<< endl;
    }
    return 0;
}



Measured memory_bytes: 3144
import java.util.Scanner;


	public class Main {
		
		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int n = sc.nextInt();
			long[] d = new long[100001];
			
			
			for(int i=0;i<n;i++) {
				int val = sc.nextInt();
				d[val]++;
			}
			
			int ret = 0;
			long sum = 0;
			
			for(int i=0;sum<=n/2;i++) {
				sum += d[i];
				if(sum==n/2) {
					ret++;
				}
			}
			
			System.out.println(ret);
			
			
	    }
		
	}
	


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

int N;
int a[100];
int c[100];

bool f() {
  int s = a[0], g = a[N-1];
  for (int i=s; i<=g; i++) {
    if (c[i] == 0) return false;
  }
  if (g % 2 == 0) {
    if (c[s] != 1) return false;
  }
  else {
    if (c[s] != 2) return false;
  }
  return true;
}

int main() {
  cin >> N;
  for (int i=0; i<N; i++) {
    cin >> a[i];
    c[a[i]]++;
  }
  sort(a, a+N);
  cout << (f() ? "Possible\n" : "Impossible\n");
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

string smax(string s, string t) {
  if(s.size() > t.size())
    return s;
  else if(s.size() < t.size())
    return t;
  else if(s > t)
    return s;
  else
    return t;
}

int main() {
  int n, m;
  cin >> n >> m;
  vi a(m);
  rep(i, m) cin >> a[i];
  vi v = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  vs dp(n + 10, "");
  rep(i, n) rep(j, m) {
    if(i > 0 && dp[i] == "") continue;
    dp[i + v[a[j]]] = smax(dp[i + v[a[j]]], dp[i] + char('0' + a[j]));
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 43648
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
typedef long long int lint;
using namespace std;

//ただの辺
struct edge {
    using lint = long long int;
    int to;
    lint cost;
    //引数一つの時は距離1
    edge(int t, lint c = 1) : to(t), cost(c) {
    }
};

// dijkstra
// depend:edge
vector<long long int> dijkstra(vector<vector<edge>>& g, int start) {
    using lint = long long int;
    vector<lint> res(g.size(), LLONG_MAX);
    res[start] = 0;
    // first:距離、second:行き先
    priority_queue<pair<lint, lint>, vector<pair<lint, lint>>,
                   greater<pair<lint, lint>>>
        pq;
    pq.push({0, start});
    while (!pq.empty()) {
        lint dist = pq.top().first, now = pq.top().second;
        pq.pop();
        if (res[now] < dist) continue;
        for (int i = 0; i < (int)g[now].size(); i++) {
            edge e = g[now][i];
            if (res[e.to] > res[now] + e.cost) {
                res[e.to] = res[now] + e.cost;
                pq.push(make_pair(res[e.to], e.to));
            }
        }
    }
    return res;
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--, t--;
    vector<vector<edge>> g_yen(n), g_snuuk(n);
    for (int i = 0; i < m; i++) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        g_yen[u].push_back(edge(v, a));
        g_yen[v].push_back(edge(u, a));
        g_snuuk[u].push_back(edge(v, b));
        g_snuuk[v].push_back(edge(u, b));
    }
    vector<lint> d_s = dijkstra(g_yen, s), d_t = dijkstra(g_snuuk, t);
    // loss[i]:[i,n)の街で両替する時の使用金額の最小値
    vector<lint> loss(n + 1);
    loss[n] = LLONG_MAX;
    for (int i = n - 1; i >= 0; i--) {
        loss[i] = min(loss[i + 1], d_s[i] + d_t[i]);
    }
    for (int i = 0; i < n; i++) {
        cout << 1000000000000000 - loss[i] << endl;
    }
}

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

#define M_PI 3.14159265358979323846

using namespace std;

//typedef
//-------------------------#include <bits/stdc++.h>

#define M_PI 3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
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();
}
inline int readInt()
{
    int x;
    scanf("%d", &x);
    return x;
}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a) * (a))
#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 SORT(c) sort((c).begin(), (c).end())

//repetition
//------------------------------------------
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define MOD 1000000007

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-8;

#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const int INF = 2147483647;

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

    ll N, K;
    cin >> N >> K;

    vector<ll> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    ll ans = 0;
    for (int i = 0; i < N; i++)
    {
        ll cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < i; j++)
        {
            if (A[i] > A[j])
            {
                cnt1++;
            }
        }
        for (int j = i; j < N; j++)
        {
            if (A[i] > A[j])
            {
                cnt2++;
            }
        }

        ll t1 = (K * (K + 1) / 2) % MOD * cnt2;
        t1 %= MOD;
        ll t2 = (K * (K - 1) / 2) % MOD * cnt1;
        t2 %= MOD;

        ans += (t1 + t2) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# include <iostream>
# include <sstream>
# include <cstdio>
# include <cstdlib>
# include <algorithm>
# include <string>
# include <cstring>
# include <cmath>
# include <stack>
# include <queue>
# include <vector>
# include <list>
# include <map>
# include <set>
# include <deque>
# include <iterator>
# include <functional>
# include <bitset>
# include <climits>
# include <ctime>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define odd(x) (x&1)
typedef long long ll;
typedef long double ld;
const ll oo = 2 * 1000 * 1000 * 1000;
const int _cnt = 1000 * 1000;
const int _p = 1000 * 1000 * 1000 + 7;
ll o(ll x) { return x%_p; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a, b)*b; }
using namespace std;

void file_put() {
	freopen("filename.in", "r", stdin);
	freopen("filename.out", "w", stdout);
}

char a, b;

int main() {
	//file_put();

	scanf("%c%*c%c", &a, &b);
	if (a == b) printf("H\n"); else printf("D\n");

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <stack>
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
string S;
ll N,K,A,B;
ll J[200005];
ll I[200005];
ll ans;
 
 
 
int main(){
    cin >> N;
    for(int i = 0;i<N;i++){
        ll a;
        cin >> a;
        I[i]=a+i+1;
        J[i] = i + 1 - a;
    }
    sort(I,I+N);
    sort(J,J+N);
    ll cnti = 0;
    ll cntj = 0;
    ll nowans = 0;
    I[N] = 10000000000002;
    J[N] = 10000000000001;
    while(cnti <= N && cntj <= N){
        if(I[cnti]==J[cntj]){
            nowans++;
            cntj++;
        }else if(I[cnti] < J[cntj]){
            int k = 0;
            if(nowans!=0){
                while(I[cnti]==J[cntj-1]){
                    cnti++;
                    k++;
                }
                ans += k*nowans;
                nowans = 0;
            }else{
                cnti++;
            }
        }else{
            cntj++;
            nowans = 0;
        }
        
    }
    cout << ans << endl;
    
    
}


Measured memory_bytes: 6740
def Qc():
    n = int(input())
    l = list(map(int, input().split()))
    ans = 0
    last = l[0]
    for current in l:
        if last < current:
            last = current
        if current < last:
            stand = last - current
            ans += stand
            last = current + stand
    print(ans)


if __name__ == '__main__':
    Qc()


Measured memory_bytes: 32376
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for (int (i) = 1; (i) <= (n); (i++))
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
#define printd(x) printf("%.12f\n", x);
template<class T> bool chmin(T& a, const T& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T& a, const T& b) {if (a < b) {a = b; return 1;} return 0;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	ll ans = 0;
	ans += 1900 * m + 100 * (n - m);
	ans *= 1<<m;

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

Measured memory_bytes: 256
#include <iostream>
#include <valarray>
//#include "../cxx-prettyprint/prettyprint.hpp"

int main() {
    int N;
    std::cin >> N;

    std::valarray<int> a(N);
    for (int i = 0; i < N; i ++) {
        std::cin >> a[i];
    }

    int count = 0;
    for (int a_elem : a) {
        while (a_elem % 2 == 0) {
            count += 1;
            a_elem /= 2;
        }
    }
    std::cout << count << std::endl;
}


Measured memory_bytes: 256
/*
String[]の初期化、整数の型がlongになっているか
関数（splitとかcontainsとか）内では"+"とかは正規表現となされるので"\\+"とする
配列のコピーはarr1=arr.clone()
HashSet<>[]はおのおの初期化した？？？？？
負の数の割り算は絶対値が小さいほうに切り捨てられるex.-1/2=0ので、ある値>kみたいな式だとバグらせやすいので注意
ある値>=kとして、切り上げた値をとるべき
toLowerCase()はアルファベット以外に対して行ってもエラーにはならない
 */
//入力終了→Ctrl+D
import java.util.*;
import java.awt.*;
import java.awt.Graphics.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            double[] x=new double[n];
            double[] y=new double[n];
            for (int i = 0; i < n; i++) {
                x[i]=sc.nextDouble();
            }
            double l1=0,l2=0,l3=0,l8=0;
            for (int i = 0; i < n; i++) {
                y[i]=abs(sc.nextDouble()-x[i]);
                l1+=y[i];
                l2+=pow(y[i],2);
                l3+=pow(y[i],3);
                l8=max(l8,y[i]);
            }
            out.println(l1);
            out.println(sqrt(l2));
            out.println(pow(l3,(double) 1/3));
            out.println(l8);
        }
    }
}


Measured memory_bytes: 28988
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

template<typename Type> class RangeMin {
private:
	int size_;
	std::vector<Type> dat;
public:
	RangeMin() : size_(0), dat(std::vector<Type>()) {};
	RangeMin(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat.resize(size_ << 1, std::numeric_limits<Type>::max());
	}
	template<class T>
	RangeMin(T begin_, T end_) {
		int n = end_ - begin_;
		for (size_ = 1; size_ < n; size_ <<= 1); dat.resize(size_ << 1, std::numeric_limits<Type>::max());
		for (int i = 0; i < n; i++) dat[i + size_] = *(begin_ + i);
		for (int i = size_ - 1; i > 0; i--) dat[i] = std::min(dat[i << 1], dat[(i << 1) + 1]);
	}
	inline unsigned size() { return size_; }
	inline void update(int i, Type x) {
		i += size_; dat[i] = x;
		while (i > 1) {
			i >>= 1;
			dat[i] = std::min(dat[i << 1], dat[i << 1 | 1]);
		}
	}
	inline Type query(int l, int r) {
		Type ret = std::numeric_limits<Type>::max();
		l += size_; r += size_;
		while (l != r) {
			if (l & 1) ret = std::min(ret, dat[l++]); l >>= 1;
			if (r & 1) ret = std::min(ret, dat[--r]); r >>= 1;
		}
		return ret;
	}
};

int H, W;
int A[1 << 18], B[1 << 18];
set<pair<int, int>> Set;
RangeMin<int> X;

void update(int cl, int cr) {
	if (Set.size() == 0) return;

	auto itr = Set.lower_bound(make_pair(cl, 0));

	vector<pair<int, int>> I; int border = W + 1;
	while (itr != Set.end()) {
		if ((*itr).first > cr) { border = (*itr).first; break; }
		I.push_back(*itr);
		itr++;
	}
	for (int i = 0; i < I.size(); i++) {
		Set.erase(I[i]);
		X.update(I[i].first, (1 << 30));
	}

	if (border != cr + 1 && I.size() >= 1) {
		Set.insert(make_pair(cr + 1, I[I.size() - 1].second));
		X.update(cr + 1, (cr + 1) - I[I.size() - 1].second);
	}
}

int main() {
	// 入力
	cin >> H >> W;
	for (int i = 1; i <= H; i++) {
		cin >> A[i] >> B[i];
	}

	// 前準備
	X = RangeMin<int>(W + 2);
	for (int i = 1; i <= W; i++) X.update(i, 0);
	for (int i = 1; i <= W; i++) Set.insert(make_pair(i, i));

	// クエリ
	for (int i = 1; i <= H; i++) {
		update(A[i], B[i]);
		int ret = X.query(1, W + 1);
		if (ret == (1 << 30)) cout << "-1" << endl;
		else cout << i + ret << endl;
	}
	return 0;
}

Measured memory_bytes: 16264
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
struct Edge {
    int from, to; string spell;
    Edge(int f, int t, string s)
         :from(f), to(t), spell(s){}
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, A, S, G;
    while(cin >> N >> A >> S >> G && N){
        vector<Edge> es;
        int x_, y_; string s;
        rep(i, A){
            cin >> x_ >> y_ >> s;
            es.push_back(Edge(y_, x_, s));
        }
        vector<string> dist(N, "~"); dist[G] = "";
        bool fail = false;
        rep(repnum, N * 6){
            bool update = false, update_s = false;
            for(const Edge& e : es)
              if(dist[e.from] != "~" && dist[e.to] > e.spell + dist[e.from]){
                  dist[e.to] = e.spell + dist[e.from];
                  update = true;
                  if(e.to == S) update_s = true;
              }
            if(!update) break;
            if(repnum == N && dist[S] == "~") break;
            if(repnum > N && update_s){
                fail = true;
                break;
            }
        }
        if(dist[S] == "~" || fail) cout << "NO" << endl;
        else cout << dist[S] << endl;
    }
    return 0;
}

Measured memory_bytes: 3344
import math
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
score = A[0]
for i in range(1, math.ceil(N*0.5)):
    if N - i * 2 != 1:
        score += 2 * A[i]
    else:
        score += A[i]
print(score)

Measured memory_bytes: 94172
import sys
import numpy as np

# N K モンスターの数と必殺技の回数
n, k = map(int, input().split())

# H1 ... モンスターの体力
h = list(map(int, input().split()))

h.sort(reverse=True)
h_ar = np.array(h)

if k > 0:
    h_ar[:k] = 0

print(h_ar.sum())

Measured memory_bytes: 43336
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=1; i <= n; i++)
#define ALL(n) begin(n), end(n)

int k, sum;

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

int gcd(int a, int b, int c){
  return gcd(gcd(a, b), c);
}

int main()
{
  cin >> k;

  REP(i, k){
    REP(j, k){
      REP(l, k){
        sum += gcd(i, j, l);
      }
    }
  }

  cout << sum << endl;
}

Measured memory_bytes: 3608
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int64_t k, a, b;
    cin >> k >> a >> b;

    if ((a + 2 >= b) || (k <= a - 1))
    {
        cout << (k + 1) << endl;
    }
    else
    {
        int64_t ans = a + (k - a + 1) / 2 * (b - a);
        if ((k - a + 1) % 2 == 1)
        {
            ans++;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(n) (n).begin(),(n).end()
typedef long long ll;
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}else{return 0;}}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}else{return 0;}}
template <class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <class T> inline T LCM(T a,T b){return a*b/GCD(a,b);}


const int MAX = 510000;
ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(){
	ll n,m,k;
	cin >> n >> m >> k;
	COMinit();
	ll ans=0;
	for(int i=1;i<n;i++){
		ans+=((((n-i)*m*m)%MOD)*COM(n*m-2,k-2)%MOD)*i;
		ans%=MOD;
	}

	for(int i=1;i<m;i++){
		ans+=((((m-i)*n*n)%MOD)*COM(n*m-2,k-2)%MOD)*i;
		ans%=MOD;
	}

	cout << ans << endl;
}

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

int main(){
	int N, i, f = 0, ans = 0;
	scanf("%d",&N);
	int *p = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &p[i]);
		p[i]--;
	}
	for(i = 0; i < N; i++){
		if(p[i] == i){
			if(f == 0){
				ans++;
				f = 1;
			}
			else{
				f = 0;
			}
		}
		else{
			f = 0;
		}
	}
	printf("%d\n", ans);
	return 0;
}

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

using namespace std;

int main()
{
    while (true) {
        string str;
        size_t n;
        cin >> str;
        if (str == "-") break;
        cin >> n;

        size_t acc = 0;
        for (auto i = 0; i < n; ++i) {
            size_t j;
            cin >> j;
            acc += j;
        }
        acc %= str.length();
        cout << str.substr(acc) << str.substr(0, acc) << endl;
    }
    
    return 0;
}



Measured memory_bytes: 3176
while True:
  n = int(input())
  if n == 0:
    break
  f = [0] * 10
  for i in range(n):
    f[int(input())] += 1
  for i in range(10):
    if f[i] == 0:
      print('-')
    else:
      print('*'*f[i])


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

int main(){
  int h,w;
  cin >> h >> w;
  vector<vector<char>>s(h+1,vector<char>(w+1));
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++) cin >> s[i][j];
    s[i][w]='#';
  }
  for(int i=0; i<w+1; i++) s[h][i]='#';
  
  vector<vector<ll>>r(h,vector<ll>(w));
  vector<vector<ll>>l(h,vector<ll>(w));
  
  ll count=0;
  for(int i=0; i<h+1; i++){
   for(int j=0; j<w+1; j++){
     if(s[i][j]=='#'){
      for(int k=count; k>=1; k--){
        l[i][j-k]=count;
      }
       count=0;
       continue;
     }
     count++;
   }
  }
  
  count=0;
  for(int i=0; i<w+1; i++){
   for(int j=0; j<h+1; j++){
     if(s[j][i]=='#'){
      for(int k=count; k>=1; k--){
        r[j-k][i]=count;
      }
       count=0;
       continue;
     }
     count++;
   }
  }
  
  ll ans=0;
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      ll x = r[i][j]+l[i][j]-1;
      ans=max(ans,x);
    }
  }
  
  cout << ans << endl;
  
}

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

int main() {

  int K;
  string S;
  cin >> K;
  cin >> S;
    if(S.size() <K+1){
    cout << S << endl;}
    
    else {
      char a;
      for (int i=0; i<K; i++){
       a = S.at(i); 
       cout << a ;
      }
     cout << "..." << endl;
    }
  
}


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

int main(){
  int n, m;
  char c[256];
  char a,b;

  while( cin >> n && n ){
    for( int i=0;i<256;i++ )
      c[i] = '.';
    while( n-- ){
      cin >> a >> b;
      c[(int)a] = b;
    }

    cin >> m;
    while( m-- ){
      cin >> a;
      if( c[(int)a]!='.' ){
	cout << c[(int)a];
	//	c[(int)a] = '.';
      }else{
	cout << a;
      }
    }
    cout << endl;
  }
  return 0;
}

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

int main()
{
    ll MOD = 1000000007;
    ll N; cin >> N;
    ll p = 1;
    rep(i,N) {
        p = (p * (i+1)) % MOD;
        //cout << p << endl;
    }
    cout << p << endl;


}


Measured memory_bytes: 3580
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        n: u64,
    }

    let mut res = 0;
    for i in 1.. {
        if i * i >= n {
            break;
        }
        if n % i == 0 {
            if i != 1 && n / (i - 1) == n % (i - 1) {
                res += i - 1;
            }
            let x = n / i - 1;
            if n / x == n % x {
                res += x;
            }
        }
    }
    println!("{}", res);
}


Measured memory_bytes: 2116
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;




int main() {
   int  n,m;
   cin >> n >> m;
   vector<int> h(n);
   rep(i, n)cin >> h[i];

   vector<int>  ans(n);
   int a, b;
   rep(i, m) {
       cin >> a >> b;
       
       if (h[a - 1] == h[b - 1]) {
           ans[a - 1]--;
           ans[b - 1]--;
       }

       if (h[a-1] > h[b-1]) {
           ans[b-1]--;
       }
       if (h[a - 1] < h[b - 1]) {
           ans[a - 1]--;
       }
   
   }
   int c = 0;
   rep(i, n) {
       if (ans[i] >= 0)c++;
   }
   cout << c << endl;
}



Measured memory_bytes: 3984
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j):
        return self.find(i)==self.find(j)


n, q = map(int,input().split())
uf = UnionFind(n)
for q in range(q):
    cmd, i, j = map(int,input().split())
    if cmd == 0:
        uf.unite(i,j)
    else:
        print(int(uf.same(i,j)))


Measured memory_bytes: 6112
import heapq

INF=10**12

N, K = map(int,input().split())
td = [[0,0] for i in range(N)]
s = [[] for i in range(N)]

for i in range(N):
    td[i][0], td[i][1] = map(int,input().split())
    td[i][0] -= 1
    s[td[i][0]].append(td[i][1])

for i in range(N):
    if s[i] == []:
        s[i].append(-INF)
    s[i].sort(key=lambda x:-x)

s.sort(key=lambda x:-x[0])

tmp = 0
q = []

for i in range(K):
    tmp += s[i][0]
    for j in range(1,len(s[i])):
        heapq.heappush(q,-s[i][j])
for i in range(K,N):
    for j in range(len(s[i])):
        heapq.heappush(q,-s[i][j])

res = tmp + K * K

for i in range(1,K)[::-1]:
    v = s[i][0]
    if q == []: break
    w = - q[0]
    if v < w:
        tmp = tmp + w - v
        heapq.heappop(q)
        heapq.heappush(q,-v)
    res = max(res, tmp + i * i)        

print(res)

Measured memory_bytes: 40396
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

int ctoi(const char c) {
    switch (c) {
        case 'a': return 0;
        case 'b': return 1;
        case 'c': return 2;
        case 'd': return 3;
        case 'e': return 4;
        case 'f': return 5;
        case 'g': return 6;
        case 'h': return 7;
        case 'i': return 8;
        case 'j': return 9;
        case 'k': return 10;
        case 'l': return 11;
        case 'm': return 12;
        case 'n': return 13;
        case 'o': return 14;
        case 'p': return 15;
        case 'q': return 16;
        case 'r': return 17;
        case 's': return 18;
        case 't': return 19;
        case 'u': return 20;
        case 'v': return 21;
        case 'w': return 22;
        case 'x': return 23;
        case 'y': return 24;
        case 'z': return 25;
    }
}

int main() {
    string s;

    cin >> s;
    int d[26];
    int num[26] = {0};

    for (int i = 0; i < s.size(); i++) {
        d[i] = ctoi(s[i]);
    }

    for (int i = 0; i < s.size(); i++) {
        num[d[i]]++;
    }

    for (int i = 0; i < s.size(); i++) {
        if ((num[i] != 1) && (num[i] != 0)) {
            cout << "no" << endl;
            return 0;
        }
    }
    cout << "yes" << endl;
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int, input().split()))
mod = 10**9 + 7
def f():
  memo = {}

  for i in l:
    if i in memo:
      memo[i] += 1
    else:
      memo[i] = 1
  
  for k, v in memo.items():
    if k == 0 and not v == 1:
      return 0
    elif not k == 0 and not v == 2:
      return 0
  
  return 2**(n//2) % mod

print(f())

Measured memory_bytes: 14436
const Main = (input) => {
  // 入力値の整形
  input = input.split('\n');
  const line2 = input[1].split(' ');
  const baseHot = parseInt(line2[0]);
  const targetHot = parseInt(line2[1]);
  const hotPoints = input[2]
    .split(' ')
    .map((hight, index) => {
      return {
        inputIndex: index,
        hot: baseHot - parseInt(hight) * 0.006,
      };
    })
    .sort((a, b) => {
      const rangeA = Math.abs(a.hot - targetHot);
      const rangeB = Math.abs(b.hot - targetHot);
      return rangeA - rangeB;
    });

  console.log(hotPoints[0].inputIndex + 1);
};

//* この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));
/*
Main(`3
21 -11
81234 94124 52141`);

Main(`2
12 5
1000 2000`);
*/


Measured memory_bytes: 7748
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

const int N = 100'009;

int p[N];

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

set<pair<int, int>> s[N];
long long sum[N];
bool was[N];

void join(int &root, int y) {
  int py = find(y);
  if (py == root) {
    return;
  }
  if ((int)s[py].size() > (int)s[root].size()) {
    swap(root, py);
  }
  p[py] = root;
  sum[root] += sum[py];
  for (auto &e : s[py]) {
    if (!was[e.second]) {
      s[root].insert(e);
    }
  }
}

int n;
int a[N];
int b[N];
int w[N];
vector<int> g[N];

bool can(int ss) {
  for (int i = 0; i < n; ++i) {
    w[i] = max(0, a[i] - ss - b[i]);
    p[i] = i;
    was[i] = false;
    s[i].clear();
  }
  for (int i = 0; i < n; ++i) {
    if (was[i] || w[i] != 0) {
      continue;
    }
    sum[i] = 0;
    s[i].emplace(w[i], i);
    int root = i;
    while (!s[root].empty()) {
      int x = s[root].begin()->second;
      if (sum[root] < w[x]) {
        break;
      }
      was[x] = true;
      p[x] = root;
      s[root].erase(s[root].begin());
      sum[root] += b[x];
      for (int y : g[x]) {
        if (!was[y]) {
          s[root].emplace(w[y], y);
        } else {
          join(root, y);
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    if (!was[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  int m;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d %d", a + i, b + i);
  }
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    --x;
    --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int ll = -1, rr = 1'000'000'000;
  while (rr - ll > 1) {
    int ss = (ll + rr) / 2;
    if (can(ss)) {
      rr = ss;
    } else {
      ll = ss;
    }
  }
  long long tot = 0;
  for (int i = 0; i < n; ++i) {
    tot += b[i];
  }
  printf("%lld\n", tot + rr);
}


Measured memory_bytes: 16384
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
c=Counter(lis)
sm=0
for i in c.keys():
    sm+=c[i]-1
if sm%2==0:
    print(len(list(c)))
else:
    print(len(list(c))-1)
    
    
        


Measured memory_bytes: 18716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
#define bas 233
int n;
char s[5050];
ull hsh[5050],powe[5050];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

ull query(int l,int r)
{
	return hsh[r]-hsh[l-1]*powe[r-l+1];
}

bool chk(int len)
{
	//cout << len << endl;
	for (int l1=1;l1+len+len-1<=n;l1++)
	{
		for (int l2=l1+len;l2+len-1<=n;l2++)
		{
			int r1=l1+len-1,r2=l2+len-1;
			//cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
			if (query(l1,r1)==query(l2,r2)) return 1;
		}
	}
	return 0;
}

int main()
{
	n=read();
	scanf("%s",s+1);
	powe[0]=1;
	rep(i,1,n) powe[i]=powe[i-1]*bas;
	rep(i,1,n) hsh[i]=hsh[i-1]*bas+(s[i]-'a'+1);
	//rep(i,1,n) cout << hsh[i] << " ";cout << endl;
	int l=1,r=n,ans=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (chk(mid)) {ans=mid;l=mid+1;}
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;
const long long INFLL = 1LL << 60;
const int INFI = 1000000000;

int main() {
    int h,w; cin >> h >> w;
    vector<vector<char>> v(h, vector<char> (w));
    vector<int> disph(h, 0);
    vector<int> dispw(w, 0);
 
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> v[i][j];
            if(v[i][j] == '#'){disph[i]=1; dispw[j] = 1;}
        }
    }
 
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(disph[i] && dispw[j]) cout << v[i][j];
        }
        if(disph[i])cout << endl;
    }
}

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int a, b;

int main(){
    cin >> a >> b;
    cout << (a*b%2?"Odd":"Even") << endl;
}
































Measured memory_bytes: 256
n, m = [int(i) for i in input().split()]
# 高さ入力
h = [int(i) for i in input().split()]
# 条件を満たす地点を記録
list = [[]for i in range(n)]
for i in range(m):
    a, b = [int(i) for i in input().split()]
    list[a-1].append(h[b-1])
    list[b-1].append(h[a-1])
ans = 0
for i in range(n):
    if len(list[i]) == 0:
        ans += 1
    elif h[i] > max(list[i]):
        ans += 1
print(ans)

Measured memory_bytes: 23104
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int X,N;
  cin >> X >> N;
  if(N==0){
    cout << X << endl;
  }
  else{
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
    int ans1=0;
    int ans2=0;
    int count=0;
    for (int j = X; j > 0; j--) {
      count=0;
    for (int i = 0; i < N; i++) {
    if(A.at(i)!=j){
     count++;
    }
    if(count==N){
      ans1=j;
      break;
    }
    }
      if(ans1!=0){
        break;
      }
    }
    
    for (int j = X; j < 102; j++) {
      count=0;
    for (int i = 0; i < N; i++) {
    if(A.at(i)!=j){
     count++;
    }
    if(count==N){
      ans2=j;
      break;
    }
    }
      if(ans2!=0){
        break;
      }
    }
    if(abs(ans2-X)<abs(ans1-X)){
    cout << ans2 << endl;
    }
    else{
      cout << ans1 <<endl;
    }
  }
}



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

int main()
{
	string s;
	cin >> s;

	int ans = 0;
	for (int i = 0; i < 4; i++) {
		if (s.at(i) == '+') ans++;
		else ans--;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


int n, m;

main(){
	while(cin >> n >> m, n){
		priority_queue<pii> q;
		ll sum = 0;
		REP(i, n){
			int a, b;
			cin >> a >> b;
			q.emplace(b, a);
			sum += a*b;
		}
		while(!q.empty() && m>0){
			pii t = q.top();
			q.pop();
			sum -= t.first*min(m, t.second);
			m -= t.second;
		}
		cout << sum << endl;
	}
	return 0;
}

Measured memory_bytes: 1324
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};






void solve(){
    string s;
    cin>>s;
    ll n=s.size();
    rep(i,n){
        if(s[i]=='9'){
            cout<<"Yes"<<endl;
            return;
        }
    }
    cout<<"No"<<endl;
}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    ll q;
    q=1;
    rep(_,q){

        solve();

    }
    

    return 0;
}


Measured memory_bytes: 256
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

N = int(input())

al = [[] for i in range(N+1)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    al[a].append((b,c))
    al[b].append((a,c))


seen = [0 for i in range(N+1)]
ans = [0 for i in range(N+1)]

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    ans[u] = 0

    while len(stack) > 0:
        v = stack.popleft()

        for w in al[v]:
            if seen[w[0]] == 0:
                stack.append(w[0])
                if w[1] % 2 == 0:
                    ans[w[0]] = ans[v]
                else:
                    ans[w[0]] = 1 - ans[v]
                seen[w[0]] = 1

bfs(1)

for i in range(1,N+1):
    print(ans[i])

Measured memory_bytes: 108652