akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <regex>
#ifdef _DEBUG
#include "debug.h"
#endif
#define int ll
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define mkpr make_pair
#define mktp make_tuple
#define tv(tp, i) get<(i)>(tp)
#define CLEAR(obj) obj = decltype(obj)()
#define var auto
#define OUT(type) type &
#define IN(type) const type &
#define self (*this)
#define in :
#define True true
#define False false
using namespace std; using str = string; using cstr = const str;
using ll = long long; using ull = unsigned long long; using cint = const int; using cll = const ll;
using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>;
using vb = vector<bool>; using vvb = vector<vb>; using vd = vector<double>; using vvd = vector<vd>;
using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<double, double>; using psl = pair<string, ll>;
using tiii = tuple<int, int, int>; using tlll = tuple<ll, ll, ll>;
static const int MGN = 10; static const int ARYSZ_MAX = (int)1e7;
static const ll LINF = LLONG_MAX/2;
#ifdef int
static const int INF = LINF;
#else
static const int INF = INT_MAX/2;
#endif
static double EPS = 1e-9;
static inline bool DBLEQ(double a, double b) {return abs(a - b) < EPS;}
static inline void EPR(str msg) {cerr << msg << endl;}
static inline void AST(bool exp, str msg) {if(!exp){EPR(msg);} assert(exp);}
static inline void TAST(bool exp, str msg) {if(!exp){EPR(msg);} while(!exp){}}


int32_t main(int32_t argc, char* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef IMPORT_SAMPLE
    vs args(argv, argv+argc);
    string sample = make_sample(args, "sample-1");
    ifstream ifs(sample); cin.rdbuf(ifs.rdbuf());
#endif


    int H, W; cin >> H >> W;
    vs S(H); REP(i, H) cin>>S[i];

    int black = 0;
    REP(i, H)
        REP(j, W) if (S[i][j] == '#') black++;

    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    queue<pii> que;
    que.push(mkpr(0, 0));
    vvi dist(H, vi(W, INF));
    //vvi vis(H, vi(W, 0));
    dist[0][0] = 0;

    while(!que.empty()) {
        var pr = que.front(); que.pop();
        int x = pr.first, y = pr.second;
        //vis[x][y] = 1;
        if(x == H-1 and y ==  W-1) break;

        REP(i, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 or H <= nx or ny < 0 or W <= ny) continue;
            if (S[nx][ny] == '#') continue;
            if (dist[nx][ny] != INF) continue;

            dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1);
            //dist[nx][ny] = dist[x][y] + 1;
            que.push(mkpr(nx, ny));
        }
    }

    int ans = -1;
    if (dist[H-1][W-1] != INF) {
        ans = H*W - black - (dist[H-1][W-1] + 1);
    }
    cout << ans << endl;


    return 0;
}


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

int main(){

  int n,k;
  int ct=0;
  int save = 0;
  double ans = 0;
  cin >> n >> k;
  for(int i=1;i<=n;i++){
    save = i;
    while(save<=k-1){
      save *= 2;
      ct++;
    }

    ans += (1/(pow(2,ct)*n));
    ct = 0;
  }
  printf("%.32f\n",ans);
}

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

int main(){
	int n;
	cin >> n;
	string t;
	set<string> s;
	for(int i=0; i<n; ++i){
		cin >> t;
		s.insert(t);
	}
	cout << s.size() << endl;
	return 0;
} 

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

using namespace std;
typedef long long ll;
typedef long double lb;
#define mod 10000000007
#define REP(i,j,n) for (int i=j;i<(n);i++)
#define RREP(i,n) for (int i = n; 0<i;i--)
#define print(out) cout<< out  << "\n"

int main(){
  ll N,K;cin>>N>>K;
  int ans=0;
  while(pow(K,ans)<=N){
    ans++;
  }
  print((ans));
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int x, n;

    cin >> x >> n;
    set<int> p;

    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        p.insert(a);
    }

    ll ans = 111;

    for (int i = 110; i >= -10; i--)
    {
        if (abs(x - ans) >= abs(x - i) && p.find(i) == p.end())
        {
            ans = i;
        }
    }

    cout << ans << endl;
}


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

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

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

    int n; ll w;
    cin >> n >> w;
    V<ll> dp(100100, TEN(18));
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        for (int j = 100099; j >= y; j--) {
            dp[j] = min(dp[j], dp[j - y] + x);
        }
    }
    for (int j = 100099; j >= 0; j--) {
        if (dp[j] <= w) {
            cout << j << endl;
            return 0;
        }
    }
    assert(false);
    return 0;
}


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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

