akhauriyash/Code-Regression huggingface dataset:
// b棟f階のr番目の部屋にv人
// １フロア１０部屋、３階建ての公舎４棟

// Input情報
// 最初の行に情報の数 n が与えられます。
// 続いて n 件の情報が与えられます。各情報には４つの整数 b, f, r, v が空白区切りで１行に与えられます。

// アプローチは以下2つが浮かんだ
// ・1つのでかい2次元配列を用意して4棟分まとめた情報を格納するか
// ・4棟分の配列を用意してそれぞれに情報を格納するか
// 後者のほうがわかりやすいため後者を選択

import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n;	// 情報の数
		String str = null;
		String[] spl = new String[4];

		//入力受け取り用変数を定義
		String b;
		int f, r, v;

		// ループカウンタ変数
		int i, j;

		// 棟の数だけ2次元配列を用意（int）
		int [][] b1 = new int[3][10];
		int [][] b2 = new int[3][10];
		int [][] b3 = new int[3][10];
		int [][] b4 = new int[3][10];

		// 情報の数を取得
		str = scan.nextLine();
		n = Integer.parseInt(str);

		// 情報の数だけ繰り返し
		for(i=0; i<n; i++){
			// 入力受け取り
			str = scan.nextLine();
			spl = str.split(" ");
			b = spl[0];
			f = Integer.parseInt(spl[1]);
			r = Integer.parseInt(spl[2]);
			v = Integer.parseInt(spl[3]);

			switch(b){
				// b="1"のとき
				case "1":
					// 1棟の[f][r]要素にv人足す
					b1[f-1][r-1] = b1[f-1][r-1] + v;
					break;
				// b="2"〜"4"も同様
				case "2":
					b2[f-1][r-1] = b2[f-1][r-1] + v;
					break;
				case "3":
					b3[f-1][r-1] = b3[f-1][r-1] + v;
					break;
				case "4":
					b4[f-1][r-1] = b4[f-1][r-1] + v;
					break;
			}
		}
		// 二重ループで出力
		for(i=0 ;i<3; i++){
			for(j=0; j<10; j++){
				System.out.print(" " + b1[i][j]);
			}
			System.out.println();
		}
		System.out.println("####################");

		for(i=0 ;i<3; i++){
			for(j=0; j<10; j++){
				System.out.print(" " + b2[i][j]);
			}
			System.out.println();
		}
		System.out.println("####################");

		for(i=0 ;i<3; i++){
			for(j=0; j<10; j++){
				System.out.print(" " + b3[i][j]);
			}
			System.out.println();
		}
		System.out.println("####################");

		for(i=0 ;i<3; i++){
			for(j=0; j<10; j++){
				System.out.print(" " + b4[i][j]);
			}
			System.out.println();
		}
	}
}


Measured memory_bytes: 27188
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        long mod = (long)Math.pow(10,9)+7;
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long p = sc.nextLong();
        if(n == 1){
            System.out.println(p);
            return;
        }
        HashMap<Long,Integer> pl = factorization(p);
        long ans = 1;
        for(Map.Entry<Long,Integer> e : pl.entrySet()){
            long k = e.getKey();
            long v = e.getValue();
            if(n <= v){
                ans *= Math.pow(k,v/n);
            }
        }
        System.out.println(ans);
    }
    
    static HashMap<Long,Integer> factorization(long x) {
        HashMap<Long,Integer> ret = new HashMap<Long,Integer>();
        int div2 = 0;
        while (x % 2 == 0) {
            x /= 2;
            div2++;
        }
        if(div2 != 0) ret.put(2L,div2);
        long d = 3;
        while (x/d >= d) {
            int cnt = 0;
            while (x % d == 0) {
                cnt++;
                x /= d;
            }
            if(cnt != 0) ret.put(d,cnt);
            d += 2;
        }
        if(ret.containsKey(x)){
            ret.put(x, ret.get(x)+1);
        }else{
            ret.put(x, 1);
        }
        return ret;
    }
}


Measured memory_bytes: 23636
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())

// code
// ------------------------------------------------
int main() {

  string r,g,b;
  string s;
  cin >> r >> g >> b;

  s = r + g + b;

  int aa = stoi(s);

  if(aa%4) cout << "NO" << endl;
  else cout << "YES" << endl;

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

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

using ll = long long;

using namespace std;

int main() {
    long n;
    cin >> n;
    long r = (long)sqrt(n), ans = n;
    for (long i=1; i<=r; i++) {
        if (n % i != 0) continue;
        ans = min(ans, i - 1 + n / i - 1);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n; scanf("%d", &n); std::vector<int> a(n);
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	int ans = a[0];
	for(int i = 1; i < n; i++) ans = std::__gcd(ans, a[i]);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>

using namespace std;

int main(){
    string str;
    cin >> str;
    str.pop_back();
    while(true){
        if(str.length()%2!=0){
            str.pop_back();
        }
        if(str.substr(0,str.length()/2)==str.substr(str.length()/2,str.length()/2)){
            break;
        }
        str.pop_back();
    }
    cout << (int)str.length() << endl;
    return 0;
}


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,ans=0;
    cin >> n;
    if(n%2 == 0)
    {
        n/=2;
        while(n > 0)ans+=n/5,n/=5;
    }
    cout << ans;
    return 0;
}


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

int main(){
  int m,d; cin>>m>>d;

  int ans=0;
  for(int i=1; i<=m; ++i){
    for(int j=20; j<=d; ++j){
      int d1=j%10, d10=j/10;
      if(d1>=2 && d10>=2 && d1*d10==i)++ans;
    }
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Mid (l+r)/2
#define int ll
const int mod=1e9+7,inf=0x3f3f3f3f,maxn=1e5+5;
int n,m,Q,K;

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int a[maxn];


signed main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i){
        int x=read();
        if(x%2==0&&(x%3!=0&&x%5!=0)){puts("DENIED");return 0;}
    }puts("APPROVED");


    return 0;
}


Measured memory_bytes: 256
using System;

namespace abc145B
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int M;
            if (N % 2 == 1)
            {
                Console.WriteLine("No");
            }
            else if (N % 2 == 0)
            {
                M = N / 2;
                string temp = S.Substring(0, M);
                string tome = S.Substring(M);
                if (temp == tome)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("No");
                }
            }
        }
    }
}


