akhauriyash/Code-Regression huggingface dataset:
//ALDS1_12_B:Single Source Shortest Path I
//C++
#include <iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;
int n,M[MAX][MAX];
void dijkstra(){
    int minv;
    int d[MAX],color[MAX];
    for(int i=0;i<n;i++){
        d[i]=INFTY;
        color[i]=WHITE;
    }
    d[0]=0;
    color[0]=GRAY;
    while(1){
        minv=INFTY;
        int u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i]&&color[i]!=BLACK){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1)break;
        color[u]=BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK&&M[u][v]!=INFTY){
                if(d[v]>d[u]+M[u][v]){
                    d[v]=d[u]+M[u][v];
                    color[v]=GRAY;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            M[i][j]=INFTY;
        }
    }
    int k,c,u,v;
    for(int i=0;i<n;i++){
        cin>>u>>k;
        for(int j=0;j<k;j++){
            cin>>v>>c;
            M[u][v]=c;
        }
    }
    dijkstra();
    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)


i64 C;
int N;
vector<i64> x;
vector<i64> v;

vector<i64> xs;
vector<i64> vs;

i64 ans = 0;

int main(){
    cin >> N >> C;
    x.resize(N);
    v.resize(N);

    rep(i,0,N - 1) cin >> x[i] >> v[i];

    using P =  pair<i64,int>;



    {
        i64 ene = 0;
        rep(i,0,N - 1){
            ene += v[i];
            ans = max(ans,ene - x[i]);
        }
    }
    {
        i64 ene = 0;
        for(int i = N - 1;i >= 0;i--){
            ene += v[i];
            ans = max(ans,ene - (C - x[i]));
        }
    }
    {
        vector<i64> left(N,0);
        vector<i64> right(N,0);

        //left;
        i64 ene = 0;
        rep(i,0,N - 1){
            ene += v[i];
            left[i] = ene - x[i] * 2;
            if(i > 0){
                left[i] = max(left[i - 1] , left[i]);
            }
        }
        ene =0;
        for(int i = N - 1;i >= 0;i--){
            ene += v[i];
            right[i] = ene - (C - x[i]);
            if(i != N - 1){
                right[i] = max(right[i + 1],right[i]);
            }
        }

        for(int i = 0;i < N - 1;i++){
            ans = max(ans , left[i] + right[i + 1]);
        }
    }
    {
        vector<i64> left(N,0);
        vector<i64> right(N,0);

        //left;
        i64 ene = 0;
        rep(i,0,N - 1){
            ene += v[i];
            left[i] = ene - x[i];
            if(i > 0){
                left[i] = max(left[i - 1] , left[i]);
            }
        }
        ene = 0;
        for(int i = N - 1;i >= 0;i--){
            ene += v[i];
            right[i] = ene - (C - x[i]) * 2;
            if(i != N - 1){
                right[i] = max(right[i + 1],right[i]);
            }
        }

        for(int i = 0;i < N - 1;i++){
            ans = max(ans , left[i] + right[i + 1]);
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3424
#include<stdio.h>
int main(void)
{
	int a,b;

	scanf("%d",&a);
	scanf("%d",&b);

	if(a<b){
		printf("a < b\n");
	}else if(a>b){
		printf("a > b\n");
	}else{
		printf("a == b\n");
	}

	return 0;
}


Measured memory_bytes: 2140
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using Cost = LL;
const Cost INF = 1e18;

class dijkstra {
	struct edge {
		int to;
		Cost cost;
		edge(int to_, Cost cost_) : to(to_), cost(cost_) {}
	};
	bool isdir;
	vector<vector<edge> > G;
	int V;
public:
	dijkstra(int V_, bool isdir_ = true) : isdir(isdir_), V(V_), G(V_) {}
	void add(int a, int b, Cost c) {
		G[a].emplace_back(b, c);
		if (!isdir) G[b].emplace_back(a, c);
	}
	vector<Cost> calc(int s) {
		vector<Cost> d(V, INF);
		using pci = pair<Cost, int>;
		priority_queue<pci, vector<pci>, greater<pci> > q;
		q.emplace(0, s);
		while (!q.empty()) {
			auto p = q.top(); q.pop();
			int v = p.second;
			if (d[v] < p.first) continue;
			d[v] = p.first;
			for (auto& e : G[v]) {
				if (d[e.to] > d[v] + e.cost) {
					d[e.to] = d[v] + e.cost;
					q.emplace(d[e.to], e.to);
				}
			}
		}
		return d;
	}
};


int main() {
  LL n,m,s,t;
  cin>>n>>m>>s>>t;
  dijkstra yen(n,false);
  dijkstra snuuk(n,false);
  s--;t--;
  REP(i,m){
    LL u,v,a,b;
    cin>>u>>v>>a>>b;
    u--;v--;
    yen.add(u,v,a);
    snuuk.add(u,v,b);
  }

  vector<Cost> yen_cost=yen.calc(s);
  vector<Cost> snuuk_cost=snuuk.calc(t);

  vector<Cost> ans(n,0);
  ans[n-1]=yen_cost[n-1]+snuuk_cost[n-1];
  for(int i=n-2;i>=0;--i){
    ans[i]=min(yen_cost[i]+snuuk_cost[i],ans[i+1]);
  }

  REP(i,n){
    cout<<1000000000000000LL-ans[i]<<endl;
  }
}


Measured memory_bytes: 19744
#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int N=3000009,mod=1e9+7;
	int f[N],iv[N];
int pw(int a,int t=mod-2){
	int x=1;
	while(t){
		if(t&1)x=x*a%mod;
		a=a*a%mod,t>>=1;
	}
	return x;
}
int C(int n,int r){
	int x=(((f[n]*iv[r])%mod)*iv[n-r])%mod;
	return x;
}
int32_t main(){
	if(fopen("input.txt", "r"))
		freopen("input.txt", "r", stdin),
		freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	f[0]=1,iv[0]=1;
	for(int i=1;i<N;i++){
		f[i]=i*f[i-1]%mod;
		iv[i]=pw(f[i]);
	}
	int r1,r2,c1,c2,sum=0;
	cin >> r1 >> c1 >> r2 >> c2;
	for(int i=c1;i<=c2;i++)
		sum=(sum+(C(r2+i+1,r2)+mod-C(r1+i,r1-1)))%mod;
	cout << sum;

}

Measured memory_bytes: 47104
#include<stdio.h>
int main(){
  int W;
  int H;
  int x;
  int y;
  int r;
  scanf("%d%d%d%d%d", &W,&H,&x,&y,&r);
  if(x - r < 0){
    printf("No\n");
  }
  else if(x + r > W){
    printf("No\n");
  }
  else if(y - r < 0){
    printf("No\n");
  }
  else if(y + r > H){
    printf("No\n");
  }
  else{
    printf("Yes\n");
  }
}
  

  



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


int main() {
	int N;
	cin >> N;
	int* number = new int [N];
	int sum = 0;
	for (int i = 0; i < N; ++i) {
		cin >> number[i];
		sum += number[i];
	}
	int avg = sum / 2;
	//f[i][v] = f[i - 1][v] || f[i - 1][v - ai]
	bitset<4000001> f;
	f.reset();
	f[0] = 1;
	for (int i = 0; i < N; ++i) {
		f = f | (f << number[i]);
	}
	for (int v = avg; v >= 0; --v) {
		if (f[v] == 1) {
			cout << (sum - v) << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 2176
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll n,m;



//スコアが一定のとき、何人握手するかを返す
ll solve(ll score,vector<ll> &a){
  ll nin=0;
  ll l;
  REP(i,n){
    l=score-a[i];
    auto Iter2 = lower_bound(a.begin(),a.end(), l);//1,2,3・・のときl=3なら2が返る
    int k=(Iter2-a.begin());
    nin+=n-(ll)k;
  }
  return nin;
}


int main(){
  ll ans=0;
  cin >> n >> m;
  vi a(n);
  vi b(n+1);
  REP(i,n) cin>>a[i];
  sort(a.begin(), a.end());
  REP(i,n){
    b[i+1]=b[i]+a[i];
  }


  //2分岐探索
  ll ok=100000LL*100000LL;//解が存在する値
  ll ng=-1;//解が存在しない値
  while(abs(ok-ng)>1)
  {
    ll mid=(ok+ng)/2;
    if (solve(mid,a)<m)
    {
      ok=mid;
    }
    else
    {
      ng=mid;
    }
  }



  ok-=1;
  ll l,score=ok;
  ll nin=0;
  REP(i,n){
    l=score-a[i];
    auto Iter2 = lower_bound(a.begin(),a.end(), l);//1,2,3・・のときl=3なら2が返る
    int k=(Iter2-a.begin());
    ans+=(b[n]-b[k])+a[i]*(n-k);
    nin+=n-(ll)k;
  }

  nin-=m;
  ans-=nin*ok;


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

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

int N;
int main(){
    cin >> N;
    vector<int> W(N);
    rep(i,N) cin >> W[i];
    int ans = 1e9;
    rep(i,N){
        int sum1 = 0,sum2 = 0;
        repi(j,0,i) sum1 += W[j];
        repi(j,i+1,N-1) sum2 += W[j];
        ans = min(ans,abs(sum1-sum2));
    }
    pr(ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int N;
vector<int> S[10000];

int main()
{
	cin >> N;
	int u=-1; //|Si| 集合数はu+1
	rep(i,1,10000){
		if(N == i*(i+1)/2){
			u = i;
			break;
		}
	}
	if(u==-1){
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	cout << u+1 << endl;
	int c = 1;
	rep(i,0,u){
		int t = u-i;
		rep(j,0,t){
			S[i].push_back(c);
			S[i+j+1].push_back(c);
			c++;
		}
	}
	rep(i,0,u+1){
		cout << u;
		rep(j,0,S[i].size()){
			cout << " ";
			cout << S[i][j];
		}
		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<cmath>
#include<string>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n, x;
    cin>>n>>x;
    int a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    sort(a, a+n);
    int count=0;
    for(int i=0; i<n; i++)
    {
        x-=a[i];
        if(x>=0)
        {
            count++;
        }
        else
        {
            break;
        }
    }
    if(x>0) count--;
    cout<<count<<endl;
	return 0;
}


Measured memory_bytes: 256
object Main extends App {
 
  val n = scala.io.StdIn.readInt
  val k = scala.io.StdIn.readInt
  val x = scala.io.StdIn.readInt
  val y = scala.io.StdIn.readInt
 
  if (n > k) {
    println(k * x + (n - k) * y)
  } else {
    println(n * x)
  }
 
}

Measured memory_bytes: 21328
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;

int main(){
	int a , b ; 
	cin >> a >> b ;     
	if ( a >= 13 ){
		cout << b << endl;
	}
	else if ( a >= 6 && a <= 12 ){
		cout << b/2 << endl;
	}
	else {
		cout << 0 << endl;
	}
    return 0 ;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int INF = (int)1e9 + 7;

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    int mi = INF;
    for (int x = -100; x <= 100; x++) {
        int sum = 0;
        for (int i = 0; i < N; i++) sum += (x - a[i]) * (x - a[i]);
        mi = min(mi, sum);
    }
    cout << mi << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n;
ll a[N], p[62];
bool chk[62];

void insert(ll x) {
    for(int i = 60; i >= 0; i--) {
        if(chk[i]) continue;
        if(x >> i & 1) {
            if(!p[i]) {
                p[i] = x;
                break;
            }
            x ^= p[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    ll all = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], all ^= a[i];
    for(int i = 0; i <= 60; i++) {
        if(all >> i & 1) chk[i] = 1;
    }
    for(int i = 1; i <= n; i++) insert(a[i]);
    ll ans = 0;
    for(int i = 0; i <= 60; i++) {
        if(chk[i])
        for(int j = 0; j <= 60; j++) {
            if(p[j] >> i & 1) {
                p[j] ^= (1ll << i);
            }
        }
    }
    for(int i = 60; i >= 0; i--) {
        if((p[i] ^ ans) > ans) ans = p[i] ^ ans;
    }
    cout << ans + (ans ^ all);
    return 0;
}


Measured memory_bytes: 1024
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	k := nextInt()
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		tmp := nextInt()
		m[tmp]++
	}

	if len(m) <= k {
		fmt.Println(0)
	} else {
		var count []int
		for _, v := range m {
			count = append(count, v)
		}
		sort.Ints(count)

		num := len(m)
		ans := 0
		for _, v := range count {
			ans += v
			num--
			if num <= k {
				fmt.Println(ans)
				break
			}
		}
	}
}

func next() string {
	scanner.Scan()
	return scanner.Text()
}
func nextInt() int {
	i, err := strconv.Atoi(next())
	if err != nil {
		fmt.Println(err)
	}
	return i
}


Measured memory_bytes: 14848
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
signed main(){
  ll n,m,tmp0,tmp1,ans=0,val,tmp;
  cin >> n >> m;
  ll x[n],lv;
  map<ll,ll> mp[m],t_mp;
  ll cnt[m];
  fill(cnt,cnt+m,0);
  for(int i=0;i<n;i++){
    cin >> x[i];
    mp[x[i]%m][x[i]]++;
    cnt[x[i]%m]++;
  }
  for(int i=0;i<=m/2;i++){
    if(i!=0&&!(m%2==0&&i==m/2)){
      tmp0 = cnt[i];
      tmp1 = cnt[m-i];
      if(tmp0<tmp1){
        val = tmp0;
        t_mp = mp[m-i];
        lv = tmp1-tmp0;
      }else{
        val = tmp1;
        t_mp = mp[i];
        lv = tmp0-tmp1;
      }
      for(auto j:t_mp){
        if(lv<2){
          break;
        }
        if(j.second>=2){
          tmp = min(j.second,lv);
          val += tmp/2;
          lv -= (tmp/2)*2;
        }
      }
      ans += val;
//      cout << i<<" "<<val<<endl;
    }else{
      ans += cnt[i]/2;
    }
  }
  cout << ans <<endl;
}


Measured memory_bytes: 12800
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Q = sc.nextInt();
		int[] cumulativeSum = new int[999999];
		for (int i = 1; i < cumulativeSum.length; i++) {
			if (isPrime(i) && isPrime((i + 1) / 2)) {
				cumulativeSum[i]++;
			}
			cumulativeSum[i] += cumulativeSum[i - 1];
		}
		StringBuilder ans = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			int l = sc.nextInt();
			int r = sc.nextInt();
			int count = cumulativeSum[r] - cumulativeSum[l - 1];
			ans.append(count);
			if (i < Q - 1) {
				ans.append("\n");
			}
		}
		System.out.println(ans.toString());
	}

	//素数判定
	//計算量O(√N)
	public static boolean isPrime(long n) {
		if (n == 1) {
			return false;
		}
		for (long i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

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

#define REP(i, a, b) for(int i = a; i <= b; i ++)
#define REPG(i, x) for(int i = head[x]; i; i = g[i].nxt)

#define clr(x, y) memset(x, y, sizeof(x));

using namespace std;

typedef long long LL;
typedef double LF;

LL Max(LL a, LL b){return a > b ? a : b;}
LL Min(LL a, LL b){return a < b ? a : b;}
LL abs(LL x){return x > 0 ? x : -x;}

inline int read(){
	int r = 0, z = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') z = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){r = r * 10 + ch - '0'; ch = getchar();}
	return r * z;
}

void work(){
	int a = read(), b = read(), c = read(), x = read(), y = read();
	int ans1 = max(x * 2, y * 2) * c, ans2 = min(x * 2, y * 2) * c + (x < y ? (y - x) * b : (x - y) * a), ans3 = a * x + b * y;
	printf("%d\n", min(ans1, min(ans2, ans3)));
}

int main(){
	work();
	return 0;
}


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

typedef long lint;
typedef long long llint;
typedef pair<int, int> pint;
typedef pair<long long, long long> pllint;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const llint INF = 1<<21;
// static const llint MOD = 1e9 + 7;

bool compPair(const pint& arg1, const pint& arg2) { return arg1.first > arg2.first; }
template<class T> void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> void chmin(T& a, T b) { if (a > b) { a = b; } }

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

    vector<int> a(n);
    for(int in=0;in<n;in++) {
        cin >> a.at(in);
        if(a.at(in)%2==1) {
            cout << 0 << endl;
            return 0;
        }
    }

    int ans = 0;
    bool flg = true;
    while(flg) {
        for(int in=0;in<n;in++) {
            a.at(in) /= 2;
            if(a.at(in)%2==1) {
                flg=false; 
                break;
            }
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>



int main(void){
    int a,b,c;
    
    
    
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);

    int max = a;
    if(b > max) max = b;
    if(c > max) max = c;


    printf("%d\n",a+b+c-max);
  
    return 0;

}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<malloc.h>
#include<math.h>
#include<x86intrin.h>


int my_gets(char *buf,int nBuf,FILE *fp){
    int ch;

    while(--nBuf >0){
        ch=getc(fp);
        if(ch==EOF || ch=='\n')
            break;
        *(buf++)=(char)ch;
    }
    *(buf)='\0';

    return nBuf;
}

void InputIntAry(int *a,int nDigit,int N){      //nDigitは想定される最大桁数
    char *buf,*ptr;

    buf=(char*)malloc( (N*(nDigit+2)) * sizeof(char) );
    my_gets(buf,N*(nDigit+2),stdin);

    ptr=strtok(buf," ");
    while(ptr!=NULL && N-->0){
        *(a++)=atoi(ptr);
        ptr=strtok(NULL," ");
    }
    free(buf);
}

int CmpInt(const void *a, const void *b){        //b-aを返す(qsortなら4321)
    return *((int*)b)- *((int*)a);
}

typedef struct{
    int A,B;
} JobInfo_t;

int CmpJob(const void *p1, const void *p2){
    JobInfo_t Job1=*(JobInfo_t*)p1, Job2=*(JobInfo_t*)p2;

    if(Job1.A == Job2.A){
        return Job2.B - Job1.B;
    }
    else{
        return Job1.A - Job2.A;
    }
}

#define MAX_OF(a,b) (((a)>(b))?(a):(b))

int main(){
    int K,X;

    scanf("%d %d%*c",&K,&X);
    for(int i=X-(K-1); i<=X+(K-1); i++){
        printf("%d ",i);
    }
    puts("");
}

/*int main(){
    int N,M;
    JobInfo_t Job[100000];

    scanf("%d %d%*c", &N, &M);
    for(int i=0;i<N;i++){
        scanf("%d %d%*c", &(Job[i].A), &(Job[i].B));
    }
    qsort(Job, N, sizeof(JobInfo_t), CmpJob);

    int allowed=0,max;
    for(int i=0;i<N;i++){
        
    }
    return 0;
} */

Measured memory_bytes: 128
n=97,t,s;
int c(int i,int j,int k){printf("< %d %d %d ",i,j,k);}
int a(int i,int j,int k){printf("+ %d %d %d ",i,j,k);}
int b(int i,int j,int k){a(i,j,98);c(n,98,99);a(k,99,k);}
int m(int i,int j,int k){for(t=0;t<59;++t){if(t)a(k,k,k);for(s=0;s<=t;++s)if(s<30&&s+30>t)b(i+t-s,j+s,k);}}
int d(int x,int i,int j){for(t=0;t<30;++t){if(t)a(j+t-1,j+t-1,j+t);a(j+t,n,j+t);for(s=t;s<29;++s)a(j+s,j+s,j+s+1);c(j+29,x,i+t);a(j+t-1,j+t-1,j+t);a(j+t,i+t,j+t);}}
main(){puts("3930");a(0,1,n);c(2,n,n);a(0,n,3);a(1,n,4);d(3,5,36);d(4,36,67);m(5,36,2);}

Measured memory_bytes: 1584
#include<bits/stdc++.h>
using namespace std;
#define sq(a) (a)*(a)
long double PI=3.14159265358979;
int main()
{
    int a,b,h,m;
    cin>>a>>b>>h>>m;
    long double p,q,r,s,tt,uu,vv,ww,angle,ans;
    p=h*1.00*30;
    q=(m/60.00)*30.00;
    r=p+q;
    s=m*6.00;
    if(r>=s)
    {
        tt=((r-s)*PI)/180.00;
        angle=cos(tt);
        uu=sq(a)*1.00+sq(b)*1.00-2.00*a*b*angle;
        vv=sqrtl(uu);
        cout<<setprecision(15)<<vv<<endl;
        return 0;
    }
    else
    {
        tt=((s-r)*PI)/180.00;
        angle=cos(tt);
        uu=sq(a)*1.00+sq(b)*1.00-2.00*a*b*angle;
        vv=sqrtl(uu);
        cout<<setprecision(15)<<vv<<endl;
        return 0;
    }
}

Measured memory_bytes: 4140
# /usr/bin/python
# -*- coding: utf-8 -*-
import math
import sys


def check(route,N):
  dct = {i:[] for i in range(1,N+1)}
  for a,b in route:
    dct[a].append(b)
    dct[b].append(a)

  nxt = [1]
  visited = set()
  while len(nxt)>0 and len(visited)<N:
    p = nxt.pop(0)
    visited.add(p)
    for q in dct[p]:
      if q not in visited:
        nxt.append(q)      

  if len(visited)<N:
    return 1
  else:
    return 0


def main():
  ## input
  N,M = map(int, input().split())
  route = []
  for _ in range(M):
    route.append(list(map(int, input().split())))

  ## solve
  ans = 0
  for i in range(M):
    ans += check(route[0:i]+route[i+1:], N)    
  return ans

if __name__ == "__main__":
  print(main())


Measured memory_bytes: 40432
string = input()
num = int(string)
n = list(map(int,list(string)))
total = sum(n)
if(len(n)==1):
    print(num)
else:
    digit_n = int(num/(10**(len(n)-1)))
    result = ((digit_n-1)+(len(n)-1)*9)
    print(result if result>total else total)

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
 	ll cost;
 };
using Graph = vector<vector<Edge>>;

const int MAX = 10000000;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = LLONG_MAX;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
/****** define constant end ********/
long long modpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
	if (n & 1)
	  res = res * a % mod;
	a = a * a % mod;
	n >>= 1;
  }
  return res;
}
/****** define variable start ******/
ll n;
/******* define variable end *******/
int solve() {
	cin >> n;
	if(n == 1) {
		cout << 0 << endl;
		return 0;
	}
	ll ans = (modpow(10, n, MOD) - modpow(9, n, MOD) - modpow(9, n, MOD) + modpow(8, n, MOD)) % MOD;
	while(ans < 0){
		ans += MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}

int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


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

const int N = 200005;
const int offset = 2005;
const int mod = 1000000007;

void add(int &x,int y) {
	x += y; if (x >= mod) x -= mod;
}

int mul(int x,int y) {
	return (long long) x * y % mod;
}

int pw(int x,int y) {
	int ret = 1;
	while (y) {
		if (y & 1) ret = mul(ret, x);
		x = mul(x, x);
		y >>= 1;
	}
	return ret;
}

int n;
int a[N], b[N];
vector<int> _get[offset + offset];
int f[offset + offset][offset + offset], upd[offset + offset][offset + offset];
int fac[N], ifac[N];

int calc(int x,int y) {
	return mul(fac[x + y], mul(ifac[x], ifac[y]));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i] >> b[i];
		upd[-a[i] + offset][-b[i] + offset]++;
		_get[a[i] + offset].push_back(b[i] + offset);
	}
	int res = 0;
	for (int x = 0; x < offset + offset; ++x) {
		for (int y = 0; y < offset + offset; ++y) {
			add(f[x][y], upd[x][y]);
			if (x > 0) add(f[x][y], f[x - 1][y]);
			if (y > 0) add(f[x][y], f[x][y - 1]);
		}
		for (int y : _get[x]) add(res, f[x][y]);
	}
	fac[0] = 1;
	for (int i = 1; i < N; ++i) fac[i] = mul(fac[i - 1], i);
	ifac[N - 1] = pw(fac[N - 1], mod - 2);
	for (int i = N - 2; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
	for (int i = 1; i <= n; ++i) add(res, mod - calc(a[i] + a[i], b[i] + b[i]));
	res = mul(res, pw(2, mod - 2));
	cout << res << '\n'; 
}


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

typedef pair<int, int> II;
typedef vector< II > VII;
typedef vector<int> VI;

#define endl "\n"
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ll long long
#define fr(i,n) for(i=0;i<n;i++)


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;
    int i;
    cin>>s;
    cout<<s[0]<<s[1]<<s[2]<<"8";
    for(i=4;i<10;i++)
        cout<<s[i];
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
n,x,y=map(int,input().split())

count=[0]*(n-1)
for i in range(n):
    l=i
    for j in range(i+1,n):
        r=j
        dis=min(j-i, abs(x-1-l)+1+abs(y-1-r))
        count[dis-1]+=1
        

for i in range(n-1):
    print(count[i])

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

int main(){
  int h,w;
  cin>>h>>w;
  char ma[111][111];
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin>>ma[i][j];

  int x[111]={},y[111]={};
  for(int i=0;i<h;i++){
    
    int f=1;
    for(int j=0;j<w;j++){
      if(ma[i][j]=='#'){
	f=0;
	break;
      }
    }
    y[i]=f;
  }

  for(int j=0;j<w;j++){
    int f=1;
    for(int i=0;i<h;i++){
      if(ma[i][j]=='#'){
	f=0;
	break;
      }
    }
    x[j]=f;
  }

  for(int i=0;i<h;i++){
    int f=0;
    for(int j=0;j<w;j++){
      if(y[i]||x[j])continue;
      cout<<ma[i][j];
      f=1;
    }
    if(f)cout<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoderMake.ABC161
{
    class ABC161C
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select((x) => long.Parse(x)).ToArray();
            long par = input[0] % input[1];
            long bar = input[1] - par;
            if (par >= bar)
            {
                Console.WriteLine(bar.ToString());
            }
            else
            {
                Console.WriteLine(par.ToString());
            }
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll N; cin >> N;
    ll res = to_string(N).size();
    ll A,B;
    for (ll i=1;i<=sqrt(N);i++){
        if (N%i!=0) continue;
        B = N/i;
        res = min(ll(to_string(B).size()),res);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <numeric>
#include <type_traits>
using namespace std;


int gcdH(int p, int q){
  if(p==0){return q;}
  if(q==0){return p;}
  return gcdH(q,p%q);
}


int main(){
  // INPUT
  int n,g;
  cin >> n;
  int a[n+2];
  int l[n+2];
  int r[n+2];
  for(int i=1;i<=n;i++){cin >> a[i];}

  //CALC
  int p = 1;
  int q = n;
  r[n+1] = 0;
  l[0] = 0;
  for(int i=1;i<=n;i++){
    l[i] = gcdH(a[i],l[i-1]);
  }
  for(int i=n;i>=1;i--){
    r[i] = gcdH(a[i],r[i+1]);
  }
  int maxG = 0;
  for(int i=1;i<=n;i++){
    g = gcdH(l[i-1],r[i+1]);
    //cout << g << endl;
    if(maxG < g){maxG = g;}
  }
  //OUTPUT
  cout << maxG << endl;
  return 0;
}


Measured memory_bytes: 1408
using System;

class MyClass
{
    static void Main(string[] args)
    {
        for (int i = 1; i <= 9; i++)
        {
            for (int j = 1; j <= 9; j++)
            {
                Console.WriteLine("{0}x{1}={2}", i, j, i * j);
            }
        }
    }
}


Measured memory_bytes: 5544
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

int main() {
    int n;
    cin >> n;
    if(n % 10 == 9){
        cout << "Yes" << endl;
    }else if(n/10 == 9){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 256
/* template.cpp [[[ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)s)
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)s)
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
ll in(){ ll x; cin >> x; return x; }
vector<ll> in(size_t n){ vector<ll> v(n); each(x, v) cin >> x; return v; }
/* ]]] */

int n;
int a[100];
int b[110];

int main(){
  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) b[a[i]]++;
  int mx = *max_element(a, a + n);
  if (n >= 3 && mx < 2) cout << "Impossible\n", exit(0);
  int t = mx % 2 == 0 ? mx / 2 + 1 : (mx + 1) / 2;
  rep(i, t, mx + 1){
    if (b[i] < 2) cout << "Impossible\n", exit(0);
  }
  if (mx % 2 == 0 && b[mx / 2] != 1) cout << "Impossible\n", exit(0);
  if (mx % 2 == 1 && b[(mx + 1) / 2] != 2) cout << "Impossible\n", exit(0);
  if (mx % 2 == 0) rep(i, mx / 2) if (b[i] > 0) cout << "Impossible\n", exit(0);
  if (mx % 2 == 1) rep(i, mx / 2 + 1) if (b[i] > 0) cout << "Impossible\n", exit(0);
  cout << "Possible\n";
}


Measured memory_bytes: 256
N, x = map(int, input() .split())
a = list(map(int, input() .split()))
a.sort()
for i in range(N):
    if x - a[i] > 0:
        x = x - a[i]
    elif x - a[i] == 0:
        i += 1
    else:
        break
print(i)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<map>
#include<queue>

#define rep(i,n) for(int i=0;i<int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
using namespace std;

int xx,yy;

class Q{
	public:
	int bx,by,bbx,bby;
	int dep;
	Q(int bx,int by,int bbx,int bby,int dep):
	bx(bx),by(by),bbx(bbx),bby(bby),dep(dep){}
};

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

int masu[51][51];
int memo[51][51][51][51];

int search(int bx,int by,int bbx,int bby){
	
	queue<Q> hako;
	
	hako.push(Q(bx,by,bbx,bby,0));
	
	while(1){
		if(hako.empty()==1){
			break;
		}
		
		Q u=hako.front();
		hako.pop();
		
		if(u.dep>=100){
			break;
		}
		
		if(u.bx<=0 || u.by<=0 || u.bx>xx || u.by>yy ){
			continue;
		}
		if(u.bbx<=0 || u.bby<=0 || u.bbx>xx || u.bby>yy){
			continue;
		}
		if(masu[u.bx][u.by]==1 || masu[u.bbx][u.bby]==1){
			//puts("fsdafasdf");
			continue;
		}
		
		
		if(memo[u.bx][u.by][u.bbx][u.bby]==1){
			continue;
		}else{
			memo[u.bx][u.by][u.bbx][u.bby]=1;
		}
		
		
		/*
		printf("\n%d\n",u.dep);
		rep(i,yy){
			rep(j,xx){
				if(i+1==u.by && j+1==u.bx){
					printf("4 ");
					continue;
				}
				if(i+1==u.bby && j+1==u.bbx){
					printf("5 ");
					continue;
				}
				printf("%d ",masu[j+1][i+1]);
			}puts("");
		}
		*/
		if(u.bx==u.bbx && u.by==u.bby){
			return u.dep;
		}
		
		
		rep(i,4){
			int ddx=dx[i],ddy=dy[i];
			int mx,my;
			mx=u.bx+ddx;
			my=u.by+ddy;
			//printf("mx %d  my %d   masu %d\n",mx,my,masu[mx][my]);
			if(mx<=0 || my<=0 || mx>xx || my>yy||masu[mx][my]==1){ddx=ddy=0;}
			
			int ddxx=dx[(i+2)%4],ddyy=dy[(i+2)%4];
			mx=u.bbx+ddxx;
			my=u.bby+ddyy;
			//printf("mmx %d  mmy %d   masu %d\n",mx,my,masu[mx][my]);
			if(mx<=0 || my<=0 || mx>xx || my>yy||masu[mx][my]==1){ddxx=ddyy=0;}
			
			//printf("pushhhhhhhhhhhhhhhh %d %d %d %d\n",u.bx+ddx,u.by+ddy,u.bbx+ddxx,u.bby+ddyy);
			hako.push(Q(u.bx+ddx,u.by+ddy,u.bbx+ddxx,u.bby+ddyy,u.dep+1));
		}
	}
	return -1;
}

int main(){
	while(1){
		sintt(xx,yy);
		
		if(xx==0){
			break;
		}
		int bx,by,bbx,bby;
		sintt(bx,by);
		sintt(bbx,bby);
		
		rep(i,51)rep(j,51)rep(k,51)rep(p,51){
		memo[i][j][k][p]=0;
		}
		
		rep(i,yy){
			rep(j,xx){
				sint(masu[j+1][i+1]);
			}
		}
		
		int ans=search(bx,by,bbx,bby);
		if(ans==-1){
			puts("NA");
		}else{
			printf("%d\n",ans);
		}
	}
}

/*
3 4
1 3
2 4
0 0 0
0 1 0
0 1 0
1 0 0

3 2
1 1
2 2
0 0 0
1 0 0
*/

Measured memory_bytes: 27000
#include <stdio.h>
 
#define N 100001
#define Q 501
 
int main() {
  int i,j,S[N],T[Q],n,q,count=0;
  scanf("%d",&n);
  for(i=0; i<n; i++) scanf("%d",&S[i]);
  scanf("%d",&q);
  for(i=0; i<q; i++) scanf("%d",&T[i]);
 
  for(i=0;i<q;i++){
    for(j=0;j<n;j++){
      if(T[i]==S[j]){
	count++;
	break;
      }
    }
  }
  printf("%d\n",count);
 
  return 0;
 
}

Measured memory_bytes: 648
n=gets.to_i
for x in 1..n do
    y=x
    if y%3==0 then
        printf(" %d",y)
        next
    end
    while true
       if y%10==3 then
          printf(" %d",x)
          break;
       end
       y/=10
       if y == 0 then
          break
       end
    end
end
print "\n"

Measured memory_bytes: 8724
#include <stdio.h>
 
#define MOD 2019
 
int main(void) {
  	int L, R, l, r, A, a;
    int c = 2018;
  	scanf("%d %d", &L, &R);
    if((R - L) >= 2018) {
        printf("0\n");
        return 0;
    }
    for (int i = L; i < R; i++) {
        for(int j = i + 1; j <= R; j++) {
            l = i % MOD;
            r = j % MOD;
            A = l * r;
            a = A % MOD;
            if (a < c) {
                c = a;
            }
        }
    }
    printf("%d", c);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

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

	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		if (i % 3 > 0 && i % 5 > 0) {
			ans += i;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3164
#include<stdio.h>
int main()
{
    int i,n,a[10000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=n-1;i>=0;i--)
    {
        if(i>0)
        printf("%d ",a[i]);
        else 
            printf("%d",a[i]);
    }
    printf("\n");
    return 0;
}



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

class myStack {
public:
	void push(int x) {
		S[++top] = x;
	}
	int pop() {
		top--;
		return S[top + 1];
	}

private:
	int top = 0;
	int S[1000] = { 0 };
};

int main() {
	string s;
	myStack sta;

	std::cin >> s;
	while (!std::cin.eof()) {
		if (s[0] == '+') {
			int a = sta.pop();
			int b = sta.pop();
			sta.push(b + a);
		}
		else 	if (s[0] == '-') {
			int a = sta.pop();
			int b = sta.pop();
			sta.push(b - a);
		}
		else 	if (s[0] == '*') {
			int a = sta.pop();
			int b = sta.pop();
			sta.push(b * a);
		}
		else {
			int i; 
			i = stoi(s);
			sta.push(i);
		}

		std::cin >> s;
	}

	cout << sta.pop() << endl;

	return 0;
}

Measured memory_bytes: 3212
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <iterator>
#pragma warning(disable:4996)

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define MOD 1000000007
using namespace std;

long a[100];
long b[100];
long c[100];
long d[100];

int main(int argc, char* argv[])
{
    char ans[4]={0};
    long i;
    for(i=0; i<3; i++) {
        char str[4]={0};
        scanf("%s", str);
        ans[i]=str[i];
    }
    printf("%s\n", ans);
    return 0;
}


Measured memory_bytes: 128
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void minAssign(T, U = T)(ref T dst, U src)
{
    dst = cast(T) min(dst, src);
}

alias sread = () => readln.chomp();

void main()
{
    long N = lread();

    static immutable dp = () {
        enum Nmax = 10 ^^ 5;
        auto dp = new byte[](Nmax + 1);
        dp[] = byte.max;
        dp[0] = 0;

        foreach (i; 0 .. Nmax)
            if (dp[i] != byte.max)
            {
                dp[i + 1].minAssign(cast(ubyte) dp[i] + 1);

                size_t j = 6;
                while (i + j < dp.length)
                {
                    dp[i + j].minAssign(cast(ubyte) dp[i] + 1);
                    j *= 6;
                }

                j = 9;
                while (i + j < dp.length)
                {
                    dp[i + j].minAssign(cast(ubyte) dp[i] + 1);
                    j *= 9;
                }
            }
        return dp;
    }();

    dp[N].writeln();
}


Measured memory_bytes: 256
open Scanf
open Printf

let flip f x y = f y x

let rec range a b = if a >= b then [] else a :: range (a+1) b

let read_int () = scanf " %d" (fun x -> x)
let rec read_ints n = if n = 0 then [] else let i = read_int () in i :: read_ints (n-1)

let rec for_iter a b f = if a >= b then [] else let x = f a in x :: for_iter (a+1) b f
let rec for_iter_ a b f = if a >= b then () else (f a; for_iter_ (a+1) b f)

let list_of_string str = range 0 (String.length str) |> List.map (fun i -> str.[i])
let array_of_string str = Array.init (String.length str) (fun i -> str.[i])

let () =
  let [a; b; c; d] = read_ints 4 in
  printf "%d\n" @@ max 0 @@ (min b d - max a c)


Measured memory_bytes: 384
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};

class UnionFind{
    public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> parent;

    UnionFind(int N){
        parent = vector<int>(N,-1);
    }

    int root(int A){
        if(parent[A] < 0) return A;
        return parent[A]=root(parent[A]);
    }

    int size(int A){
        return -parent[root(A)];
    }

    bool unite(int A, int B) {
        A = root(A), B = root(B);
        if(A == B) return false; 

        if(size(A) < size(B)) swap(A,B);
        parent[A] += parent[B];
        parent[B] = A;
        return true;
    }

    bool same(int A, int B){
        return root(A)==root(B);
    } 
};


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

    int n,q;
    cin>>n>>q;
    UnionFind uni(n);
    while(q--){
        int t,u,v;
        cin>>t>>u>>v;
        if(t){
            cout << uni.same(u,v) << "\n";
        }
        else {
            uni.unite(u,v);
        }
    }

}

Measured memory_bytes: 3980
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;

void solve()
{
    int n;
    cin >> n;
    ll a[n];

    ll sum = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a+n);
    sum += *max_element(a, a+n);

    int take = 0, j = n - 2;
    for(int i = 0; i < n - 2; i++)
    {
        take++;
        sum += a[j];
        if(take > 1)
        {
            j--;
            take = 0;
        }
    }
    cout << sum << endl;
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll t;
    solve();
    return 0;
}


Measured memory_bytes: 5108
#include <iostream>

using namespace std;

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

  int h = 0;
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    
    if (a < h) sum += h - a;
    else h = a;
  }
  cout << sum << endl;
}


Measured memory_bytes: 3588
N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))

id = [-1] * (N + 1)
x = 1
l = 0
a = []
while id[x] == -1:
    a.append(x)
    id[x] = l
    l += 1
    x = A[x]

c = l - id[x]
if K < l:
    print(a[K])
else:
    K -= l
    print(a[id[x] + K % c])


Measured memory_bytes: 103712
#include <stdio.h>

int main(void) {
 	unsigned long long int x, ans;
	int rest;
	scanf("%llu", &x);

	ans = (x / 11) * 2;
	rest = x % 11;
	if (rest > 6) {
		ans += 2;
	}
	else if (rest != 0){
		ans++;
	}

	printf("%llu\n", ans);

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
int W,H,x,y,r;
cin>>W>>H>>x>>y>>r;
if(x-r<0){
	cout<<"No"<<endl;
}else if(x+r>W){
	cout<<"No"<<endl;
}else if(y-r<0){
	cout<<"No"<<endl;
}else if(y+r>H){
	cout<<"No"<<endl;
}else{
	cout<<"Yes"<<endl;
return 0;
}
}


Measured memory_bytes: 3096
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

bool isPrime[1080000];
void init(){
  fill(isPrime, isPrime + 1080000, true);
  isPrime[0] = isPrime[1] = false;
  for(int i = 2;i*i < 1080000;i++){
    if(!isPrime[i])continue;
    for(int j = i * i;j < 1080000;j += i)isPrime[j] = false;
  }
}

int main(){
  init();
  Int n;
  cin >> n;
  cout << n << ":";
  for(int i = 2;i*i <= n;i++){
    if(!isPrime[i])continue;
    while(n % i == 0){
      cout << " " << i;
      n /= i;
    }
  }
  if(n != 1)
    cout << " "<<n ;
  cout << endl;
  return 0;
}


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


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

typedef pair<int, int> P;



int main() {

    ll l,r ; cin >> l >> r;

    // 最大の数を使っても2019に到達しない場合は、最小の掛け算が答え
//    if(r*(r-1) < 2019) {
//        cout << l*(l+1) << endl;
//        return 0;
//    }

    // lとrの間で2019で割れるかずがあるとき
    // l < 2019 < rのとき　は0
//    if((l/2019) != (r/2019)) {
//        cout << 0 << endl;
//        return 0;
//    }
//    if(l <= 2019 && r >= 2019) {
//        cout << 0 << endl;
//        return 0;
//    }

    // もしlとrの間に2019を割った素数673の数があれば、2019を作れるので0
    if(r-l >= 673) {
        cout << 0 << endl;
        return 0;
    }


    ll ans = LONG_MAX;
    for(ll i=l; i <= r; i++) for(ll j=i+1; j <= r; j++) {
        ans = min((i*j)%2019, ans);
    }

    cout << ans << endl;

    return 0;

}

Measured memory_bytes: 256
A, B, C, X, Y = map(int, input().split())
ans = 10**18
if Y < X:
    t = X
    X = Y
    Y = t
    t = A
    A = B
    B = t
for i in range(2 * Y + 1):
    if i % 2:
        continue
    x, y = max(0, X - i//2), max(0, Y - i//2)
    sub = C * i + A * x + B * y
    if sub < ans:
        ans = sub
print(ans)

Measured memory_bytes: 39280
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 10;
            int[] array = new int[N];
            for (int i = 0; i < N; ++i)
            {
                array[i] = int.Parse(Console.ReadLine());
            }
            Array.Sort(array);
            Array.Reverse(array);
            for (int i = 0; i < 3; ++i)
            {
                Console.WriteLine(array[i]);
            }
        }
    }
}

Measured memory_bytes: 20084
/*siddharth goyal*/
#include<bits/stdc++.h>
using namespace std;
#define   pb              push_back
#define   REP(i,n)        for(int i=1;i<=n;i++)
#define   FOR(i,a,b)      for(int i=a;i<=b;i++)
#define   all(v)          v.begin(),v.end()
#define   F               first
#define   S               second
#define   vl              vector<LL>
#define   itr             ::iterator it
#define   lb              lower_bound
#define   ub              upper_bound
#define   LL              long long
#define   ULL             unsigned long long
#define   ret             return 
LL n,i,j,ans = 0;
long long f(long long a) {
     long long res[] = {a,1,a+1,0};
     return res[a%4];
}

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}
 LL findXORofRange(LL m, LL n) {
    LL patternTracker[4];

    if(m % 2 == 0)
    {  LL patternTracker[] =  {n, 1LL, n^1, 0};
         return patternTracker[(n-m) % 4]; 
    }
    else
    { LL patternTracker[] =  {m, m^n, m-1, (m-1)^n};
      return patternTracker[(n-m) % 4];
    } 
    
}
int main()
{   // Read the constraints,highlights,Time Limit,Test Cases
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    LL a,b ; 

    cin>>a>>b ; 
    //if(a==b) ret cout<<a,0 ; 
    //cout<<getXor(a,b)<<endl;
    cout<<findXORofRange(a,b)<<endl;
}
//Check for 0,1 and other corner cases.

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

int main(){
    int a,b,c,d;
    cin >> a >> b >> c;

    if(a > b){
        d = a;
        a = b;
        b = d;
    }
    if(b > c){
        d = b;
        b = c;
        c = d;
    }
    if(a > b){
        d = a;
        a = b;
        b = d;
    }
    
    cout << a << " " << b << " " << c << endl;
  
}


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

#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

int main() {
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
}


Measured memory_bytes: 3620
<?php 
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextString() {
        return (string)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}

class out {
    public static function println($str = "") {
        echo $str . PHP_EOL;
    }
}

$sc = new Scanner();
$A = $sc->nextInt();
$OP = $sc->nextString();
$B = $sc->nextInt();


if ($OP == '+') {
    out::println($A  +  $B);
}else {
    out::println($A  -  $B);
}


Measured memory_bytes: 16152