akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

long long pow_mod(long long n, long long p, long long m)
{
    if (p == 0) {
        return 1;
    }

    if (p % 2 == 0) {
        long long t = pow_mod(n, p / 2, m);
        return t * t % m;
    }
    return n * pow_mod(n, p - 1, m) % mod;
}

long long nCr_mod(long long n, long long r)
{
    long long x = 1;
    for (long long i = n - r + 1; i <= n; i++) {
        x *= i;
        x %= mod;
    }

    long long a = 1;
    for (long long i = 1; i <= r; i++) {
        a *= i;
        a %= mod;
    }

    long long y = pow_mod(a, mod - 2, mod) % mod;

    return x * y % mod;
}

int main()
{
    long long n;
    std::cin >> n;

    std::vector<long long> x(n);
    std::vector<long long> sorted(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
        sorted[i] = x[i];
    }

    std::sort(sorted.begin(), sorted.end());
    long long a = sorted[n / 2 - 1], b = sorted[n / 2];
    for (int i = 0; i < n; i++) {
        std::cout << (x[i] <= a ? b : a) << std::endl;
    }
}


Measured memory_bytes: 5376
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
#include<numeric>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  while(n > 0){
    if(n % 10 == 7){
      cout << "Yes\n";
      return 0;
    }
    n /= 10;
  }
  cout << "No\n";
  return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
//luoxuejieshihaoren

int main()
{
    int p,a;
    scanf("%d%d",&a,&p);
    printf("%d\n",(a*3+p)/2);
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>

using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N], col[N];
int lowLeft[N * 2 - 1], lowRight[N * 2 - 1];
bool X[N][N];

void printBoard() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (X[i][j] && row[i] != j)
				return;
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (row[i] == j)
				cout << "Q";
			else
				cout << ".";
		}
		cout << endl;
	}
}

void backTrack(int i) {
	if (i == N) {
		printBoard();
		return;
	}
	for (int j = 0; j < N; ++j) {
		if (col[j] == NOT_FREE || lowLeft[i + j] == NOT_FREE || lowRight[i - j + N - 1] == NOT_FREE)
			continue;
		row[i] = j;
		col[j] = lowLeft[i + j] = lowRight[i - j + N - 1] = NOT_FREE;
		backTrack(i + 1);
		row[i] = col[j] = lowLeft[i + j] = lowRight[i - j + N - 1] = FREE;
	}
}

int main() {
	for (int i = 0; i < N; ++i) {
		row[i] = col[i] = FREE;
	}
	for (int i = 0; i < N * 2 - 1; ++i) {
		lowLeft[i] = lowRight[i] = FREE;
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			X[i][j] = false;
		}
	}

	int k;
	scanf("%d", &k);
	for (int i = 0; i < k; ++i) {
		int r, c;
		scanf("%d %d", &r, &c);
		X[r][c] = true;
	}
	backTrack(0);

	return 0;
}

Measured memory_bytes: 3232
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    while(cin >> n, n){
        vector<pair<double, int>> v;
        for (int i = 0; i < n; ++i) {
            int p; int h, w;
            cin >> p >> h >> w;
            v.emplace_back(abs(22-1e4*w/h/h), p);
        }
        cout << min_element(v.begin(),v.end())->second << "\n";

    }
    return 0;
}


Measured memory_bytes: 3016
#include<bits/stdc++.h>
#include<algorithm>
#include<string>
#include<vector>
#include<tuple>
using namespace std;

int main(){
  int d;
  cin >> d;
  if(d == 7 || d == 5 || d == 3) cout << "YES" << endl;
  else cout << "NO";

}


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

#define MAX_N 602
int N, M;
vector<int> graph[MAX_N];
double ans = MAX_N;
void rewrite(int id){
    double dp[MAX_N] = {};
    // dp[N] = 0;
    for (int i = N-1; i > 0; --i) {
        if(i != id || graph[i].size() == 1) { // 書き換えない場合
            for (int x: graph[i]) dp[i] += dp[x];
            dp[i] = dp[i] / graph[i].size() + 1;
        } else {
            vector<double>v;
            for (int x: graph[i]) v.push_back(dp[x]);
            sort(v.begin(), v.end());
            v.pop_back();
            for (double x: v) dp[i] += x;
            dp[i] = dp[i] / v.size() + 1;
        }
    }
    ans = min(ans, dp[1]);
}


int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int s, t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    for (int i = 1; i < N; ++i) {
        rewrite(i);
    }
    cout << setprecision(20) << ans << "\n";
    return 0;
}

Measured memory_bytes: 1408
def main():
    n,w = map(int, input().split())
    weight = []
    value = []
    for i in range(n):
        wi, vi = map(int, input().split())
        weight.append(wi)
        value.append(vi)
    
    def chmax(a, b):
        if a < b:
            a = b
        return a
    
    dp = [[0 for i in range(100100)] for j in range(110)]

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - weight[i] >= 0:
                dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i])

            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])
    
    print(dp[n][w])

if __name__ == "__main__":
    main()


Measured memory_bytes: 181384
x = input()