Measured memory_bytes: 13140
N,M = map(int,input().split())
H = list(map(int,input().split()))
alllist = []
notwinner = []
for i in range(M):
    ab = list(map(int,input().split()))
    if H[ab[0]-1] > H[ab[1]-1]:
        notwinner.append(ab[1])
    elif H[ab[0]-1] < H[ab[1]-1]:
        notwinner.append(ab[0])
    else:
        notwinner.append(ab[0])
        notwinner.append(ab[1])
wtou = N - len(set(notwinner))
print(wtou)

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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

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

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

vi g[200005];
int d[200005];

void dfs(int c, int s=0, int p=-1) {
    d[c] = s;
    for (int a : g[c]) {
        if (a == p) continue;
        dfs(a, s^1, c);
    }
}

int main(){
    int n;
    cin >> n;
    rep(i, n-1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0);
    vi e, o;
    rep(i, n) {
        if (d[i]) e.push_back(i);
        else o.push_back(i);
    }
    vector<vi> st(3);
    rep1(i, n) st[i%3].push_back(i);
    if (e.size() > o.size()) swap(e, o);
    vi ans(n);
    if (e.size() <= st[0].size()) {
        for (int a : e) {
            ans[a] = st[0].back();
            st[0].pop_back();
        }
        for (int a : o) {
            rep(i, 3) {
                if (st[i].empty()) continue;
                ans[a] = st[i].back();
                st[i].pop_back();
                break;
            }
        }
    } 
    else {
        for (int a : e) {
            repr(i, 2) {
                if (st[i].empty()) continue;
                ans[a] = st[i].back();
                st[i].pop_back();
                break;
            }
        }
        for (int a : o) {
            repr(i, 3) {
                if (st[i].empty()) continue;
                ans[a] = st[i].back();
                st[i].pop_back();
                break;
            }
        }
    }
    rep(i, n) {
        cout << ans[i];
        printf("%c", i<n-1?' ':'\n');
    }
    return 0;
}


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

#define ll long long int
#define vi vector<int> 
ll prime(int i){

    int j=2;
    for(j=2;j<sqrt(i);j++){
        if(i%j==0)return 0;
        
    }
return 1;    
}




int main() {
 int a,b;
 cin >> a >> b;
 int j;
 for(int i:{1,2,3}){
     if(i!=a&&i!=b){j=i;
      break;}
 }
cout << j;
    
}


Measured memory_bytes: 256
import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

k, n = I()
a = I()
ans = k
mx = 0
for i in range(n):
    mx = max(mx, (a[i] - a[i - 1]) % k)
print(ans - mx)

Measured memory_bytes: 30700
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#define N 505
using namespace std;
typedef long long ll;
int c[505]; //到一个车站的花费时间
int s[505]; //一个车站出发的等待时间
int f[505];  //一个车站每f秒出发一个车
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&c[i],&s[i],&f[i]);
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j=i;j<n;j++){
            if(ans<s[j])
                ans=s[j];
            if(ans%f[j]!=0)
                ans=ans+f[j]-ans%f[j];
            ans+=c[j];
        }
        printf("%d\n",ans);
    }
}


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

#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define eb emplace_back
#define rep(i, a, b) for (long i = (a); i <= (b); ++i)
#define per(i, a, b) for (long i = (a); i >= (b); --i)
#define mmst(v) memset(v, 0, sizeof(v))

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

const long kMax2 = 109;
const long kMax3 = 1009;
const long kMax4 = 10009;
const long kMax5 = 100009;
const long kMax6 = 1000009;
const long kInfI = 0x3F3F3F3F;
const float kInfF = 1e15;
const long long kMod = 1000000007;

const long long kMAX = 1000000000;

using namespace std;
using ll = long long;

inline int readInt() {
  char c = getchar();
  while(!isdigit(c) && c != '-') c = getchar();
  int sigma = 1;
  if (c == '-') {
    sigma = -1;
    c = getchar();
  }
  int x = 0;
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * sigma;
}

template <class T>
void PrintVector(const vector<T> & v) {
  for (const auto & e: v) {
    cout << e << endl;
  }
}

template <class T>
void PrintVector(const vector<T> & v, int n) {
  rep(i, 0, n - 1) {
    cout << v[i] << endl;
  }
}

