akhauriyash/Code-Regression huggingface dataset:
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#ifdef PERVEEVM_LOCAL
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl
#else
    #define debug(x) 238;
#endif

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)
#define NAME "File"

using ll = long long;
using ld = long double;

#ifdef PERVEEVM_LOCAL
    std::mt19937 rnd(238);
#else
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const double PI = atan2(0.0, -1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = (ll)2e18;
const int N = 1100;
const int MOD = (int)1e9 + 7;

int add(int a, int b, int mod = MOD) {
    if (a + b >= mod) {
        return a + b - mod;
    }
    return a + b;
}

int sub(int a, int b, int mod = MOD) {
    if (a - b < 0) {
        return a - b + mod;
    }
    return a - b;
}

int mul(int a, int b, int mod = MOD) {
    return (int)(1ll * a * b % mod);
}

int binpow(int a, int n, int mod = MOD) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        return binpow(mul(a, a, mod), n / 2, mod);
    } else {
        return mul(binpow(a, n - 1, mod), a, mod);
    }
}

int rev(int a, int mod = MOD) {
    return binpow(a, mod - 2, mod);
}

char a[N][N];
int dp[N][N];

void run() {
    int n, m;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; ++i) {
        scanf("\n%s", a[i]);
    }

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == '#') {
                continue;
            }

            if (i != 0) {
                dp[i][j] = add(dp[i][j], dp[i - 1][j]);
            }
            if (j != 0) {
                dp[i][j] = add(dp[i][j], dp[i][j - 1]);
            }
        }
    }

    printf("%d\n", dp[n - 1][m - 1]);
}

int main(void) {
    // freopen(NAME".in", "r", stdin);
    // freopen(NAME".out", "w", stdout);

    auto start = std::chrono::high_resolution_clock::now();
    run();
    auto end = std::chrono::high_resolution_clock::now();

    #ifdef PERVEEVM_LOCAL
        std::cerr << "Execution time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms" << std::endl;
    #endif

    return 0;
}


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

#define vi vector<int>
#define pb push_back

int main(){
        string s;
        cin >> s;
        int over = 0;
        rep(i,s.length()){
                if(s[i] == 'g') over++;
                else over--;
        }
        // 小数点以下は切り捨て
        cout << over/2 << endl;
        return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<lint,lint> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const lint INF=1e18;
int n,m;
vector<pi> g[100005];

pi ar[100005];
bool vis[100005];

lint state=-1;
bool fail;
void dfs(int v,int p,int sign,lint off){
  ar[v]={sign,off};
  vis[v]=1;
  dump(v);
  for(auto e:g[v]){
    if(e.fr==p) continue;
    lint nsign=-sign;
    lint noff=(e.sc-off);
    if(!vis[e.fr]) dfs(e.fr,v,nsign,noff);
    else{
      if(nsign==ar[e.fr].fr){
        if(noff!=ar[e.fr].sc) fail=true;
      }else{
        lint tmp=noff-ar[e.fr].sc;
        if(nsign==1) tmp*=-1;
        dump(e.fr);
        dump(tmp);
        if(tmp%2 || tmp<0 || (state!=-1 && state!=tmp/2)) fail=true;
        else state=tmp/2;
      }
    }
  }
}
int main(){
  cin>>n>>m;
  REP(i,m){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);--a;--b;
    c-=2;
    g[a].pb({b,c});
    g[b].pb({a,c});
  }

  dfs(0,-1,1,0);

  dump(state);
  debug(ar,ar+n);
  if(fail) {
    puts("0");
    return 0;
  }
  lint lb=0,ub=INF;
  REP(i,n){
    if(ar[i].fr==1) chmax(lb,-ar[i].sc);
    else chmin(ub,ar[i].sc);
  }
  lint res;
  if(state==-1) res=max(0ll,ub-lb+1);
  else{
    if(lb<=state && state<=ub) res=1;
    else res=0;
  }
  cout<<res<<endl;
  return 0;
}





Measured memory_bytes: 17280
#include<bits/stdc++.h>
using namespace std;
 
#define cinsc ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(0);
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOR(i,k,n)  for(int64 i=k;i<(int64)n;i++)
#define FORr(i,k,n)  for(int64 i=(int64)k;i>=n;i--)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define FOREACHr(it, l) for (auto it = l.rbegin(); it != l.rend(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
#define SQ(x) ((x)*(x))
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//ONLINE_JUDGE   LOCAL
 
int64 powr(int64 x,int64 y,int64 p)  
{  
    int res = 1;    
    x = x % p; 
    if (x == 0) return 0;
    while (y > 0){   
        if (y & 1)  
            res = (res*x) % p;   
        y = y>>1; 
        x = (x*x) % p;  
    }  
    return res;  
} 
 
void  in_o(){
#ifndef LOCAL
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif
	cinsc;
}


int64 a[51],b[51],c[51],d[51];

int64 dist(int x,int y){
	return abs(a[x]-c[y])+abs(b[x]-d[y]);
}