void solve(){
    i64 N,M;
    cin >> N >> M;

    vector<i64> A(N);
    rep(i,0,N) cin >> A[i];
    
    map<i64,i64> cnt;
    i64 acc=A[0];
    ++cnt[A[0]%M];
    rep(i,1,N){
        acc+=A[i];
        ++cnt[acc%M];
    }
    
    i64 ans=0;
    acc=0;
    rep(i,0,N){
        ans+=cnt[acc%M];
        acc+=A[i];
        --cnt[acc%M];
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 4992
S = list(input())
rtu = "Yes"
ks = 1
for i in S:
    if ks == 1:
        if i == "L":
            rtu = "No"
            ks = 0
            break
        else:
            ks = 0
    elif ks == 0:
        if i == "R":
            rtu = "No"
            ks = 1
            break
        else:
            ks = 1
print(rtu)

Measured memory_bytes: 3060
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

ll mod = 1e9 + 7;
int n, cnt[26];
char s[100010];
int main() {
	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 0; i < n; i++)
		cnt[s[i] - 'a']++;
	ll r = 1;
	for (int i = 0; i < 26; i++)
		r = r * (cnt[i] + 1) % mod;
	r = (r + mod - 1) % mod;
	printf("%lld\n", r);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int dp[n] = {0};
	dp[0] = 0;
	dp[1] = abs(a[1] - a[0]);
	for(int i = 2; i < n; ++i) {
		dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));
	}
	cout<<dp[n - 1];
}

Measured memory_bytes: 4392
sub f{my$a=pop;
	++$d,$$a{$_}>$x[$_]++&&f($_),--$d,--$x[$_]for 2..$N;
	$%+=$d==$N
}
$N=<>;${$`}{$'+0}=${$'+0}{$`}=/ / for<>;
print f$d=1


Measured memory_bytes: 512
N = int(input())
A = list(map(int, input().split()))
cnt = 0
f = True
while f:
    f = False
    for i in range(N):
        if A[i] >= N - cnt:
            q, m = divmod(A[i] + cnt + 1, N+1)
            A[i] = m - cnt - 1
            cnt += q
            f = True
print(cnt)


Measured memory_bytes: 3060
const main = arg => {
    const input = arg.trim().split("\n");
    const n = parseInt(input[0]);
    const arr = input[1].split(" ").map(item => BigInt(item));

    if(arr.includes(0n)){
        console.log(0)
        return
    } 
    let ret = 1n
    for(let item of arr){
        ret = ret*item
        if(ret > BigInt(1000000000000000000)){
            console.log(-1)
            return
        }
    }
    console.log(ret.toString())
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  


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

using namespace std;

const int maxn=1e3+5;

int dp[maxn][maxn];
string s1,s2;

void lcs()
{
    int len1=s1.size();
    int len2=s2.size();
    s1=" "+s1;
    s2=" "+s2;
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(s1[i]==s2[j]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
//    for(int i=0;i<=len1;i++){
//        for(int j=0;j<=len2;j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    cout<<dp[len1][len2]<<endl;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s1>>s2;
        lcs();
    }
    return 0;
}



Measured memory_bytes: 7088
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()

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

int root(int i,vector<int> &parent){
    if(parent[i]==-1){
        return i;
    }else{
        int result=root(parent[i],parent);
        parent[i]=result; //パス圧縮
        return result;
    }
}

int main(){
    int n,q;
    cin >> n >> q;
    vector<int> parent(n,-1); //-1が親なしを示す
    for(int i=0;i<q;++i){
        int com,x,y;
        cin >> com >> x >> y;
        if(com==0){
            //unite
            if(root(x,parent)!=root(y,parent)){
                parent[root(y,parent)]=root(x,parent);
            }
        }else{
            //same
            if(root(x,parent)==root(y,parent)){
                cout << 1 << endl;
            }else{
                cout << 0 << endl;
            }
        }
    }
}


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

int main() {
  int n, p;
  cin >> n >> p;
  string s;
  cin >> s;
  if (p == 2 || p == 5){
    ll ans = 0;
    rep(i,n){
      if((s[i] - '0') % p == 0){
        ans += i + 1;
      }
    }
    cout << ans << endl;
    return 0;
  }
  vector<int> d(n + 1);
  int ten = 1;
  for (int i = n - 1; i >= 0; i--){
    int a = (s[i] - '0') * ten % p;
    d[i] = (d[i + 1] + a) % p;
    ten *= 10; ten %= p;
  }
  vector<int> cnt(p);
  ll ans = 0;
  for (int i = n; i >= 0; i--) {
    ans += cnt[d[i]];
    cnt[d[i]]++;
  }
  cout << ans << endl;
  return 0;
}

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

MOD = 10 ** 9 + 7
N = 3000
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD

def main():
    MOD = 10 ** 9 + 7
    s = int(input())
    ans = 0
    for i in range(1, s // 3 + 1):
        n = s - 3 * i
        ans += nCk(i + n - 1, n)
        ans %= MOD
    print(ans)

main()

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



using namespace std;



using ull = unsigned long long;



typedef bitset<64> ULLBitSet;



int main(){

  int n;

  vector <ULLBitSet> a;



  ull tmp_ull;



  cin >> n;

  cin.ignore();



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

    cin >> tmp_ull;

    ULLBitSet tmp(tmp_ull);

    a.push_back(tmp);

  }



  ULLBitSet sum;

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

    sum = sum | a[i];

  }



  int ans = 0;

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

    if(sum[i] == 0){

      ++ans;

    } else {

      break;

    }

  }



  cout << ans << endl;

  return 0;

  

}



    