int main(int argc, char const *argv[]) {
  // long n, m, h, w, x, y;
  double a, b, x;
  // long ans = 0;
  // vector<int> a, b;
  // cin >> n >> m;
  // rep(i, 1, n) {
  //   int a0, b0;
  //   cin >> a0 >> b0;
  //   a.pb(a0);
  //   b.pb(b0);
  // }
  cin >> a >> b >> x;
  // for (const auto & a0: a) {
  //
  // }

  // cout << std::setprecision(10) << atan(2.0 * (b / a - x / a / a / a)) * 180 / 3.14159265359 << endl;
  cout << std::setprecision(12);
  if (x > a * a * b / 2) {
    cout << atan(2.0 * (b / a - x / a / a / a)) * 180 / 3.14159265359 << endl;
  } else {
    cout << atan(a * b * b / x / 2) * 180 / 3.14159265359 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
def attack_survival(n, k, q, aq)
  ans = Array.new(n, 0)
  aq.each { |a| ans[a - 1] += 1 }
  ans.each do |n|
    puts k - q + n > 0 ? 'Yes' : 'No'
  end
end

n, k, q = gets.split.map(&:to_i)
aq = []
q.times{ aq << gets.to_i }

attack_survival(n, k, q, aq)


Measured memory_bytes: 4148
<?php
/*
	AOJ 2015
	title:Square Route
	@kankichi573
*/

while(fscanf(STDIN,"%d %d",$n,$m) && ($n||$m))
  {
    $row=array();
    $col=array();

    for($i=0;$i<$n;$i++)
      fscanf(STDIN,"%d",$h[$i]);
    for($i=0;$i<$m;$i++)
      fscanf(STDIN,"%d",$w[$i]);
    $sum=0;		
    for($i=0;$i<$n;$i++)
      {
	$sum=$h[$i];
	//fprintf(STDOUT,":NUM=%d\n",$sum);
	if(empty($row[$sum]))
	  $row[$sum]=1;
	else
	  $row[$sum]++;	
	for($j=$i+1;$j<$n;$j++)
	  {
	    $sum += $h[$j];
	    //fprintf(STDOUT,"::NUM=%d\n",$sum);
	    if(empty($row[$sum]))
	      $row[$sum]=1;
	    else
	      $row[$sum]++;
	  }
      }
    $sum=0;
    for($i=0;$i<$m;$i++)
      {
	$sum=$w[$i];
	//fprintf(STDOUT,";NUM=%d\n",$sum);
	if(empty($col[$sum]))
	  $col[$sum]=1;
	else
	  $col[$sum]++;	
	for($j=$i+1;$j<$m;$j++)
	  {
	    $sum += $w[$j];
	    //fprintf(STDOUT,":;NUM=%d\n",$sum);
	    if(empty($col[$sum]))
	      $col[$sum]=1;
	    else
	      $col[$sum]++;	
	  }
      }
    
    $result=0;
      foreach($row as $rowkey => $rowval) 
	{
	  //fprintf(STDOUT,"*=%d\n",$rowkey);
	  if(!empty($col[$rowkey]))
	    $result += $rowval * $col[$rowkey];
	}
    fprintf(STDOUT,"%d\n",$result);
    	
  }

return(0);
?>

Measured memory_bytes: 93332
"use strict";

const main = (input) => {
    const spi = input.split('\n');
    let n = Number(spi[0]);
    let loop = 3;
    while (loop--) {
        if (n % 10 === 7) {
            console.log("Yes");
            return;
        }
        n = Math.floor(n / 10);
    }

    console.log("No");
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29608
//A,Elebereth Gilthoniel mantae!
//For Temeria!
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<cstdio>
#include<map>
#include<stack>
#include<queue>
#include<cstring> 
using namespace std;;
string s;int nxt[500008];int n; int dp[500008];int op;
int main()
{
	cin>>n>>s;nxt[n]=n;
	for(int i=n-1;i>=0;i--)
	{
		nxt[i]=nxt[i+1];if(s[i]=='0') nxt[i]=i;else op++;
	}
	for(int i=0;i<=n;i++) dp[i]=n+233;dp[0]=0;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='0')
		{
			dp[i+1]=min(dp[i],dp[i+1]);
			continue;
		}
		dp[i+1]=min(dp[i]+1,dp[i+1]);
		if(s[i+1]=='0')
		{
			for(int j=i+2;j<n;j++)
			{
				if(s[j]=='0')
				{
					break;
				}
				dp[j+1]=min(dp[i]+1,dp[j+1]);
			}
		}
		else
		{
			if(s[nxt[i]+1]=='1')dp[nxt[i]+1+1]=min(dp[i]+1,dp[nxt[i]+1+1]);
		}
	}
	cout<<op-dp[n];
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  string A, B, C;
  cin >> A >> B >> C;
  int ans = 0;
  for (int i=0; i<N; i++){
    if (A[i]!=B[i]&&B[i]!=C[i]&&C[i]!=A[i]) ans+=2;
    else if (A[i]!=B[i]||B[i]!=C[i]||C[i]!=A[i]) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W; 
  for (int i = 0; i < W + 2; i++) {
    cout << "#";
  }
  cout << endl;
  for (int i = 0; i < H; i++) {
    string a;
    cin >> a;
    cout << "#" << a << "#" << endl;
  }
  for (int i = 0; i < W + 2; i++) {
    cout << "#";
  }
}
    

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

int n, m;
vector<long long> a, b, c;
vector<long long> dist;
vector<bool> negative;
long long INF = 1001001001001001001;


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

  a.resize(m); b.resize(m); c.resize(m);

  rep (i, m) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
    c[i] = -c[i];
  }


  dist.resize(n);
  fill(dist.begin(), dist.end(), INF);
  dist[0] = 0;

  rep (i, n-1) {
    rep (j, m) {
      if (dist[a[j]] == INF) continue;
      if (dist[b[j]] > dist[a[j]] + c[j]) {
        dist[b[j]] = dist[a[j]] + c[j];
      }
    }
  }


  negative.resize(n);
  fill(negative.begin(), negative.end(), false);

  rep (i, n) {
    rep (j, m) {
      if (dist[a[j]] == INF) continue;
      if (dist[b[j]] > dist[a[j]] + c[j]) {
        dist[b[j]] = dist[a[j]] + c[j];
        negative[b[j]] = true;
      }
    }
  }

  if (negative[n-1]) {
    cout << "inf" << endl;
  }
  else {
    cout << -dist[n-1] << endl;
  }
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 710
using namespace std;
int u,v,n,m;
int a[2][MAXN],cnt,w[MAXN][MAXN];
vector<int> px[2],p[2];
bool vis[MAXN];
int solve(int x,int now){
	p[0].clear();
	p[1].clear();
	px[0].clear();
	px[1].clear();
	px[0].push_back(x);
	vis[x]=1;
	int flag=0;
	while(px[flag].size()!=0){
		for(int i=0;i<px[flag].size();i++){
			int y=px[flag][i];
			for(int j=0;j<p[flag].size();j++)
				if(w[y][p[flag][j]]==0)
					return -1;
			p[flag].push_back(y);
			a[flag][now]++;
			for(int j=1;j<=n;j++)
				if(w[y][j]==0&&vis[j]==0){
					px[flag^1].push_back(j);
					vis[j]=1;
				}
		}
		px[flag].clear();
		flag^=1;
	}
	/*PF("(%d %d)\n",p[0].size(),p[1].size());
	for(int i=0;i<p[0].size();i++)
		PF("{%d}",p[0][i]);
	PF("\n");
	for(int i=0;i<p[1].size();i++)
		PF("[%d]",p[1][i]);
	PF("\n");*/
	return 0;
}
int get_ans(int x){
	int y=n-x;
	return x*(x-1)/2+y*(y-1)/2;
}
int dp[MAXN][MAXN];
int main(){
	SF("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		SF("%d%d",&u,&v);
		w[u][v]=1;
		w[v][u]=1;
	}
	for(int i=1;i<=n;i++)
		if(vis[i]==0)
			if(solve(i,++cnt)==-1){
				PF("-1");
				return 0;
			}
	dp[0][0]=1;
	for(int i=1;i<=cnt;i++)
		for(int j=0;j<=n;j++)
			if(dp[i-1][j]==1){
				dp[i][j+a[0][i]]=1;
				dp[i][j+a[1][i]]=1;
			}
	int minx=-1;
	for(int i=0;i<=n;i++)
		if(dp[cnt][i]==1){
			if(minx==-1)
				minx=i;
			else{
				if(get_ans(minx)>get_ans(i))
					minx=i;
			}
		}
	PF("%d",get_ans(minx));
} 

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef long double D;
typedef complex<D> P;
#define F first
#define S second
const ll MOD=1000000007;
//const ll MOD=998244353;

#define endl "\n"

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

const ll MX=100100;


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N,M,T;
  cin>>N>>M>>T;
  vector<pair<int,pair<int,int>>> A(M);
  cin>>A;
  for(auto &I:A){swap(I.S.F,I.S.S);}
  sort(A.begin(),A.end());
  set<int> S;
  vector<vector<pll>> ev(N);
  pair<int,int> ans[MX];
  for(int i=0;i<N;i++){ans[i]={0,0};}
  ans[0]={0,-1};
  for(int i=0;i<M;i++){
    int a=A[i].F,b=A[i].S.S,c=A[i].S.F;
    b--;
    if(c==1){
      for(auto &I:S){
        ev[I].push_back({b,-a});
        ev[b].push_back({I,-a});
      }
      S.insert(b);
    }
    else{
      S.erase(b);
      for(auto &I:S){
        ev[I].push_back({b,a});
        ev[b].push_back({I,a});
      }
    }
  }
  vector<int> rem;
  for(auto &I:S){rem.push_back(I);}
  for(auto &b:rem){
    int a=T;
    S.erase(b);
    for(auto &I:S){
      ev[I].push_back({b,a});
      ev[b].push_back({I,a});
    }
  }
  vector<ll> bk(N,0);
  for(int i=0;i<N;i++){
    for(auto &I:ev[i]){
      bk[I.F]+=I.S;
      ans[i]=max(ans[i],{bk[I.F],-1*I.F});
    }
    for(auto &I:ev[i]){
      bk[I.F]-=I.S;
    }
    cout<<ans[i].S*-1+1<<endl;
  }
  
  
  
  return 0;
}