int main(){
	//in_o();
	int64 n,m;
	cin>>n>>m;
	FOR(i,0,n){
		cin>>a[i]>>b[i];
	}
	FOR(i,0,m){
		cin>>c[i]>>d[i];
	}
	FOR(i,0,n){
		int z=-1;
		FOR(j,0,m){
			if(z<0 || dist(i,j)<dist(i,z)) z=j;
		}
		cout<<z+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	
	public static final Scanner sc = new Scanner(System.in);
	
	public static int fun(String s) {
		s = s.substring(1, s.length());
		return Integer.valueOf(s);
	}
	
	public static void show(String[] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]);
			System.out.print(i==a.length-1 ? '\n' : ' ');
		}
	}
	
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		String[] card = new String[n];
		String[] card2 = new String[n];
		for(int i=0;i<n;i++) {
			card[i] = sc.next();
			card2[i] = card[i];
		}
		
		//冒泡排序
		for(int i=0;i<n;i++) {
			for(int j=n-1; j>i; j--) {
				if(fun(card[j]) < fun(card[j-1]) ) {
					String t = card[j];
					card[j] = card[j-1];
					card[j-1] = t;
				}
			}
		}
		
		//选择排序
		for(int i=0;i<n;i++) {
			int mini = i;
			for(int j=i;j<n;j++) {
				if(fun(card2[j]) <fun(card2[mini]) ) {
					mini = j;
				}
			}
			if(mini != i) {
				String t = card2[mini];
				card2[mini] = card2[i];
				card2[i] = t;
			}
		}
		
		show(card);
		System.out.println("Stable");
		show(card2);
		boolean f = true;
		for(int i=0;i<n && f;i++) {
			if(card[i].equals(card2[i]) == false) {
				f = false;
			}
		}
		if(f) {
			System.out.println("Stable");
		}else {
			System.out.println("Not stable");
		}
		
		
	}

}



Measured memory_bytes: 26544
#include <bits/stdc++.h>
using namespace std;
int main() {
string N;
cin >> N;
if (N.at(0) == N.at(1) && N.at(1) == N.at(2) || N.at(1) == N.at(2) && N.at(2) == N.at(3)) {
  cout << "Yes" << endl;
} else {
  cout << "No" << endl;
}



return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

signed main(){
    int k,t;
    cin >> k >> t;
    int a, mx = 0;
    REP(i,t){
        cin >> a;
        mx = max(mx, a);
    }
    cout << max(0, mx - (k - mx) - 1) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        int time = 0;
        long biscuits = 1;
        int money = 0;

        if (a + 1 >= b) {
            System.out.println(k + 1);
        } else {
            while (time < k) {
                if (money == 1) {
                    biscuits += b;
                    time++;
                    money--;
                } else if (biscuits < a || k - time == 1) {
                    biscuits++;
                    time++;
                } else {
                    biscuits -= a;
                    money++;
                    time++;
                }

            }
            System.out.println(biscuits);
        }
    }
}




Measured memory_bytes: 24148
#include <cmath>
#include <iostream>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <vector>

/**
 * Calcurate Comb(n, k) in mod p.
 * This creates factorial/inverse cache table.
 * see https://drken1215.hatenablog.com/entry/2018/06/08/210000 in detail.
 */
class ModComb {
public:
  /**
   * \param p prime number
   * \param k max number for table
   */
  ModComb(uint64_t p, uint64_t k);

  uint64_t factorial(uint64_t n) const;
  uint64_t inverse(uint64_t n) const;
  uint64_t factorial_inverse(uint64_t n) const;

  uint64_t combination(uint64_t n, uint64_t k) const;

private:
  const uint64_t p_, k_;
  // table for n!
  std::vector<uint64_t> factorial_;
  // table for n^(-1)
  std::vector<uint64_t> inverse_;
  // table for (n!)^(-1)
  std::vector<uint64_t> factorial_inverse_;
};

ModComb::ModComb(uint64_t p, uint64_t k)
    : p_(p), k_(k)
{
  if(p < k) {
    throw std::runtime_error("p < k (must k <= p");
  }

  factorial_.resize(k_ + 1);
  inverse_.resize(k_ + 1);
  factorial_inverse_.resize(k_ + 1);

  factorial_[0] = factorial_[1] = 1;
  inverse_[0] = inverse_[1] = 1;
  factorial_inverse_[0] = factorial_inverse_[1] = 1;
  for(uint64_t i=2; i<=k_; i++) {
    factorial_[i] = (i * factorial_[i-1]) % p_;
    int64_t a = - (p_/i) * inverse_[p_ % i];
    while(a<0) {
      a += p_;
    }
    inverse_[i] = a % p_;
    factorial_inverse_[i] = (inverse_[i] * factorial_inverse_[i-1]) % p_;
  }
}

uint64_t ModComb::factorial(uint64_t n) const
{
  if(k_ < n) {
    throw std::runtime_error("too large n (must n <= k)");
  }
  return factorial_[n];
}

