akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>

using namespace std;
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
//typedef boost::multiprecision::cpp_int bigint;

template< typename T >
struct edge {
	ll src, to;
	T cost;

	edge(ll to, T cost) : src(-1), to(to), cost(cost) {}

	edge(ll src,ll to, T cost) : src(src), to(to), cost(cost) {}

	edge& operator=(const int& x) {
		to = x;
		return *this;
	}

	operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

vector<vector<bool>> check;

template< typename T >
void warshall_floyd(Matrix< T >& g, T INF) {
	for (int k = 0; k < g.size(); k++) {
		for (int i = 0; i < g.size(); i++) {
			for (int j = 0; j < g.size(); j++) {
				if (g[i][k] == INF || g[k][j] == INF) continue;
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
}

ll N, M;

int main() {
	cin >> N >> M;
	vector<vector<ll>> G,was;
	G.resize(N,vector<ll>(N,1e6));
	was.resize(N, vector<ll>(N, 1e6));
	for (ll n = 0; n < N; n++) {
		G[n][n] = 0;
		was[n][n] = 0;
	}
	for (ll m = 0; m < M; m++) {
		ll a, b, c;
		cin >> a >> b >> c;
		G[--a][--b] = c;
		G[b][a] = c;
		was[a][b] = c;
		was[b][a] = c;
	}
	warshall_floyd(was, (ll)1e6);
	check.resize(N, vector<bool>(N, false));
	for (ll s = 0; s < N; s++) {
		for (ll t = 0; t < N; t++) {
			if (s == t)continue;
			for (ll k = 0; k < N; k++) {
				if (G[s][k] == 1e6)continue;   //辺なし
				if (G[s][k] + was[k][t] == was[s][t])check[s][k] = true;
			}
		}
	}
	ll ans = 0;
	for (ll s = 0; s < N; s++) {
		for (ll t = 0; t < N; t++) {
			if (s == t)continue;
			if (G[s][t] == 1e6)continue;
			if (check[s][t])ans++;
		}
	}
	cout << M - ans / 2 << endl;
	return 0;
}

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

using namespace std;

#define int long long
int const maxn = 1e5 + 5;
int dist[maxn];
int inf = 1e16;
map < pair < int, int >, int > gett;

main() {
#ifdef HOME
    //freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, l, r, c;
    cin >> n >> m;
    set < pair < int, int > > d;
    for (int i = 1; i <= m; ++i) {
        cin >> l >> r >> c;
        d.insert({l, r});
        if (gett.find({l, r}) == gett.end()) gett[{l, r}] = c;
        else gett[{l, r}] = min(gett[{l, r}], c);
    }
    set < pair < int, int > > Q;
    for (int i = 2; i <= n; ++i) dist[i] = inf;
    for (int i = 1; i <= n; ++i) Q.insert({dist[i], i});
    while ((int)Q.size() > 0) {
        auto p = (*Q.begin());
        if (p.first >= inf) break;
        if (p.second == n) {
            cout << p.first;
            return 0;
        }
        Q.erase(p);
        //cout << p.first << " " << p.second <<endl;
        while ((int)d.size() > 0) {
            auto t = (*d.begin());
            if (t.first > p.second) break;
            d.erase(t);
            if (dist[t.second] > p.first + gett[t]) {
                Q.erase({dist[t.second], t.second});
                dist[t.second] = p.first + gett[t];
                Q.insert({dist[t.second], t.second});
            }
        }
    }
    cout << -1 << '\n';
    return 0;
}



Measured memory_bytes: 19328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll H,W;
	cin>>H>>W;
	if(H>W) swap(H,W);
	if(H==1 || W==1){
		cout<<1;
		return 0;
	}
	ll row1=(H+1)/2;
	ll row2=H/2;
	ll res=0;
	res+=(W+1)/2*row1+W/2*row2;
	cout<<res;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;int sum=0;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    sum+=a[i];
  }
    int p;
  cin>>p;
  vector<pair<int,int>> m;
  for(int i=0;i<p;i++)
  {
    int x,y;
    cin>>x>>y;
    m.push_back({x,y});
  }
  for(auto it=m.begin();it!=m.end();it++)
  {
    cout<<sum-a[it->first-1]+it->second<<"\n";
  }
}

Measured memory_bytes: 256
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    dic = {}
    for i in range(n):
        # 文字列をソートすると、list化しちゃう~~~
        # から"".join(list)で結合させてあげるのだよ
        s = "".join(sorted(input()))
        if s in dic:
            dic[s] += 1
        else:
            dic[s] = 1
    ans = 0
    for k,v in dic.items():
        ans += (v * (v-1))//2
    print(ans)
if __name__ == '__main__':
  main()


Measured memory_bytes: 17852
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;


const int MAX = 100005;


int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	for (int i = 0; i < n; i++) {
		s[i] += s[i];

	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		bool isGood = true;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (j == k) {
					continue;
				}

				isGood = isGood && (s[j][i + k] == s[k][i + j]);
			}
		}

		if (isGood) {
			ans += n;
		}
	}
	cout << ans << endl;
}

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

char str[14];
int p[9], num;
int stack[9], top;

void init() {
  int i;
  for (i = 0; i < 9; i++) p[i] = 0;
  for (i = 0; i < 13; i++) p[str[i] - '1']++;
  top = 0;
}