Measured memory_bytes: 256
void main() {
    int n = readln.chomp.to!int;
    int[] h = readln.split.to!(int[]);
    int hs = h[0];
    int cnt = 1;
    foreach (i; 1 .. n) {
        if (h[i] >= hs) {
            ++cnt;
            hs = h[i];
        }
    }
    cnt.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.container;
import std.typecons;

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }

const int mod=1e9+7;
const int INF=1001001001;
int main() {
  int N;
  cin>>N;
  vector<double>p(N);
  for(int i=0;i<N;i++){
    cin>>p[i];
  }
  vector<vector<double>>dp(N+1,vector<double>(N+1));
  dp[0][0]=1;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      if(j==0){dp[i+1][j]=dp[i][j]*(1-p[i]);}
      dp[i+1][j+1]=dp[i][j]*(p[i])+dp[i][j+1]*(1-p[i]);
    }
  }
  double ans=0;
  for(int j=N/2+1;j<=N;j++){
    ans+=dp[N][j];
  }
  cout<<fixed<<setprecision(10)<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 73740
N = int(input())
A = reversed(tuple(enumerate(map(int, input().split()), 1)))

boxes = [0] * (N + 1)
ans = []

for n, digit in A:
    put = sum(d for d in boxes[n::n]) & 1 != digit
    if put:
        boxes[n] = 1
        ans.append(n)

print(len(ans))
if ans:
    print(*ans)


Measured memory_bytes: 27804
n = int(input())
csf = []
for i in range(n-1):
    t = list(map(int, input().split()))
    csf.append(t)

ans = []
for i in range(n-1):
    now = 0
    for c,s,f in csf[i:]:
        if now < s:
            now = s
        now += (s-now)%f+c
    ans.append(now)
ans.append(0)

for a in ans:
    print(a)

Measured memory_bytes: 3188
n = int(input())
ls = [list(map(int,input().split())) for _ in range(n-1)]
def culc(nt,p):
    if nt == 0:
        if p != n-1:
            nt = ls[p][1] + ls[p][0]
            culc(nt,p+1)
        else:
            print(0)
    else:
        if p != n-1:
            if nt >= ls[p][1]:
                m = (nt - ls[p][1])//ls[p][2]
                if (nt - ls[p][1])%ls[p][2] != 0:
                    m += 1
                nt = ls[p][1] + ls[p][2]*m + ls[p][0]
                culc(nt,p+1)
            else:
                nt = ls[p][1] + ls[p][0]
                culc(nt,p+1)
        else:
            print(nt)
for i in range(n):
    culc(0,i)



Measured memory_bytes: 9368
n,k = list(map(int, input().split()))
h = list(map(int, input().split()))

for _ in range(k):
    h.insert(0, float("inf"))

dp = [0 for _ in range(n+k)]

for i in range(k, n+k-1):
    s1 = []
    for j in range(k):
        s1.append(dp[i-j] + abs(h[i+1] - h[i-j]))
    dp[i+1] = min( s1 )

print(dp[-1])

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

ll N, M;
char S[100010];
char T[100010];

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

int main()
{
	cin >> N >> M;
	cin >> S >> T;
	auto d = gcd(N, M);
	auto L = N * M / d;
	ll j = 0;
	for (ll i = 0; i < N; ++i) {
		auto idx1 = L / N * i;
		for (; j < M; ++j) {
			auto idx2 = L / M * j;
			if (idx1 == idx2) {
				if (S[i] != T[j]) {
					cout << -1 << endl;
					return 0;
				}
			}
			else if (idx1 < idx2) {
				break;
			}
		}
	}
	cout << L << endl;
	return 0;
}

