akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a;}

long long lcm(long long a, long long b) { return a / gcd(a,b) * b;}

int f(int x){
    int res = 0; 
    
    while(x % 2 == 0){
        x /= 2;
        res++;
    }
    
    return res;
}


int main(void){
    // Your code here!
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    
    for(int i = 0; i < n; i++){
        
        if(a[i] % 2 == 1){
            cout << 0 << endl;
            return 0;
        }
        
        a[i] /= 2;
    }
    
    int t = f(a[0]);
    
    for(int i = 0; i < n; i++){
        
        if(f(a[i]) != t){
            cout << 0 << endl;
            return 0;
        }
        
        a[i] = a[i] >> t;
    }
    
    m = m >> t;
    
    long long l = 1;
    
    for(int i = 0; i < n; i++){
        l = lcm(l, a[i]);
        
        if(l > m){
            cout << 0 << endl;
            return 0;
        }
    }
    
    m /= l;
    
    int ans = (m + 1) / 2;
    cout << ans << endl;
    return 0;
    
}


Measured memory_bytes: 640
// 2020-07-31 09:01:12
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(ALL(a));
  int lim = 1e6+10;
  vector<int> appear(lim, 0), sieve(lim, 0);
  set<int> ok;
  rep(i, n) {
    appear[a[i]]++;
    if(sieve[a[i]]) continue;
    ok.insert(a[i]);
    for(int x = a[i]; x <= lim; x += a[i]) {
      sieve[x] = 1;
    }
  }
  int ans = 0;
  for(int x : ok) {
    if(appear[x] == 1) ans++;
  }
  cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 21060
n=int(input())
dp=[[0]*n,[0]*n,[0]*n]

for i in range(n):
    a,b,c=map(int,input().split())
    if i==0:
        dp[0][0]=a
        dp[1][0]=b
        dp[2][0]=c
    else:
        dp[0][i]=max(dp[1][i-1],dp[2][i-1])+a
        dp[1][i]=max(dp[0][i-1],dp[2][i-1])+b
        dp[2][i]=max(dp[0][i-1],dp[1][i-1])+c

#print(dp)
print(max(dp[0][-1],dp[1][-1],dp[2][-1]))



