akhauriyash/Code-Regression huggingface dataset:
from collections import Counter
from decimal import Decimal

def func(n):
    cnt2 = 0
    cnt5 = 0
    while n % 2 == 0:
        n //= 2
        cnt2 += 1
    while n % 5 == 0:
        n //= 5
        cnt5 += 1
    return cnt2, cnt5

def main():
    N = int(input())
    A = [input() for _ in range(N)]
    ctr = Counter()

    for a in A:
        d = Decimal(a)
        d = int(d * 1000000000)
        cnt2, cnt5 = func(d)
        ctr[(cnt2,cnt5)] += 1
    ans = 0
    for (ni1, go1), v1 in ctr.items():
        for (ni2, go2), v2 in ctr.items():
            if not (ni1 + ni2 >= 18 and go1 + go2 >= 18):
                continue
            if ni1 == ni2 and go1 == go2:
                ans += v1 * (v1 - 1)
            else:
                ans += v1 * v2


    print(ans // 2)


if __name__ == "__main__":
    main()

Measured memory_bytes: 214316
#include<iostream>
using namespace std;
long long n,a,b,x[100005],ans=0;
int main(){

    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)
        cin>>x[i];
    for(int i=1;i<n;i++)
        ans+=min(a*(x[i+1]-x[i]),b);
    cout<<ans<<endl;
    return 0;
}


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