Measured memory_bytes: 384
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int L, R, d;
  cin >> L;
  cin >> R;
  cin >> d;
  
  int sum = 0;
  for(int i=L; i<R+1; i++) {
    if (i%d == 0) sum++;
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 3632
s = int(input())

def func(x):
    if x % 2 == 0:
        return int(x/2)

    return 3*x + 1

A = [s]
tmp = func(s)
ans = 2
for i in range(2,1000001):
    if tmp in A:
        print(ans)
        break
    else:
        A.append(tmp)
        tmp = func(A[-1])
        ans += 1

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

int main(){
  string s,l,ss="#";
  int a,now,nnow,cou;
  l="qwertasdfgzxcvb";
  while(1){
    cin>>s;
    if(s==ss)break;
    a=s.size();
    if(l.find(s[0])==-1)now=0;
    else now=1;
    cou=0;
    for(int i=1;i<a;i++){//最後まで
      if(l.find(s[i])==-1)nnow=0;
      else nnow=1;
      if(now!=nnow){
	cou++;
	now=nnow;
      }
    }
    cout << cou << endl;
  }
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
#define ll long long int
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define rep(i,a,n)   for(int i=a;i<n;i++)
#define pb           push_back
#define ff           first
#define ss           second
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define all(v)       v.begin(),v.end()
#define rall(v)      v.rbegin(),v.rend()
#define Pi           2*acos(0.0)
#define pii          pair<int,int>
#define pll          pair<ll,ll>
#define mem(a,b)     memset(a, b, sizeof(a))
#define fill_(a,b)   fill(a,a+n,b);
using namespace std;

ll modpow(ll a,ll b,ll m = mod){
	ll res = 1;
	while(b>0){
		if(b&1)
			res = (res*a)%m;
		a = (a*a)%m;
		b>>=1;
	}
	return res;
}
ll gcd(ll a,ll b){
	while(b>0){
		ll r = a%b;
		a = b; b = r;
	}
	return a;
}
int getSteps(int x){
    int res=0;
    while(x>0){
        x = x%__builtin_popcount(x);     
        res++;
    }
    return res;
    
}
int main()
{
	 
   boost
   #ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int t=1;
// 	cin>>t;
	while(t--)
	{
	    ll n;
	    cin>>n;
	    string s;
	    cin>>s;
	    ll cnt = 0;
	    for(int i=0;i<s.length();i++){
	        cnt+=(s[i]=='1'?1:0);
	    }
	    ll res = 0,resm = 0,resp = 0;
	    for(int i=0;i<s.length();i++){
	        if(s[i]=='0') continue;
	        res+=modpow(2,n-i-1,cnt);
	        if(cnt>1){
	           
	            resm+=modpow(2,n-i-1,cnt-1);
	            resm%=(cnt-1);
	        }
	        resp+=modpow(2,n-i-1,cnt+1);
	        resp%=(cnt+1);

	    }

	   // cout<<cnt<<" "<<resp<<" "<<resm<<"\n";
	    for(int i=0;i<s.length();i++){
	        if(s[i]=='1'){
	            
	            if(cnt-1==0)
	            cout<<"0\n";
	            else{ 
	                int temp = (resm - modpow(2,n-i-1,cnt-1) + cnt-1)%(cnt-1);
	                cout<<1+getSteps(temp)<<"\n";        
	            }
	        }
	        else{
	            int temp = (resp + modpow(2,n-i-1,cnt+1))%(cnt+1);
	            cout<<1+getSteps(temp)<<"\n";
	        }
	    }
	}
    return 0;
}


Measured memory_bytes: 3736
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
map = [list(input()) for _ in range(H)]
from collections import deque

que = deque()
seen = [[-1]*W for _ in range(H)]
max = 0



for i in range(H):
    for j in range(W):
        if map[i][j] == "#":
            que.append([i,j])
            seen[i][j] = 0

while que:
    #print(que)
    y, x = que.popleft()
    for dy, dx in ([0,1],[0,-1],[1,0],[-1,0]):
        ny = y + dy
        nx = x + dx
        if 0<=ny<H and 0<=nx<W and seen[ny][nx]==-1:
            seen[ny][nx] = seen[y][x] + 1
            que.append([ny,nx])
            if max < seen[ny][nx]:
                max = seen[ny][nx]

print(max)


Measured memory_bytes: 175964
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000
int p[N];
vector<pair<int, long long> >e[N];
long long xx[N];
int da, db;
bool v;

void init(void){
	v = true;
	f(i, N){
		p[i] = i;
		xx[i] = MOD;
	}
	v = true;
	return;
}

int par(int x,int y){
	if (p[x] == x)return x;
	else{
		if (y == 0)da++;
		else db++;
		p[x] = par(p[x], y);
		return p[x];
	}
	return 0;
}

void uni(int x, int y){
	da = 0;
	db = 0;
	x = par(x,0);
	y = par(y,1);
	if(da>db)p[y] = x;
	else p[x] = y;
	return;
}

void dfs(int x){
	for (int i = 0; i < e[x].size();i++){
		if (xx[e[x][i].first] == MOD){
			xx[e[x][i].first] = xx[x] + e[x][i].second;
			dfs(e[x][i].first);
			if (v == false)break;
		}
		else{
			if (xx[e[x][i].first] != xx[x] + e[x][i].second){
				v = false;
				break;
			}
		}
	}
	return;
}


int main(){
	int a[N];
	f(i, N)a[i] = 0;
	int x, y, z;
	int n, k, m;
	long long s, ans;
	ans = 0;
	init();
	scanf("%d %d", &n,&m);
	for (int i = 0; i < m; i++){
		scanf("%d %d %lld", &x,&y,&s);
		x--;
		y--;
		e[x].push_back(make_pair(y, s));
		e[y].push_back(make_pair(x, -s));
		uni(x, y);
	}
	for (int i = 0; i < n; i++){
		da = 0;
		p[i] = par(i, 0);
	}
	for (int i = 0; i < n; i++){
		if (p[i] == i){
			xx[i] = 0;
			dfs(i);
			if (v == false)break;
		}
	}
	
	if(v)printf("Yes\n");
	else printf("No\n");


	return 0;
}

Measured memory_bytes: 20352
#include<bits/stdc++.h>
#define long long long
using namespace std;
const int N=3e5;
const long mod=1e9+7;
long aa[N+2],cnt[N+2][62];
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  int n;cin>>n;
  for(int i=1;i<=n;i++)cin>>aa[i];

  for(int i=n;i>=1;i--)
  {
    for(int j=0;j<60;j++)
      cnt[i][j]=cnt[i+1][j]+(bool)(aa[i]&(1LL<<j));
  }

  long ans=0;
  for(int i=1;i<=n;i++)
  {
    for(int j=0;j<60;j++)
    {
      bool f=(bool)(aa[i]&(1LL<<j));
      if(!f)ans=(ans+((1LL<<j)%mod)*cnt[i+1][j])%mod;
      else ans=(ans+((1LL<<j)%mod)*(n-i-cnt[i+1][j]))%mod;
    }
  }
  cout<<ans<<endl;
  return 0;
}

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

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

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
//#include <bits/stdc++.h>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string yn(bool x){
    return x ? "Yes" : "No";
}
int main()
{
    int n,d,x; cin >> n >> d >> x;
    int a[n];
    rep(i,n) cin >> a[i];
    
    int ans = 0;
    rep(i,n){
        ans += ((d-1)/a[i])+1;
    }

    cout << ans + x << endl;
}



