akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

double getMoreHeadsProb(vector<double> inp) {
    int n=inp.size();
    vector<vector<double>> dp(n+1,vector<double>(n+1,0));
    dp[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            dp[i][j]=j==0?dp[i-1][j]*double(1-inp[i-1]):dp[i-1][j]*double(1-inp[i-1])+dp[i-1][j-1]*double(inp[i-1]);
        }
    }
    double res=0;
    for(int i=n/2+1;i<=n;i++) {
        res+=dp[n][i];
    }
    return res;
}

int main(void){
    // Your code here!
    int n=0;
    cin>>n;
    vector<double> inp(n,0);
    for(int i=0;i<n;i++)cin>>inp[i];
    cout<<setprecision(15)<<getMoreHeadsProb(inp)<<endl;
}


Measured memory_bytes: 73816
#!/usr/bin/env python3
from collections import Counter
N = int(input())
S = []
for i in range(N):
    S.append(input())
s = Counter(S).most_common()
maximum = s[0][1]
tmp = []
for i in s:
    if i[1] == maximum:
        tmp.append(i[0])
    else:
        break
for i in sorted(tmp):
    print(i)

Measured memory_bytes: 45032
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include <iomanip>
#include <cmath>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

int A[509];
int N, K;

bool C(int n) {
	int B[509];
	int sum = 0;
	for (int i = 0; i < N; i++) {
		B[i] = A[i] - (A[i] / n)*n;
		sum += B[i];
	}
	sort(B, B + N);

	if (sum % n != 0 || (sum/n) > N) return false;
	else {
		int L = sum / n;
		int totL = 0;
		for (int i = 0; i < N-L; i++) totL += B[i];
		if (totL <= K) return true;
		else return false;
	}
}

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

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

	int ans = 1;

	for (int i = 1; i*i <= sum; i++) {
		if (sum % i == 0) {

			int num = i;
			if (C(num)) ans = max(ans, num);
			

			num = sum / i;
			if (C(num)) ans = max(ans, num);
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  vector<int> a, b, c;
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    a.pb(x);
  }
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    b.pb(x);
  }
  for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    c.pb(x);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());
  vector<int> bc;
  vector<ll> sum;
  sum.resize(n);
  for(int i = 0; i < n; i++){
    int index = upper_bound(c.begin(), c.end(), b[i]) - c.begin();
    bc.pb(n - index);
  }
  for(int i = n - 1; i >= 0; i--){
    if(i == n - 1)sum[i] = bc[i];
    else sum[i] = sum[i + 1] + bc[i];
  }
  ll res = 0;
  for(int i = 0; i < n; i++){
    int index = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
    if(index < n)res += sum[index];
  }
  cout << res << endl;
	return 0;
}


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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

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

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, std::vector<std::string> s, long long M, std::vector<std::string> t){
    map<string, int> b;
    map<string, int> r;

    REP(i, N) {
        if(b.count(s[i])) {
            b[s[i]]++;
        } else {
            b[s[i]] = 1;
        }
    }

    REP(i, M) {
        if(r.count(t[i])) {
            r[t[i]]++;
        } else {
            r[t[i]] = 1;
        }
    }

    int ans = 0;
    for(auto it = b.begin(); it != b.end(); it++) {
        if (r.count(it->first)) {
            ans = max(ans, it->second - r[it->first]);
        } else {
            ans = max(ans , it->second);
        }
    }

    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<std::string> s(N);
    for(int i = 0 ; i < N ; i++){
        std::cin >> s[i];
    }
    long long M;
    scanf("%lld",&M);
    std::vector<std::string> t(M);
    for(int i = 0 ; i < M ; i++){
        std::cin >> t[i];
    }
    solve(N, std::move(s), M, std::move(t));
    return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0

for na in range(a+1):
    for nb in range(b+1):
        for nc in range(c+1):
            if (500 * na + 100 * nb + 50 * nc) == x:
                count += 1

print(count)

Measured memory_bytes: 3060
#include <cstdio>

int N;
int A[200010];
int num[200010][20];
long long res;

int bsrch(int ii, int jj)
{
	int l = ii, r = N;
	int m;
	while(l<r){
		m = (l+r)/2;
		if(num[m+1][jj] - num[ii][jj] >= 2)
			r = m;
		else
			l = m+1;
	}
	return l-1;
}

void solve()
{
	int i, j;
	for(i=0; i<N; i++){
		for(j=0; j<20; j++){
			if( (A[i] & (1<<j)) > 0)
				num[i+1][j] = num[i][j] + 1;
			else
				num[i+1][j] = num[i][j];
		}
	}
	for(i=0; i<N; i++){
		int mn = 1000000;
		for(j=0; j<20; j++){
			int tmp = bsrch(i, j);
			if(tmp < mn)
				mn = tmp;
		}
		res += mn-i+1;
	}
	printf("%lld\n", res);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	int i;
	scanf("%d", &N);
	for(i=0; i<N; i++)
		scanf("%d", &A[i]);
	solve();
	return 0;
}

Measured memory_bytes: 16512
// abc054a: One Card Poker
#include <bits/stdc++.h>
using namespace std;

#define in(x) cin>>(x)
#define oute(x) cout<<(x)<<endl

int main(){
  int a,b;in(a);in(b);
  if(a==b) oute("Draw");
  else if(a==1) oute("Alice");
  else if(b==1) oute("Bob");
  else if(a>b) oute("Alice");
  else if(a<b) oute("Bob");
}

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

using namespace std;

#define ll long long int
#define get(a) ll a; cin >> a;
#define show(a) cout << a << endl;
#define full(p) p.begin(), p.end()
#define sz(a) (ll)(a.size())
#define pb push_back

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

	long double n,k;
	cin >> n >> k;
	// so we do this thing now
	long double score = 0;

	for(int i = 1 ;  i<= (int)n ; i++)
	{
		long double prob = (long double)(1/n);
		ll temp = i;

		while(temp < k)
		{
			prob = (long double)(prob/2);
			temp *= 2;
		}
		// cout << 1/prob << endl;
		score += (long double)(prob);
	}
	cout << score << endl;
	return 0;
}

