akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
using namespace std;
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(){
    int H,N;
    cin>>H>>N;
    vector<int> A(N),B(N);
    for(int i=0;i<N;i++)cin>>A[i]>>B[i];

    vector<vector<long long> > dp(N+1,vector<long long> (H+1,INF));
    dp[0][0]=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<=H;j++){
            chmin(dp[i+1][j],dp[i][j]);
            chmin(dp[i+1][min(j+A[i],H)],dp[i+1][j]+B[i]);
        }
    }
    cout<<dp[N][H]<<endl;
}

Measured memory_bytes: 78592
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int main(){
  int N;
  int count = 0;
  scanf("%d",&N);
  for(int i = 1;i <= N;i++){
    if(i%2 == 0)continue;
    int count_d = 0;
    for(int j = 1;j <= i;j++){
      if(i%j == 0)count_d++;
    }
    if(count_d == 8){
      count++;
    }
  }
  printf("%d\n",count);
  return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<double> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    sort(v.begin(), v.end());
    int k = n;
    while (k > 1) {
        double m = (v[0] + v[1]) / 2;
        v.erase(v.begin() + 1);
        v.erase(v.begin());
        v.push_back(m);
        sort(v.begin(), v.end());
        k--;
    }
    cout << fixed << setprecision(10);
    cout << v[0] << endl;
    return 0;
}


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

int main() {
  string S;
  cin >> S;
  if (S[0] == S[1] && S[1] == S[2] && S[2] == S[3]) {
    cout << "No" << endl;
  }
  else if (S[0] == S[1] && S[2] == S[3]) {
    cout << "Yes" << endl;
  }
  else if (S[0] == S[2] && S[1] == S[3]) {
    cout << "Yes" << endl;
  }
  else if (S[0] == S[3] && S[1] == S[2]) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int p=998244353;
typedef long long ll;
int i,j,k,n,m,x,y,t,a[N][N];
ll w[N][N],r[N][N],f[N][N];
ll val(int a,int b,int c){ return w[b][c]-w[a-1][c]; }
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (i!=j)scanf("%d",&a[i][j]);
	for (i=1;i<=n;i++)for (j=n;j>=i+1;j--){w[i][j]=w[i][j+1];for (k=1;k<=i;k++)w[i][j]+=a[j][k];}
	for (i=1;i<=n;i++)for (j=i+1;j<=n+1;j++){ r[i][j]=r[i][j-1]; for (k=i;k<=j-1;k++)r[i][j]+=a[k][j]; }
    memset(f,0x3f,sizeof f);
	f[0][0]=0;for (i=0;i<=n;i++)for (j=i;j<=n;j++)if (f[i][j]<1e18){for (k=j+1;k<=n+1;k++)f[j][k]=min(f[j][k],f[i][j]+r[j+1][k]+val(i+1,j,k+1));}
    ll ans=1e18;
    for (i=0;i<=n;i++)ans=min(ans,f[i][n+1]);
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
char a[52],b[52];
int main(){
    cin>>a;
    cin>>b;
    int la=strlen(a),lb=strlen(b);
    int l=min(la,lb),ll=max(la,lb);
    for(int i=0;i<=l-1;i++)
        cout<<a[i]<<b[i];
    if(la>lb)
        for(int i=l;i<=ll-1;i++)
            cout<<a[i];
    else for(int i=l;i<=ll-1;i++)
            cout<<b[i];
    return 0;
}

Measured memory_bytes: 256
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn rep<T, F: FnMut() -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|_| f()).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let a: Vec<i32> = rep(n, || scan(tokens));
    let mut k = 0;
    let mut next = 1;
    for ai in a {
        if ai == next {
            next += 1;
        } else {
            k += 1;
        }
    }
    if next == 1 {
        println!("-1");
    } else {
        println!("{}", k);
    }
}


Measured memory_bytes: 6396
# -*- coding: utf-8 -*-
# 入力
x = int(input())

# 6->5->6->5-> ...が最大

# 11の商を計算し2倍
quot, rem = divmod(x, 11)
quot *= 2

# 剰余が1～6なら+1, 7～11なら+2
if rem>6:
    quot += 2
elif rem>0:
    quot += 1

print(quot)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;
const ll mod = 1e9+7;
const int MAX = 3e5;
using P = pair<ll,ll>;

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

P process(ll a, ll b) {
  P p;
  ll g = gcd(abs(a),abs(b));
  a /= g, b /= g;
  if(a*b > 0) p = P(abs(a),abs(b));
  else if(a*b < 0) p = P(-abs(a),abs(b));
  else p = (a == 0 ? P(0,1) : P(1,0)); 
  return p;
}