Measured memory_bytes: 256
from collections import defaultdict
n,m = map(int,input().split())
d = defaultdict(list)
l = [0] * m
for i in range(m):
  p,y = map(int,input().split())
  d[p].append((y,i))
for k,cities in d.items():
  cities.sort()
  for j in range(len(cities)):
    _,i = cities[j]
    l[i] = "0" * (6 - len(str(k))) + str(k) + "0" * (6 - len(str(j + 1))) + str(j + 1)
print(*l,sep="\n")

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

int main(){

  int w, h, x, y, r; cin >> w >> h >> x >> y >> r;
  int up = y + r;
  int right = x + r;
  int down = y - r;
  int left = x - r;

  if(left < 0 || down < 0 || right > w || up > h) cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 3100
import java.util.Scanner;

public class Main {
    int n;
    int[] as;

    public static void main(String[] args) {
        Main m = new Main();
        m.read();
        m.solve();
    }

    private void read() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        as = new int[n];
        for (int i = 0; i < n; i++)
            as[i] = sc.nextInt();
    }

    private void solve() {
        int mod4 = 0, mod2 = 0, mod1 = 0;
        for (int i = 0; i < n; i++) {
            if (as[i] % 4 == 0) {
                mod4++;
            }
            else if(as[i] % 2 == 0) {
                mod2++;
            }
            else {
                mod1++;
            }
        }
        if (mod2 % 2 != 0) {
            mod1++;
        }
            if (mod4 - mod1 >= -1) {
                System.out.println("Yes");
            }
            else {
                System.out.println("No");
            }
    }
}


Measured memory_bytes: 49148
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
    long double a,b,c;
    cin>>a>>b>>c;
    long double d = sqrt(a);
    long double e = sqrt(b);
    if(a+b+2*d*e<c){
        cout<<"Yes";
        return 0;
    }else {
        cout<<"No";
        return 0;
    }
    long double g = d*e;
    long double f = c-a-b;
    if(c-a-b<0){
        cout<<"No"<<endl;
        return 0;
    }
    f/=2.0;
    if(g<f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1LL << 30;

ll choose2(int n){
  return (ll)n * ((ll)n - 1) / 2;
}

int main(){
  int N;
  cin >> N;
  vi A(N);
  map<int, int> m;
  vi C(0);
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
    if(!m.count(A.at(i))){
      m[A.at(i)] = C.size();
      C.push_back(1);
    }
    else{
      C.at(m.at(A.at(i)))++;
    }
  }
  ll res = 0;
  for(auto x: C) res += choose2(x);
  for(int i = 0; i < N; i++){
    ll result = res;
    result -= choose2(C.at(m.at(A.at(i))));
    result += choose2(C.at(m.at(A.at(i)))-1);
    cout << result << endl;
  }
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n;
    cin >> n;
    int32 a[n+1];
    REP(i,n+1)cin >> a[i];
    int64 ans = 0;
    REP(i,n){
        int32 b;
        cin >> b;
        int32 x = min(b, a[i]);
        ans += x;
        b -= x;
        a[i] -= x;
        int32 y = min(b, a[i+1]);
        ans += y;
        b -= y;
        a[i+1] -= y;
    }
    ANS(ans);
    return 0;
}

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