Measured memory_bytes: 52404
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
typedef pair<int,int> P;
int n,m,par[55]={},ans=0,a[55]={},b[55]={};
int find(int x) {
  if(par[x]==x) {
    return x;
  }
  return par[x]=find(par[x]);
}
bool same(int x,int y) {
  return find(x)==find(y);
}
void unit(int x,int y) {
  x=find(x),y=find(y);
  if(x!=y) {
    par[x]=y;
  }
}
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    cin >> a[i] >> b[i];
    a[i]--,b[i]--;
  }
  for(int i=0; i<m; i++) {
    for(int j=0; j<n; j++) {
      par[j]=j;
    }
    for(int j=0; j<m; j++) {
      if(i!=j) {
        unit(a[j],b[j]);
      }
    }
    set<int> s;
    for(int i=0; i<n; i++) {
      s.insert(find(i));
    }
    if(s.size()!=1) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
N ,K = map(int,input().split(" "))
if N % 2 == 1:
    if K <= ((N - 1) // 2) + 1:
        print("YES")
    else:
        print("NO")

else:
    if K <= ((N - 2) // 2) + 1:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 3316
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
ll gcd(ll a,ll b){
    if(a%b==0)return b;
    return gcd(b,a%b);
}

int main() {
    ll m,d;
    std::cin >> m>>d;
    ll cnt = 0;
    
    for (int j = 1; j <= m; j++) {
        for (int i = 10; i <= d; i++) {
            if( j == (i/10)*(i%10) && (i/10)>=2 && (i%10)>=2){
                cnt++;
            }    
        }
    }
    std::cout << cnt << std::endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int n; 
    long long int max=0, stool_height=0, a;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a;
        if(a > max)
            max = a;
        else
            stool_height += max - a;
    }
    cout<<stool_height<<endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
const ll INF = 1LL << 60;

int main(){
	int n, d, x; cin >> n >> d >> x;
	int sum = x;
	for( int i = 0; i < n; ++i ){
		int tmp; cin >> tmp;
		sum += (d - 1)/tmp + 1;
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define strall(v) (v).cbegin(),(v).cend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}




int main(){
  
  int x;
  cin >> x;
  vector<bool> e(x+1,false);
  e[1] = true;
  int ans = 0;
  for(int i=2;i*i<=x;i++){
    int tmp=i*i;
    while(tmp<=x){
      e[tmp] = true;
      tmp*=i;
      
    }
  }
  
  for(int i=1;i<=x;i++){
    if(e[i]) ans = i;
  }
  cout << ans << endl;
  
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	string ans="No"s;
	for(int i=0;i<=n;i+=4){
		for(int j=0;i+j<=n;j+=7){
			if(i+j==n)ans="Yes"s;
		}
	}
	cout<<ans<<"\n"s;
}

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

using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int N;
ll p_c[1001];
bool prime[1001];
ll ans = 1;

void init(int N) {
  for(int i = 2; i <= N; i++) {
    if(prime[i])continue;
    for(int j = i+i; j <= N; j+=i) prime[j] = true;
  }
}
      

int main() {
  cin >> N;
  init(N);
  for(int i = 2; i <= N; i++) {
    for(int j = 2; j <= i; j++) {
      if(prime[j])continue;
      int tmp = i;
      while(tmp % j == 0) {
	  p_c[j]++;
	  tmp /= j;
      }
      if(tmp == 1) break;
    }
  }

  for(int i = 0; i < 1001; i++) {
    if(p_c[i] > 0) ans = ans * (p_c[i]+1) % mod;
  }

  cout << ans % mod <<endl;
}
    

  
  


Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define int long long
#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 << '\n'; }
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 fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
const double EPS = 1e-6 ; 
signed main(){
    fastio
    int n ;
    cin >> n ; 
    vector<int> v(n) ; 
    for(int i = 0; i < n; i++){
        cin >> v[i] ; 
    }
    int ans = INF ; 
    for(int i = 1; i <= 100; i++){
        int sum = 0 ; 
        for(int j = 0; j < n; j++){
            sum += (v[j] - i)*(v[j] - i) ;
        }
        ans = min(ans , sum) ; 
    }
    cout << ans << endl;
    return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

int main(void)
{
    int N, K;
    cin >> N >> K;

    vector<int> box(N + 1, 0);
    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        box[num]++;
    }

    sort(box.begin(), box.end(), greater<int>());
    int ans = 0;
    for (int i = 0; i < N + 1; i++)
    {
        if (box[i] == 0)
        {
            break;
        }
        else if (K > 0)
        {
            K--;
        }
        else if (K == 0)
        {
            ans += box[i];
        }
    }
    cout << ans << endl;
    return (0);
}

Measured memory_bytes: 1024
#include<iostream>

#define S 16
int num[S+1][S+1];
int a, b;
int n;

void print(){
	int i, j;
	for( j = 1; j <= b; j++ ){
		for( i = 1; i <= a; i++ ){
			std::cout << num[i][j] << " ";
		}
		std::cout << std::endl;
	}
	return;
}

void init(){
	int i, j;
	for( i = 1; i <= S; i++ ){
		for( j = 1; j <= S; j++ ){
			num[i][j] = -1;
		}
	}
	num[1][1] = 1;
	return;
}

int input(){
	int i, x, y;
	init();
	std::cin >> a >> b;
	if( a == 0 || b == 0 ){ return 0; }
	std::cin >> n;
	for( i = 0; i < n; i++ ){
		std::cin >> x >> y;
		num[x][y] = 0;
	}
	return (a+b);
}

int get(int i, int j){
	if( num[i][j] >= 0 ){ return num[i][j]; }
	if( i == 0 || j == 0 ){ return (num[i][j] = 0); }
	num[i][j] = get(i-1, j) + get(i, j-1);
	return num[i][j];
}

int main(){
	while( input() > 0 ){ std::cout << get(a, b) << std::endl; }
	return 0;
}

Measured memory_bytes: 3084
a,b,x = map(int,input().split())
h = x/(a*a)

import math

def f1(d,H,h):
    if h == H:
        return 90
    if h > H/2:
        return math.degrees(math.atan(d/(2*(H-h))))
    else:
        return math.degrees(math.atan((2*d*h)/(H*H)))

print(str.format('{0:.10f}', 90 - f1(a,b,h)))


Measured memory_bytes: 3060
n=int(input())
dic={}
for i in range(n):
  hoge=list(input())
  hoge.sort()
  hoge=str(hoge)
  if(hoge in dic):
    dic[hoge]+=1
  else:
    dic[hoge]=1


ans=0
for i in dic.values():
  ans+=i*(i-1)//2
print(ans)

Measured memory_bytes: 21988
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,x;
  cin>> a>> b>> c>> x;
  int count = 0;
  for(int i=0; i<=a; i++){
    for(int j=0; j<=b; j++){
      for(int k=0; k<=c; k++){
        if(i*500 + j*100 + k*50 == x){
          count++;
        }

      }
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
str_arr = gets.chomp!.split(" ")

a = str_arr[0].to_i
b = str_arr[1].to_i
c = str_arr[2].to_i

hash1 = {"a"=>a, "b"=>b, "c"=>c}

ab = (str_arr[0] + str_arr[1]).to_i
ba = (str_arr[1] + str_arr[0]).to_i
bc = (str_arr[1] + str_arr[2]).to_i
cb = (str_arr[2] + str_arr[1]).to_i
ac = (str_arr[0] + str_arr[2]).to_i
ca = (str_arr[2] + str_arr[0]).to_i
hash2 = {"ab"=>ab, "ba"=>ba, "bc"=>bc, "cb"=>cb, "ac"=>ac, "ca"=>ca}
arrrr = [ab,ba,bc,cb,ac,ca]
maxnum = [ab,ba,bc,cb,ac,ca].max
hash2.select!{|key,val|
  val == maxnum
}
if hash2.length == 1 then
  hash2.each{|key,val|
    puts val + hash1[("abc".delete(key))]
  }
else
  max__arr = []
  hash2.each{|key,val|
    sum = val + hash1[("abc".delete(key))]
    max__arr.push(sum)
  }
  puts max__arr.max
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define N 100
#define INF 1e9 + 5
#define LINF 1e18 + 5

using namespace std;
using ll = long long;
string a, b;
vector<vector<int>> memo;
int solve(int y, int x)
{

    if (x == 0 || y == 0)
        return memo[y][x] = 0;
    int& best = memo[y][x];
    if(best!=-1) return best;
    best = max(solve(y-1,x), solve(y,x-1));
    if(a[y]==b[x])
        best = max(best, solve(y-1,x-1)+1);
    return best;
}
/*
 abyxb
a10000 
x11122
y11222
b12223

*/
int main()
{
    cin >> a >> b;
    a = "$" + a;
    b = "$" + b;
    memo.resize(a.length()+1, vector<int>(b.length()+1,-1));
    //memo[0][0] = 0;
    int maxlenth = solve(a.length() - 1, b.length() - 1);
    for (int y = 0; y < a.length(); y++)
    {
        for (int x = 0; x < b.length(); x++)
        {
            //cout << memo[y][x];
        }
        //cout << endl;
    }

    int x = b.length() - 1, y = a.length() - 1;
    string t = "";
    while (x > 0 && y > 0)
    {
       if(memo[y][x]!=memo[y-1][x]&&memo[y][x]!=memo[y][x-1]){
           t = a[y]+t;
           x--;y--;
       }else{
           if(memo[y][x]==memo[y-1][x]){
               y--;
           }else{
               x--;
           }
       }
    }
    // cout<<maxlenth<<endl;
    cout << t;
    return 0;
}

Measured memory_bytes: 35968
#[allow(dead_code)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(dead_code)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(dead_code)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        aa: [u64; n]
    }
    let mut aa: Vec<_> = aa.iter().enumerate().collect();

    // desc
    aa.sort_by(|&(_li, lv), &(_ri, rv)| {
        rv.cmp(&lv)
    });

    let (maxi, maxv) = aa[0];
    let (_secmaxi, secmaxv) = aa[1];

    for i in 0..n {
        let v = if i == maxi {
            secmaxv
        } else {
            maxv
        };
        println!("{}", v);
    }

}


Measured memory_bytes: 13820
import string

INF = float('inf')

n = int(input())
ss = [input() for _ in range(n)]

ans_d = {c: INF for c in string.ascii_lowercase}  # AtoZ
for s in ss:
    d = {c: 0 for c in string.ascii_lowercase}  # AtoZ
    for c in s:
        d[c] += 1
    for c in string.ascii_lowercase:
        ans_d[c] = min(ans_d[c], d[c])

ans = ''
for c in string.ascii_lowercase:
    ans += c * ans_d[c]
print(ans)

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

int main() {
	int H, W;
	cin >> H >> W;
	while (H != 0 && W != 0) {
		for (int i = 0; i < W; i++)
			cout << "#";
		cout << endl;
		for (int j = 0; j < H - 2; j++) {
			cout << "#";
			for (int k = 0; k < W - 2; k++) {
				cout << ".";
			}
			cout << "#" << endl;
		}
		for (int l = 0; l < W; l++)
			cout << "#";
		cout << endl;
		cout << endl;
		cin >> H >> W;
	}
}


Measured memory_bytes: 3064
#include <stdio.h>
  
#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
  
int in()
{
    int n = 0, c = gc();
    do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
    return n;
}
  
void skip(int k) { while (k--) gc(); }
  
void out(int n)
{
    int i;
    char ob[20];
  
    if (!n) { pc('0'); return; }
    i = 0; while (n) ob[i++] = n%10 + '0', n/=10;
    while (i--) pc(ob[i]); 
}
  
int que[1500005]; int top, end;
  
int main()
{
    int n, i, t;
    char op;
  
    n = in(); top = 0, end = 1;
    while (n--) {
        if (gc() == 'i') {
            skip(6);
            que[end++] = in();
        } else {
            skip(5);
            op = gc();
            if (op == 'L') {
                skip(4);
                top++;
            } else if (op == 'F') {
                skip(5);
                end--;
            } else {
                que[top] = t = in();
                i = end; while (que[--i] != t);
                if (i > top) {
                    if (end - i < i - top) {
                        while (++i < end) que[i-1] = que[i];
                        end--;
                    } else {
                        while (--i > top) que[i+1] = que[i];
                        top++;
                    }
                }
            }
        }
    }
    i = end-1; out(que[i--]);
    while (i > top) pc(' '), out(que[i--]);
    pc('\n');
    return 0;
}



Measured memory_bytes: 5436
#include <bits/stdc++.h> 
using namespace std; 
#define ll long long int 
#define pb push_back
#define vv vector<ll>
#define MAX 105000
#define fr(i,x) for(int i=0;i<x;i++)
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};

bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    
    if(a.first == b.first) return a.second<b.second;
    return (a.first < b.first); 
}
ll ar[MAX];
void divisor(){
    for (int i = 1; i <= MAX; i++)
    {
        for (int j = i; j <= MAX;j+=i)
        {
            ar[j]++;
            
        }
        
        
    }
    
}
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    
    ll n,x,min,c = 1;
    cin >> n;
    cin >> min;
    for (int i = 1; i < n; i++)
    {
        cin >> x;
        if(x <= min) {c++;min = x;}
    }
    cout << c << endl;
    
        
}

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

int main() {
  unsigned int K;
  cin >> K;

  if(K % 2 == 0 || K % 5 == 0) {
    cout << -1 << endl;
    return 0;
  }

  unsigned int i = 0;
  unsigned int ai = 0;
  while(true) {
    i++;
    ai = (ai * 10 + 7) % K;
    if (ai == 0) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>

int main(int argc, const char * argv[]){
    int a, b;
    char op;
    while (1) {
        scanf("%d %c %d",&a,&op,&b);
        switch (op) {
            case '+': printf("%d\n", a+b);
                break;
            case '-': printf("%d\n", a-b);
                break;
            case '*': printf("%d\n", a*b);
                break;
            case '/': printf("%d\n", a/b);
                break;
            default:
                goto endloop;
        }
    }
endloop: ;
}


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

using namespace std;
int main(void)
{
    short int K,A,B,count=0;
    cin>>K;
    cin>>A>>B;

    for(int i=A;i<=B;i++)
    {
        if(i%K==0)
        {
            count=1;
            break;
        }
    }


    if(count==1) cout<<"OK"<<endl;
    else cout<<"NG"<<endl;

}

Measured memory_bytes: 3584
def solve():
    N,M = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]
    total = sum(A)
    threshold = float(total) / (4*M)
    cnt = 0
    for num in A:
        if num >= threshold:
            cnt += 1
    if cnt >= M:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
typedef pair<long,long> pii;
#define F first
#define S second
bool prime[100010];
vector<long long> v;
int main(){
    long long m,a,b;
    rep(i,100010) prime[i]=true;
    rep(i,2) prime[i]=false;
    for(int i=2;i*i<100010;i++){
        if(prime[i]){
            for(int j=i*i;j<100010;j+=i){
                prime[j]=false;
            }
        }
    }
    rep(i,100010){
        if(prime[i]) v.push_back(i);
    }
    while(cin>>m>>a>>b,m||a||b){
        pii ans(0,0);
        rep(i,v.size()){
            if(v[i]>m) break;
            rep(j,i+1){
                if(v[i]*v[j]>m) break;
                if(a*v[i]<=b*v[j]){
                    if(ans.F*ans.S<v[j]*v[i]){
                        ans=pii(v[j],v[i]);
                    }
                }
            }
        }
        cout<<ans.F<<" "<<ans.S<<endl;
    }
}

Measured memory_bytes: 1436
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int l1,l2,r1,r2;
    cin>>l1>>l2>>r1>>r2;
    if (l1+l2>r1+r2)
        cout<<"Left"<<endl;
    else if(l1+l2==r1+r2)
        cout<<"Balanced"<<endl;
    else
        cout<<"Right"<<endl;
    return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())

Hcnt = [0] * H
Wcnt = [0] * W

L = [list(input()) for _ in range(H)]

for i, s in enumerate(L):
  for j, c in enumerate(s):
    if c == "#":
      Hcnt[i] += 1
      Wcnt[j] += 1

for i, s in enumerate(L):
  if Hcnt[i] <= 0:
    continue
  for j, c in enumerate(s):
    if Wcnt[j] > 0:
      print(c, end="")
  print()


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

int main(){
  int n;
  cin>>n;
  vector<long> v(n+1);
  for(int i=1;i<=n;i++)
    cin>>v[i];
  v[0]=0;
  for(int i=1;i<=n;i++)
    v[i]+=v[i-1];
  long dp[n+1][n+1];
  for(int i=0;i<=n;i++)
  {
    for(int j=0;j<=n;j++)
      dp[i][j]=1e18;
  }
  for(int i=0;i<=n;i++)
    dp[i][i]=0;
  for(int len=2;len<=n;len++)
  {
    for(int i=1;i+len-1<=n;i++)
    {
      int j=i+len-1;
      for(int k=i;k<j;k++)
      	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+v[j]-v[i-1]);
      
    }
  }
    
  cout<<dp[1][n];
  
}