int main(){
  ll n, zero = 0, ans, x, y, res = 1;
  cin >> n;
  map<P,ll> m;
  vector<ll> pw(MAX,1);
  vector<P> v;
  for(int i = 1; i < MAX; i++) pw[i] = pw[i-1] * 2 % mod;
  rep(i,n) {
    cin >> x >> y;
    if(x == 0 && y == 0) zero++;
    else {
      P p = process(x,y);
      v.push_back(p);
      m[p]++;
    }
  }
  ans = zero;
  for(auto x : v) {
    P y;
    if(x.first > 0) y = P(-x.second,x.first);
    else y = P(x.second,-x.first); 
    ll c = (pw[m[x]] + pw[m[y]] - 1) % mod;
    (res *= c) %= mod;
    m[x] = m[y] = 0;
  }
  res += mod - 1;
  (ans += res) %= mod;
  cout << ans << endl;
  return 0;
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    int N, A;
    cin >> N >> A;
    if(N%500 <= A) {
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


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

typedef long long  ll;
	

int main()
{
  
  ll n,k,x;
  cin>>n>>k;
  map<ll,ll>mp;
 for(ll i=0;i<k;i++)
 {
   cin>>x;
   for(ll j=0;j<x;j++)
    {
    	ll k;
    	cin>>k;
    	mp[k]=1;
    }
 }
 ll c=0;
 for(ll i=1;i<=n;i++)
 {
 	if(!mp[i])
 		c++;
 }
 cout<<c;

}

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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N, K; cin >> N >> K;
	vector<int> h(N);

	REP(i,N) cin >> h[i];

	SORT(h);

	int left = 0, right = K - 1;
	int ans = INF;
	REP(i,N-K+1){
		ans = min(ans, h[right++]-h[left++]);
	}

	cout << ans << endl;



	return 0;

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
 
 
#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define rjm	rep(j,m)


#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)		idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)	for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)		idp p2((x).F, (x).S)
#define dump(x,n)	idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)	idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)	idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)	idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)	rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)	rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}


#define EPS 1e-10
#define ETOL 1e-8
#define MOD 1000000007
#define INF bit(60)

typedef pair<li, li> PI;

vector<pair<string, li>> book;

int main(int argc, char *argv[]){
	string s;
	li page;
	while(cin>>s){
		if(s=="hogehogehogehogehogehogehogehogehogehoge")break;
		cin>>page;
		book.pb({s, page});
	}
	sort(allof(book));

	string prev="";
	foreach(it, book){
		if(it->F!=prev){
			if(prev!="")cout<<endl;
			prev=it->F;
			cout<<prev<<endl;
		}
		cout<<it->S;
		vector<pair<string, li>>::iterator next=it;
		next++;
		if(next!=book.end() && next->F==it->F)cout<<" ";
	}
	puts("");


	return 0;
}

Measured memory_bytes: 1236
N = int(input())
letter_list = []
letter_dic = {}
ans = 0
for _ in range(N):
    tmp = list(input())
    tmp.sort()
    tmp = "".join(tmp)
    if tmp in letter_dic:
        letter_dic[tmp] += 1
        ans += letter_dic[tmp]
    else:
        letter_dic[tmp] = 0

print(ans)


Measured memory_bytes: 17928
import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
# print(a)
# print(b)
# print(c)

ans=0
acount=[0]*n
bcount=[0]*n
ruiseki=[0]*(n+1)
for i in range(n):
    acount[i]=n-bisect.bisect(b,a[i])
    bcount[i]=n-bisect.bisect(c,b[i])
    ruiseki[i+1]=ruiseki[i]+bcount[i]
# print(acount)
# print(bcount)
# print(ruiseki)

for i in range(n):
    # print(ruiseki[n]-ruiseki[n-acount[i]])
    ans+=ruiseki[n]-ruiseki[n-acount[i]]
print(ans)

Measured memory_bytes: 109412
import Data.List as List
import Data.Maybe
import Data.Map as Map
import Control.Monad.State
import Control.Applicative
import Debug.Trace

n = 100000

type Money = Int
type Times = Int

dp :: Money -> Times
dp m = evalState (f 1) $ fromList [(0,0)]
  where
  f :: Int -> State (Map.Map Money Times) Times
  f i = do
    t <- get
    let u = 1 + (minimum $ catMaybes $ List.map (\j -> Map.lookup (i - j) t) ms)
    modify $ Map.insert i u
    if m == i then return u else f $ succ i
    where
      ms = sort $ [1] ++ (takeWhile (n >) [6 ^ i | i <- [1..]]) ++ (takeWhile (n >) [9 ^ i | i <- [1..]])

main = do
  i <- read <$> getLine :: IO Int
  print $ dp i


Measured memory_bytes: 202108
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[3000],x,am[3000];
long long ans=0;
int main()
{
	scanf("%d%d",&n,&x);
	for (int i=1;i<=n;i++) scanf("%d",a+i),am[i]=a[i];
	for (int i=1;i<=n;i++) ans+=a[i];
	for (int i=1;i<n;i++)
	{
		long long tmp=0;
		for (int j=1;j<=n;j++) am[j]=min(am[j],a[(j+i-1)%n+1]),tmp+=am[j];
		tmp+=1ll*x*i;
		ans=min(ans,tmp);
	}
	printf("%lld\n",ans);
}

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

int main() {
    int a,b,c; cin >> a >> b >> c;
    int Max = a;
    Max = max(Max,b);
    Max = max(Max,c);
    cout << a+b+c-Max << endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N,L,minus;
    long ans;
    cin>>N>>L;
    if(L*(L+N-1)<=0) minus=0;
    else if(L>0) minus=L;
    else minus=L+N-1;
    ans=(L-1)*N+(N+1)*N/2-minus;
    cout<<ans;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        
        while (true) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            
            if (left == 0 && right == 0) {
                break;
            }
            
            if (right < left) { 
                int tmp = 0; 
                tmp = right; 
                right = left; 
                left = tmp; 
            }
            
            System.out.printf("%d %d\n", left, right);
            
            
        }
        
        
    }
}


Measured memory_bytes: 40992
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> V;