signed main() {
  int m;
  cin >> m;
  map<string, pair<int, int>> range;
  rep(i, m) {
    string name;
    int lb, ub;
    cin >> name >> lb >> ub;
    range[name] = {lb, ub};
  }
  int n;
  cin >> n;
  vector<string> es(n);
  rep(i, n) cin >> es[i];
  stack<bitset<256>> sets;
  for (auto &&e : es) {
    bitset<256> top;
    if (isdigit(e[0])) {
      top[stoi(e)] = true;
    } else if (isalpha(e[0])) {
      loop(i, range[e].first, range[e].second + 1) top[i] = true;
    } else {
      bitset<256> y = sets.top();
      sets.pop();
      bitset<256> x = sets.top();
      sets.pop();
      rep(i, 256) rep(j, 256) if (x[i] && y[j]) {
        if (e == "+") top[(i + j) % 256] = true;
        if (e == "-") top[(i - j + 256) % 256] = true;
        if (e == "*") top[(i * j) % 256] = true;
        if (e == "/") {
          if (j == 0) return cout << "error" << endl, 0;
          top[(i / j) % 256] = true;
        }
      }
    }
    sets.emplace(top);
  }
  cout << "correct" << endl;
}



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

int main() {
  string S;
  cin >> S;
  if(S=="A"){
    cout << "A" <<endl;
  }
  else if(S=="B"){
    cout << "A" <<endl;
  }
  else if(S=="C"){
    cout << "A" <<endl;
  }
  else if(S=="D"){
    cout << "A" <<endl;
  }
  else if(S=="E"){
    cout << "A" <<endl;
  }
  else if(S=="F"){
    cout << "A" <<endl;
  }
  else if(S=="G"){
    cout << "A" <<endl;
  }
  else if(S=="H"){
    cout << "A" <<endl;
  }
  else if(S=="I"){
    cout << "A" <<endl;
  }
  else if(S=="J"){
    cout << "A" <<endl;
  }
  else if(S=="K"){
    cout << "A" <<endl;
  }
  else if(S=="L"){
    cout << "A" <<endl;
  }
  else if(S=="M"){
    cout << "A" <<endl;
  }
  else if(S=="N"){
    cout << "A" <<endl;
  }
  else if(S=="O"){
    cout << "A" <<endl;
  }
  else if(S=="P"){
    cout << "A" <<endl;
  }
  else if(S=="Q"){
    cout << "A" <<endl;
  }
  else if(S=="R"){
    cout << "A" <<endl;
  }
  else if(S=="S"){
    cout << "A" <<endl;
  }
  else if(S=="T"){
    cout << "A" <<endl;
  }
  else if(S=="U"){
    cout << "A" <<endl;
  }
  else if(S=="V"){
    cout << "A" <<endl;
  }
  else if(S=="W"){  
    cout << "A" <<endl;
  }
  else if(S=="X"){  
    cout << "A" <<endl;
  }  
  else if(S=="Y"){  
    cout << "A" <<endl;
  }
  else if(S=="Z"){  
    cout << "A" <<endl;
  }
  else{
    cout << "a" <<endl;
  }
}

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


def solve():
    N, q = map(int, input().split())
    root = [-1] * N
    rank = [0] * N

    def find(x: int) -> int:
        if root[x] < 0:
            return x
        else:
            while root[x] >= 0:
                x = root[x]
            return x

    def union(x: int, y: int):
        x = find(x)
        y = find(y)
        if x == y:
            return
        elif rank[x] > rank[y]:
            root[x] += root[y]
            root[y] = x
        else:
            root[y] += root[x]
            root[x] = y
            if rank[x] == rank[y]:
                rank[y] += 1

    for _ in range(q):
        t, u, v = map(int, input().split())
        if t:
            print(int(find(u) == find(v)))
        else:
            union(u, v)


solve()


Measured memory_bytes: 76116
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner( System.in );
		double r = sc.nextDouble();
		
		double PI		= 3.14159265359;
		
		double area		= r * r * PI;
		double circle	= 2 * PI * r;
		
		System.out.printf("%.6f %.6f", area, circle);
	}
}

Measured memory_bytes: 19068
N = gets.chomp.to_i
b = Array.new(N)
str = gets.split
for i in 0...N-1 do
    b[i] = str[i].to_i
end

answer = b[0] + b[N-2]
for i in 0...N-2 do
    answer += b[i] < b[i+1] ? b[i] : b[i+1]
end

puts answer

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a;
  cin>>a;
  int ans=0;
  int n;
  for(int i=0;i<a.size();i+=n){
    n=0;
    if(a[i]=='A'||a[i]=='T'||a[i]=='C'||a[i]=='G'){
      n++;
      if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
        n++;
        if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
          n++;
          if(a[i+n]=='A'||a[n+i]=='T'||a[i+n]=='C'||a[i+n]=='G'){
            n++;
            if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
              n++;
              if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
                n++;
                if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
                  n++;
                  if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
                    n++;
                    if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
                      n++;
                      if(a[i+n]=='A'||a[i+n]=='T'||a[i+n]=='C'||a[i+n]=='G'){
                        n++;
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
    if(n>ans){
      ans=n;
    }
    n++;
  }
  cout<<ans<<endl;    
}

Measured memory_bytes: 256
#include <iostream>
#include <atcoder/dsu>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    atcoder::dsu dsu(n);
    for (int i = 0; i < q; i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) dsu.merge(u, v);
        else if (t == 1)  cout << dsu.same(u, v) << endl;
    }
}


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