Measured memory_bytes: 1536
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>

using namespace std;

template<typename T>
class DListNode {
    public:
        T value;
        DListNode<T> *prev;
        DListNode<T> *next;
        DListNode(): prev(nullptr), next(nullptr) {};
};

template<typename T>
class DList {
    public:
        DListNode<T> *first;
        DListNode<T> *last;

        DList():first(nullptr), last(nullptr){};

        void insert(T value){
            DListNode<T> *n = new DListNode<T>();
            n->next = this->first;

            if(this->first){
                this->first->prev = n;
            }else{
                this->last = n;
            }

            this->first = n;
            n->value = value;
        }

        void del(T value){
            DListNode<T> *n = this->first;
            while (n) {
                if(n->value == value){
                    if(n->prev){
                        n->prev->next = n->next;
                    }else{
                        this->first = n->next;
                    }

                    if(n->next){
                        n->next->prev = n->prev;
                    }else{
                        this->last = n->prev;
                    }

                    delete n;
                    break;
                }
                n = n->next;
            }
        }

        void deleteFirst(){
            DListNode<T> *fst = first;
            if(fst->next){
                fst->next->prev = nullptr;
            }else{
                last = nullptr;
            }
            first = fst->next;
            delete fst;
        }

        void deleteLast(){
            DListNode<T> *lst = last;
            if(lst->prev){
                lst->prev->next = nullptr;
            }else{
                first = nullptr;
            }
            last = lst->prev;
            delete lst;
        }

};