//.define
//#define FILE_IN_OUT
#define RET(_x)                       return std::cout << (_x), 0;
#define all(_obj)                     (_obj).begin(), (_obj).end()
#define fori(_iterator, _begin, _end) for (int _iterator = (_begin); _iterator < (_end); ++_iterator)
#define forr(_iterator, _begin, _end) for (int _iterator = (_begin); _iterator >= (_end); --_iterator)
#define loop(_n)                      for (int i = 0; i < (_n); ++i)
#define divCeil(_dividend, _divider)  (((_dividend) - 1LL + (_divider)) / (_divider))
#define sz(_obj)                      static_cast<int>((_obj).size())
#define endl                          "\n"
template<typename Tp>
inline void outarr(Tp _array, const std::size_t _N, const char* _delim = " ") {
    Tp end = _array + _N;
    for (Tp current = _array; current != end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll  = std::int64_t;
using pii = std::pair<int, int>;
constexpr int INF = INT_MAX;
constexpr int MOD = 1e9 + 7;

//.data

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream сin  ("input.txt",  std::ios::in);
    std::ofstream сout ("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

   int x, y, z;
   cin >> x >> y >> z;

   x -= z;
   y += z;

   cout << x / y;

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

#define INF 1e9
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;


int main() {
    int a, b;
    cin >> a >> b;
    cout << (a - 1) * (b - 1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
signed main(void){
    int n,m; cin>>n>>m;
    vector <int> a(n), mo(m),dic(100005); 
    rep(i,n) {cin>>a[i]; mo[a[i]%m]++; dic[a[i]]++;}
    vector <int> need(m);
    int ans = 0;
    ans += mo[0]/2;
    mo[0] = 0;
    need[0] = INF;
    if(m%2==0) ans += mo[m/2]/2, mo[m/2] = 0;
    //cout<<m/2<<endl;
    for(int i=1;i<=m/2;i++){
        //cout<<i<<' '<<m-i<<endl;
        need[i] = need[m-i] = min(mo[i],mo[m-i]);
        ans += need[i];
    }
    if(m%2==0) need[m/2] = INF;
    /*rep(i,m){
        cout<<need[i]<<endl;
    }*/
    rep(i, 100005){
        while(dic[i]>=2){
            if(need[i%m] <= mo[i%m]-2){
                ans++;
                mo[i%m]-=2;
                dic[i]-=2;
            }else break;
        }
    }
    
    cout<<ans<<endl;
}


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


int main() {
	ll p,MIN=1000000000000001;
	cin>>p;
	for(int i=0;i<5;i++){
		ll z;
		cin>>z;
		MIN=min(z,MIN);
	}
	ll sum=(p+MIN-1)/MIN;
	cout << 5+sum-1;
}

Measured memory_bytes: 256
#include<stdio.h>
#define max(a,b) ((a>b)?(a):(b))

int main() {
	int n;
	scanf("%d", &n);
	long long dp[2][3] = { {0,0,0}, {0,0,0} };
	for( int i=0; i<n; ++i )
	{
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		dp[1][0] = a + max(dp[0][1],dp[0][2]);
		dp[1][1] = b + max(dp[0][0],dp[0][2]);
		dp[1][2] = c + max(dp[0][0],dp[0][1]);
		dp[0][0] = dp[1][0];
		dp[0][1] = dp[1][1];
		dp[0][2] = dp[1][2];
	}
	printf("%lld\n", max(max(dp[0][0],dp[0][1]),dp[0][2]) );
}


Measured memory_bytes: 256
N,Y = map(int,input().split())
y = Y/1000
Answer = [-1, -1, -1]

for i in range(N+1):
  for j in range(N+1-i):
    if 10*i+5*j+(N-i-j) == Y/1000:
      Answer = [i, j, N-i-j]
      print(*Answer)
      exit()
print(*Answer)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

//INT_MAX	2,147,483,647 = 2*1.0e9

int main(){
  string S;
  cin >> S;

  int len = S.length();
  string S2 = S.substr(0); 

  int ans1 = 0;
  for(int i = 1; i < len; i++){
    if(S[i-1] == S[i]){
      if(S[i] == '1') S[i] = '0';
      else S[i] = '1';
      ans1 += 1;
    }
  }

  int ans2 = 1;
  if(S2[0] == '1') S2[0] = '0';
  else S2[0] = '1';
  for(int i = 1; i < len; i++){
    if(S2[i-1] == S2[i]){
      if(S2[i] == '1') S2[i] = '0';
      else  S2[i] = '1';
      ans2 += 1;
    }
  }

  cout << min(ans1, ans2) << endl;

  return 0;
}



Measured memory_bytes: 512
R,G,B,N=map(int,input().split())
cnt=0
for i in range(0,N//R+1):
    buf=N-i*R
    for j in range(0,buf//G+1):
        #print(i,j)
        if (buf-j*G)%B==0:
            cnt=cnt+1
print(cnt)


Measured memory_bytes: 40376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
const int MOD=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<string> s(3);
    for(int i=0;i<3;i++){
        cin >> s[i];
    }
    int t=0;
    vector<int> c(3);
    while(true){
        if(s[t].size()==c[t]){
            cout << char('A'+t) << endl;
            return 0;
        }
        int p=s[t][c[t]]-'a';
        c[t]++;
        t=p;
    }
}

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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<int> A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	for (int i = 0; i < N - K; i++) {
		res += A[i];
	}
	cout << res << endl;
}

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

int main() {
  ll N, A, B; cin >> N >> A >> B;
  if (A+B == 0) {cout << 0 << endl; return 0;}
  ll k = N/(A+B); ll rem = N%(A+B);
  ll res = k * A + min(rem, A);
  cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

lli body(lli a, lli b){
	return (a-b)*(a-b);
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	lli n;
	string s;
	cin>> s;
	n = s.length();
	lli cnt = 0;
	lli i=0;
	while(i<n-1){
		if(s[i] != s[i+1]){
			cnt +=2;
			s.erase(i,2);
			if(i != 0) i--;
			n -= 2;
		}else{
			i++;
		}
	}
	cout << cnt << endl;
 	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	int m = n / 2;
	if (n % 2)
		m++;
	long long ans = 0;
	for (int i = 1; i <= m; i++)
	{
		ans += (long long)a[n + 1 - i];
	}
	for (int i = 1; i <= n - 1 - m; i++)
	{
		ans += (long long)a[n - i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4420
program test
implicit none
integer::l
character::S*100000
read(*,*)S
l=len_trim(S)
do 
	if(l==0)then
    print*,'YES'
    stop
	else if(S(l-4:l)=='dream')then
    	l=l-5
   	else if(S(l-6:l)=='dreamer')then
    	l=l-7
    else if(S(l-4:l)=='erase')then
    	l=l-5
    else if(S(l-5:l)=='eraser')then
    	l=l-6
    else 
    	print*,'NO'
        stop
    end if
end do
end program test



Measured memory_bytes: 700
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#include<functional>
typedef long long ll;

using namespace std;


int main(){
    int H, W;
    cin >> H >> W;
    int M[H][W];
    int A[H][W];
    int B[H][W];
    int MAX = 80*160+3;
    vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(MAX*2+2, false)));
    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            cin >> A[y][x];
        }
    }
    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            cin >> B[y][x];
        }
    }

    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            M[y][x] = abs(A[y][x]-B[y][x]);
        }
    }
    dp[0][0][MAX+M[0][0]]=true;
    dp[0][0][MAX-M[0][0]]=true;
    for(int y=0;y<H;y++){
        for(int x=0;x<W;x++){
            for(int k=0;k<MAX*2+2;k++){
                if(y > 0){
                    if(k-M[y][x] >= 0)
                        dp[y][x][k] = dp[y-1][x][k-M[y][x]] | dp[y][x][k];
                    if(k+M[y][x] < MAX*2+2)
                        dp[y][x][k] = dp[y-1][x][k+M[y][x]] | dp[y][x][k];
                }
                if(x > 0){
                    if(k-M[y][x] >= 0)
                        dp[y][x][k] = dp[y][x-1][k-M[y][x]] | dp[y][x][k];
                    if(k+M[y][x] < MAX*2+2)
                        dp[y][x][k] = dp[y][x-1][k+M[y][x]] | dp[y][x][k];
                }
            }
        }
    }
    for(int i=0;i<MAX;i++){
        if(dp[H-1][W-1][MAX+i] || dp[H-1][W-1][MAX-i]){
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}


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

int main() {
  int N, K;
  int a = 1;
  cin >> N >> K;

  // ここにプログラムを追記
  for (int i = 0; i < N; i++) {
    if (a > K) {
      a += K;
    }
    else {
      a *= 2;
    }
  }
  
  cout << a << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main()
{
	string s,t;
	ll ans=0;
	cin>>s>>t;
	cout<<t<<s<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
    ll a,b,c,count=0,sum=0;
    cin>>a>>b>>c;
    sum=a+b+c;
    while(1){
        if(a%2||b%2||c%2){
            break;
        }
        else{
            if(sum-a*3==0&&sum-b*3==0){
                cout<<"-1"<<endl;
                return 0;
            }
            a=(sum-a)/2;
            b=(sum-b)/2;
            c=(sum-c)/2;
            count++;
        }
    }
cout<<count<<endl;
return 0;
}


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

#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                                                       \
    for(long long hoge = 0; (hoge) < (n); ++(hoge))                            \
    cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
const ll INF = LLONG_MAX / 2;
const ll MOD = 998244353;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll D0;
    cin >> D0;
    ll ans = D0 == 0;
    ll D[N - 1];
    for(int i = 0; i < N - 1; i++) {
        cin >> D[i];
    }
    sort(D, D + N - 1);
    int j = 0;
    ll prev = 1;
    for(int i = 1; i < N - 1; i++) {
        if(j < N - 1 && D[j] != i) {
            ans = 0;
            break;
        }
        ll cnt = 0;
        while(j < N - 1 && D[j] == i) {
            ans = ans * prev % MOD;
            cnt++;
            j++;
        }
        prev = cnt;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i, a, b) for(ll i = (a); i < (ll)b; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define INF (1ll << 60)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll, ll> p;
constexpr int MOD = 1000000007;
using ll = long long;
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

void print(const std::vector<int> &v) {
    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << " "; });
    std::cout << std::endl;
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(b - a == c - b) {
        cout << "YES" << endl;
        return 0;
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  int ans = b / a;
  if(ans > c) ans = c;
  cout << ans << endl;
  return 0;
}

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

int main() {
  int n;
  char s[100];
  
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    if (s[i] == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;
  
  return 0;
}

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

using namespace std;

typedef long long ll;

const int N = 300010;

int n , m , a[N];


vector<int> odd,even,res;
int main() {
 //	freopen("input.txt","r",stdin);
 	scanf("%d%d",&n,&m);
 	for (int i = 0; i < m; ++i){
 		scanf("%d",&a[i]);
 		if(a[i]&1)
 			odd.push_back(a[i]);
 		else
 			even.push_back(a[i]);
 	}
 	if(odd.size() > 2){
 		puts("Impossible");
 	}else{
 		if(odd.size()){
 			res.push_back(odd.back());
 			odd.pop_back();
 		}
 		while(even.size()) res.push_back(even.back()),even.pop_back();
 		if(odd.size()){
 			res.push_back(odd.back());
 			odd.pop_back();
 		}
 		for (int i = 0; i < res.size(); ++i){
 			if(i)
 				printf(" ");
 			printf("%d",res[i]);
 		}
 		puts("");
 		if(res.size() == 1){
 			res.back()--;
 			res.push_back(1);
 		}else{
 			res[0]--;
 			res.back()++;
 		}
 		int cnt = 0;
 		for (int i = 0; i < res.size(); ++i){
 			if(res[i])
 				cnt++;
 		}
 		printf("%d\n",cnt);
 		cnt = 0;
 		for (int i = 0; i < res.size(); ++i){
 			if(cnt)
 				printf(" ");
 			if(res[i])
 				printf("%d",res[i]),cnt++;
 		}
 		puts("");
 	}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve(){
  int x, k, d;
  cin>>x>>k>>d;

  int cur = abs(min(abs(x/d), k));
  if(x>0)
    x-=(cur)*d;
  else
    x+=(cur)*d;
  k-=cur;
  if(k == 0){
    cout<<abs(x)<<endl;
    return;
  }
  if(k%2 == 0){
    cout<<abs(x)<<endl;
  }else{
    cout<<min(abs(x-d), abs(x+d))<<endl;
  }
}
signed main(){
  // int t;
  // cin>>t;
  // while(t--)
    solve();
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include<string>
using namespace std;
int main(){
int  n,a[200000]={},b[200000]={};
cin>>n;
for (int i=0;i<n;i++){
    cin>>a[i];
    b[i]=a[i];

}
sort(a,a+n);
for (int i=0;i<n;i++){
    if(b[i]==a[n-1])
    cout<<a[n-2]<<' ';
else cout<<a[n-1]<<" ";}
}


Measured memory_bytes: 3200
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)*}
    };
}

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)*}
    };
}

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! {
        a: u32,
        b: u32,
    }
    let ans = if a * b % 2 == 0 { "Even" } else { "Odd"};
    println!("{}", ans)
}