int main() {
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  if (k%2) dump(b-a);
  else dump(a-b);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int n,count=0;
	cin >> n;
	vector<int>wari(n+1,0);
	for (int i = 1; i <= n; i += 2) {
		for (int j = 1; j <= n; j++) {
			if (i%j == 0) {
				wari[i]++;
			}
		}
	}
	for (int i = 1; i <= n; i+=2) {
		if (wari[i] == 8) {
			count++;
		}
	}
	cout << count << endl;
	
	
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
#include <cassert>
 
using namespace std;
 
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
template<class T> string tostr(T x) { stringstream o; o << x; return o.str(); }
template<class T> T sqr(T x) { return x*x; }
template<class T> T mypow(T x, int n) { T r = 1; while (n > 0) { if (n & 1)r = r*x; x = x*x; n >>= 1; }return r; }
 
int toint(string s) { int v; stringstream i(s); i >> v; return v; }
bool check(int x, int y, int w, int h) { return x >= 0 && y >= 0 && w > x && h > y; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
 
#define REP(i,a,b)	for(int (i) = (a);i < (b);(i)++)
#define rep(i,n)	REP(i,0,n)
#define PER(i,a,b)	for(int (i) = (a-1);i >= (b);(i)--)
#define per(i,n)	PER(i,n,0)
#define each(i,n)	for(auto &i : n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define dump(val) 	cerr << #val " = " << val << endl;
#define dum(val)	cerr << #val " = " << val;
#define FILL(a,v)	fill(a,a+sizeof(a)/sizeof(*a),v)
 
const int dx[8] = { +1,+0,-1,+0,+1,+1,-1,-1 };
const int dy[8] = { +0,-1,+0,+1,-1,+1,-1,+1 };
const int mod = 1e9 + 7;
const int INF = 1e9 + 9;
 
int dp[5001][5001];

int n, k;
vector<int> a;

bool dfs(int t, int sum, int i) {
	if (t == n) {
		return false;
	}
	if (t == i) {
		return dfs(t + 1, sum, i);
	}
	if (sum >= k)return false;
	if (dp[t][sum] == i)return false;
	dp[t][sum] = i;

	if (dfs(t + 1, sum, i))return true;

	if (sum + a[t] < k) {
		if (sum + a[t] >= k - a[i])return true;
		return dfs(t + 1, sum + a[t], i);
	}

	return false;
};

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
 
	cin >> n >> k;
 
	//ai が 必要 => aiを除いて 総和xが (k - ai) <= x < k を満たす集合が存在する
	//
	//ai >= k は絶対必要　<= 取り除いてよい
 
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		if (t < k) {
			a.push_back(t);
		}
	}
 
	n = a.size();

	sort(all(a));
	mclr(dp);
 
	int l = -1, r = n;
	while(r - l > 1) {
		int m = (r + l) / 2.0;
		if (!dfs(0, 0, m)) {
			l = m;
		}
		else {
			r = m;
		}
	}
 
	cout << r << endl;
 
 
	return 0;
}

Measured memory_bytes: 98304
#include<stdio.h>

int main(){
    long long int N;
    long long int A,B,C;


    scanf("%lld %lld %lld", &N,&A,&B);

    C = N/(A+B);
    if(N%(A+B)<= A){
        printf("%lld\n",C*A + (N%(A+B)));
    }
    else{
        printf("%lld\n",C*A + A);
    }
    return 0;
}



    




Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, A, B, m;
    cin >> N >> A >> B;
    if (A + B <= N)
    {
        m = 0;
    }
    else
    {
        m = (A + B) - N;
    }
    cout << min(A, B) << " " << m << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

  for (int i = 0; i < k; i++) {
    if (i%2 == 0) {
      //a->b
      if (a%2 == 1) {
        a--;
      }
      b += a/2;
      a /= 2;
    } else {
      //b->a
      if (b%2 == 1) {
        b--;
      }
      a += b/2;
      b /= 2;
    }
  }

  cout << a << " " << b << endl;
  return 0;
}


Measured memory_bytes: 256
from itertools import combinations
N=input()
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(K+2)] for _ in range(2)]
#dp[smaller][j][i]:=上からiケタ目までを確定したときの場合の数
#smaller = 0: 一致
#j: 0意外の数

dp[0][0][0] = 1
for i in range(1, L+1):
    num = int(N[i-1])
    for k in range(K+1):
        dp[1][k][i] += dp[1][k][i-1]
        dp[1][k+1][i] += dp[1][k][i-1]*9
        
        if num > 0:
            dp[1][k][i] += dp[0][k][i-1]
            dp[1][k+1][i] += dp[0][k][i-1] * (num-1)
        
        if num > 0:
            dp[0][k+1][i] = dp[0][k][i-1]
        else:
            dp[0][k][i] = dp[0][k][i-1]

print(dp[0][K][L] + dp[1][K][L])

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

int main()
{
    int i, j, n, q, S[10001], T[500], C;
    cin >> n;
    for(i = 0; i < n; i++) cin >> S[i];
    cin >> q;
    for(i = 0; i < q; i++) cin >> T[i];

    C = 0;
    for(i = 0; i < q; i++){
        j = 0;
        S[n] = T[i];
        while(S[j] != S[n]) j++;
        if(j < n) C++;
    }
    cout << C << endl;

    return 0;
}

Measured memory_bytes: 1196
#include<bits/stdc++.h>
using namespace std;
#pragma region InOutputMacros
#define ios\
    ios::sync_with_stdio(false);\
    cin.tie(nullptr);
#define VEC(type, name, size)\
    V<type> name(size);\
    IN(name)