int main(int argc, char const* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, key;
    string cmd;
    DList<int> l;

    cin >> n;
    for (int i = 0; i < n ; i++) {
        cin >> cmd;
        if (cmd == "insert") {
            cin >> key;
            l.insert(key);
        } else if(cmd == "delete") {
            cin >> key;
            l.del(key);
        } else if(cmd == "deleteFirst"){
            l.deleteFirst();
        } else if(cmd == "deleteLast"){
            l.deleteLast();
        }
    }

    DListNode<int> *v = l.first;
    while (v) {
        cout << v->value;
        v = v->next;
        if(v){
            cout << " ";
        }
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 34380
N, M = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(N)]
data.sort()

honsu=0
cost=0
for i in range(N):
  honsu+=data[i][1]
  cost+=data[i][0]*data[i][1]
 
  if honsu>M:
    cost=cost-((honsu-M)*data[i][0])
    print(cost)
    exit()
print(cost)

Measured memory_bytes: 27880
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  ll n;
  cin >> n;
  ll ans = sqrt(n);
  cout << ans*ans << endl;
  return 0;
}

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

typedef long long ll;
const int N = 2e5 + 7;
ll p[N][2];
int n;

ll max_Manhattan(){
	ll ans=0;
	for (int s=0;s<(1<<2);++s){
		ll mx=-1e18,mn=1e18;
		for (int i=0;i<n;++i){
			ll tmp=0;
			for (int j=0;j<2;++j)
				tmp+=(s&(1<<j))?p[i][j]:-p[i][j];
			mx=max(mx,tmp),mn=min(mn,tmp);
		}
		ans=max(ans,mx-mn);
	}
	return ans;
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%lld %lld", &p[i][0], &p[i][1]);
    ll ans = max_Manhattan();
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 6924
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;

VVI g;
VI visited;
VI sol[2];

void dfs(int u, int it_num) {
	visited[u] = 1;
	for (int v : g[u]) {
		if (!visited[v]) {
			sol[it_num].push_back(v);
			dfs(v, it_num);
			return;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	g = VVI(n);
	for (int i = 0, u, v; i < m; ++i) {
		cin >> u >> v;
		--u; --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	sol[0].clear();
	sol[1].clear();
	visited = VI(n, 0);
	dfs(0, 0);
	dfs(0, 1);
	reverse(sol[1].begin(), sol[1].end());
	cout << sol[0].size() + sol[1].size() + 1<< '\n';
	for (int x : sol[1]) cout << x+1 << ' ';
	cout << 1 << ' ';
	for (int x : sol[0]) cout << x+1 << ' ';
}

Measured memory_bytes: 9976
import java.util.*;

public class Main{
    void solve(){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int dec = 1;
        for(int i = 0; i < n; i++) if(scan.nextInt() % 2 == 0) dec *= 2;
        System.out.println((int)Math.pow(3, n) - dec);
    }
    
    public static void main(String[] args){
        new Main().solve();
    }
}


Measured memory_bytes: 35820
using System;
namespace a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] c = Console.ReadLine().Split();
            int a = int.Parse(c[0]);
            int b = int.Parse(c[1]);
            Console.Write(a * b + " ");
            Console.WriteLine(2 * (a + b));
        }
    }
}


