akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;

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


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N, M; std::cin >> N >> M;
  std::unordered_map<int, int> a, w;
  rep(i,M) {
    int p; std::cin >> p;
    std::string s; std::cin >> s;
    if ( s == "AC") {
      a[p] = 1;
    }
    else {
      if ( a.count(p) == 0 ) w[p]++;
    }
  }

  int wa = 0;
  for(auto&& k : a) if ( w.count(k.first) != 0 ) wa += w[k.first];

  std::cout << sz(a) << " " << wa << std::endl;
  return 0;
}


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

int main(){
  string S;
  cin >> S;
  int N = S.size();
  string pre="";
  string past="";
  for(int i=0;i<N;i++){
    if(i < (N-1)/2){
      pre += S.at(i);
    }else if(i >= (N+1)/2) {
      past += S.at(i);
    }
  }
  
  if(pre == past){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return(0);
}


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

/*int memo[1000];
int compute(int a[],int n,int st){
	if(st==n-1)
		return 0;
	if(st>=n)
		return 0;

	int q1=10000,q2=10000;
	if(st-1<=n-1){
		q1=abs(a[st]-a[st+1])+compute(a,n,st+1);
		//cout<<q1<<" "<<st<<endl;
	}
	if(st-2<=n-1)
	{
		q2=abs(a[st]-a[st+2])+compute(a,n,st+2);
		//cout<<q2<<" "<<st<<endl;
	}
	return min(q1,q2);
}
int compute_memo(int a[],int n,int s){
	if(s==0)
	{
		memo[s]=0;
		return 0;
	}
	int q1=10000;
	int q2=10000;
	if(memo[s]!=-1)
		return memo[s];
	if(s-1>=0){
		q1=abs(a[s]-a[s-1])+compute_memo(a,n,s-1);
	}
	if(s-2>=0)
	{
		q1=abs(a[s]-a[s-2])+compute_memo(a,n,s-2);
	}
	cout<<s<<" "<<q1<<" "<<q2<<endl;
	memo[s]=min(q1,q2);
	return memo[s];
}*/
int dp_compute(int a[],int n){
	int dp[100009]={};
	dp[0]=0;
	for(int i=1;i<n;i++){
		int q1=INT_MAX,q2=INT_MAX;
		if(i-1>=0)
			q1=dp[i-1]+abs(a[i]-a[i-1]);
		if(i-2>=0)
			q2=dp[i-2]+abs(a[i]-a[i-2]);
		dp[i]=min(q1,q2);
	}
	return dp[n-1];
}

int main(){
	int n;
	cin>>n;
	int a[100009];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<dp_compute(a,n)<<endl;
	return 0;
}




Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

const int MOD_TYPE = 1;
const ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const ld PI = acos(-1.0);
const ld EPS = 1e-11;

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

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

  string s;
  cin >> s;
  Yes(s[2] == s[3] && s[4] == s[5]);

  return 0;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

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

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

string X="ATCG";
bool ok(char c){
	return find(all(X),c)!=X.end();
}
signed main(){
	string S;cin>>S;
	int N=S.size();
	int cur=0;
	int ans=0;
	while(cur<N){
		if(!ok(S[cur])){
			cur++;
			continue;
		}
		int nex=cur;
		while(nex<N&&ok(S[nex]))nex++;
		chmax(ans,nex-cur);
		cur=nex;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	nums, err := nextInts(n, sc)
	if err != nil {
		panic(err)
	}
	ms := prepareMs(n)
	cnt := 0
	for _, v := range ms {
		cnt += insertionSort(nums, v)
	}
	fmt.Println(len(ms))
	fmt.Println(strings.Join(istoAs(ms), " "))
	fmt.Println(cnt)
	for _, v := range nums {
		fmt.Println(v)
	}
}

func insertionSort(nums []int, g int) int {
	cnt := 0
	n := len(nums)
	for i := g; i < n; i++ {
		v := nums[i]
		j := i - g
		for j >= 0 && nums[j] > v {
			nums[j+g] = nums[j]
			j = j - g
			cnt++
		}
		nums[j+g] = v
	}
	return cnt
}

func prepareMs(n int) []int {
	if n <= 1 {
		return []int{1}
	}
	ms := []int{}
	for x := (n - 1); x > 0; x = x >> 1 {
		ms = append(ms, x)
	}
	return ms
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextInts(n int, sc *bufio.Scanner) ([]int, error) {
	res := make([]int, n)
	for i, _ := range res {
		x, err := nextInt(sc)
		if err != nil {
			return nil, err
		}
		res[i] = x
	}
	return res, nil
}

func istoAs(ns []int) []string {
	is := make([]string, len(ns))
	for i, v := range ns {
		is[i] = strconv.Itoa(v)
	}
	return is
}



Measured memory_bytes: 17424
import sys

INPUT = lambda: sys.stdin.readline().rstrip()

sys.setrecursionlimit(10 ** 9)


def main():
    S = INPUT()

    ans = 1000
    for i in range(len(S)-2):
        ans = min(abs(int(S[i:i+3]) - 753), ans)

    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
class UnionFind
  def initialize(n)
    @parent = (0..n).to_a
  end

  def unite(x, y)
    while @parent[x] != @parent[y]
      x, y = y, x if @parent[x] > @parent[y]
      break @parent[x] = @parent[y] if x == @parent[x]
      @parent[x], x = @parent[y], @parent[x]
    end
  end

  def root(x)
    x = @parent[@parent[x]] while x != @parent[x]
    return x
  end
end

n, k, l = gets.split.map(&:to_i)
uf1 = UnionFind.new(n)
uf2 = UnionFind.new(n)
k.times do
  a, b = gets.split.map(&:to_i)
  a -= 1
  b -= 1
  uf1.unite(a, b)
end
l.times do
  a, b = gets.split.map(&:to_i)
  a -= 1
  b -= 1
  uf2.unite(a, b)
end
cnt = Hash.new(0)
n.times do |i|
  cnt[[uf1.root(i), uf2.root(i)].inspect] += 1
end
ans = []
n.times do |i|
  ans << cnt[[uf1.root(i), uf2.root(i)].inspect]
end
puts ans * " "


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

def selectionSort(A, N):
    count = 0
    for i in range(0, N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j
        if not minj == i: count += 1
        A[i],  A[minj] = A[minj], A[i]
        
    return count

count = selectionSort(A, N)        
print(' '.join(map(str,A)))
print("%d"%(count))


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

int main () {
    string s;
    cin >> s;

    string ans;

    for (int i = 0; i < s.length(); i++) {
        if (s.at(i) == '1') ans += '1';
        else if (s.at(i) == '0') ans += '0';
        else if(!ans.empty()) ans.pop_back();
    }

    cout << ans << endl;

    return 0;
}

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

ll n, k, a[MAXN], ans;

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 1; i < n; i++){
        if(a[i] + a[i - 1] > k){
            ll m = a[i] + a[i - 1] - k;
            if(a[i] >= m){
                a[i] -= m;
                ans += m;
            }
            else {
                a[i] = 0;
                a[i - 1] -= m - a[i];
                ans += m;
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

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

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

    vector<ll> a(n);
    rep(i,n) {
        cin >> a[i];
    }

    ll ans = 1;
    int ansm = 0 ;
    sort(ALL(a));
    for (int i = 0; i < n; i++)
    {

        if(a[i] == 0) {
            ans = 0;
            break;
        }
        if (ans > 1000000000000000000 / a[i])
        {
            ansm = -1;
            break;
        } else 
        {
            ans *= a[i];
        }
    }

    if(ansm == -1) {
        cout << ansm << "\n";
    } else {
        cout << ans << "\n";
    }
}

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

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

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


int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int a=0,b=0,c=0,d=0,m=0,n=0,h=0,w=0,count=0,ans=0;
  string s;
  cin>>a>>b>>c;
  for(int i=1;i<=(int)pow(100,2);i++){
    if((a*i)%b==c){
      cout<<"YES"<<endl;
      return 0;
    }
  }
  cout<<"NO"<<endl;
}
///////////////////////////

Measured memory_bytes: 256
import java.util.Scanner;

//Extraordinary Grid 2
public class Main{

	public static char[][] key = {
		{' '},
		{'\'' , ',' , '.' , '!' , '?'},
		{'a', 'b', 'c', 'A', 'B', 'C'},
		{'d', 'e', 'f', 'D', 'E', 'F'},
		{'g', 'h', 'i', 'G', 'H', 'I'},
		{'j', 'k', 'l', 'J', 'K', 'L'},
		{'m', 'n', 'o', 'M', 'N', 'O'},
		{'p', 'q', 'r', 's', 'P', 'Q', 'R', 'S'},
		{'t', 'u', 'v', 'T', 'U', 'V'},
		{'w', 'x', 'y', 'z', 'W', 'X', 'Y', 'Z'}
	};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			char[] s = (sc.next()+"0").toCharArray();
			StringBuilder sb = new StringBuilder();
			int i=0;
			while(i<s.length){
				char p = s[i];
				int k = (int)(s[i]-'0');
				int c = 0;
				i++;
				if(k==0){
					sb.append(' ');
					continue;
				}
				while(i<s.length&&p==s[i]){
					i++;
					c++;
				}
				sb.append(key[k][c%key[k].length]);
				if(s[i]=='0')i++;
			}
			System.out.println(sb);
		}
	}
}

Measured memory_bytes: 12000
N, K = map(int, input().split())
r = list(map(int, input().split()))
n_cnt = 0
g_cnt = 0
for n in range(N):
  for i in range(N):
    if i > n and r[n] > r[i]:
      n_cnt += 1
    if r[n] > r[i]:
      g_cnt += 1
ans = ((n_cnt * K) + (g_cnt * ((K - 1) * K // 2))) % (10**9 + 7)
print(ans)


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

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

  int ans = 0;
  for (int i = A; i <= B; i++) {
    int first2 = i / 1000;
    int last2 = i % 100;

    int digit1 = first2 % 10 * 10;
    int digit2 = first2 / 10;
    first2 = digit1 + digit2;

    if (first2 == last2) {
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
	int id,amount,sum;
	for(int i = 0; i < 4; i++){
		scanf("%d %d",&id,&amount);
		switch(id){
		case 1:sum = 6000*amount;
		break;
		case 2:sum = 4000*amount;
		break;
		case 3:sum = 3000*amount;
		break;
		case 4:sum = 2000*amount;
		break;
		}
		printf("%d\n",sum);
	}
}


Measured memory_bytes: 2756
// AOJ 0294 Catch a Thief
// 2018.2.14 
// Lengauer-Tarjan algorithm? 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX   100002
#define QSIZE 150000
#define MAGIC 150

int par[MAX], m[MAX];
int parent[MAX], vertex[MAX];
int semi[MAX], idom[MAX], U[MAX];
int **b_to, b_hi[MAX];
int *g_to[MAX], g_hi[MAX], _g_hi[MAX];
int *r_to[MAX], r_hi[MAX], _r_hi[MAX];
int *q, top;

int find(int v) { int r;
	if (par[v] == v) return v;
	r = find(par[v]);
	if (semi[m[v]] > semi[m[par[v]]]) m[v] = m[par[v]];
	return par[v] = r;
}
int eval(int v) { find(v); return m[v]; }
void link(int x, int y) { par[y] = x; }

void tree(int n)
{
	int id, i, j, w, u, v;
	
	for (i = 0; i < n; i++) par[i] = m[i] = i, semi[i] = -1;

	id = 0, q[0] = 0, top = 1;
	while (top) {
		v = q[--top];
		if (semi[v] >= 0) continue;
		semi[v] = id;
		vertex[id++] = v;
		for (i = g_hi[v]-1; i >= 0; i--) {
			u = g_to[v][i];
			if (semi[u] < 0) parent[u] = v, q[top++] = u;
		}
	}
	free(q);

	b_to = malloc(n * sizeof(int *));
	b_to[0] = malloc(25000 << 2);
	for (i = 1; i < n; i++) b_to[i] = malloc(MAGIC << 2);

	b_to[0][0] = 0, u = 25000;
	for (i = 1; i < n; i++) for (j = 0; j < MAGIC; j++) {
		b_to[i][j] = u, u += MAGIC;
	}

	for (i = n-1; i > 0; i--) {
		w = vertex[i];
		for (j = 0; j < r_hi[w]; j++) {
			v = r_to[w][j];
			u = eval(v);
			if (semi[w] > semi[u]) semi[w] = semi[u];
		}
		v = vertex[semi[w]];
		b_to[v][b_hi[v]++] = w;
		u = parent[w];
		for (j = 0; j < b_hi[u]; j++) {
			v = b_to[u][j];
			U[v] = eval(v);
		}
		b_hi[u] = 0;
		link(u, w);
	}
//	free(b_to);

	for (i = 1; i < n; i++) {
		w = vertex[i];
		u = U[w];
		if (semi[w] == semi[u]) idom[w] = semi[w];
		else idom[w] = idom[u];
	}
	for (i = 1; i < n; i++) {
		w = vertex[i];
		idom[w] = vertex[idom[w]];
	}
}

//#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}

int main()
{
	int n, m, i, s, t, Q, r;
	
	n = in(), m = in();
	i = m << 2; if (i < QSIZE) i = QSIZE;
	q = malloc(i << 2);

	top = 0; for (i = 0; i < m; i++) {
		s = in()-1, t = in()-1;
		q[top++] = s, q[top++] = t;
		_g_hi[s]++, _r_hi[t]++;
	}
	for (i = 0; i < n; i++) {
		g_to[i] = malloc(_g_hi[i] << 2);
		r_to[i] = malloc(_r_hi[i] << 2);
	}
	top = 0; for (i = 0; i < m; i++) {
		s = q[top++], t = q[top++];
		g_to[s][g_hi[s]++] = t;
		r_to[t][r_hi[t]++] = s;
	}

	tree(n);

	Q = in();
	while (Q--) {
		r = in()-1;
		if (!idom[r]) printf("%d\n", r+1);
		else          printf("%d\n", idom[r]+1);
	}
	return 0;
}


Measured memory_bytes: 74544
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using ll = long long;
using P = pair<ll,ll>;
using vec = vector<ll>;
using vecp = vector<P>;
using mat = vector<vec>;
using matp = vector<vecp>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define all(v) v.begin(), v.end()

int main(){
  ll N,Q;
  cin >> N >> Q;
  fenwick_tree<ll> A(N);
  rep(i,N){
    ll a;
    cin >> a;
    A.add(i,a);
  }
  rep(i,Q){
    ll a,b,c;
    cin >> a >> b >> c;
    if(a==0){
      A.add(b,c);
    }else{
      cout << A.sum(b,c) << endl;
    }
  }
}

Measured memory_bytes: 8236
package main

import (
	"fmt"
	"math"
)

func chmin(a *int, b int) bool {
	if *a > b {
		(*a) = b
		return true
	}
	return false
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func main() {
	var N, K int
	fmt.Scan(&N, &K)

	const INF = 1 << 30
	var dp = make([]int, N)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = 0

	var h = make([]int, N)
	for i := range h {
		fmt.Scan(&h[i])
	}

	for i := 0; i < N; i++ {
		for j := 1; j <= K; j++ {
			if i+j < N {
				chmin(&dp[i+j], dp[i]+abs(h[i]-h[i+j]))
			}
		}
	}

	fmt.Println(dp[N-1])
}

Measured memory_bytes: 5504
import sys
import math
 
 
def solv(l, w, h, ent):
    cheese = [l, w, h]
    cheese.pop(cheese.index(max(cheese)))
    diagonal = math.sqrt(cheese[0] ** 2 + cheese[1] ** 2)
    ent_size = map(lambda x: x * 2, ent)
    for size in ent_size:
        if diagonal < size:
            print 'OK'
        else:
            print 'NA'
 
 
while True:
    l, w, h = tuple(map(int, sys.stdin.readline().split(' ')))
    if (l, w, h) == (0, 0, 0):
        exit()
    n = int(sys.stdin.readline())
    ent = []
    for i in range(n):
        ent.append(int(sys.stdin.readline()))
    solv(l, w, h, ent)

Measured memory_bytes: 4380
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <utility>
#include <random>
#include <chrono>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//const int mod = 1e9+7;
unordered_set<int> us;
const int N = 2e5 + 10;
int arr[N], n;
bool st[N];
unordered_map<int, int> cnts;
inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

bool cmp(int a, int b) {
    return a > b;
}

int main()
{
    quickread();
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> arr[i];
        cnts[arr[i]] ++;
    }
    int cnt = 0;
    sort(arr, arr+n);
    
    for(int i = 0; i < n; i ++) {
        for(int j = 1; j * j <= arr[i]; j ++ ) {
            if(arr[i] % j == 0) {
                if(us.count(j) || us.count(arr[i] / j)) {
                    st[i] = true;
                    break;
                }
            }
        }
        us.insert(arr[i]);
    }
    for(int i = 0; i < n; i ++) {
        if(cnts[arr[i]] == 1 && (!st[i])) cnt ++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 20564
//#define local
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,n); for(long long i = 0;i < (n);i++)
using ll = long long;
using P = pair<long long,long long>;
template <class T> using vec = vector<T>;
#ifdef local
#include "debug.cpp"
#else
#define debug(...)
#endif

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout << fixed << setprecision(10);
    ll n; cin >> n;
    vec<ll> a(n); rep(i,n)cin >> a[i];
    ll res = 0;
    rep(i,n-1){
        if(a[i] > a[i+1]){
            res += a[i] - a[i+1];
            a[i+1] = a[i];
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 4716
#include <stdio.h>

void Digits(int n, int *a);

int main(){
    int A, B, a[5], count = 0;
    scanf("%d %d", &A, &B);

    for(int i = A; i <= B; i++){
        Digits(i, a);
        if(a[0] == a[4] && a[1] == a[3]){
            count++;
        }
    }

    printf("%d\n", count);
    return 0;
}

void Digits(int n, int *a){
    int num = 0;
    for(int i = n; i > 0; i /= 10){
        a[num] = i % 10;
        num++;
    }
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a = input.nextInt();
        int b = input.nextInt();
        String s = input.next();
        int pop = 0;
        int abr = 0;
        for (int i = 0; i < n; i++){
            String ans = "No";
            char c = s.charAt(i);
            if (c == 'a'){
                if (pop < a+b){
                    ans = "Yes";
                    pop += 1;
                }
            } else if (c == 'b'){
                if (pop < a+b && abr < b){
                    ans = "Yes";
                    pop += 1;
                    abr += 1;
                }
            }
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 37528
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#define ll long long
#define rep(i,s,n) for(ll i = (ll)(s); i < (ll)(n); i++)
#define all(a) (a).begin(),a.end()
#define mod 1000000007
using namespace std;
using graph =vector<vector<ll>>;
const ll MAX = 510000;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
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;
    }
}

// 二項係数計算nCk
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;
}

// 二項係数計算nPk
ll per(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n-k] % MOD) % MOD;
}

// mod. m での a の逆元 a^{-1} を計算する
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/* ユークリッドの互除法 最大公約数*/
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;
}


/*二点間の距離*/
double dist(pair<double,double> a,pair<double,double> b){
	return sqrt(pow((a.first - b.first) ,2) + pow((a.second - b.second),2));
}

//繰り返し自乗法
double ism(double aa,ll p){
    double ap=aa;
    double ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans*=ap;
        }
        p/=2;
        ap=ap*ap;
    }
    return ans;

}
//繰り返し自乗法(アマリトリバージョン)
ll ismm(ll aa,ll p,ll m){
    ll ap=aa;
    ll ans=1;
    while(p>0){
        //cout<<"p="<<p<<",ap="<<ap<<endl;
        if(p&1){//奇数が真
            ans=(ans*ap)%m;    
        }
        p/=2;              
        ap=(ap*ap)%m;
    }
    return ans;

}
/*
ll solve(ll i,ll m,vector<ll>t,ll n){
    if(m==0){
        return 1;
    }
    if(i>=n){
        return 0;
    }
    
    
    cout<<i+1<<" "<<m<<endl;
    cout<<i+1<<" "<<m-t[i]<<endl;
    ll res=solve(i+1,m,t,n)||solve(i+1,m-t[i],t,n);
    return res;
}
*/


//小数点12桁
struct all_init
{
    all_init()
    {
        cout << fixed << setprecision(12);
    }
} All_init;


int main()
{
    ll h,w;
    cin>>h>>w;
    vector<string>a(h);
    rep(i,0,h){
        cin>>a[i];        
    }
    vector<vector<ll>>dp(h,vector<ll>(w,0));
    dp[0][0]=1;
    rep(i,0,h){
        rep(j,0,w){
            if(i==0&&j==0){
                continue;
            }
            if(a[i][j]=='.'){
                if(i>0){
                    dp[i][j]=(dp[i-1][j]+dp[i][j])%mod;
                }
                if(j>0){
                    dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
                }
            }
        }
    }
    cout<<dp[h-1][w-1]<<endl;
    

    
    
}


Measured memory_bytes: 9216
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  string s(a,'0'+b);
  string t(b,'0'+a);
  if(a<=b){
    cout<<t<<endl;
  }
  else{
    cout<<s<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Scanner;

class Program
{
    static void Main() => new Program().Solve();

    public void Solve()
    {
        int h = ReadInt();
        int w = ReadInt();
        var s = Read(h).ToArray();
        var dp = new int[h, w];
        dp[0, 0] = s[0][0] == '.' ? 0 : 1;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (i == 0 && j == 0) continue;
                int min = int.MaxValue;
                if (i > 0)
                    min = Math.Min(min, dp[i - 1, j] + (s[i][j] == '.' || s[i - 1][j] == '#' ? 0 : 1));
                if (j > 0)
                    min = Math.Min(min, dp[i, j - 1] + (s[i][j] == '.' || s[i][j - 1] == '#' ? 0 : 1));
                dp[i, j] = min;
            }
        }
        Console.WriteLine(dp[h - 1, w - 1]);
    }
}

static class Scanner
{
    static Queue<string> que = new Queue<string>();
    public static string Read() { if (!que.Any()) foreach (var s in Console.ReadLine().Split()) que.Enqueue(s); return que.Dequeue(); }
    public static int ReadInt() => int.Parse(Read());
    public static long ReadLong() => long.Parse(Read());
    public static double ReadDouble() => double.Parse(Read());
    public static decimal ReadDecimal() => decimal.Parse(Read());
    public static IEnumerable<string> Read(long n) { for (long i = 0; i < n; i++) yield return Read(); }
    public static IEnumerable<int> ReadInt(long n) => Read(n).Select(int.Parse);
    public static IEnumerable<long> ReadLong(long n) => Read(n).Select(long.Parse);
    public static IEnumerable<double> ReadDouble(long n) => Read(n).Select(double.Parse);
    public static IEnumerable<decimal> ReadDecimal(long n) => Read(n).Select(decimal.Parse);
}

Measured memory_bytes: 28388
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
fn main() {
    let r: u32 = read();
    let g: u32 = read();
    let b: u32 = read();
    let ans = if ( r * 100 + g * 10 + b ) % 4 == 0 { "YES" } else { "NO" };
    println!("{}", ans);
}


Measured memory_bytes: 4352
while 1:
    n,m=map(int,input().split())
    a=[]
    if n==0:break
    for _ in range(n):
        d,p=map(int,input().split())
        a.append([p,d])
    a.sort(reverse=1)
    b=0
    for p,d in a:
        if d<=m:
            m-=d
        else:
            b+=p*(d-m)
            m=0
    print(b)

Measured memory_bytes: 8900
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

int main() {
  i64 W, R, c, r;
  while(cin >> R >> W >> c >> r, W) {
    i64 want = W * c;
    i64 a = max(0ll, want - R);
    cout << a / r + !!(a % r) << endl;
  }
}



Measured memory_bytes: 3016
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using T3 = tuple<int, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
int c[505050]; // 石情報.
int q[505050]; // クエリ回答.
// handmade04, random06 で, WA版 となったため, ロジック変更.
// int b[505050]; // 良い玉.
map<int, int> b; // 良い玉.

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q, x, y;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%d", &c[i]);
    vector<T3> v;
    rep(i, Q){
        scanf("%d %d", &x, &y);
        x--, y--;
        v.emplace_back(x, y, i);
    }
    
    // 2. sort.
    // https://www.geeksforgeeks.org/sorting-vector-tuple-c-ascending-order/
    sort(all(v), [](const T3 &a, const T3 &b){
        return get<1>(a) < get<1>(b);
    });
    // for(auto &p : v) printf("l=%d r=%d i=%d\n", get<0>(p), get<1>(p), get<2>(p));
    
    // 3. クエリの回答を作成.
    BIT<int> ft(N + 1);
    int bef = 0, cur = 0;
    assert(v.size() == Q);
    rep(j, Q){
        int l = get<0>(v[j]);
        int r = get<1>(v[j]);
        int i = get<2>(v[j]);
        
        // 今回分更新.
        cur = r;
        
        // 良い玉の集合を更新.
        repx(k, bef, cur + 1){
            // 前回以前に, 良い玉をチェック済か否か.
            if(b.count(c[k])){
                int at = b[c[k]];
                if(at < k){
                    // 良い玉の場所を解除.
                    int tSum = ft.sum(at, at + 1);
                    assert(tSum <= 1);
                    if(tSum) ft.add(at, -1);
                    
                    // 良い玉の出現位置を更新.
                    b[c[k]] = k;
                    
                    // 良い玉の場所を更新.
                    ft.add(b[c[k]], 1);
                    // printf("k=%d tSum=%d c[k]=%d b=%d at=%d\n", k, tSum, c[k], b[c[k]], at);
                    // puts("----------");
                    // rep(m, N + 1) printf("%d ", ft.sum(m, m + 1));
                    // puts("\n----------");
                }
            }else{
                // 良い玉の出現位置を更新.
                b[c[k]] = k;
                
                // 良い玉の場所を更新.
                ft.add(b[c[k]], 1);
            }
        }
        
        // クエリ回答.
        q[i] = ft.sum(l, r + 1);
        
        // 前回分更新.
        bef = cur;
        
    }
    
    // 4. 出力.
    rep(i, Q) printf("%d\n", q[i]);
    return 0;
    
}

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

int main() {
    int a[5], k;
    rep(i, 5) cin >> a[i];
    cin >> k;

    bool ok = true;
    rep(i, 4) {
        for (int j = i+1; j < 5; j++) {
            if (abs(a[i] - a[j]) > k) ok = false;
        }
    }

    if (ok) cout << "Yay!" << endl;
    else cout << ":(" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fv               first
#define sv               second
#define ll               long long
#define pll              pair<ll,ll>
#define pii              pair<int,int>
#define READ(x)          freopen(x,"r",stdin)
#define WRITE(x)         freopen(x,"w",stdout)
#define isWorking()      cout<<"Wroking"<<endl
#define all(x)           (x).begin(),(x).end()
#define allr(x)          (x).rbegin(),(x).rend()
#define fill(x,y)        memset(x, y, sizeof(x))
#define PRINT(ok)        cout<<(ok? "YES":"NO")<<endl
#define DoublePrint(x,a) cout<<fixed<<setprecision(x)<<a<<endl
#define Fast_Input       ios_base :: sync_with_stdio(0),cin.tie(0);

const ll mod = 1e9+7, INF = 1e8, mx = 1e5+5, mn = 100;
int testCase=1,cas=0;

int main() {
    Fast_Input

    while(testCase--){
        int n; cin >> n;
        map <string, int> F;
        while(n--){
            string str; cin>>str;
            F[str]++;
        }
        cout << "AC x " <<F["AC"]<<endl;
        cout << "WA x " <<F["WA"]<<endl;
        cout << "TLE x " <<F["TLE"]<<endl;
        cout << "RE x " <<F["RE"]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define PI 3.14159265359
#define sz(c) (int)c.size()
#define len(c) (int)c.length()
#define hcf(a, b) __gcd(a, b)
#define all(c) c.begin(), c.end()
#define vint vector<int>
#define vll vector<ll>
#define vpint vector<pair<int, int>>
#define vpll vector<pair<ll, ll>>
#define tr(con, it) \
    for (auto it = con.begin(); it != con.end(); it++)
#define fr(it, a, b) \
    for (int it = (a); it < (b); it++)
#define present(con, ele) (con.find(ele) != con.end())
#define cpresent(con, ele) (find(all(con), ele) != con.end())
#define maximum(a, b, c) (a > b ? (a > c ? a : c) : (b > c ? b : c))
#define minimum(a, b, c) (a < b ? (a < c ? a : c) : (b < c ? b : c))
typedef long long ll;
typedef long double lf;
typedef unsigned long long lu;
const ll mod = 1e9 + 7;
// symmetry
bool compare(pair<int, int> &p1, pair<int, int> &p2)
{
    return (p1.F - p1.S) < (p2.F - p2.S);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, op = 0, clos = 0, flag = 1;
    cin >> n;
    vpint a;
    fr(i, 0, n)
    {
        int op2 = 0, clos2 = 0;
        string s;
        cin >> s;
        fr(j, 0, len(s))
        {
            if (s[j] == ')')
            {
                op2 > 0 ? op2-- : clos2++;
            }
            else
            {
                op2++;
            }
        }
        if (op2 && clos2)
        {
            a.pb({clos2, op2});
        }
        else
        {
            op += op2;
            clos += clos2;
        }
    }
    sort(all(a), compare);
    fr(i, 0, sz(a))
    {
        op -= a[i].F;
        if (op < 0)
        {
            flag = 0;
        }
        op += a[i].S;
    }
    op -= clos;
    if (flag == 1 && op == 0)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
    return 0;
}

Measured memory_bytes: 5312
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
 
int h, w, ans;
int castle[1001][1001], times[1001][1001];
int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
char beach[1001][1001];
 
int main(){
    scanf("%d%d", &h, &w);
    for(int i = 0; i < h; i++){
        scanf("%s", &beach[i]);
    }
 
    queue<P> Q;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(beach[i][j] == '.'){
                Q.push(P(i, j));
            } else{
                castle[i][j] = (int)beach[i][j] - '0';
            }
        }
    }
 
    while(Q.size()){
        P p = Q.front();
        Q.pop();
        ans = max(ans, times[p.first][p.second]);
 
        for(int i = 0; i < 8; i++){
            int y = p.first + dy[i], x = p.second + dx[i];
            if(y < 0 || y >= h || x < 0 || x >= w){
                continue;
            }
 
            castle[y][x]--;
            if(castle[y][x] == 0){
                Q.push(P(y, x));
                times[y][x] = times[p.first][p.second] + 1;
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}

Measured memory_bytes: 10040
def f():
    for i in t:
        for j in h:
            if (i-j)*2==sumt-sumh:
                print(i,j)
                return
    print(-1)
            

while True:
    n,m=map(int,input().split())
    if n==0:
        break
    t=[int(input()) for i in range(n)]
    h=[int(input()) for j in range(m)]
    t.sort()
    h.sort()
    sumt=sum(t)
    sumh=sum(h)
    f()


Measured memory_bytes: 5604
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

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

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

      if (x==1)     cout << 0 << endl;
  else     cout << 1 << endl;
    return 0;
}

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

#define ll long long

int main(){

    int N,M;
    int i,j,k,l;
    int a,b,c,d;
    int count=0,count_n=0,count_m=0;
    bool flag = false;
    int ans=0;

    cin >> a >> b >> c >> d;    

    if((fabs(a-b) <= d && fabs(c-b) <= d ) || fabs(a-c) <= d)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;

}

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

long long x, y, t = 0;
const long long M = 1000000007;
const long long N = 1000000005;

int main()
{	

	cin >> x >> y;

	if (x <= y * 2 && y <= x * 2) {
		if ((x * 2 - y) % 3 == 0 && (y * 2 - x) % 3 == 0) {
			long long a = (x * 2 - y) / 3, b = (y * 2 - x) / 3;

			t = 1;

			for (long long i = 0; i < a; i++)
				t = (t * (a + b - i)) % M;

			for (long long i = 1; i <= a; i++) {
				long long c[40];
				long long d = i;

				c[0] = i;

				for (int j = 1; (1ull << j) < N; j++) {
					c[j] = c[j - 1] * c[j - 1] % M;

					if (N & (1ull << j))
						d = (d * c[j]) % M;
				}

				t = t * d % M;
			}
		}
	}

	cout << t << endl;

	return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> s(n);

    rep(i, n) cin >> s[i];

    rep(i, n-1){
        if(s[i]<=s[i+1])continue;
        else {
            if(s[i+1] - s[i] == -1){
                s[i+1]++;
                continue;
            }else{
                puts("No");
                return 0;
            }
        }
    }

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


Measured memory_bytes: 640
import java.util.Scanner;

class Main {

  static int sqr(int x) {
    return x * x;
  }

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    int n = stdIn.nextInt();
    
    int[] x = new int[8];
    int[] y = new int[8];
    
    for (int i = 0; i < n; i++) {
      x[i] = stdIn.nextInt();
      y[i] = stdIn.nextInt();
    }
    
    double sum = 0;
    for (int i = 0; i < n-1; i++) {
      for(int j = i+1; j < n; j++) {
        sum += Math.sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
      }
    }
    
    System.out.println(sum * 2 / n);
  }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll N; cin >> N;
    int ans = 0;
    FOR(i, 2, 1000000) {
        int cur = 0;
        while (N % i == 0) {
            cur++;
            N /= i;
        }
        FOR(j, 1, 10000) {
            if (cur < j) break;
            ans++; cur -= j;
        }
    }
    if (N > 1) ans++;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3644
h,w=map(int, input().split())
a=[list(map(int, input().split())) for _ in range(h)]

cnt=0
ans=[]
for i in range(h):
    for j in range(w):
        if a[i][j]%2==1:
            if i==h-1 and j==w-1:
                break
            cnt+=1
            if j!=w-1:
                ans.append([i+1,j+1,i+1,j+2])
                a[i][j]-=1
                a[i][j+1]+=1
            else:
                ans.append([i+1,j+1,i+2,j+1])
                a[i][j]-=1
                a[i+1][j]+=1

print(cnt)
for ans_i in ans:
    print(*ans_i)



Measured memory_bytes: 32400
///****In the name of ALLAH, most Gracious, most Compassionate****//

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

#define ALL(a) a.begin(), a.end()
#define FastIO ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define IN freopen("input.txt","r+",stdin)
#define OUT freopen("output.txt","w+",stdout)

#define DBG(a) cerr<< "line "<<__LINE__ <<" : "<< #a <<" --> "<<(a)<<endl
#define NL cout<<endl

template < class T1,class T2>
ostream &operator <<(ostream &os,const pair < T1,T2 > &p)
{
    os<<"{"<<p.first<<","<<p.second<<"}";
    return os;
}

int dx[] = { 2, 3 ,5};

ll a[3] ;
ll d;

map<ll,ll> save;

ll dp(ll n)
{
    if(n==0) return 0;
    ll & ret = save[n];
    if(ret!=0)
        return ret;
    else
    {
        ret = 1e18;
        if(n<1e18 / d)
            ret = min(ret ,n * d);

        for(int i=0;i<3;i++)
        {
            ll k= dx[i];
            {
                ll y = n/k;
                ll cost =  abs(n-y*k) * d + a[i];
//                ll cost = min((n-y) * d , abs(n-y*k) * d + a[i]);
                ret = min(ret , cost + dp(y));
            }
            {
                ll y = (n+k-1)/k;
                ll cost =   abs(n-y*k) * d + a[i];
//                ll cost = min((n-y) * d , abs(n-y*k) * d + a[i]);
                ret = min(ret , cost + dp(y));
            }

        }

    }
    return ret;
}

int32_t main()
{
    FastIO;
    int t;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        for(int i=0;i<3;i++)
            cin>>a[i];
        save.clear();
        cin>>d;
        cout<<dp(n)<<"\n";
    }
}


Measured memory_bytes: 4368
#include<iostream>
#include<set>

using namespace std;

int main(){

    int size,query;
    set<int> ans;
    cin >> size;
    for (int i=0;i<size;i++){
        cin >> query;
        if (ans.find(query) == ans.end()){
            ans.insert(query);
        }
        else{
            ans.erase(query);
        }

    }
    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll r,d,x;
  cin >> r >> d >> x;
  rep(i,10){
    x=r*x-d;
    cout << x << endl;
  }
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    const N = lines[0]-0;
    const list = lines[1].split(" ").map(v=>v-0).sort((a,b)=>b-a);
    let ans = 0;
    for(let i=1;i<N*2;i+=2){
        ans += list[i];
    }
    console.log(ans);
});


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

void solve(long long A, long long B)
{
    cout << max(A + B, max(A - B, A * B)) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
# https://atcoder.jp/contests/abc046/tasks/arc062_a
# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

N = int(input().split()[0])
ta_list = []

for _ in range(N):
    t, a = list(map(int, input().split()))
    ta_list.append((t, a))

# 最初のやつ
t, a = ta_list[0]
total_p = t + a
now_t, now_a = t, a

for t, a in ta_list[1:]:
    w_t, w_a = t, a

    c = max(now_t // w_t, now_a // w_a)
    w_t *= c
    w_a *= c

    while w_t < now_t or w_a < now_a:
        w_t += t
        w_a += a

    now_t = w_t
    now_a = w_a
    total_p = now_t + now_a

print(total_p)


Measured memory_bytes: 39408
import java.util.*;
import java.util.Collections;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    HashSet<String> list = new HashSet<String>();
    for (int i = 0; i < N; i++) {
      list.add(sc.next());
    }
    if (list.size() == 3) {
      System.out.println("Three");
    } else {
      System.out.println("Four");
    }
  }
}


Measured memory_bytes: 22996
#include<stdio.h>
int main()
{
	int d;
	scanf("%d",&d);
	if(d==25){
		printf("Christmas\n");
	}
	if(d==24){
		printf("Christmas Eve\n");
	}
	if(d==23){
		printf("Christmas Eve Eve\n");
	}
	if(d==22){
		printf("Christmas Eve Eve Eve\n");
	}
	return 0;
}


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

int main()
{
	char a,b,c,d,e,f;
	scanf("%c%c%c%c%c%c",&a,&b,&c,&d,&e,&f);
	if(c==d)
	{
		if(e==f)
		{
			cout << "Yes" << endl;
		}else cout << "No" << endl;
	}else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
X, Y, Z, K = map(int, input().split())
a_cakes = list(map(int, input().split()))
b_cakes = list(map(int, input().split()))
c_cakes = list(map(int, input().split()))
a_b_cakes = []
for a in a_cakes:
  for b in b_cakes:
    a_b_cakes.append(a+b)
a_b_cakes.sort(reverse=True)
a_b_c_cakes = []
for a_b in a_b_cakes[:K]:
  for c in c_cakes:
    a_b_c_cakes.append(a_b+c)
a_b_c_cakes.sort(reverse=True)
for ans in a_b_c_cakes[:K]:
  print(ans)


Measured memory_bytes: 151644
# -*- coding: utf-8 -*-

import itertools

n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))

a = list(range(1,n+1,1))
count = 1

res1 = 0
res2 = 0

temp = []

for i in itertools.permutations(a):
    for j in range(n):
        temp.append(i[j])
    if temp == p and (res1 == 0):
        res1 = count
    if temp == q and (res2 == 0):
        res2 = count
    count += 1
    temp = []

print(abs(res1-res2))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> list;
    for (int i = 0; i < N; i++) {
        long long t;
        cin >> t;
        list.push_back(t);
    }

    long long answer = 1;
    
    for (auto t : list) {
        long long m = max(answer, t);
        long long n = min(answer, t);
        while (n != 0) {
            long long tmp = n;
            n = m % n;
            m = tmp;
        }
        answer = answer / m * t;
    }

    cout << answer << endl;
    
    return 0;
}


Measured memory_bytes: 256