void calc(int n) {
  if (n < 14 && num > 0) {
    int i;
    for (i = 0; i < 9; i++) {
      if (i < 7 && p[i] && p[i + 1] && p[i + 2]) {
        p[i]--; p[i + 1]--; p[i + 2]--;
        calc(n + 3);
        p[i]++; p[i + 1]++; p[i + 2]++;
      }
      if (p[i] >= 3) {
        p[i] -= 3;
        calc(n + 3);
        p[i] += 3;
      }
    }
  } else {
    if (num < 0) return;
    stack[top++] = num;
    num = -1;
  }
}

void calc0(int n) {
  int i;
  for (i = 0; i < 9 && num > 0; i++) {
    if (p[i] >= 2) {
      p[i] -= 2;
      calc(n + 2);
      p[i] += 2;
    }
  }
}

void solve() {
  int i;
  for (i = 0; i < 9; i++) {
    if (p[i] == 4) continue;
    num = i + 1;
    p[i]++;
    calc0(0);
    p[i]--;
  }
}

void printResult() {
  int i;
  for (i = 0; i < top; i++) {
    printf(i ? " %d" : "%d", stack[i]);
  }
  puts(top ? "" : "0");
}

int main() {
  while (~scanf("%s\n", str)) {
    int i;
    init();
    solve();
    printResult();
  }
  return 0;
}

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

int main() {
  int N, l, r;
  cin >> N;
  int sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> l >> r;
    sum += r - l + 1;
  }
  cout << sum << 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<int, int> P;

ll mod = 1000000007;
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
long long modinv(long long a) {
    return modpow(a, mod - 2);
}