Measured memory_bytes: 15944
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
  ll N,M;
  cin >> N >> M;
  ll flag[M];
  ll i,j;
  for(i=0;i<M;i++){
    flag[i]=0;
  }
  ll K,A;
  for(i=0;i<N;i++){
    cin >> K;
    for(j=0;j<K;j++){
      cin >> A;
      flag[A-1]+=1;
    }
  }
  ll ans=0;
  for(i=0;i<M;i++){
    if(flag[i]==N){
      ans++;
    }
  }
  cout << ans;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 45916
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def cum_2d(field: list):
    row = len(field)
    col = len(field[0])

    # 横方向に累積和
    for r in range(row):
        for c in range(col - 1):
            field[r][c + 1] += field[r][c]

    # 縦方向に累積和
    for c in range(col):
        for r in range(row - 1):
            field[r + 1][c] += field[r][c]

    return field

n,m,q = li()
field = [[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    l, r = li()
    field[l][r] += 1

field = cum_2d(field)

for _ in range(q):
    pi, qi = li()
    print(field[qi][qi] - field[qi][pi-1] - field[pi-1][qi] + field[pi-1][pi-1])

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

int main() {
  int P, Q, R, h1, h2, h3;
  cin >> P >> Q >> R;
  h1 = P + Q;
  h2 = P + R;
  h3 = Q + R;
  cout << min(min(h1, h2), min(h1, h3)) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int x, a;
    cin >> x >> a;
    if(x<a)
        cout << 0 << endl;
    else
        cout << 10 << endl;

    return 0;
}

Measured memory_bytes: 888
#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	int h[n];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	int d[n];
	for (int i = 0; i < n; i++) {
		d[i] = 0;
	}
	d[1] = abs(h[1]-h[0]);
	for (int i = 2; i < n; i++) {
		d[i] = min(d[i-1] + abs(h[i]-h[i-1]),
				d[i-2] + abs(h[i]-h[i-2]));
	}
	cout << d[n-1] << endl;

	return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll MOD=1e9+7;
#define INF 1e9+7
#define N 400001
#define MAX_V 400010
#define vec vector<int>
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umap unordered_map<ll,int,custom_hash>
struct pair_hash
{
    template<class T1,class T2>
    size_t operator() (const pair<T1,T2> &p)const{
        return hash<T1>()(p.first)^hash<T2>()(p.second);
    }
};


main(){
    int n=in();
    int k=in();
    int a[N];
    rep(i,n)a[i]=in();
    sort(a,a+n);
    int ans=2e9;
    rep(i,n+1-k){
        ans=min(ans,a[i+k-1]-a[i]);
    }
    cout<<ans;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
    int a,b;
    int d,r;
    double x,y,f;

    scanf("%d %d",&a,&b);

    d = a/b;
    r = a%b;

	x = a;
	y = b;
	f = x/y;

    printf("%d %d %f\n",d,r,f);

    return 0;
}


Measured memory_bytes: 2684
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
 freopen("input","r",stdin);
 freopen("output","w",stdout);
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    if (N == 3) {
        cout << "2 5 63" << endl;
        return 0;
    }
    if (N == 4) {
        cout << "2 5 20 63" << endl;
        return 0;
    }
    ll sum = 0;
    vector<ll> sol;
    int crt = 3;
    while (sol.size() < N - 1 && crt <= 30000) {
        sol.push_back(crt);
        crt += 6;
    }
    while (sol.size() + 3 > N) sol.pop_back();
    if (sol.size() % 2 == 1) sol.pop_back();
    crt = 2;
    while (sol.size() + 3 <= N) {
        sol.push_back(crt);
        sol.push_back(crt + 2);
        sol.push_back(crt + 4);
        crt += 6;
    }
    if (sol.size() + 1 == N) {
        sol.push_back(crt + 4);
    }
    else if (sol.size() + 2 == N) {
        sol.push_back(crt);
        sol.push_back(crt + 2);
    }
    sort(sol.begin(), sol.end());
    for (int i = 0;i < sol.size();i++) {
        if (i != 0) cout << ' ';
        cout << sol[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#include<utility>
#include<vector>
#include<climits>
#include<queue>
#include<random>
#include<map>

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
using namespace std;

int n,mm;


int main(int argc, char const *argv[]) {

    cin >> n >> mm;
    vector<int> k(n);
    for(int i=0;i<n;i++) cin >> k[i];
    map<int , ll> m;
    vector<int> sum(n+1);
    sum[0] = 0;
    for(int i=0;i<n;i++){
        sum[i+1] = (sum[i] + k[i])%mm;
    }

    ll ans=0;

    for(int i=0;i<=n;i++){
        ans += m[sum[i]];
        m[sum[i]]++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt();
        int w = scanner.nextInt();
        int [][] a = new int[h][w];
        int [][] b = new int[h][w];
        for(int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                a[i][j] = scanner.nextInt();
            }
        }
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                b[i][j] = scanner.nextInt();
            }
        }
        boolean[][][] dp = new boolean[h][w][13000];
        dp[0][0][Math.abs(a[0][0] - b[0][0])] = true;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (i == 0 && j == 0) {
                    continue;
                }
                int diff = Math.abs(a[i][j] - b[i][j]);
                for (int k = 0; k <= 12800; ++k) {
                    if (i > 0 && dp[i - 1][j][k]) {
                        dp[i][j][Math.abs(k + diff)] = true;
                        dp[i][j][Math.abs(k - diff)] = true;
                    }
                    if (j > 0 && dp[i][j - 1][k]) {
                        dp[i][j][Math.abs(k + diff)] = true;
                        dp[i][j][Math.abs(k - diff)] = true;
                    }
                }
            }
        }
        for (int k = 0; k <= 12800; ++k) {
            if (dp[h - 1][w - 1][k]) {
                System.out.println(k);
                return;
            }
        }
    }
}


