akhauriyash/Code-Regression huggingface dataset:
//bayemirov
#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;

#define pb push_back

const int N = 3e5;

vector<int> adj[N];
int sz[N], k;
bool was[N];

void dfs(int v) {
	was[v] = 1;
	sz[k]++;
	for (auto to : adj[v])
		if (!was[to])
			dfs(to);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
   int n, m;
   cin >> n >> m;
   while (m--) {
   	int u, v;
   	cin >> u >> v;
   	adj[u].pb(v);
   	adj[v].pb(u);
   }
   int ans = 0;
   for (int i = 1; i <= n; i++) {
   	if (!was[i]) {
   		++k;
   		dfs(i);
   		ans = max(ans, sz[k]);
   	}
  	}
  	cout << ans;
   return 0;
}

Measured memory_bytes: 23364
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()
b = LI()
b.sort()
c = LI()
c.sort()
A = []
B = []
ans = 0
for i in b:
    r = br(c,i)
    B.append(n-r)
B = [0] + list(accumulate(B))
for i in a:
    r = br(b,i)
    ans += B[-1] - B[r]
print(ans)

Measured memory_bytes: 100068
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;
ll gcd(ll a,ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}

int main(){
  ll n,X;
  cin >> n >> X;
  vector<ll> x(n);
  rep(i,n){
    int y; cin >> y;
    x.at(i) = abs(X-y);
  }

  sort(all(x));

  ll ans = x.at(0);

  for(int i=0;i<n;i++){
    ans = gcd(ans,x.at(i));
  }

  cout << ans << endl;


}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

int main() {
  long N;
  std::string S;

  std::cin >> N;
  std::cin >> S;

  std::vector<size_t> westers(N+1);
  std::vector<size_t> easters(N+1);

  westers[0] = 0;
  for (size_t i=1; i<N+1; i++) {
    westers[i] = westers[i-1] + (S[i-1] == 'W' ? 1 : 0);
  }

  easters[N] = 0;
  for (size_t i=N; i>0; i--) {
    easters[i-1] = easters[i] + (S[i-1] == 'E' ? 1 : 0);
  }

  size_t ans = N+1;

  for (size_t i=0; i<N+1; i++) {
    size_t n = westers[i] + easters[i];
    if (ans > n) ans = n;
  }

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 5380
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 n,k;
  cin >> n >> k;
  set<int> st;
  rep(i,k) {
    in6 d;
    cin >> d;
    rep(j,d) {
      in6 a;
      cin >> a;
      st.insert(a);
    }
  }
  cout << n - st.size();
  hinata;
}

Measured memory_bytes: 3664
import operator

N, K = map(int, input().split())
A = list(map(int, input().split()))

k = [((K+1)&(1<<i))>>i for i in range(40)]

m = [0]*40
for i in range(40):
	c = 0
	for a in A:
		c += (a&(1<<i))>>i
	
	if N < 2*c:
		m[i] = 0
	else:
		m[i] = 1

f = 0
b = [1<<i for i in range(40)]
for i in range(40):
	if k[i]==1:
		x = sum(map(operator.mul, m[:i]+[0]+k[i+1:], b))
		f = max(f, sum([x^a for a in A]))

print(f)

Measured memory_bytes: 14748
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _i in range(n)]

result = []
for i in range(2**n):
    num = i
    memo = [0 for _ in range(m)]
    cost = 0
    for j in range(n):
        if num%2==1:
            cost += a[j][0]
            for s in range(m):
                memo[s] += a[j][s+1]
        num >>= 1
    if all(i >= x for i in memo):
        result.append(cost)

if len(result)==0:
    print(-1)
else:
    print(min(result))

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