Measured memory_bytes: 226868
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++) cin >> a[i];
    int ans = 0;
    int pos = 0;
    while(pos < N-1){
        if(a[pos] == a[pos+1]){
            pos += 2;
            ans++;
        }else pos++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] l = new int[N];
    for(int i = 0; i < N; i++){
      l[i] = sc.nextInt();
    }
    Main abc117B = new Main();
    if(abc117B.solve(l)){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }

  public boolean solve(int[] l) {
    int max = 0;
    int sum = 0;
    for(int i = 0; i < l.length; i++ ){
      if(l[i] > max ) {
        sum += max;
        max = l[i];
      } else {
        sum += l[i];
      }
    }
    return sum > max;
  }
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.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; }
const long long INF = 1LL << 60;

int main(){
  ll a;
  cin >> a;
  string s;
  cin >> s;
  if(a>=3200){
    cout << s << endl;
  }
  else{
    cout << "red" << endl;
  }
  }

Measured memory_bytes: 256
while True:
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == "+":
      print(a + b)
    elif op == "-":
      print(a - b)
    elif op == "*":
      print(a * b)
    elif op == "/":
      print(a // b)
    else:
      break

Measured memory_bytes: 7556
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        s: Chars
    };

    let len = s.len();
    if s[len - 1] == 's' {
        let res = s.into_iter().chain(vec!['e', 's']).collect::<String>();
        println!("{}", res);
    } else {
        let res = s.into_iter().chain(vec!['s']).collect::<String>();
        println!("{}", res);
    }
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


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

