akhauriyash/Code-Regression huggingface dataset:
// Created by kashi on 21-07-2020.
//
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define Endl endl
#define int long long
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
bool cmps(pair<int,int>p1,pair<int,int>p2) {
    return p1.ss<p2.ss;
}


int32_t main() {
    int n;
    cin >>n;
    string str;
    cin>>str;
    map<char,int>m;
    m['W']; m['R'];
    for(int i=0;i<str.size();i++){
        m[str[i]]++;
    }
    string ans;
    int count=0;
    for(int i=0;i<m['R'];i++)
        ans+='R';
    for(int i=0;i<m['W'];i++)
        ans+='W';
    for(int i=0;i<ans.size();i++){
        if(ans[i]!=str[i])
            count++;
    }
    cout<<count/2<<endl;
    return 0;
}

Measured memory_bytes: 3836
N, M = map(int, input().split())
d = [[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1],
     [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]
array = [[] for _ in range(8)]
for i in range(N):
    x, y, z = map(int, input().split())
    for n in range(8):
        array[n].append(d[n][0] * x + d[n][1] * y + d[n][2] * z)
beauty = -9999999999999999999
for a in array:
    a.sort(reverse=True)
    beauty = max(beauty, sum(a[:M]))
print(beauty)


Measured memory_bytes: 43628
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,flag=0,cnt=0;
    cin >> n;
    int max=0,min=n,A[n+1];
    long long x;
    for(int i=0;i<=n;i++) A[i]=0;
    for(int i=0;i<n;i++){
        flag=0;
        cin >> x;
        if(x>n) {
            cnt++;
            continue;
        }
        A[x]++;
        if(max<x) max=x;
        if(min>x) min=x;
    }
    for(int i=min;i<=max;i++) {
        if(A[i]>i) cnt += A[i]-i;
        else if(A[i] != i && A[i] != 0) cnt += A[i];
    }
    cout<<cnt;
}
    


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{   int a, b;
   cin >> a >> b ;
   if ( a > b)
   cout << "a > b" << endl;
   if ( a < b)
   cout << "a < b" << endl;
   if ( a == b)
   cout << "a == b" << endl;
}


Measured memory_bytes: 3112
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin>>n;
	bool h=true;
	rep(i,n){
		int a;cin>>a;
		if(a%2==0){
			if(a%3&&a%5)h=false;
		}
	}
	
	if(h)cout<<"APPROVED"<<endl;
	else cout<<"DENIED"<<endl;
	
}









Measured memory_bytes: 256
#include <cstdio>

int N, M;
int h[100 + 10], m[100 + 10];
int k[100 + 10], g[100 + 10];

int ah[200 + 20], am[200 + 20];