Measured memory_bytes: 3756
#include<functional>
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<string>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};// 上 左 下 右
const int N=100005,M=1000005,K=200005,mod=1000000007;
const long long llinf=9223372036854775807ll;
//int & long long
long long a,b;
int gcd(long long a,long long b)
{
	if(a%b==0)
		return b;
	return gcd(b,a%b);
}
int main(){
	cin>>a>>b;
	cout<<a*b/gcd(a,b); 
	return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [[int(i) for i in input().split()] for _ in range(H)]

op = []
for y in range(H - 1) :
    for x in range(W) :
        if a[y][x] % 2 != 0 :
            op.append((y + 1, x + 1, y + 2, x + 1))
            a[y+1][x] += 1

for x in range(W - 1) :
    if a[H-1][x] % 2 != 0 :
        op.append((H, x + 1, H, x + 2))
        a[H-1][x+1] += 1
        
print(len(op))
for op_ in op :
    print(*op_)

Measured memory_bytes: 73820
n = int(input())
a = [int(i) for i in input().split(' ')]

mc = 0
for e in a:
  if e < 0:
    mc += 1


    
f = 0
if mc % 2 == 1:
  a = [abs(i) for i in a]
  a.sort()
  f = 0
  for i in range(1, n):
    f += a[i]
  f -= a[0]
else:
  for e in a:
    if e >= 0:
      f += e
    else:
      f -= e
      
print(f)

Measured memory_bytes: 14332
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <fstream>

using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    for(int i = 0; i <= 100; i ++){
        int sockets = a * i;
        sockets -= (i - 1);
        if(sockets >= b){
            cout << i << endl;
            return 0;
        }
    }
    
}


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

int main(){
    int a,b,c,x;
    int cnt = 0;
    std::cin >> a >> b >> c >> x;
    for (int i_a = 0; i_a < a+1; ++i_a)
    {
        for (int i_b = 0; i_b < b+1; ++i_b)
        {
            for (int i_c = 0; i_c < c+1; ++i_c)
            {
                /* code */
                if(500*i_a + 100*i_b + 50*i_c == x) ++cnt;
            }
        }
    }
    std::cout << cnt << "\n";
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
bonus=0
for x in range(1,n):
  if A[x-1]+1 == A[x]:
    bonus += C[A[x]-2]
 
ans = sum(B) + bonus
print(ans)

Measured memory_bytes: 3064
# coding: utf-8

import sys

S = input()

i = 0
while i < len(S):
	if i + 4 < len(S) and S[i : i + 5] == "dream":
		if i + 6 < len(S) and S[i + 5 : i + 7] == "er":
			if i + 9 < len(S) and S[i + 7 : i + 10] == "ase":
				if i + 10 < len(S) and S[i + 10] == "r":
					i += 11
				else:
					i += 10
			else:
				i += 7
		else:
			i += 5
	else:
		if i + 4 < len(S) and S[i : i + 5] == "erase":
			if i + 5 < len(S) and S[i + 5] == "r":
				i += 6
			else:
				i += 5
		else:
			print("NO")
			sys.exit()

print("YES")


Measured memory_bytes: 3188
#include<stdio.h>

void operation(int a[100][100],int b[100],long long c[100],int n,int m){
	int i_c, i_p;
	for (i_c = 0; i_c < n; i_c++){
		for (i_p = 0; i_p < m; i_p++){
			c[i_c] = c[i_c]+a[i_c][i_p] * b[i_p];
		}
	}
}

int main(void){
	long long c[100] = { 0 };
	int a[100][100] = { 0 };
	int b[100] = { 0 };
	int m, n;
	scanf("%d %d", &n, &m);
	int i_c, i_p;
	for (i_c = 0; i_c < n; i_c++){
		for (i_p = 0; i_p < m; i_p++){
			scanf("%d", &a[i_c][i_p]);
		}
	}
	for (i_p = 0; i_p < m; i_p++){
		scanf("%d", &b[i_p]);
	}

	operation(a, b, c,n,m);
	for (i_p = 0; i_p < n; i_p++){
		printf("%lld\n", c[i_p]);
	}


	return 0;
}


Measured memory_bytes: 2120
m=10**9+7
i=s=r=f=1
a=open(0).read().split()
for x in a[1:]:r+=int(x)*~-s+int(a[-i])*s;f=f*i%m;i+=1;s+=pow(i,m-2,m)
print(~-r*f%m)


Measured memory_bytes: 70824
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a;
	cin>>a;
	int yu=7%a;
	for (int i=1;i<=a+30;i++)
	{
		if (yu==0)
		{
			cout<<i<<endl;
			return 0;
		}
		yu=(yu*10+7)%a;
	}
	cout<<"-1"<<endl;
	return 0;
}