Measured memory_bytes: 4352
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int a, b, k;
    cin >> a >> b >> k;

    vector<int> v;
    for(int i = 1; i <= 100; ++i) {
        if (a % i == 0 && b % i == 0) {
            v.push_back(i);
        }
    }
    cout << v[v.size()-k] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
const ll ccc=2155;
bool prime[ccc+1];
vector<ll> pr;
void makeprime(){
	ll i,j;
	for(i=2;i<=ccc;i++) prime[i]=true;
	for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false;
	for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i);
}
ll MX=10000000000LL;
vector<ll> cs;
typedef pair<int,int> P;
map<ll,P> mp;
int N;
int main(){
	makeprime();
	int K=pr.size();
	for(ll p:pr) cs.pb(p*p*p);
	cin>>N;
	int ans=0;
	rep(i,N){
		ll x,y=1;
		ll qx;
		cin>>x;
		qx=x;
		bool ok=0;
		rep(j,K){
			ll p=pr[j];
			ll c=cs[j];
			if(x%c==0){
				while(x%c==0) x/=c,qx/=c;
			}
			if(x%(p*p)==0){
				qx/=(p*p);
				y*=p;
				if(y>MX){
					ok=1;
					break;
				}
			}else if(x%p==0){
				qx/=p;
				y*=p*p;
				if(y>MX){
					ok=1;
					break;
				}
			}
		}
		if(ok){
			ans++;
			continue;
		}
		if(qx>1){
			ll rx=round(sqrt(qx));
			if(rx*rx==qx){
				y*=rx;
				if(y>MX){
					ans++;
					continue;
				}
			}else{
				if(1e16/y<qx){
					ans++;
					continue;
				}
				y*=qx;
				if(y>MX){
					ans++;
					continue;
				}
				if(1e16/y<qx){
					ans++;
					continue;
				}
				y*=qx;
				if(y>MX){
					ans++;
					continue;
				}
			}
		}
		if(x<y) mp[x].fs++;
		else mp[y].sc++;
//		show(i);
//		show(x);
//		show(y);
	}
	for(auto p:mp){
		if(p.fs==1) ans++;
		else ans+=max(p.sc.fs,p.sc.sc);
	}
	cout<<ans<<endl;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const ll INF = 2e18;
const int inf = 1e9+10;
const int maxN = 10010;
const int maxD = 15;
const int maxH = 100; 
const int MOD = 1000000007;

char s[maxN];
char t[maxN];

int main()
{
	scanf("%s",s+1);
	scanf("%s",t+1);
	int n = strlen(s+1);
	int m = strlen(t+1);
	if(n+1 == m)
	{
		int flag = 0;
		for(int i=1;i<=n;i++)
		{
			if(s[i] != t[i])
				flag = 1;
		}
		if(flag)
		{
			puts("No");
		}
		else
		{
			puts("Yes");
		}
	}
	else
	{
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 3692
fun main() {
    val l = readLine()!!.split(' ').map { it.toInt() }
    var map: MutableList<Int> = (1..l[0]).toMutableList()

    for (i in 0 until l[1]) {
        readLine()!!
        val a = readLine()!!.split(' ').map { it.toInt() }
        for (x in a) {
            map.remove(x)
        }
    }
    println(map.count())
}



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

int main() {

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


    int n;
    cin >> n;
    vector<int> a(2 * n);

    for (int i = 0; i < (n << 1); i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int i = 0; i < (n << 1); i+=2) {
        ans += a[i];
    }
    cout << ans;    
    
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
const int MN = 100012;
int n,a[MN],b[MN],c[MN],dp[MN][3];
int main (void) {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i] >> c[i];
    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];
    for (int i = 1; i < n; i++) {
        dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
        dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
        dp[i][2] = c[i] + max(dp[i-1][0],dp[i-1][1]);
    }
    cout << *max_element(dp[n-1],dp[n-1]+3) << "\n";
    return 0;
}


Measured memory_bytes: 2560
from collections import deque

h, w = map(int, input().split())

s = []

for i in range(h):
    s.append(list(input()))


def bfs(x, y):
    if s[y][x] == '#':
        return 0

    queue = deque()
    queue.appendleft([x, y])
    visited = dict()
    visited[(x, y)] = 0

    while queue:
        nx, ny = queue.pop()
        cur = visited[(nx, ny)]

        if nx - 1 >= 0 and (nx - 1, ny) not in visited:
            if s[ny][nx - 1] == '.':
                visited[(nx - 1, ny)] = cur + 1
                queue.appendleft((nx - 1, ny))

        if nx + 1 < w and (nx + 1, ny) not in visited:
            if s[ny][nx + 1] == '.':
                visited[(nx + 1, ny)] = cur + 1
                queue.appendleft((nx + 1, ny))

        if ny - 1 >= 0 and (nx, ny - 1) not in visited:
            if s[ny - 1][nx] == '.':
                visited[(nx, ny - 1)] = cur + 1
                queue.appendleft((nx, ny - 1))

        if ny + 1 < h and (nx, ny + 1) not in visited:
            if s[ny + 1][nx] == '.':
                visited[(nx, ny + 1)] = cur + 1
                queue.appendleft((nx, ny + 1))

    return max(visited.values())


result = 0
for i in range(h):
    for j in range(w):
        r = bfs(j, i)
        result = max(result, r)

print(result)


Measured memory_bytes: 76128
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
	int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 4005, mod = 998244353;
int sum[N][2], f[N][N];
char s[N];

inline void add(int &x,int y) {
	x += y; x = x >= mod ? x - mod : x;
}

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) {
		if (s[i] == '0') sum[i][0] += 2;
		else if (s[i] == '1') sum[i][0] ++, sum[i][1] ++;
		else sum[i][1] += 2;
		sum[i][0] += sum[i - 1][0], sum[i][1] += sum[i - 1][1];
	}
//	f[0][0] = 1;

	if (sum[1][0] >= 1) f[1][1] = 1;
	if (sum[1][1] >= 1) f[1][0] = 1;
	
	for (int i = 2; i <= (n << 1); ++i) {
		for (int j = 0; j <= i; ++j) {
			int r = j, b = i - j;
			if (r > sum[min(i, n)][0] || b > sum[min(i, n)][1]) continue;;
			add(f[i][j], f[i - 1][j]);
			if (j) add(f[i][j], f[i - 1][j - 1]);
//			cout << f[i][j] << " " << f[i - 1][j] << " " << f[i - 1][j - 1] << "\n";
		}
	}
	cout << f[n + n][sum[n][0]];


	return 0;
}


