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

using namespace std;

long long x;

int main()
{
    long long sum = 100 , ans = 0;
    cin >> x;
    while(sum < x)
    {
        ++ans;
        sum = sum + (sum / 100);
    }
    cout << ans << "\n";
    return 0;
}


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

int main() {
  int k, a, b;
  cin >> k >> a >> b;
  bool flag = false;
  for(int i = a; i <= b; i++) {
    if(i % k == 0) {
      flag = true;
      break;
    }
  }
  if(flag) cout << "OK" << endl;
  else cout << "NG" << endl;
  return 0;
}

Measured memory_bytes: 3600
//#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
//#include<iomanip>
using namespace std;

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

	int a, b;
	string op;
	int ans;
	do{
		cin >> a >> op >> b;
		if (op[0] == '?'){
			break;
		}
		switch (op[0]){
		case '+':
			ans = a + b;
			break;
		case '-':
			ans = a - b;
			break;
		case '*':
			ans = a * b;
			break;
		case '/':
			ans = a / b;
			break;
		}
		cout << ans << "\n";
	} while (op[0] != '?');

	return 0;
}


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

int main(){
  int a,b;
  cin>>a>>b;
  
  int n=a;
  int count=0;
  
   for(int i=a;i<=b;i++){
     int s=i%10; int t=i/10000%10;
     int u=i/10%10; int v=i/1000%10;
    
    if(s==t and u==v){
       count++;
    }
  }
  cout<<count<<endl;
}

  
  
    
  
  
      
  


Measured memory_bytes: 256
#include <stdio.h>
int main() {
    int n,p,c = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%d",&p);
        if(i == p) {
            c++;
            scanf("%d",&p);
            i++;
        }
    }
    printf("%d",c);
    return 0;
}

Measured memory_bytes: 128
#!/usr/bin/env python
# coding: utf-8

# In[12]:


from collections import deque


# In[1]:


K = int(input())


# In[15]:


q = deque(list(range(1,10)))
for i in range(K-1):
    x = q.popleft()
    if x%10 != 0:
        y = x*10 + x%10 - 1
        q.append(y)
    y = x*10 + x%10
    q.append(y)
    
    if x%10 != 9:
        y = x*10 + x%10 + 1
        q.append(y)
    
ans = q.popleft()
print(ans)


# In[ ]:






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

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

namespace _20192abc1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int T = int.Parse(s[1]);

            double d = (double)N / T;

            Console.WriteLine(d);
        }
    }
}


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

const ll s = pow(3, 29);
ll solve(ll a1, ll a2, ll b1, ll b2) {
  if (a2 > b2) {
    swap(a1, b1);
    swap(a2, b2);
  }
  ll res = abs(a1-b1) + abs(a2-b2);
  for (ll ss = s; ss > 0; ss /= 3) {
    ll na1 = a1 / ss, nb1 = b1 / ss;
    if (na1 != nb1) break;
    ll na2 = a2 / ss, nb2 = b2 / ss;
    if (na1%3 == 1 && abs(nb2 - na2) > 1) {
      ll up = ss*na1 - 1;
      ll down = ss*(na1+1);
      ll loss = min(min(a1, b1)-up, down-max(a1, b1));
      res += 2*loss;
      break;
    }
  }
  return res;
}

int main () {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  int q;
  cin >> q;
  rep(i, q) {
    ll ai, aj, bi, bj;
    cin >> ai >> aj >> bi >> bj;
    --ai, --aj, --bi, --bj;
    ll ans = 0;
    ans = max(ans, solve(ai, aj, bi, bj));
    ans = max(ans, solve(aj, ai, bj, bi));
    cout << ans << endl;
  }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define sort_(a) sort(a.begin(), a.end())
#define rsort(a) sort(a.rbegin(), a.rend())
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; 0 <= i; i--)
#define for_(i, start, end) for (int i = start; i < end; i++)
#define rfor(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD53       = 998'244'353;
constexpr double PI       = 3.14159265358979323846;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void scan() {}
template <class H, class... T> void scan(H &&head, T &&... args) {
    std::cin >> head;
    scan(std::forward<T>(args)...);
}
template <class T> void scan(std::vector<T> &v) {
    for (auto &&i : v) {
        scan(i);
    }
}

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

    int N;
    scan(N);
    vector<int> dp(N + 1);
    for_(i, 100, 106) {
        if (i <= N) {
            dp[i] = 1;
        }
    }
    rep(i, N + 1) {
        for_(money, 100, 106) {
            int x = i - money;
            if (0 <= x && dp[x]) {
                dp[i] = 1;
            }
        }
    }
    print(dp[N]);

    return 0;
}

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

int n, m;
vector<int> A;
vector<pair<int, int>> CB;

void input() {
    cin >> n >> m;
    A = vector<int>(n);
    CB = vector<pair<int, int>>(m);
    rep(i, n) cin >> A[i];
    rep(i, m) cin >> CB[i].second >> CB[i].first;
}

int main() {
    input();
    sort(A.begin(), A.end());
    sort(CB.rbegin(), CB.rend());
    int x = 0;
    for (auto p : CB) {
        while (A[x] < p.first) {
            A[x++] = p.first;
            p.second--;
            if (x == n) goto endloop;
            if (p.second == 0) break;
        }
    }
    endloop:
    ll ans = 0;
    for (int a : A) ans += a;
    cout << ans << endl;
}