uint64_t ModComb::inverse(uint64_t n) const
{
  if(k_ < n) {
    throw std::runtime_error("too large n (must n <= k)");
  }
  return inverse_[n];
}

uint64_t ModComb::factorial_inverse(uint64_t n) const
{
  if(k_ < n) {
    throw std::runtime_error("too large n (must n <= k)");
  }
  return factorial_inverse_[n];
}

uint64_t ModComb::combination(uint64_t n, uint64_t k) const
{
  if(n < k) {
    throw std::runtime_error("error: n < k (must k < n)");
  }
  if(k_ < n) {
    throw std::runtime_error("too large n (must n < p_)");
  }

  return (((factorial_[n] * factorial_inverse_[n-k]) % p_) * factorial_inverse_[k]) % p_;
}

int main()
{
  const uint64_t mod = std::pow(10, 9) + 7;
  ModComb mc(mod, 2 * std::pow(10, 5));
  uint64_t N, M, K;
  std::cin >> N >> M >> K;

  uint64_t ret = 0;
  for(uint64_t i=0; i<N; i++) {
    for(uint64_t j=0; j<M; j++) {
      uint64_t tmp = ((i + j) * (N-i) * (M-j)) % mod;
      if(i * j != 0) {
        tmp *= 2;
      }
      // std::cout << "i: " << i << " j: " << j << " tmp: " << tmp << std::endl;
      ret += tmp;
      ret %= mod;
    }
  }

  ret *= mc.combination(M*N - 2, K - 2);
  ret %= mod;

  std::cout << std::fixed << ret << std::endl;

  return 0;
}


Measured memory_bytes: 7804
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
//#include <bits/stdc++.h>
using namespace std;

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