inline int earlyTime(int h1, int m1, int h2, int m2) {
  if (h1 < h2) { return 0; }
  else if (h1 == h2) {
    if (m1 < m2) { return 0; }
    else if (m1 == m2) { return 2; }
    else { return 1; }
  }
  else { return 1; }
}

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

  scanf("%d", &M);
  for (int i = 0; i < M; ++i) {
    scanf("%d %d", &k[i], &g[i]);
  }

  int nind = 0;
  int mind = 0;
  int aind = 0;

  while (nind < N && mind < M) {
    switch (earlyTime(h[nind], m[nind], k[mind], g[mind])) {
      case 0:
        ah[aind] = h[nind];
        am[aind] = m[nind];
        aind++; nind++;
        break;
      case 1:
        ah[aind] = k[mind];
        am[aind] = g[mind];
        aind++; mind++;
        break;
      case 2:
        ah[aind] = h[nind];
        am[aind] = m[nind];
        aind++; nind++; mind++;
        break;
    }
  }

  for (; nind < N; ++nind) {
    ah[aind] = h[nind];
    am[aind] = m[nind];
    aind++;
  }

  for (; mind < M; ++mind) {
    ah[aind] = k[mind];
    am[aind] = g[mind];
    aind++;
  }

  for (int i = 0; i < aind; ++i) {
    if (i) { printf(" "); }
    printf("%d:%02d", ah[i], am[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 1052
//Author is Sorowar Mahabub
//Studies B. Sc in CSE
//Int' Islamic University Chittagong (IIUC)
//Cell: 01834-756433
//Email: sorowarmahabub1709vip@gmail.com

#include<stdio.h>

int isprime( int n ) {
    if(n<=1)
        return 0;
    for(int i=2; i*i<=n; i++) {
        if(n%i==0)
            return 0;
    }
    return 1;
}


int main() {
    int end, i;
    scanf("%d",  &end);

    for (i = 2; ; ++i) {
        
        if (isprime(i)== 1) {
            if(i>=end) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}






Measured memory_bytes: 1708
#include<iostream>
#include<vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define MAX 10001
vector<int> divisors[MAX];

int main(){
  divisors[0].push_back(0);
  for(int i=1;i<MAX;++i){
    divisors[i].reserve(100);
    for(int j=1;j<=i/2+1;++j){
      if(i%j==0){
	divisors[i].push_back(j);
	divisors[i].push_back(-j);
      }
    }
    divisors[i].push_back(i);
    divisors[i].push_back(-i);
  }
  while(true){
    int a,b,c;
    int p=0,q=0,r=0,s=0;
    cin >> a >> b >> c;
    if(a==0&&b==0&&c==0)break;
    for(int i = 0; i < divisors[a].size(); ++i){
      int tr = divisors[a][i];
      if( tr < 0 ) continue;
      int tp = a / tr;
      if( tp < tr ) continue;
      for(int j = 0; j < divisors[(c<0?-c:c)].size(); ++j){
	int ts = c!=0?divisors[(c<0?-c:c)][j]:0;
	int tq = c!=0?c / ts:b;
	if( tp == tr && ts == 0 && tq < ts && b < 0 ) swap(ts,tq);
	if( tp == tr && tq < ts ) continue;
	if( tp*ts+tq*tr == b ){
	  p = tp; s = ts; q = tq; r = tr;
	}
      }
    }
    if( p==0 && r==0 && q==0 && s==0 ) cout << "Impossible" << endl;
    else cout << p << ' ' << q << ' ' << r << ' ' << s << endl;
  }
  return 0;
}

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

using namespace std;

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int ans = 0;
    for (int i = 0; i < 3; ++i) {
        if (s[i] == t[i]) {
            ++ans;
        }
    }

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

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int[] leaf;

	public static void main(String[] args) throws Exception {
		while (true) {
			String tree = sc.nextLine();
			if (tree.equals("END")) break;
			int N = sc.nextInt();
			leaf = new int[N];
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < 4; ++j) {
					leaf[i] += (sc.nextInt() << j);
				}
			}
			sc.nextLine();
			Node root = new Parser(tree).parse();
			root.process();
			System.out.println(root.count[0xF]);
		}
	}

	static class Parser {
		String val;
		int pos = 0;

		Parser(String tree) {
			this.val = tree;
		}

		Node parse() {
			Node ret = new Node();
			++pos;
			if (val.charAt(pos) == '(') {
				ret.left = parse();
			} else {
				int index = parseInt();
				ret.left = new Node();
				ret.left.count[leaf[index - 1]] = 1;
			}
			++pos;
			if (val.charAt(pos) == '(') {
				ret.right = parse();
			} else {
				int index = parseInt();
				ret.right = new Node();
				ret.right.count[leaf[index - 1]] = 1;
			}
			++pos;
			return ret;
		}

		int parseInt() {
			int ret = 0;
			while ('0' <= val.charAt(pos) && val.charAt(pos) <= '9') {
				ret *= 10;
				ret += val.charAt(pos) - '0';
				++pos;
			}
			return ret;
		}

	}

	static class Node {
		Node left;
		Node right;
		int[] count = new int[16];

		void process() {
			if (left == null) return;
			left.process();
			right.process();
			for (int i = 0; i < 16; ++i) {
				for (int j = 0; j < 16; ++j) {
					count[i & j] += left.count[i] * right.count[j];
					count[i | j] += left.count[i] * right.count[j];
					count[i ^ j] += left.count[i] * right.count[j];
				}
			}
		}
	}

}

Measured memory_bytes: 12000
n, m = map(int, input().split())
ppyy = [list(map(int, input().split())) for _ in range(m)]
order = [{}] * (n + 1)
cnt = [1] * (n + 1)
for p, y in sorted(ppyy, key=lambda x: x[1]):
    order[p].update({y: cnt[p]})
    cnt[p] += 1
for p, y in ppyy:
    cnt[p] += 1
    print(str(format(p, '06')) + str(format(order[p][y], '06')))

Measured memory_bytes: 41852
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int n;
  std::string s;
  cin>>n>>s;
  int cum_right[100001]={};
  int cum_left[100001]={};
  std::unordered_map<int,int> cummap_r,cummap_l;
  if(s[0]=='>'){
    cum_right[0]=1;
    cummap_r[1]=0;
  }else{
    cum_left[0]=1;
    cummap_l[1]=0;
  }

  for(int i=1;i<n;i++){
    cum_left[i]=cum_left[i-1];
    cum_right[i]=cum_right[i-1];
    if(s[i]=='>'){
      cum_right[i]++;
      cummap_r[cum_right[i]]=i;

    }else{
      cum_left[i]++;
      cummap_l[cum_left[i]]=i;
    }
  }

  int result=0;
  for(int i=0;i<n;i++){

    int r=(i==0?0:cum_right[i-1]);
    int l=cum_left[n-1]-cum_left[i];
    int tmp;

    if(s[i]=='<'){

if(r<=l){
        tmp=cummap_l[r+cum_left[i]]+1;

      }else{
        tmp=n-cummap_r[cum_right[i]-l];

      }
    }else{
      if(r<l){
        tmp=cummap_l[r+1+cum_left[i]]+1;

      }

      else{
        tmp=n-cummap_r[cum_right[i]-l];

      }
    }
    result=std::max(result,tmp);
  }

  cout<<std::min(result,n)<<endl;



  return 0;
}


Measured memory_bytes: 7896
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
dist_matrix = [[INF]*N for _ in range(N)]

for _ in range(M):
	A, B, C = MAP()
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

for i in range(N):
	dist_matrix[i][i] = 0

#for i in range(N):
#	print(dist_matrix[i])
#print()

def Warshall_Floyd(dist, N):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Warshall_Floyd(dist_matrix, N)

#for i in range(N):
#	print(dist_matrix[i])


ans = INF
for x in permutations(r):
	tmp = x[0]
	dis = 0
	for i in range(1, R):
		dis += dist_matrix[tmp-1][x[i]-1]
		tmp = x[i]
	ans = min(ans, dis)
	
print(int(ans))






Measured memory_bytes: 76632
#include<stdio.h>

int H[251];

int main(){
	int i,n;	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&H[i]);
	}

	for(i=1;i<=n;i++){
		printf("node %d: key = %d, ",i,H[i]);
		if(i/2>=1)printf("parent key = %d, ",H[i/2]);
		if(i*2<=n)printf("left key = %d, ",H[i*2]);
		if(i*2+1<=n)printf("right key = %d, ",H[i*2+1]);

		printf("\n");
	}

	return 0;
}



