akhauriyash/Code-Regression huggingface dataset:
# ABC044
N, A = map(int, input().split())
X = list(map(int, input().split()))

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max(X) * (N+1)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

ans = 0
for k in range(1, N+1):
    if k * A > max_wa:
        break
    ans += dp[-1][k][k*A]

print(ans)


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

void solve(std::istream &ist, std::ostream &ost)
{
    /* ------- 宣言と入力 ------- */

    int N;
    ist >> N;

    vector<string> S;

    for (int i = 0; i < N; i++)
    {
        string input;
        ist >> input;
        S.emplace_back(input);
    }

    /* ------- 計算 ------- */

    unordered_map<string, int> C;

    C.insert(make_pair("AC", 0));
    C.insert(make_pair("WA", 0));
    C.insert(make_pair("TLE", 0));
    C.insert(make_pair("RE", 0));

    for (auto s : S)
    {
        C.at(s)++;
    }

    ost << "AC x " << C.at("AC") << endl;
    ost << "WA x " << C.at("WA") << endl;
    ost << "TLE x " << C.at("TLE") << endl;
    ost << "RE x " << C.at("RE") << endl;
}

#ifndef WOMAIN
int main()
{
    solve(std::cin, std::cout);
    return 0;
}
#endif


Measured memory_bytes: 7464
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>  // std::unique
#include <cmath>
using namespace std;

using ll = long long;
constexpr auto PrimeBigNum10_9_7 = 1000000007;

// 素数判定
template <typename T>
bool IsPrimeNumber(T value) {

	for (int i = 2; i * i <= value; ++i) {
		if ((value % i) == 0) {
			return true;
		}
	}
	return false;
}

// 桁数判定
template <typename T>
T GetFigureLength(T value) {
	T figure = 1;
	while (value >= 10) {
		value /= 10;
		++figure;
	}
	return figure;
}

// 素因数分解結果
template <typename T>
map<T, T> GetPrimeFactorize(T value) {

	map<T, T> res;

	for (T i = 2; i * i <= value; ++i) {
		if ((value%i) != 0)	continue;

		T count = 0;
		while ((value % i) == 0) {
			value /= i;
			++count;
		}

		res[i] = count;
	}

	if (value != 1) {
		res[value] = 1;
	}
	return res;
}

int main(void) {
	int n, k;
	cin >> n >> k;

	vector<int> list(n, 0);
	for (int i = 0; i < k; ++i) {
		int d;
		cin >> d;
		for (int j = 0; j < d; ++j) {
			int a;
			cin >> a;
			list[a-1]++;
		}
	}

	int count = 0;
	for (auto itr = list.begin(); itr != list.end(); ++itr) {
		if (*itr == 0) {
			count++;
		}
	}

	auto output = count;
	cout << output;

	return 0;
}

Measured memory_bytes: 3628
# coding: utf-8
# Your code here!

def pertision(A, l, r):
    pivot = A[r]
    i = 0
    for j in range(l, r):
        if A[j] <= pivot:
            A[l+i], A[j] = A[j], A[l+i]
            i += 1
    A[l+i], A[r] = A[r], A[l+i]      
    
    return l+i

N = int(input())
A = [int(i) for i in input().split()]

pivot_i = pertision(A, 0, N-1)

s = []
for i in range(N):
    if i == pivot_i:
        s.append('[{}]'.format(A[i]))
    else:
        s.append(str(A[i]))

print(*s)



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

void dfs(vector<int> graph[], int a, vector<bool>& vis, vector<int>& dp)
{
    vis[a] = true;
    for(auto i: graph[a])
    {
        if(!vis[i])
        {
            dfs(graph, i, vis, dp);
        }
        dp[a] = max(dp[a], 1 + dp[i]);
    }
}



int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> graph[n+1];
  for(int i=0;i<m;++i)
  {
      int x, y;
      cin >> x >> y;
      graph[x].push_back(y);
  }
  vector<int> dp(n+1, 0);
  int ans = 0;
  vector<bool> vis(n+1, false);
  
  for(int i=1;i<=n;++i)
  {
      if(!vis[i])
      {
          dfs(graph, i, vis, dp);
      }
  }
  cout << *max_element(dp.begin(), dp.end()) << endl;;
  
}

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

int main() {
  string s;
  cin >> s;
  ll odr=0,er=0;
  ll odl=0,el=0;
  vector<ll> ans(s.size());
  for(ll i=0;i<s.size();i++) {
    if(s[i]=='R') {
      if(i%2) {
        odr++;
      }
      else {
        er++;
      }
    }
    else {
      if(i%2) {
        ans[i]+=odr;
        ans[i-1]+=er;
      }
      else {
        ans[i]+=er;
        ans[i-1]+=odr;
      }
      er=0;
      odr=0;
    }
  }
  for(ll i=s.size()-1;i>-1;i--) {
    if(s[i]=='L') {
      if(i%2) {
        odl++;
      }
      else {
        el++;
      }
    }
    else {
      if(i%2) {
        ans[i]+=odl;
        ans[i+1]+=el;
      }
      else {
        ans[i]+=el;
        ans[i+1]+=odl;
      }
      el=0;
      odl=0;
    }
  }
  for(ll i=0;i<s.size();i++) {
    if(i!=0) {
      cout << " ";
    }
    cout << ans[i];
  }
  cout << endl;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int H = scanner.nextInt();
            int W = scanner.nextInt();
            if (H == 0 && W == 0) break;
            for (int h = 0; h < H; h++) {
                for (int w = 0; w < W; w++) {
                    System.out.print('#');
                }
                System.out.println("");
            }
            System.out.println("");
        }
    }
}



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