int main(){
  int D,G,ans = 1e9;
  cin >> D >> G;
  PII Q[D];
  for(int i=0;i<D;i++){
    cin >> Q[i].first;
    cin >> Q[i].second;
  }
  for(int mask = 0; mask < (1 << D); ++mask){
    int Tans = 0, Tsum = 0, rest_max = -1;
    for(int k = 0; k < D; k++){
      if(mask >> k & 1){
        Tsum += Q[k].first * (k + 1) * 100 + Q[k].second;
        Tans += Q[k].first;
      }else{
        rest_max = k;
      }
    }//ボーナスを貰う問題はすべて解いてボーナスを貰う
    //ボーナスをもらわない最大の問題を中途半端にとく
    //cout <<  "1Tans = " << Tans << endl;
    if(Tsum < G){
      for(int j = 1; j < Q[rest_max].first; j++){
        Tsum += 100 * ( rest_max + 1);
        if(Tsum >= G){
          Tans += j;
          break;
        }
      }
    }
    //cout <<  "2Tans = " << Tans << endl;
    if( Tsum >= G)
      ans = min(ans,Tans);
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
deque<int> Era(int n) {
    deque<int> arr(n+1,1);
    deque<int> prime;
    arr[0]=0;
    arr[1]=1;
    for (int i=2;i*i<n;i++) {
        if (arr[i]==1) {
            for (int j=i*i;j<n;j+=i) {
                arr[j]=0;
            }
        }
    }
    for (int k=2;k<=n;k++) {
        if (arr[k]==1) {
            prime.emplace_back(k);
        }
    }
    return prime;
}
int main(void){
    deque<int> poyo=Era(130000*2);
    int a;
    while (cin>>a) {
        if (a==0) {
            break;
        } else {
            int count=0;
            for (int hoge=0;hoge<poyo.size();hoge++) {
                if (a<poyo[hoge]&&a*2>=poyo[hoge]) {
                    count++;
                }
            }
            cout<<count<<endl;
        }
    }
}



Measured memory_bytes: 3660
//g++ -std=c++14 test.cpp -o test.out
//問題URL
//https://atcoder.jp/contests/abc157/tasks/abc157_d
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const int INF_INT = 2147483647;
const LL mod = 1000000007ll;

//引用元
//http://drken1215.hatenablog.com/entry/2019/03/03/224600
//union くっつける
//find  どのグループか調べる
struct UnionFind {
    vector<long> parent;
    
    UnionFind(long n) : parent(n, -1) { }
    void init(long n) { parent.assign(n, -1); }
    
    //xの属している木の根っこを返す
    long root(long x) {
        if (parent[x] < 0) return x;
        else return parent[x] = root(parent[x]);//経路圧縮
    }
    
    long size(long x) {return -parent[root(x)];}//xの属する木の要素数を求める
    bool is_same_tree(long x,long y) {return root(x)==root(y);}
    
    bool merge(long x,long y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (parent[x] > parent[y]) swap(x, y);//xの親の方がyの親より小さくなるようにする
        parent[x] += parent[y];//経路の長さを加算
        parent[y] = x;//yの親をxとする
        return true;
    }
};

int N,M,K;

vector<int> ans;

UnionFind *uf;
vector<int> numof_direct_friends;//iの持つ直接の対人関係の数をnumof_direct_friends[i]とおく
vector<vector<int>> block_list;//iの持つブロックリストをblock_list[i]とする
 
void solve(){
	for(int i=0;i<N;i++){
		ans[i] = (*uf).size(i)-1-numof_direct_friends[i];
		for(int blocked:block_list[i]){
			if((*uf).is_same_tree(i,blocked)) ans[i]--;
		}
	}
}
 
int main(){
	cin >> N >> M >> K;
	ans = vector<int>(N,0);
	UnionFind unionfind(N);
	uf = &unionfind;
	numof_direct_friends = vector<int>(N,0);
	block_list = vector<vector<int>>(N,vector<int>(0));

	for(int i=0;i<M;i++){
		int a,b;
		cin >> a >> b;
		a--;b--;
		numof_direct_friends[a]++;
		numof_direct_friends[b]++;
		(*uf).merge(a,b);
	}
	for(int i=0;i<K;i++){
		int a,b;
		cin >> a >> b;
		a--;b--;
		block_list[a].push_back(b);
		block_list[b].push_back(a);
	}
 
	solve();
 
	for(int i=0;i<ans.size();i++) cout << ans[i] << " ";
	return 0;
}

Measured memory_bytes: 7552
// https://atcoder.jp/contests/abc139/submissions/7298310

#include <iostream>
#include <vector>
#pragma GCC target("avx")

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

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int a[1010][1010] = {};
    int head[1010] = {};
    rep(i,n){
        rep(j,n-1){
            int x;
            cin >> x;
            x--;
            a[i][j] = x;
        }
    }
    register int turn = 0;
    int used[1010] = {};
    for (int &i : used) i = -1;
    while(true){
        register bool ng = true;
        register int empty_cnt = 0;
        rep(i,n){
            if (head[i] == n-1) {
                empty_cnt++;
                continue;
            }
            int j = a[i][head[i]];
            if (used[i] == turn || used[j] == turn) continue;
            if (a[j][head[j]] == i) {
                head[i]++;
                head[j]++;
                used[i] = used[j] = turn;
                ng = false;
            }
        }
        if (empty_cnt == n) break;
        if (ng) {
            cout << -1 << endl;
            return 0;
        }
        turn++;
    }
    cout << turn << endl;

    return 0;
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    string st;
    cin >> st;

    int state = 0;
    rep(i, st.size()) {
        if (state == 0) {
            if (st[i] == 'A') {
                state = 1;
            } else if (st[i] == 'K') {
                state = 2;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 1) {
            if (st[i] == 'K') {
                state = 2;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 2) {
            if (st[i] == 'I') {
                state = 3;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 3) {
            if (st[i] == 'H') {
                state = 4;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 4) {
            if (st[i] == 'A') {
                state = 5;
            } else if (st[i] == 'B') {
                state = 6;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 5) {
            if (st[i] == 'B') {
                state = 6;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 6) {
            if (st[i] == 'A') {
                state = 7;
            } else if (st[i] == 'R') {
                state = 8;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 7) {
            if (st[i] == 'R') {
                state = 8;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else if (state == 8) {
            if (st[i] == 'A') {
                state = 9;
            } else {
                cout << "NO" << endl;
                return 0;
            }
        } else {
            cout << "NO" << endl;
            return 0;
        }
    }
    if (state == 8 || state == 9)
        cout << "YES" << endl;
    else cout << "NO" << endl;




    return 0;
}





Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

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

using ll = long long;

ll N;

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

  std::cout << N*(N-1)/2 << std::endl;

  return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  int m = min(a, b);
  int M = max(a, b);
  for (int i = 0; i < M; i++) {
    cout << m;
  }
  cout << endl;
}


Measured memory_bytes: 256
N,K= map(int, input().split())
S=[int(x) for x in list(str(input()))]

nums=list()
ds={0:1,1:0}
now=1
cnt=0
for i in S:
    if i==now:
        cnt=cnt+1
    else:
        nums.append(cnt)
        now=ds[now]
        cnt=1

if cnt!=0:
    nums.append(cnt)

if len(nums)%2==0:
    nums.append(0)

Add=2*K+1
ans=0

sum=[0]*(len(nums)+1)
for i in range(len(nums)):
    sum[i+1]=sum[i]+nums[i]

for i in range(0,len(nums),2):
    
    left=i
    right=min(i+Add,len(nums))

    tmp=sum[right]-sum[left]
    ans=max(ans,tmp)

print(ans)


Measured memory_bytes: 8432
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,res;
int main()
{
  cin>>n;
  for (int i=0;i<n;i++)
  {
    int x;
    cin>>x;
    while (x%2==0) {x/=2;res++;}
  }
  cout<<res<<endl;
  //system("pause");
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n;cin>>n;
  string s;cin>>s;
  int ans = 0;
  for(int i = 0; n > i+1; i++){
    if(s[i]!=s[i+1]){
      ans++;
      i++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3300
#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ROOT 1,n,1
#define deb  cout<<"----------------------------"<<endl;
using namespace std;
const int maxn=2e5+10;
const int INF=0x3f3f3f3f;
inline void MIN(int &x,int y){if (y<x) x=y;}
struct adjs{int to,nx;}edge[maxn];
int h[maxn],sz;
void init(int n){for (int i=0;i<=n;i++) h[i]=-1;sz=0;}
void addedge(int u,int v){
    edge[sz].to=v;edge[sz].nx=h[u];h[u]=sz++;
}
int tree[maxn<<2];
void build(int l,int r,int rt){
    tree[rt]=INF;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(lson);build(rson);
}
int query(int l,int r,int rt,int pos){
    if (l==r) return tree[rt];
    int mid=(l+r)>>1;
    if (pos<=mid) return min(query(lson,pos),tree[rt]);
    else return min(query(rson,pos),tree[rt]);
}
void update(int l,int r,int rt,int L,int R,int val){
    if (L<=l&&r<=R) {MIN(tree[rt],val);return;}
    int mid=(l+r)>>1;
    if (L<=mid) update(lson,L,R,val);
    if (R>mid) update(rson,L,R,val);
}
void pt(int l,int r,int rt){
    printf("[%d,%d]=%d\n",l,r,tree[rt]);
    if (l==r) return;
    int mid=(l+r)>>1;
    pt(lson);pt(rson);
}
int n,a[maxn],sum[maxn],dp[maxn];
int m,u,v;
int main(){
    #ifdef VGel
    freopen("F.in","r",stdin);
    freopen("F.out","w",stdout);
    #endif // VGel
    while (~scanf("%d",&n)){
        sum[0]=dp[0]=0;
        for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=sum[i-1]+!a[i];
        init(n);
        scanf("%d",&m);
        while (m--){
            scanf("%d%d",&u,&v);
            addedge(v,u);
        }
        build(ROOT);
//        pt(ROOT);deb;

        for (int r=1;r<=n;r++){
            dp[r]=dp[r-1]+a[r];
            for (int i=h[r];~i;i=edge[i].nx){
                int l=edge[i].to;
                int tmp=dp[l-1]+sum[r]-sum[l-1];//xuan
                int tmp2=query(ROOT,l)+sum[r];
//                cout<<"l="<<l<<"  r="<<r<<"  tmp="<<tmp<<"  tmp2="<<tmp2-sum[r]<<endl;
                MIN(tmp,tmp2);
                update(ROOT,l,r,tmp-sum[r]);
                MIN(dp[r],tmp);
//                pt(ROOT);deb;
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}


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

int main(){
    int n,m;
    cin >> n >> m;
    int a[n];
    int sum  = 0;
    for(int i=0;i<n;i++){
        cin >> a[i];
        sum += a[i];
    }
    int count = 0;
    for(int i=0;i<n;i++){
        if(a[i]*4*m>=sum)count++;
    }
    if(count>=m) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            a.add(in.nextInt());
        }
        int average = (int) Math.round(a.stream().mapToDouble(i -> i).average().orElse(0));
        int sum = (int) a.stream().mapToDouble(i -> Math.pow((double) average - i, 2)).sum();
        System.out.println(sum);
    }
}

Measured memory_bytes: 32948
#include <iostream>
#include <string>
#include<algorithm>

using namespace std;

int main(){
    int A,B,K;
    cin >> A >> B >> K;

    for(int i = 0; i < K; i++){
        if( (i%2) == 0){
            if( (A%2) == 1){
                A--;
            }
            B += (A/2);
            A /= 2;
        }else{
            if( (B%2) == 1){
                B--;
            }
            A += (B/2);
            B /= 2;
        }
    }

    cout << A << " " << B << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
const int N=2010;
int vis[N],f[N][N],du[N],a[N];
vector<int>g[N];
int n;
void dfs(int u)
{
    vis[u]=1;
    for(int i=1;i<=n;i++)
    	if(!vis[i]&&f[u][i])
		{
	        du[i]++;
	        g[u].push_back(i);
	        dfs(i);
   	 	}
}
void solve()
{
    priority_queue<int>q;
    for(int i=1;i<=n;i++)
		if(!du[i])q.push(i);
    while(!q.empty())
	{
        int u=q.top();q.pop();
        cout<<a[u]<<" ";
        for(int i=0;i<g[u].size();i++)q.push(g[u][i]);
    }
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    	for(int j=i+1;j<=n;j++)
    		if(__gcd(a[i],a[j])!=1)f[i][j]=f[j][i]=1;
    for(int i=1;i<=n;i++)
		if(!vis[i])dfs(i);
    solve();
}

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

int main(){
    using namespace std;
    long N; cin >> N;
    long ans = N; 
    for (long i = 1; i * i <= N; i++)
    {
        if(N%i==0) ans = min(ans, i + (N/i) -2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
//file_name:ABC70_A.cpp
#include <bits/stdc++.h>
#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)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


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

    if(n%10==(n/100)%10)yn;
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 200005
using namespace std;
int nx[N],n;
LL a[200][26],le[200],l,r;
char ch[N];
void kmp()
{
	int j=0;
	fo(i,2,n/2)
	{
		while(j&&ch[j+1]!=ch[i]) j=nx[j];
		if(ch[j+1]==ch[i]) j++;
		nx[i]=j;
	}
}
LL calc(int c,LL w)
{
	int id=1;
	if(le[id]>=w) 
	{
		int s=0;
		fo(i,1,w)
		{
			if(ch[i]-'a'==c) s++;
		}
		return s;
	}
	while(w>=le[id])
	{
		a[id+1][c]=a[id][c]+a[id-1][c];
		le[id+1]=le[id]+le[id-1];
		id++;
	}
	LL s=a[id-1][c];
	if(w==le[id-1]) return s;
	else return s+calc(c,w-le[id-1]);
}
int main()
{
	scanf("%s",ch+1);
	n=strlen(ch+1);
	kmp();
	cin>>l>>r;
	le[0]=n/2-nx[n/2];
	le[1]=n/2;
	fo(i,1,n/2) 
	{
		a[1][ch[i]-'a']++; 
		if(i<=le[0]) a[0][ch[i]-'a']++;
	}
	fo(i,0,25) printf("%lld ",calc(i,r)-calc(i,l-1));
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
 
#define scd second
#define fst first
#define pb push_back
#define mkp make_pair
#define all(x) x.begin(), x.end()
#define VT(T) vector<T>
 
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vint;
typedef vector<ll> vlong;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vint> vvint;
typedef vector<vlong> vvlong;
typedef list<int> lint;
typedef list<ll> llong;
typedef list<pii> lpii;
typedef list<pll> lpll;
typedef list<lint> llint;
typedef list<llong> lllong;
 
ll const LINF=numeric_limits<long long int>::max();
int const INF=numeric_limits<int>::max();
 
ll gcd(ll a, ll b){
	return b ? gcd(b,a%b) : a;
}
 
ll pow_mod(ll a, ll e, ll m){
	ll res=1;
	while(e){
		if(e&1) res=res*a%m;
		a=a*a%m;
		e>>=1;
	}
	return res;
}
 
ll inv_mod(ll b, ll m){
	b%=m;
	ll x=0, y=1, r, q, a=m;
	while(b){
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		r=x;
		x=y;
		y=r-q*y;
	}
	x+=m;
	return x%m;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int a, b, c;
	cin>>a>>b>>c;
	if(a+b+c>=22) cout<<"bust"<<endl;
	else cout<<"win"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;
 
ll N, A[10];
 
int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> A[i];
 
  ll ans = 1;
  REP(i, 0, N) {
    if(A[i] % 2 == 0) {
      ans *= 2;
    }
  }
  cout << pow(3, N) - ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int W,H,N;
    cin >> W >> H >> N;

    vector<vector<int>> m(H,vector<int>(W));

    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            m.at(i).at(j)=1;
        }
    }

    for(int i=0;i<N;i++){
        int x,y,a;
        cin >> x >> y >> a;

        if(a==1){
            for(int j=0;j<x;j++){
                for(int k=0;k<H;k++){
                    m.at(k).at(j)=0;
                }
            }
        }
        
        else if(a==2){
            for(int j=x;j<W;j++){
                for(int k=0;k<H;k++){
                    m.at(k).at(j)=0;
                }
            }
        }

        else if(a==3){
            for(int j=0;j<y;j++){
                for(int k=0;k<W;k++){
                    m.at(j).at(k)=0;
                }
            }
        }

        else if(a==4){
            for(int j=y;j<H;j++){
                for(int k=0;k<W;k++){
                    m.at(j).at(k)=0;
                }
            }
        }
    }

    int ans=0;
    
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            ans += m.at(i).at(j);
        }
    }
 
    cout << ans << endl;

}

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

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

    vector<pair<int,int>> a;
    rep(i,n) {
        int x;
        cin >> x;
        a.push_back(make_pair(x,i));
    } 
    
    sort(a.rbegin(), a.rend());

    rep(i,n) {
        if (i != a[0].second) cout << a[0].first << endl;
        else cout << a[1].first << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3312
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const int MOD = 1000000007;
/* テンプレートここまで */

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

/* 二項係数 C(n,k) mod p を計算 */
const int MAX = 114514 * 2;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

long long COM(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a , ll b){
  if (b == 0) return 1;

  if (b%2 == 0){
    ll  t = modpow(a, b/2)%MOD;
    return t*t % MOD;
  }else{
    ll t = modpow(a, (b-1)/2)%MOD;
    return a*t %MOD * t % MOD;
  }
}

ll inverse (ll a){
  return modpow(a,MOD-2)%MOD;
}

int main() {
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  A--;
  B--;
  C--;
  D--;

  string S;
  cin >> S;

  if (C < B){
    FOR(i, A, C){
      if(S[i] == '#' && S[i+1] == '#') {
        cout << "No" << endl;
        return 0;
      }  
    }

    FOR(i, B, D){
      if(S[i] == '#' && S[i+1] == '#') {
        cout << "No" << endl;
        return 0;
      }  
    }

    cout << "Yes" << endl;
    return 0;
  }

  if (C < D){
    FOR(i, A, D){
      if(S[i] == '#' && S[i+1] == '#') {
        cout << "No" << endl;
        return 0;
      }  
    }
    cout << "Yes" << endl;
    return 0;
  }
  

  // C > D
  FOR(i, A, C){
    if(S[i] == '#' && S[i+1] == '#') {
      cout << "No" << endl;
      return 0;
    }  
  }

  FOR(i, B, D+1){
    if(S[i-1] == '.' && S[i] == '.' && S[i+1] == '.') {
      break;
    }

    if (i == D){
      cout << "No" << endl;
      return 0;
    }
  }


  cout << "Yes" << endl;
} 

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    string a;
    cin >> a;
    string b;
    cin >> b;
    
    int2(aa, bb);

    string c;
    cin >> c;
    
    if (a == c) {
        aa--;
    } else {
        bb--;
    }

    cout << aa << " " << bb << endl;


    return 0;
}


Measured memory_bytes: 256
import math

a,b,h,m=map(int,input().split())

jikan=math.pi*(h*60+m)/360

hun=math.pi*m/30

kakudo=jikan-hun

cos=math.cos(kakudo)
nijo=a**2+b**2-2*a*b*cos
if(nijo<=0):
    print(0)
else:
    print(nijo**(1/2))

Measured memory_bytes: 9516
import java.util.*;
class Main{
 public static void main (String[] args){
 	Scanner sc = new Scanner(System.in);
 	int a = sc.nextInt();
   	int b = sc.nextInt();
   	
   	if((a*b)%2 == 0){
    	System.out.println("Even");
    } else {
     	System.out.println("Odd"); 
    }
 
 
 }
  
  
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
main()
{
    long n,g,i,j;
    map<long,long> a;
    scanf("%ld",&n);
    for(i=1;i<=n;i++)
    {
        scanf(" %ld",&g);
        a[g]++;
    }
    printf("%ld",a.size()-(a.size()+1)%2);
}


Measured memory_bytes: 6528
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
int main(){
    double a,b,c,degree,S;
    scanf("%lf %lf %lf",&a,&b,&degree);
    S = (0.5)*a*b*sin(M_PI*degree/180);
    c = sqrt(a*a+b*b-2*a*b*cos(M_PI*degree/180));
    printf("%.8lf\n",S);
    printf("%.8lf\n",a+b+c);
    printf("%.8lf\n",2*S/a);
}


Measured memory_bytes: 2928
from collections import Counter


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


N = int(input())

c = Counter(prime_factorize(N))
keys = c.keys()
ans = 0

for key in keys:
    cnt = 0
    while c[key] >= cnt + 1:
        ans += 1
        c[key] -= (cnt + 1)
        cnt += 1

print(ans)


Measured memory_bytes: 9464
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  li[x-1].append(y-1)
  li[y-1].append(x-1)
an=[]
for i in li[0]:
  an+=li[i]
if n-1 in an:
  print('POSSIBLE')
else:print('IMPOSSIBLE')

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

#include <math.h>
#include <stdlib.h>


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

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

// const int INF = 1001001001;
// long long max => LLONG_MAX

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    string s; cin >> s;
    if(s == "SUN") cout << 7 << endl;
    else if (s == "MON") cout << 6 << endl;
    else if (s == "TUE") cout << 5 << endl;
    else if (s == "WED") cout << 4 << endl;
    else if (s == "THU") cout << 3 << endl;
    else if (s == "FRI") cout << 2 << endl;
    else  cout << 1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int Y;
	int i;
}pair;

signed compair(const void *a, const void *b){
	return ((pair *)a)->Y - ((pair *)b)->Y;
}

int main(){
	int N, M, i, j;
	scanf("%d%d", &N, &M);
	int *city_num = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		city_num[i] = 0;
	}
	int *P = (int *)malloc(sizeof(int) * M);
	int *Y = (int *)malloc(sizeof(int) * M);
	for(i = 0; i < M; i++){
		scanf("%d%d", &P[i], &Y[i]);
		P[i]--;
		city_num[P[i]]++;
	}
	pair **citys = (pair **)malloc(sizeof(pair *) * N);
	for(i = 0; i < N; i++){
		citys[i] = (pair *)malloc(sizeof(pair) * city_num[i]);
		city_num[i] = 0;
	}
	for(i = 0; i < M; i++){
		citys[P[i]][city_num[P[i]]].Y = Y[i];
		citys[P[i]][city_num[P[i]]].i = i;
		city_num[P[i]]++;
	}
	for(i = 0; i < N; i++){
		qsort(citys[i], city_num[i], sizeof(pair), compair);
	}
	int *x = (int *)malloc(sizeof(int) * M);
	for(i = 0; i < N; i++){
		for(j = 0; j < city_num[i]; j++){
			x[citys[i][j].i] = j;
		}
	}
	for(i = 0; i < M; i++){
		printf("%06d", P[i] + 1);
		printf("%06d\n", x[i] + 1);
	}
	return 0;
}

Measured memory_bytes: 7712
#include <bits/stdc++.h>
 
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dumpi(x1) fprintf(stderr, "#%s.%d (%s) = (%d)\n", __func__, __LINE__, #x1, x1);
#define dumpii(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%d, %d)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpiii(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%d, %d, %d)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
 
struct S002 {
  int n;
  S002& operator > (long& x) {
    n = x;
    return *this;
  }
  S002& operator >= (long& x) {
    if( scanf("%ld", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (double& x) {
    if( scanf("%lf", &x) <= 0 ) exit(0);
    return *this;
  }
  S002& operator >= (std::string& s) {
    if( not (std::cin >> s) ) exit(0);
    return *this;
  }
  template<typename a>
  S002& operator >= (std::vector<a>& v) {
    v.resize(n);
    for(long i = 0; i < n; ++i) {
      *this >= v[i];
    }
    return *this;
  }
  template<typename a, std::size_t s>
  S002& operator >= (std::array<a, s>& x) {
    for(long i = 0; i < (long)s; ++i) {
      *this >= x[i];
    }
    return *this;
  }
};

struct Solver {
  std::array<std::string, 3> xs;
  Solver() {
    S002 r;
    r >= xs;
  }
  void solve() {
    long ys[3] = {};
    long p = 0;
    loop {
      long t = xs[p][ys[p]];
      if( ys[p] >= (long)xs[p].size() ) break;
      ys[p] += 1;
      p = t - 'a';
    }
    printf("%c\n", (int)p + 'A');
  }
};
 
int main() {
  for(;;) std::unique_ptr<Solver>(new Solver())->solve();
  return 0;
}

Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define REP(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288
long long seg_tree[seg_size*2];
long long seg_find(int now,int n_l,int n_r,int w_l,int w_r){
    if(w_l <= n_l&&n_r <= w_r) return seg_tree[now];
    if(n_r <= w_l||w_r <= n_l) return (1LL << 31LL) - 1LL;
    return min(seg_find(now*2,n_l,(n_l+n_r)/2,w_l,w_r),seg_find(now*2+1,(n_l+n_r)/2,n_r,w_l,w_r));
}
long long seg_set(int now){
    seg_tree[now] = min(seg_tree[now*2],seg_tree[now*2+1]);
    if(now != 1) seg_set(now/2);
    return 0;
}
int main() {
    for(int i = 0;i < seg_size*2;++i){
        seg_tree[i] = (1LL << 31LL) - 1;
    }
    int n,query;
    cin >> n >> query;
    REP(i,query){
        int a,b,c;
        cin >> a >> b >> c;
        if(a == 1){
            cout << seg_find(1,0,seg_size,b,c+1) << endl;
        }else{
            seg_tree[seg_size + b] = c;
            seg_set((seg_size+b)/2);
        }
    }
    return 0;
}


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

const int L = 2e5+10;

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

int root[L], folga[L];

int find(int a){
	if(root[a] == a) return a;
	return root[a] = find(root[a]);
}

bool join(int a, int b){
	a = find(a);
	b = find(b);

	if(folga[a] + folga[b]){
		if(a != b) folga[a] += folga[b];
		folga[a]--;
		root[b] = a;
		return 1;
	}

	return 0;
}

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

	int N, H, W;
	cin >> N >> H >> W;

	for(int i=0; i<H+W; i++){
		folga[i] = 1;
		root[i] = i;
	}

	vector<card> C(N);
	for(int i=0; i<N; i++){
		cin >> C[i].second.first >> C[i].second.second >> C[i].first;
		C[i].second.second += H;
	}
	sort(C.begin(), C.end());

	ll ans = 0;
	for(int i=N-1; i>=0; i--){
		if(join(C[i].second.first, C[i].second.second))
			ans += C[i].first;
	}

	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  ll X,N;
  cin>>X>>N;
  unordered_map<ll,ll> mp;
  for(ll i=0;i<N;i++){
    ll a;
    cin>>a;
    mp[a]++;
  }
  for(ll i=0;i<120;i++){
    if(mp[X-i]==0){cout<<X-i<<endl;return 0;}
    if(mp[X+i]==0){cout<<X+i<<endl;return 0;}
  }
}

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


int dp[100'000+5];      /// dp[i] = min cost to get from 0 to i

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

    int n, k;
    cin>>n>>k;

    vector<int> input(n);
    for(int i = 0; i<n; i++)
        cin>>input[i];


    dp[0] = 0;
    for(int i = 1; i<n; i++){
        dp[i] = 2'000'000'000;
        for(int j = 1; j<=k; j++){
            if(i-j >= 0)
                dp[i] = min(dp[i], dp[i-j] + abs(input[i] - input[i-j]) );
        }
    }

    cout<<dp[n-1]<<endl;

    return 0;
}



Measured memory_bytes: 4040