#define VVEC(type, name, h, w)\
    VV<type> name(h, V<type>(w));\
    IN(name)
#define INT(...)\
    int __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LL(...)\
    ll __VA_ARGS__;\
    IN(__VA_ARGS__)
#define STR(...)\
    string __VA_ARGS__;\
    IN(__VA_ARGS__)
#define CHAR(...)\
    char __VA_ARGS__;\
    IN(__VA_ARGS__)
#define DOUBLE(...)\
    DOUBLE __VA_ARGS__;\
    IN(__VA_ARGS__)
#define LD(...)\
    LD __VA_ARGS__;\
    IN(__VA_ARGS__)
template <class T> void scan(T &a) { cin >> a; }
template <class T> void scan(vector<T> &a) { for(auto &i : a) scan(i); }
template <class T, class L> void scan(pair<T, L> &p){ scan(p.first); scan(p.second); }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); }
template <class T> inline void print(T &x){ cout << x << '\n';}
#pragma endregion
#pragma region Macros
#define ll long long
#define ld long double
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
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; }
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
inline void err(bool b = true) {if(b) {cout << -1 << '\n'; exit(0);}}
template<class T> inline void fin(bool b = true, T e = 0) {if(b) {cout << e << '\n'; exit(0);}}
template<class T> T Roundup_div(T x, T y) {return (x+(y-1))/y;}
template <typename T> T pow(T a, long long n, T e = 1) {T ret = e; while (n) {if (n & 1) ret *= a; a *= a; n >>= 1; } return ret; }
const ll INF = 1e18;
#pragma endregion

int main(){
    ios;
    INT(n, m);
    VV<> d(n,V<>(n,INF));
    V<> a(m), b(m), c(m);
    REP(i, m){
        cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--;
        d[a[i]][b[i]] = d[b[i]][a[i]] = c[i];
    }
	REP(i, n) d[i][i] = 0;
    REP(k,n) REP(i,n) REP(j,n) chmin(d[i][j], d[i][k] + d[k][j]);
	ll res = m;
    REP(i, m){
        bool flg = false;
        REP(j, n) if(d[j][a[i]] == d[j][b[i]] + c[i]) flg = true;
        res -= flg;
    }
    print(res);
}

Measured memory_bytes: 3688
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,sum=0,n;
cin>>N;
int B=N;
while(N!=0){
    n=N%10;
    sum+=n;
    N/=10;
}
if(B%sum==0)cout<<"Yes";
else cout<<"No";
return 0;
}

Measured memory_bytes: 256
def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    while(b>0):
        n = a%b
        a = b
        b = n
    return a

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

n = int(input())
s = input().split()
arr = []
for i in range(n):
    arr.append(int(s[i]))
a = arr[0]
for i in range(1,n):
    a = lcm(a, arr[i])
print(a)

Measured memory_bytes: 7764
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int[] a = new int[10000];
    int count = 0;
    for (int i = 0; i < N; i++) {
      a[i] = sc.nextInt();
    }
    for (int i = 0; i <= N - 2; i++) {
      if (a[i] == a[i + 1]) {
        count++;
        a[i + 1] = 10001;
      }
    }
    
    System.out.println(count);
  }
}

Measured memory_bytes: 21716
N, elem_okashi_gram = gets.chomp.split(" ").map(&:to_i)
use_okashi_grams = []
donut_count = 0

N.times do 
  use_okashi_grams.push(gets.chomp.to_i)
end

use_okashi_grams.each do |use_okashi_gram|
  elem_okashi_gram -= use_okashi_gram
  donut_count += 1
end

min_gram = use_okashi_grams.min  
while elem_okashi_gram >= min_gram do
  elem_okashi_gram -= min_gram
  donut_count += 1
end

puts donut_count


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

template <typename InputIterator>
typename InputIterator::value_type
summation(InputIterator first, InputIterator last) {
  using T = typename InputIterator::value_type;
  T *p = new T();
  const auto sum = std::accumulate(first, last, *p);
  delete p;
  return sum;
}
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t x;
  std::cin >> x;
  int64_t i = 1;
  while (true) {
    if (x <= i * (i + 1) / 2) {
      std::cout << i << std::endl;
      return 0;
    }
    i++;
  }
  return 0;
}

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

using namespace std;

string s;
int len;