int main(int argc, char **argv)
{
	ll N; cin >> N;
	vector<ll> X(N); for (ll i = 0; i < N; ++i) cin >> X[i];

	ll res{1ll<<60};
	for (ll x = 1; x <= 100; ++x)
	{
		ll tmp{0};
		for (auto &e : X)
			tmp += pow(e-x, 2.0);
		res = min(res, tmp);
	}
	std::cout << res << std::endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int N,i,j=-1,Y,cnt=0;
    int m[1000];
  cin>>N;
    for(i=0;i<N;i++){cin>>m[i];}
    sort(m,m+N);
    for(i=0;i<N-1;i++){cnt+=m[i];}
    
    if(m[N-1]<cnt){cout<<"Yes\n";}
    else{cout<<"No\n";}
    
    

     
 
    
    
    

    }

Measured memory_bytes: 256
import Control.Monad
import Data.List

f :: [Int] -> [Int] -> Int
f [x] [y] = x - y
f tails@(x:xs) heads@(y:ys)
  | diff == 0 = 0
  | otherwise = min diff (f xs ys)
  where diff = x - y


main :: IO ()
main = do
  [all, number] <- map read . words <$> getLine
  heights <- replicateM all readLn
  let sorted = sort heights
  let heads = take (all - number + 1) sorted
  let tails = drop (number - 1) sorted
  print $ f tails heads

Measured memory_bytes: 65916
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll fastpowMOD(ll a, ll p,ll MOD);
ll fastpowMOD(ll a, ll p,ll MOD){ if(p==0) return 1; a %= MOD; ll z = fastpowMOD(a,p/2,MOD); z = (z*z)%MOD; if(p%2) z = (z*a)%MOD; return z; }

ll lcm(ll a,ll b){
	return (a*b)/__gcd(a,b);
}



int main(){
	fastio;
	ll h;
	cin>>h;
	ll t = 1;
	ll p = 1;
	while(h>1){
		t += 1LL<<p;
		p++;
		h /= 2;
	}
	
	cout<<t<<"\n";
	
	
}


















Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<(b); i++)
#define per(i,a,b) for (int i=(b)-1; i>=(a); i--)
#define debug(x) cout << #x << " => " << x << endl
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define mp make_pair
typedef pair<int,int> pii;

#define pb push_back
typedef vector<int> vi;

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAX_N = 7 + 400;
///----------------------------------------------
//int qpow(int

int col[10];
void rote() {
    int tmp[4]; rep(i,0,4) tmp[i]=col[i];
    rep(beg,1,4) {
        int i; for (i=0; i<3&&tmp[(beg+i)%4]==col[i]; ) i++;
        if(tmp[(beg+i)%4]<col[i]) {
            rep(i,0,4) col[i]=tmp[(beg+i)%4];
        }
    }
}

const int B[4]={1000000000, 1000000, 1000, 1};
ll getval() {
    rote();
    ll val=0;
    rep(i,0,4) val+=1ll*col[i]*B[i];
    return val;
}

bool same() {
    rep(i,1,4) if (col[i]!=col[0]) return false;
    return true;
}
bool same2() {
    return col[0]==col[2]&&col[1]==col[3];
}


map<ll,int> num;
int tab[MAX_N][4];
int main() {

    ///freopen ( "xx.in" , "r" , stdin );

    ///init
    ///read
    int n; cin>>n;
    rep(i,0,n) {
        rep(j,0,4) scanf("%d",&col[j]), tab[i][j]=col[j];
        num[getval()]++;
    }

    ///work
    ll ans=0;
    rep(i,0,n) {
        rep(j,0,4) col[j]=tab[i][j]; num[getval()]--;
        rep(j,i+1,n) {
            rep(k,0,4) col[k]=tab[j][k]; num[getval()]--;
            rep(off,0,4) {
                ll tmp=1;
                ///front
                col[0]=tab[i][1]; col[1]=tab[j][(off+0)%4];
                col[3]=tab[i][2]; col[2]=tab[j][(off+3)%4]; rote();
                ll val1 = getval();
                ll tmp1 = same() ? 4 : same2() ? 2 : 1;
                tmp=1ll*tmp*(num[val1]--)*tmp1;
                ///top
                col[0]=tab[i][0]; col[1]=tab[j][(off+1)%4];
                col[3]=tab[i][1]; col[2]=tab[j][(off+0)%4]; rote();
                ll val2 = getval();
                ll tmp2 = same() ? 4 : same2() ? 2 : 1;
                tmp=1ll*tmp*(num[val2]--)*tmp2;
                ///buttom
                col[0]=tab[i][2]; col[1]=tab[j][(off+3)%4];
                col[3]=tab[i][3]; col[2]=tab[j][(off+2)%4]; rote();
                ll val3 = getval();
                ll tmp3 = same() ? 4 : same2() ? 2 : 1;
                tmp=1ll*tmp*(num[val3]--)*tmp3;
                ///back
                col[0]=tab[i][3]; col[1]=tab[j][(off+2)%4];
                col[3]=tab[i][0]; col[2]=tab[j][(off+1)%4]; rote();
                ll val4 = getval();
                ll tmp4 = same() ? 4 : same2() ? 2 : 1;
                tmp=1ll*tmp*(num[val4]--)*tmp4;
                ans=ans+tmp;
                num[val1]++;
                num[val2]++;
                num[val3]++;
                num[val4]++;

            }
            rep(k,0,4) col[k]=tab[j][k]; rote(); num[getval()]++;
       }
    }

    ///print
    cout << ans << endl;




}













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