stack = []
cnt = 0
for c in x:
  #stackになかったら、抜き出した文字(S or T)を追加
  if not stack:
    stack.append(c)

  else:
    #抜き出したもの(c)が"S"だった場合
    if c == "S":
      #stackに追加
      stack.append(c)

    #抜き出したもの(c)が"T"だった場合
    else:
      #末尾をstackから削除しつつ、その末尾のものをtopと定義する
      top = stack.pop()

      #topが"S",cが"T"でちゃんと対応していた場合cntを2増やす
      if top == 'S' and c == 'T':
        cnt += 2
        
print(len(x)-cnt)
        

Measured memory_bytes: 4328
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int n, m;
char s[1000], t[1000];
int dp[1001][10001];

int main(void){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s;
        cin >> t;
        int sizeofs = strlen(s);
        int sizeoft = strlen(t);
        for(int i=0;i<sizeofs;i++){
            for(int j=0;j<sizeoft;j++){
                if(s[i] == t[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        cout << dp[sizeofs][sizeoft] <<endl;
    }

    return 0;
}

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

/*bit全探索*/
int main(void){
    string S;
    cin >> S;
    int SIGN_NUM = S.size() - 1;
    int GOAL = 7;
    int ans_bit;
    rep(bit,1 << SIGN_NUM){
        int result = S[0] - '0';
        rep(i,SIGN_NUM){
            if(bit & 1<<i)result += (S[i+1] - '0');
            else result -= (S[i+1] - '0');
        }
        if(result == 7){
            ans_bit = bit;
            break;
        }
    }
    cout << S[0];
    rep(i,SIGN_NUM){
        if(ans_bit & 1<<i)cout << "+" << S[i+1];
        else cout << "-" << S[i+1];
    }
    cout << "=" << GOAL << endl;
    return 0;
}

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

int main(){
  int n; cin >> n;
  int k=n/2;
  vector<int> o(k);
  vector<int> e(k);
  for(int i=0;i<k;i++){
    cin >> o[i] >> e[i];
  }
  if(k==1 && o[0]!=e[0]){
    cout << 0 << endl;
    return 0;
  }
  if(k==1 && o[0]==e[0]){
    cout << 1 << endl;
    return 0;
  }
  int oco=1;
  int eco=1;
  int oone=0;
  int otwo=0;
  int eone=0;
  int etwo=0;
  int ooo=0;
  int eee=0;
  sort(o.begin(),o.end());
  o.push_back(-1);
  sort(e.begin(),e.end());
  e.push_back(-1);
  for(int i=1;i<k+1;i++){
    if(o[i]==o[i-1]){
      oco++;
    }
    if(o[i]!=o[i-1]){
      if(oone<=oco){
        otwo=oone;
        oone=oco;
        ooo=o[i-1];
      }
      else if(otwo<=oco){
        otwo=oco;
      }
      oco=1;
    }
  }
  for(int i=1;i<k+1;i++){
    if(e[i]==e[i-1]){
      eco++;
    }
    if(e[i]!=e[i-1]){
      if(eone<=eco){
        etwo=eone;
        eone=eco;
        eee=e[i-1];
      }
      else if(etwo<=eco){
        etwo=eco;
      }
      eco=1;
    }
  }
  if(ooo!=eee){
    cout << 2*k-oone-eone << endl;
    return 0;
  }
  if(ooo==eee){
    cout << 2*k-max(oone+etwo,otwo+eone) << endl;
    return 0;
  }
}

Measured memory_bytes: 828
#include <stdio.h>
#include <string.h>

int main()
{
    int health, attack, attemp = 0;
    scanf("%d %d", &health, &attack);

    while(health > 0)
    {
        health -= attack;
        attemp++;
    }

    printf("%d", attemp);

    return 0;
}

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

#define endl '\n'

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    setprecision(16);
    
    long double l;
    cin >> l;
    l /= 3.0;
    cout << fixed << l*l*l << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>

std::vector<char> c(10);
int n;

void dfs(std::string s, int i, int usenum)
{
    if(i == n)
    {
        std::cout << s << std::endl;
    }
    else
    {
        for(int k = 0; k < usenum; k++)
        {
            //s += c[k];
            dfs(s+c[k], i + 1, usenum);
        }
        //s += c[usenum];
        dfs(s+c[usenum], i + 1, usenum + 1);
    }
}

int d()
{
    std::cin >> n;
    
    c[0] = 'a';
    c[1] = 'b';
    c[2] = 'c';
    c[3] = 'd';
    c[4] = 'e';
    c[5] = 'f';
    c[6] = 'g';
    c[7] = 'h';
    c[8] = 'i';
    c[9] = 'j';
    
    std::string s = "a";
    dfs(s, 1, 1);

    return 0;
}

int main(int argc, const char * argv[])
{
    d();
    return 0;
}


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

int main(){

    int n;
    cin >> n;
    string s;
    cin >> s;

    for(int i = 0; i < s.length(); ++i){
        if(s[i] + n > 'Z')s[i] = 'A' + (s[i]+n-'Z') - 1;
        else s[i] += n;
    }

    cout << s << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N,K;
    cin >> N >> K;
    
    int A=1;
    
    for (int i=0;i<N;i++){
        A = min(2*A,A+K);
    }
    cout << A << endl;
  
}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
int a[200010];
set<int> st;
int main()
{
	cin >>n;
	for (int i=0;i<n;i++) cin >>a[i];
	for (int i=0;i<n;i++)
	{
		if (st.count(a[i]-1)) st.insert(a[i]);
		if (a[i]==1) st.insert(1);
	}
	if (st.empty())
	{
		cout <<"-1";
		return 0;
	}
	set<int>::iterator it=st.end();
	it--;
	cout <<n-*it;
	return 0;
}

Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define boost_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define num(a) a-'0'
#define charr(a) (a - 'A' + 1)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#define debug(x) cerr<<"["<<#x<<":"<<x<<"] "
#define debug2(a,b) debug(a);debug(b)
#define debug3(a,b,c) debug2(a,b);debug(c)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/(__gcd(a,b))
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<long long>
#define v vector
#define p pair
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
typedef double d;
using namespace std;
int modF=1e9+7;
int INF=1e11;

void solve(){
	int x,y,z;
	cin>>x>>y>>z;
	cout<<z<<" "<<x<<" "<<y<<ln;
}

signed main(){
	boost_io;
	solve();
	return 0;
}

Measured memory_bytes: 3592
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

using namespace::std;

void solve(){
	int N;
	cin >> N;
	cout << (( N/10==9 || N%10==9)?"Yes":"No") << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

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

template<typename T>
struct Segtree {
    int n;
    T e;
    vector<T> dat;
    typedef function<T(T a, T b)> Func;
    Func f;

    Segtree(int n_input, Func f, T e_input):f(f), e(e_input){
        n = 1;
        while(n < n_input) n <<= 1;
        dat.resize(2*n-1, e);
    }

    void update(int k, T a){
        k += n - 1;
        dat[k] = a;
        while(k > 0){
            k = (k - 1)/2;
            dat[k] = f(dat[2*k+1], dat[2*k+2]);
        }
    }

    T get(int k){
        return dat[k+n-1];
    }

    T between(int a, int b){
        return query(a, b+1, 0, 0, n);
    }

    T query(int a, int b, int k, int l, int r){
        if(r<=a || b<=l) return e;
        if(a<=l && r<=b) return dat[k];
        T vl = query(a, b, 2*k+1, l, (l+r)/2);
        T vr = query(a, b, 2*k+2, (l+r)/2, r);
        return f(vl, vr);
    }
};

int main(){
    const int MAX = 200001;
    int N, Q, B[MAX], num0 = 0;
    vector<int> LR[MAX];
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> B[i];
        if(B[i] == 0) num0++;
    }
    cin >> Q;
    for(int i=0; i<Q; i++){
        int l, r;
        cin >> l >> r;
        LR[l].push_back(r);
    }

    Segtree<int> st(N+1, [](int a, int b){return min(a, b);}, 1e9);
    st.update(0, 0);
    for(int i=1; i<=N; i++){
        sort(LR[i].rbegin(), LR[i].rend());
        for(auto r : LR[i]){
            int result = st.between(i-1, r-1);
            if(result < st.get(r)) st.update(r, result);
        }
        int result = st.get(i-1) + (B[i] ? 1 : -1);
        if(result < st.get(i)) st.update(i, result);
    }

    int ans = st.get(N) + num0;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11776
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;
using lli = long long int;
using tsi = tuple<string, lli,lli>;

vector<tsi> vec;

int main(void) {

	lli N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		string s;
		lli l;
		cin >> s >> l;
		vec.push_back(tsi{s,-1 * l, i});
	}

	sort(vec.begin(),vec.end());



	for (int i = 0; i < N; i++) {
		cout << get<2>(vec[i]) + 1 << endl;
	}

	return 0;
}


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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

signed main(){
	cout<<fixed<<setprecision(7);

	int n, a, b, c;
	
	cin>>n>>a>>b>>c;
	
	cout<<n-(a+b-c)<<endl;
	
	return 0;
}


Measured memory_bytes: 3088
#include <iostream>

using namespace std;

typedef long long INT;


static INT MOD = (INT)1000000007;
#define MAX 500000

INT modPow(INT a, INT b) {
    INT x = 1;
    
    while(b > 0){
        if (b & 1){
            x = (x*a)%MOD;
	}

        a = (a*a)%MOD;
        b /= 2;
    }

    return x;
}


INT modInv(INT x){
    return modPow(x, MOD-2);
}


INT mod(INT x) {
    x %= MOD;
    if (x < 0) {
	x += MOD;
    }

    return x;
}


int main(void) {
    static INT Facts[MAX+1];
    Facts[0] = 1;

    INT f = 1;
    for(INT i=1; i<=MAX; ++i){
	f = f*i%MOD;
	Facts[i] = f;
    }

    INT M, N;
    cin >> N >> M;

    INT a0 = Facts[M]*modInv(Facts[M-N])%MOD;
    INT a = a0;
    INT n = 1;
    INT b2 = Facts[M-N];

    for(INT i=1; i<=N; ++i) {
	n = n*(N-i+1)%MOD;
	b2 = b2*i%MOD;
	INT b = Facts[M-i]*n%MOD*modInv(b2)%MOD;

	if (i%2 == 1) {
	    b = -b;
	}

	a = mod(a + b);
    }
	
    cout <<mod(a*a0) << endl;
    return 0;
}



Measured memory_bytes: 7540
R, G, B, N = map(int, input().split())

R, G, B = tuple(sorted([R, G, B], reverse=True))

count = 0
r = N // R
for i in range(r+1):
    n = N - R * i
    g = n // G
    for j in range(g+1):
        m = n - G * j
        if m % B == 0:
            count += 1

print(count)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;

vector<ll> divisor(ll n) {
  vector<ll> res;
  res.push_back(1);
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i) continue;
    res.push_back(i);
    if (i * i != n) res.push_back(n / i);
  }
  if (n != 1) res.push_back(n);
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> nums(1000010);
  rep(i, n) {
    cin >> a[i];
    nums[a[i]]++;
  }

  int ans = 0;

  rep(i, n) {
    bool ok = true;
    auto divs = divisor(a[i]);
    for (auto div: divs) {
      if (div == a[i]) {
        if (nums[div] >= 2) ok = false;
      } else {
        if (nums[div] >= 1) ok = false;
      }
    }

    if (nums[a[i]] >= 2) ok = false;
    if(ok) {
      ans++;
    }
  }

  cout << ans << endl;


}

Measured memory_bytes: 7944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
    string s,t;
    bool hantei=true;
    cin >> s >> t;
    int size = s.size();
    rep(i,size){
        if(s[i] != t[i]) hantei =false;
    }
    if(hantei) cout << "Yes" <<endl;
    else cout << "No"<< endl;
}

