akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.io.*;

public class Main{

	public static void main(String[] args) throws IOException {
		String a = next(), b = next();
		int x = Integer.parseInt(a+b);
		if((int)(Math.sqrt(x))*(int)(Math.sqrt(x)) == x) println("Yes");
		else println("No");
		exit();
	}

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	static String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine().trim());
		return st.nextToken();
	}

	static long readLong() throws IOException {
		return Long.parseLong(next());
	}

	static float readFloat() throws IOException {
		return Float.parseFloat(next());
	}

	static boolean readBoolean() throws IOException {
		return Boolean.parseBoolean(next());
	}

	static short readShort() throws IOException {
		return Short.parseShort(next());
	}

	static byte readByte() throws IOException {
		return Byte.parseByte(next());
	}

	static int readInt() throws IOException {
		return Integer.parseInt(next());
	}

	static double readDouble() throws IOException {
		return Double.parseDouble(next());
	}

	static char readCharacter() throws IOException {
		return next().charAt(0);
	}

	static String readLine() throws IOException {
		return br.readLine().trim();
	}

	static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	static void print(Object o) {
		pr.print(o);
	}

	static void println(Object o) {
		pr.println(o);
	}

	static void flush() {
		pr.flush();
	}

	static void println() {
		pr.println();
	}

	static void exit() throws IOException {
		br.close();
		pr.close();
		System.exit(0);
	}
}


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

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define RREP(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define RFOR(i, a, b) for (ll i = a; i >= (ll)(b); i--)
#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[ ";
    for (auto a : v) os << a << " ";
    os << "]";
    return os;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(31, vector<int>(N));
    REP(i, N) {
        int a;
        cin >> a;
        int j = 0;
        while (a > 0) {
            A[j][i] = (a % 2);
            a /= 2;
            j++;
        }
    }
    vector<int> ans(N);
    RREP(i, 31) {
        int cnt = 0;
        REP(j, N) cnt += A[i][j];
        REP(j, N) {
            if (cnt % 2 == 0) {
                ans[j] = ans[j] * 2 + A[i][j];
            } else {
                ans[j] = ans[j] * 2 + ((A[i][j] + 1) % 2);
            }
        }
    }

    REP(i, N) {
        if (i) cout << " ";
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

// 1010 > 0111
// 1111 > 0010
// 0001 > 1100
// 1001 > 0100
// ----
//

// 1110 -> 0001


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

int main() {
  int A,B,C;
  string ans="Yes";
  cin >> A >> B >> C;
  if(A==B && B== C) ans = "No";
  else if(A!=B && B!=C && C!=A) ans = "No";
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3596
#include<iostream>
#include<math.h>
using namespace std;

int main(){
    double a,b,c,d=0,e=0;
    string s;
    cin>>s;
    if(s[0]==s[1] && s[1]==s[2]){cout<<"No"; return 0;}
    if(s[0]==s[2] || s[0]==s[1] || s[1]==s[2]){cout<<"Yes";return 0;}
    else{cout<<"No";}
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}


int main(){
    cin.tie(0);
    Int N, X; cin >> N >> X;
    
    Int ans = 0;
    Int crt;
    Int pre;
    if (X*2 < N){
        ans += X+(N-X);
        crt = X;
        pre = N-X;
    }else if(X*2 > N){
        ans += X+(N-X);
        crt = N-X;
        pre = X;
    }else if(X*2 == N){
        ans += 3*X;
        cout << ans << endl;
        return 0;
    }

    while (pre % crt){
        ans += pre/crt*2*crt;
        Int tmp = crt;
        crt = pre%crt;
        pre = tmp;
    }
    ans += pre*2-crt;
    cout << ans << endl;

}


Measured memory_bytes: 256
#include<set>  
#include<map>  
#include<stack>  
#include<cstdio>  
#include<queue>  
#include<cmath>  
#include<vector>  
#include<cstring> 
#include<climits>  
#include<iostream> 
#include<algorithm> 
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
LL read(){ 
    LL f=1,x=0; 
    char c=getchar(); 
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();} 
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();} 
    return f*x; 
}
#define MAXN 100000
struct node{
	int x,y;
	node(){}
	node(int X,int Y){x=X,y=Y;}
	friend bool operator < (node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
}dot[MAXN+5];
map<node,bool> Map,Use;
LL H,W,N,ans[10];
bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int main(){
	H=read(),W=read(),N=read();
	for(int i=1;i<=N;i++){
		dot[i].x=read(),dot[i].y=read();
		Map[node(dot[i].x,dot[i].y)]=1;
	}
	for(int i=1;i<=N;i++)
		for(int t=0;t<=8;t++){
			int sx=dot[i].x-t%3,sy=dot[i].y-t/3;
			if(sx<1||sy<1||sx>H-2||sy>W-2||Use.count(node(sx,sy))) continue;
			int tmp=0;
			for(int j=sx;j<sx+3;j++)
				for(int k=sy;k<sy+3;k++)
					if(Map.count(node(j,k))) tmp++;
			Use[node(sx,sy)]=1;
			if(tmp) ans[tmp]++;
		}
	LL tmp=0;
	for(int i=1;i<=9;i++)
		tmp+=ans[i];
	ans[0]=(H-2)*(W-2)-tmp;
	for(int i=0;i<=9;i++)
		printf("%lld\n",ans[i]);
    return 0;
}

Measured memory_bytes: 63488
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef long long ll;
typedef long double ld;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ld w, h;
    int x, y;
    cin >> w >> h >> x >> y;
    cout << (w * h) / 2 << ' ';
    if(x == w / 2 && y == h / 2)
    {
        cout << 1;
    }
    else
    {
        cout << 0;
    }

    return 0;
}


Measured memory_bytes: 384
def resolve():
    INF = 1<<60
    H, N = map(int, input().split())
    A, B = [], []
    for i in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [[INF]*(H+1) for _ in range(N+1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(H+1):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            dp[i+1][min( j + A[ i ], H)] = min(dp[i+1][min( j + A[ i ], H)], dp[i+1][j] + B[i])
    print(dp[N][H])


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 147012
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> //__gnu_pbds::gp_hash_table<int, int> table;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  //min heap

typedef int OwO;
typedef double UwU;

#define int long long
#define double long double
#define INF 1000000000
#define PI 3.14159265358979323846
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vi vector<int>

using namespace std;

OwO main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin >> N;
  vi t(N);
  int c_n = 0;
  int abs_sum = 0;
  int m_p = INF;
  int m_n = -INF;
  for(int x=0; x<N; x++){
    cin >> t[x];
    if(t[x]<=0){
      c_n++;
      m_n=max(m_n, t[x]);
    }
    abs_sum+=abs(t[x]);
    if(t[x]>0)
      m_p = min(m_p, t[x]);
  }
  if(c_n%2==0)
    cout << abs_sum << endl;
  else{
    cout << max(abs_sum-2*m_p, abs_sum+2*m_n) << endl;
  }

  return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import sys
# from collections import defaultdict, deque
# from math import sqrt, gcd, factorial, tan, pi, sin, cos
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline()[:-1]


def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    mn = 1e9
    c = 0
    z = 0
    sm = 0
    for e in a:
        mn = min(mn, abs(e))
        if e < 0:
            c += 1
        if e == 0:
            z += 1
        sm += abs(e)
    if not z:
        if c % 2:
            sm -= 2 * mn

    print(sm)
    
        




t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()



"""
1 -> (1, 2) -> (2 ** 3, 3) -> (3, 1)

"""



Measured memory_bytes: 14464
n,a,b,c,d = gets.split.map(&:to_i)

g = (a-b).abs
n.times{|i|
  df = (d-c)*i
  min = c*(n-1-i*2)-df
  max = d*(n-1-i*2)+df
  
  if min<=g && g<=max
    puts "YES"
    exit
  end
}
puts "NO"


Measured memory_bytes: 1788
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long K = sc.nextLong();
		int[][] f = new int[N][2];
		
		for(int i=0; i<N; i++){
			f[i][0] = sc.nextInt();
			f[i][1] = sc.nextInt();
		}
		Arrays.sort(f, new Comparator<int[]>(){
			public int compare(int[] a, int[] b) {
			    if(a[0] > b[0]) {
			      return 1;
			    }else if (a[0] == b[0]) {
			      return 0;
			    }else {
			      return -1;
			  }}
		});
		
		long sum = 0;
		int ans = 0;
		int p = 0;
		while( sum<K ){
			ans = f[p][0];
			sum += f[p][1];
			p++;
		}
		System.out.println(ans);
		return;
	}
}

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

using namespace std;


int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> x(m);
	for (int i = 0; i < m; i++)
	{
		cin >> x.at(i);
	}
	sort(x.begin(), x.end());
	vector<int> p(m);
	for (int i = 0; i <m ; i++)
	{
		if (i==m-1)
		{
			p.at(i) = 5000030;
		}
		else
		{
			p.at(i) = x.at(i + 1) - x.at(i);
		}
	}
	sort(p.begin(), p.end());
	reverse(p.begin(), p.end());
	int ans = 0;
	for (int i = n; i < m; i++)
	{
		ans += p.at(i);
	}
	cout << ans << endl;
}

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