int main(){

	string s;
	cin>>s;
	bool bad=false;
	for(int i=0;i<3;i++){
		if(s[i]==s[i+1]){
			bad=true;
			break;
		}
	}
	if(bad){
		cout<<"Bad"<<endl;
	}
	else{
		cout<<"Good"<<endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

class Edge{
public:
    int to, cost;
    Edge(){}
    Edge(int to0, int cost0){
        to = to0;
        cost = cost0;
    }
};

vector<vector<Edge> > edges;
int maxPath;

int solve(int curr, int prev, int sum)
{
    maxPath = max(maxPath, sum);

    int ret = 0;
    for(unsigned i=0; i<edges[curr].size(); ++i){
        int to = edges[curr][i].to;
        int cost = edges[curr][i].cost;
        if(to == prev)
            continue;
        if(edges[to].size() == 1)
            continue;
        ret += cost * 2;
        ret += solve(to, curr, sum + cost);
    }
    return ret;
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        edges.assign(n, vector<Edge>(0));
        for(int i=0; i<n-1; ++i){
            int a, b, t;
            cin >> a >> b >> t;
            -- a;
            -- b;
            edges[a].push_back(Edge(b, t));
            edges[b].push_back(Edge(a, t));
        }

        maxPath = 0;
        int ret = solve(0, -1, 0);
        ret -= maxPath;
        cout << ret << endl;
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define whlie while
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repr(i,N) for(int i = (N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (N) ; i++)
#define repr1(i,N) for(int i = (N) ; i > 0 ; i--)
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define vrep(v,it) for(auto it = v.begin(); it != v.end(); it++)
#define vrepr(v,it) for(auto it = v.rbegin(); it != v.rend(); it++)
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
using namespace std; void solve();
using ll = long long; using vl = vector<ll>;
using vi = vector<int>; using vvi = vector< vector<int> >;
constexpr int inf = 1001001001;
constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
  #include "NyaanDebug.h"
  #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
  #define trca(v,...) do { cerr << #v << " = "; array_out(v , __VA_ARGS__ );} while(0)
#else
  #define trc(...)
  #define trca(...)
  int main(){solve();}
#endif
 
using P = pair<int,int>; using vp = vector<P>;
constexpr int MOD = /**/ 1000000007; //*/ 998244353;
/////////////////

void solve(){
  string S[3] = {"Sunny" , "Cloudy" , "Rainy"};
  ins(T);
  rep(i , 3){
    if(T == S[i]) cout << S[(i + 1) % 3] << endl;
  }
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++)
    cin >> vec[i];
  sort(vec.begin(), vec.end());
  int mi = 0, tmp = 0;

  for (int i = 0; i < n; i++)
    mi += ((vec[i] - vec[0]) * (vec[i] - vec[0]));
  for (int i = vec[0]; i <= vec[n-1]; i++)
  {
    tmp = 0;
    for (int j = 0; j < n; j++)
      tmp += ((vec[j] - i) * (vec[j] - i));
    mi = min(tmp, mi);
  }
  cout << mi << endl;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    long n = Integer.parseInt(sc.next());
    long d = Integer.parseInt(sc.next());
    long range = d * 2 + 1;
    long div = n / range;
    long ans;
    if (n % range == 0) {
      ans = div;
    } else {
      ans = div + 1;
    }
    pw.println(ans);
  }
}


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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int N;
    cin >> N;
    map<string, int> M;
    long long Ans = 0;
    while (N--) {
        string S;
        cin >> S;
        sort(S.begin(), S.end());
        Ans += M[S];
        M[S]++;
    }
    cout << Ans;
	return 0;
}


Measured memory_bytes: 11264
from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()

g = gcd(n,m)
l = n*m//g

n2,m2 = l//n,l//m
g2 = gcd(n2,m2)
l2 = n2*m2//g2

ans = l
for i in range(l//l2):
  if s[i*l2//n2] != t[i*l2//m2]:
    ans = -1
    break
print(ans)



Measured memory_bytes: 5336
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main ()
{
    ll i,j,n;
    vector<ll> s,t;
    cin>>n;
    for(i=0;i<n;i++)
    {
        ll q; cin>>q;
        s.push_back(q);
        t.push_back(q);
    }
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    if(s.size()==t.size())
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
    return 0;
}

Measured memory_bytes: 6644
#pragma GCC optimize("Ofast")   //Comment optimisations for an interatcive problem - use endl
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define  fastio         ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0);cout<<fixed;cout<<setprecision(10);
#define  randomINIT     mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define  foo(i,a,n)     for(ll i = (a); i <= n; i++)
#define  frr(i,a,n)     for(ll i = (a); i >= n; i--)
#define  fo(i,n)        for(ll i = 0; i < n; i++)
#define  all(x)         (x).begin(),(x).end()
#define  mset(x,val)    memset(x,val,sizeof(x))
#define  newl           cout<<"\n"
#define  pb             push_back
#define  mp             make_pair
#define  s              second
#define  f              first
#define  dline          cout<<"///REACHED///\n";
#define  deb1(x)        cout<<#x<<" = "<<x<<'\n';
#define  deb2(x,y)      cout<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define  deb3(x,y,z)    cout<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef  long long             ll;
typedef  long double           ld;
typedef  pair<ll,ll>           pll;
typedef  vector<ll>            vll;
typedef  unordered_map<ll,ll>  um;
typedef  vector<pll>           vpll;

const ll   MOD   =  1e+9+7;
const ll   INF   =  0x7f7f7f7f7f7f7f7f;
const int  INFi  =  0x7f7f7f7f;
const ll   MAXN  =  1e+5+7;

vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};

//<<-----Declare Variable Here------->>//
int qq;
ll n;
string s;
//<<-----Implement Functions Here---->>//


//<<-----Start of Main--------------->>//

int main(){
	fastio;randomINIT;

	cin>>n>>s;

	if(s==(s.substr(0,n/2)+s.substr(0,n/2)))cout<<"Yes";
	else cout<<"No";

}

Measured memory_bytes: 2560
import sys
input = sys.stdin.readline

N = int(input())
A = [0]*N
B = [0]*N
for i in range(N):
    a, b = map(int, input().split())
    A[i] = a
    B[i] = b
ans = 0
for i in range(N-1,-1,-1):
    A[i] += ans
    if A[i]%B[i] != 0:
        ans += B[i]-(A[i]%B[i])
print(ans)


Measured memory_bytes: 14836
#include <bits/stdc++.h>
#define LLI long long int
#define FOR(v, a, b) for(LLI v = (a); v < (b); ++v)
#define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(LLI v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define popcount __builtin_popcount
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <misc/C++/Debug.cpp>
#else
#define dump(...) ((void)0)
#endif

#define gcd __gcd

using namespace std;
template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;}

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}

struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  int N;
  while(cin >> N){
    vector<vector<int>> x(N);
    vector<vector<int>> y(N);

    REP(i,N){
      int a; cin >> a;

      x[i] = vector<int>(a);
      y[i] = vector<int>(a);

      REP(j,a){
        cin >> x[i][j] >> y[i][j];
        x[i][j] -= 1;
      }
    }

    dump(x,y);

    int ans = 0;

    REP(i,1<<N){
      bool ok = true;
      REP(j,N){
        if(i & bit(j)){
          int a = x[j].size();
          //dump(a);
          REP(k,a){
            if(y[j][k] != ((i >> x[j][k]) & 1)){
              ok = false;
            }
          }
          
        }
      }
      
      if(ok){
        chmax(ans, popcount(i));
      }
    }

    cout << ans << endl;
  }


  return 0;
}


Measured memory_bytes: 256
type tree = Nil | Node of int * tree * tree

let create () = Nil

let insert x t =
  let rec doit = function
    | Nil -> Node (x, Nil, Nil)
    | Node (y, l, r) ->
      if x < y then Node (y, doit l, r)
      else Node (y, l, doit r) in
  doit t

let preorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> f x; doit l; doit r in
  doit t

let inorder f t =
  let rec doit = function
    | Nil -> ()
    | Node (x, l, r) -> doit l; f x; doit r in
  doit t

let print t =
  inorder (fun e -> print_string " "; print_int e) t;
  print_newline ();
  preorder (fun e -> print_string " "; print_int e) t;
  print_newline ()

let find x t =
  let rec doit = function
    | Nil -> false
    | Node (y, _, _) when x = y -> true
    | Node (y, l, _) when x < y -> doit l
    | Node (_, _, r) -> doit r in
  doit t

let delete x t =
  let rec doit = function
    | Nil -> assert false
    | Node (y, l, r) ->
      begin
        if x = y then
          if l = Nil then r
          else if r = Nil then l
          else
            let rec dudu = function
              | Nil -> assert false
              | Node (x, Nil, _) -> x
              | Node (_, l, _) -> dudu l in
            let rec wa = function
              | Nil -> assert false
              | Node (_, Nil, r) -> r
              | Node (x, l, r) -> Node (x, wa l, r) in
            Node (dudu r, l, wa r)
        else if x < y then Node (y, doit l, r)
        else Node (y, l, doit r)
      end in
  doit t

let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let () =
  let m = read_int () in
  let t = ref (create ()) in
  for _ = 0 to m - 1 do
    match read_line () |> split_on_char ' ' with
    | ["insert"; n] -> t := insert (int_of_string n) !t
    | ["find"; n] -> print_endline (if find (int_of_string n) !t then "yes" else "no")
    | ["delete"; n] -> t := delete (int_of_string n) !t
    | _ -> print !t
  done

Measured memory_bytes: 25336
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

int n;

class Com
{
private:
	const int MAX = 510000;

	vector<ll> fac;
	vector<ll> finv;
	vector<ll> inv;

public:
	Com()
	{

	}