Measured memory_bytes: 3636
from sys import stdin

if __name__ == '__main__':
    A, B = [ int(x) for x in stdin.readline().rstrip().split() ]
    num_of_tup = 0
    total_plugs = 1
    while True:
        if total_plugs >= B:
            break
        else:
            total_plugs = total_plugs - 1 + A
            num_of_tup += 1
    print(num_of_tup)


Measured memory_bytes: 2940
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    char a[4], b[4];
    cin >> a >> b;
    if(a[0] == b[2] && a[1] == b[1] && a[2] == b[0])
        cout << "YES\n";
    else 
        cout << "NO\n";

return 0;
}

Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words

getIntList = readIntList <$> BS.getLine

calc :: Int -> Int -> Int -> Int -> Int
calc g b n (-1) = 0
calc g b n j
  | (n - j * g) `mod` b == 0 = 1 + calc g b n (j -1)
  | otherwise = calc g b n (j -1)

calcAll :: Int -> Int -> Int -> Int -> Int -> Int
calcAll r g b n (-1) = 0
calcAll r g b n i = calc g b rest j + calcAll r g b n (i -1)
  where
    rest = n - r * i
    j = rest `div` g

main = do
  [r, g, b, n] <- getIntList
  let [r', g', b'] = reverse $ sort [r, g, b]
  print $ calcAll r' g' b' n (n `div` r')


Measured memory_bytes: 4432
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)
#define kiriage(a,b)  ((a)+(b)-1)/(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  string s;

  cin >> s;
  for(int i = 0;i < sz(s) ;i = i + 2)
  {
    cout << s[i];
  }  



  return 0;
}
// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}


Measured memory_bytes: 512
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i];
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion


int32_t main() {
    make(int, n);
    makev(a, n);
    VI cnt(n + 1);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        ans -= cnt[a[i]] * (cnt[a[i]] - 1) / 2;
        cnt[a[i]]++;
        ans += cnt[a[i]] * (cnt[a[i]] - 1) / 2;
    }
    for(int i = 0; i < n; ++i){
        ans -= cnt[a[i]] * (cnt[a[i]] - 1) / 2;
        cnt[a[i]]--;
        ans += cnt[a[i]] * (cnt[a[i]] - 1) / 2;
        cout << ans << '\n';
        ans -= cnt[a[i]] * (cnt[a[i]] - 1) / 2;
        cnt[a[i]]++;
        ans += cnt[a[i]] * (cnt[a[i]] - 1) / 2;
    }
    return 0;
}

Measured memory_bytes: 5760
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	float a, b, c, cal[100];
	float ans;
	float save, sum = 0;
	
	scanf("%d %d %d %d", &n, &a, &b, &c);
	
	for (int i = 0; i < n; i++){
		scanf("%d", &cal[i]);
		c += cal[i];
	}
	
	sort(cal, cal + n);
	ans = c / (a + (b * n));
	
	for (int i = 0; i < n; i++){
		sum += cal[i];
		save = (c - sum) / (a + (b * (n - i - 1)));
		if (ans < save){
			ans = save;
		}
	}
	
	int best;
	best = (int)ans;
	
	printf("%d\n", best);
	
	return (0);
}

Measured memory_bytes: 1040
n = gets.to_i
a = gets.split.map(&:to_i)

def parent(i)
  i / 2
end

def left(i)
  2 * i
end

def right(i)
  2 * i + 1
end

(1..n).each do |i|
  s =  "node #{i}: key = #{a[i - 1]}, "
  s << "parent key = #{a[parent(i) - 1]}, " if parent(i) >= 1
  s << "left key = #{a[left(i) - 1]}, " if left(i) <= n
  s << "right key = #{a[right(i) - 1]}, " if right(i) <= n
  puts s
end