const int MAX_N = 100005;

/* UNION FIND木 */
int par[MAX_N]; //親
int ranks[MAX_N]; //子

// n要素で初期化
void init(int n){
  for(int i=0; i<n; i++){
    par[i] = i;
    ranks[i] = 0;
  }
}

// 木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if(x == y) {
    return;
  }
  if(ranks[x] < ranks[y]){
    par[x] = y;
  } else {
    par[y] = x;
    if(ranks[x] == ranks[y]){
      ranks[x]++;
    }
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y){
  return find(x) == find(y);
}


int main() {
  int N, M;
  int x, y, z;
  cin >> N >> M;
  init(N);
  rep(i, M) {
    scanf("%d %d %d", &x, &y, &z);
    x--; y--;
    unite(x, y);
  }
  set<int> idx;
  rep(i, N) {
    find(i);
  }
  rep(i, N) {
    idx.insert(par[i]);
  }
  cout << idx.size() << endl;
  return 0;
}


Measured memory_bytes: 5760
n = int(input())
s = input()
s = s.replace('R', '0')
s = s.replace('G', '1')
s = s.replace('B', '2')

s0 = [0] * (n + 5)
s1 = [0] * (n + 5)
s2 = [0] * (n + 5)

for i in range(n):
    s0[i + 1] = s0[i] + (s[i] == '0')
    s1[i + 1] = s1[i] + (s[i] == '1')
    s2[i + 1] = s2[i] + (s[i] == '2')

#print(s0)
#print(s1)
#print(s2)

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]: continue
        h = 99 - (ord(s[i]) + ord(s[j]))
        if h == 0:
            ans += s0[n] - s0[j]
            if 2 * j - i < n and s[2 * j - i] == '0': ans -= 1
        if h == 1:
            ans += s1[n] - s1[j]
            if 2 * j - i < n and s[2 * j - i] == '1': ans -= 1
        if h == 2:
            ans += s2[n] - s2[j]
            if 2 * j - i < n and s[2 * j - i] == '2': ans -= 1
        #print(i, j, h, ans)
print(ans)


Measured memory_bytes: 68652
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,pair<int,int> > P;
typedef unsigned long long int ull;
const ll MOD=1e9+7;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXH=500;
const int MAXW=500;
const ll INF=1e9;