Measured memory_bytes: 159576
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <numeric>

/* debug macros */
#ifdef WAFDAYO
#define DBG_LINE() {std::cerr<<"\e[2m[L"<<__LINE__<<"]\e[m ";}
#define DBG_PRINT(s,t,u) {std::cerr<<(s)<<" \e[2m=\e[m \e[1m"<<(t)<<"\e[m"<<(u);}
#define SELECT_7TH(x1,x2,x3,x4,x5,x6,x7,...) x7
#define dbg1(x1) DBG_PRINT(#x1,x1,std::endl)
#define dbg2(x1,x2) DBG_PRINT(#x1,x1,", ")dbg1(x2)
#define dbg3(x1,x2,x3) DBG_PRINT(#x1,x1,", ")dbg2(x2,x3)
#define dbg4(x1,x2,x3,x4) DBG_PRINT(#x1,x1,", ")dbg3(x2,x3,x4)
#define dbg5(x1,x2,x3,x4,x5) DBG_PRINT(#x1,x1,", ")dbg4(x2,x3,x4,x5)
#define dbg6(x1,x2,x3,x4,x5,x6) DBG_PRINT(#x1,x1,", ")dbg5(x2,x3,x4,x5,x6)
#define dbg(...) DBG_LINE()\
SELECT_7TH(__VA_ARGS__,dbg6,dbg5,dbg4,dbg3,dbg2,dbg1)(__VA_ARGS__)
#else
#define dbg(...) {}
#endif