Measured memory_bytes: 2692
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def prime(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > x**(1/2): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = prime(10**6)
pd = {}
for i in range(len(primes)):
	pd[primes[i]] = i
MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]
K = [0]*len(primes)
for i in range(N):
	a = A[i]
	for i in range(len(primes)):
		p = primes[i]
		if a == 1:
			break
		elif p > 1000:
			K[pd[a]] = 1
			break
		else:
			cou = 0
			while a%p==0:
				a = a//p
				cou += 1
			K[i] = max(cou, K[i])
kv = 1
for i in range(len(primes)):
	kv *= power(primes[i], K[i])
	kv %= MOD
ans = 0
for i in range(N):
	ans += divide(kv, A[i])
	ans %= MOD
print(ans)

Measured memory_bytes: 114032
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>

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

using namespace std;

int main(){

	int A,B;

	cin >> A >> B;

	if(A == B){
		cout << A +B << endl;
	} else {
		cout << 2 * max(A, B) - 1 << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = long long;

vector<vector<ll>> connect;
vector<vector<ll>> color;

void update(ll v, ll d, ll i) {
    if (color[v][d] != 0) {
        return;
    }

    color[v][d] = i;

    if (d == 0) {
        return;
    }

    update(v, d - 1, i);
    for (auto next : connect[v]) {
        update(next, d - 1, i);
    }
}

int main() {
    ll N, M;
    cin >> N >> M;

    connect.resize(N);

    for (ll i = 0; i < M; i++) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }

    ll Q;
    cin >> Q;

    vector<ll> v(Q), d(Q), c(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> v[i] >> d[i] >> c[i];
        v[i]--;
    }

    color.assign(N, vector<ll>(11, 0));

    for (ll i = Q - 1; i >= 0; i--) {
        update(v[i], d[i], c[i]);
    }

    for (ll i = 0; i < N; i++) {
        cout << color[i][0] << endl;
    }
}

Measured memory_bytes: 20980
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main(){
  int n;
  std::cin >> n;
  vector<int> p(n), cell(n, 1e9);
  for (int i = 0; i < n; i++) {
    std::cin >> p[i];
  }
  queue<pii> que;
  cell[0] = 0;
  que.push(pii(0, 0));
  while(not que.empty()){
    int s = que.front().first;
    int cost = que.front().second;
    que.pop();
    for (int i = 1; i <= 6; i++) {
      int pos = s + i;
      bool flag = false;
      for (int j = 0; j < 2*n; j++) {
        pos = min(n - 1, pos);
        if(p[pos] != 0 and cell[pos] > cost){
          cell[pos] = cost;
          pos += p[pos];
        }else{
          break; 
        }
        if(j == 2*n - 1)flag = true;
      }
      pos = min(n - 1, pos);
      if(flag == true)continue;
      if(cell[pos] > cost + 1){
        cell[pos] = cost + 1;
        que.push(pii(pos, cost + 1));
      }
    }
  }

  std::cout << cell[n - 1] << std::endl;
  return 0;
}

Measured memory_bytes: 1796
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		sc.close();
		char c;
		StringBuilder sb = new StringBuilder();
		for (int i =0; i < str.length(); i++) {
			c = str.charAt(i);
			if (Character.isUpperCase(c)) {
				c = Character.toLowerCase(c);
			} else if (Character.isLowerCase(c)) {
				c = Character.toUpperCase(c);
			}
			sb.append(c);
		}
		System.out.println(sb);
	}
}