/*#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/

/// Typedef
typedef long long           ll;
typedef unsigned long       ul;
typedef unsigned long long  ull;
typedef vector<int>         vi;
typedef vector<ll>          vl;
typedef vector<vi>          vvi;
typedef vector<ll>          vll;
typedef pair<int,int>       pii;
typedef pair<ll,ll>         pll;

#define pb                  push_back
#define ppb                 pop_back
#define MP                  make_pair
#define ff                  first
#define ss                  second
#define sf                  scanf
#define pf                  printf
#define loop(i, y)          for(int i=0; i<int(y); i++)
#define FOR(i, x, y)        for(int i=int(x); i<int(y); i++)
#define ROF(i, x, y)        for(int i=int(x); i>=int(y); i--)
#define all(c)              c.begin(), c.end()
#define sz(c)               int(c.size())
#define clr(x, y)           memset(x, y, sizeof(x))
#define si(x)               scanf("%d", &x)
#define sii(x, y)           scanf("%d %d", &x, &y)
#define siii(x, y, z)       scanf("%d %d %d", &x, &y, &z)
#define sl(x)               scanf("%lld", &x)
#define sll(x, y)           scanf("%lld %lld", &x, &y)
#define slll(x, y, z)       scanf("%lld %lld %lld", &x, &y, &z)
#define MAX                 10005
#define MOD                 1000000009
#define base                1000000007
#define eps                 1e-9
#define INF                 1llu<<61    // 2,305,843,009,213,693,952
#define inf                 1<<29       // 536,870,912
#define PI                  acos(-1.0)  // 3.1415926535897932
// #define INF              0x3f3f3f3f3f3f3f3f
// #define inf              0x3f3f3f3f

int ara[13][13],p[13];
int main(){
    #ifdef VAMP
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    string str;
    cin>>str;
    int w=0;
    FOR(i,0,sz(str)){
        if(str[i]=='o')w++;
    }
    if(w>=8)pf("YES\n");
    else{
        int need = (8-w);
        if(need<=(15-sz(str)))pf("YES\n");
        else pf("NO\n");
    }
    #ifdef VAMP
       printf("\n>>Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
      	
      	if("ABC".equals(str)){
          System.out.println("ARC");
        }else{
          System.out.println("ABC");
        }
    }
}

Measured memory_bytes: 26964
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        int n = in.nextInt();
        int[] a = readInt(n);           // dish
        int[] b = readInt(n);           // points
        int[] c = readInt(n - 1);       // extra points
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans += b[a[i] - 1];
            if(i > 0 && a[i] - 1 == a[i - 1]){
                ans += c[a[i - 1] - 1];
            }
        }
        println(ans);
        in.close();
        out.close();
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static int[] readInt(int N) throws IOException { 
    	int arr[] = new int[N];
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    	return arr;
    }
    
    static long[] readLong(int N) throws IOException { 
    	long arr[] = new long[N];
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    	return arr;
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i] + " "); 
    	} 
    	println(""); 
    }
    
    static void displayRuntime(long startTime){
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Runtime: " + elapsedTime / 1000D);
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}


Measured memory_bytes: 25452
#include<cstdio>
#include<cmath>
#include<algorithm>
int a[150], s[2];
bool cmp(int a, int b){
	return a>b;
}
int main(){
	int n, ans;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	std::sort(a+1, a+n+1, cmp);
	for(int i=1; i<=n; i++){
		if(i&1) s[1]+=a[i];
		else s[0]+=a[i];
	}
	ans=abs(s[0]-s[1]);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
//Author ::  ABHINAV3010 ::

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define fast ios_base::sync_with_stdio(false)
typedef long long ll;
typedef pair<ll,ll> p;
ll mod=1000000007;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
int main()
{
fast;
ll a,b,c;
cin>>a>>b>>c;
ll dif=a-b;
if(dif>=c)
{
    cout<<0<<endl;
}else
{
    c=c-dif;
    cout<<c<<endl;
}
return 0;
}


Measured memory_bytes: 256
from collections import Counter

n=int(input())
*a,=map(int,input().split())

def sieve(n):
    res=list(range(n))

    i=2
    while i*i<n:
        if res[i]<i:
            i+=1
            continue

        for j in range(i*i,n,i):
            if res[j]==j:
                res[j]=i
        i+=1
    
    return res
min_factor=sieve(10**6+1)
def factor(x):
    res=set()
    while x>1:
        res.add(min_factor[x])
        x//=min_factor[x]
    
    return list(res)

lst=[]

for aa in a:
    lst+=factor(aa)

cnt=list(Counter(lst).items())

if len(cnt)==len(lst):
    print('pairwise coprime')
else:
    for k,v in cnt:
        if v==n:
            print('not coprime')
            exit(0)
    
    print('setwise coprime')


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

class SegTree {
    using T = long long;
    static const T& op(const T& lhs, const T& rhs) { // binary operator
        return max(lhs, rhs);
    }
    constexpr static T unit = -1LL<<60; // unit element
    const int N;
    T *data;
    static int calc_size(int sz) {
        int n = 1;
        while (sz > n) n *= 2;
        return n;
    }
public:
    explicit SegTree(int sz) : N(calc_size(sz)) {
        data = new T[2*N-1];
    }
    ~SegTree() { delete[] data; }
    T query(int a, int b, int i = -1, int l = -1, int r = -1) const {
        if (i == -1) { i = 0; l = 0; r = N; }
        if (r <= a || b <= l) return unit; // need this if a query can be empty
        if (a <= l && r <= b) return data[i];
        int m = (l+r)/2;
        if (b <= m) return query(a, b, 2*i+1, l, m);
        if (m <= a) return query(a, b, 2*i+2, m, r);
        T v1 = query(a, b, 2*i+1, l, m),
          v2 = query(a, b, 2*i+2, m, r);
        return op(v1, v2);
    }
    T get(int i) const {
        return data[i + N - 1];
    }
    void update(int i, T v) {
        int x = i + N - 1;
        data[x] = v;
        while (x > 0) {
            x = (x-1)/2;
            data[x] = op(data[2*x+1], data[2*x+2]);
        }
    }
};

int main() {
    int n; cin >> n;
    pair<int, int> x[n];
    for (int i = 0; i < n; i++) cin >> x[i].first >> x[i].second;
    sort(x, x+n);
    int u[n];
    u[n-1] = n;
    SegTree st(n+1);
    st.update(n-1, n);
    for (int i = n-2; i >= 0; i--) {
        int j = upper_bound(x+i, x+n, make_pair(x[i].first+x[i].second, -1)) - x;
        if (i == j-1) u[i] = i+1;
        else u[i] = st.query(i, j);
        st.update(i, u[i]);
    }
    long long dp[n+1];
    const int M = 998244353;
    dp[n] = 1;
    dp[n-1] = 2;
    for (int i = n-2; i >= 0; i--) dp[i] = (dp[i+1] + dp[u[i]]) % M;
    cout << dp[0] << endl;
}


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

using namespace std;

const int MAXN = 100 + 10;
const int INF = (int)(1e9);

void run() {
    int n;
    cin >> n;
    vector<long long> a(n), s(n, 0);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    s[0] = a[0];
    for(int i = 1; i < n; ++i) s[i] = s[i - 1] + a[i];
    vector<bool> ok(n, false);
    ok[n - 1] = true;
    for(int i = n - 2; i >= 0; --i) {
        ok[i] = (ok[i + 1] && (a[i + 1] <= s[i] * 2));
    }
    int res = 0;
    for(int i = 0; i < n; ++i) {
        if (ok[i])
            ++res;
    }
    cout << res << endl;
}

int main()
{
    //freopen("input.txt", "r", stdin);

    int ntests = 1;
    //cin >> ntests;
    for(int tc = 1; tc <= ntests; ++tc) {
        run();
    }
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class UnionFind
{
private:
  vector<int> parent, rank;

public:
  UnionFind(int n)
  {
    for (int i = 0; i < n; ++i) {
      parent.push_back(i);
      rank.push_back(0);
    }
  }

  int find(int x)
  {
    if (parent[x] == x)
      return x;
    else
      return parent[x] = find(parent[x]);
  }

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if (x == y)
      return;

    if (rank[x] < rank[y]) {
      parent[x] = y;
    } else {
      parent[y] = x;
      if (rank[x] == rank[y])
	++rank[x];
    }
  }

  bool same(int x, int y)
  {
    return find(x) == find(y);
  }
};

int main()
{
  int n, m;
  while (cin >> n >> m) {
    if ((n|m) == 0)
      break;

    priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > que;
    for (int i = 0; i < m; ++i) {
      pair<int, pair<int, int> > p;
      cin >> p.second.first >> p.second.second >> p.first;
      que.push(p);
    }

    int ans = 0;
    UnionFind uf(n);
    while (!que.empty()) {
      const pair<int, pair<int, int> > p = que.top();
      que.pop();

      if (!uf.same(p.second.first, p.second.second)) {
	uf.unite(p.second.first, p.second.second);
	ans += p.first;
      }
    }

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

Measured memory_bytes: 0
s = input()
flag = True
if(s[0]!='A'):flag=False
if(s[2:-1].count('C')!=1):flag=False
for i in range(len(s)):
    if(s[i]!='A' and s[i]!='C' and s[i].lower()!=s[i]):flag=False
if flag:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<numeric>
//#include <boost/math/common_factor.hpp> 
#define int long long
#define ld long double
#define all(x) x.begin(),x.end()
const int maxn=1000000;
#define what_is(x) cerr << #x << " is " << x << endl;
const int MOD = 1e9 + 7;
using namespace std;
string abc="abcdefghijklmnopqrstuvwxyz";
int powmod(int a, int b, int MOD = MOD){
    if(!a and !b)    return 1ll;
    if(!a)    return a;
    int res = 1ll;
    b %= (MOD - 1ll), a %= MOD;
    while(b){
        if(b%2 == 1)    res = (res * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}
int popcount(uint32_t n)
{
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
bool check(int n) {return (((double)sqrt(n)-floor((double)sqrt(n)))==0);}
vector<bool> sieve(maxn + 1, true);
void fillprime() {
    sieve[0] = sieve[1] = false;
    for (int i = 2; i <= maxn; ++i) {
        if (sieve[i] && (int) i * i <= maxn) {
            for (int j = i * i; j <= maxn; j += i) {
                sieve[j] = false;
            }
        }
    }
}
const int nn=1e5+5;
void solve() {
     int n;
     cin>>n;
     if(n%2!=0) cout<<0;
     else 
     {
         int ans=n/10;
         int p=50;
         while(n/p>0)
         {
             ans+=n/p;
             p*=5;
         }
         cout<<ans;

     }

    
}
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //fillprime();
    //int t;cin>>t;while(t--)
    solve();
}

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

int main()
{
    int A,B;

    cin>>A>>B;

    if(A==1||B==1)
        if(A==B)cout<<"Draw\n";
        else if(A==1)cout<<"Alice\n";
        else cout<<"Bob\n";
    else if(A==B)cout<<"Draw\n";
    else if(A>B)cout<<"Alice\n";
    else
        cout<<"Bob\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> P;

int INF = 1e7;
int n, m;
vector<P> edge[110];
P dist[110][110];
set<P> edges;
long long ans;

void dijkstra(int s) {
  for (int i = 0; i < n; i++) {
    dist[s][i] = P(INF, -1);
  }
  dist[s][s] = P(0, -1);
  
  priority_queue<P, vector<P>, greater<P> > pq;
  pq.push(P(0, s));
  
  while (pq.size()) {
    P p = pq.top();
    pq.pop();
    int u = p.second;
    if (dist[s][u].first < p.first) continue;
    for (P np: edge[u]) {
      int v = np.first;
      int cost = np.second;
      if (dist[s][v].first > dist[s][u].first + cost) {
        dist[s][v] = P(dist[s][u].first + cost, u);
        pq.push(P(dist[s][v].first, v)); 
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    edge[a].push_back(P(b, c));
    edge[b].push_back(P(a, c));
  }
  
  for (int i = 0; i < n; i++) {
    dijkstra(i);
  }
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int pre = dist[i][j].second;
      if (pre == -1) continue;
      edges.insert(P(pre, j));
    }
  }
  
  ans = m - edges.size() / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<algorithm>
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
int const maxn=2e6+100;
int const mod=1e9+7;
ll num[maxn];
void init(){
	num[0]=1;
	for(int i=1;i<maxn;i++) num[i]=num[i-1]*i%mod;
}
ll qpow(ll m,ll n){
	ll res=1;
	while(n){
		if(n&1) res=res*m%mod;
		n>>=1;
		m=m*m%mod;
	}
	return res;
}
ll C(ll n,ll m){
	return num[n]*qpow(num[m],mod-2)%mod*qpow(num[n-m],mod-2)%mod;
}
int main(){
	init();
	ll r1,r2,c1,c2;
	scanf("%lld%lld%lld%lld",&r1,&c1,&r2,&c2);
	ll res=C(r2+c2+2,c2+1)+C(r1+c1,c1)-C(r2+c1+1,c1)-C(r1+c2+1,c2+1);
	printf("%lld\n",(res+(ll)mod*4)%mod);
}


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

int main(){
    int N; cin >> N;
    vector<int> A(N);
    vector<int> X;

    for(int i=0; i<N; i++){
    cin >> A.at(i);
    X.push_back(A.at(i));
    }

    sort(X.begin(),X.end());
    int l = X.at(N/2-1);
    int r = X.at(N/2);

    for(int i=0; i<N; i++){
        if(A.at(i) >= r )   cout << l << endl;
        else    cout << r << endl;
    }
    
}

Measured memory_bytes: 5080
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <set>
#include <bitset>
#include <cstring>
typedef long long ll;
typedef long double ld;

#define REP(i,s,n)for(ll i=s;i<(n);++i)
#define rep(i,n) REP(i,0,n)
using namespace std;
using Graph = vector<vector<int>>;
/* 4 方向への隣接頂点への移動を表すベクトル */
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
ll H, W;
ll sX, sY, gX, gY;
char maze[100];
bool reached[100];
ll sectin = 0;
ll flg = true;
vector<string>field;
ll cheese;
vector<pair<int,int>>cheeseList;
int main() {
	cin >> H >> W;
	field = vector<string>(H);
	ll sharp = 0;
	rep(i,H) {
		cin >> field[i];
		rep(j,W) {
			if (field[i][j]=='#') {
				sharp++;
			}
		}
	}
	Graph dist(H, vector<int>(W, -1));
	queue<pair<int, int>> que;
	dist[0][0] = 0;
	que.push(make_pair(0, 0));

	while (!que.empty()) {
		pair<int, int>pos = que.front();
		int x = pos.first;
		int y = pos.second;
		que.pop();

		rep(direction, 4) {
			int nextX = x + dx[direction];
			int nextY = y + dy[direction];
			if (nextX < 0 || H <= nextX || nextY < 0 || W <= nextY)continue;
			if (field[nextX][nextY] == '#')continue;

			if (dist[nextX][nextY] == -1) {
				que.push(make_pair(nextX, nextY));
				dist[nextX][nextY] = dist[x][y] + 1;
			}
		}
	}
	if (dist[H - 1][W - 1]!=-1) {
		ll ans = H * W - (sharp + dist[H-1][W-1]+1);
		cout << ans << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define watch(x) cout << (#x) << " is " << (x) << endl

typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
typedef pair< double,double> dd;
#define pb push_back
#define eb emplace_back
#define sz(a) (int)a.size()
#define all(c) c.begin(),c.end()
#define FOR(i,a,b) for(i=a; i<b; i++)
#define FORR(i,a,b) for(i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define x first
#define y second
#define mp make_pair

const int INF = 1000000007;
const long long INFLL = (ll)INF * (ll)INF;

int32_t main()
{
	IOS;
	set<string> s;
	int n;
	string str;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>str;
		s.insert(str);
	}
	cout<<(int)s.size();
	return 0;
}


Measured memory_bytes: 19108
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {

	public static void main(String[] args) {
		Task task = new Task();
		task.solve();
	}

	public static class Task {
		static final long MOD = (long) 1e9 + 7;

		public void solve() {
			Scan sc = new Scan();
			int n = (int) sc.scanLong();
			int[] arr = new int[n];
			int mx = 0;
			for (int i = 0; i < n; ++i) {
				arr[i] = (int) sc.scanLong();
				mx = Math.max(mx, arr[i]);
			}
			int mx2 = 0;
			int r = 0;
			for (int i = 0; i < n; ++i) {
				int test = Math.min(arr[i], mx - arr[i]);
				if (test > mx2) {
					r = arr[i];
					mx2 = test;
				}
			}
			System.out.println(mx + " " + r);
		}
	}

	public static class Scan {
		private byte[] buf = new byte[1024];
		private int index;
		private InputStream in;
		private int total;

		public Scan() {
			in = System.in;
		}

		public int scan() {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				try {
					total = in.read(buf);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public long scanLong() {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		public char scanChar() {
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			return (char) n;
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}
}


Measured memory_bytes: 37092
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
flag = True

for Ai in A:
    if Ai%2==0:
        if Ai%3!=0 and Ai%5!=0:
            flag = False

if flag:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int min_a, max_a, a;
    int64_t sum_a;
    cin >> a;
    sum_a = min_a = max_a = a;
    for (int i = 1; i < n; ++i) {
        cin >> a;
        if (min_a > a) min_a = a;
        if (max_a < a) max_a = a;
        sum_a += a;
    }
    cout << min_a << " " << max_a << " " << sum_a << endl;
}


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

vector<int> scores;

int main(){
	int N; cin >> N;
	scores.resize(N);
	int sum = 0;
	for (int i = 0; i < N; ++i){
		cin >> scores[i];
		sum += scores[i];
	}
	sort(scores.begin(), scores.end());
	int next = 0;
	if (sum%10 == 0) {
		for (next=0; next<N; next++) {
			if (scores[next]%10) {
				sum-=scores[next];
				break;
			}
		}
	}
	if (sum%10==0) cout << 0 << endl;
	else cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 200005
#define ll long long

void DBG() {
    cerr << "]\n";
}
template <class H, class... T> void DBG(H h, T... t) {
    cerr << h;
    if (sizeof...(t)) {
        cerr << ", ";
    }
    DBG(t...);
}
#define _DEBUG
#ifdef _DEBUG
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

int tt, n, k;
ll a[maxn];
const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);

    if (a[n - 1] == 0 && k % 2) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    if (a[n - 1] < 0 && k % 2) {
        for (int i = n - 1; i >= (n - k); i--) {
            ans = ans * a[i] % mod;
        }
        cout << (ans + mod) % mod << endl;
        return 0;
    }
    int i = 0, j = n - 1;
    if (k % 2) {
        ans = ans * a[j] % mod;
        j--, k--;
    }
    for (int l = 0; l < (k / 2); l++) {
        ll t1 = a[i] * a[i + 1];
        ll t2 = a[j] * a[j - 1];
        if (t1 >= t2) {
            t1 %= mod;
            ans = ans * t1 % mod;
            i += 2;
        }
        else {
            t2 %= mod;
            ans = ans * t2 % mod;
            j -= 2;
        }
    }
    cout << (ans + mod) % mod << endl;
    return 0;
}

Measured memory_bytes: 5132
n = int(input())
prime = [2]
A = 55555
for L in range(3, A, 2):
    for L2 in prime:
        if L % L2 == 0:
            break
    else:
        prime.append(L)

cnt=0
ans=[]
for p in prime:
    if p%5==1:
        ans.append(p)
        cnt+=1
    if cnt==n:
        break
print(*ans)

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

int main(){
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size()-1] == b[0] && b[b.size()-1] == c[0])cout << "YES" << endl;
	else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
n1, nn = [], []
m.times do
  a, b = gets.split.map(&:to_i)
  n1 << b if a == 1
  nn << a if b == n
end

puts (n1 & nn).empty? ? 'IMPOSSIBLE' : 'POSSIBLE'

Measured memory_bytes: 9836
t,*s=gets.chomp.split(?T,-1).map(&:size)
k=gets.split.map &:to_i
k[0]-=t
s,*t=s.each_slice(2).to_a
s=(s||[]).zip(*t).map{|e|e.compact.sort_by &:-@}
puts 2.times.all?{|i|(s[i^1]||[]).map{|e|k[i]+=e*(k[i]<0?1:-1)};k[i]==0}?:Yes: :No

Measured memory_bytes: 4220
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>
#include <iomanip>

using namespace std;

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

	int  n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n - 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n - 1; i++) {
		cin >> c[i];
	}

	int ans = b[a[0]-1];
	int pre = a[0];
	for (int i = 1; i < n; i++) {
		ans += b[a[i]-1];
		if (a[i] - pre == 1) {
			ans += c[pre-1];
		}
		pre = a[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=100+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
}
int u[N],v[N],w[N],cnt;
void work()
{
	int L=read<int>();
	int k=0;
	while(1<<k <= L)k++;
	For(i,0,k-2)
	{
		u[++cnt]=i+1,v[cnt]=i+2,w[cnt]=1<<i;
		u[++cnt]=i+1,v[cnt]=i+2,w[cnt]=0;
	}
	Fordown(i,k-2,0)if((L>>i)&1)
	{
		u[++cnt]=i+1,v[cnt]=k,w[cnt]=L>>(i+1)<<(i+1);
	}
	printf("%d %d\n",k,cnt);
	For(i,1,cnt)printf("%d %d %d\n",u[i],v[i],w[i]);
}
int main()
{
//	file();
	work();
	return 0;
}


Measured memory_bytes: 256
h, w = map(int, input().split())
if not h%3 or not w%3:
  print(0)
else:
  ans = min([h, w])
  for i in range(h):
    sub = max([abs(w*i-w//2*(h-i)), abs(w*i-(w-w//2)*(h-i))])
    if ans > sub:
      ans = sub
  for i in range(w):
    sub = max([abs(h*i-h//2*(w-i)), abs(h*i-(h-h//2)*(w-i))])
    if ans > sub:
      ans = sub
  print(ans)


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
#define nil -1

struct node{
	int p,l,r;
};

node A[27];
int n,D[27],H[27];

void printsib(int i){
	cout << "sibling = ";
	if(A[i].p==nil){
		cout << "-1, ";
		return;
	}
	int Lsib=A[A[i].p].l;
	int Rsib=A[A[i].p].r;
	cout << (i==Lsib? Rsib:Lsib)<< ", ";
}

void dep(int root,int d){
	D[root]=d;
	if(A[root].l!=nil){
		dep(A[root].l,d+1);
	}
	if(A[root].r!=nil){
		dep(A[root].r,d+1);
	}
}

void degree(int i){
	printf("degree = ");
	if(A[i].l==nil&&A[i].r==nil){
		printf("0, ");
	}
	else if(A[i].l!=nil&&A[i].r!=nil){
		printf("2, ");
	}
	else{
		printf("1, ");
	}
	
}

int hei(int root){
	int h1=0,h2=0;
	if(A[root].l!=nil){
		h1=hei(A[root].l)+1;
	}
	if(A[root].r!=nil){
		h2=hei(A[root].r)+1;
	}
	return H[root]=max(h1,h2);
}

void print(void){
	for(int i=0;i<n;i++){
		printf("node %d: parent = %d, ",i,A[i].p);
		printsib(i);
		degree(i);
		printf("depth = %d, ",D[i]);
		printf("height = %d, ",H[i]);
		if(A[i].p==nil){
			cout <<"root";
		}
		else if(A[i].l==nil&&A[i].r==nil){
			cout<<"leaf";
		}
		else{
			cout <<"internal node";
		}
		cout<<endl;
	}
}

int main() {
	cin>>n;
	int v,L,R,root;
	for(int i=0;i<n;i++){
		A[i].p=A[i].l=A[i].r=nil;
	}
	for(int i=0;i<n;i++){
		cin>>v>>L>>R;
		A[v].l=L;A[v].r=R;
		if(L!=nil){A[L].p=v;}
		if(R!=nil){A[R].p=v;}
	}
	for(int i=0;i<n;i++){
		if(A[i].p==nil){
			root=i;
		}
	}
	dep(root,0);
	hei(root);
	print();
	return 0;
}


Measured memory_bytes: 3148
a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0
for a in range(a+1):
    for b in range(b+1):
        for c in range(c+1):
            if (500*a) + (100*b) + (50*c) == x:
                cnt += 1

print(cnt)                 


Measured memory_bytes: 3060
N = int(input())
s = [input() for i in range(N)]

M = int(input())
t = [input() for i in range(M)]

count_max = 0
for i in range(N):
    count = s.count(s[i]) - t.count(s[i])
    if count > count_max:
         count_max = count
            
print(count_max)


Measured memory_bytes: 3060
def euclidean_distance(p1, p2)
  sum_of_squares = 0
  p1.each_with_index do |p1_coord, index|
    sum_of_squares += (p1_coord - p2[index]) ** 2
  end
  Math.sqrt(sum_of_squares)
end

gets.to_i.times do
  input = gets.split.map(&:to_f)
  center_a = input[0..1]
  radius_a = input[2]
  center_b = input[3..4]
  radius_b = input[5]

  distance = euclidean_distance(center_a, center_b)

  if distance > radius_a + radius_b
    puts 0 # A and B do not overlap
  elsif radius_a > radius_b + distance
    puts 2 # B is in A
  elsif radius_b > radius_a + distance
    puts -2 # A is in B
  else
    puts 1 # A and B intersect
  end
end

Measured memory_bytes: 6896
inp=input().split()
N,A,B=[int(n) for n in inp]
S=input()

total=0
total2=0
for i,s in enumerate(S):
    if s=='a':
        if total<A+B:
            print('Yes')
            total +=1
        else:
            print('No')
    elif s=='b':
        if total<A+B and total2<B:
            print('Yes')
            total2+=1
            total +=1
        else:
            print('No')
    else:
        print('No')


Measured memory_bytes: 4016
#include <stdio.h>
int main(void){    
int a,b,c,n;    
int count_n = 0;    
scanf("%d %d %d", &a, &b, &c);    
for(n = a; n <= b; n++) {  
if(c % n == 0) {    
count_n += 1;  }} 
printf("%d\n", count_n);      

return 0;
}


Measured memory_bytes: 2140
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    V<int> imos(101,0);
    imos[a]++;imos[b]--;
    imos[c]++;imos[d]--;
    for(int i=1;i<=100;i++) imos[i]+=imos[i-1];
    int ans=0;
    for(int i=0;i<=100;i++){
        if(imos[i]==2) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
from collections import Counter
n=int(input())
s=set()
d={}

for i in range(n):
  st=input()
  b={i for i in st}
  d[i]=Counter(st)
  if not i:
    s=s|b
  else:
    s=s&b

buf=""
l=sorted(s)
for j in l:
  buf+=j*min([i[j] for i in d.values()])
print(buf)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int a[1000005];
int len_p[100005];
int len_m[100005];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n-1;i++){
		if(a[i]>a[i+1])len_m[i]++;
		if(a[i]<a[i+1])len_p[i]++;
	}
	for(int i=n-1;i>=0;i--){
		if(len_m[i]>0){
			len_m[i]+=len_m[i+1];
		}
		if(len_p[i]>0){
			len_p[i]+=len_p[i+1];
		}
		if(len_m[i]==0 && len_p[i]==0){
			len_m[i]+=len_m[i+1];
			len_p[i]+=len_p[i+1];
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		res=max(res,len_p[i]+len_m[i]);
	}
	printf("%d\n",res+1);
	return 0;
}

Measured memory_bytes: 4352
#include<iostream>
 #include<vector>
 using namespace std;
 int main(int arg, char* argv[]) {
    int n = 0;
    cin >> n;
    vector<int> f(45,0);
    f[0] = 1; f[1] = 1;
    for(int i = 2; i <= n; i++){
      f[i] = f[i-1] + f[i-2];
    }
   cout << f[n] << endl;
 }

Measured memory_bytes: 3072
N, K, Q = map(int, input().split())

l = [0] * N

for i in range(Q):
	ind = int(input())
	l[ind-1] += 1


K_ = [K] * N

fin = list(map(lambda x: "Yes" if x[0] - Q + x[1] > 0 else "No", zip(K_, l)))

print("\n".join(fin))

Measured memory_bytes: 6692
//
//AtCoder Beginner Contest 079
//C
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>
#include <numeric>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

int calc(int f, int x, int y){
    if (f==0) return x+y;
    else return x-y;
}
int main()
{
    int abcd;
    cin >> abcd;
    int d = abcd%10; abcd/=10;
    int c = abcd%10; abcd/=10;
    int b = abcd%10; abcd/=10;
    int a = abcd%10;

    REP(i,2)REP(j,2)REP(k,2){
        if (calc(k,calc(j,calc(i,a,b),c),d)==7){
            cout << a << ((i==0) ? "+" : "-") ;
            cout << b << ((j==0) ? "+" : "-");
            cout << c << ((k==0) ? "+" : "-");
            cout << d << "=7" << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define forloop(n) for(int i = 0; i < n; i++)
#define ll long long
/*ll sum(vector<ll> vec, int left, int right){
	if(right == left){
		return vec[0];
	}
	return vec[right] + sum(vec, left, right-1);
}*/
int main(){
	int n; cin>>n;
	ll res = 0, sum = 0;
	forloop(n){
		ll a,b; cin>>a>>b;
		sum += a*b;
		res += b;
	}
	cout<< (sum-1)/9 + res-1;
	return 0;
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;

int main(){
    int N; cin >> N;
    vector<int> l(N), r(N); REP(i, N) cin >> l[i] >> r[i];

    int cnt = 0;
    REP(i, N) {
        for(int j = l[i]; j <= r[i]; ++j) {
            cnt++;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
n = int(input())

dp = [i for i in range(n+1)]
dp[1] = 1
if n >= 6:
    dp[6] = 1
if n >= 9:
    dp[9] = 1
for i in range(1, n+1):
    for j in range(7):
        if i - 6**j >= 0:
            dp[i] = min(dp[i], dp[i - 6**j] + 1)
    for j in range(6):
        if i - 9**j >= 0:
            dp[i] = min(dp[i], dp[i - 9**j] + 1)
print(dp[n])

# dp[i] = i円を引き出すのに必要な最低回数
# dp[i] = min(dpcd [i-6**p]+1,dp[i-9**q],dp[i])

Measured memory_bytes: 7064
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

#include <typeinfo>

using namespace std;

int main(){
  int N,K,X,Y;
  cin >> N >> K >> X >> Y;
  int summing = 0;
  if(N <= K){
    summing = N*X;
  }else{
    summing = K*X;
    summing += (N - K)*Y;
  }
  cout << summing << endl;
  return 0;
}


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

int main() {
  string s;
  cin>>s;
  long int x,ans;
  x=ans=0;
  for(long int i=0;i<s.size();i++){
    if(s.at(i)=='B')x++;
    if(s.at(i)=='W')ans+=x;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<algorithm>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int dp[4000][4000];
int b[4000];
int sum[4000];

int main() {
	int n, m; cin >> n >> m;
	string s; cin >> s;
	vector<P>v;
	for (int i = 0; i < m; i++) {
		int l, r; scanf("%d%d", &l, &r); l--; r--;
		if (v.empty())v.push_back(P(l, r));
		else if (v.back().first == l)v.back().second = max(v.back().second, r);
		else if (v.back().second < r)v.push_back(P(l, r));
	}
	for (auto p : v)b[p.first] = p.second;
	for (int i = 1; i < n; i++)b[i] = max({ i,b[i],b[i - 1] });
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '1')cnt++;
		sum[i] = cnt;
	}
	dp[0][cnt] = 1;
	for (int i = 0; i < n; i++)for (int j = 0; j < cnt + 1; j++) {
		if (dp[i][j] == 0)continue;
		int a = j - (sum[n - 1] - sum[b[i]]);
		if (a)(dp[i + 1][j - 1] += dp[i][j]) %= MOD;
		if (b[i] - i + 1 - a)(dp[i + 1][j] += dp[i][j]) %= MOD;
	}
	cout << dp[n][0] << endl;

	return 0;
}

Measured memory_bytes: 45952
N, X = map(int, input().split()) # 横に2個

X = X if 2*X <= N else N - X
a = X
b = (N-X)//X
c = (N-X)%X
ans = 0
while True:
    ans += a*b*3
    if c == 0:
        break
    a, b, c = c, a//c, a%c

print(ans)

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  float a, b;
  cin >> a >> b;
  cout << ceil((a + b) / 2) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 +c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,M;
char s[1005][1005];
int dis[1005][1005];
bool vis[1005][1005];
queue<pii > Q;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
void Solve() {
    read(N);read(M);
    for(int i = 1 ; i <= N ; ++i) {
        scanf("%s",s[i] + 1);
        for(int j = 1 ; j <= M ; ++j) {
            if(s[i][j] == '#') {
                Q.push(mp(i,j));
                vis[i][j] = 1;
            }
        }
    }
    int ans = 0;
    while(!Q.empty()) {
        pii u = Q.front();Q.pop();
        ans = max(dis[u.fi][u.se],ans);
        for(int k = 0 ; k < 4 ; ++k) {
            int tx = u.fi + dx[k],ty = u.se + dy[k];
            if(tx >= 1 && tx <= N && ty >= 1 && ty <= M) {
                if(!vis[tx][ty]) {
                    vis[tx][ty] = 1;
                    dis[tx][ty] = dis[u.fi][u.se] + 1;
                    Q.push(mp(tx,ty));
                }
            }
        }
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

Measured memory_bytes: 11008
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int>p(m);
    vector<string>s(m);
    REP(i,m)cin >> p[i] >> s[i];
    map<int,int>ac,wa;
    vector<int>wrong(n);
    REP(i,n)wrong[i]=0;
    int aca=0,waa = 0;
    REP(i,m){
        if(ac[p[i]]==0){
            if(s[i]=="AC"){
                ac[p[i]]++;
                aca++;
                wa[p[i]]=wrong[p[i]];
                waa += wrong[p[i]];
            }
            else{
                wrong[p[i]]++;
            } 
        }
    }
    cout << aca << " " << waa << endl;
    return 0;
}

Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI (3.1415926535897932384)

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>void tf(bool b,S t,T f){if(b)puta(t);else puta(f);}
void YN(bool b){tf(b,"YES","NO");}
void Yn(bool b){tf(b,"Yes","No");}
void yn(bool b){tf(b,"yes","no");}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1;for(auto s:t){os<<(a?"":" ")<<s;a=0;}return os;}
template<class S>auto&operator>>(istream&is,vector<S>&t){for(S&a:t)cin>>a;return is;}

/*他のライブラリを入れる場所*/


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,d;
	cin>>n>>d;
	int ans=0;
	while(n){
		n-=d*2+1;
		ans++;
		chmax(n,0ll);
	}
	puta(ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;

int N;

int main() {
  cin >> N;
  long mp[5] = {0L};
  for (int i=0; i<N;i++) {
    string s;
    cin >> s;
    if (s.at(0) == 'M') {
      mp[0]++;
    } else if (s.at(0) == 'A') {
      mp[1]++;
    } else if (s.at(0) == 'R') {
      mp[2]++;
    } else if (s.at(0) == 'C') {
      mp[3]++;
    } else if (s.at(0) == 'H') {
      mp[4]++;
    }
  }
  long ans = 0;
  for (int i=0; i<3; i++) {
    for (int j=i+1; j<4; j++) {
      for (int k=j+1; k<5; k++) {
        ans += mp[i]*mp[j]*mp[k];
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256