	void init()
	{
		fac.resize(MAX);
		fac.at(0) = 1;
		fac.at(1) = 1;

		finv.resize(MAX);
		finv.at(0) = 1;
		finv.at(1) = 1;

		inv.resize(MAX);
		inv.at(1) = 1;

		for (int i = 2; i < MAX; i++)
		{
			fac.at(i) = fac.at(i - 1) * i % mod;
			inv.at(i) = mod - inv.at(mod % i) * (mod / i) % mod;
			finv.at(i) = finv.at(i - 1) * inv[i] % mod;
		}
	}

	ll get(int n, int k)
	{
		if (n < k || n < 0 || k < 0)
		{
			return 0;
		}
		return fac.at(n) * (finv.at(k) * finv.at(n - k) % mod) % mod;
	}
};

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

	Com com;
	com.init();


	for (int i = 1; i <= k; i++)
	{
		cout << (com.get(n - k + 1, i) * com.get(k - 1, i - 1)) % mod << endl;
	}
}


Measured memory_bytes: 12160
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long N,x,ans = 0;
    cin >> N >> x;
    vector<long long> a(N);
    for(int i = 0;i < N;i ++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    for(int i = 0;x > 0 && i < N;i ++){
        x -= a[i];
        ans ++;
    }
    if(x != 0) ans --; 
    
    cout << ans << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
using namespace std;

main()
{
        double h,w,n;
        cin>>h>>w>>n;

        cout<<ceil(n/max(h,w))<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
long long INF = (long long)1E17;
#define i_7 (long long)(1E9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}

//typedef long long ll;
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

//配列のSIZEは問題ごとに定義する必要がある。
const int SIZE = 2000010;
long long inv[SIZE+1];//各iの逆元を格納する配列。
long long kai[SIZE+1];//i!のmodを格納する配列。
long long invkai[SIZE+1];//各i!の逆元を格納する配列。
const int MOD=i_7;
void invinit(){//上の配列を初期化する関数。
    inv[1]=1;
    for(int i=2;i<=SIZE;i++){
        inv[i] = MOD - ((MOD/i)*inv[MOD%i])%MOD;
    }
    
    kai[0]=invkai[0]=1;
    for(int i=1;i<=SIZE;i++){
        kai[i]=(kai[i-1]*i)%MOD;
        invkai[i]=(invkai[i-1]*inv[i])%MOD;
    }
}

long long comb(long long a, long long b){
    if(b<0 || a<b){
        return 0;
    }
    return mod(kai[a]*mod(invkai[b]*invkai[a-b]));
}

int main(){
  invinit();
  using namespace std;
  long long n, k;
  cin>>k;
  string s;
  cin>>s;
  n = s.size();
  long long ans = 0;
  for(long long i = 0; i <= k; i++){
    long long c = comb(n + k - i - 1, n - 1);
    long long temp = mod(po(25, k-i) * po(26, i));
    ans += mod(c * temp);
    ans = mod(ans);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 52152
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};
 
 
void solve(){
    string a,b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
 
} 
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
     
    ll Q=1;
    // cin>>Q;
    rep(_,Q){
 
        solve();
 
    }
   
 
 
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,N) for(int i = 0;i < (int)(N);i++)
int main(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  string ans="Yes";
  if(n%2==1) {
    ans="No";
    cout<<ans<<endl;
    return 0;
  }
 string a=s.substr(0,n/2);
 string b=s.substr(n/2);
  if(a!=b){
    ans="No";
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rrep(i, n) for(ll i = n - 1; i > -1; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define fi first
#define se second
#define debug(V) rep(i, V.size()) cout << V[i] << " ";
const ll INF = (1LL << 61) - 1;
const ll MOD = 1000000007 /*998244353*/;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, h, x, y, z, p, q, n, t, r, k, w, l, ans, i, j, u, v;
string S, T;
vl A, B;
void input() { cin >> S; }
void solve() {
    x = S[0] - 'A';
    if(x > -1 && x < 26)
        cout << "A" << endl;
    else
        cout << "a" << endl;
}
int main() {
    // cout<<fixed<<setprecision(15);
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    solve();
}


Measured memory_bytes: 3496
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=1e5+5;
ll dp[N][2];
//dp[i][0]前面i位确定，并且a,b的异或值前i位等于L的前i位的方案数
//dp[i][0]前面i位确定，并且a,b的异或值前i位小于L的前i位的方案数
char s[N];
int main()
{
    scanf("%s",s+1);
    int l=strlen(s+1);
    dp[0][0]=1;
    for(int i=1;i<=l;i++)
    {
        if(s[i]=='1')
        {
            dp[i][0]=dp[i-1][0]*2%mod;//(0,1),(1,0),a在这一位选1，b在这一位选0或者a在这一位选1，b在这一位选0
            dp[i][1]=(dp[i-1][1]*3+dp[i-1][0])%mod;//前i-1位小于l，三种选法(0,1),(1,0),(0,0)都合法，否则只有(0,0)合法
        }
        else
        {
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1]*3%mod;
        }
    }
    printf("%lld\n",(dp[l][1]+dp[l][0])%mod);
}


Measured memory_bytes: 1920
#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>

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

using namespace std;



int main()
{
	int n,m;
	cin>>n>>m;
	
	vector<int> x;
	vector<int> y;
	rep(i,m+1)x.push_back(0);
	
	rep(i,n)
	{
		int a;
		cin>>a;
		y.push_back(a);
		x[a%m]++;
	}
	
	sort(y.begin(), y.end());
	
	
	int ans = 0;
	rep(i,m)
	{
		while(1)
		{
			bool ok = false;
			
			bool isHit = false;
			int a = i;
			int b = (m-i)%m;
			isHit |= (a!=b) && (x[a]>=1 && x[b]>=1);
			isHit |= (a==b) && (x[a]>=2);
			
			if(isHit)
			{
				ok = true;
				ans++;
				x[a]--;
				x[b]--;
			}
			
			if(!ok)break;
		}
	}
	
	
	rep(i,y.size()-1)
	{
		if(x[y[i]%m] < 2)continue;
		
		if(y[i]==y[i+1])
		{
			ans++;
			x[y[i]%m]-=2;
			i++;
		}
	}
	
	printf("%d\n",ans);
}

Measured memory_bytes: 1400
#include <iostream>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;

double f(double a,double p,double q,double x) {
    return a*(x-p)*(x-p)+q;
}

double f(double a, double p, double x) {
    return sqrt(1.0 + 4.0*a*a*x*x - 8.0*a*a*p*x + 4.0*a*a*p*p);
}

double s(double a, double p, double x1, double x2){
    double N = 1000.0;
    double h = (x2 - x1)/ N, p1=0.0, p2=0.0;
    for(int n = 1; n <= N/2-1; n++){
        p1 += f(a, p, x1+2.0*n*h);
    }
    for(int n = 1; n <= N/2; n++){
        p2 += f(a, p, x1+2.0*n*h-h);
    }
    p = f(a, p, x1) + 2.0*p1 + 4.0*p2 + f(a, p, x2);
    return p*h/3.0;
}

int main(){
    int W,H,n; 
    double a[50],p[50],q[50];
    cin >> W >> H >> n;
    for(int i=0; i<n; i++) {
        cin >> a[i] >> p[i] >> q[i];
    }
    vector<double> X; //動的配列クラス
    X.push_back(0);//末尾に0を挿入
    X.push_back(W);//末尾にWを挿入
   for(int i=0; i<n; i++){
       // 山 i と窓枠の下辺との交点
       if(0<=p[i]-sqrt(-(q[i]/a[i])) && p[i]-sqrt(-(q[i]/a[i]))<=W) {
           X.push_back(p[i]-sqrt(-(q[i]/a[i]))); //枠内ならx1を末尾に挿入
       }
       if(0<=p[i]+sqrt(-(q[i]/a[i])) && p[i]+sqrt(-(q[i]/a[i]))<=W) {
           X.push_back(p[i]+sqrt(-(q[i]/a[i]))); //枠内ならx2を末尾に挿入
       }
       for(int j=0; j<i; j++){ // 山 i と山 j の交点
           double A=a[i]-a[j];
           double B=-2*a[i]*p[i]+2*a[j]*p[j];
           double C=a[i]*p[i]*p[i]+q[i]-a[j]*p[j]*p[j]-q[j];

           if(A!=0){ // Ax^2+Bx+C=0
               if(B*B-4*A*C>=0){
                   double x;
                   x=(-B-sqrt(B*B-4*A*C))/(2*A);
                   if(0<=x && x<=W) X.push_back(x);//枠内なら交点を末尾に挿入
                   x=(-B+sqrt(B*B-4*A*C))/(2*A);
                   if(0<=x && x<=W) X.push_back(x);//枠内なら交点を末尾に挿入
               }
           }
           else if(B!=0){ // Bx+C=0
               double x=-1.0*C/B;
               if(0<=x && x<=W) X.push_back(x);//枠内なら交点を末尾に挿入
           }
       }
   }

   sort(X.begin(),X.end()); //昇順でソートする

   double ans=0;
   for(int i=0; i<(int)X.size()-1; i++){
       double x1=X[i],x2=X[i+1];

       int jmax=-1;
       for(int j=0; j<n; j++){
           if(f(a[j],p[j],q[j],(x1+x2)/2)>0//ｙ＝０より上
           && (jmax==-1 || f(a[jmax],p[jmax],q[jmax],(x1+x2)/2)<f(a[j],p[j],q[j],(x1+x2)/2))){//それまでで一番高い位置にある関数＜ｊ個目の関数のとき交換
               jmax=j;
           }
       }

       if(jmax != -1)ans+=s(a[jmax], p[jmax], x1, x2);
       
   }

   cout << fixed;
   cout << setprecision(9) << ans << endl;

   return 0;
}


Measured memory_bytes: 3304
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

const long long inf = 1LL << 60;

int N;
long long W, weight[110], value[110];

long long dp[110][100010];

int main(){
    int N,W; cin >> N >> W;
    for (int i = 0; i < N; i++) cin >> weight[i] >> value[i];

    for (int i = 0; i < 110; i++) for(int j = 0; j < 100010; j++)dp[i][j]=inf;
    dp[0][0] = 0;


    for (int i = 0; i < N; i++){
        for (int sum = 0; sum < 100010; sum++){
            if(sum - value[i] >= 0){
                dp[i+1][sum] = 
                    (dp[i+1][sum] < dp[i][sum - value[i]]+ weight[i])?
                        dp[i+1][sum]: 
                        dp[i][sum - value[i]]+ weight[i];
            }
            dp[i+1][sum] = 
                (dp[i+1][sum] < dp[i][sum])?
                    dp[i+1][sum]:
                    dp[i][sum];
        }
    }

    long long out = 0;
    for (int v = 0; v < 100010; v++)
    {
        if (dp[N][v] <= W) out = v;
    }
    cout << out << endl;
    return 0;
}


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

const int mod = 1000000007;

bool check(int i) {
  int a[4];
  for (int j = 0; j < 4; j++) {
    a[3-j] = i % 4;
    i /= 4;
  }
  bool ok = true;
  for (int j = 0; j < 4; j++) {
    if (j) swap(a[j-1], a[j]);
    if (a[0] == 1 && a[1] == 2 && a[2] == 3) ok = false;
    if (a[1] == 1 && a[2] == 2 && a[3] == 3) ok = false;
    if (j) swap(a[j-1], a[j]);
  }
  return (ok ? true : false);
}

int main() {
  int n; cin >> n;
  int dp[105][64];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < 64; j++) dp[i][j] = 0;
  }
  dp[0][0] = 1;
  bool tabl[64][4];
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 4; j++) {
      tabl[i][j] = (check(4 * i + j) ? true : false);
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 64; j++) {
      for (int k = 0; k < 4; k++) {
        if (tabl[j][k]) {
          int p = (4 * j + k) % 64;
          dp[i+1][p] += dp[i][j];
          dp[i+1][p] %= mod;
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 64; i++) {
    ans += dp[n][i];
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main() {
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    int sum = 0;
    for (int i=1; i<=n; i++)
        sum += a[i];
    int avg = sum;
    int idx = 0;
    int mn = 1e9;
    for (int i=1; i<=n; i++)
        if (abs(a[i]*n-avg) < mn) {
            mn = abs(a[i]*n-avg);
            idx = i;
        }
    printf("%d\n", idx-1);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do { cout << "\033[32;1m " << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
ll rand_int(ll l, ll r) //[l, r]
{
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<ll>(l, r)(gen);
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
    print(v[i],i==(int)(v.size())-1?suc:2);
}
const int maxn=1e5+7;
vi G[maxn];
int a[maxn],b[maxn];
int sum[maxn];
ll ans=0;
void dfs(int u,int fa=-1)
{
    sum[u]=b[u]-a[u];
    for(auto v:G[u])if(v!=fa)
    {
        dfs(v,u);
        sum[u]+=sum[v];
    }
}
ll k[maxn];
void dfs2(int u,int fa=-1,ll cur=0)
{
    k[u]=cur;
    ans=min(ans,k[u]);
    for(auto v:G[u])if(v!=fa)
        dfs2(v,u,cur-sum[v]);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1,u,v;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=0;i<n;i++) cin>>a[i+1];
    for(int i=0;i<n;i++) cin>>b[i+1];
    dfs(1);
    dfs2(1);
    //dbg(ans);
    ll op=0;
    for(int i=1;i<=n;i++)
    {
        //dbg(k[i]);
        op+=k[i];
    }
    op+=-n*ans;
    print(op);
}


Measured memory_bytes: 16268
def test():

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

	for i in range(n):

		given_face = list(map(int,input().split()))

		top = given_face[0]
		front = given_face[1]

		if (top == faces[1] and front == faces[2]) or (top == faces[2] and front == faces[4]) or (top == faces[4] and front == faces[3]) or (top == faces[3] and front == faces[1]):
			print(f"{faces[0]}")
		elif (top == faces[0] and front == faces[3]) or (top == faces[3] and front == faces[5]) or (top == faces[5] and front == faces[2]) or (top == faces[2] and front == faces[0]):
			print(f"{faces[1]}")
		elif (top == faces[0] and front == faces[1]) or (top == faces[1] and front == faces[5]) or (top == faces[5] and front == faces[4]) or (top == faces[4] and front == faces[0]):
			print(f"{faces[2]}")
		elif (top == faces[0] and front == faces[4]) or (top == faces[4] and front == faces[5]) or (top == faces[5] and front == faces[1]) or (top == faces[1] and front == faces[0]):
			print(f"{faces[3]}")
		elif (top == faces[0] and front == faces[2]) or (top == faces[2] and front == faces[5]) or (top == faces[5] and front == faces[3]) or (top == faces[3] and front == faces[0]):
			print(f"{faces[4]}")
		elif (top == faces[1] and front == faces[3]) or (top == faces[3] and front == faces[4]) or (top == faces[4] and front == faces[2]) or (top == faces[2] and front == faces[1]):
			print(f"{faces[5]}")

if __name__ == "__main__":
	test()


Measured memory_bytes: 5616
N = int(input())
V_list = list(map(int, input().split()))


import heapq

heapq.heapify(V_list)


for i in range(N-1):
        v1=heapq.heappop(V_list)
        v2=heapq.heappop(V_list)
        new_v = (v1+v2)/2
        heapq.heappush(V_list,new_v)





print(V_list[0])

Measured memory_bytes: 3060
<?php
fscanf(STDIN, "%d %d", $n, $k);
$as = explode(' ', trim(fgets(STDIN)));

$ans = array();
for ($l=0; $l < $k; $l++) {
  $cnts = array_fill(0, $n+1, 0);
  foreach ($as as $p => $a) {
    $begin = max($p - $a, 0);
    $end   = min($p + $a + 1, $n);
    ++$cnts[$begin];
    --$cnts[$end];
  }

  $tmp = 0;
  for ($i=0; $i < $n; $i++) {
    $tmp += $cnts[$i];
    $ans[$i] = $tmp;
  }

  if ($as === $ans) {
    break;
  }

  $as = $ans;
}

echo implode(' ', $ans);


Measured memory_bytes: 46336
var std = process.stdin;
std.resume();
std.setEncoding('utf8');
std.on('data', function (chunk) {
    var data = chunk.replace(/\n/, '').split(' ').map(Number);
    var count = 0;
    for (var i = data[0]; i <= data[1]; i++) {
        if (data[2] % i === 0) {
            count++;
        }
    }
    console.log(count);
});

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

using namespace std;

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

	int n;
	cin >> n;
	double count = 0;
	for(int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		if(a % 4 == 0)count++;
		else if(a % 2 == 0)count += 0.5;
	}
	if(n / 2 <= count)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 256
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).unwrap();
    word.trim().to_owned()
}

fn main() {
    let n:usize = get_input().parse().unwrap();
    let mut w:Vec<i64> = Vec::new();

    let line = get_input();
    let mut split = line.split_whitespace();
    for _ in 0..n {
        w.push(split.next().unwrap().parse().unwrap());
    }

    let mut ans = (n + 0) as i64;
    for i in 1..n {
        let s1:i64 = w[0..i].iter().sum();
        let s2:i64 = w[i ..].iter().sum();
        let s = if s1 > s2 {
            s1 - s2
        } else {
            s2 - s1
        };
        ans = std::cmp::min(ans, s);
    }

    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;



int main(void) {
  ll N;
  cin >> N;
  ll i, j;
  ll K=0, M=0;
  
  for(i=0; i<=N; i++) {
    if(i*(i+1)==N*2) {
      K=i+1;
      M=i;
      break;
    }
  }
  
  if(K==0) {
    pt("No");
    return 0;
  }
  
  
  
  vector<ll> g[K];
  ll c=0;
  
  for(i=0; i<K; i++) {
    ll t=c;
    for(j=0; j<M-i; j++) {
      g[i].push_back(c);
      c++;
    }
    
    for(j=i+1; j<K; j++) {
      g[j].push_back(t);
      t++;
    }
    
  }
  
  
  pt("Yes");
  pt(K);
  for(i=0; i<K; i++) {
    cout << M << " ";
    for(j=0; j<M; j++) {
      cout << g[i][j]+1 << " ";
    }
    pt("");
  }
  
}


Measured memory_bytes: 3200
#include<stdio.h>

int main(){
  int N,M,h[201],m[201];
  int time[201],temp;
  int i,j;

  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d %d",&h[i],&m[i]);
    time[i]=h[i]*100+m[i];
  }
  scanf("%d",&M);
  for(i=N;i<M+N;i++){
    scanf("%d %d",&h[i],&m[i]);
    time[i]=h[i]*100+m[i];
  }

  for(i=0;i<M+N-1;i++){
    for(j=0;j<M+N-1-i;j++){
      if(time[j]>time[j+1]){
	temp=time[j];
	time[j]=time[j+1];
	time[j+1]=temp;
      }
    }
  }

  for(i=0;i<N+M;i++){
    if(time[i]==time[i+1] && i<N+M-1){
      continue;
    }else{
      printf("%d:%02d",time[i]/100,time[i]%100);
      if(i<N+M-1)printf(" ");
    }
  }
  printf("\n");
  return(0);
}



Measured memory_bytes: 2708
class Tree():
    def __init__(self):
        self.nodes = {}
        self.root = None

    def add_node(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)

    def insert(self, z_key):
        self.add_node(z_key)
        z = self.nodes[z_key]
        y = None  # xの親
        x = self.root
        while x is not None:
            y = x  # 親を設定
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def __str__(self):
        ans_in, ans_pre = [], []
        self.root.in_walk(ans_in)
        self.root.pre_walk(ans_pre)
        str_in = ' ' + ' '.join(map(str, ans_in))
        str_pre = ' ' + ' '.join(map(str, ans_pre))
        return str_in + '\n' + str_pre


class Node():
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

    def pre_walk(self, ans):
        ans.append(self.key)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.key)
        if self.right:
            self.right.in_walk(ans)


# ここからmain
tree = Tree()
n = int(input())
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == 'insert':
        key = int(line[1])
        tree.insert(key)
    else:
        print(tree)



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

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

    int B ;
    B = N % 500 ;
    
    if (B <= A){
        cout << "Yes" << endl;
    }
    
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N, Y;

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

    for (int x = 0; x <= N; x++) {
        for (int y = 0; y <= N-x; y++) {
            int z = N - y - x;
            if (10000 * x + 5000 * y + 1000 * z == Y) {
                cout << x << ' ' << y << ' ' << z << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
}


Measured memory_bytes: 256
def bubbleSort(A,N):
    flag=1
    cnt=0
    while flag:
        flag=0
        for i in range(N-1,0,-1):
            if A[i]<A[i-1]:
                A[i],A[i-1]=A[i-1],A[i]
                flag=1
                cnt+=1
    return A,cnt

N = int(input())
A = list(map(int,input().split()))
A,cnt = bubbleSort(A,N)
print(*A)
print(cnt)


Measured memory_bytes: 5612