int main(int argc, char **argv)
{
	long long x; cin >> x;
	long long deposit = 100;
	int y = 0;
	
	while(deposit < x) {
		deposit *= 1.01;
		y++;
	}
	
	cout << y << "\n";
	
	return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll;
#define forn(i,e) for(ll i=0; i<e; i++)
#define fors(i,e) for(ll i=s; i<e; i++)
#define endl "\n"
#define zoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PB push_back 
#define MP make_pair
#define F first
#define S second


int main()
{

zoom;

ll a[5] ; 
forn(i,5) 
{cin >> a[i] ;
	if(a[i] == 0) 
		cout << i+ 1 ; 
}



}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
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 (a>b) { a=b; return 1; } return 0; }
ll n;
void dfs(int i, int k,string s){
    if(i==n){
        cout<<s<<endl;
        return ;
    }
    rep(j,k+1){
        char tmp = 'a'+j;
        dfs(i+1,((j==k)?k+1:k),s+tmp);
    }
}

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

cin>>n;
dfs(0,0,"");
//system("pause");
return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define MAX 100100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n;
vector<int> E[MAX];
bool dfs(int u,int ff)
{
	int cnt=0;
	for(int v:E[u])
	{
		if(v==ff)continue;
		if(dfs(v,u))++cnt;
	}
	if(cnt>=2){puts("First");exit(0);}
	return cnt^1;
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		E[u].push_back(v);
		E[v].push_back(u);
	}
	if(dfs(1,0))puts("First");
	else puts("Second");
	return 0;
}