int main(){
    int n;cin>>n;
    vector<vector<int> > a(n,vector<int>(n));
    vector<vector<bool> > brg(n,vector<bool>(n,false));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
            if(j<i) brg[i][j]=true;
        }
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(a[i][j]>a[i][k]+a[k][j]){
                    cout<<-1<<endl;
                    return 0;
                }else if(i!=k&&j!=k&&a[i][j]==a[i][k]+a[k][j]){
                    brg[i][j]=false;
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(brg[i][j]) ans+=a[i][j];
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define MOD 1000000007
#define fastio std::ios_base::sync_with_stdio(false);
#define ll long long

int main(){

    fastio;
    
    int n;
    string s;
    vector <string> v;
    cin >> n;
    for(int  i = 0; i < n; i++){
        cin >> s;
        v.push_back(s);
    }
    for(int i = 0; i < n; i++)
        v.push_back(v[i]);
    ll ans = 0;
    for(int k = 0; k < n; k++){
        int flag = 0;
        for(int i = k; i < k+n; i++){
            for(int j = 0; j < n; j++){
                if(v[i][j] != v[j+k][i-k]){
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 0)
            ans += n;
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 512
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    H,W,K=mis()
    c = [input() for _ in range(H)]
    ans = 0
    for D in product((0, 1), repeat=H+W):
        h = D[:H]
        w = D[H:]
        if sum(c[y][x]=='#' and not w[x] and not h[y] for x, y in product(range(W), range(H))) == K:
            ans += 1
    print(ans)






main()



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

#define ld long double
#define ll long long
#define ull unsigned long long

#define f first
#define s second

#define endl '\n'
#define pii pair <ll, ll>

#define ios ios_base::sync_with_stdio(0), cin.tie()
#define pb push_back
#define mp make_pair

#define pi 3.14159265358979323846264
#define y1 abacaba

using namespace std;

const int MXN = 1e5 + 30;
const int MAXN = 1e3 + 2;
const ll INF = 1e9 + 7;
const ll BINF = 1e18;
const int MOD = 1e9 + 7;
const ld EPS = 1e-15;   
const ll dx[] = {0, 0, 1, -1};      
const ll dy[] = {1, -1, 0, 0};
           
string a;
int n;

int cnt;

int main(){
    //freopen("input.txt", "r", stdin); 
    cin >> a;
    n = a.size();
    a = '$' + a;
    for(int i = 0; i <= n; i++){
        if(a[i] == a[i - 1]) cnt ++;
        else cnt = 1;
        if(cnt == 3) return cout << "Yes", 0; 
    } 
    cout << "No";
    return 0;
}

Measured memory_bytes: 384
tmp = list(map(int, input().split()))
x = tmp[0]
y = tmp[1]
z = tmp[2]
k = tmp[3]
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ansl = []
for p in range(x):
  if p > k:
    break
  for q in range(y):
    if p * q > k:
      break
    for r in range(z):
      if p * q * r > k:
        break
      ansl.append(a[p] + b[q] + c[r])

ansl.sort(reverse=True)

for i in range(k):
  print(ansl[i])

Measured memory_bytes: 105324
#include <stdio.h>
int main()
{
    int num=1, i=1, x, n=1;

    for(x=1;x<=9;x++)
    {
        for(i=1; i<=9; i++)
        {
            printf("%dx%d=%d\n", n, i, n*i);
        }
        n++;
    }

    return 0;
}

Measured memory_bytes: 524
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int INF = 1 << 28;
const double EPS = 1e-10;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------


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

	if (a <= 0 && b >= 0) {
		cout << "Zero" << endl;
		return 0;
	}

	if (a < 0 && b < 0 && (b - a) % 2 == 0 ) {
		cout << "Negative" << endl;
		return 0;
	}

	cout << "Positive" << endl;

	return 0;
}








Measured memory_bytes: 384
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a//gcd(a,b)*b

n=int(input())
A=[int(i) for i in input().split()]
ans=A[0]
for i in range(n):
    ans=lcm(ans,A[i])
result=0
for i in range(n):
    result+=(ans-1)%A[i]
print(result)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,nxt,id,color;
}e[200001];
inline bool cmp(node x,node y){
if(x. id!=y. id)return x. id<y.id;
return x.color>y.color;}
int n,cnt ,head[100001],ans,x,y;
inline void Add(int xx,int yy,int iidd){
e[++cnt]. to=yy;
e[cnt].nxt=head[xx];
e[cnt]. id=iidd;
head[xx]=cnt;}
void Df5(int xx,int fa,int lst){
int cc=0; 
for(register int i=head[xx];i;i=e[i].nxt){
if(e[i].to!=fa){
++cc;
if(cc==lst)++cc;
e[i].color=cc;
if(cc>ans)ans=cc;
Df5(e[i].to,xx,cc);
}
}
}
int main(){
scanf("%d",&n);
for(register int i=1;i<n;i++){
scanf( "%d%d" ,&x,&y);
Add(x,y,i);
Add(y,x,i);}
Df5(1,0,0);
printf("%d\n" ,ans);
sort(e+1,e+(n-1)*2+1,cmp);
for(register int i=1;i<=(n-1)*2;i++)if(e[i]. id!=e[i-1]. id)printf("%d\n" ,e[i]. color);
}

Measured memory_bytes: 5120
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言
#define MAX 100000

//問題をよく読もう！
//論理的に考えよう！
//サンプルを確認しよう!
//絶対に諦めるな！
//工夫をしろ！
int main() {
  int N, K;
  cin >> N >> K;

  if(N < K)
    cout << 1 << endl;
  else if(N%K == 0)
    cout << 0 << endl;
  else
    cout << 1 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
#define P pair<int, int>
int main () {
    ll x;   cin >> x;
    ll sum=0, t=0;
    while(sum<x){
        t += 1;
        sum += t;
    }
 
    cout << min(x, t) << endl;

}

 


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<unordered_map>
#include<bitset>

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

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int main(){
  string s;
  cin >> s;
  s = s + "T";
  int x, y;
  cin >> x >> y;
  bitset<20000> bx(1), by(1);
  bx = bx << 10000;
  by = by << 10000;
  bool flag = true, first = true;
  int cnt = 0;
  for(char c : s){
    if(c == 'F'){
      cnt += 1;
    }else{
      if(first){
        x -= cnt;
        first = false;
      }else if(flag){
        bx = (bx << cnt) | (bx >> cnt);
      }else{
        by = (by << cnt) | (by >> cnt);
      }
      flag = !flag;
      cnt = 0;
    }
  }
  x += 10000;
  y += 10000;
  //cout << x << " " << y << endl;
  bitset<20000> bu(1);
  if(((bu << x) & bx) != 0 && ((bu << y) & by) != 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}


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


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

void solve() {
  ll a, b;
  cin >> a >> b;
  ll g = gcd(a, b);
  int count = 1;
  for (ll i = 2; i * i < g; ++i) {
    if (g % i == 0) {
      count ++;
      while (g % i == 0) g /= i;
    }
  }
  if (g != 1) {
    count++;
  }

  cout << count << endl;

}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256