int main() {
    int N, M; cin >> N >> M;
    map<int, int> m;
    for (int i = 2; i*i <= M; i++){
        while(M%i == 0){
            m[i]++;
            M /= i;
        }
    }
    if(M != 1)m[M]++;

    ll ans = 1;


    for(auto p : m){
        ll value = p.second;
        for (int i = N-1+value; i > value; i--){
            ans *= i;
            ans %= mod;
        }

        for (ll i = N-1; i > 1; i--){
            ll x = modinv(i);
            ans *= x;
            ans %= mod;
        }

        /*for (ll i = value; i > 1; i--){
            ll x = modinv(i);
            ans *= x;
            ans %= mod;
        }

        cout << ans << endl;
        */
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3616
package main

import (
  "fmt"
)

func main() {
  var p, sum, maxSurplus int
  for i := 0; i < 5; i++ {
    fmt.Scan(&p)
    sum += p
    if surplus := 10 - p%10; surplus != 10 {
      if maxSurplus < surplus {
        maxSurplus = surplus
      }
      sum += surplus
    }
  }
  fmt.Println(sum - maxSurplus)
}


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

typedef long long ll;

vector<ll> v[27];
string s, t;

int main(void)
{
	ll i, nxt = 0, it, cnt = 0;

	cin >> s >> t;

	for (i = 0; i < s.size(); i++)
		v[s[i] - 'a'].push_back(i);

	for (i = 0; i < t.size(); i++)
	{
		ll sh = t[i] - 'a';

		if (v[sh].empty())
		{
			cout << -1;
			return 0;
		}

		it = lower_bound(v[sh].begin(), v[sh].end(), nxt) - v[sh].begin();
		if (it == v[sh].size())
		{
			++cnt;
			nxt = v[sh][0] + 1;
		}
		else
			nxt = v[sh][it] + 1;
	}

	cout << cnt * (ll)s.size() + nxt;
	return 0;
}


Measured memory_bytes: 1724
use std::io::{ stdin, stdout, Write, BufRead };

fn main() {
  let mut s = Vec::with_capacity(7);
  let mut t = Vec::with_capacity(7);

  {
    let stdin = stdin();
    let mut reader = stdin.lock();
    let len = reader.read_until(b'\n', &mut s).unwrap() - 1;
    s.truncate(len);
    let len = reader.read_until(b'\n', &mut t).unwrap() - 1;
    t.truncate(len);
  }

  let mut s2t = [0; 27];
  let mut t2s = [0; 27];

  let mut i = 0;
  while i < t.len() {
    let c1 = (s[i] - 0x60) as usize;
    let c2 = (t[i] - 0x60) as usize;

    if s2t[c2] == 0 {
      s2t[c2] = c1;
    }
    if t2s[c1] == 0 {
      t2s[c1] = c2;
    }

    if s2t[c2] != c1 || t2s[c1] != c2 {
      let stdout = stdout();
      let mut writer = stdout.lock();
      writer.write(b"No\n").unwrap();
      writer.flush().unwrap();
      return;
    }

    i += 1;
  }

  let stdout = stdout();
  let mut writer = stdout.lock();
  writer.write(b"Yes\n").unwrap();
  writer.flush().unwrap();
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std; 
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ll long long
long long min(long long x,long long y){return (x<y ? x:y);}
long long max(long long x,long long y){return (x>y ? x:y);}
#define ld long double
int stoi(string s) {return atoi(s.c_str());}
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
#define LINEY "YES\n"
#define Liney "Yes\n"
#define LINEN "NO\n"
#define Linen "No\n"

void func(ll* x,ll* y){
  *x -= (*x%2);
  *x /= 2;
  *y += *x;
}

int main(){
  ll A,B;
  int K;
  cin >> A>>B>>K;
  bool turn_A = true;
  REP(i,K){
    if(turn_A){func(&A,&B);}
    else{func(&B,&A);}
    turn_A = !turn_A;
  }
  printf("%d %d\n",A,B);
}

Measured memory_bytes: 256
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return


def main():
    N, D = map(int,input().split())
    if (D==1):
        print(0)
        exit()
    D-=N
    ans = 1
    while(D>0):
        ans +=1
        D -= N-1
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

#include <vector>
using namespace std;
using i64 = long long;

struct WeightedUnionFind {
  vector<int> par;
  vector<i64> ws;

  WeightedUnionFind(int n) : par(n, 0), ws(n, 0) {
    for (int i = 0; i < n; i++) {
      par[i] = -1;
    }
  }

  int find(int x) {
    if (par[x] < 0) {
      return x;
    } else {
      const int parent = find(par[x]);
      ws[x] += ws[par[x]];
      return par[x] = parent;
    }
  }

  int weight(int x) {
    find(x);
    return ws[x];
  }

  bool unite(int x, int y, int w)  // x + w = y
  {
    w += weight(x);
    w -= weight(y);
    x = find(x);
    y = find(y);

    if (x != y) {
      if (par[y] < par[x]) {
        swap(x, y);
        w = -w;
      }
      par[x] += par[y];
      par[y] = x;
      ws[y] = w;
      return true;
    } else {
      return false;
    }
  }

  bool same(int x, int y) { return find(x) == find(y); }

  pair<bool, int> diff(int x, int y) {
    if (!same(x, y)) return {false, 0};
    return {true, weight(x) - weight(y)};
  }
};

int N;
int M;

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

  WeightedUnionFind uf(N);
  
  rep(i,0,M - 1){
    int l,r,d;
    cin >> l >> r >> d;
    l--;
    r--;
    auto p = uf.diff(r,l);
    if(!p.first){
      uf.unite(l,r,d);
    }
    else if(p.second != d){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
}


Measured memory_bytes: 1408
/**

author:	©LoneWolfDON
Git: MahinHossainMunna

**/
/*

*/
#include <stdio.h>
int main()
{
    int n;
    scanf("%d",&n);

    long long ans=0;

    for(int i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
            ans+=i;
    }
    printf("%lld\n",ans);

    return 0;
}



Measured memory_bytes: 1720
#include<stdio.h>
#include<stdlib.h>
int main(){
    int N=0;
    int sum=0;
    int i=0;
    int tmp;

    scanf("%d",&N);

    for(int j=1;j<=N;j++){
        tmp=j;
        while(tmp>0){
            tmp/=10;
            i++;
        }
        if(i%2!=0){
            sum++;
        }
        i=0;
    }
printf("%d\n",sum);
return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int dp[3009][3009];
string s,x;
int main()
{
    cin>>s>>x;
    for(int i=1;i<=s.size();i++)
    {
        for(int j=1;j<=x.size();j++)
        {
            if(s[i-1]==x[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            dp[i][j]=max(dp[i-1][j],max(dp[i][j-1],dp[i][j]));
        }
    }
    string ans="";
    int i=s.size(),j=x.size();
    while(dp[i][j])
    {
        if(dp[i][j]>dp[i-1][j]&&dp[i][j]>dp[i][j-1])
        {
            ans+=s[i-1];
            i--;
            j--;
        }
        else if(dp[i][j]==dp[i-1][j])
        {
            i--;
        }
        else j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;

}


Measured memory_bytes: 35584
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = new int[M];
		int s=0;
		for(int i=0; i<M; i++) {
			A[i] = sc.nextInt();
			s+=A[i];
		}
		if(s>N) {
			System.out.println(-1);
		}else {
			System.out.println(N-s);
		}
	}

}

Measured memory_bytes: 46376
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> n;
  rep(i, n) {
    cin >> s;
    if (s == "AC") a++;
    if (s == "WA") b++;
    if (s == "TLE") c++;
    if (s == "RE") d++;
  }
  cout << "AC x " << a << "\n";
  cout << "WA x " << b << "\n";
  cout << "TLE x " << c << "\n";
  cout << "RE x " << d << "\n";
  return 0;
}

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

int main(void)
{
    int i,len;
    char a[1000];
    char b[1000] = "";
    char c[1000] = "x";
    scanf("%s",a);
  	len = strlen(a);
    for(i=0;i<len;i++)
    {
        strcat(b,c);
    }
    printf("%s",b);
}

Measured memory_bytes: 128
#include <iostream>

int main()
{
  int n;
  double number[100];
  std::cin >> n;
  for (int i=0; i < n; ++i){
    std::cin >> number[i];
  }
  double x = 0.0;

  for (int i=0; i < n; ++i){
    x += 1.0 / number[i];
  }

  x = 1.0 / x;

  printf("%f8", x);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PI;
PI a[5];

int main()
{
    LL q,h,s,d;
    LL n;
    cin >> q >> h >> s >> d;
    a[1] = {q * 4, 1};
    a[2] = {h * 2, 1};
    a[3] = {s, 1};
    a[4] = {d / 2, 2};
    sort(a + 1, a + 5);
    cin >> n;
    LL ans = 0;
    for(int i = 1; i <= 4; i++)
    {
        while(n - a[i].second >= 0)
        {
            if(a[i].second == 2)
            ans += d * (n / a[i].second);
            else
            ans += a[i].first * (n / a[i].second);
            n = n % a[i].second;
        }
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define ll1 1ll
#define ONE 1ll
#define DBG 1
#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 loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T> void printvv(const vector<vector<T>> &v) {
  cerr << endl;
  rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
    if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
      cerr << "INF";
    } else
      cerr << v[i][j];
    cerr << (j == v[i].size() - 1 ? '\n' : ' ');
  }
  cerr << endl;
}
/*
   typedef __int128_t Int;
   std::ostream &operator<<(std::ostream &dest, __int128_t value) {
   std::ostream::sentry s(dest);
   if (s) {
   __uint128_t tmp = value < 0 ? -value : value;
   char buffer[128];
   char *d = std::end(buffer);
   do {
   --d;
 *d = "0123456789"[tmp % 10];
 tmp /= 10;
 } while (tmp != 0);
 if (value < 0) {
 --d;
 *d = '-';
 }
 int len = std::end(buffer) - d;
 if (dest.rdbuf()->sputn(d, len) != len) {
 dest.setstate(std::ios_base::badbit);
 }
 }
 return dest;
 }

 __int128 parse(string &s) {
 __int128 ret = 0;
 for (int i = 0; i < s.length(); i++)
 if ('0' <= s[i] && s[i] <= '9')
 ret = 10 * ret + s[i] - '0';
 return ret;
 }
 */

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

signed main(signed argc, char *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int a, b, c;
  cin >> a >> b >> c;
  if (a + b >= c) {
    cout << b + c << endl;
  } else {
    cout << b + c - (c - a - b)+1 << endl;
  }

  return 0;
}


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

int main() {
    string S;
    cin >> S;
    bool is_hitachi = false;
    if (S.size() % 2 == 0) {
        is_hitachi = true;
        for (int i = 0; i < S.size(); i += 2) {
            if (S[i] != 'h' || S[i+1] != 'i') is_hitachi = false;
        }
    }
    if (is_hitachi) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

ll goukei[100];//n桁までの57577の個数
ll kakuketa[100];//最上位を固定したときの個数

string fixit(int keta,int n1,ll n)
{
	string ret="";
	int n2=-1;
	//cerr<<kakuketa[keta]<<endl;
	//今見ている最上位から2番目の数を確定する
	for(int i=0;i<10;i++)
	{
		//cerr<<i<<" "<<n<<endl;
		if(i==n1)
		{
			if(n<kakuketa[keta])
			{
				n2=n1;
				break;
			}else{
				n-=kakuketa[keta];
			}
		}else{
			if(n<(1LL<<(keta-1LL)))
			{
				n2=i;
				break;
			}else
				n-=(1LL<<(keta-1LL));
		}
	}
	//cerr<<n2<<endl;
	keta--;
	//3桁目以降
	if(n1!=n2)
	{
		ret+=(char)(n2+'0');
		//cerr<<keta<<endl;
		for(ll i=keta;i>0;i--)
		{
			ll tmp=(n&(1LL<<(i-1)));
			if(tmp>0LL)
				ret+=(char)(max(n1,n2)+'0');
			else
				ret+=(char)(min(n1,n2)+'0');
		}
		return ret;
	}else{
		ret+=(char)(n1+'0');
		return ret+fixit(keta,n2,n);
	}
}

int main()
{
	goukei[0]=0;
	goukei[1]=0;
	kakuketa[0]=0;
	kakuketa[1]=0;
	for(int i=2;i<100;i++)
	{
		kakuketa[i]=9LL*((1LL<<((ll)i-1LL))-1LL);
		goukei[i]=goukei[i-1]+kakuketa[i]*9LL;
	}

	while(1)
	{
		long long nin;
		cin>>nin;
		ll n=nin;
		if(n==0)
			break;
		//nが何桁の数か
		n--;
		int nketa=0;
		for(int i=0;i<100;i++)
		{
			if(n<goukei[i])
			{
				nketa=i;
				n-=goukei[i-1];//余計な桁の数を引く
				break;
			}
		}
		int n1=n/kakuketa[nketa]+1;//nの最上位の数を確定する
		n%=kakuketa[nketa];
		if(n<0)
			n+=kakuketa[nketa];
		//cout<<nketa<<" "<<n1<<" "<<n<<endl;//for debug
		string ans="";
		ans+=(char)(n1+'0');
		ans+=fixit(nketa-1,n1,n);
		cout<<ans<<endl;
	}
	return 0;
}


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

int main(){
	int n;
	while( scanf(" %d", &n) != EOF){
		long ans=2;	
		for(int i=1; i<n; ++i) ans+=i+1;
		printf("%ld\n", ans);
	}
	return 0;
}

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

const int N = 1e6 + 10;

int main() {
	string s;
	cin >> s;
	int n = int(s.size());
	long long int c = 0;

	long long int ans = 0 ;
	for(int i = 0 ; i < n - 1 ; i ++ ) {
		if(s[i] == 'A') c++;
		else
		if(s[i] == 'B' && s[i + 1] == 'C') {
			ans += c;
			i++;
		} else c = 0;
	}
	cout << ans;
}


Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

vector<ll> build_z(const vector<ll>& s) {
  ll n = s.size();
  vector<ll> z(n, 0);
  ll l = -1, r = -1;
  for (ll i = 1; i < n; ++i) {
    if (i <= r) {
      z[i] = min<ll>(r - i + 1, z[i - l]);
    }
    while (i + z[i] < n && s[i + z[i]] == s[z[i]]) {
      ++z[i];
    }
    if (i + z[i] - 1 > r) {
      r = i + z[i] - 1;
      l = i;
    }
  }
  return z;
}


vector<ll> f(const vector<ll>& x) {
  ll n = x.size();
  vector<ll> res(n);
  rep(i,n) {
    res[i] = x[i]^x[(i+1)%n];
  }
  return res;
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  rep(i,n) {
    cin >> a[i];
  }
  rep(i,n) {
    cin >> b[i];
  }
  vector<ll> xa = f(a);
  vector<ll> xb = f(b);

  vector<ll> t = xb;
  t.push_back(-1);
  t.insert(t.end(), all(xa));
  t.insert(t.end(), all(xa));
  // printvec(t);

  vector<ll> z = build_z(t);
  rep(k,n) {
    if (z[n+1+k] == n) { // ok
      ll x = a[k]^b[0];
      cout << k << " " << x << endl;
    }
  }
}


Measured memory_bytes: 19088
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#define SIZE 105

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int A[SIZE];

int main()
{
	int K,n;
	scanf("%d %d",&K,&n);
	int mx=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		mx=max(mx,A[i]);
	}
	printf("%d\n",max(0,(mx-1)-(K-mx)));
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>

using namespace std;

int n, k;

void solve() {
  double prob = 0.0;
  for (int i=1;i<=n;i++) {
    int score = i;
    double tmp = 1;
    while (score < k) {
      score *= 2;
      tmp *= 0.5;
    }
    prob += 1.0 / n * tmp;
  }
  cout << setprecision(10) << prob << endl;
}

int main() {
  cin >> n >> k;
  solve();
}


Measured memory_bytes: 256
p=[0]*42
q=[0]*42
x=1
a,b=map(int,input().split())
if a==b:
    print(a)
    exit()

a-=1
for i in range(42):
    if b//x<1: break
    if x==1:
        q[0]=((b+1)//2)%2
    else:
        q[i]=[0,((b+1)%x)%2][(b//x)%2]
    x*=2
x=1
for i in range(42):
    if a//x<1: break
    if x==1:
        p[0]=((a+1)//2)%2
    else:
        p[i]=[0,((a+1)%x)%2][(a//x)%2]
    x*=2
x=1
ans=0
for i in range(42):
    ans+=(p[i]^q[i])*x
    x*=2
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main(){
//	int a,b,c,d,e,limit;
//	int i,j,k,l,total;
//	double temp=-1;
//	int temptt=0;
//	int tempyy=0;

	int H;
	int W;
	char C;
	int i,j;


	while(cin>>H>>W){
		int a[26]={0};
		int qishu=0;
		int liang=0;
		int liang_temp=0;
		
		for(i=0;i<H*W;i++){
			cin>>C;
			
			a[C-'a']++;
		}
		
		
		for(i=0;i<26;i++){
			
			if(a[i]&1){
				a[i]--;
				qishu++;
			}
			
			if(a[i]%4==2)
				liang++;
		}
//			cout<<qishu<<endl;
			int temp=(H*W)&1;
//			cout<<temp<<endl;

		if(temp !=qishu){
//			cout<<qishu<<endl;
			cout<<"No"<<endl;
		}else{
			if(H%2)
			   liang_temp+=W/2;
			if(W%2)
			   liang_temp+=H/2;
			if(liang>liang_temp)
			cout<<"No"<<endl;
			else
			cout<<"Yes"<<endl;
		}		
	} 

	return 0;
}

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

#define double long double
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define eb emplace_back
//#define ll long long
#define int long long
using namespace std;

const int INF = 2e9;
const int MOD = 1e9 + 7;
const int MB = 20;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	int ans = INF;
	for (int x = 1; x <= 100; x++) {
		int res = 0; 
		for (int i = 0; i < n; i++) {
			res += (a[i] - x) * (a[i] - x);
		}
		ans = min(res, ans);
	}
	
	cout << ans;
}

signed main() {
	/*
	freopen("caves.in", "r", stdin);
	freopen("caves.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout.precision(12);
	solve();
}

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

#define INF ((1LL <<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

#define LIMIT_SEC 1.98

class Timer {
    chrono::high_resolution_clock::time_point start;
public:
    double limit;
    Timer() {
        start = chrono::high_resolution_clock::now();
        limit = LIMIT_SEC;
    }
    Timer(double limit) :limit(limit) {
        start = chrono::high_resolution_clock::now();
    }
    double get_time() {
        return chrono::duration<double>(chrono::high_resolution_clock::now() - start).count();
    }
    bool time_over() {
        if (get_time() > limit) {
            return true;
        }
        return false;
    }
    void set_start() {
        start = chrono::high_resolution_clock::now();
    }
    double get_limit() {
        return limit;
    }
};

Timer timer;

// 乱数器
class XorShift {
public:
    unsigned long x, y, z, w;
    XorShift() {
        x = 123456789; y = 362436069; z = 521288629; w = 88675123;
    }
    XorShift(unsigned long seed) {
        XorShift();
        w = seed;
        for (int i = 0; i < 100; ++i) (*this)();
    }
    unsigned long operator()() {
        unsigned long t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
};

XorShift rnd;

ll c[27];
ll s[366][27];

const int C = 26;

ll bestScore = 0;
ll ans[365], lc[C];


ll getScore() {
    ll ret = 0;
    for (int d = 0; d < 365; ++d) {
        ret += s[d][ans[d]];
        lc[ans[d]] = d+1;
        rep(i, C) {
            ret -= c[i] * ((d+1) - lc[i]);
        }
        return max(ret, 0LL);
    }
}

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

    int D;
    cin >> D;
    rep(i, C) cin >> c[i];
    rep(i, D) rep(j, C) cin >> s[i][j];


    ll tmp = getScore();
    //cout << "Best Score = " << tmp << endl;

    rep(i, D) cout << ans[i]+1 << endl;


}


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

int main(){
  int N;
  string S;
  cin >> N >> S;
  
  if( N % 2 == 1 ){
    cout << "No" << endl;
  }else {
    string sub_str = S.substr( N/2 );
    if( sub_str == S.erase( N/2 ) ){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define rg register
#define ll long long
#define LDB long double
#define ull unsigned long long
#define view(i,x) for(rg int i=hd[x];i!=-1;i=e[i].nt)
#define go(i,x,a) for(rg int i=a;i<x;i++)
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
using namespace std;

const int maxn=10;
int n,m,mp[maxn][maxn];
char s[maxn];

inline int rd(){
	int ret=0,af=1; char gc=getchar();
	while(gc < '0' || gc > '9'){ if(gc=='-') af=-af; gc=getchar(); }
	while(gc >= '0' && gc <= '9') ret=ret*10+gc-'0',gc=getchar();
	return ret*af;
}

int main(){
	#ifndef ONLINE_JUDGE
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	#endif
	n=rd(); m=rd();
	go(i,n+1,1){
		scanf("%s",s+1);
		go(j,m+1,1) mp[i][j]=s[j]=='#';
	}
	go(i,n+1,1) go(j,m+1,1)
		if(mp[i][j]){
			go(x,i,1) go(y,m+1,j+1)
			if(mp[x][y]){
				puts("Impossible");
				return 0;
			}
		}
	puts("Possible");
	return 0;
}//Faze


Measured memory_bytes: 256
N,M=map(int,input().split())
A = list(map(int,input().split()))
bc = []

for i in range(N):
  bc.append( [1, A[i]])

for i in range(M):
  bc.append(list(map(int,input().split())))
bc = sorted( bc, key=lambda ii:ii[1], reverse=True)
p = []
tmp=0
for i in range(N):
  if bc[tmp][0] == 0:
    tmp +=1
  p.append( bc[tmp][1] )
  bc[tmp][0] -= 1
print( sum(p) )


Measured memory_bytes: 47064
import math

def burger_size(n):
    return 2**(n + 2) - 3

def num_of_patty(n):
    return 2**(n + 1) - 1

def calc(n, x):
    if n == 0:
        return 1
    if x <= n:
        return 0
    if x == burger_size(n):
        return num_of_patty(n)
    
    center = math.floor((burger_size(n) + 1) / 2)
    if x < center:
        return calc(n - 1, x - 1)
    elif x > center:
        return num_of_patty(n - 1) + 1 + calc(n - 1, x - burger_size(n - 1) - 2)
    else:
        return num_of_patty(n - 1) + 1

n, x = [int(i) for i in input().split()]
print(calc(n, x))

Measured memory_bytes: 3064
#include<iostream>
#include <string>
#include<stdio.h>

using namespace std;


int main() {

	
		int n, q, C = 0;
		long long int S[10000], T[500], check[500] = { 0 };
		cin >> n;
		for (int i = 0; i < n; i++) cin >> S[i];

		cin >> q;
		for (int i = 0; i < q; i++) cin >> T[i];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < q; j++) {
				if (S[i] == T[j] && check[j] == 0) {
					C++;
					check[j] = 1;
				}
			}
		}
		cout << C << endl;

		return 0;
	}

	







Measured memory_bytes: 3160
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var ar = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var q = ToInt32(ReadLine());
        var ar2 = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var set = new HashSet<int>();
        for(var i = 1; i < Pow(2, num); i++)
        {
            var sum = 0;
            for(var j = 0; j < num; j++)
            {
                if (((i >> j) & 1) == 1)
                    sum += ar[j];
            }
            set.Add(sum);
        }
        ar2.ToList().ForEach(v => WriteLine(set.Contains(v) ? "yes" : "no"));
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


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

using namespace std;

//FILE *fi=freopen("1.txt","r",stdin);

int n,dem=0;

void process()
{
    for (int i=1;i<=n/2;++i)
    {
        if (i!=n-i) dem++;
    }
    cout<<dem;
}

int main()
{
    scanf("%d",&n);
    process();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a<b){
  int tmp=a;
  a=b;
  b=tmp;
  }
  if(a<c){
  int tmp=a;
  a=c;
  c=tmp;
  }
   cout << a*10 + b + c;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define MOD 1000000007
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main() {
    char s[10];
    cin >> s;
    if (s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I') {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 256
// ABC049C - Daydream
package main

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

func Reverse(s string) []rune {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}
func canMakeT(sRuneR []rune) bool {
	i := 0
	for i < len(sRuneR) {
		if i+5 > len(sRuneR) {
			return false
		}
		if string(sRuneR[i:i+5]) == "esare" ||
			string(sRuneR[i:i+5]) == "maerd" {
			i += 5
			continue
		}

		if i+6 > len(sRuneR) {
			return false
		}
		if string(sRuneR[i:i+6]) == "resare" {
			i += 6
			continue
		}
		if i+7 > len(sRuneR) {
			return false
		}
		if string(sRuneR[i:i+7]) == "remaerd" {
			i += 7
			continue
		}
		return false
	}
	return true
}

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}
func main() {
	//
	//sc := bufio.NewScanner(os.Stdin)
	//sc.Scan()
	//s = sc.Text()
	//fmt.Scan(&s)
	s := readLine()
	sRuneR := Reverse(s)
	if canMakeT(sRuneR) {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 1408
//==========================================
// ABC141b
//
// 2019/09/15
//==========================================

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>

using namespace std;

int main(int argc, char* argv[])
{
  string s;
  cin >> s;

  bool j=true;
  for(int i=0; i< s.length(); ++i)
  {
    if(i%2==0)
    {
      if(s[i]=='L') j=false;
    }
    else
    {
      if(s[i]=='R') j=false;
    }
  }
  if(j) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
vector <int> E[5050];
int down[5050];
const int MOD = 1e9 + 7;

void pdfs(int x, int fa) {
	down[x] = 1;
	for(int e : E[x]) if(e != fa) {
		pdfs(e, x);
		down[x] += down[e];
	}
}

int C[5050][5050], F[5050];
int D[5050][5050], temp2[5050];

int Get(vector <int> L) {
	int n = szz(L);
	for(int i=1;i<=n;i++) {
		int ai = L[i-1];
		D[i][0] = 1;
		for(int j=1;j<=ai;j++) D[i][j] = (ll) D[i][j-1] * (ai - j + 1) % MOD;
		for(int j=0;j<=ai;j++) D[i][j] = D[i][j] * (ll) C[ai][j] % MOD;
	}
	int s = L[0];
	for(int i=2;i<=n;i++) {
		int ai = L[i-1];
		for(int j=0;j<=s+ai;j++) temp2[j] = 0;
		for(int j=0;j<=s;j++) {
			for(int k=0;k<=ai;k++) {
				temp2[j+k] = (temp2[j+k] + (ll) D[i-1][j] * D[i][k]) % MOD;
			}
		}
		for(int j=0;j<=s+ai;j++) D[i][j] = temp2[j];
		s += ai;
	}
	int ans = 0;
	for(int i=0;i<=s;i++) {
		ll v = F[s-i] * (ll)D[n][i] % MOD;
		if(i & 1) ans = (ans - v + MOD) % MOD;
		else ans = (ans + v) % MOD;
	}
	return ans;
}

void solve() {
	F[0] = 1;
	for(int i=0;i<5050;i++) {
		C[i][0] = 1;
		if(i) F[i] = (ll) i * F[i-1] % MOD;
		for(int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	scanf("%d", &n);
	rep(i, n-1) {
		int x, y; scanf("%d%d", &x, &y);
		E[x].pb(y);
		E[y].pb(x);
	}
	pdfs(1, -1);
	int h = n / 2, c = 1;
	while(1) {
		int f = 0;
		for(int e : E[c]) if(down[e] < down[c] && down[e] > h) {
			c = e; f = 1; break;
		}
		if(f == 0) break;
	}
	pdfs(c, -1);
	vector <int> A;
	for(int e : E[c]) A.pb(down[e]);
	ll ans = Get(A); A.pb(1);
	ans = (ans + Get(A)) % MOD;
	printf("%lld\n", ans);
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}




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

int main(){
  int N;
  cin>>N;
vector<int> data(N);
	for(int i=0;i<N;i++){
      int a;
      cin>>a;
      data[i]=a;
	}
  int count=0;
  map<int,int> data_set;
for(int i=0;i<N;i++){
  data_set[data[i]]++;
}
  cout<<data_set.size()<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using vll = vector<ll> ;
using vs = vector<string> ;
#define all(v) v.begin(),v.end()

int main(){
  ll A,B,N;cin>>A>>B>>N;
  ll tmp;
  ll ans1 = ll(N/B)*B-1;
  ll ans2 = 
  tmp = max(ll(A*N/B)-A*ll(N/B),ll(A*ans1/B)-A*ll(ans1/B));  
  tmp = max(0ll,tmp);
  tmp = max(tmp,ll(A/B)-A*ll(1/B));
  cout << tmp << endl;
}

Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                int n = int.Parse(Console.ReadLine());

                if (n == 0) break;

                int[,] dp = new int[n, n];
                int max = 0;

                string input = Console.ReadLine();

                for (int j = 0; j < n; j++)
                {
                    dp[0, j] = input[j] == '.' ? 1 : 0;
                }

                for (int i = 1; i < n; i++)
                {
                    input = Console.ReadLine();

                    for (int j = 0; j < n; j++)
                    {
                        if (input[j] == '*')
                        {
                            dp[i, j] = 0;
                        }
                        else
                        {
                            dp[i, j] = 1;

                            if (j == 0) continue;

                            dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]);
                            dp[i, j] = Math.Min(dp[i, j], dp[i - 1, j - 1]) + 1;
                            max = Math.Max(max, dp[i, j]);
                        }
                    }
                }
                Console.WriteLine(max);
            }
        }
    }
}

Measured memory_bytes: 22960
#include<iostream>
#include<algorithm>
#include<vector>
using LL = long long;
LL N,w;
LL W, V;
LL size[4],ww[4];
LL ans;
std::vector<LL> dp[4];
void value(LL x, LL y, LL z, LL q) {
	LL sum = 0;
	for (LL aa = 0; aa < x; aa++) {
		sum += dp[0][aa];
	}
	for (LL aa = 0; aa < y; aa++) {
		sum += dp[1][aa];
	}
	for (LL aa = 0; aa < z; aa++) {
		sum += dp[2][aa];
	}
	for (LL aa = 0; aa < q; aa++) {
		sum += dp[3][aa];
	}
	ans = std::max(ans, sum);
	sum = 0;
}
void solve() {
	for (LL i = 0; i <= size[0]; i++) {
		for (LL j = 0; j <= size[1]; j++) {
			for (LL k = 0; k <= size[2]; k++) {
				for (LL l = 0; l <= size[3]; l++) {
					ww[0] = i*w;
					ww[1] = j*(w + 1);
					ww[2] = k*(w + 2);
					ww[3] = l*(w + 3);
					if ((ww[0] + ww[1] + ww[2] + ww[3]) <= W) {
						value(i, j, k, l);
					}
				}
			}
		}
	}
}
int main() {
	std::cin >> N >> W;
	std::cin >> w>> V;
	dp[0].push_back(V);
	for (LL i = 1; i < N; i++) {
		LL tmp,Q;
		std::cin >> tmp >> Q;
		dp[tmp-w].push_back(Q);
	}
	for (LL i = 0;  i < 4; i++) {
		std::sort(dp[i].rbegin(), dp[i].rend());
		size[i] = dp[i].size();
	}
	solve();
	std::cout << ans << std::endl;
	return 0;
}
 


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;

struct data {
	int first, second, id;
	data(int _f, int _s, int _id) : first(_f), second(_s), id(_id) {}
};

const int N = (int)1e5+5;
int n, m, len, a[N], dp[18][N];

int query(int u, int steps) {
	int ret = u;
	for (int i = 0; i < 20; ++i) if ((steps >> i) & 1)
		ret = dp[i][ret];
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", a + i);
	scanf("%d%d", &len, &m);
	for (int i = 0; i < 18; ++i) fill(dp[i] + 1, dp[i] + n + 1, n + 5);
	for (int i = n, j = n; i >= 1; --i) {
		while (j >= 1 && a[j] - a[i] > len) --j;
		dp[0][i] = j;
	}
	for (int i = 1; i <= 17; ++i)
		for (int j = 1; j <= n; ++j)
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		if (u > v) swap(u, v);
		int lo = 1, hi = n, ans = -1, mid;
		while (lo <= hi) {
			mid = (lo + hi) >> 1;
			if (query(u, mid) >= v) ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

const int Nmax=200010;

int main() {
	char c[2][3];
	for(int i=0;i < 2;i++)
		for(int j=0;j < 3;j++)
			cin >> c[i][j];
	
	if(c[0][0]==c[1][2]&&c[0][1]==c[1][1]&&c[0][2]==c[1][0])
		cout << "YES" << endl;
	else cout << "NO" << endl;
	
	return 0;
}

Measured memory_bytes: 256
//satyaki3794
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


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


int n, A, B, c, d;
ll fac[1002], DP[1005][1005], invFac[1003], ncr[1003][1004], powers[1002][1002];

ll dp(int rem, int g){

    if(rem == 0)    return 1;
    if(g == B+1)    return 0;
    ll &ans = DP[rem][g];
    if(ans != -1)   return ans;

    ans = dp(rem, g+1);
    for(int i=c*g;i<=rem&&i<=d*g;i+=g){
    
// if(!((rem==7&&g==2&&i==4) || (rem==3&&g==3&&i==3)))    continue;

        ll temp = ncr[rem][i];
        temp = (temp * fac[i]) % MOD;
        temp = (temp * invFac[i/g]) % MOD;
        temp = (temp * powers[g][i/g]) % MOD;

        if(i >= c*g)    ans = (ans + temp*dp(rem-i, g+1)) % MOD;
    }

// cout<<"dp "<<rem<<" "<<g<<" returns "<<ans<<endl;
    return ans;
}



int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fac[0] = invFac[0] = 1;
    for(int i=1;i<=1001;i++){
        fac[i] = (i * fac[i-1]) % MOD;
        invFac[i] = pwr(fac[i], MOD-2);
    }

    for(int i=1;i<=1001;i++){
        powers[i][0] = 1;
        for(int j=1;j<=1001;j++)
            powers[i][j] = (powers[i][j-1] * invFac[i]) % MOD;
    }

    ncr[0][0] = 1;
    for(int i=1;i<=1000;i++){
        ncr[i][0] = 1;
        for(int j=1;j<=i;j++)
            ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % MOD;
    }

    cin>>n>>A>>B>>c>>d;
    memset(DP, -1, sizeof(DP));
    cout<<dp(n, A);
    return 0;
}





Measured memory_bytes: 23040
const main = (input) => {
    input = input.split(" ");
    const X = Number(input[0]);
    const A = Number(input[1]);
    if (X < A) {
        console.log(0);
    } else {
        console.log(10);
    }
};

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

Measured memory_bytes: 21064
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>
#include <algorithm>
//#include <iomanip> : 表示桁数

#define pi 3.14159265358979323846
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
typedef unsigned char Byte;
using namespace std;

//string ans = "Yes";
string ans;
int N;
int main() {
	cin >> N;
	if (N % 10 == 3) {
		ans = "bon";
	} else if (N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8) {
		ans = "pon";
	} else {
		ans = "hon";
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3568