Measured memory_bytes: 5888
from sys import stdin

readline = stdin.readline


def ns():
    """
    入力を`[\\s]`を除いて文字列として取得
    """
    return readline().rstrip()


def ni():
    """
    入力を`int`に変換
    """
    return int(ns())


def main():
    print(3 * ni() ** 2)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
K, S = map(int, input().split())

count = 0

for z in range(K, -1, -1):
    for y in range(K, -1, -1):
        x = S - z - y
        if z >= y and y >= x and x >= 0:
            if x == y == z:
                count += 1
            elif (x == y and y != z) or (y == z and z != x):
                count += 3
            else:
                count += 6

print(count)

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

char s[MAXN];

void solve(){
	scanf("%s", &s[0]);
	int len = strlen(s);
	int fl = 0;
	REP(i, 1, len) {
		if (s[i] != '9') {
			fl = 1;
			break;
		}
	}
	int sum = (len - 1) * 9 - fl + s[0] - '0';
	printf("%d\n", sum);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if(x<=y&&y<=z) printf("%d %d %d\n",x,y,z);
else if(x<=z&&z<=y) printf("%d %d %d\n",x,z,y);
else if(y<=x&&x<=z) printf("%d %d %d\n",y,x,z);
else if(y<=z&&z<=x) printf("%d %d %d\n",y,z,x);
else if(z<=x&&x<=y) printf("%d %d %d\n",z,x,y);
else if(z<=y&&y<=x) printf("%d %d %d\n",z,y,x);
return 0;
}

Measured memory_bytes: 596
array1 = [1,3,5,7,8,10,12]
array2 = [4,6,9,11]
array3 = [2]
x,y = map(int,input().split())
if (x in array1 and y in array1) or (x in array2 and y in array2) or (x in array3 and y in array3):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 9124
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define FAST_IO                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define watch(x) cout << (#x) << " is: " << (x) << endl
#define vw(v)                        \
    cout << (#v) << " is: " << endl; \
    for (long long B : (v))                \
    {                                \
        cout << B << " ";            \
    }                                \
    cout << endl
#define check(x) cout << "here " << (x) << "?" << endl
#define rep(i, a, b) for (long long i = (a); i < (b); i++)
#define per(i, a) for (long long i = (a); i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define rv(x) (x).rbegin(), (x).rend()
#define pb push_back
long long const MAX = 2147483647, REALMAX = 9223372036854775806;
int main()
{
	long long a;
	cin >> a;
	cout << a * (a - 1) / 2;
}

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

int main(){
	int a, b;
	cin >> a >> b;
	int luas, jalan;
	luas = a*b;
	jalan = a + b - 1;
	luas = luas-jalan;
	cout << luas << endl;
	return 0;
}

Measured memory_bytes: 256
// Copyright 2017 wu_qing
#include <cstdio>
#include <algorithm>
const int N = 2e5 + 10;
int n, a[N], d = 1;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    std::sort(a + 1, a + n + 1);
    if (a[n] == a[1]) {
        if (n == a[1] + 1 || a[1] * 2 <= n)
            printf("Yes\n");
        else
            printf("No\n");
    } else if (a[n] - a[1] == 1) {
        while (a[d] == a[d + 1])
            d++;
        if (a[1] >= d && (a[1] + 1 - d) * 2 + d <= n)
            printf("Yes\n");
        else
            printf("No\n");
    } else {
        printf("No\n");
    }
    return 0;
}


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

int main() {
    int H, N;
    cin >> H >> N;
    vector<int> A(N);
    rep(i, N) {
        cin >> A[i];
    }
    int sum = accumulate(A.begin(), A.end(), 0);
    if (H <= sum) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<numeric>

using namespace std;

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

template<typename A, typename B> bool chmin(A &a, const B &b){ return b < a && (a = b, true); }
template<typename A, typename B> bool chmax(A &a, const B &b){ return a < b && (a = b, true); }

int main () {
  int n;
  cin >> n;
  while (n > 1000){
    n -= 1000;
  }
  if (n == 0){
    cout << n << '\n';
  }
  else{
    cout << 1000-n << '\n';
  }
  
  return 0;
}

Measured memory_bytes: 3628
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;

using Graph = vector<vector<int>>;
int main(){
  lll ii,jj,kk;
  vector<int> ret;

  int n,m;
  cin >> n >> m;

  Graph g(n);

  int a,b;

  for(ii=0;ii<m;ii++){
    cin >> a >> b;
    g[a-1].push_back(b-1);
    g[b-1].push_back(a-1);
  }

  //cout << "regist!" << endl;
  vector<int> todo;
  vector<bool> seen(n);

  seen.assign(n,false);

  seen[0] = true;
  todo.push_back(0);
  int v;
  //cout << "todo:" << todo[0] << endl;
  vector<int> prev(n);
  while(!todo.empty()){

    v = todo[0];
    todo.erase(todo.begin());
    //cout << "todo:" << v << endl;
    
    for(int w : g[v]){
      if(seen[w] == true){continue;}
      seen[w] = true;
      todo.push_back(w);
      prev[w] = v;
    }
  }
  bool okflg = true;

  for(ii=0;ii<n;ii++){
    if(seen[ii] == false){
      okflg = false;
      break;
    }
  }
  if(okflg){
    cout << "Yes" << endl;
    for(ii=1;ii<n;ii++){
      cout << prev[ii] + 1 << endl;
    }
  }
  else{
    cout << "No" << endl;
  }
  //cout << "n:" << n << endl;

  return 0;
}


Measured memory_bytes: 10460
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))