Measured memory_bytes: 3628
import numpy as np
import fractions as fra



n,k=map(int,input().split())
d =[x for x in input().split()]

def che(s):#string s
    for x in s:
        for y in d:
            if(x==y):
                return 0
    return 1


for i in range(n,10**10):
    if(che(str(i))):
        print(i)
        exit(0)


Measured memory_bytes: 13540
int main()
{
  int n, m;
  scanf("%d %d", &n, &m);
  int h[n], a[m], b[m], i;
  int ans[n];
  for (i = 0; i < n; i++)
    ans[i] = 1;
  for (i = 0; i < n; i++)
    scanf("%d", &h[i]);
  for (i = 0; i < m; i++)
  {
    scanf("%d %d", &a[i], &b[i]);
    if (h[a[i]-1] > h[b[i]-1])
    {
      ans[a[i] - 1] *= 1;
      ans[b[i] - 1] = -1;
    }
    else if (h[a[i]-1] < h[b[i]-1])
    {
      ans[a[i] - 1] = -1;
      ans[b[i] - 1] *= 1;
    }
    else if (h[a[i]-1] == h[b[i]-1])
    {
      ans[a[i] - 1] = -1;
      ans[b[i] - 1] = -1;
    }
  }
  
  int cnt = 0;
  for (i = 0; i < n; i++)
  {
//    printf("%d = %d\n", i+1, ans[i]);
    if (ans[i] > 0)
    {
      cnt++;
    }
  }
  printf("%d", cnt);
  
}