Measured memory_bytes: 6868
INF = 1000000000

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(n)]

maxA = max(AB, key=lambda x: x[0])[0]

dp = [INF for i in range(h+maxA)]
dp[0] = 0

for i in range(1, h+maxA):
    dp[i] = min(dp[i-a] + b for a, b in AB)

print(min(dp[h:]))


Measured memory_bytes: 43484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=10100100100100100;
int main(){
    int n;cin >> n;
    map<string,int> mp;
    for(int i=0; i<n; i++){
        string s;cin >> s;
        mp[s]++;
    }
    int mx=0;
    vector<string> ans;
    for(auto p: mp){
        mx=max(mx,p.second);
    }
    for(auto p: mp){
        if(p.second==mx) ans.push_back(p.first);
    }
    sort(ans.begin(),ans.end());
    for(int i=0; i<ans.size(); i++) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 27376
r, c = map(int, input().split())

a = [[0 for j in range(c)] for i in range(r)]
for i in range(r):
    a[i] = list(map(int, input().split()))

rsum = [0 for i in range(r)]
csum = [0 for i in range(c)]
for i in range(r):
    rsum[i] = sum(a[i])
    for j in range(c):
        csum[j] += a[i][j]
allsum = sum(rsum)

for i in range(r):
    for j in range(c):
        print(a[i][j], end = " ")
    print(rsum[i])
for i in range(c):
    print(csum[i], end = " ")
print(allsum)

Measured memory_bytes: 8276
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
ukv = [list(map(int, input().split())) for _ in range(N)]
dist = [-1]*N
dist[0] = 0

deq = deque()
#deq.append(ukv[0][2:])
deq.append([1])

step = 0
while deq[0]:
#    print('deq:', deq)
    nextvs = []
    currvs = deq.popleft()
    for v in currvs:
        for nv in ukv[v-1][2:]:
            if dist[nv-1] == -1:
                dist[nv-1] = step+1
                nextvs.append(nv)
    deq.append(nextvs)
    step += 1

res = [[val1, val2] for val1, val2 in zip(range(1, N+1), dist)]
for a in res:
    print(*a)








Measured memory_bytes: 6132
#ABC096-C
h,w = map(int,input().split())
grid = [input() for _ in range(h)]

def grid_search(x,y,grid):
    now = grid[x][y]
    flg = True
    #上下左右を見る
    if now == '#':
        flg = False
        
        if x+1<=h-1 and grid[x+1][y] == '#':
            flg = True
        elif x-1 >= 0 and grid[x-1][y] == '#':
            flg = True
        elif y+1 <= w-1 and grid[x][y+1] == '#':
            flg = True
        elif y-1 >= 0 and grid[x][y-1] == '#':
            flg = True
        else:
            flg = False
            
        if not flg:
            return False
        
    return True
flg = True    
for i in range(h):
    for j in range(w):
        if not grid_search(i,j,grid) and flg:
            print('No')
            flg = False
            break
if flg:
    print('Yes')
            
        

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

signed main(){

  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
    if(a[i] == 0){
      cout << 0 << endl;
      return 0;
    }
  }

  __int128_t res = 1;
  for(int i = 0; i < n; i++){
    res *= a[i];
    if(res > (int)1e18){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << (int)res << endl;

  return 0;
}


Measured memory_bytes: 4060
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

int main(){
	int x1,y1,x2,y2,n,xf=1,yf=1,x,y;
	scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
	if(x1>x2)swap(x1,x2),xf=-1;
	if(y1>y2)swap(y1,y2),yf=-1;
	vector<pair<int,int>>v;
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y);
		if(x1<=x&&x<=x2 && y1<=y&&y<=y2)v.emplace_back(x*xf,y*yf);
	}
	sort(v.begin(),v.end());
	vector<int>d(v.size(),1<<30);
	for(auto &e:v)n=e.second,*lower_bound(d.begin(),d.end(),n)=n;
	n=lower_bound(d.begin(),d.end(),1<<30)-d.begin();
	printf("%.9f\n",100.0*(x2-x1+y2-y1)-20*n+5*(n+(n>=min(x2-x1,y2-y1)+1))*3.1415926536);
}

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

using namespace std;
#define MAX 1000000
typedef unsigned long long ULL;