Measured memory_bytes: 3572
package main

import "fmt"

const mod int = 1e9 + 7

func main() {
	var n int
	fmt.Scan(&n)
	ts := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ts[i])
	}
	as := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])
	}

	hs := make([]int, n)
	for i := 0; i < n; i++ {
		hs[i] = int(1e18)
	}

	hs[0] = ts[0]
	hs[n-1] = as[n-1]

	fx := make([]bool, n)
	fx[0] = true
	fx[n-1] = true

	if n == 1 && ts[0] != as[0] {
		fmt.Println(0)
		return
	}

	for i := 1; i < n; i++ {
		if ts[i-1] != ts[i] {
			if fx[i] && ts[i] != hs[i] {
				fmt.Println(0)
				return
			}
			fx[i] = true
		}
		hs[i] = min(hs[i], ts[i])
	}

	for i := n - 2; i >= 0; i-- {
		if as[i] != as[i+1] {
			ok := true
			if fx[i] && as[i] != hs[i] {
				ok = false
			}
			if hs[i] < as[i] {
				ok = false
			}
			if !ok {
				fmt.Println(0)
				return
			}
			fx[i] = true
		}
		hs[i] = min(hs[i], as[i])
	}

	ans := 1
	for i := 0; i < n; i++ {
		if fx[i] {
			continue
		}
		ans *= hs[i]
		ans %= mod
	}

	fmt.Println(ans)
}

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


Measured memory_bytes: 7276
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pii pair<ll, ll> 
#define pb push_back
#define debug(x) cerr<< #x << " is " <<x<<endl;
#define debug2(x) cerr<<#x<< " is\n"; for (auto &i:x) {cout<<i<<' '; } cout<<endl;
#define f first
#define s second
using namespace std;



int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin>>n;
    vector<double> dp(3000);
    dp[0]=1.0;
    for (int i=0; i<n; i++){
    	double p; cin>>p;
    	vector<double> ndp(3000);
    	for (int j=0; j<n; j++){
    		ndp[j+1]+=dp[j]*p;
    		ndp[j]+=dp[j]*(1-p);
    	}
    	dp = ndp;
    }
    double re = 0;
    for (int i=n/2+1; i<=n; i++){
    	re+=dp[i];
    }
    cout<<fixed<<setprecision(15)<<re<<'\n';
}

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

int main(){
    long long int N;
    long long int i;
    long long int sum=0;
    cin >> N;
    for(i=1;i<N+1;i++)if((i%3 != 0) && (i%5 != 0))sum+=i;
    cout << sum << endl;
}

Measured memory_bytes: 3636
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

//#include<bits/stdc++.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

#define _USE_MATH_DEFINES
#define ll long long
#define ins Not Needed Thing
#define ull unsigned long long
#define ld long double
#define Accepted 0
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define SORRY FUL Accepted 
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
#define Toktama Kazakhstan 

using namespace std;

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 3e5 + 123;                                          
const int PRI = 555557;
const int pri = 997;

int tests = 1;

inline void Solve () {
	//easy
	int n, k;
	ll ans = 0;
	cin >> n >> k;
	if (k == 0) {
		cout << 1ll * n * n;
		exit(0);
	}
	for (int i = 1;i <= n; i ++) {
           ans += 1ll * n / i * max(0,i - k);
           ans += max(0, n % i - k + 1);
    }

	cout << ans;
}

int main () {
	SpeedForce;
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);	
	// cin >> tests;
	while(tests --) {
		Solve ();
		// Ee Zadrot
	}

	return Accepted; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lson now<<1