int main(){
	getline (cin,s);
	len = s.size ();
	for (int i = 0; i < len ; ++ i){
		if (s [i] == 'C'){
			for (int j = i; j < len; ++ j){
				if (s [j] == 'F'){
					cout << "Yes";
					return 0;
				}
			}
		}
	}
	cout << "No"; 
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> p(N + 1);
  p[0] = -1;  // Dummy for one-based.
  for (int i = 1; i <= N; ++i) {
    cin >> p[i];
  }
  int n_swaps = 0;
  for (int i = 1; i <= N - 1; ++i) {
    if (p[i] == i) {
      swap(p[i], p[i + 1]);
      ++n_swaps;
    }
  }
  if (p[N] == N) {
    swap(p[N - 1], p[N]);
    ++n_swaps;
  }
  cout << n_swaps << endl;
}


Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	m := nextInt()
	x := nextInt()

	a := map[int]int{}

	for i := 0; i < m; i++ {
		tmp := nextInt()
		a[tmp] = tmp
	}

	cost0 := 0
	// 0方向探索
	for i := x - 1; i > 0; i-- {
		if _, ok := a[i]; ok {
			cost0++
		}
	}

	costN := 0
	// N方向探索
	for i := x + 1; i < n; i++ {
		if _, ok := a[i]; ok {
			costN++
		}
	}

	fmt.Println(min(cost0, costN))

}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// ---- readfunc
func scanInit() {
	const cap = 64 * 1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1812
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <list>
#include <string.h>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

struct node{
	int key;
	node *parent, *left, *right;
};

node *root, *NIL;

void insert(int k) {
	node *y = NIL;
	node *x = root;
	node *z;

	z = (node *)malloc(sizeof(node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while( x != NIL) {
		y = x;
		if( z->key < x->key) x = x->left;
		else x = x->right;
	}
	z->parent = y;
	if( y == NIL) {
		root = z;
	} else if( z->key < y->key){
		y->left = z;
	} else {
		y->right = z;
	}
}



void Preorder(node *t) {
	if( t == NIL) return;
	printf(" %d", t->key);
	Preorder(t->left);
	Preorder(t->right);
}

void Inorder(node *t) {
	if( t == NIL) return;
	Inorder(t->left);
	printf(" %d", t->key);
	Inorder(t->right);
}

void Postorder(node *t) {
	if( t == NIL) return;
	Postorder(t->left);
	Postorder(t->right);
	printf(" %d", t->key);
}

int main(){
	int x, n;
	string st;
	cin >> n;
	for( int i = 0; i < n; i++) {
		cin >> st;
		if(st[0] == 'i') {
			cin >> x;
			insert(x);
		} else {
			Inorder(root);
			cout << endl;
			Preorder(root);
			cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 24648
#include <iostream>

using namespace std;
int a,b,c;
int main(){
	cin >> a >> b >> c;
  	int ans = 3;
  	if(a==b)ans--;
  	if(a==c)ans--;
  	if(b==c)ans--;
  	if(a==b && b==c)ans ++;
  	cout << ans;
	
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	if (a == 0)
		return b;
	return gcd(b % a, a);
}
 
int main()
{
	int k;
	cin >> k;
	int k1 = 9 * k;
	if (k % 7 == 0)
		k1 /= 7;
	if (gcd(10, k1) != 1)
	{
		cout << "-1" << endl;
		return 0;
	}
 
	int s = 1;
	for (int i = 1; i < k1; i++)
	{
		s = (s * 10) % k1;
		if (s == 1)
		{
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int main(){
	
	int L, A, B, C, D, ans, div1, div2;
	
	cin >> L >> A >> B >> C >> D;
	
	div1 = A / C;
	if(A % C != 0){
		div1++;
	}
	div2 = B / D;
	if(B % D != 0){
		div2++;
	}
	
	ans = L - max(div1, div2);
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

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

  int k; cin >> k;

  vi odd, even;

  reps(i, 1, k) {
    if( i % 2 == 0 ) even.pb(i);
    else odd.pb(i);
  }

  int cnt = 0;

  for (int i = 0; i < odd.size(); ++i) {
    for (int j = 0; j < even.size(); ++j) {
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 256
s = input()
s_rev = s[::-1]
#print(s_rev)
center = (len(s)+1)//2
s_firsthalf = s[0:center-1]
#print(s_firsthalf)
s_firsthalf_rev = s_firsthalf[::-1]
if s == s_rev and s_firsthalf == s_firsthalf_rev:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int N, M;
	cin >> N >> M;
	puts([&] {
		return N == M;
	}() ? "Yes": "No");
	return 0;
}


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

int main(void){
    string s;
    cin >> s;
    if(s[(int)s.size()-1] =='s'){
        rep(i,(int) s.size()) cout << s[i];
        cout << "es" << endl;
    }
    else{
        rep(i,(int) s.size()) cout << s[i];
        cout << "s" << endl;
    }
}


Measured memory_bytes: 3624
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pint;
const int MAX = 510000;
const int MOD = 1000000007;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define Rep(i, n) for(ll i = 1; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll fac[MAX], finv[MAX], inv[MAX];


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll 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;
    }

}
ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b) {
  return b ? GCD(b,a%b) : a;
}


ll LCM(ll a,ll b){
  return a/GCD(a,b)*b;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

void runlength(string s,vector<pair<char,ll>> &p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
}




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

const int MAX_N=100010;
vector<bool> sieve_of_eratosthenes(){
  vector<bool> isPrime(MAX_N+1,true);
  for(int i=2;i<=MAX_N;i++){
    if(isPrime[i]){
      for(int j=2*i;j<=MAX_N;j+=i){
        isPrime[j]=false;
      }
    }
  }
  return isPrime;
}

vector<pint> prime_factorize(ll n){
  vector<pint> ans;
  for(ll p=2;p<=sqrt(n);p++){
    if(n%p!=0) continue;
    ll cnt=0;
    while(n%p==0){
      n/=p;
      cnt++;
    }
    ans.push_back(make_pair(p,cnt));
  }
  if(n!=1) ans.push_back(make_pair(n,1));
  return ans;
}

/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  string s;
  cin>>s;
  ll ans1=0;
  ll ans2=0;
  rep(i,s.size()){
    if(i%2==0){
      if(s[i]=='1') ans1++;
      else ans2++;
    }else{
      if(s[i]=='0') ans1++;
      else ans2++;
    }
  }
  cout<<min(ans1,ans2)<<endl;
}

Measured memory_bytes: 512
/*
** Vishal Raj Roy
** Indian Institute of Technology Kharagpur
*/

#include <bits/stdc++.h>

using namespace std;

#define posLSB(X) __builtin_ctz(X)
#define num1bit(X) __builtin_popcount(X)
#define numlead0(X) __builtin_clz(X)
#define gcd(X,Y) __gcd(X,Y)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define ifpresent(CON,VAL) (CON.find(VAL) != CON.end())
#define all(x) x.begin(),x.end()
#define at(X,N) get<N>(X)
#define ins insert
#define xx first
#define yy second
#define sz(x) ((int)x.size())
#define count_ones __builtin_popcountl
#define nl cout<<"\n";
#define name(X) (#X)
#define watch(X) cout << (#X) << " is " << (X) << "\n"
#define sqr(x) ((x)*(x))
#define mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mem(x,val) memset((x),(val),sizeof(x))
#define rite(X) freopen(X,"w",stdout)
#define read(X) freopen(X,"r",stdin)
//FOR(i,1,10) gives 1,2,3,....,9 and FOR(i,10,1) gives 9,8,....,1 also FOR(it, end(v), begin(v)) and FOR(it, begin(v), end(v))
#define FOR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define SEL(X,C) for( auto & X : C )
#define ima INT_MAX
#define imi INT_MIN
#define lma LLONG_MAX
#define lmi LLONG_MIN
using st = string; typedef long long int li; typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef tuple<int,int> i2; typedef tuple<int,int,int> i3; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<i2> vi2; typedef vector<i3> vi3; typedef vector<iii> viii; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef pair<li, li> ll; typedef pair<li, ll> lll; typedef tuple<li,li> l2; typedef tuple<li,li,li> l3; typedef vector<li> vl; typedef vector<ll> vll; typedef vector<l2> vl2; typedef vector<l3> vl3; typedef vector<lll> vlll; typedef vector<vl> vvl; typedef vector<vvl> vvvl; typedef double db; typedef complex<db> cd; typedef vector<cd> vcd; template <class S> using ve = vector<S>; template <class S> using gr = greater<S>; template <class S> using le = less<S>;

const double pi = 2 * acos(0.0);
const int oo = 0x3f3f3f3f; // don't use for long long
const double inf = 1.0/0.0;

int main() {
    ios_base::sync_with_stdio(0);
    int n,d; cin>>n>>d;
    cout<<(n/(2*d+1))+(n%(2*d+1)?1:0)<<"\n";
    return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;
using Graph = vector<vector<int>>;



int main(){
  int n;
  cin>>n;
  for(int i = 0; i*4 <= n; i++){
    for(int j = 0; j*7 + i*4 <= n; j++){
      if(j*7+i*4==n){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
  return 0;
}

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


int main() {
        int n;
        scanf("%d", &n);
        int a[n], dp[n];
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
                dp[i] = dp[i - 1] + abs(a[i] - a[i - 1]);
                if (i - 2 >= 0) dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]));
        }
        cout << dp[n - 1];
}

Measured memory_bytes: 4408
/*
Arthor : Ender_zzm
E-mail zzm_ender_wiggin@outlook.com
Blog ender-zzm.enbar.cn
*/
#include <bits/stdc++.h>
#include<tr1/unordered_map>
using namespace std;

inline int Isdigit(char c) {
	if (c < '0' || c > '9') return 0;
	return 1;
}
inline int readint(){
    register int x = 0, flag = 1;
    register char ch;
    while (!Isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), Isdigit(ch = getchar()));
	return x * flag;
}

inline long long readlong() {
	register long long x = 0, flag = 1;
	register char ch;
	while (!Isdigit(ch = getchar())) if (ch == '-') flag = -1;
    while (x = x * 10 + (ch & 15), Isdigit(ch = getchar()));
	return x * flag;
}
template <class T>
inline void write(T x){
    if (x < 0)
        putchar('-'), x = -x;
    if(x >= 10) write(x / 10); 
    putchar(x % 10 + '0');
}

template<class T> inline bool Chkmax(T& x, const T& y) { return x < y ? x = y, true : false; }
template<class T> inline bool Chkmin(T& x, const T& y) { return x > y ? x = y, true : false; }

#define For(i, x, y) for (int i = (x); i <= (y); i++) 
#define Rep(i, x, y) for (int i = (x); i >= (y); i--) 
#define ri readint
#define rl readlong

const int maxn = 2e5 + 30;
#define int long long 
int n;
int a[maxn], ans;
int prime[maxn], tot, isprime[maxn];
inline void Sieve(int N) {
	isprime[1] = isprime[0] = 1;
	for (int i = 2; i <= N; i++) {
		if (isprime[i] == 0) {
			prime[++tot] = i;
		}
		for (int j = 1; j <= tot && i * prime[j] <= N; j++) {
			isprime[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}
unordered_map<int, int> q; 
int dl[maxn], now[maxn];
#define mp make_pair
pair<int, int> Fj(int x) {
	int tmp = x, asd = 1, dl = 1;
	for (int i = 1; i <= tot; i++) {
		if (tmp % prime[i] == 0) {
			int cnt = 0;
			while(tmp % prime[i] == 0) {
				cnt ++; tmp /= prime[i];
			}
			cnt = cnt % 3;
			for (int j = 1; j <= cnt; j++) asd *= prime[i];
			for (int j = 1; j <= (3 - cnt) % 3; j++) dl *= prime[i];
		}
	}
	//printf("%d %d %d %d\n", x, tmp, asd, dl);
	if (tmp == 1 || tmp == 0) return mp(asd, dl);
	int hhd = sqrt(tmp);
	if (hhd * hhd == tmp) return mp(asd * tmp, dl * hhd);
	return mp(asd * tmp, dl * tmp * tmp);
}
signed main() {
	n = rl();
	for (int i = 1; i <= n; i++) {
		a[i] = rl();
	}
	Sieve(3000);
	for (int i = 1; i <= n; i++) {
		pair<int, int> asd = Fj(a[i]);	
		now[i] = asd.first; dl[i] = asd.second;
		q[now[i]]++;
	//	printf("asdad %d %d %d\n", a[i], asd.first, asd.second);
	}
	for (int i = 1; i <= n; i++) {
		int le = q[now[i]], ri = q[dl[i]];
		if (q[now[i]] == 0 && q[dl[i]] == 0) continue;
		if (now[i] == dl[i]) {
			ans ++;
			q[now[i]] = q[dl[i]] = 0;
			continue;
		}
		ans += max(le, ri);
		q[now[i]] = q[dl[i]] = 0;
	//	cout << ans << endl;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 13812
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    int N, T;
    cin >> N >> T;

    vector<P> AB(N);
    rep(i, N) {
        int A, B;
        cin >> A >> B;
        AB[i] = {A, B};
    }

    sort(all(AB));

    vector<vector<int>> dp(N + 1, vector<int>(7000, -1));
    dp[0][0] = 0;

    rep(i, N) {
        rep(j, 7000) {
            if (dp[i][j] != -1) {
                if (j < T) chmax(dp[i + 1][j + AB[i].first], dp[i][j] + AB[i].second);
                chmax(dp[i + 1][j], dp[i][j]);
            }
        }
    }

    int ans = 0;
    rep(i, dp[N].size()) {
        chmax(ans, dp[N][i]);
    }

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

Measured memory_bytes: 85584
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <tuple>
#include <set>
using namespace std;

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

#define max_n 100

int N;
vector<int> A;

int main() {

	cin >> N;

	rep(i, N){
		int j = 0;
		cin >> j;
		A.push_back(j);
	}

	sort(A.begin(), A.end());

	double Left = A[0];
	rep(i,N-1){
		Left = (Left + A[i + 1])/2;
	}

	printf("%f\n", Left);

	return 0;	
}

Measured memory_bytes: 256
N, D = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]

import numpy as np
def dist(X, Y, D):
    s2 = 0
    for i in range(D):
        s2 += (X[i] - Y[i]) * (X[i] - Y[i])
    s1 = int(np.sqrt(s2))
    if s2 == s1 * s1:
        return True
    return False

c = 0
for i in range(N):
    for j in range(i+1, N):
        if dist(data[i], data[j], D):
            c += 1
print("{}".format(c))


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

using namespace std;

int main()
{
	double A, B, C, D;
	cin >> A >> B >> C >> D;
	if (ceil(A / D) >= ceil(C / B)) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
    int sum,a,total=0;
    cin >> sum;
    if(sum == 0) break;
    for(int i=0;i<9;i++){
      cin >> a;
      total+=a;
    }
    cout << sum-total << endl;
    total=0;
  }
  return 0;
}

Measured memory_bytes: 3000
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long ll;

int matrix[50][50];

void init(){
	for(int i = 0; i < 50; i ++){
		for(int j = 0; j < 50; j++){
			matrix[i][j] = 0;
		}
	}
}

int main()
{
	string str;
	cin>>str;
	str.pop_back();
	int n = str.length()/2;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		if( str.substr(0,i) == str.substr(i,i)) ans = max(ans,i*2);
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3200
#include <iostream>
using namespace std;
int main()
{
	int A;
	int B;
	cin>>A>>B;
	if(A-2*B <= 0)
	{
		cout<< 0 <<endl;
	}
	else
	{
		cout<< A-2*B <<endl;
	}
	return 0;
}

Measured memory_bytes: 256
from collections import deque

def dfs(sx, sy ,gx, gy):             
    d = [[float("inf")] * w for i in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    # スタート地点をキューにしまう
    que.append((sx,sy))
    # スタート地点に初期移動回数をしまう
    d[sx][sy] = 0

    white = 0

    for m in maze:
        white += m.count(".")

    while que:
        # キューの左端を取り出す
        now = que.popleft()
        # ゴールにたどり着いていれば終了
        if now[0] == gx and now[1] == gy:
            break
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            # 移動できてまだ到達していない場合以下の処理を行う
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 次の地点をキューに加える
                que.append((nx, ny))
                # 次の位置に移動回数をしまう
                d[nx][ny] = d[now[0]][now[1]] + 1

    if d[gx][gy] == float("inf"):
       return -1
    else:
        return white - d[gx][gy] - 1

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]

print(dfs(0, 0, h - 1, w - 1))

Measured memory_bytes: 3436
#include <stdio.h>
#include <math.h>
int main(void)
{
	int s[50],i = 0,j;
	double w[50],h[50],b[50];
	while (scanf("%d, %lf, %lf", &s[i], &w[i], &h[i]) != EOF) {
		b[i]=w[i]/(h[i]*h[i]);
		i++;
	}
	for(j=0;j<=i;j++){
		if(b[j]>=25){
			printf("%d\n",s[j]);
		}
		
		}
	
	
	return 0;
}


Measured memory_bytes: 2032
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10;

int main() {
	fast_cin();
	string s; cin >> s;
	int n = s.length();
	s = "0" + s;
	bool fail = false;
	if (s[n] == '1' or s[1] == '0') {
		fail = true;
	}
	for (int i = 1; i <= n - 1; ++i) {
		if (s[i] != s[n - i]) {
			fail = true;
		}
	}
	if (fail) {
		cout << "-1\n";
	} else {
		int u = 1, prev = 0;
		for (int i = 1; i <= n - 1; ++i) {
			if (s[i] == '0') {
				continue;
			}
			int c = i - prev - 1, v = u + c + 1;
			for (int j = u + 1; j <= v; ++j) {
				cout << u << ' ' << j << '\n';
			}
			u = v;
			prev = i;
		}
	}
}

Measured memory_bytes: 1664
B, W = map(int,input().split())
Mod = 10**9+7
magick = 500000004

inv_t = [0]+[1]
for i in range(2,B+W+1):
   inv_t += [inv_t[Mod % i] * (Mod - int(Mod / i)) % Mod]

consts_B, consts_W = [0]*(B-1)+ [1], [0]*(W-1)+[1]
for i in range(B+W):
  if i >= B: consts_B += [consts_B[-1]*(i)*inv_t[i-B+1]%Mod]
  if i >= W: consts_W += [consts_W[-1]*(i)*inv_t[i-W+1]%Mod]

p, q = 0, 0
inv = 1
for i in range(B+W):
  print((1-p+q)*magick%Mod)
  inv *= magick
  inv = inv%Mod
  p += consts_B[i]*inv
  q += consts_W[i]*inv


Measured memory_bytes: 85448
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <cstring>
using namespace std;
int A[200000];
int next_A[60][200000];

int main(){
  int N;
  long long K;
  cin >> N >> K;
  for(int i = 0; i < N; i++){
    cin >> A[i];
    A[i] --;
  }

  for(int i = 0; i < N; i++){
    next_A[0][i] = A[i];
  }
  for(int i = 1; i < 60; i++){
    for(int j = 0; j < N; j++){
      next_A[i][j] = next_A[i - 1][next_A[i - 1][j]];
    }
  }

  int cur_city = 0;
  for(int i = 0; i < 60; i++){
    if(((K >> i) & 1) == 1){
      cur_city = next_A[i][cur_city];
    }
  }
  cout << cur_city + 1 << endl;
  return 0;
}


Measured memory_bytes: 51268
import Control.Monad
import Data.List

reduceRow :: [[Bool]] -> [[Bool]]
reduceRow = filter or

map2 :: (a -> b) -> [[a]] -> [[b]]
map2 f = map (map f)

main = do
    [y, x] <- map read . words <$> getLine
    map <- replicateM y getLine
    let ans = map2 (\b -> if b then '#' else '.') $ transpose $ reduceRow $ transpose $ reduceRow $ map2 (== '#') map
    forM_ ans putStrLn


Measured memory_bytes: 2428
/*
          ,     \    /      ,
         / \    )\__/(     / \
        /   \  (_\  /_)   /   \
   ____/_____\__\@  @/___/_____\____
  |             |\../|              |
  |              \VV/               |
  |        ------hoi-------         |
  |_________________________________|
   |    /\ /      \\       \ /\    |
   |  /   V        ))       V   \  |
   |/     `       //        '     \|
   `              V                '
*/

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define f first
#define se second
#define Speedforce boost();
#define fop(s1, s2) freopen(s1, "r", stdin);freopen(s2, "w", stdout);

using namespace std;

void boost(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const int N = 1e6;
const ll inf = 1e9 + 7;
const ld PI = acos(-1);

ll bin_pow(ll x, ll y){
    ll res = 1, base = x;
    while(y){
        if(y & 1){
            res *= base;
            res %= inf;
        }
        base *= base;
        base %= inf;
        y /= 2;
    }
    return res;
}

int x, y, a, b, c;
ll A[N], B[N], C[N];

int main(){
    Speedforce
    //fop("", "")
    cin >> x >> y >> a >> b >> c;
    for(int i = 1;i <= a;i ++){
        cin >> A[i];
    }
    for(int i = 1;i <= b;i ++){
        cin >> B[i];
    }
    for(int i = 1;i <= c;i ++){
        cin >> C[i];
    }
    sort(A + 1, A + 1 + a);
    sort(B + 1, B + 1 + b);
    sort(C + 1, C + 1 + c);
    reverse(A + 1, A + 1 + a);
    reverse(B + 1, B + 1 + b);
    reverse(C + 1, C + 1 + c);
    ll sum1 = 0, sum2 = 0;
    for(int i = 1;i <= x;i ++){
        sum1 += A[i];
    }
    for(int i = 1;i <= y;i ++){
        sum1 += B[i];
    }
    for(int i = 1;i <= c;i ++){
        if(!x && !y){
            break;
        }
        if(!x){
            if(B[y] < C[i]){
                sum2 -= B[y];
                sum2 += C[i];
                y--;
            }
            continue;
        }
        if(!y){
            if(A[x] < C[i]){
                sum1 -= A[x];
                sum1 += C[i];
                x--;
            }
            continue;
        }
        if(A[x] < B[y]){
            if(A[x] < C[i]){
                sum1 -= A[x];
                sum1 += C[i];
                x--;
            }
            continue;
        }
        if(A[x] >= B[y]){
            if(B[y] < C[i]){
                sum2 -= B[y];
                sum2 += C[i];
                y--;
            }
            continue;
        }
    }
    cout << sum2 + sum1;
}


Measured memory_bytes: 9216