akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int nxpt(int *s){
  int i,l=4,max=0,f[260]={0};
  for(l--;l+1&&max<=s[l];l--)f[max=s[l]]++;
  if(l<0)return 0;
  f[s[l]]++;
  for(i=s[l]+1;f[i]==0;i++);
  f[s[l]=i]--;
  for(i=0;s[++l];f[s[l]=i]--){
    while(f[i]==0)i++;
  }
  return 1;
}
int f(int a,int c,int b){
  if(c==0)return a+b;
  if(c==1)return a-b;
  if(c==2)return a*b;
}
int main(){
  int i,h,d[5]={0};
  int s[5],o[3];
  char c[]={"+-*"};
  while(1){
    for(i=0;i<4;i++)s[i]=i+1;
    s[4]=0;
    for(i=h=0;i<4;i++)scanf("%d",&d[i+1]);
    if(d[1]==0)return 0;
    do{
      for(i=0;i<27;i++){
	o[0]=i%3;
	o[1]=(i/3)%3;
	o[2]=i/9;
	///printf("%d%c%d==%d ",d[s[i]],c[o[i]],d[s[i+1]],f(d[s[i]],o[i],d[s[i+1]]));
	/*printf("((%d%c%d)%c%d)%c%d==%d\n",d[s[0]],c[o[0]],d[s[1]],c[o[1]],d[s[2]],c[o[2]],d[s[3]],
	       f(f(f(d[s[0]],o[0],d[s[1]]),o[1],d[s[2]]),o[2],d[s[3]]));
	printf("(%d%c%d)%c(%d%c%d)==%d\n",d[s[0]],c[o[0]],d[s[1]],c[o[1]],d[s[2]],c[o[2]],d[s[3]],
	f(f(d[s[0]],o[0],d[s[1]]),o[1],f(d[s[2]],o[2],d[s[3]])));//*/
	if(f(f(f(d[s[0]],o[0],d[s[1]]),o[1],d[s[2]]),o[2],d[s[3]])==10){
	  printf("((%d%c%d)%c%d)%c%d\n",d[s[0]],c[o[0]],d[s[1]],c[o[1]],d[s[2]],c[o[2]],d[s[3]]);
	  h=1;
	  break;
	}
	if(f(f(d[s[0]],o[0],d[s[1]]),o[1],f(d[s[2]],o[2],d[s[3]]))==10){
	  printf("(%d%c%d)%c(%d%c%d)\n",d[s[0]],c[o[0]],d[s[1]],c[o[1]],d[s[2]],c[o[2]],d[s[3]]);
	  h=1;
	  break;
	}
	//printf("%d %d\n",f(f(d[s[0]],o[0],d[s[1]]),o[1],f(d[s[2]],o[2],d[s[3]])),
	// f(f(f(d[s[0]],o[0],d[s[1]]),o[1],d[s[2]]),o[2],d[s[3]])==10);
      }
      //for(i=0;i<4;i++)printf("%d ",d[s[i]]);
      //printf("\n");
    }while(nxpt(s)&&h==0);
    if(h==0)printf("0\n");
  }
}

Measured memory_bytes: 612
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	int64 xx, yy;
	cin >> xx >> yy;
	cout << (xx + yy / 2) << endl;
	return 0;
}

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

int main()
{
    int a, b;
    cin >> a >> b;
    if (a < b)
        cout << "a < b" << endl;
    else if (a > b)
        cout << "a > b" << endl;
    else
        cout << "a == b" << endl;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define PB push_back
#define INF 1000000001
#define INFL 1000000000000000001
#define M 1000000007
int n,m;
bool vis[100005];
vector<int>g[100005];
vector<int>ans[2];
void dfs(int v,int k){
	vis[v]=true;
	for(int i=0;i<g[v].size();i++){
		if(!vis[g[v][i]]){
			ans[k].PB(g[v][i]);
			dfs(g[v][i],k);
			return;
		}
	}
}
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		g[--a].PB(--b);
		g[b].PB(a);
	}
	dfs(0,0);
	dfs(0,1);
	printf("%d\n",ans[0].size()+ans[1].size()+1);
	for(int i=ans[0].size();i>0;i--)printf("%d ",ans[0][i-1]+1);
	printf("1");
	for(int i=0;i<ans[1].size();i++)printf(" %d",ans[1][i]+1);
	printf("\n");
}


Measured memory_bytes: 6904
import math
import sys 
input = sys.stdin.readline

N = int(input())
x = list(map(int,input().split()))
mod = 10**9+7

d = [0]*(N-1)

for i in range(N-1):
    d[i] = x[i+1]-x[i]
    d[i] %= mod


kaijou = 1
for i in range(1,N):
    i %= mod
    kaijou *= i
    kaijou %= mod #これをしないとkaijouが発散


ans=0
x=0

def pow_a(a,n): #(modを取るように改良)
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= a
            K %= mod
        a *= a
        a %= mod
        n //= 2

    return (K*a)%mod

for i in range(N-1):
    y = pow_a(i+1,mod-2) #i+1の逆元
    x += kaijou*y
    ans += d[i]*x
    ans %= mod

print(ans)


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

typedef long long int ll;
typedef long double ld;

#define Pb push_back
#define Mp make_pair

#define ff first
#define ss second

#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))