#define rson now<<1|1
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int mod=1e9+7;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++)cout<<'x';
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> dim(N);
    vector<vector<int>> edge(N, vector<int>(N, 0));
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        edge[u][v] = edge[v][u] = c;
        dim[u]++, dim[v]++;
    }
    int ans = 0;
    for (int s = 2; s <= 14; s++) {
        vector<int> cand;
        for (int i = 0; i < N; i++) {
            if (dim[i] >= s - 1) { cand.push_back(i); }
        }
        if (cand.size() < s) { break; }
        const int sz = cand.size();
        vector<bool> mask(sz, false);
        fill(mask.end() - s, mask.end(), true);
        auto score = [&](const vector<int>& node) {
            int ans = 0;
            for (const int i : node) {
                int mini = 1 << 30;
                for (const int j : node) {
                    if (i == j) { continue; }
                    if (edge[i][j] == 0) { return 0; }
                    mini = min(mini, edge[i][j]);
                }
                ans += mini;
            }
            return ans;
        };
        do {
            vector<int> node;
            for (int i = 0; i < sz; i++) {
                if (mask[i]) { node.push_back(cand[i]); }
            }
            ans = max(ans, score(node));
        } while (next_permutation(mask.begin(), mask.end()));
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3156
a = gets.to_i # 2
b = gets.to_i # 2
c = gets.to_i # 2
x = gets.to_i # 100

count = 0

0.upto(a) do |a_num|
  0.upto(b) do |b_num|
    0.upto(c) do |c_num|
      x == (a_num * 500 + b_num * 100 + c_num * 50) && count += 1
    end
  end
end

p count


Measured memory_bytes: 1788
import sys
from collections import OrderedDict

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)


class Graph():
    def __init__(self):
        self.adjacency_dict = {}
        self.counter_dict = OrderedDict()

    def add_vertex(self, v):
        self.adjacency_dict[v] = set()
        self.counter_dict[v] = 0

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].add(v2)
        self.adjacency_dict[v2].add(v1)

    def add_count(self, v, count):
        self.counter_dict[v] += count

    def dfs_stack(self, start):
        stack = [start]
        visited = set()

        parent_vertex = 0
        while stack:
            current_vertex = stack.pop()
            visited.add(current_vertex)
            for v in self.adjacency_dict[current_vertex]:
                if v not in visited and v != parent_vertex:
                    self.counter_dict[v] += self.counter_dict[current_vertex]
                    stack.append(v)
            parent_vertex = current_vertex

    def dfs_rec(self, v, pv):
        for nv in self.adjacency_dict[v]:
            if nv != pv:
                self.counter_dict[nv] += self.counter_dict[v]
                self.dfs_rec(nv, v)

    def print_counters(self):
        print(*self.counter_dict.values())


def main():
    n, q = map(int, input().split())
    tree = Graph()
    for v in range(1, n+1):
        tree.add_vertex(v)
    for _ in range(n-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
    for _ in range(q):
        p, x = map(int, input().split())
        tree.add_count(p, x)
    tree.dfs_stack(1)
    # tree.dfs_rec(1, 0)
    tree.print_counters()


if __name__ == "__main__":
    main()


Measured memory_bytes: 192200
package main

import (
	"fmt"
)

// UnionFind has a int slice.
// The index is root if the value is negative,
// and the negative value means the size.
// Else, the index has root,
// and the value means the root index.
type UnionFind struct {
	rootOrSize []int 
}

// New returns an initialized list of size
func New(size int) *UnionFind {
	return new(UnionFind).init(size)
}

// Constructor initializes root and size arrays
func (uf *UnionFind) init(size int) *UnionFind {
	uf = new(UnionFind)
	uf.rootOrSize = make([]int, size)

	for i := 0; i < size; i++ {
		uf.rootOrSize[i] = -1
	}

	return uf
}

// Union connects p and q by finding their roots and comparing their respective
// size arrays to keep the tree flat
func (uf *UnionFind) Union(p int, q int) {
	qRoot := uf.Root(q)
	pRoot := uf.Root(p)

	if qRoot == pRoot {
		return
	}

	// Note that the size is expressed by negative numbers.
	if uf.rootOrSize[qRoot] > uf.rootOrSize[pRoot] {
		uf.rootOrSize[pRoot] += uf.rootOrSize[qRoot]
		uf.rootOrSize[qRoot] = pRoot
	} else {
		uf.rootOrSize[qRoot] += uf.rootOrSize[pRoot]
		uf.rootOrSize[pRoot] = qRoot
	}
}

// Root traverses each parent element while compressing the
// levels to find the root element of p.
func (uf *UnionFind) Root(p int) int {
	// If the rootOrSize is negative, it is the root.
	if uf.rootOrSize[p] < 0 {
		return p
	}

	// Else, the value means the root and should be
	// compressed.
	uf.rootOrSize[p] = uf.Root(uf.rootOrSize[p])
	return uf.rootOrSize[p]
}

// Check if items p, q are connected
func (uf *UnionFind) Connected(p int, q int) bool {
	return uf.Root(p) == uf.Root(q)
}

// Size returns the size of the .
func (uf *UnionFind) Size(p int) int {
	return -uf.rootOrSize[uf.Root(p)]
}

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	A := make([][]int, M)
	ans := make([]int64, M)
	
	for i := range A {
		A[i] = make([]int, 2)
		fmt.Scan(&A[i][0], &A[i][1])
	}

	uf := New(N)
	ans[M-1] = int64(N) * int64(N - 1) / 2
	for i := range A[:len(A)-1] {
		if uf.Connected(A[M-i-1][0]-1, A[M-i-1][1]-1) {
			ans[M-i-2] = ans[M-i-1] 
			uf.Union(A[M-i-1][0]-1, A[M-i-1][1]-1)
		} else {
			ans[M-i-2] = ans[M-i-1] - int64(uf.Size(A[M-i-1][0]-1)) * 
				int64(uf.Size(A[M-i-1][1]-1))
			uf.Union(A[M-i-1][0]-1, A[M-i-1][1]-1)
		}
	}

	for _, e := range ans {
		fmt.Println(e)
	}
}

