akhauriyash/Code-Regression huggingface dataset:
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX = 2e5 + 5;
const int MOD = 1e9+7;

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))
ll POW(ll a, ll b, bool usemod = true) {ll c = 1LL; while (b > 0) {if (b & 1LL) {if(!usemod)c*=a;else c = a * c%MOD;}if (!usemod) a*=a;else a = a * a%MOD; b >>= 1LL;}return c;}

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }


int N, K;
ll c[2010][2010];

int main() {
    cin >> N >> K;
    
	REP(i,2010){
		c[i][0]=1;
		c[i][i]=1;
	}
	for(int i=1;i<2010;i++){
		for(int j=1;j<i;j++){
			c[i][j]=c[i-1][j-1]+c[i-1][j];
			c[i][j]%=MOD;
		}
	}

    for(int i=1;i<=K;i++){
        print((c[N-K+1][i]*c[K-1][i-1])%MOD);
    }

    return 0;
}


Measured memory_bytes: 30336
function Main(input) {
  input = input.split("\n");
  n = Number(input[0].split(" "));
  a = input[1].split(" ").map(Number);
  b = input[2].split(" ").map(Number);
  c = input[3].split(" ").map(Number);
  var ans=0;
  for(var i=0; i<n; i++){
    ans+=b[a[i]-1];
    if(a[i] == a[i-1]+1){
      ans+=c[a[i-1]-1];
    }
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
using System;

namespace A___Sandglass2
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');
            var x = int.Parse(input[0]);
            var t = int.Parse(input[1]);
            if (x > t)
            {
                Console.WriteLine(x - t);
            }
            else
            {
                Console.WriteLine(0);
            }
        }
    }
}

Measured memory_bytes: 11092
from collections import deque
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(m)]
ans = n*(n-1)//2
check = [ans]
class Unionfind:
    
    def __init__(self,n):
        self.uf = [-1]*n

    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]

    def same(self,x,y):
        return self.find(x) == self.find(y)

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]


uf = Unionfind(n)
for i,j in l[::-1]:
    if uf.same(i-1,j-1) == False:
        ans -= uf.size(i-1)*uf.size(j-1)
        uf.union(i-1,j-1)
    check.append(ans)
        
for i in check[m-1::-1]:
    print(i)






Measured memory_bytes: 35780
using System;
using System.Collections.Generic;
using System.Linq;

class Progaram
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var l = Console.ReadLine().Split(' ').Select(long.Parse).OrderByDescending(x => x).ToArray();

        long res = 1;
        var count = 0;
        for (var i = 0; n - 1 > i; i++)
        {
            if (l[i] == l[i + 1])
            {
                res *= l[i];
                i++;
                count++;
            }
            if (count == 2) break;
        }

        Console.WriteLine((count == 2) ? res : 0);
    }
}

Measured memory_bytes: 26080
def amida(arr, rest):
    num=0
    if rest<1:
        return 1

    num+=amida(arr, rest-2)
    arr[-rest-1]+=num
    num+=amida(arr, rest-1)
    return num

H,W,K=list(map(int,input().split()))

arr=[0 for i in range(W+2)]
arr[1]=1

line=[0 for i in range(W+1)]
sum_=amida(line,W-1)

for i in range(H):
    tmp=arr[:]
    for j in range(1,W+1):
        arr[j]=(tmp[j]*(sum_-line[j]-line[j-1])+tmp[j+1]*line[j]+tmp[j-1]*line[j-1])%(10**9+7)
print(arr[K])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  long long N,K;
  cin>>N>>K;
  
  
  if(N==1){
    cout<<K<<endl;
  }
  else{
  long long ans=K*(K-1);
  
  for(int i=0;i<N-2;i++){
    ans*=K-1;
  }
  
  cout<<ans<<endl;
  }
}

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

int main(){
  int w, h, x, y;
  cin >> w >> h >> x >> y;
  double ans = (double)w*h/2;
  int num = (w==x*2 && h==y*2) ? 1 : 0;
  printf("%.10f %d\n", ans, num);
  
  return 0;
}

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