/* utility functions */
struct read_item{read_item(){};
template<class T>operator T(){T t;std::cin>>t;return t;}};
char splf(int i,int n){return(i+1<n)?' ':'\n';};
template<bool up>
struct _RI{int i;_RI(int a):i(a){}
int operator*(){return i;}void operator++(){i+=(up?1:-1);}
bool operator!=(const _RI& r){return up?i<r.i:i>=r.i;}};
template<bool up>
struct _RX{_RI<up> x,y;_RI<up> begin(){return x;}_RI<up> end(){return y;}
_RX(int a,int b):x(up?a:(a-1)),y(b){}_RX(int a):_RX(up?0:a,up?a:0){}};
typedef _RX<true> range;
typedef _RX<false> revrange;

/* types and constants */
typedef int64_t i64;
typedef uint64_t u64;
// const i64 inf = (i64)1.05e18;
// const int inf = (int)1.05e9;

using namespace std;

int get_msb(i64 x) {
	int msb = -1;
	for(auto k : range(63)) {
		if((1LL << k) & x) {
			msb = k;
		}
	}
	return msb;
}

bool is_composable(i64 x, vector<i64>& values) {

	if(values.empty()) {
		return false;
	}

	const int n = values.size();

	for(auto i : range(n)) {

		for(auto j : range(i + 1, n)) {
			if(values[i] < values[j]) {
				swap(values[i], values[j]);
			}
		}

		int msb = get_msb(values[i]);
		if(msb < 0) {
			break;
		}

		for(auto j : range(i + 1, n)) {
			if((1LL << msb) & values[j]) {
				values[j] = values[j] ^ values[i];
			}
		}
	}

	for(auto i : range(n)) {
		i64 y = values[i];
		int msb = get_msb(y);
		if(msb >= 0 && ((1LL << msb) & x)) {
			x = x ^ y;
		}
	}

	return x == 0;
}

void solve() {

	const int N = read_item();
	vector<i64> As(N);
	for(auto i : range(N)) {
		As[i] = read_item();
	}
	string S = read_item();

	bool zero_win = true;

	for(auto pos : range(N)) {

		if(S[pos] == '0') {
			continue;
		}

		i64 x = As[pos];
		vector<i64> zero_items;
		for(auto i : range(pos + 1, N)) {
			if(S[i] == '0') {
				zero_items.push_back(As[i]);
			}
		}

		bool ok = is_composable(x, zero_items);
		if(!ok) {
			zero_win = false;
			break;
		}
	}

	printf("%s\n", zero_win ? "0" : "1");
}

int main() {

	const int T = read_item();
	for(auto i : range(T)) {
		solve();
	}

	return 0;
}