Measured memory_bytes: 10112
#include<iostream>
#include<functional>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef pair<string,int> P;
int main(){
	string s,temp;
	int x;
	map<string,set<int> > box;
	while(cin>>s>>x)
		box[s].insert(x);
	map<string,set<int> >::iterator ite;
	set<int>::iterator t;
	for(ite=box.begin();ite!=box.end();ite++){
		cout<<ite->first<<endl;
		for(set<int>::iterator se=ite->second.begin();ite->second.end()!=se;se++){
			cout<<*se;
			se++;
			t=se--;
			cout<<(t!=ite->second.end()?' ':'\n');
		}
	}
	return 0;
}

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

using namespace std;

int main(){
    int A,B,C;
    cin>>A>>B>>C;
    int s = 0;
    bool ok = false;
    for(int i = 0; i < B; i++){
        s+=A;
        if(s%B == C) ok = true;
    }
    if(ok) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = "";
 
        boolean[] primes = new boolean[1000000];
        int[] counts = new int[1000000];
 
        for (int i = 2; i < 1000000 / 2 + 1; i++) {
            if (!primes[i]) {
                for (int j = 2; j < 999999 / i + 1; j++) {
                    primes[i * j] = true;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < 1000000; i++) {
            if (!primes[i]) {
                count++;
            }
            counts[i] = count;
        }
 
        while ((line = br.readLine()) != null && !line.isEmpty()) {
            System.out.println(counts[Integer.parseInt(line)]);
        }
    }
}


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

const int N = 1e6+5;
const ll mod = 1e9+7;
vector<ll> primes;
vector<ll> arr;
unordered_map<ll,ll> ind;
vector<ll> lcm;
int n;
int m;

ll binpow(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1) { res = res * a % m; }
		a = a * a % m;
		b >>= 1;
	}
	return res;
}

void sieve(){
	vector<ll> siv(N,0);
	for(int i=2; i<N; ++i){
		if( siv[i] == 0 ){
			primes.push_back(i);
			ind[i] = primes.size() - 1;
			for(int j=i+i; j<N; j+=i){
				siv[j] = 1;
			}
		}
	}
	m = primes.size();
}