int main() {
    int N;
    cin >> N;
    ll L[N];
    rep (i, N) cin >> L[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                if (L[i] != L[j] && L[j] != L[k] && L[k] != L[i]) {
                    if (L[i] + L[j] > L[k] && L[j] + L[k] > L[i] && L[k] + L[i] > L[j]) {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}


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

#define INF (INT64_MAX)
#define MOD (1000000000+7)
#define MAX 1000

int N, M;
int A[MAX];
int B[MAX];
int ac[MAX*MAX + 1];
int bc[MAX*MAX + 1];

int main() {
	cin >> N >> M;
	for( int i = 0; i < N; i++ ) {
		cin >> A[i];
		ac[A[i]]++;
	}
	for( int i = 0; i < M; i++ ) {
		cin >> B[i];
		bc[B[i]]++;
	}

	long long ans = 0;
	int flag = 0;
	for( int i = 0; i < N*M + 1; i++ ) {
		if( ac[i] > 1 ) {
			flag = 1;
			break;
		}
	}
	for( int i = 0; i < N*M + 1; i++ ) {
		if( bc[i] > 1 ) {
			flag = 1;
			break;
		}
	}
	if( flag == 0 ) {
		sort( A, A + N );
		sort( B, B + M );
		ans = 1;
		for( int x = N * M; x > 0; x-- ) {
			int icnt = upper_bound( A, A + N, x ) - lower_bound( A, A + N, x );
			int jcnt = upper_bound( B, B + M, x ) - lower_bound( B, B + M, x );
			if( icnt && jcnt ) {
			}
			else if( icnt && jcnt == 0 ) {
				ans = ans * (B + M - upper_bound( B, B + M, x ) ) % MOD;
			}
			else if( icnt == 0 && jcnt ) {
				ans = ans * (A + N - upper_bound( A, A + N, x ) ) % MOD;
			}
			else {
				long long acnt = A + N - upper_bound( A, A + N, x );
				long long bcnt = B + M - upper_bound( B, B + M, x );
				ans *= ((acnt * bcnt % MOD) - (M * N - x) + MOD ) % MOD;
				ans %= MOD;
			}
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 2304
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC115A
{
    class Program
    {
        static void Main(string[] args)
        {
            int D = int.Parse(Console.ReadLine());

            if (D == 25)
                Console.WriteLine("Christmas");

            else if (D == 24)
                Console.WriteLine("Christmas Eve");

            else if (D == 23)
                Console.WriteLine("Christmas Eve Eve");

            else if (D == 22)
                Console.WriteLine("Christmas Eve Eve Eve");

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>
int main () {
  int S, h, m, s;
  scanf("%d", &S);
  h = (S/3600);
  m = ((S - 3600*h)/60);
  s = ((S - 3600*h)%60) ;
  printf("%d:%d:%d\n", h, m, s);
  return 0;
}
  

Measured memory_bytes: 1020
n,t[999];int main(i){for(;n*=scanf("%d",&n);puts("")){bzero(t,999);for(;n--;t[i]=*t)scanf(" %c %c",&i,t);for(scanf("%d",&n);n--;putchar(!t[i]*i+t[i]))scanf(" %c",&i);}exit(0);}

Measured memory_bytes: 588
package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	listK := make([]int, n)
	listA := make([][]int, n)
	countM := make([]int, m+1)
	count := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&listK[i])
		listA[i] = make([]int, listK[i])
		for j := 0; j < listK[i]; j++ {
			fmt.Scan(&listA[i][j])
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < listK[i]; j++ {
			countM[listA[i][j]]++
		}
	}
	for i := 1; i <= m; i++ {
		if countM[i] == n {
			count++
		}
	}
	fmt.Println(count)
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;

ll nCr(ll n, ll r) {
	if (r > n) { return 0; }
	if (r * 2 > n) r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i) {
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
ll sumdigit(ll n) {
	ll dig = 0, sum = 0;
	while (n) {
		dig = n % 10;
		sum = sum + dig;
		n = n / 10;
	}
	return sum;
}



int main() {
	int a, b;
	std::cin >> a >> b;
	if (a % 3 == 0 || b % 3 == 0) {
		std::cout << "Possible" << std::endl;
	}
	else if ((a + b) % 3 == 0) {
		std::cout << "Possible" << std::endl;
	}
	else {
		std::cout << "Impossible" << std::endl;
	}
}

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

int main(){
  int64_t N,cyc=0;
  string S;
  cin >> S >> N;
  char f=S.at(0);
  int a=0;
  ulong b=0;
  int64_t ans=0;
  if(N==1){
    bool ok=false;
    for(int i=0;i<S.size()-1;i++){
      if(S.at(i)==S.at(i+1)&&!ok){
        cyc++;
        ok=true;
      }else{
        ok=false;
      }
    }
    cout << cyc << endl;
    return 0;
  }
  while(a<S.size()&&S.at(a)==f){
    a++;
    b++;
  }
  if(a==S.size()){
    cout << S.size()*N/2 << endl;
    return 0;
  }
  a=S.size()-1;
  while(a>=0&&S.at(a)==f){
    a--;
    b++;
  }
  //cout << a << "/" << b << endl;
  if(b%2==1){
    bool ok=false;
    for(int i=0;i<S.size()-1;i++){
      if(S.at(i)==S.at(i+1)&&!ok){
        cyc++;
        ok=true;
      }else{
        ok=false;
      }
    }
    //cout << cyc << endl;
    ans=cyc*N;
  }else{
    int i=0,j=S.size()-1;
    while(i<N&&S.at(i)==f)
      i++;
    while(j>=0&&S.at(j)==f)
      j--;
    bool ok=false;
    for(int k=i;k<j;k++){
      if(S.at(k)==S.at(k+1)&&!ok){
        cyc++;
        ok=true;
      }else{
        ok=false;
      }
    }
    //cout << cyc << '#' << j << '/' << i << endl;
    ans=cyc*N;
    ans+=min(S.size(),S.size()-j+i)/2*(N-1)+i/2+(S.size()-j-1)/2;
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
    int N, K, X, Y;
    cin >> N >> K >> X >> Y;

    int cost = 0;
    int a = N - K;
    if(a > 0)
    {
        cost += X * K;
        cost += Y * a;
    }
    else
    {
        cost += X * N;
    }
    cout << cost;
}

Measured memory_bytes: 256
#pragma GCC target("tune=native")
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int n, m, p[N], val[N], T[2][N * 3];
char ans[N];

void modify(int *T, int p, int v) {
	for (T[p += m] = v; p >>= 1;) {
		int w = max(T[p << 1], T[p << 1 | 1]);
		if (w == T[p]) break;
		T[p] = w;
	}
}
int query(int *T, int s) {
	int res = -(2 * N);
	for (s += m; s >>= __builtin_ctz(~s); s >>= 1) res = max(res, T[s ^ 1]);
	return res;
}

bool check(int x, int y) {
	return x >= 0 && x <= query(T[x & 1], y);
}

int main() {
	scanf("%d", &n);
	m = 1;
	while (m <= n) m <<= 1;
	for (int i = 1; i <= m + n + 1; ++i) T[1][i] = -(2 * N);
	int Q = 0, mx = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", p + i);
		if (p[i] > mx) mx = p[i], val[i] = 2, ++Q;
		else val[i] = 1;
	}
	for (int i = n; i; --i) {
		int tmp[2];
		for (int j = 0; j < 2; ++j) {
			tmp[j] = query(T[j ^ val[i] & 1], p[i]) + val[i];
			if (tmp[j] < 0) tmp[j] = -(2 * N);
		}
		for (int j = 0; j < 2; ++j) modify(T[j], p[i], tmp[j]);
	}
	if (!check(Q, 0)) return puts("-1"), 0;
	int c[2] = {}, h[2] = {};
	for (int i = 1; i <= n; ++i) {
		modify(T[0], p[i], 0), modify(T[1], p[i], -(2 * N));
		Q -= val[i] - 1;
		ans[i] = !(check(Q + c[1] - (c[0] + (p[i] > h[0])), max(h[0], p[i])) || check(Q - c[1] + (c[0] + (p[i] > h[0])), h[1]));
		if (p[i] > h[ans[i]]) ++c[ans[i]], h[ans[i]] = p[i];
		ans[i] += '0';
	}
	puts(ans + 1);
	return 0;
}


Measured memory_bytes: 6656
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

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

    map<string, int> mp;

    rep(i, n){
        string s;
        cin >> s;
        mp[s]++;
    }

    int max_num = 0;

    for(auto p : mp)
    {
        max_num = max(max_num, p.second);
    }  
     
    for(auto p : mp){
        if(p.second == max_num) cout << p.first << endl;
    }

    return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

#define d(x) cerr<<#x<<"="<<x<<endl;
ll n,a,b,sum=0,ans=1;
vector<ll> v(51);
double maxmean;

std::vector<std::vector<long long>> comb(int n, int r) {
  std::vector<std::vector<long long>> v(n + 1,std::vector<long long>(n + 1, 0));
  for (int i = 0; i < v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
    }
  }
  return v;
}


int main(void){
    cin>>n>>a>>b;
    for(int i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end(), greater<ll>());
    map<int, int> m2;
    for(int i=0;i<a;i++){
        sum+=v[i];
        if(m2[v[i]])m2[v[i]]++;
        else m2[v[i]]=1;
    }
    maxmean=(double)sum/a;
    cout.precision(20);
    cout<<fixed<<maxmean<<endl;
    map<int, int> m;
    for(int i=0;i<n;i++){
        int count=0;
        if(m[v[i]])continue;
        for(int j=0;j<n;j++)if(v[j]==v[i])count++;
        m[v[i]]=count;
    }
    for(auto x: m2)ans*=comb((ll)m[x.first],(ll)x.second)[m[x.first]][x.second];
    for(int i=a;i<b;i++){
        if((double)v[i]==maxmean){
            ll tans=1;
            m2[v[i]]=m2[v[i]]+1;
            for(auto x: m2){
                tans*=comb((ll)m[x.first],(ll)x.second)[m[x.first]][x.second];
            }
            ans+=tans;
        }
        else break;
    }
    cout<<ans<<endl;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N;
    cin >> N;
    vec A(N);
    REP(i,0,N) cin >> A[i];

    ll cnt = 0;
    REP(i,0,N) {
        while(A[i] % 2 == 0) {
            A[i] /= 2;
            ++cnt;
        }
    }
    PR(cnt);

    return 0;
}

/*



*/

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

using namespace std;
using Graph = vector<vector<int>>;
using Grid= vector<vector<char>>;
using vin= vector<int>;
using ll=long long;
using vll= vector<ll>;
using vbl=vector<bool>;
using vch=vector<char>;
using pnn=pair<int ,int>;

#define ft first
#define sd second
#define fn front
#define pb push_back
#define it insert
#define si(v) int((v).size())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rell(i,n) for (ll i=0; i< (ll)(n); i++)
#define sot(x) sort(x.begin(), x.end())
#define rese(x) reverse(x.begin(), x.end())
#define vnn(x,y,s,name) vector<vector<int>> name(x, vector<int>(y,s))
#define mse(x) memset(x, 0, sizeof(x))
#define mii(x,y,z) min(x,min(y,z))
#define maa(x,y,z) max(x,max(y,z))

string yes="Yes",no="No";

int main() {
   ll n,k;
   cin>>n>>k;
   vll h(n);
   rep(i,n) cin>>h[i];
   sot(h);
   ll sum=0;
   rep(i,n-k){
       sum+=h[i];
   }
   cout<<sum<<endl;
}


Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % MOD;
      x = x * x % MOD;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    scanf("%lld", &res);
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  void in(t&x){
    cin >> x;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

vector<ll> primes(ll maxs){
  vector<int> is_prime(maxs+1,true);
  vector<ll> res;
  for(ll i=2;i<=maxs;++i){
    if(is_prime[i]){
      res.emplace_back(i);
      for(ll j=i*2;j<=maxs;j+=i){
        is_prime[j] = false;
      }
    }
  }
  return res;
}

vector<pair<long long,long long>> prime_factorize(long long x){
	using P = pair<long long,long long>;
	vector<P> res;
  vector<ll> primess = primes(2e6);
  foreach(i,primess){
    if(i*i>x)break;
		int cnt = 0;
		while(x%i==0){
			x /= i;
			++cnt;
		}
		if(cnt){
			res.emplace_back(i,cnt);
		}
	}
	if(x>1)res.emplace_back(x,1);
	return res;
}
int main(){
  ll n = in();
  vector<pll> line = prime_factorize(n);
  ll ans = 0;
  foreach(i,line){
    rep(j,1,INF){
      if(i.second<j)break;
      i.second -= j;
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 13200
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<ctype.h>
#include<cstdio>
using namespace std;
main(){
  int h,w;
  char wether[120][120];
  int time[120][120];
  cin>>h>>w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>wether[i][j];
      if(wether[i][j]=='c'){
	time[i][j]=0;
      }
      else{
	time[i][j]=-1;
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(time[i][j]!=0){
	int k=j;
	int count=0;
	while(wether[i][k]!='c'&&k>=0){
	  k=k-1;
	  count=count+1;
	}
	if(k>=0){
	   time[i][j]=count;
	}
      }
      if(j!=w-1){
	cout<<time[i][j]<<" ";
      }
      else{
	cout<<time[i][j]<<endl;
      }
    }
  }
}

Measured memory_bytes: 1224
#include<stdio.h>
#include<math.h>
int main()
{
	int n,i,min=10000000,s,j;
	scanf("%d",&n);
	int a[n];
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=100;i++)
	{
		s=0;
		for(j=0;j<n;j++)
		{
			s=s+pow((a[j]-i),2);
		}
		if(min>s)
		min=s;
	}
	printf("%d\n",min);
}

Measured memory_bytes: 128
#include <iostream>

int main() {
    using namespace std;

    int c;
    int num;
    int max ;
    int min;
    int sum;
    int ans;
    while(true){
        max = 0;
        min = 1001;
        sum = 0;
        cin >> c;
        if(c == 0){
            break;
        }
        for(int i = 0; i < c; i++){
            cin >> num;
            if(num > max){
                max = num;
            }
            if(num < min){
                min = num;
            }
            sum += num;
        }
        ans = (sum - max - min)/(c-2);
        cout << ans << "\n";
    }
    return 0;
}


Measured memory_bytes: 3068
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793
 
   
int main(){
   int  n;
   string s,t;
   cin >> n >> s >> t;
   int ans=2*n;
   rep(i,n){
       bool a=true;
       rep(j,n-i){
           if(s.at(i+j)!=t.at(j))a=false;
       }
       if(a){
           ans-=(n-i);
           break;
       }
   }
   cout << ans << endl;
} 

    

Measured memory_bytes: 3624
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.B
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var L = new List<long>();

            for (int i = 0; i <= 86; i++)
            {
                if (i == 0)
                {
                    L.Add(2);
                }
                else if (i == 1)
                {
                    L.Add(1);
                }
                else
                {
                    L.Add(L[i - 1] + L[i - 2]);
                }
            }

            return L[(int)N];
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int N, count;
	string A, B, C;
	char a, b, c;
	cin >> N >> A >> B >> C;
	count = 0;
	for (int i = 0; i < N; ++i) {
		a = A[i];
		b = B[i];
		c = C[i];
		if(a == b and b == c and c == a){
			continue;
		}
		if(a == b or b == c or c == a){
			count++;
			continue;
		}
		count+=2;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
// ABEY SAALE
// QUESTION KHUD KR SOLUTION KYU DEKH RHA H
 
 
 
 
 
 
 
 
//MAAF KIJIYEGA ME GUSSE ME IDHAR UDHAR NIKAL JATA HU
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define senky_bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;

ll fac[2000005];
void pre(){ fac[0]=1; fac[1]=1; for(int i=2;i<200005;i++) fac[i]=(i*fac[i-1])%mod;}
ll power(ll a,ll b){ll res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b=b/2;}return res%mod;}
ll ncr(ll n,ll r){return ((fac[n]*power(fac[r],mod-2))%mod*power(fac[n-r],mod-2))%mod;}
// DEKHIYE JI  WALID JO THE ABBA HAMARE WO YEH function CHHOD KR GYE THE

signed main()
{   



      
      senky_bansal
      IIIT_ALLAHABAD
      
      // pre();
      ll t;
      // cin>>t;
      t=1;
      while(t--)
      { 
         
           ll a,b,c;
           cin>>a>>b>>c;
           ll p1 = 4*a*b;
           ll p2 = (c-a-b)*(c-a-b)*1LL;
           if(c-a-b>0 && p1<p2)
            cout<<"Yes\n";
          else
            cout<<"No\n";

      }
      






}



























Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};
use std::collections::HashMap;

fn main() {
    input!{
        n: usize,
        v: [usize; n]
    }
    let mut map = HashMap::new();
    for &a in &v {
        *map.entry(a).or_insert(0) += 1;
    }
    let l = map.len();
    if l == 1 {
        if let Some(_) = map.get(&0) {
            println!("Yes");
        } else {
            println!("No");
        }
        return;
    }
    if n % 3 != 0 {
        println!("No");
        return;
    }
    let m = n / 3;
    if l > 3 {
        println!("No");
    } else if l == 3 {
        for &x in map.values() {
            if x != m {
                println!("No");
                return;
            }
        }
        let ks: Vec<usize> = map.keys().map(|x| *x).collect();
        if ks[0] ^ ks[1] == ks[2] {
            println!("Yes");
        } else {
            println!("No");
        }
    } else if l == 2 {
        if let Some(&c) = map.get(&0) {
            if c == m {
                println!("Yes");
                return;
            }
        }
        println!("No");
    }
}


Measured memory_bytes: 12540
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

ll answer[200005];

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	string s;
 	cin >> s;
 	int n = (int) s.length();

 	for (int i = 1; i <= n; i++) answer[i] = (ll) (i + 1) / 2 + answer[i - 1];

 	int len = n, pref = 0, odd = 0, even = 0;
 	for (int i = 0; i < n; i++)
 		if (i % 2 == 0) odd += s[i] - '0';
 		else even += s[i] - '0';

 	int uk = 0;
 	ll ans = 0;
 	while (uk < n)
 	{
 	 	while (uk < n && s[uk] == '0')
 	 	{
 	 		ans += (ll) (pref + odd);
 	 		swap(odd, even);
 	 		len--;
 	 		uk++;
 	 	}
 	 	pref++, odd--;
 	 	if (uk + 1 < n && s[uk + 1] == '1') even--;
 	 	uk += 2;
 	}
 	ans += answer[len];
 	cout << ans << '\n';
 	return 0;
}

Measured memory_bytes: 5344
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(start,n,g):
    visited = [-1]*(n+1)
    visited[start] = 0
    stack = deque([start])
    while stack:
        c_node = stack.pop()
        for neib, dist in g[c_node]:
            if visited[neib] != -1: continue
            visited[neib] = visited[c_node] + dist
            stack.append(neib)
    return visited
    

N = int(input())
g = [ [] for _ in range(N+1)]
visited = [-1] * (N+1)

for _ in range(N-1):
    u, v, w = map(int, input().split()) 
    w%=2
    g[u].append((v,w))
    g[v].append((u,w))

visited = dfs(1,N,g)
for p in visited[1:]:
    print(p%2)
    



Measured memory_bytes: 95172
#include <stdio.h>
#include <string.h>
 
int main() {
 
    int a, b, c, k;
    scanf("%d %d %d %d", &a, &b, &c, &k);
 
    if (a >= k) {
        printf("%d", k);
    } else if (a + b >= k) {
        printf("%d", k-b);
    } else {
        printf("%d", a - (k - a - b));
    }
 
    return 0;
} 

Measured memory_bytes: 1732
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define MAX 100000
#define INFTY (1 << 30)

class Edge {
public:
  int t, w;
  Edge(){}
  Edge(int t, int w): t(t), w(w) {}
};

vector<Edge> G[MAX];
int n, d[MAX];

bool vis[MAX];
int cnt;

void bfs(int s) {
  for ( int i = 0; i < n; i++ ) d[i] = INFTY;
  queue<int> Q;
  Q.push(s);
  d[s] = 0;
  int u;
  while ( !Q.empty() ) {
    u = Q.front(); Q.pop();
    for ( int i = 0; i < G[u].size(); i++ ) {
      Edge e = G[u][i];
      if ( d[e.t] == INFTY ) {
        d[e.t] = d[u] + e.w;
        Q.push(e.t);
      }
    }
  }
}

void solve() {
  // 適当な視点 s から最も遠い節点 tgt を求める
  bfs(0);
  int maxv = 0;
  int tgt = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INFTY ) continue;
    if ( maxv < d[i] ) {
      maxv = d[i];
      tgt = i;
    }
  }

  // tgt から最も遠い節点の距離 maxv を求める
  bfs(tgt);
  maxv = 0;
  for ( int i = 0; i < n; i++ ) {
    if ( d[i] == INFTY ) continue;
    maxv = max(maxv, d[i]);
  }

  cout << maxv << endl;
}

main() {
  int s, t, w;
  cin >> n;

  for ( int i = 0; i < n-1; i++ ) {
    cin >> s >> t >> w;

    G[s].push_back(Edge(t, w));
    G[t].push_back(Edge(s, w));
  }
  solve();
}


Measured memory_bytes: 9764
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef unsigned long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define B 60
int a[2018];
lint dp[2][(4000010/B)+200];
vector<int> v;
int main()
{
	int n,sum=0,out=1001001001;cin>>n;
	rep(i,n){
		cin>>a[i];
		sum+=a[i];
	}
	sort(a,a+n);
	//cout<<(4000010/B)+100<<endl;
	memset(dp,0LL,sizeof(dp));
	dp[0][0]=1;
	rep(i,n){
		int now=i%2,ne=1-now;
		int s=a[i]/B,mo=a[i]%B;
		memset(dp[ne],0LL,sizeof(dp[ne]));
		rep(j,(4000010/B)+100){
			if(dp[now][j]<1LL) continue;
			//cout<<i<<' '<<j<<' '<<dp[now][j]<<endl;
			dp[ne][j]|=dp[now][j];
			//cout<<((1LL<<(B-mo))-1)<<' '<<(dp[now][j]&((1LL<<(B-mo))-1))<<endl;
			//dp[ne][j+s]|=((dp[now][j]&((1LL<<(B-mo))-1))<<mo);
			dp[ne][j+s]|=(dp[now][j]<<mo);
			//dp[ne][j+s+1]|=(dp[now][j]/(1LL<<(B-mo)));
			dp[ne][j+s+1]|=(dp[now][j]>>(B-mo));
		}
	}
	rep(j,(4000010)/B+5){
		int now=n%2;
		if(dp[now][j]<1LL) continue;
		//cout<<n<<' '<<j<<' '<<dp[now][j]<<endl;
	}
	rep(i,4000001){
		if((dp[n%2][i/B]&(1LL<<(i%B)))){
			if(i>=(sum+1)/2) out=min(out,i);
			//cerr<<i<<endl;
		}
	}
	assert(out<1001001001);
	cout<<out<<endl;
}


Measured memory_bytes: 1280
L=input()
x=int(0)
if (L in 'RRR'):
 x+=3
if (L in 'RRS'):
 x+=2
if (L in 'SRR'):
 x+=2
if (L in 'RSS'):
 x+=1
if (L in 'SRS'):
 x+=1
if (L in 'SSR'):
 x+=1
if (L in 'RSR'):
 x+=1
print(x)

Measured memory_bytes: 9044
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b

signed main(){
	ll n; cin>>n;
	vl vec(n);
	ll m=0;
	ll cnt=0;
	map<ll,ll> mp;
	rep(i,0,n){
		ll a; cin>>a;
		mp[a]++;
		chmax(m,a);
		vec[i]=a;
	}
	vector<bool> ok(m+2,true);
	rep(i,0,n){
		ll k=vec[i];
		k+=vec[i];
		while(k<=m){
			ok[k]=false;
			k+=vec[i];
		}
	}
	ll ans=0;
	rep(i,0,n){
		if(mp[vec[i]]>1)continue;
		if(ok[vec[i]])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 17412
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c,d,L,R;
  cin >>a>>b>>c>>d;
  L=a+b;
  R=c+d;
  if (L>R){
    cout << "Left" << endl;
  }
  else if(L==R){
    cout << "Balanced" << endl;
  }
  else{
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
//	cut here before submit 
//	freopen ("testcase.third_root", "r", stdin );
	while (1 ){
		int q;
		scanf ("%d", &q );
		if (q == -1 ) break;
		double x = (double)q/2.;
		while (fabs (x*x*x - (double)q) >= 0.00001*(double)q ){
			double y = (x*x*x - (double)q)/(3.*x*x);
			x = x - y;
		} // end while
		printf ("%lf\n", x );
	} // end loop
		
	return 0;
}

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

long modpow(long a, long n, long mod) {
    long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long modinv(long a, long mod) {
    return modpow(a, mod - 2, mod);
}

int main()
{
    int A[3][3];
    int seen[3][3];
    int N;
    int b[20];
    REP(i, 3)
        REP(j, 3)
            cin >> A[i][j];
    cin >> N;
    REP(i, N)
        cin >> b[i];
    REP(i, 3)
        REP(j, 3)
            seen[i][j] = 0;
    REP(i, N)
        REP(j, 3)
            REP(k, 3)
                if(b[i] == A[j][k])
                    seen[j][k] = 1;
    bool flag = true;
    REP(i, 3){
        int temp = 0;
        REP(j, 3)
            temp += seen[i][j];
        if(flag && temp == 3){
            cout << "Yes" << endl;
            flag = false;
        }
    }
    REP(i, 3){
        int temp = 0;
        REP(j, 3)
            temp += seen[j][i];
        if(flag && temp == 3){
            cout << "Yes" << endl;
            flag = false;
        }
    }
    int temp = 0;
    REP(i, 3)
        temp += seen[i][i];
    if(flag && temp == 3){
        cout << "Yes" << endl;
        flag = false;
    }
    temp = 0;
    REP(i, 3)
        temp += seen[i][2-i];
    if(flag && temp == 3){
        cout << "Yes" << endl;
        flag = false;
    }
    if(flag)
        cout << "No" << endl;
    
    return 0;
}



Measured memory_bytes: 256
# ALDS1_2_D Shell Sort
n = gets.chomp.to_i
a = []
$cnt = 0
n.times do
  a << gets.chomp.to_i
end

def insertionSort(a, n, g)
  (g..n-1).each do |i|
    v = a[i]
    j = i - g
    while j >= 0 and a[j] > v
      a[j+g] = a[j]
      j = j - g
      $cnt += 1
    end
    a[j+g] = v
  end
  return a
end

$gg = [1]
h = $gg[0]
while true
  h = h * 3 + 1
  break if h > n
  $gg << h
end
$gg.reverse!

def shellSort(a, n)
  $gg.each do |i|
    insertionSort(a, n, i)
  end
end

shellSort(a, n)

puts $gg.length
puts $gg.join(" ")
puts $cnt
puts a

Measured memory_bytes: 16736
#include <bits/stdc++.h>
using namespace std;
#define ll              long long
#define pb              push_back
#define mp              make_pair
#define ff              first
#define ss              second
#define SQ(x)           ((x)*(x))
#define LCM(x,y)        (((x)/gcd((x),(y)))*(y))
#define PI              acos(-1)
#define SZ(x)           x.size() - 1
#define waa             printf("Ripon\n")
#define mem(a,b)        memset(a,b,sizeof(a))
#define rep(i,a,n)      for(int i=(int)(a);i<=(int)(n);i++)
#define per(i,n,a)      for(int i=(int)(n);i>=(int)(a);i--)
#define all(v)          v.begin(), v.end()
#define allr(v)         v.rbegin(), v.rend()
int dx[] = { 0, 1, 0, -1, -1, 1, 1, -1 };
int dy[] = { 1, 0, -1, 0, -1, -1, 1, 1 };
int kx[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int ky[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
int overlap(int rs,int re,int qs,int qe){ if(rs>qe or re<qs) return 0; else if(qs<=rs and re<=qe) return 1; else return 2;} // 0 no, 1 total, 2 partial
void pvec(auto v){for(auto x:v){cout<<x<<" ";}cout<<'\n';}
//------------useless stuff--------------//
#define TC 0
#define mod 10000007
#define N 1000000
int n,m;
string str;
vector<int> v;

int arr[1234];
void solve(int T) {
    string str;
    cin>>str;
    bool res = 1;

    rep(i,0,SZ(str)){
        arr[str[i]]++;
    }

    rep(i,97,125){
        if(arr[i]==0) continue;
        else if(arr[i]%2!=0) res = 0;
    }

    if(res) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    #ifdef LOCALDEF
        freopen("input.txt","r",stdin);
    #endif
    int T=1;
    if(TC) cin>>T;
    for(int t=1;t<=T;t++)   solve(t);
    return 0;
}


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

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

using namespace std;
using ll = long long;

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

    string n;
    cin >> n;

    int sum = 0;
    for(char c: n) {
        sum += c - '0';
    }

    printf(sum % 9 == 0 ? "Yes\n" : "No\n");

    return 0;
}

Measured memory_bytes: 3864
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
#define int long long int
int sum(int n, int b){
    if(n == 0)return 0;
    return (n % b) + sum((n/b), b);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n, s; cin >> n >>s;
    int temp = sqrt(n);
    if(temp * temp == n)temp--;
    int ans = -1;
    if(s== n)ans = n+1;
    for(int i = 1; i <= temp; i++){
        int start= n/i;
        int end = n/(i+1);
        int range = start - end;
//        cout << start << " " << end << endl;
//        debug(start);
        int val = sum(n, start);
        //decrement in i start from val for range
        int times = (s- val)/i;
        if(times*i + val == s && 0 <=times && times <= range -1){
            ans = start - times; 
        }
    }
    for(int i = sqrt(n); i >= 2; i--){
        if(sum(n, i) == s){
            ans = i;
        } 
    }
    cout << ans;
}




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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  for (int i = 0; i < N - 1; i++) {
    if (vec.at(i) == vec.at(i + 1)) {
      cout << "NO" << endl;
      break;
    }
    if (i == N - 2 && vec.at(i) != vec.at(i + 1)) {
      cout << "YES" << endl;
    }
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define FOR(i,a,n) for(int i=a,i##_len=(int)(n);i<i##_len;++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i=(int)(n);i>=0;--i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)   // c++14
#define SZ(c) ((int)c.size())
#define EXIST(c,x) (c.find(x)!=end(c))
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : "\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> * i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
    }
} before_main_function;
//------------------------------------------------------------------------------

signed main() {
    double a,b;
    cin>>a>>b;
    double ans=INF;
    if(a>b) swap(a,b);
    // a < b
    if(b-a<180) {
        cout<<(b-a)/2.0+a<<endl;
        return 0;
    }
    else {
        if((a+360-b)/2.0+b > 360) {
            cout<<(a+360-b)/2.0+b-360<<endl;
        }
        else {
            cout<<(a+360-b)/2.0+b<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3216
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iomanip>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<long long> v(N);
    rep(i, N) cin >> v[i];
    
    map<long long, int> cnt;
    rep(i, N) ++cnt[v[i]];
    
    long long now = 0;
    int c = 0;
    map<long long, int> use;
    sort(v.rbegin(), v.rend());
    rep(i, B) {
        if (i < A) {
            now += v[i];
            ++use[v[i]];
            ++c;
        } else {
            if (v[i] == v[0]) {
                now += v[i];
                ++use[v[i]];
                ++c;
            }
        }
    }
    
    cout << fixed << setprecision(10) << now / (double)c << endl;
    
    vector<vector<long long>> comb(60, vector<long long>(60));
    rep(i, 60) rep(j, 60) {
        if (j > i) {
            continue;
        } else if (j == 0 || j == i) {
            comb[i][j] = 1;
        } else {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
        }
    }
    if (use.size() == 1) {
        long long ans = 0;
        for (int i = A; i <= B; ++i) {
            ans += comb[cnt[v[0]]][i];
        }
        cout << ans << endl;
        return 0;
    }
    long long ans = 1;
    for (auto n : use) {
        ans *= comb[cnt[n.first]][use[n.first]];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<list>
#include<map>
using namespace std;
#define ll long long
#define mod 998244353
#define add(x) (x>=mod?x-mod:x)
#define jian(x) (x<0?x+mod:x)
ll n,m,inv2,inv6,f[205][8005],g[2005][2005],c[10005],inv[10005],anss,r[40005],gg=3,A[40005],B[40005],limit,l,CC[40005];
ll C(ll n,ll m){
	if(n<m||m<0) return 0;
	return c[n]*inv[m]%mod*inv[n-m]%mod; 
}
ll ksm(ll x,ll y){
	ll anss=1,t=x;
	while(y){
		if(y&1) anss=anss*t%mod;
		t=t*t%mod;
		y>>=1;
	}
	return anss;
}
void NTT(ll a[],ll limit,ll tp){
	for(ll i=0;i<limit;i++){
		if(i>r[i]) swap(a[i],a[r[i]]);
	}
	for(ll mid=1;mid<limit;mid<<=1){
		ll wc=ksm(gg,(mod-1)/(mid*2));
		if(tp==-1) wc=ksm(wc,mod-2);
		for(ll i=0;i<limit;i+=mid<<1){
			ll w=1;
			for(ll t=0;t<mid;t++,w=w*wc%mod){
				ll x=a[i+t],y=a[i+t+mid]*w%mod;
				a[i+t]=add(x+y);a[i+t+mid]=jian(x-y);
			}
		}
	}
	if(tp==-1){
		ll s=ksm(limit,mod-2);
		for(ll i=0;i<limit;i++){
			a[i]=a[i]*s%mod;
		}
	}
}
int main(){
//	freopen("wind.in","r",stdin);
//	freopen("wind.out","w",stdout);
	scanf("%lld%lld",&m,&n);
	inv2=ksm(2,mod-2);inv6=ksm(6,mod-2);
	c[0]=1;
	for(ll i=1;i<=n+m+20;i++) c[i]=c[i-1]*i%mod;
	inv[n+m+20]=ksm(c[n+m+20],mod-2);
	for(ll i=n+m+19;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	f[0][0]=1;
	for(ll i=1;i<=n;i++){
		for(ll t=0;t<=m;t++){
			f[i][t]=f[i-1][t]*(C(t+1,2)+1);
		}
		for(ll t=0;t<=4*m;t++) A[t]=B[t]=0;
		for(ll t=0;t<=m;t++) A[t]=f[i-1][t]*inv[t]%mod;
		for(ll t=0;t<=m;t++) B[t]=inv[t+3];
		limit=1,l=0;
		while(limit<=2*m) limit<<=1,l++;
		for(ll t=0;t<limit;t++) r[t]=(r[t>>1]>>1)|((t&1)<<(l-1)); 
		NTT(A,limit,1);NTT(B,limit,1);
		for(ll t=0;t<limit;t++) CC[t]=A[t]*B[t]%mod;
		NTT(CC,limit,-1);
		for(ll t=1;t<=m;t++){
			f[i][t]=(f[i][t]+CC[t-1]*c[t+2])%mod;
		}
	}
	for(ll i=0;i<=m;i++){
		anss=(anss+f[n][i]*C(m,i))%mod;
	}
	printf("%lld",anss);
}

Measured memory_bytes: 17144
#include  <bits/stdc++.h>
using namespace std;
#define int long long
#define forr(i, n) for(int i = 0;i < (int)n; i++)
#define deb(x) cout<<#x<<" " <<x<<"\n";
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define mp make_pair
#define test int tests;cin >> tests;while(tests--)
#define endl "\n"
const int INF = 2e9;
int32_t main()
{
#ifndef ONLINE_JUDGE
	freopen("inputa.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	if(n&1){
		cout<<(double)(((n+1)/2.0)/(double)n);
	}else{
		cout<<(double)((n/2.0)/(double)n);
	}	
	return 0;
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int>s;

int main() {
    int n;
    cin>>n;ll p=0;
   for(int i=1;i<=n;i++){
    ll temp;
    cin>>temp;
    ll k = (temp-i);
   s.push_back(k);
   }
   sort(s.begin(),s.end());
    ll med = s[(n-1)/2];
    //cout<<med<<endl;
    for(auto x:s){
           // cout<<x<<endl;
        p+=abs(x-med);
    }
cout<<p;
 return 0;
}


Measured memory_bytes: 1400