#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN

#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define db1(x) cout<<#x<<" : "<<x<<endl;
#define db2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
#define db3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;

int n,k;
bool dp[100005];
int a[105];

void solve()
{
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if((i-a[j]) >= 0 && !dp[i-a[j]])
			{
				dp[i] = 1;
				break;
			}
		}
	}
	if(dp[k])
	{
		cout << "First";
	}
	else
	{
		cout << "Second";
	}
}

signed main()
{
   IOS;
   int t = 1;
   //cin >> t;
   while(t--)
   {
      solve();
   }
   return 0;
}


/*==============================================================================================================================================================*/


Measured memory_bytes: 384
#include<cstdlib>
#include<cstdio>
using namespace std;

char s[10];
bool get() {
	scanf("%s", s);
	if (s[0] == 'M') return true;
	else if (s[0] == 'F') return false;
	else exit(0);
}

void check(int left, int right, bool fir) {
	printf("%d\n", (right + left) / 2);
	fflush(stdout);
//	printf(" %d,%d : %d (c=%d)\n", left, right, fir, ((right - left) / 2) % 2);
	if (((right - left) / 2) % 2 == fir ^ get()) {
		check((right + left) / 2 + 1, right, fir ^ !(((right - left) / 2) % 2));
	} else {
		check(left, (right + left) / 2 - 1, fir);
	}
}
int main() {
	int N;
	scanf("%d", &N);
	printf("0\n");
	fflush(stdout);
	bool fir = get();
	check(0, N - 1, fir);
	return 0;
}

/*
まず、分かるように基本的には男性と女性が隣り合わせに座っている
まず、最初のiは0を選ぶとする(どれを選んでも円形なら確率的に等しい)
この時、帰ってきたのがMaleとする(女性でも影響しない、空席なら既に正解しているので考慮する必要がない)
また、Male=0、Female=1とする
次に、N/2を尋ねる
もしも0からN/2までに空席がないならば当然だが(N/2)%2の答えが返るはず
逆にそうでないなら予想と違う答えが返るはず
よって、(N/2)%2の答えならばN/2+1からN-1まで、そうでないなら1からN/2-1までの間に空席がある
以下、同手法を繰り返す

ところでいまだにTLEの理由分かってないんだけど、なんでTLEなの？
……って、行末に改行かよ！さっき見た時に無かったように思えたんだけど！
*/

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

typedef long lint;
typedef long long llint;

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

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