Measured memory_bytes: 17140
import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        
        int b = a % 10;
        if(b == 2 || b == 4 || b==5 || b==7 || b==9){
            System.out.println("hon");
        }else if(b == 3){
            System.out.println("bon");
        }else{
            System.out.println("pon");
        }

        scan.close();
    }
}

Measured memory_bytes: 35748
#include "bits/stdc++.h"
#include <unordered_set>

#define _CRT_SECURE_NO_WARNINGS

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

const int dy[] = { 0, 1, 0, -1 };
const int dx[] = { 1, 0, -1, 0 };

using LL = long long int;
using LD = long double;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
//					===
//					===	
//					===
//	**================================
//	**								**	
//	**		v[0]			○		**
//	**	v[3]	v[1]	○		○	**
//	**		v[2]			○		**
//	**								**
//	**			(===)	(===)		**
//  ==================================
//
//============================================

bool solve(vi v) {
	if (v[0] <= 0 && 0 < v[2] || v[2] <= 0 && 0 < v[0]) return false;
	if (v[1] <= 0 && 0 < v[3] || v[3] <= 0 && 0 < v[1]) return false;

	return true;
}

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

	string s;
	cin >> s;

	int n = s.size();

	vi v(4);
	for (int i = 0; i < n; i++) {
		if (s[i] == 'N') v[0]++;
		else if (s[i] == 'W') v[1]++;
		else if (s[i] == 'S') v[2]++;
		else v[3]++;
	}

	cout << (solve(v) ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
//set many funcs template
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007
#define pi 3.1415926535897932384

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
double dbmax(double a,double b){if(a>b){return a;}return b;}
double dbmin(double a,double b){if(a<b){return a;}return b;}
double dbzt(double a,double b){return dbmax(a,b)-dbmin(a,b);}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int strsortfncsj(const void *a,const void *b){return strcmp((char *)a,(char *)b);}
int strsortfnckj(const void *a,const void *b){return strcmp((char *)b,(char *)a);}

int main(void){
    int i,j,n,m,k,a[262144],b,c,w,r=0,l,t,d,x;
    //double d;
    char s[262144];
    scanf("%d%d%d",&n,&d,&x);
    //l=strlen(s);
    for(i=0;i<n;i++){scanf("%d",&a[i]);
        x+=(1+(d-1)/a[i]);
    }
    //qsort(a,n,sizeof(int),sortfncsj);
    printf("%d\n",x);
    return 0;
}

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

def get_parent(node):
    parent = -1
    if "parent" in node:
        return node["parent"]
    return parent

def get_depth(node):
    depth = 0
    while "parent" in node:
        depth += 1
        parent = node["parent"]
        node = rooted_tree[parent]
    return depth

def get_node_type(node):
    if "parent" not in node:
        return "root"
    if "left" not in node:
        return "leaf"
    return "internal node"

def get_children(node):
    if "left" not in node:
        return "[]"
    left = node["left"]
    siblings = []
    siblings.append(str(left))
    while rooted_tree[left]["right"] > -1:
        right = rooted_tree[left]["right"]
        siblings.append(str(right))
        left = right
    return "[{}]".format(", ".join(siblings))

        
rooted_tree = [{} for i in range(N)]
for _ in range(N):
    row = input() #0 3 1 4 10みたいにid k c1,...,ckが与えられる。
    id, k, *c = list(map(int, row.split()))
    if k > 0:
        #まずleftになる子供を設定。
        rooted_tree[id]["left"] = c[0]
        #親(id)から見て、各子供のrightになる兄弟を設定していく。さらにparentも親(id)と設定する。
        for i in range(len(c)):
            child_id = c[i]
            right = -1
            if i < len(c) - 1:
                right = c[i+1]
            rooted_tree[child_id]["right"]  = right
            rooted_tree[child_id]["parent"] = id

for id in range(N):
    node = rooted_tree[id]
    parent = get_parent(node)
    depth = get_depth(node)
    node_type = get_node_type(node)
    children = get_children(node)
    print("node {}: parent = {}, depth = {}, {}, {}".format(id, parent, depth, node_type, children))


Measured memory_bytes: 42148
import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args){
        int count;
        int[] array = new int[100];
        int key;
        int counter = 0;

        try{
            Scanner scan = new Scanner(System.in);
            String str = scan.next();

            count = Integer.parseInt(str);

            for(int i = 0; i < count; i++){
                str = scan.next();
                array[i] = Integer.parseInt(str);
            }

            //Sort Part
            for(int i = 0; i < count - 1; i++){
                for(int j = count - 1; j > i; j--){
                    //System.out.println("---OK");
                    if(array[j] < array[j-1]){
                        key = array[j-1];
                        array[j-1] = array[j];
                        array[j] = key;
                        counter++;
                    }
                }
                //System.out.println("OK");
            }

            for(int i = 0; i < count; i++){
                if(i == count - 1){
                    System.out.println(array[i]);
                }else{
                    System.out.print(array[i] + " ");
                }
            }

            System.out.println(counter);

        }catch(Exception e){
            System.out.println("ERROR");
        }

    }
}



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

