akhauriyash/Code-Regression huggingface dataset:
//#define CCF
//#define OLD

#ifndef CCF
	#pragma comment(linker, "/STACK:102400000,102400000")
    #ifdef OLD
		#pragma GCC diagnostic error "-std=c++11"
	#endif
	#pragma GCC optimize ("O3")
	#pragma GCC -mcmodle=large
#endif

#include <bits/stdc++.h>
using namespace std;

int n, m;
int w[100020];
int v[100020];
vector<int> a[100020];
int bestvalue;
int bestindex;
long long ans;

void dfs(int x) {
    v[x] = 1;
    	if (bestvalue > w[x]) {
    	bestvalue = w[x];
    	bestindex = x;
   	}
   	for (int i: a[x]) if (!v[i]) dfs(i);
}

int main() {
   	scanf("%d%d", &n, &m);
   	for (int i = 0; i < n; i++) {
   		scanf("%d", &w[i]);
   	}
   	for (int i = 0; i < m; i++) {
    	int x, y;
   		scanf("%d%d", &x, &y);
   		a[x].push_back(y);
		a[y].push_back(x);
   	}
   	int cnt = 0;
   	for (int i = 0; i < n; i++) {
    	if (!v[i]) {
   			bestvalue = 2e9;
   			bestindex = -1;
    		dfs(i);
    		cnt++;
    		ans += bestvalue;
    		w[bestindex] = 2e9;
    	}
    }
    sort(w, w + n);
    if (cnt == 1) {
    	printf("0\n");
    	exit(0);
    }
   	for (int i = 0; i < cnt - 2; i++) {
    	if (w[i] == 2e9) {
    		printf("Impossible\n");
   			exit(0);
    	}
    	ans += w[i];
   	}
   	printf("%lld\n", ans);
   	return 0;
}

Measured memory_bytes: 6528
// ░░░░░░░░( •̪●)░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░███████ ]▄▄▄▄▄▄▄▄▃░░░▃░░░░ ▃░
// ▂▄▅█████████▅▄▃▂░░░░░░░░░░░░░░░░░
// [███████████████████].░░░░░░░░░░░░░░
// ◥⊙▲⊙▲⊙▲⊙▲⊙▲⊙▲⊙◤...░░░░░░░░░░░░

//PointBlank's code (⌐■_■)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
 
#define repp(I, A, B) for(int I = A; I <= B; I++)
#define rep(I, A, B) for(int I = A; I < B; I++)
#define rrep(I, B, A) for(int I = B; I >= A; I--)
#define pb emplace_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define LB lower_bound
#define UB upper_bound
#define MP make_pair
#define mem(A, B) memset(A, B, sizeof(A));
#define mem0(A) memset(A, 0, sizeof(A));
#define quickio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(this) cerr<<"> "<<#this<<" : "<<this<<"\n"
#define bitsf(n) __builtin_popcount(n)
#define in_edges(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B), v[B].pb(A);}
#define in_edges2(M) repp(I, 1, M){ll A, B; cin >> A >> B; v[A].pb(B);}
#define endl "\n"
ll power(ll x, ll y); 

const ll MOD = 1000000007;
 