int main(void) {
    string s;
    llint k;
    cin >> s >> k;

    bool flg = true;
    llint cntone=0;
    llint inkeep;
    if(k==1) cout << s.at(0) << endl;
    else {
        for(int in=0;in<s.size();in++) {
            if(s.at(in)=='1') { 
                cntone++;
                continue;
            }
            else { 
                inkeep = in;
                flg = false;
                break;
            }
        }
        if(flg||cntone>=k) cout << 1 << endl;
        else cout << s.at(inkeep) << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
S=list(input())
L=[ord(s) for s in S]+[96]
for i in range(len(L)):
    l=L[-1]
    for j in range(l+1,123):
        if j not in L:
            S=S+[chr(j)]
            print(*S,sep="")
            exit()
    else:
        L.pop(-1)
        if S:
            S.pop(-1)
else:
    print(-1)

Measured memory_bytes: 9080
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;
typedef pair<int,int> P;

ll dig(ll a){
  if(a>0) return 1+dig(a/10);
  return 0;
}

ll F(ll a,ll b){
  return max(dig(a),dig(b));
}

int main(){
  ll n;
  cin >> n;
  ll ans = 10;
  for(ll i=1;i*i<=n;i++){
    if(n%i == 0) ans = min(ans,F(i,n/i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
S = list(map(int,input()))
assert len(S) == N

def solve():
    t1, t2, t3 = set(), set(), set()
    for i in range(N):
        z = S[i]
        for x, y in t2:
            t3.add((x, y, z))
        for x in t1:
            t2.add((x, z))
        t1.add(z)
    return len(t3)

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


Measured memory_bytes: 42220
package main

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

func scanner() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}

func get_int(sc *bufio.Scanner) int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func main() {
	var a, b, q int
	fmt.Scan(&a, &b, &q)

	ss := make([]int, a)
	ts := make([]int, b)
	xs := make([]int, q)

	sc := scanner()
	for i := range ss {
		ss[i] = get_int(sc)
	}
	ss = append(ss, -100000000000)
	ss = append(ss, 100000000000)
	for i := range ts {
		ts[i] = get_int(sc)
	}
	ts = append(ts, -100000000000)
	ts = append(ts, 100000000000)
	for i := range xs {
		xs[i] = get_int(sc)
	}

	sort.Ints(ss)
	sort.Ints(ts)

	for _, x := range xs {
		si := sort.SearchInts(ss, x)
		ti := sort.SearchInts(ts, x)
		v0 := s1(ss[si], ts[ti], x)
		v1 := s1(ss[si-1], ts[ti-1], x)
		v2 := s2(ss[si-1], ts[ti], x)
		v3 := s2(ss[si], ts[ti-1], x)

		min := 100000000000
		for _, v := range []int{v0, v1, v2, v3} {
			if min > v {
				min = v
			}
		}
		fmt.Println(min)
	}
}

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

func s1(a, b, x int) int {
	return max(diff(a, x), diff(b, x))
}

func s2(a, b, x int) int {
	d1 := diff(a, x)
	d2 := diff(x, b)
	return d1 + d2 + min(d1, d2)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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


Measured memory_bytes: 8704
#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>;

// 素因数分解
vector<pair<long long, long long>> prime_factorize(long long n) {
    vector<pair<long long, long long>> res;
    for(long long p = 2; p * p <= n; ++p) {
        if(n % p != 0)
            continue;
        int num = 0;
        while(n % p == 0) {
            ++num;
            n /= p;
        }
        res.push_back(make_pair(p, num));
    }
    if(n != 1)
        res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    ll n, cnt = 2;
    cin >> n;

    int ans = 0;
    auto m = prime_factorize(n);
    for(auto it = m.begin(); it != m.end(); it++) {
        // cout << it->first << "," << it->second << endl;
        int n = it->second;
        for(int i = 1; i <= n; i++) {
            n -= i;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>

using namespace std;

// template for creating 2d vector
template<typename T>
vector<vector<T>> make_2d_vector(size_t rows, size_t cols, T init)
{ return vector< vector<T> >(rows, vector<T>(cols, init)); }


#define debug(x) cout << #x << "==" << x << endl;

const int mod = 1e+9 + 7;

typedef long long ll;



int main() {
  ios::sync_with_stdio(false);

  int A, B, C;
  cin >> A >> B >> C;

  int cnt = 0;
  while( (A % 2 == 0) and (B % 2 == 0) and  (C % 2 == 0) ) {
    cnt++;
    int tA = A, tB = B, tC = C;
    A = ( tB + tC ) / 2;
    B = ( tA + tC ) / 2;
    C = ( tA + tB ) / 2;

    // cout << A << " " << B << " " << C << "\n";

    if( tA == A and tB == B and tC == C ) {
      cnt = -1;
      break;
    }

  }

  cout << cnt << "\n";

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,A[50],q,M;
bool solve(int i,int key)
{

	if(key ==0) return true;
	if(i>=n)return false;
	int res = solve(i+1,key)||solve(i+1,key-A[i]);
	return res;
}



int main()
{
	cin >> n;
	for(int i = 0; i< n; i++)
 		cin >> A[i];
	
	cin >> q;
	for(int i =0; i<q; i++)
	{
		cin >>M;
		if(solve(0,M))
			cout << "yes"<<endl;
		else
			cout << "no"<<endl;
	}	
}	

Measured memory_bytes: 3096
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
#include <numeric>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
    REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
//#define int ll

const int md = 1000000007;
const int INF = 1<<30;



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

    int ans = 0;

    char prev = '#';

    rep(i,n){
        if(prev != s[i]) ans++;
        prev = s[i];
    }

    cout << ans << endl;

}


Measured memory_bytes: 512
def main():
    from functools import reduce
    def a_comb_mod(n, r):
        mod = 1000000007
        r = min(n-r,r)
        if r == 0: return 1
        numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
        denom = reduce(lambda x, y: x * y % mod, range(1,r + 1), 1)
        denom_inv = pow(denom, mod - 2, mod)
        return numer * denom_inv % mod

    n, a, b = list(map(int, input().split()))
    mod = 1000000007
    print((pow(2, n, mod) - 1 - a_comb_mod(n, a) - a_comb_mod(n, b)) % mod)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9636
MOD = 10**9+7
H, W, K = map(int, input().split())
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1<<(W-1)):
            # 2つの横線がつながっていないか調べる
            ok = True
            for l in range(W-2):
                if (k>>l)&1 and (k>>(l+1))&1:
                    ok = False
            if ok:
                if j>=1 and (k>>(j-1))&1:
                    # 左方向に横線をたどるケース
                    dp[i+1][j-1] += dp[i][j]
                    dp[i+1][j-1] %= MOD
                elif j<W-1 and (k>>j)&1:
                    # 右方向に横線をたどるケース
                    dp[i+1][j+1] += dp[i][j]
                    dp[i+1][j+1] %= MOD
                else:
                    # 横線をたどらないケース
                    dp[i+1][j] += dp[i][j]
                    dp[i+1][j] %= MOD
print(dp[H][K-1])


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

int main() {
    ll n,k;
    cin>>n>>k;
    n%=k;
    n=(n+k)%k;
    cout<<min(abs(n),abs(n-k))<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define PI 3.14159265359
typedef long long LL;

template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

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

	map<int, int> integers;
	integers[A]++;
	integers[B]++;
	integers[C]++;

	for (auto &kv:integers) {
		if (kv.second == 1) {
			cout << kv.first << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    a, b, x = LI()

    ans = b // x - (a - 1) // x
    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9868
N, Y = map(int, input().split( ))

ans = '-1 -1 -1'
for n in range(N+1):
	for m in range(N-n+1):
		l = N - n - m
		sum_ot = n * 10000 + m * 5000 + l * 1000
		if Y == sum_ot:
			ans = str(n)+ ' ' + str(m) + ' ' + str(l)
			break
print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;
public class Main{ 
	public static void main(String[] args) {
	Scanner input = new Scanner (System.in);
    int a = input.nextInt();
    int b = input.nextInt();
    int h = input.nextInt();
    int s = (int) (0.5*h*(a+b));
    System.out.println(s);
   
	}
}

Measured memory_bytes: 27004
n = int(input())
h= list(map(int, input().split())) 

count = 0
ans = 0

for i in range(len(h)):
    if i + 1 < len(h):
        if h[i] >= h[i+1]:
            count = count + 1
        else:
            count = 0
    if count > ans :
        ans = count
        
print(ans)
    

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

#define fi first
#define se second
#define ll long long

const int N = 3003;
const int mod = 998244353;

using namespace std;

int a, b, c, d;
ll f[N][N];

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        cin >> a >> b >> c >> d;
        f[a][b] = 1;
        for(int i = a; i <= c; i++){
                for(int j = b; j <= d; j++){
                        if(i == a && j == b){
                                continue;
                        }
                        f[i][j] += f[i - 1][j] * j % mod;
                        f[i][j] += f[i][j - 1] * i % mod;
                        f[i][j] -= f[i - 1][j - 1] * (i - 1) * (j - 1) % mod;
                        f[i][j] %= mod;
                        if(f[i][j] < 0){
                                f[i][j] += mod;
                        }
                }
        }
        cout << f[c][d] << "\n";
}


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

using ll = long long;
struct edge {
    ll from, to, cost;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

void add_edge(graph& g, int from, int to, int cost) {
    g[from].push_back((edge){from, to, cost});
    g[to].push_back((edge){to, from, cost});
}


class lca {
public:
    lca(graph& g, int root)
        : V(g.size()),
          log_V(0),
          depth_(V, 0)
    {
        for(int v=V; v>0; v /= 2) {
            ++log_V;
        }
        parent.assign(log_V, std::vector<int>(V, 0));
        dfs(g, root, -1, 0);
        for(int k=0; k+1 < log_V; ++k) {
            for(int v=0; v<V; ++v) {
                if(parent[k][v] < 0) {
                    parent[k+1][v] = -1;
                } else {
                    parent[k+1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(graph const& g, int v, int p, int d) {
        parent[0][v] = p;
        depth_[v] = d;
        for(int i=0; i<g[v].size(); ++i) {
            if(g[v][i].to != p) {
                dfs(g, g[v][i].to, v, d+1);
            }
        }
    }

    int depth(int v) const {
        return depth_[v];
    }

    int query(int u, int v) {
        if(depth_[u] > depth_[v]) {
            std::swap(u, v);
        }
        for(int k=0; k<log_V; ++k) {
            if((depth_[v] - depth_[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if(u == v) {
            return u;
        }
        for(int k=log_V - 1; k>=0; --k) {
            if(parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

private:
    int V, log_V;
    std::vector<vector<int>> parent;
    std::vector<int> depth_;
};


void dfs(int v, int prev, graph& g, vector<ll>& d, ll sum) {
    d[v] = sum;
    for(auto& e : g[v]) {
        if(e.to == prev) {
            continue;
        }
        dfs(e.to, v, g, d, sum + e.cost);
    }
}


int main() {
    int N;
    cin >> N;
    graph g(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        add_edge(g, a, b, c);
    }

    int Q, K;
    cin >> Q >> K;
    K--;
    vector<ll> d(N);
    dfs(K, -1, g, d, 0);
    while(Q--) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cout << d[x] + d[y] << endl;
    }
}


Measured memory_bytes: 18944
#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

string s;

void inv(int n){
	if(s[n]=='0')s[n]='1';
	else s[n]='0';
}

int main(){
	int ans1=0,ans2=0;
	string tmp;
	cin>>s;
	tmp=s;

	for(int i=0;i<s.size();i++){

		if(s[i]==s[i+1]){
			inv(i+1);
			ans1++;
		}
	}
	
	s=tmp;
	inv(0);
	ans2++;
	for(int i=0;i<s.size();i++){

		if(s[i]==s[i+1]){
			inv(i+1);
			ans2++;
		}
	}

	if(ans1>ans2)cout<<ans2<<endl;
	else cout<<ans1<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define int long long
#define INF 10000000000
using namespace std;

typedef pair<int, int> Pii;
typedef pair<double, int> Pdi;
 
void readint(int N, vector<int> &a);
void readdouble(int N, vector<double> &a);
void readindex(int N, vector<int> &a);
 
int calc_num(int i, int p, int c, int G){
    if(G <= 0) return 0;
    if((i + 1) * 100 * p + c < G) return INF;
    if((i + 1) * 100 * p < G) return p;
    
    if(G % ((i + 1) * 100) == 0) return G / ((i + 1) * 100);
    return  G / ((i + 1) * 100) + 1;
}
 
signed main(){
 
    int D, G;
    cin >> D >> G;
    vector<int> p(D), c(D), sump(D);
 
 
    REP(i, D){
        cin >> p[i] >> c[i];
        sump[i] = (i + 1) * 100 * p[i] + c[i];
    }

    vector<int> is_solved(D);
 
    int ans = INF;
    REP(i, 1 << D){
        int sum_tmp = 0;
        int ans_tmp = 0;
        REP(j, D){
            is_solved[j] = (i >> j) % 2;
            if(is_solved[j] > 0){
                sum_tmp += sump[j];
                ans_tmp += p[j];
            }
        }
        if(sum_tmp < G){
            int Gr = G - sum_tmp;
            int imax = -1;
            int num;
            REP(j, D){
                if(is_solved[j] == 0) imax = j;
            }
            if(Gr % ((imax + 1) * 100) == 0){
                num = Gr / ((imax + 1) * 100);
            }else{
                num = Gr / ((imax + 1) * 100) + 1;
            }
            if(num >= p[imax]) continue;
            ans_tmp += num;
        }

        if(ans_tmp < ans) ans = ans_tmp;
    }
 
 
    cout << ans;
 
 
    return 0;
}
 
 
 
 
 
 
 
 
void readint(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str());
}
void readdouble(int N, vector<double> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atof(s.c_str());
    }
    getline(cin, s, '\n');
    a[N - 1] = atof(s.c_str());
}
void readindex(int N, vector<int> &a){
    string s;
    for(int i = 0; i < N - 1; i++){
        getline(cin, s, ' ');
        a[i] = atoi(s.c_str()) - 1;
    }
    getline(cin, s, '\n');
    a[N - 1] = atoi(s.c_str()) - 1;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main()
{
	int n;
	cin>>n;
	rep(loop,n){
		if(loop>0)
			cout<<endl;
		
		vvi a(9,vi(9));
		rep(i,9) rep(j,9)
			cin>>a[i][j];
		
		vvi bad(9,vi(9));
		rep(i,9){
			vi hist(10);
			rep(j,9)
				hist[a[i][j]]++;
			rep(j,9)
				if(hist[a[i][j]]!=1)
					bad[i][j]=1;
			hist=vi(10);
			rep(j,9)
				hist[a[j][i]]++;
			rep(j,9)
				if(hist[a[j][i]]!=1)
					bad[j][i]=1;
		}
		rep(k,9){
			int offi=k/3*3,offj=k%3*3;
			vi hist(10);
			rep(i,3) rep(j,3)
				hist[a[offi+i][offj+j]]++;
			rep(i,3) rep(j,3)
				if(hist[a[offi+i][offj+j]]!=1)
					bad[offi+i][offj+j]=1;
		}
		rep(i,9){
			rep(j,9)
				cout<<(bad[i][j]?'*':' ')<<a[i][j];
			cout<<endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
use itertools::Itertools;
use proconio::fastout;
use proconio::input;
use proconio::marker::Usize1;

#[fastout]
fn main() {
    input!(n: usize, town: [(Usize1, Usize1); n]);

    let id = (0..n).sorted_by_key(|&i| town[i].0).collect_vec();

    let mut col = vec![0; n];
    let mut siz = vec![0; n];
    let mut cnt = 0;
    let mut min = n + 1;
    for i in 0..n {
        let (_, y) = town[id[i]];
        if min == n - i {
            cnt += 1;
        }
        min = min.min(y);
        col[id[i]] = cnt;
        siz[cnt] += 1;
    }

    for i in 0..n {
        println!("{}", siz[col[i]])
    }
}


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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n,p[4],t[4];
    cin >> n;
    for (int i = 0;i < 4;++i) cin >> p[i];
    for (int i = 0;i < 4;++i) cin >> t[i];
    int ans = INT_MAX;
    for (int i = 0;i < 101;++i) for (int j = 0;j < 101;++j) for (int k = 0;k < 101;++k) {
        int x = p[0]*i+p[1]*j+p[2]*k,y = t[0]*i+t[1]*j+t[2]*k;
        if (y < n) {
            x += (n-y+t[3]-1)/t[3]*p[3];
        }
        ans = min(ans,x);
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 2e5 + 5;
#define next jpaoijfsj

string s , t;
int next[maxn][26];
int n , m;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> s >> t;
    s = s + s;
    n = s.size();m = t.size();
    fill_n(&next[0][0],maxn * 26,n);
    for(int i = n - 1 ; i >= 0 ; --i){
        for(int j = 0 ; j < 26 ; ++j){
            if(s[i] == j + 'a'){
                next[i][j] = i;
            }else next[i][j] = next[i + 1][j];
        }
    }
    int now = -1;
    int time = 0;
    for(char c : t){
        time += (now + 1) / (n / 2);
        now = (now + 1) % (n / 2);
//        cout << c << " ";
        if(next[now][c - 'a'] == n)return cout << -1 , 0;
        else now = next[now][c - 'a'];
    }
    cout << (ll)time * (n / 2) + now + 1;
}


Measured memory_bytes: 20972
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
// 293206GT
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <unordered_set>
#include <stack>
#include <string>
#include<algorithm>
#include <random>
#include <bitset>
#include <chrono>

typedef long long ll;
#define int ll
using namespace std;
#define put(a) cout << (a) << '\n'
#define sqr(x) (x) * (x)
typedef pair<ll, ll> pii;
typedef long double ld;

typedef pair<ld, ld> pld;
#define rep(x, y, a) for (int x = (y); x < (int)(a); ++x)
#define all(a) a.begin(), a.end()
#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))
#define prev asasdasd
#define next aasdasda
#define left asdasdasdasd
#define right asnabsdkasdl
#define rank asdasdknlasd
#define move asdasdas

typedef vector<int> vi;
typedef vector<pii> vpii;
namespace IO {
    template<class A, class B>
    ostream &operator<<(ostream &out, pair<A, B> &a) {
        out << a.first << " " << a.second;
        return out;
    }

    template<class A, class B>
    ostream &operator<<(ostream &out, vector<pair<A, B>> &a) {
        for (pair<A, B> x: a)
            out << x.first << " " << x.second << '\n';
    }

    template<class A>
    ostream &operator<<(ostream &out, vector<A> &a) {
        for (A x: a) out << x << ' ';
        return out;
    }

    template<class A, class B>
    istream &operator>>(istream &in, pair<A, B> &a) {
        in >> a.first >> a.second;
        return in;
    }

    template<class A>
    istream &operator>>(istream &in, vector<A> &a) {
        for (A &x: a) in >> x;
        return in;
    }
}
using namespace IO;

void solve() {
    int n;
    cin >> n;
    int res = n / 5 * (5 + n - n % 5) / 2;
    res +=n / 3 * (3 + n - n % 3) / 2;
    res -=n / 15 * (15 + n - n % 15) / 2;
    put(n * (n + 1) / 2 - res);
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

//    freopen("input.txt", "r", stdin);
    int t = 1;
//    cin >> t;
    while (t--) solve();
}

Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define io freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define lli long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define fi(a,n) for(lli i=a; i<=n; i++)
const int M=1000000007;
using namespace std;
const lli NINF=-1e18;
const int mxn=1e5;

int main(){

	fast
	string s,t;
	cin>>s>>t;
	int m=s.size();
	int n=t.size();
	int ans=0;

	// int j=0;
	// int p=0;
	for(int i=0;i<m-n+1;i++){
		string k=s.substr(i,n);
		int p=0;
		for(int j=0;j<n;j++){
			if(k[j]==t[j]) {p++;ans=max(ans,p);if(p==n) break;}
			
		}
	}
	cout<<n-ans<<endl;

  
    // cout<<nd(s)<<endl<<endl; 
}


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

int main() {
  int w, n, nx, ny;

  cin >> w >> n;
  vector<int> a(w);
  for(int i = 0; i < w; i++) a[i] = i+1;
  for(int i = 0; i < n; i++) {
    int x, y;
    scanf("%d,%d", &x, &y);
     swap(a[x-1], a[y-1]);
  }
  for(int i = 0; i < w; i++) cout << a[i] << endl;
}

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

int main() {
  string S;
  int64_t N;
  cin >> S;
  N = S.size();
  int64_t C0 = 0, C1 = 0;
  
  for (int i = 0; i < N; i++) {
    if (S.at(i) == '0') {
      C0++;
    }
    else {
      C1++;
    }
  }
  int a = min(C0, C1); 
  cout << 2*a << endl;
}


Measured memory_bytes: 1020
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;

    void solve() throws IOException {
    	int[] arr = nia(3);
    	Arrays.sort(arr);
    	if (arr[0] == 5 && arr[1] == 5 && arr[2] == 7) {
    		out.println("YES");
    	} else {
    		out.println("NO");
    	}
    }

    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }

    int ni() throws IOException {
        return Integer.parseInt(ns());
    }

    long nl() throws IOException {
        return Long.parseLong(ns());
    }

    double nd() throws IOException {
        return Double.parseDouble(ns());
    }

    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }

    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }

    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}


Measured memory_bytes: 8020
#include <bits/stdc++.h>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
using namespace std;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(110, vector<ll>(50, 0));
vector<tuple<ll, ll, ll>> vt;
set<ll> st;
map<ll, ll> mp;


queue<ll> q;
string s;
bool solve(int n)
{
	if (n == s.size()) return true;
	else if (n > s.size() || s.size() - n < 5) return false;
	if (s.substr(n, 7) == "dreamer") {
		if(solve(n + 7)) return true;
	}
	if (s.substr(n, 6) == "eraser")
	{
		if(solve(n + 6)) return true;
	}
	if (s.substr(n, 5) == "dream" || s.substr(n, 5) == "erase")
	{
		return solve(n + 5);
	}
	else return false;
}

int main()
{
	cin >> s;
	cout << (solve(0) ? "YES" : "NO") << endl;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int N;
  cin >> N;
  int dp[N+1];
  const int INF = 1e9;
  for(int i=0; i<N+1; i++) dp[i] = INF;
  dp[0] = 0;
  
  int q_nine = 1;
  while(q_nine <= N){
    q_nine *= 9;    
  }
  int q_six = 1;
  while(q_six <= N){
    q_six *= 6;    
  }
  while(q_nine > 1){
    for(int i=0; i+q_nine<=N+1; i++){
      dp[i+q_nine] = min(dp[i+q_nine], dp[i]+1);      
    }
    q_nine /= 9;
    
    for(int i=0; i+q_six<=N+1; i++){
      dp[i+q_six] = min(dp[i+q_six], dp[i]+1);      
    }
    q_six /= 6;

    for(int i=0; i+q_six<=N+1; i++){
      dp[i+q_six] = min(dp[i+q_six], dp[i]+1);      
    }
    q_six /= 6;

    
  }
  while(q_six > 1){
    for(int i=0; i+q_six<=N+1; i++){
      dp[i+q_six] = min(dp[i+q_six], dp[i]+1);      
    }
    q_six /= 6;
  }  

  for(int i=0; i<N; i++){
    dp[i+1] = min(dp[i+1], dp[i]+1);      
  }

/*
  for(int i=0; i<N+1; i++){
    if(dp[i] != INF)
    cout << i << ", " << dp[i] << endl;
  }
*/
  cout << dp[N] << endl;
    
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = -1*((1LL<<63)+1);
const int inf = -1*((1<<31)+1);

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N,A,B,C,D;
	cin >> N >> A >> B >> C >> D;
	B-=A;
	A =0;
	//どの隣接する2マスについても整数の差はc以上d以下
	for(int i=0;i<N-1;i++){
		ll m = i;
		if(C*(N-1-m)-D*m <= B-A && B-A <= -C*m +(N-1-m)*D){
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const long long  maxN = 1e5 + 1;

long long a[3 * maxN], i, Max[3 * maxN], Min[3 * maxN], u, n, res(-1e18);
priority_queue <long long > qpmax;
priority_queue <long long , vector <long long >, greater <long long > > qpmin;

void Init()
{
    cin >> n;
    for (i = 1; i <= 3 * n; i++) cin >> a[i];
}

void Solve()
{
    for (i = 3 * n; i >= 2 * n + 1; i--)
    {
        qpmax.push(a[i]);
        Min[2 * n + 1] += a[i];
    }
    for (i = 2 * n; i >= n + 1; i--)
    {
        u = qpmax.top();
        if (a[i] < u)
        {
            qpmax.pop();
            Min[i] = Min[i + 1] - u + a[i];
            qpmax.push(a[i]);
        }
        else Min[i] = Min[i + 1];
    }
}

void Solve2()
{
    for (i = 1; i <= n; i++)
    {
        qpmin.push(a[i]);
        Max[n] += a[i];
    }
    for (i = n + 1; i <= 2 * n; i++)
    {
        u = qpmin.top();
        if (a[i] > u)
        {
            qpmin.pop();
            Max[i] = Max[i - 1] - u + a[i];
            qpmin.push(a[i]);
        }
        else Max[i] = Max[i - 1];
    }
}

void Solve3()
{
    for (i = n; i <= 2 * n; i++) res = max (res, Max[i] - Min[i + 1]);
    cout << res;
}

int main()
{
    //freopen("B.inp", "r", stdin);
    //freopen("B.out", "w", stdout);
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    Init();
    Solve();
    Solve2();
    Solve3();
}


Measured memory_bytes: 8308
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {

        // 入力されたデータの準備
        Scanner scanner = new Scanner(System.in);
        String inputData = scanner.nextLine();
        String[] editedInputData = inputData.split(" ");
        long checkNum = Long.parseLong(editedInputData[0]);
        double baseNum = Integer.parseInt(editedInputData[1]);
        scanner.close();

        // 判定
        double exponentCount = 1;
    
        while (true) {
            double exponentNum = Math.pow(baseNum, exponentCount);
            if (checkNum < exponentNum) {
                break;
            }
            exponentCount++;
        }

        long count = (long)exponentCount;

        System.out.println(count);

    }

}

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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);	
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll ,ll> 			pll;
typedef pair<ld,ld> 			pld;
typedef unordered_map<ll,ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5+7;
const ll 	MAX7 	= 	1e+7+7;
const ll 	MAXN 	= 	MAX7;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9+7;
const ll 	N 		= 	2*1e6;

/*vll adj[MAXN];ll visit[MAXN]={};
int dx8[]={0,1,1,1,0,-1,-1,-1}, dy8[]={1,1,0,-1,-1,-1,0,1};
int dx4[]={0,1,0,-1}, dy4[]={1,0,-1,0};
*/
// <------------- Declare Variables Here ------------> //

ll T=1;
ll n,x,y,m;
string s,t;
//vll a;

// <------------- Implement Functions Here ----------> //

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> s;
	ll sum = 0;
	for(auto ch : s) {
		sum += (ch - '0');
		sum%=9;
	}
	if(sum == 0) cout<<"Yes\n";
	else cout<<"No\n";
}

int main() {
	fastio;randomINT;
	//cin>>T;
	while(T--) {
		MAIN();
	}
	return 0;
}



Measured memory_bytes: 3712
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, m = ril()
ls = ril()
ls2 = rils(m)
ls.sort()
ls2.sort(key=operator.itemgetter(1), reverse=True)
res = sum(ls)
index = 0
b, c = ls2[0]
for x in ls:
    if x < c:
        res += c - x
        b -= 1
        if b == 0:
            index += 1
            if index < m:
                b, c = ls2[index]
            else:
                break
print(res)

Measured memory_bytes: 32932
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int hour, A, B;
  	
  	cin >> hour >> A >> B;
  	
  	int plan1 = hour * A;
  	int plan2 = B;
  
  	if (plan1 > plan2) {
      cout << plan2 << endl;
    } else {
      cout << plan1 << endl;
    }
}

Measured memory_bytes: 256
# 整数全体をある数で割った余りで分類
# 余りが同じ整数はすべて同じ(合同≡)とみなす
# 加法、減法、乗法を行っても合同を保つことから
# (1) a + b ≡ 0 mod K
# (2) b + c ≡ 0 mod K
# (3) c + a ≡ 0 mod K
# (1) - (2) + (3) 2a ≡ 0 mod K
# Kが偶数の場合、mod K / 2 もゼロと合同になる
# Kが8の場合、mod 4 もゼロとなるものも対象となる
# Kで割った余りはKより小さい
# Kで割った余りの数が等しくなるものがいくつあるか数え
# a mod Kで全探索する
N, K = map(int, input().split())

Kn = [0] * K


def main():
    # a b c は 1 から
    for i in range(1, N + 1):
        Kn[i % K] += 1

    ans = 0

    # 余りはゼロから
    # a mod K 全探索
    for a in range(K):

        # b と c は a から見て 等価
        b = (K - a) % K

        if 2 * b % K != 0:
            continue

        ans += Kn[a] * Kn[b] * Kn[b]

    print(ans)
    return


main()


Measured memory_bytes: 4596
category_number, popular_product_number = input().split()
product = input().split()
product_list = [int(i) for i in product]
votes_number = sorted(product_list)[-int(popular_product_number)]
border = sum(product_list)/4/int(popular_product_number)
if votes_number < border:
  print('No')
else:
  print('Yes')

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,r ;
    cin >> n >> r;
    if (n>=10)
    {
        cout << r << endl;
    }
    else
    {
        cout << r + 100 * (10-n) << endl;
    }
    
    
    
}




Measured memory_bytes: 256
import java.text.DecimalFormat;
import java.util.Scanner;
public class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		DecimalFormat df1 = new DecimalFormat("0.########");
		DecimalFormat df2 = new DecimalFormat("0.00000000");
		
		while(sc.hasNext()){
			int n = sc.nextInt();
			if(n!=0){
				int[] s = new int[n];
				double ave = 0;
				int i;
				
				for(i=0; i<n; i++){
					s[i] = sc.nextInt();
					ave += s[i];
				}
				ave = ave/n;
				
				double a=0;
				for(i=0; i<n; i++){
					a += (s[i]-ave)*(s[i]-ave);
				}
				a = a/n;
				a = Math.sqrt(a);
				
				if(a > 0){
					System.out.println(df1.format(a));
				}
				if(a == 0){
					System.out.println(df2.format(a));
				}
			}
		}
    }
}


Measured memory_bytes: 31444
#include <stdio.h>
#include <math.h>

void main()
{
    int n=0,d=0,i,j;
    scanf("%d %d",&n,&d);
    int a[n][d];
    for(i=0;i<n;i++)
    {
        for(j=0;j<d;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    short counter=0;

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            float distance=0.0;
            for(int k=0;k<d;k++)
            {
                distance+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
            }
            distance=pow(distance,0.5);
            if((int)(distance)-distance==0)
            {
                counter++;
            }
            
        }
    }
    printf("%d",counter);
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
class Simple {
    int N, K;
    string[] P;
    void Solve() {
        //input
        N = io.Int;
        K = io.Int;
        P = new string[N];
        for (int i = 0; i < N; ++i)
            P[i] = io.String;
        //cal
        var ans = 0;
        var map = new int['z' - 'a' + 1];
        for (int i = 0; i < P.Length; ++i)
            map[P[i][0] - 'A']++;
        for (;;) {
            var cnt = 0;
            Array.Sort(map);
            Array.Reverse(map);
            for (int i = 0; i < map.Length; ++i) {
                if (map[i] > 0) { cnt++; map[i]--; }
                if (cnt == K) { ans++; break; }
            }
            if (cnt != K) break;
        }
        //ret
        Console.WriteLine(ans);
    }

    SimpleIO io = new SimpleIO();
    public static void Main(string[] args) { new Simple().Stream(); }
    void Stream() {
        Solve();
        io.writeFlush();
    }
}

class SimpleIO {
    string[] nextBuffer;
    int BufferCnt;
    char[] cs = new char[] { ' ' };
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
    public SimpleIO() {
        nextBuffer = new string[0];
        BufferCnt = 0;
        Console.SetOut(sw);
    }
    public string Next() {
        if (BufferCnt < nextBuffer.Length)
            return nextBuffer[BufferCnt++];
        string st = Console.ReadLine();
        while (st == "")
            st = Console.ReadLine();
        nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        BufferCnt = 0;
        return nextBuffer[BufferCnt++];
    }
    public string String => Next();
    public char Char => char.Parse(String);
    public int Int => int.Parse(String);
    public long Long => long.Parse(String);
    public double Double => double.Parse(String);
    public void writeFlush() { Console.Out.Flush(); }
}

Measured memory_bytes: 13268
n, m, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
Z = []
Z_x = []
f_y = False
for i in range(X+1, Y+1):
    Z.append(i)  #X < Z <= Yをappend

###Zの範囲で条件を満たすZのみZ_xにappend
for i in range(len(Z)):
    cnt_x = 0
    for j in range(len(x)):
        if Z[i] > x[j]:
            cnt_x += 1
    if cnt_x == len(x):
        Z_x.append(Z[i])

###条件を満たし、新たにできたZの範囲で条件を満たすYを探す
for i in range(len(Z_x)):
    cnt_y = 0
    for j in range(len(y)):
        if Z_x[i] <= y[j]:
            cnt_y += 1
    if cnt_y == len(y):
        f_y = True
        break

if f_y:
    print('No War')
else:
    print('War')

Measured memory_bytes: 3064