Measured memory_bytes: 1408
#include "bits/stdc++.h"
using namespace std;
int main()
{
    long long n, m, total = 0, mod = 1000000007;
    scanf("%lld%lld", &n, &m);
    if(abs(n - m) <= 1)
    {
        total = 1;
        for(int i = n; i; (total *= i--) %= mod){}
        for(int i = m; i; (total *= i--) %= mod){}
        if(n == m)
        {
            (total *= 2) %= mod;
        }
    }
    printf("%lld\n", total);
}

Measured memory_bytes: 256
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
 
#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        mut h: [usize; n],
    }
    let mut ans = vec![true; n];

    for _ in 0..m {
        input! {
            a: Usize1,
            b: Usize1,
        }
        if h[a] >= h[b] {
            ans[b] = false;
        } 
        if h[a] <= h[b] {
            ans[a] = false;
        }
    }

    println!("{}", ans.into_iter().filter(|hi| *hi).count());
}


Measured memory_bytes: 5084
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner sc=new Scanner(System.in);
	    int t=sc.nextInt();
	    System.out.println(t+t*t+t*t*t);
	   }
}

Measured memory_bytes: 35616
#include<iostream>
using namespace std;
int main(){
	long long n,m;
	cin>>m>>n;
	if(n%m==0){
		cout<<n/m<<endl;
	}else{
		long t;
		t=n/m+1;
		for(int i=t;i>=1;i--){
			if(n%i==0){
				cout<<i<<endl;
				break;
			}
		}
	} 
	
	
	return 0;
} 

Measured memory_bytes: 256
#include <stdio.h>
//#define scanf scanf_s
typedef long long int lli;

// ITP1_2_C
// 3整数a,b,cを読み込み、昇順に出力
int main()
{

	int iInputN[3];
	int iCnt;
	int iCnt2;
	int iValueTmp;

	for (iCnt = 0; iCnt < 3; iCnt++)
	{
		scanf("%d", &iInputN[iCnt]);
	}

	//バブルソート
	for (iCnt = 0; iCnt < 2; iCnt++)
	{
		for (iCnt2 = iCnt + 1; iCnt2 < 3; iCnt2++)
		{
			if (iInputN[iCnt] > iInputN[iCnt2])
			{
				iValueTmp = iInputN[iCnt];
				iInputN[iCnt] = iInputN[iCnt2];
				iInputN[iCnt2] = iValueTmp;
			}
		}
	}

	for (iCnt = 0; iCnt < 2; iCnt++)
	{
		printf("%d ", iInputN[iCnt]);
	}
	printf("%d\n", iInputN[iCnt]);

	return 0;
}


Measured memory_bytes: 2032
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>

#define ll long long
#define sz 1005

using namespace std;

int main()
{
    ll a,b;
    
    scanf("%lld %lld",&a,&b);
    
    ll c=a-b;
    
    if(c<=0)
        printf("0\n");
    
    else
        printf("%lld\n",c);

    return (0);
}


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

int main() {
	int num[6]={0};
	int n; cin >> n ;
	for(int i=0;i<n;i++){
		double tmp; cin >> tmp;
		if(tmp<165.0) num[0]++;
		else if(tmp>=185) num[5]++;
		else num[(int)((tmp-165)/5)+1]++;
	}
	for(int i=0;i<6;i++){
		cout << i+1 << ':' ;
		for(int j=0;j<num[i];j++) cout << '*' ;
		cout << '\n' ;
	}
}

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

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

int main()
{
  int N, Y;
  cin >> N >> Y;
  bool b = false;

  rep(i, N+1)
  {
    rep(j, N+1)
    {
      if((i + j) > N)
      {
        break;
      }
      int z = N - (i + j);
      if(Y == (i * 10000 + j * 5000 + z * 1000))
      {
        cout << i << ' ' << j << ' ' << z << endl;
        b = true;
        break;
      }
    }

    if(b)
    {
      break;
    }
  }

  if(!b)
  {
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;
  }
}

Measured memory_bytes: 256
// #include C/C++ {
#include <bits/stdc++.h>
// }
using namespace std;
// #typedef {
typedef long long int64;
typedef pair <int, int> PII;
typedef pair <int64, int64> PLL;
// }

// #parameter{
#ifdef _DEBUG

#define TYPE decltype
#define RF(filename) {freopen((filename), "r", stdin);}
#define WF(filename) {freopen((filename), "w", stdout);}
#define DF(filename) {freopen((filename), "w", stderr);}
#define eprintf printf

#else

#define TYPE __typeof
#define RF(filename) {;}
#define WF(filename) {;}
#define DF(filename) {;}
#define eprintf(...)
#define fprintf(...)

#endif

// #define {
#define SZ(a) ((int)(a).size())
#define X first
#define Y second
#define MP make_pair
#define L(x) ((x)<<1)
#define R(x) ((x)<<1 | 1)
#define max3(x, y, z) (max(max((x), (y)), (z)))
#define min3(x, y, z) (min(min((x), (y)), (z)))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(it) (it).begin(), (it).end()
#define FILL(__space, __val) memset(__space, __val, sizeof(__space))
#define MOVE(__spaceTo, __spaceFrom) memmove(__spaceTo, __spaceFrom, sizeof(__spaceTo))
#define UNIQUE(__vector) sort(ALL(__vector)), __vector.resize(unique(ALL(__vector)) - __vector.begin())
#define FOR(it, c) for( TYPE((c).begin()) it = (c).begin(); it != (c).end(); it++)
/////////////////////////////////////////////////////////////
const double PI = acos(-1.0);
const double EPS = 1e-6;