void process();
int main(){
    int N;
    int data;
    int *dataSet;
    int i,j,max;
    cin >> N;
    dataSet = new int[MAX+1];
    max = 0;
    for(i=0;i<=MAX;i++){
        dataSet[i] = 0;
    }
    for(i=0;i<N;i++){
        cin >> data;
        if(max < data){
            max = data;
        }
        dataSet[data]++;
    }
    for(i=0;i<=max;i++){
        if( dataSet[i] != 0){
            for(j=i*2;j<=max;j+=i){
                if( dataSet[j] > 0){
                    dataSet[j] = -1;
                }
            }
        }
    }
    int count = 0;
    for(i=0;i<=max;i++){
        if( dataSet[i] == 1){
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 7540
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ss second
#define ff first
#define pb push_back
int main(){
    ios_base::sync_with_stdio(0);
    string x;
    cin>>x;
    if(x[x.size()-1]=='3'){
        cout<<"bon";
        return 0;
    }
    else if(x[x.size()-1]=='0'||x[x.size()-1]=='1'||x[x.size()-1]=='6'||x[x.size()-1]=='8'){
        cout<<"pon";
    }
    else{
        cout<<"hon";
    }
}



Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
#define pb push_back

void solve(){
    int n, a, b; cin >> n >> a >> b;
    int res = min(n*a, b);
    cout << res << endl;
}

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

Measured memory_bytes: 256
#include <stdio.h>

int check(int n){
  if(n/10000%10 == n%10  &&  n/1000%10 == n/10%10)
    return 1;
  else
    return 0;
}

int main(){
  int a, b;  scanf("%d %d", &a, &b);

  int ans = 0;
  for(int i=a; i<=b; i++)
    ans = ans + check(i);

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define all(v) v.begin(),v.end()
#define mod 1000000007
#define mx 1000002
mt19937 myrand(time(0));

int n,m,k;
string str[10];


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    cin>>n>>m>>k;
    for(int i=0;i<n;i++) cin>>str[i];
    int tot=1<<(n+m);
    int ans=0;
    for(int i=0;i<tot;i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)) continue;
            for(int l=0;l<m;l++){
                if(i&(1<<(n+l))) continue;
                //debug()<<imie(j)imie(l);
                if(str[j][l]=='#') cnt++;
            }
        }
        if(cnt==k) ans++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3636
n, a, b = map(int, input().split())
if n == 1:
    if a != b:
        print(0)
        exit()
    else:
        print(1)
        exit()

min_  = a + a*(n-2) + b
max_ = a + b*(n-2) + b

print(max(0, max_-min_+1))


Measured memory_bytes: 2940
//2020年4月17日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>
#include <iterator>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }

namespace {
    // printElems(&a[0], &a[n]);　みたいな感じで使う。
    void printElems(const int* begin, const int* end)
    {
        for (const int* p = begin; p != end; ++p) {
            std::cout << *p << ' ';
        }
        std::cout << std::endl;
    }
}

#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n+1; i++)
#define repr(i,n) for(int i=n-1; i>=0; i--)
#define repr1(i,n) for(int i=n; i>0; i--)
#define FOR(i,j,n) for(int i=j; i < n; i++)
#define souatari(i,j,n) rep1(i,n-1)rep(j,i)
#define souatari1(i,j,n) for(int i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
const ll BIG = 10000000000000000;

int clist[15];
int alist[15][15];

int main(){
    int n,m,x;
    cin >> n >> m >> x;
    rep(i,n){
        cin >> clist[i];
        rep(j,m) cin >> alist[i][j];
    }
    int ans = inf;
    rep(itr,1<<n){
                    int anstmp = 0;
            int atmp[15];
            rep(_,15) atmp[_]=0;

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

            if((itr&1<<i)){
                rep(tmp,m) atmp[tmp]+= alist[i][tmp];
                anstmp+=clist[i];
            }}
            bool flag = true;
            rep(_,m) if(atmp[_]<x) flag = false;
            if(flag) ans = min(ans,anstmp);

    }

    if(ans == inf){prints(-1);}
    else{prints(ans);}




	return 0;
}



Measured memory_bytes: 3636
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define int long long
using namespace std;
using P = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;

class UnionFind {
public:
  VI par, rank, num;
  UnionFind(int n) {
    par = VI(n); iota(par.begin(), par.end(), 0);
    rank = VI(n, 0);
    num = VI(n, 1);
  }
  int find(int x) {
    if (par[x] == x) {
      return x;
    } else {
      return par[x] = find(par[x]);
    }
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) { return; }
    if (rank[x] < rank[y]) {
      par[x] = y;
      num[y] += num[x];
    } else {
      par[y] = x;
      num[x] += num[y];
      if (rank[x] == rank[y]) { rank[x]++; }
    }
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  int count(int x) {
    return num[par[x]];
  }
};

int N, K, L;

signed main() {
  cin >> N >> K >> L;
  UnionFind uf1(N);
  REP (i, K) {
    int p, q;
    cin >> p >> q; p--; q--;
    uf1.unite(p, q);
  }
  UnionFind uf2(N);
  REP (i, L) {
    int r, s;
    cin >> r >> s; r--; s--;
    uf2.unite(r, s);
  }

  map<P, int> ans;
  REP (i, N) {
    ans[P(uf1.find(i), uf2.find(i))]++;
  }
  REP (i, N) {
    cout << ans[P(uf1.find(i), uf2.find(i))] << endl;
  }
}


Measured memory_bytes: 21120
n, k, q = map(int, input().split())
a_l = [ int(input()) for _ in range(q) ]

d = {}
for a in a_l:
    if a in d.keys():
        d[a] += 1
    else:
        d[a] = 1
for i in range(n):
    if i+1 in d:
        if k-(q-d[i+1])>0:
            print('Yes')
        else:
            print('No')
    else:
        if k-q > 0:
            print('Yes')
        else:
            print('No')

Measured memory_bytes: 16488
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main(){
  int x,a;
  cin >> x >> a;
  if (x < a){
    cout << "0\n";
  }
  else{
    cout << "10\n";
  }
  return 0; 
}

Measured memory_bytes: 256
n = int(input())
p = input().split()
p = [int(p_) for p_ in p]

count = 0
for i in range(1,n-1):
    if((p[i]>p[i-1] and p[i+1]>p[i])or(p[i]<p[i-1] and p[i+1]<p[i])):
        count += 1
print(count)

Measured memory_bytes: 3060
//code by lynmisakura.wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int CountOdd,Count4,Count2;
int main(void){
    ll n;scanf("%lld",&n);
    for (int i = 0; i < n; ++i)
    {
        int x;cin >> x;
        if(x %2 == 1){
            CountOdd++;
        }else if(x %4 == 0){
            Count4++;
        }else Count2++;
    }
    if(Count2 <= 1){
        if(Count4 >= (CountOdd + Count2) - 1)cout << "Yes" << endl;
        else cout << "No" << endl;
    }else{
        if(Count4 >= CountOdd)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}


Measured memory_bytes: 256
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << 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; }

//最大公約数と最小公倍数
ll gcd(ll a, ll b) {
    if(b==0)return a;
    return gcd(b, a%b);
}

ll lcm(ll a, ll b) {
  ll g = gcd(a, b);
  return a/g*b;
}

vector<vector<long long> > comb(int n) {
  vector<vector<long long> > v(n + 1,vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string x,y;cin >> x >> y;
    if (x<y) cout << "<" << endl;
    else if (x>y) cout << ">" << endl;
    else if (x==y) cout << "=" << endl;
  
    return 0;
}



Measured memory_bytes: 256
n = int(input())
points = []
points.append([0, 0, 0])
for i in range(n):
    points.append([i for i in map(int, input().split())])
# print(points)
can = True
for i in range(len(points)-1):
    move_n = points[i+1][0] - points[i][0]
    dist = abs(points[i+1][1] - points[i][1]) + abs(points[i+1][2] - points[i][2])
    if move_n < dist or dist % 2 != move_n % 2:
        can = False 
        break

if can:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 25592
#include <iostream>
#include <string>
using namespace std;
int main() {
	int x, y;
	while (1) {
		cin >> x >> y;
		if (x == 0 && y == 0) {
			break;
		}
		else if (x <= y) {
			cout << x << " " << y << endl;
		}
		else {
			cout << y << " " << x << endl;
		}

	}
}




Measured memory_bytes: 3084
from math import gcd
from functools import reduce

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

num = lcm_list(A)
ans = 0
for a in A:
    ans += (num * pow(a, mod-2, mod))%mod
ans %= mod

print(ans)


Measured memory_bytes: 74288
#include<bits/stdc++.h>
using namespace std;
int main(){
  	int n,a,ans;
  	cin>>n>>a;
  	int l=a,r=a+n-1,eat;
  	if(r<=0)
    	eat=r;
  	else if(l>=0)
    	eat=l;
  	else eat=0;
 	ans=(r+l)*(r-l+1)/2-eat;
  	cout<<ans;
  	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int n,  tmp=0, res=0;
string x;
int t[1000];
struct pr
{
    string s;
    int x;
};
int main()
{
    cin>>n;
    struct pr a[1000];
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].s>>a[i].x;
    }
    cin>>x;
    for(int i=1; i<=n; i++)
    {
        if(a[i].s==x)
        {
            tmp=i;
            break;
        }
    }
    for(int i=tmp+1; i<=n; i++)
    {
        res+=a[i].x;
    }
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1, 1]
f_inv = [1, 1]
inv = [0, 1]

def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)