vector<ll> solve(vector<ll> arr){
	vector<ll> lcm(m,0);
	for(int i=0; i<arr.size(); ++i){
		for(int j=2; j<sqrt(arr[i])+1; ++j){
			if( arr[i] % j == 0 ){
				ll cn = 0;
				while(arr[i] % j == 0){ cn++; arr[i] /= j; }
				lcm[ ind[j] ] = max(lcm[ ind[j] ], cn);
			}
		}
		if( arr[i] != 1 ){ lcm[ ind[arr[i] ] ] = max( lcm[ ind[arr[i]] ] , 1ll); }
	}
	return lcm;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	sieve();
	cin>>n;
	for(int i=0; i<n; ++i){
		ll x; cin>>x; arr.push_back(x);
	}
	auto lcm = solve(arr);
	ll ans = 1;
	for(int i=0; i<m; ++i){
		ans *= binpow(primes[i], lcm[i], mod);
		ans %= mod;
	}
	ll total = 0;
	for(int i=0; i<n; ++i){
		ll inv = binpow(arr[i], mod-2, mod);
		total += (inv % mod);
		total %= mod;
	}
	ans *= (total % mod);
	ans %= mod;
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 12192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

static const int MAX = 100;
static const long long INF = (1LL<<32);

int n;
long long d[MAX][MAX];

void floyd(){
  rep(k, n){
    rep(i, n) if(d[i][k] != INF){
      rep(j, n) if(d[k][j] != INF){
        chmin(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

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

  rep(i, n){
    rep(j, n){
      if(i == j) d[i][j] = 0;
      else d[i][j] = INF;
    }
  }

  rep(i, e){
    int u, v, c;
    cin >> u >> v >> c;
    d[u][v] = c;
  }

  floyd();

  bool negative = false;
  rep(i, n) if(d[i][i] < 0) negative = true;

  if(negative){
    cout << "NEGATIVE CYCLE" << endl;
    return 0;
  }
  else{
    rep(i, n){
      rep(j, n){
        if(j) cout << " ";
        if(d[i][j] == INF) cout << "INF";
        else cout << d[i][j];
      }
      cout << endl;
    }
  }

  return 0;
}





Measured memory_bytes: 3192
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin >> s;
    int ans = 1 << 30;
    unordered_set<char> st; 
    for (int i=0; i<s.size(); i++){
        st.insert(s[i]);
    }
    if(st.size() == 1){
        cout << 0 << endl;
        return 0;
    }
    
    for (int i=0; i<26; i++){
        // cout << char('a' + i) << endl;
        char target = 'a' + i;
        string t = s;
        if(st.find(target) == st.end()){
            continue;
        }
       
        int tmp_cnt = 0;
        bool flag = false;
        while(!flag){
            flag = true;
            for (int i=0; i<t.size(); i++){
                if (t[i] != target) flag = false;
            }
            string tmp = "";
            for (int i=0; i<t.size()-1; i++){
                if(t[i] == target || t[i+1] == target){
                    tmp += target;
                }else{
                    tmp += s[i];
                }
            }
            t = tmp;
            tmp_cnt++;
        }
        ans = min(tmp_cnt, ans);
    }
    cout << ans - 1 << endl;
}


Measured memory_bytes: 3616
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

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

#define PB push_back
#define MP make_pair

#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
#define R1(a) do{scanf("%d", &(a));}while(0)
#define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0)
#define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0)
#define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0)
#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
#define INF 1000000007

int k, cnt[14][14][14];
string res;

int go_cnt (int col, int minc, int maxc)
{
  if (!col) return 1;
  if (cnt[col][minc][maxc] != -1) return cnt[col][minc][maxc];
  int res = 0;
  FOR(i, minc, maxc + 1) 
  {
    res += go_cnt(col - 1, max(0, i - 1), min(9, i + 1));
  }
  return cnt[col][minc][maxc] = res;
}

void go (int col, int minc, int maxc)
{
  if (!col) return;
  FOR(i, minc, maxc + 1)
  {
    int locc = go_cnt(col - 1, max(0, i - 1), min(9, i + 1));
    if (k - locc <= 0) 
    {
      res += (i + '0');
      go(col - 1, max(0, i - 1), min(9, i + 1));
      break;
    }
    k -= locc;
  }
}

int main ()
{
  R1(k);
  MM(cnt, -1);
  int csum = 0;
  FOR(i, 1, 12)
  {
    if (k - go_cnt(i, 1, 9) < 0)
    {
      go(i, 1, 9);
      break;
    }
    k -= go_cnt(i, 1, 9);
  }
  cout << res << endl;
  return 0;
}


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

int main(){
  int N;
  cin>>N;
  vector<int> P(N);
  for(int i=0;i<N;i++){
    cin>>P.at(i);
  }
  int k=0;
  for(int j=0;j<N;j++){
    if(P.at(j)!=j+1) k++;
  }
  if (k<=2) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

#define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;

vector<int> fac(MX);
vector<int> ifac(MX);

long long fpow(long long a,long long n){
  long long ret=1;
  if(n==1) return a;
  if(n%2==0) {
      ret = fpow(a*a%mod, n/2) %mod ;
  }else {
      ret = (a%mod)*fpow(a*a%mod, n/2) %mod;
  }
  return ret %mod;
}

int comb(int a, int b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    int tmp = ifac[a-b]* ifac[b] % mod;
    return tmp * fac[a] % mod;
}

int P(int a, int b) {
    int res = comb(a,b);
    res *= fac[b];
    return res % mod;
}

int ans, k;
vector<int> to[100005];
void dfs(int v, int p=-1) {
    for(int u: to[v]) {
        if(u == p) continue;
        dfs(u, v);
    }
    int nk = (p==-1) ? k : k-2;
    int c = (p==-1) ? to[v].size()+1 : to[v].size()-1;
    ans *= P(nk, c);
    ans %= mod;
}

int dp[MX+5];
signed main(){
    int n;
    cin >> n;
    vector<int> a;
    rep(i, n+1) dp[i]=MX+5;
    dp[0] = 0;
    dp[1] = 1;
    int cnt = 0;
    a.push_back(1);
    for(int i= 6; i<=n; i=i*6) {
        a.push_back(i);
    }
    cnt = 0;
    for(int i= 9; i<=n; i=i*9) {
        a.push_back(i);
    }

    int ans = 0;
    FOR(i, 2, n+1) {
        for(auto aa: a) {
            if(i-aa>=0) dp[i] = min(dp[i-aa]+1, dp[i]); 
        }
    }

    cout << dp[n] << endl;

    return 0;
}




Measured memory_bytes: 20736
#include <iostream>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <limits>

using namespace std;

int main (int argc, char* argv[]) {
	string s1;
	string s2;
	cin >> s1 >> s2;

	int r = 0;
	for (int i = 0; i < 3; i++) {
		if (s1[i] == s2[i]) r++;
	}
	cout << r << endl;
}


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <cmath>
#include <list>
#include <set>
#include <algorithm>
#include <map>
#include <iostream>
#include <sstream>
#include <queue>
#include <iomanip>

#include <string.h>

using namespace std;

#define MIN(a, b) a < b ? a : b

int main()
{
	unsigned long long M,N;

	cin >> N >> M;

	unsigned long long answer = 0;

	if(2*N > M)
	{
		answer = M / 2;
	}
	else
	{
		unsigned long long M2 = M - 2*N;
		answer = N + M2 / 4;
	}

	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 256
k = int(input())
if(k==1 or k==7):
    print(1)
    exit()
if(k%2==0):
    print(-1)
    exit()
x = 7
ans = None
for i in range(2,10**6+5):
    nex_x = 10*x+7
    nex_x = nex_x%k
    if(nex_x==0):
        ans = i
        break
    x = nex_x
    
if(ans is None):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9196
n,d=map(int,input().split())
l=[]
for _ in range(n):
    x=list(map(int,input().split()))
    l.append(x)
cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        num=0
        for k in range(d):
            num+=(l[i][k]-l[j][k])**2
        num=num**(1/2)
        if num==int(num):
            cnt+=1
print(cnt)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int memo[1005][1005],n,m,strain[1005],dis[1005],ans;
int solve(int dp,int days);

int main(){
    for(int i=0;i<n;i++)strain[i]=0,dis[i]=0;
    fill(memo[0],memo[1005],-1);
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> dis[i];
    for(int i=0;i<m;i++)
        cin >> strain[i];

    cout << solve(0,0) << endl;
return 0;
}

int solve(int dp,int days){
    if(n==dp)return 0;
    else{
        if(days==m)return 100010001000;
        if(memo[dp][days]!=-1)return memo[dp][days];
        return memo[dp][days]=min(solve(dp+1,days+1)+strain[days]*dis[dp],solve(dp,days+1));
    }

}

Measured memory_bytes: 7008
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long;
using P = pair<int, int>;
using lP = pair<ll, ll>;
using fP = pair<double, double>;
ll const mod = 998244353;
const ll MAX = 300000;
using vi = vector<int>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvp = vector<vector<P>>;
int main() {

    int n;
    string s;
    cin >> n >> s;
    vi l(n + 1), r(n + 1);
    l[0] = 0, r[n] = 0;
    rep(i, n) {
        if (s[i] == 'W') {
            l[i + 1] = l[i] + 1;
        }
        else l[i + 1] = l[i];
        if (s[n - 1 - i] == 'E') {
            r[n - 1 - i] = r[n - i] + 1;

        }
        else r[n - 1 - i] = r[n - i];
    }
    int ans = INF;
    rep(i, n) {
        ans = min(ans, l[i] + r[i + 1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3076
use std::collections::VecDeque;
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let a: Vec<u32> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut b = VecDeque::new();
    for i in 0..n {
        if i % 2 == 0 {
            b.push_back(a[i]);
        } else {
            b.push_front(a[i]);
        }
    }

    let mut b: Vec<u32> = b.into_iter().collect();
    if n % 2 == 1 {
        b.reverse();
    }
    let mut out = Vec::new();
    for i in 0..n {
        writeln!(out, "{}", b[i]).ok();
    }
    stdout().write_all(&out).unwrap();
}


Measured memory_bytes: 15480
class Prime:
    def __init__(self,number):#N以下の素数
        self.jud=[True]*(number+5)
        self.pri=[]
        self.jud[0]=False
        self.jud[1]=False
        for i in range(number):
            if self.jud[i]:
                self.pri.append(i)
                for j in range(2,(number-1)//i+1):
                    self.jud[i*j]=False
    
    def judge(self,x):
        return self.jud[x]
    
    def decom(self,x):
        s=x
        a =[]
        if s==1:
            return a
        while s>1:
            for p in self.pri:
                if s%p==0:
                    a.append(p)
                    s=s//p
                    break
        return a
            

from collections import defaultdict
dd=defaultdict(int)
N = int(input())
mod =10**9+7
P=Prime(10**3)
for i in range(1,N+1):
    for s in P.decom(i):
        dd[s]+=1
ans = 1
for i in dd.values():
    ans *= i+1
    ans %= mod
print(ans)

Measured memory_bytes: 3316
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	int r;
	std::cin >> r;
	print(3*r*r);
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main (String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		
		int num=0;
		for(int i=1;i<=9;i++){
		    if(N<=i*100+i*10+i){
		        num=i*100+i*10+i;
		        break;
		    }
		        
		}
		System.out.println(num);
		
	}
}

Measured memory_bytes: 22612