Measured memory_bytes: 60544
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
 
int main() {
    int n,ans=0;
    vector<int>a(9),c(9);
    rep(i,9)cin>>c[i];
    cin>>n;
    vector<int>b(n);
    rep(i,n)cin>>b[i];
    rep(i,n)rep(j,9){
    	if(b[i]==c[j])a[j]=1;
    }
    if((a[0]&a[3]&a[6])|(a[1]&a[4]&a[7])|(a[2]&a[5]&a[8])|(a[0]&a[1]&a[2])|(a[3]&a[4]&a[5])|(a[6]&a[7]&a[8])|(a[0]&a[4]&a[8])|(a[2]&a[4]&a[6])){
    	cout<<"Yes";
    }
    else cout<<"No";
	return 0;
}

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


int main(){
    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<ll> evensum(N+1, 0), oddsum(N+1, 0), sum(N+1, 0);
    oddsum[1] = A[0];
    sum[1] = A[0];
    for (int i = 2; i <= N; i++) {
        if (i%2 == 1) {
            evensum[i] = evensum[i-1];
            oddsum[i] = oddsum[i-1]+A[i-1];
            sum[i] = sum[i-1]+A[i-1];
        }
        if (i%2 == 0) {
            evensum[i] = evensum[i-1]+A[i-1];
            oddsum[i] = oddsum[i-1];
            sum[i] = sum[i-1]+A[i-1];
        }
    }
    
    for (int z = 0; z < Q; z++) {
        ll X;
        cin >> X;
        int l = N/2-1, r = N-1;
        int c = (l+r)/2;
        int d = c-1-(N-c);
        while (r-l > 1) {
            c = (l+r)/2;
            d = c-(N-1-c);
            if (abs(X-A[d]) <= abs(X-A[c])) r = c;
            else l = c;
        }
        d = r-(N-1-r);
        //cout << r << " " << d << " ";
        ll ans = 0;
        ans += sum[N]-sum[r];
        //cout << ans << " ";
        if (N%2 == 1 && d > 0) ans += oddsum[d];
        else if (N%2 == 0 && d > 0) ans += evensum[d];
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4864
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=int(3e5+5);
int n;
char s[MAXN];
string la,nw;
int main()
{
    int ans=0;
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) {
        nw=nw+s[i];
        if(nw==la)
            continue;
        else {
            la=nw;
            nw="";
            ans++;
        }
    }
    printf("%d",ans);
}


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


    class Program
    {
        static void Main(string[] args)
        {
            string[] Input = Console.ReadLine().Split(' ');
            int N = int.Parse(Input[0]);
            int K = int.Parse(Input[1]);
            int[,] list = new int[N,2];
            
            for(int i = 0; i < K; i++){
                int num = int.Parse(Console.ReadLine());
                string[] Input2 = Console.ReadLine().Split(' ');
                for(int j = 0; j < num; j++){
                    int n = int.Parse(Input2[j]);
                    list[n - 1,1]++;
                }
                
            }
            int count = 0;
            for(int i = 0; i < N; i++){
                if(list[i,1] == 0){
                    count++;
                }
            }            
            Console.WriteLine(count);
        }
    }

Measured memory_bytes: 18216
<?php

$input = explode(' ', trim(fgets(STDIN)));
$n = (int)$input[0];
$m = (int)$input[1];

$islands = [];
for ($i=1; $i <= $n; $i++) { 
	$islands[$i] = [
		'root' => $i,
		'group' => 1,
	];
}
$bridges = [];
for ($i=0; $i < $m; $i++) { 
	$input = explode(' ', trim(fgets(STDIN)));
	$a = (int)$input[0];
	$b = (int)$input[1];
	$bridges[] = [$a, $b];
}
$bridges = array_reverse($bridges);

$inc = (int)($n * ($n-1) / 2);
$result = [];
$result[] = $inc;
foreach ($bridges as $br) {
	$small = $br[0];
	$large = $br[1];
	$root = getRoot($islands, $small);
	$merge_root = getRoot($islands, $large);
	if ($root !== $merge_root) {
		$inc -= ($islands[$root]['group'] * $islands[$merge_root]['group']);
		$islands[$merge_root]['root'] = $root;
		$islands[$large]['root'] = $root;
		$islands[$root]['group'] += $islands[$merge_root]['group'];
	}
	$inc = max($inc, 0);
	// printI($islands);
	// echo $inc , PHP_EOL;
	$result[] = $inc;
}
$result = array_reverse($result);
unset($result[0]);
echo implode(PHP_EOL, $result);


function getRoot($islands, $i){
	$root = $islands[$i]['root'];
	while (true) {
		if ($root === $islands[$root]['root']) {
			break;
		}else{
			$root = $islands[$root]['root'];
		}
	}
	return $root;
}

function printI($islands){
	foreach ($islands as $i) {
		echo 'root: ' . $i['root'] . ' group: ' .  $i['group'] . PHP_EOL;
	}
}

Measured memory_bytes: 95084
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    xyh = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    xyh.sort(key=lambda x: x[2], reverse=True)
    for x in range(101):
        for y in range(101):
            h = xyh[0][2] + abs(xyh[0][0] - x) + abs(xyh[0][1] - y)
            b = True
            for xl, yl, hl in xyh:
                if max(0, h - abs(xl - x) - abs(yl - y)) != hl:
                    b = False
                    break
            if b:
                print(x, y, h)
                exit()


if __name__ == '__main__':
    slove()


Measured memory_bytes: 40688
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
    ll x,y,ans; cin >> x >> y;
    if(x*y>=0 && x<=y){
        ans = abs(abs(y) - abs(x));
    }else if(x*y>0 && x>y){
        ans = abs(abs(y) - abs(x)) + 2; 
    }else{
        ans = abs(abs(y) - abs(x)) + 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
// 2017/07/21 Tazoe

#include <iostream>
#include <algorithm>
using namespace std;

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

	int p[5000];
	for(int i=0; i<N; i++){
		cin >> p[i];
	}

	int min_sum = 20000;		// ??????????????????????????????

	for(int I=0; I<=p[0]; I++){
		int q[5000];			// ??????p????????????
		for(int i=0; i<N; i++){
			q[i] = p[i];
		}

		// ?????????I??????1??????????£???????
		int sum = I;
		q[0] -= I;

		for(int i=0; i<=N-2; i++){
			if(q[i]<=0)
				continue;

			// ?????£?????¨?£???????
			sum += q[i]*2;
			q[i+1] -= q[i];
		}

		// ?????????????????????1??????????£???????
		if(q[N-1]>0){
			sum += q[N-1];
		}

		min_sum = min(min_sum, sum);
	}

	cout << min_sum << endl;

	return 0;
}

Measured memory_bytes: 3124
#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <bits/stdc++.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <functional> 
#include<math.h> 
#include<cstring>
using namespace std;
typedef long long ll;

int main(void){
    // Your code here
    int N,Q;
    string S;
    cin >> N >> Q >> S;
    vector<int> dp(N);
    dp.at(0) = 0;
    int cnt = 0;
    for(int i = 0; i < N; i++){
        dp.at(i) = cnt;
        if(S.at(i) == 'A' && i + 1 < N && S.at(i + 1) == 'C'){
            cnt++;
        }
    }
    
   
    
    for(int i = 0; i < Q; i++){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        cout << dp.at(y)- dp.at(x) << endl;
    }
}


Measured memory_bytes: 1408
// D - Dice in Line
#include <bits/stdc++.h>
using namespace std;
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int main(){
	int N,K; scanf("%d%d",&N,&K);
	vector<int> P(N+K); rp(i,0,N) scanf("%d",&P[i+K]);
	int ans = 0, sum = 0;
	rp(i,0,N) ans = max(ans, sum += P[i+K] - P[i]);
	printf("%.12f\n",(ans+K)/2.0);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;
bool nonprime[10000005],vis[10000005];
int prime[10000005],tot,x[205],b[205],M[2],matc[205];
vector<int> to[505];
bool used[205];
bool match(int u) {
    for(auto t : to[u]) {
        if(!used[t]) {
            used[t] = 1;
            if(!matc[t] || match(matc[t])) {
                matc[t] = u;
                return true;
            }
        }
    }
    return false;
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {
        read(x[i]);
        vis[x[i]] = 1;
    }
    for(int i = 2 ; i <= 10000000 ; ++i) {
        if(!nonprime[i]) {
            prime[++tot] = i;
        }
        for(int j = 1 ; j <= tot ; ++j) {
            if(prime[j] > 10000000 / i) break;
            nonprime[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
    tot = 0;
    for(int i = 1 ; i <= 10000001 ; ++i) {
        if(vis[i] != vis[i - 1]) b[++tot] = i;
    }
    for(int i = 1 ; i <= tot ; ++i) {
        M[b[i] & 1]++;
        for(int j = 1 ; j <= tot ; ++j) {
            if(i == j) continue;
            if(abs(b[i] - b[j]) < 3) continue;
            if(!nonprime[abs(b[i] - b[j])]) to[i].pb(j);
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= tot ; ++i) {
        if(b[i] & 1) {
            memset(used,0,sizeof(used));
            if(match(i)) ++ans;
        }
    }
    out(ans + ((M[0] - ans) / 2 + (M[1] - ans) / 2) * 2 + ((M[0] - ans) & 1) * 3);enter;
}
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 24064
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<double,int> P;

int main(){
  P a[3][8];
  vector <P> b,ans;
  for(int i=0;i<3;i++){
    for(int j=0;j<8;j++) cin>>a[i][j].s>>a[i][j].f;
    sort(a[i],a[i]+8);
    ans.push_back(a[i][0]);
    ans.push_back(a[i][1]);
    for(int j=2;j<8;j++) b.push_back(a[i][j]);
  }
  sort(b.begin(),b.end());
  ans.push_back(b[0]);
  ans.push_back(b[1]);
  for(int i=0;i<8;i++) cout <<ans[i].s<<" "<<ans[i].f<<endl;
  


  return 0;
}

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

int main(){
  string S;
  cin >> S;
  int N = S.size();
  ll sum = 0;
  for(int bit=0;bit<(1<<(N-1));bit++){
    ll ps = 0;
    for(int i=0;i<N;i++){
      ps = ps * 10 + S.at(i) - '0';
      if(bit & (1<<i)){
        sum += ps;
        ps = 0;
      }
    }
    sum += ps;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;


template<typename T,typename U>istream & operator >> (istream &i,pair<T,U> &A){i>>A.F>>A.S; return i;}
template<typename T>istream & operator >> (istream &i,vector<T> &A){for(auto &I:A){i>>I;} return i;}
template<typename T,typename U>ostream & operator << (ostream &o,pair<T,U> &A){o<<A.F<<" "<<A.S; return o;}
template<typename T>ostream & operator << (ostream &o,vector<T> &A){ll i=A.size(); for(auto &I:A){o<<I<<(--i?" ":"");} return o;}
template<typename T>vector<T> & cset(vector<T> &A,T e=T()){for(auto &I:A){I=e;} return A;}





int main(){
    ll n,k;
    cin>>n>>k;
    if(k==1){cout<<0<<endl; return 0;}
    n-=k;
    cout<<n<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX = 510000;

int main(){
  ll N,M;
  cin>>N>>M;
  vector<P>A(N);
  rep(i,N){
  	ll a,b;
    cin>>a>>b;
    A[i]=P(a,b);
  }
  sort(A.begin(),A.end());
  ll ans=0;ll count=0;
  rep(i,N){
  	auto t=A[i];
    if(count+t.second>=M){
      ll g=M-count;ans=ans+(g*t.first);break;
    }
  	else{
      count+=t.second;ans=ans+(t.first*t.second);
    }
  }
  cout<<ans;
}

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

int main() {
  int N,K,count;
  cin>>N>>K;
  count=0;
  vector<int>h(N);
  for(int i=0;i<N;i++){
  cin>>h.at(i);
  }
  sort(h.begin(),h.end());
  for(int i=0;i<N;i++){
   if(h.at(i)<K){
   count++;
   }
   else{
   break;
   }
  }
  cout<<N-count<<endl;
}

Measured memory_bytes: 640
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let a: usize = read();
    let b: usize = read();

    let ans: String;
    if a < b {
        ans = (0..b).map(|_| a.to_string()).collect();
    } else {
        ans = (0..a).map(|_| b.to_string()).collect();
    }

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


Measured memory_bytes: 4352
import copy
h,w,kl = map(int, input().split(" "))
b=list(list(input()) for i in range(h))
count = 0
ans = 0
for i in range(h):
  for j in range(w):
    if b[i][j] == "#":
      count += 1
      
for hi in range(2 ** (h + w)):
  a = copy.deepcopy(b)
  temp = count
  for hj in range(h):
    if (hi >> hj) & 1:
      for l in range(w):
        if a[hj][l] == "#":
          temp -= 1
        a[hj][l] = "*"
  for wj in range(w):
    if (hi >> wj) & (2 ** h):
      for k in range(h):
        if a[k][wj] == "#":
          temp -= 1
        a[k][wj] = "*"
  if temp == kl:
    ans += 1 
  #print(hi, a)
  
print(ans)

Measured memory_bytes: 9304
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	fmt.Scanf("%d", &n)
	ns := strconv.Itoa(n)
	last := ns[len(ns)-1:]

	if last == "2" || last == "4" || last == "5" || last == "7" || last == "9" {
		fmt.Println("hon")
		return
	}

	if last == "0" || last == "1" || last == "6" || last == "8" {
		fmt.Println("pon")
		return
	}

	fmt.Println("bon")
}


Measured memory_bytes: 1820
//21:16-23:16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define mod 1000000007
ll n,a,b,c,d;
int main(){
    cin >> n >> a >> b >> c >> d;
    for(int i=0;i<n;i++){
        ll x = -1LL*i*d+1LL*(n-1-i)*c;
        ll y = -1LL*i*c+1LL*(n-1-i)*d;
        if(x<=b-a && b-a<=y){
            puts("YES"); return 0;
        }
    }
    puts("NO"); 
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<vll> vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(ll i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define fi first
#define se second
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template <class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template <class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
template <class T> inline void dump(T &v){irep(i, v){cout<<(*i)<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr ld EPS = 1e-11;






int main() {
    
    int ans=0;
    int n;
    cin>>n;
    rep(i,n){
        int a;
        cin>>a;
        if(a%2==1&&i%2==0)ans++;
    }
    fin(ans);


}



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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    int h, n;
    cin >> h >> n;
    vector<pair<int,int>> v(n);
    for(auto& i : v) cin >> i.first >> i.second;

    vector<int> dp(h+1, inf);
    dp[0] = 0;

    REP(i, n){
        REP(j, h){
            int a = v[i].first, b = v[i].second;
            chmin(dp[min(h, j + a)], dp[j] + b);
        }
    }
    
    cout << dp.back() << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
using namespace std;
typedef long long ll;

int N,X;
int L[105];

int main(){
    cin>>N>>X;
    repn(i,N) cin>>L[i];

    int ans=0;
    int dis=0;
    for(int i=1;i<=N+1;i++){
        dis+=L[i-1];
        if(dis<=X){
            ans++;
        }else{
            break;
        }
    }

    cout<<ans<<endl;
}

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

using namespace std;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n, l;
  cin >> n >> l;
  vector<int> x(n);
  vector<int> catch_left(n), catch_right(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }
  vector<long long> t(n);
  long long ans = 1;
  for (int i = 0; i < n; i++) {
    cin >> t[i];
    ans += (t[i] + 2 * l - 1) / (2 * l);
  }
  for (int i = 0; i < n; i++) {
    if (t[i] % (2 * l) > 0 && t[i] % (2 * l) <= 2 * (l - x[i])) {
      catch_right[i] = 1;
    }
    if (t[i] % (2 * l) > 0 && t[i] % (2 * l) <= 2 * x[i]) {
      catch_left[i] = 1;
    }
  }
  if (catch_right[n - 1]) {
    ans--;
  }
  int cnt_left = 0;
  int any = 0;
  for (int i = 0; i + 1 < n; i++) {
    if (catch_left[i] && catch_right[i]) {
      if (cnt_left > 0) {
        ans--;
        cnt_left--;
      } else {
        any++;
      }
    } else if (catch_right[i]) {
      if (cnt_left > 0) {
        ans--;
        cnt_left--;
      } else if (any > 0) {
        ans--;
        any--;
      }
    } else if (catch_left[i]) {
      cnt_left++;
    }
  }
  ans -= any / 2;
  ans *= 2 * l;
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 6144
//28
#include<iostream>

using namespace std;

int main(){
  for(;;){
    for(int i=0;i<3;i++){
      char s[101];
      int scr[2]={};
      cin>>s;
      if(s[0]=='0')return 0;
      for(int j=1;s[j];j++){
	scr[s[j]-'A']++;
      }
      (*((scr[0]>scr[1])?scr:scr+1))++;
      cout<<scr[0]<<' '<<scr[1]<<endl;
    }
  }
  return 0;
}
    

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
struct item{
	long long int val;
	long long int wt;
};
vector<item>v;
long long int mem[105][100005]={-1};
long long int dp(long long int n,long long int w)
{
	if(mem[n][w]!=-1)
		return mem[n][w];
	if(n==1)
	{
		if(v[n].wt<=w)
			return v[n].val;
		else
			return 0;
	}
	else
	{
		if(v[n].wt<=w)
			mem[n][w]= max(dp(n-1,w-v[n].wt)+v[n].val,dp(n-1,w));
		else
			mem[n][w]= dp(n-1,w);
	}
	return mem[n][w];
}
int main()
{
	long long int n,ww;
	cin>>n>>ww;
	item x;
	x.val=0;
	x.wt=0;
	v.push_back(x);
	memset(mem,-1,sizeof mem);
	for(long long int i=0;i<n;i++)
	{
		item x;
		cin>>x.wt;
		cin>>x.val;
		v.push_back(x);
	}
	cout<<dp(n,ww)<<endl;
	return 0;
}

Measured memory_bytes: 82304