def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def main():
    N,K,*A = map(int, read().split())

    prepare(N+5, MOD)

    A.sort()
    ans = 0
    for i, a in enumerate(A):
        s_i = a * (cmb(i, K-1, MOD) - cmb(N-i-1, K-1, MOD))
        s_i %= MOD
        ans += s_i
        ans %= MOD

    print(ans)    


if __name__ == "__main__":
    main()


Measured memory_bytes: 20588
import numpy as np

moji = int(input())
suji_10 = moji%100
suji_01 = suji_10%10


if suji_01 == 3:
    print("bon")
if (suji_01 == 0) or (suji_01 == 1) or (suji_01 == 6) or (suji_01 == 8):
    print("pon")
if (suji_01 == 2) or (suji_01 == 4) or (suji_01 == 5) or (suji_01 == 7) or (suji_01 == 9):
    print("hon")


Measured memory_bytes: 27192
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(1, n - 1):
    if p[i - 1]  < p[i] < p[i + 1] or p[i - 1]  > p[i] > p[i + 1]:
        ans += 1
print(ans)


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

public class Main {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		Random rng = new Random();
		for (int i = 0; i < n; i++) {
			int j = rng.nextInt(i + 1);
			a[i] = a[j];
			a[j] = nextInt();
		}
		Arrays.sort(a);
		for (int i = 0, j = n - 1; i < j; i++, j--) {
			int tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
		}
		