Measured memory_bytes: 3236
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>

using namespace std;

typedef long long ll;

#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR1(i,n) for(int (i)=1;(i)<(n);(i)++)
#define eFOR(i,n) for(int (i)=0;(i)<=(n);(i)++)
#define eFOR1(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define INF 1000000000

int main() {

	int a, b;
	cin >> a >> b;
	if (a > 8 || b > 8)cout << ":(" << endl;
	else cout << "Yay!" << endl;

	return 0;
}


Measured memory_bytes: 256
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions

def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())


#n = ip()                              #入力整数1つ
a,b= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
c = []
for i in range(a):
    d = [int(i) for i in input().split()]
    d.pop(0)
    c.append(d)
s = set(c[0])
for i in range(1,a):
    s = s.intersection(set(c[i]))
print(len(s))



Measured memory_bytes: 23068
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    ll A,B,C; cin >> A >> B >> C;
    ll X,Y; cin >> X >> Y;
    ll out = __LONG_LONG_MAX__;
    ll cc = max(X,Y)*2;
    for(ll i=0;i<=cc;i++){
        ll cnt=0;
        ll ca = A*max(X-i/2LL,0LL);
        ll cb = B*max(Y-i/2LL,0LL);
        cnt = ca+cb+i*C;
        cerr << ca << " " << cb << " " << i*C << " " << cnt << endl;
        if(cnt<out) out = cnt;
    }
    cout << out << endl;
    return 0;
}


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

#define INF 1e9
#define PI 3.141592653589793238
typedef long long ll;

int main() {
    char c; cin>>c;
    c += 1;
    cout<<c<<endl;

    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

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

int p[200],q[50],dp1[1000000],dp2[1000000],n;

int main(){
	rep(i,200)p[i]=(i+1)*(i+2)*(i+3)/6;
	rep(i,50)q[i]=(4*i+1)*(4*i+2)*(4*i+3)/6;
	for(int i=1;i<1e6;i++){
		dp1[i]=dp2[i]=INF;
		rep(j,200)if(p[j]<=i)dp1[i]=min(dp1[i],dp1[i-p[j]]+1);
		rep(j,50)if(q[j]<=i)dp2[i]=min(dp2[i],dp2[i-q[j]]+1);
	}
	while(cin>>n&&n){
		cout<<dp1[n]<<" "<<dp2[n]<<endl;
	}
}

Measured memory_bytes: 8532
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			int count = 0;
			while(n!=1){
				if(n%2==0) n/=2;
				else n=n*3+1;
				count++;
			}
			System.out.println(count);
		}
	}	
}