int main() //PointBlank's code ¯\_(ツ)_/¯
{
    ll h, w, A, B, C;
    cin >> h >> w;

    ll mn = 1e18;
    rep(i, 1, h){
        A = i*w;
        B = (h - i) * (w/2);
        C = (h - i) * (w - w/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
        B = w * ((h - i)/2);
        C = w * (h - i - (h - i)/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
    }

    swap(h, w);
    rep(i, 1, h){
        A = i*w;
        B = (h - i) * (w/2);
        C = (h - i) * (w - w/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
        B = w * ((h - i)/2);
        C = w * (h - i - (h - i)/2);
        mn = min(mn, max({A, B, C}) - min({A, B, C}));
    }

    cout << mn;
}

ll power(ll x, ll y)
{ 
    ll res = 1; x %= MOD;
    while(y > 0){if(y & 1) res = (res*x) % MOD; y = y>>1, x = (x*x) % MOD;} 
    return res; 
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int x[10000],y[10000],i,j,h,w;
  for(i=0;i<10000;i++){
    scanf("%d %d",&x[i],&y[i]);
    if(x[i]==0&&y[i]==0){
      break;
    }
  }
  for(j=0;j<i;j++){
    for(h=0;h<x[j];h++){
      for(w=0;w<y[j];w++){
        printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 2576
#include <bits/stdc++.h>
using namespace std;
#define MAX 10005
#define INFTY INT_MAX

struct Node {
    int point;
    int weight;
    Node() {}
    Node(int p, int w) {
        point = p;
        weight = w;
    }
};

bool operator<(Node left, Node right) {
    return (left.weight > right.weight);
}

vector<vector<Node> > vec(MAX);
vector<Node> ve;
priority_queue<Node> pq;
Node node;
int n;

void dijkstra() {
    int d[MAX], color[MAX];
    for (int i = 0; i < n; i++) {
        d[i] = INFTY;
        color[i] = 0;
    }
    d[0] = 0;
    pq.push(Node(0, d[0]));
    while (!pq.empty()) {
        node = pq.top();
        pq.pop();
        int u = node.point;
        color[u] = 1;
        if (d[u] < node.weight)
            continue;
        for (int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i].point;
            int c = vec[u][i].weight;
            if (d[u] + c < d[v]) {
                d[v] = d[u] + c;
                pq.push(Node(v, d[v]));
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i << " " << d[i] << endl;
    }
}

int main(void) {
    cin >> n;
    int u, k;
    for (int i = 0; i < n; i++) {
        ve.clear();
        cin >> u >> k;
        while (k--) {
            cin >> node.point >> node.weight;
            ve.push_back(node);
        }
        vec[u] = ve;
    }

    dijkstra();
}


Measured memory_bytes: 7232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, int b, int _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int n, m;
  cin >> n >> m;
  if (n == m) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N=int(input())
min=N-1
parr=make_divisors(N)
for i in range(len(parr)):
    if(parr[i]+N//parr[i]-2<N):
        min=parr[i]+N//parr[i]-2
print(min)


Measured memory_bytes: 3272
n, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
count = 0
for i in a:
    if x - i >= 0:
        x -= i
        count += 1
    else:
        x = 0
        break
if x != 0: count -= 1
print(count)

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

using namespace std;

#define FaSt ios::sync_with_stdio(0),cin.tie(0);
#define random uniform_int_distribution<long long>(1, 2000000000000000LL)(rng)

const int N = 105, K = 100005;
int n, k, a[N];
bool dp[K], solved[K];

bool calc(int i)
{
    if (solved[i])
    {
        return dp[i];
    }
    
    if (i == 0)
    {
        return 0;
    }
    
    for (int j = 0; j < n; j++)
    {
        if (i >= a[j] && calc(i - a[j]) == 0)
        {
            dp[i] = 1;
        }
    }
    
    solved[i] = 1;
    return dp[i];
}

int main()
{
    FaSt
    cin >> n >> k;
    
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    
    cout << (calc(k) == 1 ? "First" : "Second");
}


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

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

    x -= a;
    while(true){
        x -= b;
        if(x < 0){
            x += b;
            break;
        }
    }

    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

# a_1 > 0 の場合を試す
res, sum = 0, 0
if 0 < A[0]: sum = A[0]
else: res, sum = -A[0] + 1, 1

for i in range(1, N):
    if 0 < sum:
        if -1 < sum + A[i]: # a_i を足して、符号が変わらない
            res += abs(A[i] + sum + 1)
            sum = -1
        else: # a_i を足して符号が変わる
            sum += A[i]
    else:
        if sum + A[i] < 1:
            res += abs(A[i] - (-sum + 1))
            sum = 1
        else:
            sum += A[i]

ans = res

# a_1 < 0 の場合を試す
res, sum = 0, 0
if A[0] < 0: sum = A[0]
else: res, sum = A[0] + 1, -1

for i in range(1, N):
    if 0 < sum:
        if -1 < sum + A[i]: # a_i を足して、符号が変わらない
            res += abs(A[i] + sum + 1)
            sum = -1
        else: # a_i を足して符号が変わる
            sum += A[i]
    else:
        if sum + A[i] < 1:
            res += abs(A[i] - (-sum + 1))
            sum = 1
        else:
            sum += A[i]

ans = min(ans, res)
print(ans)

Measured memory_bytes: 14332
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vd = vector<double>;
using vi = vector<int>;

int main(){
    ll N;
    cin >> N;
    ll ans = 0;
    for(int i = 1; i < N; i++){
        ans += i;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N, A, B;
  cin >> N;
  A = N / 10;
  B = N % 1000;

  if ((A % 111 == 0) || (B % 111 == 0)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


int main() {
	int64_t N;
	cin >> N;
	int64_t ans = 1;
	for(int i=1; i<N; i++) {
		if (i*i<=N) ans = i*i;
		else {
			cout << ans << endl;
			return 0;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (ll)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

string S;

int main(){
    cin >> S;
    ll ct = 0, ans = 0;
    string T = "";
    rep(i,sz(S)){
        if(S[i] == 'B' && S[i+1] == 'C') T += 'X', ++i;
        else T += S[i];
    }
    
    ll i = 0;
    while(i < sz(T)){
        if(T[i] != 'X' && T[i] != 'A') ct=0;
        if(T[i] == 'A') ct++;
        if(T[i] == 'X') ans += ct;
        i++;
    }
    pr(ans);
}

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


def main():
    N,K = map(int, readline().split())

    i = 1
    r = 0
    while r != N:
        r = N % pow(K, i)
        i += 1

    print(i-1)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
'''
8方向走査

'.' は 空き、 '#' は爆弾の1行から複数行の「文字列」が与えられるので
Minesweeperのように、空きのマスに周囲8方向にある爆弾の数を埋める。
コンテスト中に実装すると、間違えることがあるので、dy や dx それらを使う部分は
予めスニペットなどで直ぐに読み出せるように準備しておく。
8方向走査の他、4方向走査、2方向走査も出題されるので準備しておく。
「文字列」 は 作成後に変更することができない。

ここでは、「文字列」 を 文字 の 「リスト」 とすることで 変更を可能にしている。
行継続文字はバックスラッシュ(円記号)

例えば if 条件 が長くなった場合、バックスラッシュを入れることで
その後の改行が無視されて行が継続していると見なされる。
上記のプログラム
if ny < 0 or H <= ny\
or nx < 0 or W <= nx:
バックスラッシュ無しで改行の場合、SyntaxError になる。
''(空文字).join(「リスト」)

「リスト」の 各要素 を 区切り文字 なし で結合して出力することができる。

' '(半角スペース).join(「リスト」)とすれば
「リスト」の 各要素 を 区切り文字 半角スペース で結合して出力することができる。
'''

# 下、右、上、左、右下、右上、左下、左上
dy = [1, 0, -1, 0, 1, -1, 1, -1]
dx = [0, 1, 0, -1, 1, 1, -1, -1]

H, W = map(int, input().split())
field = []

for i in range(H):
    field.append(list(input()))

for y in range(H):
    for x in range(W):

        if field[y][x] == '#':
            continue

        cnt = 0

        for k in range(8):
            ny = y + dy[k]
            nx = x + dx[k]

            if ny < 0 or H <= ny\
                    or nx < 0 or W <= nx:
                continue

            if field[ny][nx] == '#':
                cnt += 1

        field[y][x] = str(cnt)

for y in range(H):
    print("".join(field[y]))

Measured memory_bytes: 3188
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif

int main_A() {
    cin.tie(0);
    ios::sync_with_stdio(false);
     
    vs C(3); REP(i,3) cin >> C[i];

    string ans = {C[0][0], C[1][1], C[2][2]};

    cout << ans << endl;

    return 0;
}

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

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

  int sum = 0;
  for (int i = 8; i >= 0; i--) {
    int R = 1;
    for (int j = 0; j < i; j++) {
      R *= 10;
    }
    int nr = T / R;
    if (nr > 0) {
      sum += nr;
    }
    T -= nr * R;
  }

  if (N % sum == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}



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

int lcs(string a, string b){
    int i,j,m,n,mx=0;
    m=a.length();
    n=b.length();
    int c[m+1][n+1];
  
    
    for(i=0;i<m+1;i++) c[i][0]=0;
    for(i=0;i<n+1;i++) c[0][i]=0;
    
    for(i=1;i<m+1;i++){
        for(j=1;j<n+1;j++){
            if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1] + 1;
            else c[i][j]= max(c[i][j-1],c[i-1][j]);
          	mx = max(mx,c[i][j]);
        }
    }
  return mx;  
}

int main(){
    int n; cin>>n;
    for(int i=0;i<n;i++){
        string a,b; cin>>a>>b;
        cout<<lcs(a,b)<<endl;
    }
    return 0;
    
}


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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    if(s[0] == s[1] && s[1] == s[2]) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int num[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
    int k;
    while(cin>>k){
        cout<<num[k-1]<<endl;
    }
    return 0;
}


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 pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct BinaryIndexedTree{
    int n;
    vector<int>dat;
    BinaryIndexedTree(int n=0):n(n){
        dat.resize(n+1);
    }
    void add(int k,int x){
        for(k++;k<=n;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};

int N,M,Q;

int cnt[555][555];

signed main(){
    cin>>N>>M>>Q;
    rep(i,M){
        int l,r;
        cin>>l>>r;
        l--;
        cnt[l][r]++;
    }

    for(int len=2;len<=N;len++){
        for(int i=0;i+len<=N;i++){
            int j=i+len;
            cnt[i][j]+=cnt[i+1][j]+cnt[i][j-1]-cnt[i+1][j-1];
        }
    }

    while(Q--){
        int a,b;
        cin>>a>>b;
        a--;
        cout<<cnt[a][b]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3072
#include <stdio.h>

int main(void){
   int  p[26]={};
   char n;
   
   while(scanf("%c", &n) != EOF){
       if(n>='a' && n<='z') p[n-'a']++;
       else if(n>='A' && n<='Z') p[n-'A']++;
   }
   
   for(int i=0; i<26; i++){
       printf("%c : %d\n", i+'a', p[i]);
   }
   
   return 0;
    
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    string s;
    cin >> s;
    vector<bool> vec(s.size());
    for(int i = 0; i < s.size(); i++){
        char c = s[i];
        if(c == 'A' || c == 'T' || c == 'C' || c == 'G') vec[i] = true;
    }
    int length = 0;
    int mx = 0;
    for(int i = 0; i < s.size(); i++){
        if(vec[i]) {length++; mx = max(mx, length);}
        else length = 0;
    }
    cout << mx;
}

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

main = do
    [n,d] <- map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine
    xys <- replicateM n (format.map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine) :: IO [(Int,Int)]
    print $ answer d xys

format (x:y:_) = (x,y)

answer d = length . filter (<= fromIntegral d^2) . map dist

dist :: (Int,Int) -> Integer
dist (x,y) = fromIntegral x^2 + fromIntegral y^2

Measured memory_bytes: 51500
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a7=1000000007;
ll inf=100000000000000000;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
const int mod = 998244353;

const int maxn = 1e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    double ans = 0.0;
    for (int i = 1 ; i <= n ; i++) {
        double p = 1.0;
        int cur = i;
        while(cur < k) {
            cur <<= 1;
            p /= 2.0;
        }
        ans += p;
    }
    ans /= n;
    cout << fixed << setprecision(10) << ans << '\n';
}

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

int main()
{  int a,b,c,ans=0;
  scanf("%d %d %d",&a,&b,&c);
  if(a==b&&a!=c)printf("Yes");
  else if(a==c&&a!=b)printf("Yes");
  else if(b==c&&a!=b)printf("Yes");
  else printf("No");
}


Measured memory_bytes: 256
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int P=998244353;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){
	R int res=1;
	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;
	return res;
}
const int N=2e5+5,M=1e6+5;
int fac[M],ifac[M],bin[M],ibin[M];
inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
void init(int n=1e6){
	fac[0]=ifac[0]=bin[0]=ibin[0]=1;
	fp(i,1,n)fac[i]=mul(fac[i-1],i);
	ifac[n]=ksm(fac[n],P-2);
	fd(i,n-1,1)ifac[i]=mul(ifac[i+1],i+1);
	fp(i,1,n)bin[i]=mul(bin[i-1],2);
	fp(i,1,n)ibin[i]=mul(ibin[i-1],499122177);
}
char mp[4][N];int sum[4][N],f[N],b[N],s[N];
int n,m,res;
void calc(){
	memset(f,0,sizeof(f));
	memset(b,0,sizeof(b));
	memset(s,0,sizeof(s));
	R int x=sum[0][n],y,z;
	fp(i,0,m){
		if(mp[2][i+1]=='0'&&mp[3][i+1]=='0')continue;
		y=sum[2][i],z=sum[3][i];
		f[i]=(x?C(x+y+z-1,x-1):(!y&&!z));
	}
	x=sum[1][n];
	fd(i,m+1,1){
		if(mp[2][i-1]=='0'&&mp[3][i-1]=='0')continue;
		y=sum[2][m]-sum[2][i-1],z=sum[3][m]-sum[3][i-1];
		b[i]=(x?C(x+y+z-1,x-1):(!y&&!z));
	}
	fp(i,1,m)s[i]=s[i-1]+(mp[2][i]=='1'&&mp[3][i]=='1');
	fp(i,0,m)f[i]=mul(f[i],ibin[s[i]]);
	fd(i,m+1,1)b[i]=add(b[i+1],mul(b[i],bin[s[i-1]]));
	fp(i,1,m)upd(res,mul(f[i-1],b[i+1]));
}
int main(){
//	freopen("testdata.in","r",stdin);
	init();
	scanf("%d%d",&n,&m);
	fp(i,0,3)scanf("%s",mp[i]+1);
	fp(i,0,3){
		R int t=(i<=1?n:m);
		fp(j,1,t)sum[i][j]=sum[i][j-1]+(mp[i][j]=='1');
	}
	if(!sum[0][n]&&!sum[1][n]&&!sum[2][m]&&!sum[3][m])return puts("1"),0;
	calc();
	swap(mp[0],mp[2]),swap(mp[1],mp[3]);
	swap(sum[0],sum[2]),swap(sum[1],sum[3]);
	swap(n,m);
	calc();
	printf("%d\n",res);
	return 0;
}

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

map<string, bool> memo;

bool parse(string s) {
  if(memo.find(s) != memo.end()) return memo[s];
  if(s == "") return true;
  int const size = s.size();
   
  bool ok = 0;
  for(int i=1; i<size; i++) {
    if(s[i] == 'e') {
      string temp;
      string t = "m";
      if(i-1>=0) {
        if(parse(temp = s.substr(1, i-1))) t+=temp;
        else continue;
      }
      t += "e";
      if(size-i-2>=0) {
        if(parse(temp = s.substr(i+1, size-i-2))) t+=temp;
        else continue;
      }
      t +="w";
      ok |= s == t;
    }
  }
  return memo[s] = ok;
}
 
string checker(string s) {
  return parse(s) ? "Cat" : "Rabbit"; 
}
 
int main() {
  string s; cin >> s;
   
  cout << checker(s) << endl;
   
  return 0;
}

Measured memory_bytes: 16120
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true)cerr
void print(){cout<<endl;}
template<typename T,typename... Args>
void print(T a, Args... args) {cout<<a<<" ";print(args...);}
lli llipowerp(lli x, lli y, lli p=LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}
template <typename T>
inline void printvec(vector<T> inp){
    for(auto it:inp) cout<<it<<" ";
    cout << endl;
}
//---------------------------------------------------------------------------------
struct con{
    int a,b,c,d;

};
bool cmp(const con &x, const con &y){
    if(x.a==y.a) return x.d<=y.d;
    return x.a<=y.a;
}
int n,m,q;
vector<vector<int>> pos((int)1e6);
int curr=0;
void fill(int num,int rem,vector<int> curvec){
    //print("calling ",num,rem);
    //printvec(curvec);
    if(num==m){
        curvec.pb(rem);
        pos[curr]=curvec;
        curr++;
        return ;
    }
    fori(rem+1){
        
        vector<int> newvec=curvec;
        newvec.pb(i);
        fill(num+1,rem-i,newvec);
        
    }
}

int main()
{
    int w,x,y,z;
    cin>>n>>m>>q;
    
    
    vector<con> all;


    fori(q){
        cin>>w>>x>>y>>z;
        all.pb({w,x,y,z});
    }
    
    vector<int> temp={0};
    fill(1,n,temp);
    //printvec(pos[0]);
    lli ans=0;
    fori(pos.size()){
        //printvec(pos[i]);
        vector<int> check;
        if(pos[i].size()==0) break;
        for(int j=1;j<=m;j++){
            for(int k=0;k<pos[i][j];k++){
                check.pb(j);
            }

        }
        
        lli tans=0;
        forj(q){
            if(check[all[j].b-1]==check[all[j].a-1]+all[j].c) tans+=all[j].d;
        }
        ans=max(ans,tans);
    }
    cout<<ans<<endl;


}


Measured memory_bytes: 32484
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<string>
#include<assert.h>
#include<sstream>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define setIO(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
typedef long long ll;
typedef pair<int, int> pii;
const ll LINF = 1e18 + 7;
const int N = 5e5 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
//-------------head-------------
int n, p[N], f[N];
char w[N];
void kmp(int n, char s[]) {
	p[0] = -1;
	for (int i = 1, j = -1; i < n; ++i) {
		while (j >= 0 && s[j + 1] != s[i])
			j = p[j];
		j += s[j + 1] == s[i];
		p[i] = j;
	}
}
int main() {
	scanf(" %s", w);
	n = strlen(w);
	kmp(n, w);
	int L = n - 1 - p[n - 1];
	if (L == 1) {
		printf("%d\n1\n", n);
	} else if (L == n || n % L != 0) {
		printf("1\n1\n");
	} else {
		rep(i, 0, n - 1)
			f[i] = (p[i] == -1 || (i + 1) % (i - p[i]) != 0);
		reverse(w, w + n);
		kmp(n, w);
		int ans = 0;
		rep(i, 0, n)
			if ((p[i] == -1 || (i + 1) % (i - p[i]) != 0)
					&& (i == n - 1 || f[n - 2 - i]))
				++ans;
		printf("2\n%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 4608
#include <stdio.h>
 
int main(void){
  int a, b, k, i;
  scanf("%d %d %d", &a, &b, &k);
  if(b-a < 2*k) for(i=a;i<=b;i++) printf("%d\n", i);
  else{
  for(i=0;i<k;i++) printf("%d\n", a+i);
  for(i=k;i>0;i--) printf("%d\n", b-i+1);
  }
  return 0;
}

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

#define ll long long 

ll MOD = 1000000007;

ll Power(ll a, ll n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  return ((a *Power(a, n-1)) % MOD);
}

int main() {
  int N;
  cin >> N;
  
  map<int, int> Map;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    
    Map[x]++;
  }
  
  if (N % 2) {
    for (auto x : Map) {
      if (x.first == 0) {
        if (x.second != 1) {
          cout << 0 << endl;
          return 0;
        }
      } else if (x.first <= N-1 && x.first % 2 == 0) {
        if (x.second != 2) {
          cout << 0 << endl;
          return 0;
        }
      } else {
          cout << 0 << endl;
          return 0;
      }
    }
    cout << Power(2, N/2) << endl;
  } else {
    for (auto x : Map) {
      if (x.first <= N-1 && x.first % 2 == 1) {
        if (x.second != 2) {
          cout << 0 << endl;
          return 0;
        }
      } else {
          cout << 0 << endl;
          return 0;
      }
    }
    cout << Power(2, N/2) << endl;
    
  }

  
}

Measured memory_bytes: 6728
/*
 *  AUTHOR : MANAV PATEl
*/
#include<bits/stdc++.h>
#include<functional>
//#include<boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

namespace fastio {

	template <class T> istream &operator>>(istream &os, vector<T> & vec) {
		for (auto &u : vec)os >> u;
		return os;
	}
	template <class T> ostream &operator<<(ostream &os, const vector<T> & vec) {
		for (auto &u : vec)os << u << " ";
		return os;
	}
	template<class T1, class T2> inline istream& operator>>(istream& os, pair<T1, T2>& p) {
		return os >> p.first >> p.second;
	}
	template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
		return os << p.first << " " << p.second;
	}
	template <class T> ostream &operator<<(ostream &os, set<T> & con) {
		for (auto &u : con) os << u << " ";
		return os;
	}
	void re() {}
	template <typename T, typename... args> void re(T& x, args&... tail) {
		cin >> x;
		re(tail...);
	}
	void pr() {}
	template <typename T> void pr(const T& x) {
		cout << x;
	}
	template <typename T, typename... args> void pr(const T& x, const args&... tail) {
		cout << x << " ";
		pr(tail...);
	}
	template <typename... args> void prln(const args&... tail) {
		pr(tail...);
		cout << "\n";
	}
}
using namespace fastio;

typedef long long int ll;
typedef long double ld;

const ll mod = 1e9+7;
const ll mod1 = 998244353;

#define fill(a)  memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back

int main()
{
	cin.sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	cin.tie(0);
	int a, b, c;
	re(a,b);
	cout<<6-(a+b)<<"\n";
}


Measured memory_bytes: 256
import sys
n = int(input()) 
l = list(map(int, input().split()))
def is_even(num):
    if num % 2 == 0:
        return True
    else:
        return False
for n in l:
  if is_even(n):
    if n % 3 == 0 or n % 5 == 0:
      pass
    else:
      print("DENIED")
      sys.exit()
print("APPROVED")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <typeinfo>
#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()
{
    ll n, sub = 0;
    string s;

    cin >> n;
    cin >> s;
    vector<int> r, b, g;
    rep(i, n)
    {
        if (s[i] == 'R')
        {
            r.push_back(i);
            rep(j, b.size())
            {
                if ((i - b[j]) % 2 == 0 && s[(i + b[j]) / 2] == 'G')
                {
                    sub++;
                }
            }
            rep(j, g.size())
            {
                if ((i - g[j]) % 2 == 0 && s[(i + g[j]) / 2] == 'B')
                {
                    sub++;
                }
            }
        }
        if (s[i] == 'B')
        {
            b.push_back(i);
            rep(j, r.size())
            {
                if ((i - r[j]) % 2 == 0 && s[(i + r[j]) / 2] == 'G')
                {
                    sub++;
                }
            }
            rep(j, g.size())
            {
                if ((i - g[j]) % 2 == 0 && s[(i + g[j]) / 2] == 'R')
                {
                    sub++;
                }
            }
        }
        if (s[i] == 'G')
        {
            g.push_back(i);
            rep(j, r.size())
            {
                if ((i - r[j]) % 2 == 0 && s[(i + r[j]) / 2] == 'B')
                {
                    sub++;
                }
            }
            rep(j, b.size())
            {
                if ((i - b[j]) % 2 == 0 && s[(i + b[j]) / 2] == 'R')
                {
                    sub++;
                }
            }
        }
    }

    cout << (r.size() * b.size() * g.size() - sub) << endl;
}

Measured memory_bytes: 3672
use proconio::input;

const A: usize = 1000_000;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    }

    let mut ma = 0;
    let mut ac = vec![0; A + 1];
    for &a in &a {
        ac[a] += 1;
        ma = ma.max(a);
    }

    let mut pc = true;
    for i in 2..=ma {
        let mut c = 0;
        for j in (i..=ma).step_by(i) {
            c += ac[j];
        }
        if c > 1 {
            pc = false;
            break;
        }
    }

    println!("{} coprime", if pc {
        "pairwise"
    } else {
        let mut v = a[0];
        for i in 1..n {
            v = num_integer::gcd(a[i], v);
        }
        if v == 1 {
            "setwise"
        } else {
            "not"
        }
    });
}


Measured memory_bytes: 20468
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;
const i64 MOD = 1e9 + 7;

int main()
{
  i64 n;
  string s, t;
  cin >> n >> s >> t;
  i64 dp[26] = {};
  dp[s[0] - 'a'] = 1;
  for (i64 i = 1; i < n - 1; i++)
    (dp[s[i] - 'a'] += dp[t[i] - 'a']) %= MOD;
  cout << dp[t[n - 1] - 'a'] % MOD << endl;
  return 0;
}



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

using namespace std;

struct Edge { int src,dst,weight; };

struct Data {
  int cur, weight;
  bool operator < ( const Data &data ) const {
    if( weight != data.weight) return weight > data.weight;
    return cur > data.cur;
  }
};

const int MAX_V = 10010;
int V,E;
bool used[MAX_V];
vector<Edge> G[MAX_V];

int prim(){
  for(int i=0;i<V;i++) used[i] = false;
  priority_queue<Data> Q;
  Q.push((Data){0,0});
  int ret = 0;
  while( !Q.empty() ){
    Data data = Q.top(); Q.pop();
    if( used[data.cur] ) continue;
    used[data.cur] = true;
    ret += data.weight;
    for(int i=0;i<G[data.cur].size();i++){
      int next = G[data.cur][i].dst;
      if( !used[next] ) Q.push((Data){next,G[data.cur][i].weight});
    }
  }
  return ret;
}

int main(){
  cin >> V >> E; // the number of nodes, the number of edges
  for(int i=0;i<E;i++) {
    int src,dst,weight;
    cin >> src >> dst >> weight; // undirected edge 
    G[src].push_back((Edge){src,dst,weight});
    G[dst].push_back((Edge){dst,src,weight});
  }

  // sum of weights of edges of the Minimum Spanning Tree
  printf("%d\n",prim());
  return 0;
}

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

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

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [a, b] <- getIntList
  if b == 1 then
    print 0
  else
    if b <= a then
      print 1
    else do
      let d = (b - a) `div` (a - 1)
      let m = (b - a) `mod` (a - 1)
      if m == 0 then
        print $ d + 1
      else
        print $ d + 2

Measured memory_bytes: 380
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S, T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>N;
    vec a(N);
    rep(i,N) cin>>a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    ll last = a[0], count = 1;
    S = "Possible";
    reps(i,1,N){
        if(count < 2 && last != a[i]) S = "Impossible";
        if(abs(last - a[i]) > 1) S = "Impossible";
        if(last != a[i]){
            last = a[i];
            count = 1;
        }else{
            ++count;
        }
    }
    if(a[0]%2){
        if(last != (a[0]+1)/2 || count != 2) S = "Impossible";
    }else{
        if(last != a[0]/2 || count != 1) S = "Impossible";
    }
    cout<<S<<endl;
}

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

int main (){
  int n;
  cin>>n;
  ll sum = 0;
  for (int i = 1;i<=n;i++){
    if (i%3!=0 && i%5!=0){
      sum+=i;
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(1000000)
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]

Nkai=1
for i in range(1,N+1):
  Nkai*=i

seen=[]
dist=[]
d=0
def dfs(p):
  global d
  seen.append(p)
  if len(seen)==N:
    dist.append(d)
  else:
    for i in range(N):
      if i not in seen:
        d+=((xy[i][0]-xy[p][0])**2+(xy[i][1]-xy[p][1])**2)**0.5
        dfs(i)
        d-=((xy[i][0]-xy[p][0])**2+(xy[i][1]-xy[p][1])**2)**0.5
  seen.remove(p)
  
for j in range(N):
  dfs(j)
  
print(sum(dist)/Nkai)

Measured memory_bytes: 4568
import itertools
sosuu = [3,5,7,11,13]
n=(int)(input())
count = 0
for i in itertools.combinations(sosuu, 3):
  if i[0] * i[1] * i[2] <= n:
    #print(i)
    count += 1
add = 2 if n >= 189 else (1 if n >= 135 else 0)
print(count + add)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>

using namespace std;

int main(void){
    long long a, b, c;
    cin >> a >> b >> c;
    if( a<=c && c<=b){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
     }

    return 0;
}

Measured memory_bytes: 256
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]

is_reversed = False
prefix = ""
suffix = ""

for query in Query:
    if query == "1":
        is_reversed = not is_reversed
    else:
        _, f, c = query.split()
        if is_reversed ^ (f == "1"):
            prefix += c
        else:
            suffix += c

if is_reversed:
    print(suffix[::-1] + S[::-1] + prefix)
else:
    print(prefix[::-1] + S + suffix)


Measured memory_bytes: 16888
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextLong() - (long)(i + 1);
    }
    Arrays.sort(a);
    long m = a[n / 2];
    long ans = 0;
    for(int i = 0; i < n; i++) {
      ans += Math.abs(a[i] - m);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 83100
#include <stdio.h>

int main(void) {
	int N,Q;
	int i;
	char names[50][32]={"kogakubu10gokan"};
	char* answer=names[0];
	scanf("%d%d",&N,&Q);
	for(i=1;i<=N;i++) {
		int year;
		scanf("%d%s",&year,names[i]);
		if(year<=Q)answer=names[i];
	}
	puts(answer);
	return 0;
}

Measured memory_bytes: 580
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define int long long
using namespace std;
int n,mod;
const int maxn=3086;
int C[maxn][maxn];
int dp[maxn][maxn];
int F[maxn];
int qpow(int a,int b,int p)
{
	int res=1,base=a%p;
	while(b) 
	{
		if(b&1) res=res*base%p;
		b>>=1,base=base*base%p;
	}
	return res;
}
signed main()
{
	scanf("%lld%lld",&n,&mod);
	C[0][0]=1;
	for(int i=1;i<maxn;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	dp[0][0]=1;
	for(int i=1;i<maxn;++i)
	{
		dp[i][0]=1;
		for(int j=1;j<=i;++j)
			dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*(j+1))%mod;
	}
	int ans=0;
    for (int i=0;i<=n;i++)
    {
        int k=C[n][i];
        if (i&1) k=(mod-k)%mod;
        int x=qpow(2,n-i,mod-1);
        x=qpow(2,x,mod);
        int kind=qpow(2,n-i,mod);
        int cnt=0,y=1;
        for (int j=0;j<=i;j++)
        {
            cnt=(cnt+(dp[i][j]*y%mod))%mod;
            y=kind*y%mod;
        } 
        ans=(ans+(k*cnt%mod*x%mod))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 100220
#include <stdio.h>

int main(void)
{
    int n,a,max,min,i;
    long int sum=0;
    
    scanf("%d",&n);
    
    for(i=0;i<n;i++){
        scanf("%d",&a);
        if(i==0)min=max=a;
        if(min>=a)min=a;
        if(max<=a)max=a;
        sum+=a;
    }
    printf("%d %d %ld\n",min,max,sum);
    return 0;
}


Measured memory_bytes: 2112
#include<stdio.h>
#include<ctype.h>

int main(void)
{
    int ans[4]={};
    int coef=0,k=0,c=0,formula=0;
    int i,j;

    scanf("%d%*c",&k);
    for(i=0;i<k;i++)
    {
        coef=1;
        formula=0;
        int scale[2][4]={};
        while(1)
        {
            scanf("%c",&c);
            //printf("%c ",c);
            if(c==10)
            {
                break;
            }
            if(isdigit(c))
            {
                coef=c-'0';
        //        printf("coef=%d,",coef);
            }
            else if(isalpha(c))
            {
                switch(c)
                {
                    case 'm':
                    scale[formula][3]=coef;
                    break;
                    case 'c':
                    scale[formula][2]=coef;
                    break;
                    case 'x':
                    scale[formula][1]=coef;
                    break;
                    case 'i':
                    scale[formula][0]=coef;
                    break;
                    default:
                    break;
                }
                coef=1;
            }
            else
            {
                formula=1;
            }
        }

        for(j=0;j<4;j++)
        {
            int x=scale[0][j]+scale[1][j]+ans[j];
            ans[j]=x%10;
            ans[j+1]+=x/10;
        }

        for(j=3;j>=0;j--)
        {
            if(ans[j]!=0)
            {
                if(ans[j]==1)
                {
                    switch(j)
                    {
                        case 0:
                        printf("i");
                        break;
                        case 1:
                        printf("x");
                        break;
                        case 2:
                        printf("c");
                        break;
                        case 3:
                        printf("m");
                        break;
                        default:
                        break;
                    }
                }
                else
                {
                    switch(j)
                    {
                        case 0:
                        printf("%di",ans[j]);
                        break;
                        case 1:
                        printf("%dx",ans[j]);
                        break;
                        case 2:
                        printf("%dc",ans[j]);
                        break;
                        case 3:
                        printf("%dm",ans[j]);
                        break;
                        default:
                        break;
                    }
                }
            }
        }
        printf("\n");
        for(j=0;j<4;j++)
        {
            ans[j]=0;
        }
    }
    return 0;
}

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

int main () {
	int n, count = 0, a[220];
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	
	bool odd_flag = false;
	while (!odd_flag) {
		for (int i = 0; i < n; i++) {
			if (a[i] % 2 == 1) {
				odd_flag = true;
				break;
			}
			else {
				a[i] /= 2;
			}
		}
		if (!odd_flag) count++;
	}
	
	
	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin>>k;
    int x[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    cout<<x[k-1]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define cle(n) memset(n,0,sizeof(n))
typedef long long ll;
using namespace std;
const int maxn =100100;

ll n,m;
ll k;
ll a[maxn];

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

int max_common_divisor(ll several[], ll n)
{
    ll a=several[0];
    ll b=several[1];
    ll c=gcd(a,b);
    ll i;
    for (i=2; i<n; i++)
    {
        c=gcd(c,several[i]);
    }
    return c;
}

int main()
{
  cin>>n>>k;
  for(int i=0;i<n;i++)
    cin>>a[i];
  int flag=0;

  sort(a,a+n);
ll ans=max_common_divisor(a,n);

if(ans==1)
{
    if(k<=a[n-1])
        flag=1;

}
else
{
    if(k<=a[n-1])
    {
        if(k%ans==0)
            flag=1;
    }
}


  if(flag==0)
    cout<<"IMPOSSIBLE"<<endl;
  else cout<<"POSSIBLE"<<endl;
    return 0;
}


Measured memory_bytes: 1024
from itertools import accumulate
class Imos:
    def __init__(self, n):
        self.A = [0]*(n+1)
        self.n = n

    def __call__(self):
        
        dist = list(accumulate(self.A))[:self.n]
        self.A = [0] * (self.n+1)
        return dist

    def query(self, l, r):
        self.A[l] += 1
        self.A[r] -= 1

n, k, *A = map(int, open(0).read().split())
imos = Imos(n)
for _ in range(min(100, k)):
    for i in range(n):
        imos.query(max(0, i-A[i]), min(i+A[i]+1, n))
    A = imos()
print(*A)

Measured memory_bytes: 238580
def selection_sort(a, n)
  count = 0

  0.upto(n - 1) do |i|
    min_j = i

    i.upto(n - 1) do |j|
      min_j = j if a[j] < a[min_j]
    end

    if i != min_j
      a[i], a[min_j] = a[min_j], a[i]
      count += 1
    end
  end

  puts a.join(' ')
  puts count
end

N = gets.to_i
A = gets.split.map(&:to_i)

selection_sort(A, N)

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

using namespace std;

char x,y;

int main(){
	cin>>x>>y;
	if(x<y){
		cout<<"<"<<endl;
	}
	else if(x==y){
		cout<<"="<<endl;
	}
	else{
		cout<<">"<<endl;
	}
	return 0;
}

Measured memory_bytes: 764
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;

int maxV[40005];
int currV[40005];
void solve() {
  int n;
  cin >> n;
  int maxT = 0;
  for(int a = 0; a <= 40000; a++) maxV[a] = 1e9;
  {
    vector<int> tt, vv;
    tt.resize(n);
    vv.resize(n);
    for(int i = 0; i < n; i++) cin >> tt[i];
    for(int i = 0; i < n; i++) tt[i] *= 2;
    for(int i = 0; i < n; i++) cin >> vv[i];
    for(int i = 0; i < n; i++) vv[i] *= 2;
    int curr = 0;
    for(int i = 0; i < n; i++) {
      for(int j = 0; j <= tt[i]; j++) maxV[curr+j] = min(maxV[curr+j], vv[i]);
      curr += tt[i];
    }
    maxT = curr;
  }
  maxV[maxT] = 1e9;
  while(true) {
    bool upd = false;
    for(int i = 1; i < maxT; i++) {
      if(currV[i] == maxV[i]) continue;
      if(abs(currV[i] + 1 - currV[i-1]) > 1) continue;
      if(abs(currV[i] + 1 - currV[i+1]) > 1) continue;
      currV[i]++;
      upd = true;
    }
    if(!upd) break;
  }
  double ret = 0;
  for(int i = 0; i < maxT; i++) {
    ret += (currV[i] + currV[i+1]);
  }
  cout << fixed << setprecision(10) << ret/8.0 << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
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 dp[110][110];
int main(){
    int h,w;cin >> h >> w;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    rep(i,110){
        rep(j,110){
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    if(s[0][0]=='#') dp[0][0]=1;
    rep(i,h){
        rep(j,w){
            if(i+1<h) chmin(dp[i+1][j],dp[i][j]+((s[i+1][j]=='#')&&(s[i][j]=='.')));
            if(j+1<w) chmin(dp[i][j+1],dp[i][j]+((s[i][j+1]=='#')&&(s[i][j]=='.')));
            
        }
    }
    cout << dp[h-1][w-1] << endl;
    return 0;
}

Measured memory_bytes: 256