		int bad = n;
		for (int i = 0; i < n; i++) {
			if (a[i] <= i) {
				bad = i;
				break;
			}
		}
		
		bad--;
		
		int right = a[bad] - bad - 1;
		int up = 0;
		for (int i = bad + 1; i < n; i++) {
			if (a[i] > bad) {
				up++;
			} else {
				break;
			}
		}
		
		out.println((right | up) % 2 == 0 ? "Second" : "First");
	}

	Main() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Main();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}

Measured memory_bytes: 23552
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  string base = "##";
  for (int i = 0; i < W; i++){
    base += '#';
  }
  cout << base << endl;
  string s;
  for (int i = 0; i < H; i++){
    cin >> s;
    cout << '#' + s + '#' << endl;
  }
  cout << base << endl;
}

Measured memory_bytes: 3620
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 60;
ll C[MAXN+1][MAXN+1];
void Initial()
{
    int i,j;
    for(i=0; i<=MAXN; ++i)
    {
        C[0][i] = 0;
        C[i][0] = 1;
    }
    for(i=1; i<=MAXN; ++i)
    {
        for(j=1; j<=MAXN; ++j)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]);
    }
}
int main() {
    int n , p;
    cin >> n >> p;
    ll odd = 0 , even = 0;
    int x;
    Initial();
    for(int i = 0 ; i < n ; i++) {
        cin >> x;
        if(x % 2) odd++;
        else even++;
    }
    if(p == 0) {
        ll sum1 = ((ll)1 << even);
        ll sum2 = (ll)1;
        for(int i = 1 ; i <= odd ; i++) {
            if(i % 2 == 0) sum2 += C[odd][i];
        }
        cout << sum1 * sum2 << endl;
    }
    else {
        ll sum1 = ((ll)1 << even);
        ll sum2 = 0;
        for(int i = 1 ; i <= odd ; i++) {
            if(i % 2) sum2 += C[odd][i];
        }
        cout << sum1 * sum2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;


public class Main {
	  public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    String n = sc.next();
	    int sn = 0;
	    for(int i = 0; i < n.length(); i++) {
	    	sn += Integer.parseInt(n.substring(i, i+1));
	    }
	    if(Integer.parseInt(n) % sn == 0) {
	    	System.out.println("Yes");
	    } else {
	    	System.out.println("No");
	    }
	}
}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
    using namespace std;
  #define int long long int
    #define endl "\n"
    #define MOD 1000000007
    #define mod 1000000007
    #define M 1000000007
    
    #define pb push_back
    #define take(a,b,c) for(int b=0;b<c;b++) cin>>a[b]
  //  #define mp make_pair
  #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  #define mx 400005
  #define fiint(a,b) memset(a,b,sizeof(a))  
  #define bitcount __builtin_popcount
  #define fori(i,a,b) for(int i=a;i<b;i++)
  #define ford(i,a,b) for(int i=a;i>=b;i--)
  #define debug(x) cout<<x<<endl;
  #define cases(t) int t; cin>>t; while(t--)
  #define inf1 INT_MAX
  #define all(a) a.begin(),a.end()
  #define vec vector<int>
  #define pii pair<int,int>
  #define plii pair<int,int>
  #define pint pair<int,int>
  #define ff first
  #define ss second
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define sz(x) (int)x.size()
#define PI                    3.14159265359

bool prime[10000001];

void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}

signed  main() 
{ 
	int n,w;cin>>n>>w;
	vector <int>v[n+1];
	int a,b;
	int max_v =0;
	fori(i,1,n+1)
	{cin>>a>>b;v[i].pb(a);v[i].pb(b); max_v += v[i][1] ;}
	vector<int> dp (max_v + 1 , 1e9  + 3) ;
	dp[0]=0;
	fori(i,1,n+1)
		ford(j,max_v , 0 )
		    if (  dp[j] < 1e9 + 3 &&   j + v[i][1] <= max_v )
		    	dp [ j + v[i][1] ]	 = min ( dp[j] + v[i][0] , dp[j + v[i][1]  ]   ) ; 
		
		    int ans=-1;
		    fori(i,0,max_v + 1)
		    	if(  dp[i] <= w   )
					ans=i;
				cout<<ans<<endl; 

	
		
	
}




 


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