/* wafdayo~~~ */


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

int main(){
	int a = 0, b = 0;
    cin >> a >> b;
    if(a > 8 || b > 8){
        cout << ":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 10**9
for i in range(M):
  x,y,c = map(int,input().split())
  s = a[x-1] + b[y-1] - c
  ans = min(ans,s)

ma = 10**9
mb = 10**9
for j in range(A):
  ma = min(ma,a[j])
for k in range(B):
  mb = min(mb,b[k])
ans = min(ans,ma+mb)
print(ans)

Measured memory_bytes: 18688
def main():
    n, k = map(int, input().split())
    nums = [tuple(map(int, input().split())) for _ in range(n)]
    nums.sort(key = lambda x:x[0])

    for num in nums:
        if num[1] >= k:
            print(num[0])
            break
        else:
            k -= num[1]

main()


Measured memory_bytes: 18180
import scala.io.StdIn.{readLine,readInt}

object Main extends App {
  val l = readLine
  val n = readInt

  def transform(i:Int,w:String):Unit = {
    if(i>0) {
      val op = readLine.split(" ")
      val start=op(1).toInt
      val end=op(2).toInt

      (op(0)) match {
        case "replace" => transform(i-1,(w take start) + op(3) + (w takeRight (w.length-end-1)))
        case "reverse" => transform(i-1,(w take start) + (w.slice(start,end+1).reverse) + (w takeRight (w.length-end-1)))
        case "print" => println(w.slice(start, end+1));transform(i-1,w)
      }
    }
  }

  transform(n,l)
}

Measured memory_bytes: 45052
#include <iostream>

using namespace std;

int main(void){
    int a=0;
    int b=0;

    cin >> a >> b;

    if(a==1)a+=13;
    if(b==1)b+=13;

    if(a>b)cout << "Alice" << endl;
    else if(a<b)cout << "Bob" << endl;
    else cout << "Draw" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include<cstdio>
#include <vector>
#include<queue>
#include<limits.h>
#include<string.h>
#include<functional>
using namespace std;

signed main() {
	int a, b; cin >> a >> b;
	printf("%d %d %.10lf\n", a / b, a%b, double(a) / b);
}

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

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int cmin = 10000000, ans = 0;
	int N; cin >> N;
	rep(i, N) {
		int v; cin >> v;
		cmin = min(cmin, v);
		ans += (cmin == v);
	}
	cout << ans << endl;
}


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

using namespace std;
typedef long long ll;

#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359

map<pair<ll, ll>, ll> dp;

ll func(ll s, ll x) {
  if(dp.count(make_pair(s, x)) == 1) return dp[make_pair(s, x)];
  if((s == 0 && x == 0) || (s == 1 && x == 0) || (s == 0 && x == 1)) return 1;
  ll ans = func(s/2, x/2) % MOD;
  if(s >= 1 && x >= 1) ans = (ans + func((s-1)/2,(x-1)/2)) % MOD;
  if(s >= 2) ans = (ans + func((s-2)/2, x/2)) % MOD;

  return dp[make_pair(s, x)] = ans % MOD;
}

int main(void)
{
  ll n;
  cin >> n;
  cout << func(n, n) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
#define ALL(v) v.begin(), v.end()
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define chmax(x, a) x = max(x, a)
#define chmin(x, a) x = min(x, a)

int main() {
  int N, A, B; cin >> N >> A >> B;
  cout << min(A, B) << " " << max(A+B-N, 0) << endl;
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, Dist[int(1e5+5)];
vector <int> Graph[int(1e5+5)];
ll DP[int(1e5+5)][2];
bool checked[int(1e5+5)][2];

ll Solve(int num, int color){
  if (checked[num][color]) return DP[num][color];
  checked[num][color] = true;
  ll ans = 1;
  for (int i = 0; i < Graph[num].size(); i++){
    int next = Graph[num][i];
    if (Dist[num] > Dist[next]) continue;

    if (color == 0){
      ans *= (Solve(next, 0) + Solve(next, 1)) % MOD;
    }else{
      ans *= Solve(next, 0);
    }
    ans %= MOD;
  }
  return DP[num][color] = ans;
}


int main(){
  cin >> N;
  fill(Dist, Dist + N + 1, -1);
  for (int i = 0; i < N - 1; i++){
    int X, Y; cin >> X >> Y;
    Graph[X].push_back(Y);
    Graph[Y].push_back(X);
  }
  queue <int> que; que.push(1);
  Dist[1] = 0;
  while (!que.empty()){
    int Q = que.front(); que.pop();
    for (int i = 0; i < Graph[Q].size(); i++){
      int next = Graph[Q][i];
      if (Dist[next] != -1) continue;
      que.push(next);
      Dist[next] = Dist[Q] + 1; 
    }
  }
  cout << (Solve(1, 0) + Solve(1, 1)) % MOD << endl;

  return 0;
}


Measured memory_bytes: 19376