int f[] = {0, 0, 1, 1};
int s[] = {1, 0, 1, 0};

int main() {
	int m;
	cin >> m;
	for(int c = 0; c < m; ++c){
		string str;
		cin >> str;
		int ans = 0;
		map<string, int> cnt;
		for(unsigned int i = 1; i < str.size(); ++i){
			string s1[2], s2[2];
			s1[0] = s1[1] = str.substr(0, i);
			s2[0] = s2[1] = str.substr(i, str.size() - i);
			reverse(s1[1].begin(), s1[1].end());
			reverse(s2[1].begin(), s2[1].end());
			for(int j = 0; j < 4; ++j){
				string ss = s1[f[j]] + s2[s[j]];
				if(cnt[ss] == 0){
					cnt[ss] = 1;
					ans++;
				}
			}
			for(int j = 0; j < 4; ++j){
				string ss = s2[f[j]] + s1[s[j]];
				if(cnt[ss] == 0){
					cnt[ss] = 1;
					ans++;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1300
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

N, K = MAP()
A = LIST()

# 隣り合う区間との関係を確認(これで重なる区間同士は全てカバーできる)
stmin = SegTree(N, min, INF, A)
stmax = SegTree(N, max, -INF, A)
total = N - K + 1
dup = 0
for i in range(N-K):
    mn = stmin.query(i, i+K+1)
    mx = stmax.query(i, i+K+1)
    if mn == A[i] and mx == A[i+K]:
        dup += 1

# 離れた区間同士の確認
B = [0] * N
for i in range(N-1):
    # 増加か減少で2値化して累積和
    if A[i] < A[i+1]:
        B[i+1] = 1
B = list(accumulate(B))
# 最初の1回は重複にならないのでINFにしておく
prev = INF
for i in range(N-K+1):
    # 増加がK-1回連続している箇所を確認
    if B[i+K-1] - B[i] == K - 1:
        # 前回の該当箇所と離れている(区間が重ならない)ならカウントする
        if prev + K - 1 < i:
            dup += 1
        prev = i

print(total - dup)


Measured memory_bytes: 103504
#include <stdio.h>

int main(void){
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  if((a == 1 && b == 1) || (c == 1)){
    printf("Open\n");
  }else{
    printf("Close\n");
  }
  return 0;
}

Measured memory_bytes: 584
n = int(input())
s = []
nums = {}

for i in range(n):
    s.append(input())

for i in range(n):
    t = s[i]
    if t in nums:
        nums[t] += 1
    else:
        nums[t] = 1

maxV = 0
maxK = []

for key, val in nums.items():
    maxV = max(maxV, val)

for key, val in nums.items():
    if val == maxV:
        maxK.append(key)

# print(nums)
# print(maxK)

maxK.sort()

for i in range(len(maxK)):
    print(maxK[i])


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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){
  
  int n,m;
  cin >> n>> m;
  cout << n-m+1 << endl;





  

  return 0;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

int n, k;
string s;

int main(void) {
  // Here your code !

  scanf("%d %d", &n, &k);

  cin >> s;

  s[k - 1] = s[k - 1] - ('A' - 'a');

  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int N, T;
int M[1005], L[1005], K[1005];
int used[1005], add[1005];
 
bool check(int x){
   
  memset(used,0,sizeof(used));
  memset(add,0,sizeof(add));
   
  for(int i=0;i<=T;i++){
     
    x+=add[i];
     
    for(int j=0;j<N;j++){
       
      if(x==0) break;
       
      if(used[j]) continue;
       
      int mod=L[j]+K[j];
       
      if((i%mod<=L[j])&&i+M[j]<=T){
    x--;
    add[i+M[j]]++;
    used[j]=1;
      }      
       
    }
 
  }
   
  int res=0;
  for(int i=0;i<N;i++) res+=used[i];
   
  return res==N;
}
 
void solve(){
   
  for(int i=0;i<=1000;i++)
    if(check(i)){
      cout<<i<<endl;
      return;
    }
   
}
 
int main(){
   
  while(1){
     
    cin>>N>>T;
    if(!N&&!T) break;
     
    for(int i=0;i<N;i++) scanf("%d %d %d", &M[i], &L[i], &K[i]);
     
    solve();
     
  }
   
  return 0;
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1e9;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    a += b;
    c += d;
    if (a > c) printf("Left");
    else if (a == c) printf("Balanced");
    else printf("Right");
}

Measured memory_bytes: 256
N, A, B = map(int,input().split())

if N <= A:
    print(N)
elif N <= (A+B):
    print(A)
else:
    sum = A+B
    repeat = int(N/sum)
    amari = N%sum

    if amari <=A:
        print(A*repeat+amari)
    else:
        print(A*repeat+A)

Measured memory_bytes: 3064
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()



N,K=map(int,input().split())
A=list(map(int,input().split()))


def main(n):
    return(sum([max(i//n-(i%n==0)*1,0) for i in A])<=K)
#print(main(5))
ng=0
ok=10**18
while ok-ng>1:
    mid=(ok+ng)//2
    if main(mid):
        ok=mid
    else:
        ng=mid

print(ok)


Measured memory_bytes: 222352
#include <stdio.h>
#include <complex>

double cross(double x1, double y1, double x2, double y2) {
	return x1*y2-x2*y1;
}

int main()
{
	double x1, y1, x2, y2, x3, y3, xp, yp;
	while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",
				&x1, &y1, &x2, &y2, &x3, &y3, &xp, &yp)!=EOF) {
		double c1 = cross(xp-x1, yp-y1, x2-x1, y2-y1);
		double c2 = cross(xp-x2, yp-y2, x3-x2, y3-y2);
		double c3 = cross(xp-x3, yp-y3, x1-x3, y1-y3);
		if((c1>0 && c2>0 && c3>0) || (c1<0 && c2<0 && c3<0)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 0
n = int(input())
hlis = list(map(int, input().split()))
ans = 0
judge = 'Yes'
for i in range(1, n):
    if hlis[i-1] - hlis[i] == 1:
        hlis[i] += 1
    elif hlis[i-1] - hlis[i] > 1:
        judge = 'No'
        break
print(judge)

Measured memory_bytes: 15020
n = int(input())
info = []
for i in range(n):
    info.append(input())

info.sort()


ans = [info[0]]
record = 1
tem_record = 1
for i in range(n-1):
    if info[i] == info[i+1]:
        tem_record += 1
        if i == n-2:
            if tem_record > record:
                record = tem_record
                ans = [info[i]]
            elif tem_record == record and i != 0:
                ans.append(info[i])
    else:
        if tem_record > record:
            record = tem_record
            ans = [info[i]]
        elif tem_record == record and i != 0:
            ans.append(info[i])

        tem_record = 1

if record == 1 and info[n-1] != info[n-2]:
    ans.append(info[n-1])


ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 20680
#include <iostream>
using namespace std;
const int maxn = 1e5 + 100;
int n;
long long a[maxn], dp[maxn];
int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    dp[1] = 0;
    for(int i = 2; i <= n; i++) {
        dp[i] = 1e18;
        dp[i] = min(dp[i], dp[i-1] + abs(a[i] - a[i-1]));
        if(i-2 >= 1) dp[i] = min(dp[i], dp[i-2] + abs(a[i] - a[i-2]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
while 1:
    m,f,r = map(int,input().split())
    t = m + f
    if t == -2 and r == -1:break
    elif m==-1 or f == -1 or t<30:print("F")
    elif t<50>r:print("D")
    elif t < 65:print("C")
    elif t < 80 :print("B")
    else:print("A")


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

int main(){
  int a[40]={},n;
  for(int i=0;i<28;i++){
    cin>>n;
    a[n]+=1;
  }
  for(int i=1;i<=30;i++){
    if(a[i]==0){
      cout<<i<<endl;
    }
  }
  return 0;
}

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

typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A[i] >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if (N % 2) {
        cout << B[N / 2] - A[N / 2] + 1 << "\n";
    } else {
        cout << B[N / 2] + B[N / 2 - 1] - A[N / 2] - A[N / 2 - 1] + 1 << "\n";
    }
}

Measured memory_bytes: 6428
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

template<class T>inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T>inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int A, B, C; cin >> A >> B >> C;
	cout << min(C, B / A) << "\n";

	return 0;
}


Measured memory_bytes: 256
n = int(input())
l = []
for i in range(n):
    s = input()
    if i == 0:
        l.append(s)
    else:
        if l[-1][-1] == s[0] and s not in l:
            l.append(s)
        else:
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 38256
X, Y = map(int, input().split())
MOD = 10 ** 9 + 7


def pow(a, b, p):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = pow(a, b // 2, p)
        return (d * d) % p
    else:
        return (a * pow(a, b - 1, p)) % p


def fact(a, p):
    f = 1
    for i in range(1, a + 1):
        f *= i
        f %= p
    return f


if (X + Y) % 3 == 0:
    N = (X + Y) // 3
    if X - N >= 0 and Y - N >= 0:
        ans = fact(N, MOD) * pow(fact(X - N, MOD), MOD - 2, MOD) * \
            pow(fact(Y - N, MOD), MOD - 2, MOD)
        ans %= MOD
    else:
        ans = 0
else:
    ans = 0

print(ans)


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;

namespace CompetitiveProgramming
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;

            string[] n_m_c = Console.ReadLine().Split(' ');
            int n = int.Parse(n_m_c[0]);
            int m = int.Parse(n_m_c[1]);
            int c = int.Parse(n_m_c[2]);

            string[] B = Console.ReadLine().Split(' ');

            for (var i = 0; i < n;i++)
            {
                string[] A = Console.ReadLine().Split(' ');
                int sum = 0;
                for (var j = 0; j < m;j++)
                {
                    sum += int.Parse(B[j]) * int.Parse(A[j]);
                }
                if (sum + c > 0)
                {
                    count += 1;
                }
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <stdlib.h>

using namespace std;

int main(void)
{
    int h, w;
    char a[101][101] = {0};
    char b[101][101] = {0};
    char c[101][101] = {0};

    cin >> h >> w;
    
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }

    int bi = 1;
    for (int i = 1; i <= h; i++) {
        int count_row = 0;
        for (int j = 1; j <= w; j++) {
            if (a[i][j] == '.') {
                count_row++;
            }
            b[bi][j] = a[i][j];
        }
        if (count_row != w) {
            bi++;
        }
    }
    bi--;

    int bj = 1;
    for (int j = 1; j <= w; j++) {
        int count_column = 0;
        for (int i = 1; i <= bi; i++) {
            if (b[i][j] == '.') {
                count_column++;
            }
            c[i][bj] = b[i][j];
        }
        if (count_column != bi) {
            bj++;
        }
    }
    bj--;

    for (int i = 1; i <= bi; i++) {
        for (int j = 1; j <= bj; j++) {
            cout << c[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Long N = Long.parseLong(sc.next());
		sc.close();
		Long n = 0L;
		for(int i = (int)Math.sqrt(N);i > 0;i--) {
			if(N%i==0) {
				n = N/ i;
				break;
			}
		}
		System.out.println(n.toString().length());
	}
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
/*
深さしらべて、3個ずつにぬれるいろの可能性をかけてくかんじ
1=K
2=K-1
むずかしい
DFSかな
DP?
子どもの数のデータはいる
1個ウエの親データ

6*5P2*(6-2)P3*...みたいな

1-2-4
 -3-5
   -6
*/
vector<bool> seen;
vector<vector<ll>> G;
vector<ll> C;
ll MOD=1e9+7,N,K;
queue<ll> Q;
struct UnionFind{
  vector<ll> par,siz;
  
  UnionFind(ll N):par(N+1),siz(N+1,1){
    for(int i=0; i<=N; i++)
      par[i]=i;
  }
  
  void mkpar1(ll parent, ll n){//親は最上位
    for(auto next_n: G[n]){
      if(seen[next_n]) continue;
      seen[next_n]=true;
      par[next_n]=parent;
      mkpar1(parent, next_n);
    }
  }
  
  void mkpar2(ll n){//親は1個うえ
    for(auto next_n: G[n]){
      if(seen[next_n]) continue;
      seen[next_n]=true;
      par[next_n]=n;
      mkpar2(next_n);
    }
  }
  
  ll root(ll x){
    if(par[x]==x)
      return x;
    return par[x]=root(par[x]);
  }
  
  void unite(ll x, ll y){
    ll rx=root(x), ry=root(y);
    if(rx==ry)
      return;
    par[ry]=rx;
    siz[rx]+=siz[ry];    
  }
  
  bool issame(ll x, ll y){
    return root(x)==root(y);
  }
  
  ll size(ll x){
    return siz[root(x)];
  }
};

ll bfs(){
  ll ans=K;
  while(!Q.empty()){
    ll v=Q.front();
    Q.pop();
    //子どもの数だけ組み合わせ
    for(ll i=0; i<C[v]; i++){
      if(v==1) (ans*=(K-1-i))%=MOD;
      else(ans*=(K-2-i))%=MOD;
    }
    //次の数いれる
    for(auto next_v: G[v]){
      if(seen[next_v]) continue;
      seen[next_v]=true;
      if(C[next_v]==0) continue;
      Q.emplace(next_v);
    }
  }
  return ans;
}
int main(){
  cin>>N>>K;
  seen.assign(N+1,false);
  C.assign(N+1,0);
  G.assign(N+1, vector<ll>(0,0));
  for(ll i=0; i<N-1; i++){
    ll a,b; cin>>a>>b;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  UnionFind tree(N);
  tree.mkpar2(1);
  //子どもの数
  for(ll i=2; i<=N; i++) C[tree.par[i]]++;
  seen.assign(N+1,false);
  Q.emplace(1);
  seen[1]=true;
  cout<<bfs()<<endl;
}

Measured memory_bytes: 10112
import math

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

renzoku=1
ans = 0


for i in range(len(a_list)):
  if i!=0:
    if(a_list[i]==a_list[i-1]):
      renzoku += 1
      if(i==len(a_list)-1):
        ans += math.floor(renzoku/2)
    else:
      if renzoku!=1:
        ans += math.floor(renzoku/2)
        renzoku=1


print(ans)


Measured memory_bytes: 3060
N = int(input())
A = sorted([int(_) for _ in input().split()])
ans = sum(A)
for i in range(1, N // 2 + 1):
    a1 = ans - 2 * (A[2 * i - 2] + A[2 * i - 1])
    if a1 < ans:
        break
    ans = a1
print(ans)


Measured memory_bytes: 14412
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()
A = getArray(5)
# 一番乗員が少ない交通機関がボトルネックになる
# 他はトントンで行ける
neck = min(A)
print((N + neck - 1) // neck + 4)


Measured memory_bytes: 64236
N, D = list(map(int,input().split()))
X = []
for i in range(N):
    X.append(list(map(int,input().split())))
#print(X)
count = 0
for i in range(0,N,1):
    for j in range(i+1,N,1):
        wa = 0
        for k in range(D):
            wa += (X[i][k] - X[j][k])**2
        if wa**0.5 == int(wa**0.5):
            count += 1
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repeq(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define rep1(i,x,n) for(int (i)=(x);(i)<(int)(n);(i)++)
#define rep1eq(i,x,n) for(int (i)=(x);(i)<=(int)(n);(i)++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
using namespace std;
using ll = long long;
using Int = long long;

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;
typedef pair<int,int> P;

//少数点表示
//cout << std::fixed << std::setprecision(14) << 値

int main(){
    cin.tie( 0 ); ios::sync_with_stdio( false );
    int a,b,c;
    int n;
    cin >> n;
    vector<int> l(n);
    cin >> a >> b >> c;
    rep(i,n) cin >> l[i];
    int ans = inf;
    for(int bit=0; bit<(1<<(n*2)); bit++){
        //bit2桁で表す、00未使用、01A、10B、11C
        int mp = 0;
        int A=0,B=0,C=0;
        for(int keta = 0; keta<n; keta++){
            if(((bit >> (keta*2))&0b11)==0b01) {A += l[keta]; mp += 10;}
            if(((bit >> (keta*2))&0b11)==0b10) {B += l[keta]; mp += 10;}
            if(((bit >> (keta*2))&0b11)==0b11) {C += l[keta]; mp += 10;}
        }
        //cout << "A:"<<A<<"B:"<<B<<"C:"<<C<<endl;
        mp += abs(A-a) + abs(B-b) + abs(C-c) - 30;
        if(abs(A-a) == a || abs(B-b) == b || abs(C-c) == c) mp = inf;
        ans = min(ans,mp);
    }

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

Measured memory_bytes: 256
N, M = map(int, input().split())
pairs = []
for i in range(M):
    t = list(map(int, input().split()))
    pairs.append(t)

p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
    r.append("{:06d}{:06d}".format(r[0], p_count[r[0]]))
    p_count[r[0]] += 1

for r in pairs:
    print(r[2])


Measured memory_bytes: 36016
S = list(input())

p = S[0]+S[1]
q = S[2]+S[3]

p_flag = 0
q_flag = 0

if int(p) == 0 and int(q) == 0:
    print('NA')
elif int(p) == 0:
    if int(q) < 13:
        print('YYMM')
    else:
        print('NA')
elif int(q) == 0:
    if int(p) < 13:
        print('MMYY')
    else:
        print('NA')
else:
    if int(p) > 12:
        p_flag = 1
    if int(q) > 12:
        q_flag = 1

    if p_flag and q_flag:
        print('NA')
    elif p_flag:
        print('YYMM')
    elif q_flag:
        print('MMYY')
    else:
        print('AMBIGUOUS')


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


using namespace std;

int main(){
    int x,y;

    cin>>x>>y;

   int a[12]={0,1,0,2,0,2,0,0,2,0,2,0};

   if(a[x-1]==a[y-1]){
       cout<<"Yes"<<endl;
   }else{
       cout<<"No"<<endl;
   }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		
		int start = Math.max(A, C);
		int end = Math.min(B, D);
		
		System.out.println(Math.max(0, end - start));
	}
}


Measured memory_bytes: 21844
n=int(input())
ans=[int('9'+'0'*i) for i in range(0,8,2)]
p=len(str(n))
if len(str(n))&1==0:
    print(sum(ans[:p//2]))
else:
    print(sum(ans[:p//2])+(n+1-int('1'+'0'*(p-1))))
    

        

Measured memory_bytes: 38396