class ABC125B{
    public static void Main(){
        var N = int.Parse(Console.ReadLine());
        var V = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var C = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var ans = 0;
        for(int index = 0;index < V.Count();index++){
            ans += V[index]>C[index]?V[index]-C[index]:0;
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11348
n = gets.to_i
h = Hash.new {|h, k| h[k] = 0}
gets.split.map(&:to_i).each {|x| h[x] += 1}

c = 0
h.each_pair do |k, v|
  if k < v
    c += v - k
  elsif k > v
    c += v
  end
end

puts c

Measured memory_bytes: 14468
#include <cstdio>
#include <cstring>

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      char s[10];
      scanf("%s", s);
      if (strcmp(s, "snuke") == 0) {
        printf("%c%d\n", 'A' + j, i + 1);
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,s,ans,a[200005],dp[200005];
int main(){
cin>>n>>s;
for(int k=1;k<=n;k++){
   cin>>a[k];
}
dp[1]=0;
dp[2]=abs(a[2]-a[1]);
for(int k=3;k<=n;k++){
        dp[k]=INT_MAX;
for(int i=1;i<=s;i++){
        if(k-i==0)
        break;
   int t=abs(a[k-i]-a[k])+dp[k-i];
dp[k]=min(dp[k],t);
}
 
}
cout<<dp[n];
return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define REP(asd, fgh) for(int asd = 0; asd < fgh; asd++)
int n;
int cnt;
vector<int> S;

void merge(vector<int> &A, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  vector<int> L(n1+1), R(n2+1);
  REP(i, n1){
    L[i] = A[left + i];
  }
  REP(i, n2){
    R[i] = A[mid + i];
  }
  L[n1] = INT_MAX/2;
  R[n2] = INT_MAX/2;
  int i = 0, j = 0;
  for(int k = left; k < right; k++){
    cnt++;
    if(L[i] <= R[j]){
      A[k] = L[i];
      i++;
    }else{
      A[k] = R[j];
      j++;
    }
  }

}

void mergeSort(vector<int> &A, int left, int right){
  if(left + 1 < right){
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int main(void){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  S.resize(n);
  REP(i, n) cin >> S[i];
  mergeSort(S, 0, n);
  REP(i, n-1){
    cout << S[i] << " ";
  }
  cout << S[n-1] << endl;
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 5076
#include<cstdio>

const int N=305;

int n,k,mod,c[N][N],f[N][N],sum[N][N];

int main(){
	scanf("%d%d%d",&n,&k,&mod);
	for(int i=0;i<=n;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
	}
	for(int j=k;j>=0;--j){
		f[1][j]=1;
		sum[1][j]=(sum[1][j+1]+f[1][j])%mod;
	}
	for(int i=2;i<=n+1;++i){
		for(int j=0;j<=k;++j){
			for(int t=1;t<=i-1;++t){
				f[i][j]=(f[i][j]+1ll*c[i-2][t-1]*f[i-t][j]%mod*sum[t][j+1]%mod)%mod;
			}
		}
		for(int j=k;j>=0;--j){
			sum[i][j]=(sum[i][j+1]+f[i][j])%mod;
		}
	}
	printf("%d\n",f[n+1][0]);
	return 0;
}

Measured memory_bytes: 1280
#import<atcoder/all>
#define F){return
using I=int;I n,x,y;I o(I a,I b F a<b?b:a;}I e(F-1;}main(){auto&c=std::cin>>n>>y;atcoder::segtree<I,o,e>s(n);for(;x<n;s.set(x++,y))c>>y;for(;c>>n>>x>>y;--n?printf("%d ",--n?s.max_right(x,[&](I i F i<y;})+1:s.prod(x,y)):(s.set(x,y),0))x--;}

Measured memory_bytes: 6176
#include <stdio.h>
#include <math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
using namespace std;






int main(){
    int n,m;
    int a[25][25];
    cin>>n>>m;
    for(int i=0;i<25;i++){
        for(int t=0;t<25;t++){
            a[i][t]=-1;
        }
    }
    char q;
    for(int i=0;i<m;i++){
        int b,c,d,e;
        cin>>b>>q>>c>>q>>d>>q>>e;
        a[b][c]=d;
        a[c][b]=e;
    }
    int s,g,gold,p;
    cin>>s>>q>>g>>q>>gold>>q>>p;
    bool j=true;
    int count=0;
    while(j){
        j=false;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int t=1;t<=n;t++){
                if(a[i][k]==-1 || a[k][t]==-1){continue;}
                if(a[i][t]==-1){a[i][t]=a[i][k]+a[k][t]; j=true; continue;}
                if(a[i][t]>a[i][k]+a[k][t]){a[i][t]=a[i][k]+a[k][t]; j=true;}
            }
        }
    }
        count++;
    }
    cout<<gold-p-a[s][g]-a[g][s]<<endl;
    //cout<<count<<endl;
    
    
    return 0;
}


Measured memory_bytes: 3052