#define MAX_N 105
#define MAX_M 55
#define MOD (int)(1e9+7)
#define INF ((1 << 30) - 1)
#define BINF ((1LL << 62) - 1LL)
#define NONE -1
#define NIL 0
// }

/////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////
int main() {
	RF("input.txt");
	//  WF("output.txt");
	DF("err.txt");

	char s[MAX_N];
	scanf("%s", s);
	int o = 0, x = 0;
	for (char ch : s) if (ch == 'o') o++; else if(ch == 'x') x++;
	if (15 - x >= 8) puts("YES"); else puts("NO");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<limits>
#include<list>
#include <stdio.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0;i < (n); ++i)
#pragma GCC optimize("Ofast")



int main() {
	ll n;
	cin >> n;
	vector<ll>a(n);
	rep(i, n) {
		cin >> a[i];
	}
	if (n == 1) {
		cout << 0 << endl;
		return 0;
	}
	ll count = 0;

	for (int i = 0; i < (n - 1); i++) {
		if (a[i + 1] >= a[i]) {
			continue;
		}
		else {
			count += a[i] - a[i + 1];
			a[i + 1] += a[i] - a[i + 1];
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 4804
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e2 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

ll gt[maxN][4], eq[maxN][4], sm[maxN][4], k;
string st;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	cin >> st >> k;
	eq[st.size()][0] = 1;
	for(int i = st.size() - 1; i >= 0; i--) {
		{
			if(st[i] == '0') {
				memcpy(eq[i], eq[i + 1], sizeof eq[i]);
				memcpy(sm[i], sm[i + 1], sizeof sm[i]);
				memcpy(gt[i], gt[i + 1], sizeof gt[i]);
			} else {
				for(int j = 0; j <= k; j++) 
					sm[i][j] += eq[i + 1][j] + sm[i + 1][j] + gt[i + 1][j];
			}
		}

		{
			for(int j = 1; j <= k; j++)
				sm[i][j] += max(0, st[i] - '1') * 
					(eq[i + 1][j - 1] + sm[i + 1][j - 1] + gt[i + 1][j - 1]);
		}

		if(st[i] != '0') {
			for(int j = 1; j <= k; j++) {
				sm[i][j] += sm[i + 1][j - 1];
				gt[i][j] += gt[i + 1][j - 1];
				eq[i][j] += eq[i + 1][j - 1];
			}
		}

		{
			for(int j = 1; j <= k; j++)
				gt[i][j] += max(0, '9' - st[i]) * 
					(eq[i + 1][j - 1] + sm[i + 1][j - 1] + gt[i + 1][j - 1]);

		}
	}
	cout << sm[0][k] + eq[0][k] << '\n';
}


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

using namespace std;
#define inf             0x3f3f3f3f
#define INF             2e18
#define eps             1e-9

#define FastRead        ios_base::sync_with_stdio(0);cin.tie(0)
#define fRead           freopen("input.txt","r",stdin)
#define fWrite          freopen("output.txt","w",stdout)

#define LL              long long
#define ull            unsigned long long
#define PI              acos(-1.0)
#define pb              push_back
#define mk              make_pair
#define pii             pair<int,int>
#define pLL             pair<LL,LL>
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define SQR(a)          ((a)*(a))
#define min3(a,b,c)     min(a,min(b,c))
#define max3(a,b,c)     max(a,max(b,c))
#define min4(a,b,c,d)   min(min(a,b),min(c,d))
#define max4(a,b,c,d)   max(max(a,b),max(c,d))
#define max5(a,b,c,d,e) max(max3(a,b,c),max(d,e))
#define min5(a,b,c,d,e) min(min3(a,b,c),min(d,e))
#define vi              vector <int>
#define vL              vector <LL>
#define LB(a,x)         (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x)         (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define prec(n)         fixed << setprecision(n)

#define MEM(a,x)        memset(a,x,sizeof(a))
#define SORT(v)         sort(v.begin(),v.end())
#define REV(v)          reverse(v.begin(),v.end())
#define Unique(a)       sort(all(a)),a.erase(unique(all(a)),a.end())

#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)
#define IT(it,x)	    for(it=x.begin();it!=x.end();it++)
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=0; i<=100000; i++)
    {
        if(int(i*.08)==a and int(i*.1)==b)
        {
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
}


Measured memory_bytes: 3592
#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;
     
    int main() {
        string S, T;
        cin >> S >> T;
     
        //Initialize ans with a temporal value.
        //This value should be large enough; otherwise you will get wrong answer
        //Make sure that the value will lead to the correct answer.
        int ans = T.size();
     
        //Brute force through all initial position in S
        for (int start = 0; start <= S.size() - T.size(); start++)
        {
            int diff = 0;
            for (int i = 0; i < T.size(); i++)
            {
                if (T[i] != S[start + i]) {
                    diff++;
                }
            }
            ans = min(ans, diff);
        }
     
        cout << ans << endl;
    }

Measured memory_bytes: 3632
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

LL mul(LL a,LL b){
  return ((a % mod) * (b % mod)) % mod;
}

LL power(LL x,LL y){//繰り返し二乗法
  if(y==0)return 1;
  else if(y==1)return x%mod;
  else if(y%2==0){
    LL tmp=power(x, y/2) % mod;
    return tmp*tmp%mod;
  }else {
    LL tmp=power(x, y/2) % mod;
    return ((tmp*tmp)%mod)*x%mod;
  }
}

LL div(LL a,LL b){
  return mul(a,power(b,mod-2));
}


int invfact[100005];
int fact[100005];

LL factset(int a){//aまでの階乗%mod表を作成
	fact[0]=1;
  fact[1]=1;
  FORQ(i,2,a){
    fact[i]=mul(fact[i-1],i);
  }
}

void cmbset(int a){//1~aまでの階乗と階乗数の逆元のmod(mod)を用意 O(a)
  factset(a);
  invfact[a]=power(fact[a],mod-2);
	invfact[0]=1;
  FORD(i,a,1){
    invfact[i]=mul(invfact[i+1],i+1);
  }

}

LL cmb(int n,int r){//nCr%mod  (cmbset後に使用)
	if(n<r||r<0||n<0)return 0;
	return mul(fact[n],mul(invfact[r],invfact[n-r]));
}

LL  prm(int n,int r){//nPr%mod
    return mul(cmb(n,r),fact[n]);
}

LL homo(int n,int r){//nHr%mod
  return cmb(n+r-1,r);
}

int main(){
	int n,a[111111]={};
	cin>>n;
	int l=0,r=0,m;
	FOR(i,0,n+1){
		cin>>m;
		//cout<<"m"<<m<<" ";
		if(a[m]==0)a[m]=i+1;
		else {
			l=a[m];
			r=i+1;
			//cout<<l<<" "<<r<<endl;
			break;
		}
		//cout<<a[m];
	}
	m=n-r+l;
	//cout<<"m"<<m<<endl;
	cmbset(n+1);
	FORQ(i,1,n+1){
		//cout<<cmb(n+1,i)<<" "<<cmb(m,i-1)<<endl;
		int ans=(cmb(n+1,i)+mod-cmb(m,i-1))%mod;
		cout<<ans<<endl;
	}

    return 0;
}


Measured memory_bytes: 2432
// D - Transit Tree Path

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

struct Edge {
	int to_idx;
	ll cost;
};

struct Node {
	vector<Edge> edges;
	ll total_cost = 0;
	bool visited = false;
};

Node nodes[100000];

void dfs(int idx, ll total_cost) {
	nodes[idx].total_cost = total_cost;
	nodes[idx].visited = true;

	for (Edge e : nodes[idx].edges) {
		if (nodes[e.to_idx].visited) continue;
		dfs(e.to_idx, total_cost + e.cost);
	}
}

int main() {
	int N;
	cin >> N;

	int a, b, c;
	for (int i=0; i<N-1; i++) {
		cin >> a >> b >> c;
		a--;
		b--;
		nodes[a].edges.push_back(Edge{b, c});
		nodes[b].edges.push_back(Edge{a, c});
	}

	int Q, K;
	cin >> Q >> K;
	K--;

	dfs(K, 0);

	int x, y;
	vector<ll> ans;
	for (int i=0; i<Q; i++) {
		cin >> x >> y;
		x--;
		y--;

		ans.push_back(nodes[x].total_cost + nodes[y].total_cost);
	}

	for (ll a : ans) {
		cout << a << endl;
	}

	return 0;
}

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

using namespace std;

using ll=long long ;

#define rep(i) for(int i:{1,-1})

void solve() {
    int n,m;
    cin >> n >> m;
    vector<array<ll,3>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    ll res = -1e15;
    rep(x)rep(y)rep(z) {
        vector<ll> b(n);
        for (int i = 0; i < n; i++) {
            b[i] = (ll)x*a[i][0] + y*a[i][1] + z*a[i][2];
        }
        sort(b.begin(), b.end(), greater<ll>());
        ll tmp = 0;
        for (int i = 0; i < m; i++) {
            tmp += b[i];
        }
        res = max(res, tmp);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		
		while (true)
		{
			int a[] = new int[3];
			for (int i = 0; i < 3; i++)
				a[i] = sc.nextInt();
			if (a[0] == 0 && a[1] == 0 && a[2] == 0) break;
			
			Arrays.sort(a);
			int minR = a[0] * a[0] + a[1] * a[1];
			
			int n = sc.nextInt();
			for (int i = 0; i < n; i++)
			{
				int r = sc.nextInt() * 2;
				if (minR < r * r) System.out.println("OK");
				else System.out.println("NA");
			}
		}
	}
}

Measured memory_bytes: 12000
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

ll MOD;

int calc_lg(ll x) {
  int res = 0;
  while (x > 0) {
    ++res;
    x /= 10;
  }
  return res;
}

ll calc_ten(int e) {
  ll v = 1;
  for (int i = 0; i < e; i++) v *= 10;
  return v;
}

ll power(ll x, ll e) {
  x %= MOD;
  ll v = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) {
      v = v * x % MOD;
    }
    x = x * x % MOD;
  }
  return v;
}

// sum[ x^i, {i, 0, e}]
ll geometricSum(ll x, ll e) {
  x %= MOD;
  ll n = e + 1, v = 0, p = 1;
  for (int b = 63 - __builtin_clzll(n); b >= 0; b--) {
    v = (v * p % MOD + v) % MOD;
    p = p * p % MOD;
    if ((n >> b) & 1) {
      v = (v * x + 1) % MOD;
      p = p * x % MOD;
    }
  }
  return v;
}

// sum[i * x^(n-1-i), {i, 0, n - 1}]
ll func(ll b, ll n) {
  if (n == 1) return 0;
  ll a = func(b, n / 2);
  ll x = a;
  x += (n - n / 2) % MOD * geometricSum(b, n / 2 - 1) % MOD;
  x %= MOD;
  ll y = a * power(b, (n + 1) / 2) % MOD;
  ll res = (x + y) % MOD;
  if (n % 2 == 1) {
    res += (n / 2) % MOD * power(b, n / 2) % MOD;
    res %= MOD;
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  ll L, A, B;
  while (cin >> L >> A >> B >> MOD) {
    ll res = 0, cur = 0;
    while (cur < L) {
      int lg = calc_lg(A);
      ll ten = calc_ten(lg);
      // x >= (ten - A) / B
      ll x = min(L - cur, (ten - A + B - 1) / B);
      res = res * power(ten, x) % MOD;
      res += A % MOD * geometricSum(ten % MOD, x - 1) % MOD;
      res %= MOD;
      res += B % MOD * func(ten % MOD, x) % MOD;
      res %= MOD;
      cur += x;
      A += B * x;
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define GSORT(x) sort(all(x), greater<int>())
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef long long int64;
template<class T,class U>bool chmax(T &a, const U &b) { if (a<b) { a=b; return true; } return false; }
template<class T,class U>bool chmin(T &a, const U &b) { if (b<a) { a=b; return true; } return false; }
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cii(d);
    string ans;
    if (d==25)
        ans = "Christmas";
    if (d==24)
        ans = "Christmas Eve";
    if (d==23)
        ans = "Christmas Eve Eve";
    if (d==22)
        ans = "Christmas Eve Eve Eve";
    co(ans);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX(X, Y) (((X) > (Y))? (X) : (Y))
#define MIN(X, Y) (((X) < (Y))? (X) : (Y))
int compare_int(const void *a, const void *b){
  return *(long int*)b - *(long int*)a; // 大きい順
}
int compare_int_small(const void *a, const void *b){
  return *(long int*)a - *(long int*)b; // 小さい順
}
// 公約数
long long int gcd(long long int a, long long int b){
  if(b == 0){
    return a;
  }else{
    return gcd(b, a % b);
  }
}
// 最小公倍数 = a * b / 最大公約数
// 公倍数
long long int lcm(long long int a, long long int b){
  return a * b / gcd(a, b);
}

// 5min
int main(void){
  int r, d, x;
  int ans = 0;

  scanf("%d%d%d", &r, &d, &x);

  ans = x;
  for(int i = 0; i < 10; i++){
    ans = r * ans - d;
    printf("%d\n", ans);
  }
  
  return 0;
}


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

int main() {
  int N;
  cin>>N;


  if(N/1000==N%1000/100 && N/1000==N%100/10){
    cout<<"Yes"<<endl;
  }
  else if(N%1000/100==N%100/10 && N%1000/100==N%10){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(b<c){
        b=b+c;
        c=b-c;
        b=b-c;
    }

    if(a<b){
        a=a+b;
        b=a-b;
        a=a-b;
    }

    a=b+c;



    printf("%d",a);


    return 0;

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int n,dp[105][2][5],K;
int main(){
	cin>>s>>K;n=s.size();s="$"+s;
	for (int i=1;i<=n;i++) s[i]-='0';
	dp[0][1][0]=1;
	for (int i=1;i<=n;i++){
		for(int k=0;k<=K;k++){
			if (s[i]==0) dp[i][1][k]+=dp[i-1][1][k],dp[i][0][k]+=dp[i-1][0][k];
			else dp[i][0][k]+=dp[i-1][0][k]+dp[i-1][1][k];
			for (int j=1;j<10;j++){
				if (s[i]<j){
					dp[i][0][k+1]+=dp[i-1][0][k];
				}
				if (s[i]>j){
					dp[i][0][k+1]+=dp[i-1][0][k]+dp[i-1][1][k];
				}
				if (s[i]==j){
					dp[i][1][k+1]+=dp[i-1][1][k];
					dp[i][0][k+1]+=dp[i-1][0][k]; 
				}
			}
		}
	}
	cout<<dp[n][1][K]+dp[n][0][K];
}

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

int main() {
    int n, s;
    while (cin >> n >> s, n || s) {
        int cnt = 0;
        int cmb = (1 << n) - 1;
        while (cmb < 1 << 10) {
            int sum = 0;
            for (int i=0; i<=9; ++i) {
                if ((cmb >> i) & 1) {
                    sum += i;
                }
            }
            if (sum == s) {
                cnt ++;
            }
            int x = cmb & -cmb, y = cmb + x;
            cmb = ((cmb & ~y) / x >> 1) | y;
        }
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
using namespace std;
int n,i;
char c[1000010];
int main()
{
  //freopen("t2.in","r",stdin);
  //freopen("t2.out","w",stdout);
  scanf("%d\n",&n);
  bool flag=1;
  for(i=1;i<=n;i++)scanf("%c",&c[i]);
  if(n%2==1)flag=0;
  if(n%2==0)
  {
    for(i=1;i<=n/2;i++)
      if(c[i]!=c[i+n/2])flag=0;
  }
  if(!flag)cout<<"No";
  else cout<<"Yes";
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	float d,e,f,g,h,i,m,n,x;
	for(;~scanf("%f%f%f%f%f%f%f%f",&d,&e,&f,&g,&h,&i,&m,&n);){
		x=(h-f)*(n-g)-(m-f)*(i-g);
		bool ret=x*(f-d)*(n-e)>x*(m-d)*(g-e)&&x*(d-h)*(n-i)>x*(m-h)*(e-i);
		puts(ret?"YES":"NO");
	}
}

Measured memory_bytes: 1036
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int ans=-1,cnt=0;;
	for(int i=0;i<s.size();i++){
		if(s[i]!='A'&&s[i]!='T'&&s[i]!='C'&&s[i]!='G'){
			ans=max(ans,cnt);
			cnt=0;
		}
		else{
			cnt++;
			ans=max(ans,cnt);
		}
	}
	cout<<ans;
}

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

int n;
int dp[500005][4];
int len[500005];
int len2[500005];

int main(void){
	scanf("%d",&n);
	string str;
	cin >> str;
	for(int i=0;i<n;i++){
		if(str[i]=='0'){
			len[i+1]=0;
		}else{
			len[i+1]++;
			len[i+1]+=len[i];
		}
	}
	for(int i=n-1;i>=0;i--){
		if(str[i]=='0'){
			len2[i]=0;
		}else{
			len2[i]++;
			len2[i]+=len2[i+1];
		}
	}
	for(int i=0;i<n;i++){
		if(str[i]=='1' || i==0 || i==n-1 || str[i-1]=='0' || str[i+1]=='0'){
			for(int j=0;j<4;j++){
				dp[i+1][j]=dp[i][j];
			}
			if(str[i]=='0'){
				for(int j=0;j<4;j++){
					dp[i+1][3]=max(dp[i+1][3],dp[i][j]);
				}
			}
		}else{
			if(len2[i+1]==1){
				dp[i+1][2]=max(dp[i][0]+len[i]-1,dp[i][1]+1);
				int v=max(dp[i][0],dp[i][1])+len2[i+1];
				v=max(v,dp[i][3]+len[i]);
				v=max(v,dp[i][3]+len2[i+1]);
				dp[i+1][2]=max(dp[i+1][2],v);
				dp[i+1][3]=max(dp[i][0],dp[i][1]);
				dp[i+1][3]=max(dp[i+1][3],dp[i][2]);
				dp[i+1][3]=max(dp[i+1][3],dp[i][3]);
			}else{
				dp[i+1][0]=max(dp[i][0]+len[i]-1,dp[i][1]+1);
				dp[i+1][0]=max(dp[i+1][0],dp[i][3]+len[i]);

				dp[i+1][1]=max(dp[i][0],dp[i][1])+len2[i+1]-1;
				dp[i+1][1]=max(dp[i+1][1],dp[i][3]+len2[i+1]-1);
				
				dp[i+1][2]=max(dp[i][0],dp[i][1])+len2[i+1];
				dp[i+1][2]=max(dp[i+1][2],dp[i][3]+len2[i+1]);
				
				dp[i+1][3]=max(dp[i+1][3],dp[i][0]);
				dp[i+1][3]=max(dp[i+1][3],dp[i][1]);
				dp[i+1][3]=max(dp[i+1][3],dp[i][2]);
				dp[i+1][3]=max(dp[i+1][3],dp[i][3]);
			}
		}
	}
	int ans=max(dp[n][0],dp[n][1]);
	ans=max(ans,dp[n][2]);
	ans=max(ans,dp[n][3]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 12548
#include <iostream>
using namespace std;
typedef long long ll;
#define PrintLn(X) cout << X << endl

ll dp[500001][2];

int main(void)
{
	ll N, A, B, C, D;
	cin >> N >> A >> B >> C >> D;
	N--;

	if(A > B) swap(A, B);
	B -= A;

	for(int i = 0; i <= N; i++){
		ll mn = C * N - i * (C + D);
		ll mx = D * N - i * (C + D);
		if(mn <= B && B <= mx){
			PrintLn("YES");
			return 0;
		}
	}

	PrintLn("NO");
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) rep2(i,0,n)

using namespace std;

main(){
    int n;
    cin>>n;
    ll int a[2200]={};
    rep(i,n)
    cin>>a[i];
    ll int ans1=0,ans2=0;
    int count1=0,count2=0;
    rep(i,n){
        if(a[i*2]>0) {
            ans1+=a[i*2];
            count1++;
        }
        if(a[i*2+1]>0) {
            ans2+=a[i*2+1];
            count2++;
        }
    }
    if(max(ans1,ans2)==0||(max(ans1,ans2)==ans1&&count1==1)||(max(ans1,ans2)==ans2&&count2==1)){
        int memnum=a[0],memplace=0;
        rep(i,n){
            if(a[i]>memnum) {
                memnum=a[i];
                memplace=i;
            }
        }
        cout<<memnum<<endl<<n-1<<endl;
        rep(i,memplace)
        cout<<1<<endl;
        for(int i=n-memplace;i>1;i--){
            cout<<i<<endl;
        }
        return 0;
    }
    
    int b[1100]={};
    int m=0;
    if(ans1>=ans2){
        rep(i,n){
            if(a[i*2]>0){
                b[m]=i*2;
                m++;
            }
        }
    }
    if(ans1<ans2){
        rep(i,n){
            if(a[i*2+1]>0){
                b[m]=i*2+1;
                m++;
            }
        }
    }
    m--;
    cout<<max(ans1,ans2)<<endl;
    cout<<(n-1-b[m]+b[0]+(b[m]-b[0])/2)<<endl;
    for(int i=n;i>b[m]+1;i--){
        cout<<i<<endl;
    }
    for(int i=0;i<b[0];i++)
    cout<<1<<endl;
    int c[m];
    rep(i,m)
    c[i]=(b[i+1]-b[i])/2;
    rep(i,m){
        while(c[i]>1){
            cout<<3<<endl;
            c[i]--;
        }
        cout<<2<<endl;
    }
    return 0;
    
}

Measured memory_bytes: 256
N = int( input())
P = list( map( float, input().split()))
t = N//2+1
dp = [0]*(t+1)
dp[0] = 1
for p in P:
    for i in range(t-1,-1,-1):
        dp[i], dp[i+1] = dp[i]*(1-p), dp[i+1] + dp[i]*p
print(dp[t])


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

int main() {
    int n;
    while (cin >> n, n) {
        vector<pair<pair<int, int>, string>> seeds;
        for (int i = 0; i < n; i++) {
            // 作物を育てるには種を買わなければならない．
            string l;   // 作物 i の種の名前
            int p;      // その値段 Pi
            cin >> l >> p;
            int a, b, c, d, e;  // 種を植えてから実が成るまでの時間
            cin >> a >> b >> c >> d >> e;
            int total = a + b + c + d + e;
            int sub = d + e;    // 実が成ったあと葉に戻る
            int f;      // 一つの種から Fi 個の実が成る
            int s;      // それらの実は一つあたり Si の価格で売れる
            int m;      // 部の作物は多期作であり，計 Mi 回実をつける
            cin >> f >> s >> m;
            // ある種に対する収入は，
            // その種から成った全ての実を売った金額から，種の値段を引いた値である．
            int profit = f * s * m - p;
            // その種の収入効率は，
            // その収入を，種を植えてから全ての実が成り終わるまでの時間で割った値である．
            int time = total + sub * (m - 1);
            seeds.emplace_back(make_pair(profit, time), l);
        }
        // 時間あたりの収入効率にもとづいて並べる
        using pis = pair<pair<int, int>, string>;
        sort(seeds.begin(), seeds.end(), [](pis x, pis y){
            int a = x.first.first;
            int b = x.first.second;
            int c = y.first.first;
            int d = y.first.second;
            if (a * d > b * c) return true;
            if (a * d < b * c) return false;
            return x.second < y.second;
        });
        for (auto& p : seeds) {
            cout << p.second << endl;
        }
        cout << "#" << endl;
    }
    return 0;
}


Measured memory_bytes: 3080
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		String s = scan.next();
		String t = scan.next();
		int ans = 0;
		
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i) != t.charAt(i)) {
				ans += 1;
			}
		}
		
		System.out.println(ans);
	}
}
 


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

using namespace std;

#define ll long long int
#define ld long double
#define MAX 1000000
#define MOD 1000000001
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pi 3.14159265358979323846
#define Q ll _; cin >> _; while(_--)
#define endl "\n"
#define cy cout << "Yes\n";
#define cn cout << "No\n";
#define flush fflush(stdout);

int main(){

    ll i,n,l;
    cin >> n >> l;
    for(i=n*2;i<=n*4;i=i+2){
        if(l==i){
            cy;
            return 0;
        }
    }
    cn;


}

//    cout << fixed << setprecision(12);


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

vector <int> adj[10005];
queue <int> qu;
bool vis[10005];
vector <int> arr;
int val[10005] , j;

void bfs(int root){
    qu.push(root);
    vis[root] = true;
    val[root] = arr[j];
    j--;
    while(!qu.empty()){
        root = qu.front();
        qu.pop();
        for(int i = 0; i < adj[root].size(); i++){
            if(!vis[adj[root][i]]){
                vis[adj[root][i]] = true;
                qu.push(adj[root][i]);
                val[adj[root][i]] = arr[j];
                j--;
            }
        }
    }
}

int main(){
    int n , m , x, y;
    cin >> n;
    m = n-1;
    while(m--){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 0; i < n; i++){
        cin >> x;
        arr.push_back(x);
    }
    sort(arr.begin() , arr.end());
    j = arr.size()-1;
    bfs(1);
    int ans = 0;
    for(int i = 2; i <= n; i++){
        ans+=val[i];
    }
    cout << ans << '\n';
    for(int i = 1; i <= n; i++){
        cout << val[i] << " ";
    }
    
    
}

Measured memory_bytes: 1024
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int k;
    cin >> k;

    if(k == 1){
        cout << 1 << endl << 1 << endl;
        return 0;
    }

    int n = (k + 3) / 4 * 2;

    int ex = n * 2 - k;
    cout << n << endl;
    rep(i, n){
        rep(j, n){
            if(i % 2 == 0){
                cout << (i + j) % n + 1 << " ";
            }else{
                int ans = (i + j) % n + 1;
                if(ans > ex){
                    ans += n - ex;
                }
                cout << ans << " ";
            }
        }
        cout << endl;
    }

    return 0;
}


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

const int maxn = 409;
int in[maxn], out[maxn], pa[maxn], flag[maxn];
int n, H, a, b, c, d;

int getpa(int x) {
	return pa[x] == x ? x : pa[x] = getpa(pa[x]);
}

int main() {
	scanf("%d%d", &n, &H);
	for (int i=1; i<=2*H; i++) pa[i] = i;
	for (int i=1; i<=n; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if (c) a = c + H; 
		if (!d) b = b + H; else b = d;
		out[a]++; in[b]++;
		pa[getpa(a)] = getpa(b);
	}
	for (int i=1; i<=H; i++)
		if (out[i] < in[i]) { puts("NO"); return 0; }
	for (int i=H+1; i<=2*H; i++)
		if (in[i] < out[i]) { puts("NO"); return 0; }
	for (int i=1; i<=2*H; i++)
		if (in[i] != out[i]) flag[getpa(i)] = 1;
	for (int i=1; i<=2*H; i++)
		if (pa[i] == i && !flag[i] && in[i] && out[i]) { puts("NO"); return 0; }
	puts("YES");
	return 0;
}

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

int main(){
  string s1;
  
  cin >> s1;
  if( s1[2] == s1[3] && s1[4] == s1[5] ){
    cout << "Yes";
  }else{
    cout << "No";
  }}

Measured memory_bytes: 256
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
a = LI()

ans = 0
for i in range(N):
    if (i+1)%2 == 1 and a[i]%2 == 1:
        ans += 1

print(ans)

Measured memory_bytes: 65588
decode(h,l){
	if(h>='1'&&h<='6'&&l>='1'&&l<='5')
		return "abcdefghijklmnopqrstuvwxyz.?! "[(h-'1')*5+l-'1'];
	else
		return 0;
}
main(){
	char s0[201],s1[101];
	int i,e;
	for(;~scanf("%s",s0);){
		e=0;
		for(i=0;s0[i*2];i++){
			s1[i]=decode(s0[i*2],s0[i*2+1]);
			if(!s1[i]){
				e=1;
				break;
			}
		}
		s1[i]=0;
		puts(e?"NA":s1);
	}
}

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

int dp[5002][5002];

int main() {
    int n;
    string s;
    cin >> n >> s;
    for(int i = n - 1; i >= 0; --i){
        for(int j = n - 1; j >= 0; --j){
            if(s[i] == s[j]) dp[i][j] = dp[i+1][j+1] + 1;
        }
    }
    int ans = 0;
    rep(i, n)rep(j, n){
        if(i >= j) continue;
        else ans = max(ans, min(j-i, dp[i][j]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 97920
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) ((x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
const double PI = acos(-1);
const int mod = 1e9+7;
const long long INF = (1LL << 60);
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(ll a, ll b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmax(T &a, const T &b){ if(a < b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(a > b){ a=b; return 1; } return 0; }

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

  string s;
  cin >> s;
  s.erase(s.end()-1);
  while(1){
    if(sz(s) % 2 == 1) s.erase(s.end()-1);
    else{
      string t, u;
      t = s.substr(0, sz(s)/2);
      u = s.substr(sz(s)/2);
      if(t == u){
        cout << sz(s) << endl;
        return 0;
      }else{
        s.erase(s.end()-1);
      }
    }
  }
  return 0;
}

Measured memory_bytes: 256
/**
*    created: 28.06.2020 02:31:43
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcountll(bit)
using namespace std;
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}
const int mod = 1000000007;
const long double pi = acos(-1.0);
const int inf = 1LL << 60;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(n);
    int cnt = 0;
    rep(i,n) {
        int a;
        cin >> a;
        while (a % 2 == 0) {
            a /= 2;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3704
n = int(input())
a = []
for i in range(n):
  s = input()
  a.append(s)
b,c,d,e = 0,0,0,0
for i in range(n):
  if(a[i] == 'AC'):
    b += 1
  elif(a[i] == 'WA'):
    c += 1
  elif(a[i] == 'TLE'):
    d += 1
  else:
    e += 1
print('AC', 'x', b)
print('WA', 'x', c)
print('TLE', 'x', d)
print('RE', 'x', e)

  

Measured memory_bytes: 16320
#include<iostream>
using namespace std;
int main() {
	int a, b; cin >> a >> b;
	int ans = 0;
	for (int i = 0; i <= b; i++) {
		if (a * i == b) {
			ans++;
		}
	}
	if (ans != 0) { cout << a + b << endl; }
	else { cout << b - a << endl; }
	return 0;
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

A, B, H, M = map(int, input().split())

H = radians((60 * H + M) * 360 / (12 * 60))
M = radians(M * 360 / 60)

print(((A * cos(H) - B * cos(M)) ** 2 + (A * sin(H) - B * sin(M)) ** 2) ** 0.5)

Measured memory_bytes: 9852
a, b, k = map(int, raw_input().split())

stop = 0

for i in range(k):
    if i % 2 == 0:
        a /= 2
        b += a
        if b == a * 2:
            stop = i + 1
            break
    if i % 2 == 1:
        b /= 2
        a += b
        if a == b * 2:
            stop = i + 1

if stop == 0 or (k - stop) % 2 == 0:
    print a, b
else:
    print b, a


Measured memory_bytes: 2568