typedef vector<int> veci;
typedef pair<int, int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9 + 7)
#define fi first
#define se second
#define endl '\n'

void solve() {
    int n;
    cin >> n;

    veci v(n);
    for (int i=0; i<n; ++i) {
        cin >> v[i];
    }

    veci odd(int(1e5+1),0);
    veci even(int(1e5+1),0);
    for (int i=0; i<n; ++i) {
        if (i%2) {
            odd[v[i]] += 1;
        } else {
            even[v[i]] += 1;
        }
    }

    veci oddidx(int(1e5+1));
    veci evenidx(int(1e5+1));
    for (int i=0; i<=int(1e5); ++i) {
        oddidx[i] = i;
        evenidx[i] = i;
    }

    sort(oddidx.rbegin(), oddidx.rend(), [&odd](int l, int r) { return odd[l]<odd[r];});
    sort(evenidx.rbegin(), evenidx.rend(), [&even](int l, int r) { return even[l]<even[r];});

    int cnt = n-odd[oddidx[0]]-even[evenidx[0]];
    if (oddidx[0] == evenidx[0]) {
        int mini = min(odd[oddidx[0]],even[evenidx[0]]);
        if (odd[oddidx[1]]) {
            mini = min(mini, odd[oddidx[0]] - odd[oddidx[1]]);
        }

        if (even[evenidx[1]]) {
            mini = min(mini, even[evenidx[0]] - even[evenidx[1]]);
        }

        cnt += mini;
    }

    cout << cnt << endl;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST
    (void)argc;
    const string strpath = string(argv[0]) + string("-test.in");
    freopen(strpath.c_str(), "r", stdin);
    int tcs;
    cin >> tcs;
    while (tcs-- > 0)
#endif
    solve();
}


Measured memory_bytes: 2176
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const ll M = 1e9+7;
const ll INF = 1e9+7;

ll h, w, k, sx, sy, gx, gy, s, g, ans;
ll a[1100000];
bool c[1100000];
bool done[1100000];
ll dst[1100000];
priority_queue<P, vector<P>, greater<P> > q;

ll bfs() {
  q.push(P(0, s));
  done[s] = true;
  dst[s] = 0;
  
  while (q.size()) {
    P p = q.top();
    q.pop();
    ll dist = p.first + 1;
    ll pos = p.second;
    ll px = pos / w;
    ll py = pos % w;
    
    for (ll i = px-1; i >= max(0LL, px-k); i--) {
      ll ps = i*w+py;
      if (!c[ps]) break;
      if (done[ps]) {
        if (dst[ps] == dist) continue;
        else break;
      }
      done[ps] = true;
      if (i == gx and py == gy) {
        cout << dist << endl;
        exit(0);
      }
      dst[ps] = dist;
      q.push(P(dist, ps));
    }
    for (ll i = px+1; i < min(h, px+k+1); i++) {
      ll ps = i*w+py;
      if (!c[ps]) break;
      if (done[ps]) {
        if (dst[ps] == dist) continue;
        else break;
      }
      done[ps] = true;
      if (i == gx and py == gy) {
        cout << dist << endl;
        exit(0);
      }
      dst[ps] = dist;
      q.push(P(dist, ps));
    }
    for (ll i = py-1; i >= max(0LL, py-k); i--) {
      ll ps = px*w+i;
      if (!c[ps]) break;
      if (done[ps]) {
        if (dst[ps] == dist) continue;
        else break;
      }
      done[ps] = true;
      if (px == gx and i == gy) {
        cout << dist << endl;
        exit(0);
      }
      dst[ps] = dist;
      q.push(P(dist, ps));
    }
    for (ll i = py+1; i < min(w, py+k+1); i++) {
      ll ps = px*w+i;
      if (!c[ps]) break;
      if (done[ps]) {
        if (dst[ps] == dist) continue;
        else break;
      }
      done[ps] = true;
      if (px == gx and i == gy) {
        cout << dist << endl;
        exit(0);
      }
      dst[ps] = dist;
      q.push(P(dist, ps));
    }
  }
  return -1;
}

int main() {
  scanf("%lld%lld%lld", &h, &w, &k);
  scanf("%lld%lld%lld%lld", &sx, &sy, &gx, &gy);
  sx--; sy--; gx--; gy--;
  s = sx*w + sy;
  g = gx*w + gy;
  
  for (ll i = 0; i < h; i++) {
    for (ll j = 0; j < w; j++) {
      char ch;
      scanf(" %c", &ch);
      if (ch == '.') {
        c[i*w+j] = true;
      }
    }
  }
  
  cout << bfs() << endl;
  return 0;
}

Measured memory_bytes: 12244
// V solo
#include <bits/stdc++.h>

#define forn(i, a, b) for (int i = a; i <= b; ++i)
#define forr(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

const int N = (int)2e5 + 7;
const long long INF = 1e18;

typedef long long ll;
typedef long double ld;

typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