Measured memory_bytes: 17200
# 問題：https://atcoder.jp/contests/abc142/tasks/abc142_b

n, k = map(int, input().strip().split())
h = list(map(int, input().strip().split()))
res = 0
for i in range(n):
    if h[i] < k:
        continue
    res += 1
print(res)



Measured memory_bytes: 18440
a,b=map(int,input().split())

if a!=1 and b!=1:
    if a>b:
        print('Alice')
    elif a<b:
        print('Bob')
    else:
        print('Draw')
elif a==1:
    if b==1:
        print('Draw')
    else:
        print('Alice')
else:
    print('Bob')


Measured memory_bytes: 2940
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char[] c = new char[2];
		int T = 0;
		for(int i = 0;i<s.length();i++) {
			char cc = s.charAt(i);
			if(i == 0) {
				c[i] = cc;
				continue;
			}
			if(c[0]==cc)continue;
			if(c[1]==cc)continue;
			if(c[0]!=cc && T == 0) {
				c[1] =cc;
				T++;
			}else {
				T = 2;
				break;
			}
		}
		if(T == 2 || T == 0) {
			System.out.println("No");
		}else {
			System.out.println("Yes");
		}
		
	}
	

}


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

int main() {
	string s;
	cin >> s;
	int value = s.size() - 2;
	while (true) {
		bool flag = true;
		for (int i = 0; i < value / 2; i++) {
			if (s[i] != s[value / 2 + i])flag = false;
		}
		if (flag) {
			cout << value << endl;
			return 0;
		}
		else {
			value -= 2;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n;
    ll x;
    cin>>n>>x;
    vector<ll> v;
    for(ll i=0;i<n;i++){
        ll k;
        cin>>k;
        v.pb(k);
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        if(v[i]>x){
            ans+=v[i]-x;
            v[i]=x;
        }
    }
    for(ll i=0;i<n-1;i++){
        if(v[i]+v[i+1]>x){
            ans+=v[i]+v[i+1]-x;
            v[i+1]=x-v[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

int main(){
    int N,K;
    cin >> N >> K;
    string S;
    cin >> S;
    int val = 0;

    for (int i = 0; i < N - 1;i++){
        if(S[i] == S[i+1])
            val++;
    }
    int tmp = N - val - 1;
    while(tmp > 1 && K > 0){
        val += 2;
        tmp -= 2;
        K--;
    }

    if(tmp == 1 && K != 0)
        val++;
    cout << val << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define FOR(x,i,e) for(int x=i; x<e; x++)
#define int long long int
 
signed main()
{
	int k;
	cin >>k;
	int p=7;
	FOR(i,0,k+1){
		if(p%k==0)
		{
			cout<<i+1<<endl;
			return 0;
		}
		p=(p*10+7)%k;
 
	}
	cout<<"-1"<<endl;
	return 0;
}

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

int main()
{
  int N, M;
  int ans = 0;
  cin >> N >> M;

  int tmp1 = 0, tmp2 = 0;
  if (N >= 2)
    tmp1 = N * (N - 1) / 2;
  if (M >= 2)
    tmp2 = M * (M - 1) / 2;

  ans = tmp1 + tmp2;

  cout << ans;
  return 0;
}

Measured memory_bytes: 256
takahashiSTA, takahashiAttack, aokiSTA, aokiAttack = map(int, input().split())
result = ""

while True:
    aokiSTA -= takahashiAttack #takahashi attack fase
    if aokiSTA <= 0:
        result = "Yes"
        break

    takahashiSTA -= aokiAttack  #aoki attack fase
    if takahashiSTA <= 0:
        result = "No"
        break 

print(result)



    


Measured memory_bytes: 9104
import java.io.IOException;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();		

		PriorityQueue<Integer> a = new PriorityQueue<>();
		for ( int i = 0; i < n; i++ ) {
			a.add(in.nextInt());
		}

		int[][] bc = new int[m][2];
		for ( int i = 0; i < m; i++ ) {
			bc[i][0] = in.nextInt();
			bc[i][1] = in.nextInt();
		}		

		Arrays.sort(bc, (o1, o2) -> o2[1] - o1[1]);

		for ( int i = 0; i < m; i++ ) {
			while ( !a.isEmpty() && a.peek() < bc[i][1] && 0 < bc[i][0] ) {
				a.poll();
				a.add(bc[i][1]);
				bc[i][0]--;
			}
		}
		
		long ans = 0L;
		for ( Integer i : a ) {
			ans += i;
		}
		System.out.println(ans);
		in.close();
	}
}

Measured memory_bytes: 100744
using System;
using System.Collections.Generic;
public class Aprob {
    public static void Main() {
        string[] readSome = new string[2];
        readSome = Console.ReadLine().Split(' ');
        long N, T;
        N = long.Parse(readSome[0]);
        T = long.Parse(readSome[1]);
        readSome = new string[N];
        long[] t = new long[N];
        readSome = Console.ReadLine().Split(' ');
        for (int i = 0; i < N; i++) {
            t[i] = long.Parse(readSome[i]);
        }
        long time = 0;
        for (int i = 0; i < N; i++) {
            if (i == 0) {
                time += T;
            } else {
                if (t[i] - t[i - 1] >= T) {
                    time += T;
                } else {
                    time += T;
                    time -= T - (t[i] - t[i - 1]);
                }
            }
        }
        Console.WriteLine(time);
    }
}

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

#define forn(i,n) for (int i = 0; i < int(n); i++)
#define si(c) ((int)(c).size())
#define pb push_back
#define mp make_pair
#define forsn(i,a,b) for (int i = int(a); i < int(b); i++)
#define dforsn(i,a,b) for (int i = int(b)-1; i >= int(a); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << " = " << a << endl;

typedef long long tint;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int MAXN = 1e5 + 100;

int n, q, a[MAXN];

void gen(int N, int S, int W) {
    int g = S; 
    for(int i=0; i<N; i++) { 
        a[i] = (g/7) % 10;
        if( g%2 == 0 ) { g = (g/2); }
        else           { g = (g/2) ^ W; }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    int s,w;
    while (cin >> n >> s >> w >> q && n) {
        gen(n,s,w);
        reverse(a,a+n);

        int res = 0;
        if (q == 2 || q == 5) {
            int cnt = 0;
            forn(i,n) {
                if (a[i] % q == 0) cnt++;
                if (a[i]) res += cnt;
            }
        }
        else {
            int cum = 0, pot10 = 1;
            map<int,int> cnt; cnt[0]++;
            forn(i,n) {
                cum = cum + pot10*a[i] % q;
                if (cum >= q) cum -= q;
                pot10 = pot10*10 % q;

                if (a[i]) res += cnt[cum];
                cnt[cum]++;
            }
        }
        cout << res << endl;
    }

	return 0;
}

Measured memory_bytes: 5816
#include <bits/stdc++.h>
#define rep(begin, end) for (i=begin;i<end;i++)
#define repj(begin, end) for (j=begin;j<end;j++)
#define init(arr, end, val) for (i=0;i<end;i++) arr[i] = val;
#define printint(i0, i1) printf("%d %d\n", i0, i1)

using namespace std;
typedef long long int ll;
const int inf = 1000000000;
const int mod = 1000000007;
const int nil = -1;
ll i, n, m;
ll x, k, d, ans;

int main() {
    scanf(" %lld %lld %lld", &x, &k, &d);
    if (x == 0) {
        if (k%2 == 0) ans = 0;
        else ans = d;
    } else  {
        x = abs(x);
        i = floor(x / d);
        if (i >= k) ans = abs(x - k * d);
        else {
            if ((k-i)%2 == 0) ans = abs(x - i*d);
            else ans = abs(x - (i+1)*d);
        }
    } 
    printf("%lld\n", ans);
}

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

using namespace std;

int main()
{
	//freopen("input.txt", "r", stdin);
    int A, B, C;
    while(cin>>A>>B>>C){
        int count=10;
        long long int result;
        while(count--){
            result = A*C-B;
            cout<<result<<endl;
            C = result;
        }
    }
	return 0;
}



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

long long N, A[87];
long long dp[87];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];

	dp[1] = 1000;
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1];
		for (int j = 1; j <= i - 1; j++) {
			long long V = dp[j] / A[j];
			long long W = dp[j] + (A[i] - A[j]) * V;
			dp[i] = max(dp[i], W);
		}
	}
	cout << dp[N] << endl;
	return 0;
}


Measured memory_bytes: 3604
/**Bismillahir Rahmanir Raheem
    Author:Refatul Fahad**/

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const ll M = (ll)1e9 + 7;
const double pi=2*acos(0.0);
const double esp=1e-9;
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}

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

int ar[2*N];
set<int>st;
map<int,int>mp;
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);

    int test=1;
    //cin>>test;
    for(int cs=1; cs<=test; ++cs) {
        int n;
        ll ans=0ll;
        cin>>n;
        for(int i=1; i<=n; ++i) {
            cin>>ar[i];
        }
        sort(ar+1,ar+n+1);
        mp[ar[n]]=1;
        st.insert(ar[n]);
        for(int i=n-1; i>=1; --i) {
            auto it=st.end();
            --it;
            ans+=*it;
            mp[*it]--;
            mp[ar[i]]+=2;
            if(mp[*it]==0)st.erase(it);
            st.insert(ar[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 18496
import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String [] args) throws IOException{
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

		boolean [] isVisit = new boolean[101];

		if(n > 0){
			st = new StringTokenizer(br.readLine());
			while(st.hasMoreTokens()){
				int cur = Integer.parseInt(st.nextToken());
				isVisit[cur] = true;
			}
		}

		int l = x, r = x;
		while(l > 0 && isVisit[l]) l--;
		while(r < 101 && isVisit[r]) r++;

		bw.write((x - l <= r - x ? l : r )+"" );
		bw.flush();
		bw.close();
		br.close();
	}
}

Measured memory_bytes: 36532
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

long long INF=numeric_limits<long long>::max();

ll d[1000001];
//ravenclaws1's sol
int main(){
	ll n, p;
	cin >> n >> p;
	if(n==1){
		cout << p << endl;
		return 0;
	}
	ll ans = 1;
	for(ll i = 2; i <= 1e6; i++){
		int cnt = 0;
		while(p%i==0){
			p/=i;
			cnt++;
		}
		cnt/=n;
		while(cnt){
			ans*=i;
			cnt--;
		}
	}
	cout << ans;
	return 0;
}


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



int main(int argc, char const *argv[])
{
    int A[3];
    cin >> A[0] >> A[1] >> A[2];
    sort(A,A+3);
    cout << A[0] << " " << A[1] << " " << A[2] << endl;
    

    
   
    
    
   return 0;


}



Measured memory_bytes: 3104
S=int(input())
arr=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(arr[S-1])

Measured memory_bytes: 3060
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;
const int L = 7;

int main() {
  int N, n;
  while(cin >>N && N){
    int cnt[L];
    memset(cnt, 0, sizeof(cnt));
    REP(i, N){
      cin >>n;
      REP(j, L - 1) if(10 * j <= n && 10 * j + 9 >= n) cnt[j]++;
      if(n >= 60) cnt[6]++;
    }
    REP(i, L) cout <<cnt[i] <<endl;
  }
  return 0;
}

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

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("2.out", "w", stdout);
	#else
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 200500, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

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

int main() {
  
	string s;
	cin >> s;
	int ans = 9 * (SZ(s) - 1);
	int sum = 0;
	for (int i = 0; i < SZ(s); i++) {
		if (s[i] > '1') ans = max(ans, sum + (SZ(s) - i - 1) * 9 + (s[i] - '1'));
		sum += (int)(s[i] - '0');
	}
	ans = max(ans, sum);
	cout << ans;
	return 0;	
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main() {
  int N, M, ans{};
  cin >> N >> M;
  vector<int> X(M);
  for (int &x : X) cin >> x, ans += x;

  if (N>=M) {
    cout << 0 << endl;
    return 0;
  }
  sort(begin(X),end(X));
  adjacent_difference(begin(X),end(X),begin(X));
  sort(begin(X)+1,end(X));

  cout << accumulate(begin(X)+1,begin(X)+M-N+1,0)
       << endl;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
#define int long
main(){
  int n,s=0;
  cin>>n;
  vector<int> a(2*n);
  for(auto& i:a)cin>>i,s+=i;
  for(int i=0;i<n;++i)a[i+n]=a[i];
  s/=2;
  vector<int> e(n),o(n);
  for(int i=0;i<2*n;++i){
    if(i%2){
      o[i/2]=a[i];
      if(i/2)o[i/2]+=o[i/2-1];
    }
    else{
      e[i/2]=a[i];
      if(i/2)e[i/2]+=e[i/2-1];
    }
  }
  vector<int> b(n);
  for(int i=0;i<n;++i){
    if(i%2)b[i]=e[(i-1+2*(n/2))/2]-e[(i+1)/2-1];
    else b[i]=o[(i-1+2*(n/2))/2]-(i?o[(i+1)/2-1]:0);
  }
  for(int i=0;i<n;++i){
    if(i)cout<<" ";
    cout<<(s-b[i])*2;
  }
}

Measured memory_bytes: 5248
n,y=(int(i) for i in input().split())

ans=(-1,-1,-1)
for a in range(n + 1):
    for b in range(n - a + 1):
        c = n -a -b 
        if a* 10 + b* 5 + c == y/1000:
            ans=(a,b,c)
            break
print("%d %d %d"%ans)


Measured memory_bytes: 3060
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
using namespace std;
typedef long long ll;
#define free  freopen ("input.txt", "r", stdin);freopen ("output.txt", "w", stdout);
#define Fast  ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second

bool vowel(char che)
{
    if (che == 'A' || che == 'E' || che == 'I' || che == 'O' || che == 'U' || che == 'Y')
        return true;
    else
        return false;
}

const int N = 1e6+5;
const int mod = 1e9+7;
ll a[N], b[N], c[N], d, dp, dis, tree[N];
pair <int, int> p;
char o;
bool mark[N], h;
string s, s1;
stack <int> st;
set <ll> st1, st2;
deque <int> dq;
vector <int> vt, vs, vm;
//int a1[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};


int main()
{
    Fast
    ll t, n, m, k = 0, f = 0, sum = 0, ans = 0, n1 = 0;
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; (i*j) < n; j++){
            ans ++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3644
#include<stdio.h>
int main(){
  int N;
  scanf("%d",&N);
  int a[N],b[N],c[N];
  for(int i=0;i<N;i++){
    scanf("%d",&a[i]);
    b[i]=i+1;
    c[i]=a[i];
  }
  int x=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      a[i]=c[j];
      a[j]=c[i];
      for(int k=0;k<N;k++){
        if(a[k]==b[k])
          x++;
      }
      if(x==N){
        printf("YES\n");
        return 0;
      }
      x=0;
      a[i]=c[i];
      a[j]=c[j];
    }
  }
  printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
l,r = map(int, input().split())

#l,r = 4,5

if r-l>=2019:
    times = 2019
else:
    times = r-l

add = l
ans = 2019
for i in range(times):
    for j in range(times+1):
        if i<j:
            cnt = ((add+i)*(add+j))%2019
            ans = min(ans,cnt)
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
using namespace std;
vector <vector <int> > adj;
vector <long long> black, white;
const long long nine = 1000000007; 

void dfs (int cur = 1, int prev = 0)
{
	for (int i: adj[cur])
		if (i != prev)
		{
			dfs(i, cur);
			black[cur] = black[cur]*white[i] % nine;
			white[cur] = white[cur]*(black[i] + white[i]) % nine;
		}
}

int main() 
{
	int n, a, b;
	cin >> n;
	adj.resize(n + 1);
	black.resize(n + 1, 1);
	white.resize(n + 1, 1);
	
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs();
	cout << (black[1] + white[1]) % nine;
}

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

int main() {
	int n;
	cin >> n;
	int taro = 0;
	int hanako = 0;
	for(int i = 0; i < n; i++) {
		string taro_word, hanako_word;
		cin >> taro_word >> hanako_word;
		if(taro_word > hanako_word) {
			taro += 3;
		}
		else if(taro_word < hanako_word) {
			hanako += 3;
		}
		else {
			taro++, hanako++;
		}
	}
	cout << taro << " " << hanako << endl;
}


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

#define REP(i, n) for(int i = 0; i != n; ++i)
#define REPR(i, n) for(int i = n - 1; i != -1; --i)
#define FOR(i, a, b) for(int i = a; i != b; ++i)
#define RBF(i, n) for(auto &i : n)
#define ABS(n) (n < 0 ? -n : n)
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
#define IN(n) (cin >> n)
#define OUT(n) (cout << n << "\n")
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define V vector<int>

using namespace std;
using ll = long long;

int main() {
    int N;
    IN(N);
    V A(N);
    REP(i, N) IN(A[i]);
    int count = 0;
    while(true) {
        REP(i, N) {
            if(A[i] % 2 != 0) {
                OUT(count);
                return 0;
            }
            A[i] /= 2;
        }
        count++;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// for (int i = 0; i < N; i++) {
// strint'', char'
//エスケープシークエンス改行になる\n　cout << "こんにちは\nAtCoder";
// 行全て取り出す　getline(cin, 文字列変数);
// 配列　vector<型> vec(要素数, 初期値);　　vec.at(i)　　vec.size()
// int型 data[要素数]; // Cの配列

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  int count = 0;
  bool flag = true;
  int now = 1;
  for (int i = 0; i < n; i++) {
  	cin >> vec.at(i);
  }
  for (int i = 0; i < n; i++) {
    count++;
    now = vec.at(now-1);
    if (now == 2) { 
      cout << count << endl;
      flag = false;
      break;
    }
  }
  if (flag) {
    cout << -1 << endl;
 }
 
}





Measured memory_bytes: 3796
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;


int par[100000], q[100000];
int find(int x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}

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

	int N, M, K;
	cin >> N >> M >> K;
	REP(i, N)par[i] = i;
	REP(i, 100000)q[i] = -1;

	REP(i, K) {
		int a, b, c;
		cin >> a >> b >> c;
		b--;
		c--;
		if (a == 1) {
			b = find(b);
			c = find(c);
			if (q[b] != -1 && q[c] != -1) {
				if (q[b] != q[c]) {
					cout << i + 1 << endl;
					return 0;
				}
			}
			par[b] = c;
			q[c] = max(q[b], q[c]);
		}
		else {
			b = find(b);
			if (q[b] != -1 && q[b] != c) {
				cout << i + 1 << endl;
				return 0;
			}
			q[b] = c;
		}
	}

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




Measured memory_bytes: 4776
import sys
import random
H,W,M=map(int,input().split())

hlist=[0]*H
wlist=[0]*W
hwset=set()
for _ in range(M):
  h,w=map(int,input().split())
  hlist[h-1]+=1
  wlist[w-1]+=1
  hwset.add((h-1,w-1))
  
hmax=max(hlist)
wmax=max(wlist)

hlist2=[]
for i in range(H):
  if hlist[i]==hmax:
    hlist2.append(i)
hlist2.sort(reverse=True)
random.shuffle(hlist2)

wlist2=[]
for i in range(W):
  if wlist[i]==wmax:
    wlist2.append(i)
wlist2.sort(reverse=True)
random.shuffle(wlist2)

#print(hlist2,wlist2)
H2=len(hlist2)
W2=len(wlist2)

if H2*W2>=10**7:
  norm=(H2*W2)//(10**7)
  H2=int(H2/(norm**0.5))
  W2=int(W2/(norm**0.5))

for i in range(H2):
  ii=hlist2[i]
  for j in range(W2):
    jj=wlist2[j]
    if not (ii,jj) in hwset:
      print(hmax+wmax)
      sys.exit(0)
else:
  print(hmax+wmax-1)

Measured memory_bytes: 168120