int n, a, x[N];
ll dp[51][51][2505], sum;
int main (){
  scanf ("%d %d", &n, &a);
  forn (i, 0, n - 1) scanf ("%d", x + i), sum += x[i];
  dp[0][0][0] = 1;
  forn (i, 0, n - 1){
    forn (j, 0, n - 1){
      forn (k, 0, sum){
        if (k + x[i] <= sum) dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
        dp[i + 1][j][k] += dp[i][j][k];
      }
    }
  }
  ll ans = 0;
  forn (i, 1, n){
    forn (k, 0, sum){
      if (k == a * i) ans += dp[n][i][k];
    }
  }
  printf ("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 50432
#include<stdio.h>
  int main(void)
  {
   int a,b,c,x,i,j,k,r=0;
   scanf("%d%d%d%d",&a,&b,&c,&x);
   for(i=0;i<=x/500;i++)for(j=0;j<=(x-500*i)/100;j++){
         k=x-500*i-100*j;
         r+=k%50==0&&c>=k/50&&a>=i&&b>=j;
        }
         printf("%d\n",r);
        return 0;
  }


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

struct node
{
    int h;
    int w;
    inline bool operator<(const node &arg) const
    {
        return h == arg.h ? w < arg.w : h < arg.h;
    }
};

int main()
{
    int H, W, m;
    std::cin >> H >> W >> m;

    int *sumh, *sumw;
    sumh = new int[H + 1]();
    sumw = new int[W + 1]();
    int h, w;
    std::map<node, bool> map;
    for (register int i = 0; i < m; ++i)
    {
        std::cin >> h >> w;
        sumh[h]++;
        sumw[w]++;
        map[node{h, w}] = true;
    }

    int maxh = 0;
    std::vector<int> posh;
    for (register int i = 1; i <= H; ++i)
    {
        if (sumh[i] > maxh)
        {
            maxh = sumh[i];
            posh.clear();
        }
        if (sumh[i] == maxh)
        {
            posh.push_back(i);
        }
    }
    int maxw = 0;
    std::vector<int> posw;
    for (register int i = 1; i <= W; ++i)
    {
        if (sumw[i] > maxw)
        {
            maxw = sumw[i];
            posw.clear();
        }
        if (sumw[i] == maxw)
        {
            posw.push_back(i);
        }
    }

    bool flg = true;
    for (std::vector<int>::iterator ith = posh.begin(); flg && ith != posh.end(); ++ith)
    {
        for (std::vector<int>::iterator itw = posw.begin(); flg && itw != posw.end(); ++itw)
        {
            if (!map[node{*ith, *itw}])
            {
                flg = false;
            }
        }
    }

    std::cout << maxh + maxw - flg << std::endl;
    return 0;
}

Measured memory_bytes: 28436
main = do
  li <- getLine
  let [n,k] = map read $ words li
  li <- getLine
  let ps = map read $ words li
  let ans = compute n k ps
  let a2 = show $ div ans 2
  putStrLn (if even ans then a2 else a2 ++ ".5")

{-
1～pが等確率ででるときの期待値は、
sum 1～p/p = p(p+1)/2p = (p+1)/2
ずっと２倍-1で整数で計算しよう。

先頭k個の和をタネとして求める
pi <- psとp(i+k) <- drop k psを使って、
seed + p(i+k) - pi
が次のk個の和、と順に求められる
-}
compute :: Int -> Int -> [Int] -> Int
compute n k ps = k + maximum ss
  where
    s0 = sum $ take k ps
    ss = scanl step s0 $ zip ps $ drop k ps

step s (pi,pik) = s + pik - pi


Measured memory_bytes: 78204
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
using namespace std;

int main(){
	int n,num[101] = {};
	while(cin >> n)num[n]++;
	int max = 0;
	for(int i = 1; i <= 100; i++){
		if(num[i] > max)max = num[i];
	}
	for(int i = 1; i <= 100; i++){
		if(num[i] == max)cout << i << endl;
	}
}


Measured memory_bytes: 3048
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N = getN()
march = [0] * 5
for i in range(N):
    s = input()
    if s[0] =="M":
        march[0] += 1
    elif s[0] == "A":
        march[1] += 1
    elif s[0] == "R":
        march[2] += 1
    elif s[0] == "C":
        march[3] += 1
    elif s[0] == "H":
        march[4] += 1

ans = 0
for i in range(5):
    for j in range(i + 1, 5):
        for k in range(j + 1, 5):
            ans += march[i] * march[j] * march[k]
print(ans)

Measured memory_bytes: 67688
import random

class Dice():
    
    def __init__(self, *n):
       self.rolls = n

    def spin(self, order):
        if order == "N":
            self.rolls = [
                self.rolls[1],
                self.rolls[5],
                self.rolls[2],
                self.rolls[3],
                self.rolls[0],
                self.rolls[4]
            ]
        if order == "E":
            self.rolls = [
                self.rolls[3],
                self.rolls[1],
                self.rolls[0],
                self.rolls[5],
                self.rolls[4],
                self.rolls[2]
            ]
        if order == "S":
            self.rolls = [
                self.rolls[4],
                self.rolls[0],
                self.rolls[2],
                self.rolls[3],
                self.rolls[5],
                self.rolls[1]
            ]
        if order == "W":
            self.rolls = [
                self.rolls[2],
                self.rolls[1],
                self.rolls[5],
                self.rolls[0],
                self.rolls[4],
                self.rolls[3]
            ]
        return self.rolls[0]

d = Dice(*[int(i) for i in input().split()])
directions = ['N','E','S','W']
for _ in range(int(input())):
    a,b = [int(i) for i in input().split()]
    while a != d.rolls[0] or d.rolls[1] != b:
        d.spin(directions[random.randint(0,3)])
    print(d.rolls[2])

Measured memory_bytes: 8240
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e18;
using Graph = vector<vector<int>>;

signed main() {
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> C(H);
  for( int i = 0; i < H; i++ ) cin >> C[i];


  int ans = 0;
  for (int bit = 0; bit < (1<<H); ++bit) {
    vector<bool> tate(H);
    for (int h = 0; h < H; ++h) {
      if (bit & (1<<h)) { // h行目を赤く塗る
        tate[h] = 1;
      }
    }
    for (int bit2 = 0; bit2 < (1<<W); ++bit2) {
      vector<bool> yoko(W);
      for (int w = 0; w < W; ++w) {
        if (bit2 & (1<<w)) { // w列目を赤く塗る
          yoko[w] = 1;
       }
      }
      int cnt = 0;
      for( int i = 0; i < H; i++ ){
        for( int j = 0; j < W; j++ ){
          if( tate[i] == 0 && yoko[j] == 0 && C[i][j] == '#' ) cnt++;
        }
      }
      if( cnt == K ) ans++;
    }
  }

  cout << ans << endl;

 }


Measured memory_bytes: 3636
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

N, M, S = map(int, input().split())
UVAB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(N)]

sumA = 0
for u, v, a, b in UVAB:
    sumA += a
#print(sumA)

def dijkstra(s, graph) -> list:
    dist = [[INF for _ in range(N + 1)] for _ in range(sumA + 1)]
    dist[s][1] = 0
    hp = []
    heappush(hp, (0, (s, 1)))
    while hp:
        #print(hp)
        t, (i, j) = heappop(hp)
        for dt, (ni, nj) in graph[i][j]:
            if dist[ni][nj] > t + dt:
                dist[ni][nj] = t + dt
                heappush(hp, (dist[ni][nj], (ni, nj)))
    #print("")
    return dist

graph = [[[] for _ in range(N + 1)] for _ in range(sumA + 1)]
# graph[i][j] = [(dt, (ni, nj)), ...]
#都市Ajにいるときに、銀貨をi枚持っている
#この時(i, j)から(ni, nj)への遷移にかかる時間はdt

for j in range(1, N + 1):
    c, d = CD[j - 1]
    for i in range(sumA + 1):
        graph[i][j].append((d, (min(i + c, sumA), j)))
#for g in graph[1:][::-1]:
#   print(*g)

for u, v, a, b in UVAB:
    for i in range(a, sumA + 1):
        if i >= a:
            graph[i][u].append((b, (i - a, v)))
            graph[i][v].append((b, (i - a, u)))
#for g in graph[1:]:
#    print(*g)

#print("")
dist = dijkstra(min(S, sumA), graph)

for j in range(2, N + 1):
    ans = INF
    for i in range(sumA + 1):
        ans = min(dist[i][j], ans)
    print(ans)


Measured memory_bytes: 148524
fn main() {
    let s: String = read();
    let t: String = read();
    let s: Vec<char> = s.chars().collect();
    let t: Vec<char> = t.chars().collect();


    let mut ans = 0;

    for i in 0..s.len() {
        if s[i] == t[i] {
            ans += 1;
        }
    }

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





//**********************************************************************************************************************************************//

// 標準入力から一行を読み取り、指定の型に変換する関数
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

// 標準入力からn行を読み取り、各行を空白文字で分割し、各要素を指定の型に変換する関数
pub fn read_vec2<T: std::str::FromStr>(n: u64) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

// 10進数での各桁の和
pub fn sum_dights(x: isize) -> isize {
    if x % 10 == 0 {
        return 0
    }
    let m = x % 10;
    m + sum_dights((x - m) / 10)
}


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

using namespace std;

map< long long, int > prime_factor(long long n) {
	map< long long, int > ret;
	for (long long i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

int main() {

	int n;
	cin >> n;
	map<int, int> res;
	for (int i = 2; i <= n; i++) {

		long long x=i;
		map<long long, int > a;

//		cin >> x;
		a = prime_factor(x);
		a.insert(make_pair(1, 1));
		a.insert(make_pair(x, 1));
		auto iter = a.begin();
		int counter = 0;
		while (iter != a.end()) {
//			cout << iter->first << " " << iter->second << endl;
			if (iter->first != i) {
				res[iter->first] += iter->second;
			}
			else if (iter->first==i && counter == 1) {
				res[iter->first] += iter->second;
			}

			iter = next(iter, 1);
			counter++;
		}
	}
	res.erase(1);
	long long ress = 1;
	for (auto itr = res.begin(); itr != res.end(); itr++) {
		ress = (ress*(itr->second + 1)) % 1000000007;
	}
	cout << ress << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)
#if DEBUG
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...) /* ... */
#endif

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 100
#else
#define SIZE 123450
#endif

int N,M,Q;

void solve() {
    cin>>N;
    map<int, int> M;
    FOR(i,2,1e6) {
        while(N%i==0) {
            N/=i;
            M[i]++;
        }
    }
    if (N>1) {
        M[N]++;
    }
    int ans = 0;
    for (auto p:M) {
        int v = p.second;
        FOR(i,1,p.second+1) {
            if (v >= i) ans++;
            v -= i;
            if (v<=1) break;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100005;
const int maxm = maxn*2;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int n,k;
bool vis[11];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i = 1;i<=k;i++) {
        int x; cin>>x; vis[x] = 1;
    }
    while(1) {
        int x = n;
        int flag = 1;
        while(x) {
            if(vis[x%10]) {flag = 0; break;}
            x/=10;
        }
        if(flag) {
            cout<<n<<'\n'; return 0;
        }
        n++;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> G[1000000];
vector<pair<int, int> > bridge;
vector<int> articulation;
int ord[1000000], low[1000000];
bool vis[1000000];

void dfs(int v, int p, int &k)
{
	vis[v] = true;
	
	ord[v] = k++;
	low[v] = ord[v];
	
	bool isArticulation = false;
	int ct = 0;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			ct++;
			dfs(G[v][i], v, k);
			low[v] = min(low[v], low[G[v][i]]);
			if (~p && ord[v] <= low[G[v][i]]) isArticulation = true;
			if (ord[v] < low[G[v][i]]) bridge.push_back(make_pair(min(v, G[v][i]), max(v, G[v][i])));
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}
	
	if (p == -1 && ct > 1) isArticulation = true;
	if (isArticulation) articulation.push_back(v);
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		G[--x].push_back(--y);
		G[y].push_back(x);
	}
	
	int k = 0;
	for (int i = 0; i < n; i++){
		if (!vis[i]) dfs(i, -1, k);
	}
	
	sort(bridge.begin(), bridge.end());
	sort(articulation.begin(), articulation.end());
	
	//printf("%d\n", articulation.size());
	
	//for (int i = 0; i < articulation.size(); i++)
	//	printf("%d\n", articulation[i] + 1);
	
	printf("%d\n", bridge.size());
	
	//for (int i = 0; i < bridge.size(); i++)
	//	printf("%d %d\n", bridge[i].first + 1, bridge[i].second + 1);
	
	
	return (0);
}


Measured memory_bytes: 26880
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define int long long
using namespace std;
inline int read(){
	int k=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	return k*f;
}
int n,m,a[100010],s1[100010],s2[100010];
signed main()
{
	n=read();m=read();int sum=0;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<n;i++){
		if(a[i]<a[i+1]){
			sum+=a[i+1]-a[i];
			s1[a[i]+1]+=a[i]+1;
			s1[a[i+1]+1]-=a[i]+1;
			s2[a[i]+1]++;s2[a[i+1]+1]--;
		}else{
			sum+=m-a[i]+a[i+1];
			s1[a[i]+1]+=a[i]+1;
			s1[1]-=m-a[i]-1;
			s1[a[i+1]+1]+=m-a[i]-1;
			s2[a[i]+1]++;s2[1]++;s2[a[i+1]+1]--;
		}
	}
	int ans=1e18;
	for(int i=1;i<=m;i++){
		s1[i]+=s1[i-1],s2[i]+=s2[i-1];
		ans=min(ans,sum+s1[i]-i*s2[i]);
	}
	if(ans>sum)ans=sum;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 2560
#include <stdio.h>

int main(void)
{
	int n, m;
	int i;
	int pd[1000];
	int dd[1000];
	int prog;
	int ans;
	
	while (1){
		scanf("%d %d", &n, &m);
		
		if (n == 0 && m == 0){
			break;
		}
		
		for (i = 0; i < n; i++){
			scanf("%d", &pd[i]);
		}
		
		for (i = 0; i < m; i++){
			scanf("%d", &dd[i]);
		}
		
		prog = 1;
		i = 0;
		ans = 0;
		while (prog < n){
			prog += dd[i];
			prog += pd[prog - 1];
			
			i++;
			ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}

Measured memory_bytes: 1036
import bisect
def main():
    N, Q = map(int, input().split())
    S = input()
    ll = []
    t = -1
    for i, v in enumerate(S):
        if v == 'A':
            t = i
        elif v == 'C':
            if t == i-1:
                ll.append(i)
                t = -1
    for _ in range(Q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        li = bisect.bisect_right(ll, l)
        ri = bisect.bisect_right(ll, r)
        print(ri-li)
main()


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

/* short names and const
using ll = long long;
using vll = vector<long long>;
using df = vector<vector<long long>>;
df data(n, vector<long long>(m));
const int MOD = 1e9 + 7;
const long long INF = 1e18;
*/

/* Boost!
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
using boost::algorithm::split; // split(result, s, boost::is_any_of(","));
#include <boost/algorithm/string/join.hpp>
using boost::algorithm::join; // string s = join(arr, "");
#include <boost/algorithm/string/replace.hpp>
using boost::algorithm::replace_all; // replace_all(s, "AtCoder", "A");
#include <boost/range/algorithm.hpp> // boost::sort(arr)
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
*/

/* print(arr)
template <class T>
void print(vector<T> &vec) {
  for (auto& a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  cout << endl;
}
*/

/* fast cin and precise cout
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  getline(cin, s);
  cout << fixed << setprecision(15);
*/

/* sum function
int sum(vector<int> &arr) {
  int res = accumulate(arr.begin(), arr.end(), 0);
  return res;
}
*/


int main() {
  string s;
  cin >> s;
  for (auto &c : s) {
    if (c == '1') {
      c = '9';
    } else if (c == '9') {
      c ='1';
    }
  }
  cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, l, r) for (int i = l; i <= (int)(r); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define all(v) v.begin(), v.end()
#define MOD (int) (1e9+7)
#define INF (int) 1e9
#define LLINF (ll) 1e18

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cntr=0;
    rep(i, n){
        if(s[i]=='R') cntr++;
    }

    int ans = 0;
    rep(i, cntr){
        if(s[i]=='W') ans++;
    }

    cout << ans << endl;
    // printf("%d\n", N);
    return 0;
}

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

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	long long t,a,rt,ra,dt,da;
	cin >> t >> a;
	for(int i=1;i<n;i++){
		cin >> rt >> ra;
		if(rt<t || ra<a){
			if(t%rt!=0)dt=(t/rt)+1;
			else dt=t/rt;
			if(a%ra!=0)da=(a/ra)+1;
			else da=a/ra;
			if(dt>=da){
				t=rt*dt;
				a=ra*dt;
			}
			else{
				t=rt*da;
				a=ra*da;
			}
		}
		else{
			t=rt;
			a=ra;
		}
	}
	cout << t+a << '\n';
}

Measured memory_bytes: 256