akhauriyash/Code-Regression huggingface dataset:
// 2020-07-24 07:21:30
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  int n, m;
  cin >> n >> m;
  vector<int> a(m), b(m);
  rep(mi, m) {
    int b_;
    cin >> a[mi] >> b_;
    rep(bi, b_) {
      int c;
      cin >> c;
      b[mi] |= (1 << (c-1));
    }
  }
  int INF = 1e9+5;
  vector<int> dp(1<<n, INF);
  dp[0] = 0;
  rep(mi, m) {
    rep(ni, 1<<n) {
      chmin(dp[ni | b[mi]], dp[ni] + a[mi]);
    }
  }
  int ans = dp[(1<<n)-1];
  if(ans == INF) cout << -1 << '\n';
  else cout << ans << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

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

using namespace std;

bool check(string s) {
  auto rs = s;
  reverse(rs.begin(), rs.end());
  return rs == s;
}

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

  string s;
  cin >> s;
  int n = s.size();
  cout << (check(s) and check(s.substr(0, n / 2)) and check(s.substr(n / 2 + 1)) ? "Yes" : "No");

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
typedef unsigned long long ULL;
using namespace std;

int main(){
  int Q,F,i,cmd,hl=0,tl=0;
  char S[100001],C,head[200001],tail[200001];
  bool direction=0;
  cin>>S>>Q;
  for(i=0;i<Q;i++){
    cin>>cmd;
    if(cmd==1){
      direction=!direction;
    }else{
      cin>>F>>C;
      if(!direction){
        if(F==1){
          head[hl]=C;//headは逆
          head[hl+1]='\0';
          hl++;
        }else{
          tail[tl]=C;//tailは順
          tail[tl+1]='\0';
          tl++;
        }
      }else{
        if(F==1){
          tail[tl]=C;//tailは順
          tail[tl+1]='\0';
          tl++;
        }else{
          head[hl]=C;//headは逆
          head[hl+1]='\0';
          hl++;
        }
      }
    }
  }
  if(direction){
    for(i=strlen(tail)-1;i>=0;i--) cout<<tail[i];
    for(i=strlen(S)-1;i>=0;i--) cout<<S[i];
    cout<<head<<endl;
  }else{
    for(i=strlen(head)-1;i>=0;i--) cout<<head[i];
    cout<<S<<tail<<endl;
  }
}

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

vector<ll> a,p;

ll ans(ll n, ll x)
{
  ll y;
  if ( n == 0 ) {
    if ( x <= 0) return 0;
    else return 1;
  } else if ( x <= a[n-1]+1 ) {
    return ans(n-1,x-1);
  } else {
    return p[n-1] + 1 + ans(n-1,x-a[n-1]-2);
  }
  return y;
}

void print_vec(vector<ll> a)
{
  for(auto p:a) cout << p << " ";
  cout << endl;
}

int main()
{
  ll n,x;
  cin >> n >> x;
  a.push_back(1);
  p.push_back(1);
  for (ll i = 0; i <= n-1; i++)
  {
    a.push_back(2*a[i]+3);
    p.push_back(2*p[i]+1);
  }
  /*
  print_vec(a);
  print_vec(p);
  */
  cout << ans(n,x) << endl;

  return 0;
}

Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
m = str(n)
for i in m:
    if i == '7':
        print('Yes')
        exit()
print('No')

Measured memory_bytes: 68264
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int n, a, b;
ll pow(ll x, ll n) {
  if(n == 0) return 1;
  if(n == 1) return x;
  return pow(x*x%MOD, n/2)*pow(x, n%2)%MOD;
}
ll modinv(ll x, ll m) {
  ll y = m, u = 1, v = 0;
  while(y) {
    ll t = x/y;
    x -= t*y; swap(x, y);
    u -= t*v; swap(u, v);
  }
  u %= m;
  if(u < 0) u += m;
  return u;
}
ll xCr(ll x, ll r) {
  ll bunbo = 1, bunshi = 1;
  for(int i = 1; i <= r; ++i) {
    bunshi = bunshi*(x-i+1)%MOD;
    bunbo = bunbo*i%MOD;
  }
  return bunshi%MOD*modinv(bunbo, MOD)%MOD;
}
int main() {
  scanf("%d %d %d", &n, &a, &b);
  ll ans = pow(2, n)-1-(xCr(n, a)+xCr(n, b))%MOD;
  if(ans < 0) ans += MOD;
  printf("%ld\n", ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define el '\n'

int ar[105];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (i) ar[i] = ar[i-1] + x;
    else ar[i] = x;
  }
  int ans = INT_MAX;
  for (int i = 0; i < n; i++) {
    ans = min(ans, abs(ar[i-1]-(ar[n-1]-ar[i-1])));
  }
  cout << ans << el;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define X first
#define Y second
const ll maxn = 2e5 + 20;
set<int> st;
int main()
{
    int a , b , c;
    cin >> a >> b >> c;
    int x = a % b;
    while(st.find(x) == st.end())
    {
        st.insert(x);
        x += a;
        x %= b;
    }
    cout << (st.find(c) == st.end()? "NO" : "YES");
}


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

using namespace std;

int dp[1010][20202];

int main() {
  int h, n;
  cin >> h >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }

  for (int i = 0; i < 1010; i++) {
    for (int j = 0; j < 20202; j++) {
      dp[i][j] = 1 << 29;
    }
  }
  for (int i = 0; i <= n; i++) dp[i][0] = 0;

  int amax = *max_element(a.begin(), a.end());
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= h + amax; j++) {
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      if (a[i] <= j) {
        dp[i + 1][j] = min(dp[i + 1][j], dp[i + 1][j - a[i]] + b[i]);
      }
    }
  }

  int ans = 1 << 29;
  for (int i = h; i <= h + amax; i++) {
    ans = min(ans, dp[n][i]);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 80000
a, b, deg = gets.split.map(&:to_f)
rad = deg * Math::PI / 180

h = Math.sin(rad) * b
s = a * h / 2
t = h / Math.tan(rad)
c = Math.sqrt((a - t) ** 2 + h ** 2)

puts sprintf("%.6f", s)
puts sprintf("%.6f", a + b + c)
puts sprintf("%.6f", h)

Measured memory_bytes: 9084
#include <iostream>
using namespace std;
int main() {
  int n;
  while (cin >> n) {
    int sum = 0;
    int cnt = 0;
    for (int a = 0; a < 10; ++a) {
    sum += a;
    for (int b = 0; b < 10; ++b) {
    sum += b;
    for (int c = 0; c < 10; ++c) {
    sum += c;
    for (int d = 0; d < 10; ++d) {
    sum += d;
    if (sum == n) cnt++;
    sum -= d;
    }
    sum -= c;
    }
    sum -= b;
    }
    sum -= a;
    }
    cout << cnt << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 20000
int t[MAX],n,m,ans;
int main(){
  while(1){
    cin>>n>>m;
    if(n==0&&m==0)break;
    for(int i=0;i<n;i++)cin>>t[i];
    for(int i=0;i<m;i++)cin>>t[i+n];
    sort(t,t+n+m);
    ans=t[0];
    for(int i=1;i<n+m;i++)ans=max(ans,t[i]-t[i-1]);
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1252
def solve_knapsack(weight, items):
    dp = [[0]*(weight+1) for _ in range(len(items))]
    for i, item in enumerate(items[1:]):
        for w in range(1, weight+1):
            if item[1] <= w:
                if item[0] + dp[i][w-item[1]] > dp[i][w]:
                    dp[i+1][w] = item[0] + dp[i][w-item[1]]
                else:
                    dp[i+1][w] = dp[i][w]
            else:
                dp[i+1][w] = dp[i][w]
    return dp[-1][-1]



if __name__ == '__main__':
    # ??????????????\???
    # f = open('input.txt')
    num_of_sack, total_capacity = [int(x) for x in input().strip().split(' ')]
    items = [[]]
    for _ in range(num_of_sack):
        items.append([int(x) for x in input().strip().split(' ')])
    # f.close()

    # ????????¨???????????¨???
    result = solve_knapsack(total_capacity, items)
    print(result)

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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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;
}


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

vector<ll> ans;

void rec(vector<ll> a)
{
  //  rep(i, a.size()) cerr << a[i] << " "; cerr << "\n";
  if(a.size() == 0) return ;
  bool ok = false;
  for(ll i = a.size()-1; i >= 0; i--) {
    if(a[i] == i+1) {
      ok = true;
      a.erase(a.begin()+i);
      rec(a);
      cout << i + 1 << endl;
      break;
    }
  }
  if(!ok) {
    cout << -1 << endl;
    exit(0);
  }
}



void solve()
{
  ll N; cin >> N;

  vector<ll> a(N); rep(i, N) cin >> a[i];

  rec(a);

}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int main(){
    int x;
    cin >> x;
    int y = (x - 400) / 200;
    cout << 8 - y << endl;
    
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, a, b, c, d);
    CoutYn(500*a >= b);
}

Measured memory_bytes: 256
//47行目から編集
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

template<class T> bool chmin(T& a,T b);
template<class T> bool chmax(T& a,T b);
template<class T> void debugger(vector<T>& a);
template<class T> void debugger(vector<vector<T>>& a);
///////////////////////////////////////////////////////////

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    string s;cin >> s;
    bool turned = false;
    string bef = "",lat = "";
    int t;cin >> t;
    REP(_,t){
        int c;cin >> c;
        if(c == 1)turned ^= 1;
        else{
            int f;cin >> f;
            char x;cin >> x;
            if((f==1 and !turned) or (f == 2 and turned)){
                bef += x;
            }else{
                lat += x;
            }
        }
    }
    if(turned){
        reverse(all(lat));
        reverse(all(s));
        cout << lat << s << bef << '\n';
    }else{
        reverse(all(bef));
        cout << bef << s << lat << '\n';
    }
    return 0;
}

///////////////////////////////////////////////////////////
template<class T> bool chmin(T& a,T b){
    if(a > b){a = b;return true;}else return false;
}
template<class T> bool chmax(T& a,T b){
    if(a < b){a = b;return true;}else return false;
}
template<class T> void debugger(vector<T>& a){
    cerr << "{";
    for(int i = 0;i < a.size();i++){
        if(i == 0)cerr << a[i];
        else cerr << "," << a[i];
    }
    cerr << "}" << '\n';
    return;
}
template<class T> void debugger(vector<vector<T>>& a){
    int n = a.size();
    int m = a[0].size();
    cerr << "__|";
    for(int i = 0;i < m;i++){
        cerr << setw(5) << i;
    }
    cerr << '\n';
    for(int i = 0;i < n;i++){
        cerr << setw(3) << i;
        for(int j = 0;j < m;j++){
            if(a[i][j] >= 100000)cout << setw(5) << "INF";
            else cerr << setw(5) << a[i][j];
        }
        cerr << '\n';
    }
}


Measured memory_bytes: 1040
#include<stdio.h>

#define true 1
#define false 0

int binarySearch(int A[], int key, int l, int n){
  int mid;

  if(l < n){
    mid = (l+n)/2;
    if(A[mid] == key) return true;
    if(A[mid] > key) return binarySearch(A, key, l, mid);
    else if(A[mid] < key) return binarySearch(A, key, mid+1, n);
  }
  return false;
}

int main(){
  int S[1000000];
  int i, n, q, key;
  int count = 0;

  scanf("%d", &n);
  for(i = 0; i < n; i++){
    scanf("%d", &S[i]);
  }

  scanf("%d", &q);
  for(i = 0; i < q; i++){
    scanf("%d", &key);
    if(binarySearch(S, key, 0, n) == true) count++;
  }

  printf("%d\n", count);

  return 0;
}



Measured memory_bytes: 2092
X = int(input())


if X>=30:
  print("Yes")
else :
  print("No")
# A = list(map(int, input().split()))
# # S =[1]*N
# stock = 0 #株の数
# money = 1000 #所持金
# for i in range(N):
#   if i>0:
#     if A[i-1]<A[i]: #売る
#       money += stock*A[i]
#       stock = 0
#   if i!=N-1:
#     if A[i]<A[i+1]: #買う
#       stock += int(money/A[i])
#       money -= stock*A[i]
# print(money)


Measured memory_bytes: 9140
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<int> A(N, 0);
    rep(i, N) cin >> A[i];
    vector<int> B;
    B.pb(0);
    rep(i, A.size() - 1) {
        if(A[i] != A[i + 1])
            B.pb(A[i]);
    }
    B.pb(A[N - 1]);
    B.pb(0);
    N = B.size() - 2;
    map<int, vector<int>> idx;
    rep(i, N) { idx[B[i + 1]].pb(i + 1); }
    int cnt = 0;
    rep(i, N) {
        if(B[i + 1] > 0 && B[i + 2] == 0)
            cnt++;
    }
    int res = cnt;
    for(auto x : idx) {
        if(x.first == 0)
            continue;
        for(auto y : x.second) {
            if(B[y] < B[y + 1] && B[y] < B[y - 1])
                cnt++;
            else if(B[y] > B[y + 1] && B[y] > B[y - 1])
                cnt--;
        }
        res = max(res, cnt);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 14600
main = do
  (a:b:_) <- return . (map read) . words =<< getLine
  putStrLn $ judge (f a) (f b)
  where
    f 1 = 14
    f n = n 
    judge a b
      | a == b = "Draw"
      | a > b = "Alice"
      | a < b = "Bob"
      


Measured memory_bytes: 508
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
/* #include <regex> */

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n,k; string s;
    while (cin >> n >> k >> s) {
        k--;
        s[k] = tolower(s[k]);
        cout << s << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N,C = map(int,input().split())
r = [[0]*(10**5) for c in range(C)]
for i in range(N):
    s,t,c = map(int,input().split())
    r[c-1][s-1:t] = [1]*(t-s+1)
print(max(map(sum,zip(*r))))

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

using namespace std;

int N;
int a[50];

int argmax(bool rev) {
    int mx = -1;
    int mxi = 0;
    for (int i = 0; i < N; ++i) {
        int ai = rev ? -a[i] : a[i];
        if (ai > mx) {
            mx = ai;
            mxi = i;
        }
    }
    return mxi;
}

int allsign() {
    int ans = a[0] == 0 ? 0 : a[0] / abs(a[0]);
    for (int i = 1; i < N; ++i) {
        int si = a[i] == 0 ? 0 : a[i] / abs(a[i]);
        if (ans != si) return 2;
    }
    return ans;
}

int main(){
    cin >> N;
    for (int i = 0;i < N; ++i) {
        cin >> a[i];
    }
    int as = allsign();
    if (as == 0) {
        cout << 0 << endl;
        return 0;
    }

    if (as == 2) {
        cout << 2 * N - 2 << endl;
        int maxi = argmax(false);
        int mini = argmax(true);
        int k = 0;
        if (a[maxi] > - a[mini]) {
            as = 1;
            k = maxi;
        } else {
            as = -1;
            k = mini;
        }

        for (int i = 0; i < N; ++i) {
            if (i == k) continue;
            cout << k + 1 << " " << i + 1 << endl;
        }
    } else {
        cout << N - 1 << endl;
    }

    if (as == 1) {
        for (int i = 0; i < N - 1; ++i) {
            cout << i + 1 << " " << i + 2 << endl;
        }
    } else {
        for (int i = N; i > 1; --i) {
            cout << i << " " << i - 1 << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
typedef pair<int,int> P;
struct Animal{
  int size;
  bool bingo[500][500];
  map<int,P> point;
  int count;
  Animal(int s){
    count = 0;
    memset(bingo,0,sizeof(bingo));
    size = s;
  }
  void print(){
    cout<<count<<endl;
    REP(y,size){
      REP(x,size){
        printf("%d ",(int)bingo[y][x]);
      }
      putchar('\n');
    }
    putchar('\n');
  }
  void insert(int n,int x, int y){
    point[n] = P(x,y);
  }
  void drow(int n){
    if(point.find(n)!=point.end()){
      P p = point[n];
      bingo[p.second][p.first] = true;
      bool okr = true;
      bool okc = true;
      bool okd1 = (p.first == p.second);
      bool okd2 = (p.first + p.second == size-1);
      REP(i,size){
        okr &= bingo[p.second][i];
        okc &= bingo[i][p.first];
        okd1 &= bingo[i][i];
        okd2 &= bingo[i][size-1-i];
      }
      count += (okr+okc+okd1+okd2);
    }
  }
  bool check(int n){
    if(size == 1) return (int)(count>0) >= n;
    return count >= n;
  }
};

int main(){
  int n,u,v,m,d;
  cin>>n>>u>>v>>m;
  Animal usagi(n);
  Animal neko(n);
  REP(y,n)REP(x,n){
    scanf("%d",&d);
    usagi.insert(d,x,y);
  }
  REP(y,n)REP(x,n){
    scanf("%d",&d);
    neko.insert(d,x,y);
  }
  bool gameover = false;
  REP(i,m){
    scanf("%d",&d);
    if(!gameover){
      usagi.drow(d);
      neko.drow(d);
      if(usagi.check(u)&&neko.check(v)){
        cout<<"DRAW"<<endl;
        gameover = true;
      }else if(usagi.check(u)){
        cout<<"USAGI"<<endl;
        gameover = true;
      }else if(neko.check(v)){
        cout<<"NEKO"<<endl;
        gameover = true;
      }
    }
  }
  if(!gameover){
    cout<<"DRAW"<<endl;
  }
  return 0;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class UnionFind{
private:
	::std::vector<int_fast32_t> par;
	size_t n;

public:
	UnionFind(){}
	UnionFind(size_t n):n(n){
		par.resize(n, -1);
	}

	uint_fast32_t find(uint_fast32_t x){
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}

	size_t size(uint_fast32_t x){
		return -par[find(x)];
	}

	bool unite(uint_fast32_t x, uint_fast32_t y){
		x = find(x);
		y = find(y);
		if(x == y) return false;
		if(size(x) < size(y)) std::swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

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


int64 N, D;
vector<int64> A, ed;
vector<PII> e;

UnionFind uf;

void dfs(int64 l, int64 r){
	if(r-l == 1) return;
	int64 lmin = INF_LL, lidx = -1;
	int64 rmin = INF_LL, ridx = -1;
	int32 m = (l+r)/2;
	FOR(i, l, m){ if (lmin > A[i]-i*D) { lmin = A[i]-i*D; lidx = i; } }
	FOR(i, m, r){ if (rmin > A[i]+i*D) { rmin = A[i]+i*D; ridx = i; } }
	FOR(i, l, m){ e.emplace_back(i, ridx); ed.emplace_back(rmin+(A[i]-i*D));}
	FOR(i, m, r){ e.emplace_back(lidx, i); ed.emplace_back(lmin+(A[i]+i*D));}
	dfs(l, m); dfs(m, r);
}

int main(void){
	cin >> N >> D;
	A.resize(N);
	uf = UnionFind(N);
	REP(i, N) cin >> A[i];
	dfs(0, N);
	vector<int64> ord(ed.size()); iota(all(ord), 0);
	sort(all(ord), [&](int64 l, int64 r){
			return ed[l] < ed[r];
		});
	int64 res = 0;
	REP(i, e.size()){
		int64 idx = ord[i];
		if(uf.unite(e[idx].fs, e[idx].sc)) res += ed[idx];
	}
	cout << res << endl;
}




Measured memory_bytes: 116956
from collections import defaultdict 
N = int(input())
d = defaultdict(int)
for i in range(N):
    a = int(input())
    if d[a] == 0:
        d[a] += 1
    else:
        d[a] -= 1
cnt = 0
for k in d.keys():
    if d[k] > 0:cnt+=1
    
print(cnt)

Measured memory_bytes: 15448
import numpy as np
nmc=list(map(int,input().split()))
n=nmc[0]
m=nmc[1]
b=list(map(int,input().split()))
a=[0 for i in range(n)]
ans=0
for i in range(n):
    a[i] = list(map(int,input().split()))
    if np.dot(a[i],b)+nmc[2]>0:
        ans += 1
print(ans)


Measured memory_bytes: 21416
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid<int> u1(5, 10); u1(rnd);

int main(){
    fast;
    ll a; cin>>a;
    cout<<(ll)pow(a, 3);
}

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

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b;
  cin >> a >> b;
  if (b == 1) {
    cout << 0 << endl;
    return 0;
  }
  int ans = 0;
  while (b >= 0) {
    if (b <= a) {
      ans++;
      break;
    } else {
      ans++;
      b -= a - 1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#k = int(input())
#s = input()
#a, b = map(int, input().split())
#s, t = map(str, input().split())
#l = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
#a = [input() for _ in range(n)]

t,x=map(int,input().split())

print(t/x)









Measured memory_bytes: 9080
/*
*	User: Isanchez_Aguilar
*	Problem: AtCoder ABC134B - Golden Apple
*/
#include <bits/stdc++.h>

using namespace std;
using Long = long long;

vector<int> memo(100001, -1);
vector<int> graph[100001];

int dp(int u)
{
	if (memo[u] == -1)
	{
		memo[u] = 0;

		for (int v : graph[u])
			memo[u] = max(memo[u], 1 + dp(v));
	}
	
	

	return memo[u];
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		graph[u].emplace_back(v);
	}

	int ans = 0;

	for (int i = 0; i < n; ++i)
		ans = max(ans, dp(i));

	cout << ans;

	return 0;
}

Measured memory_bytes: 8192
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long  ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 

 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
float slope(float x1 , float y1  , float x2 , float y2){

	if(x1==x2) return 0 ;
	return (y2-y1)/(x2-x1) ;
}
void solve()
{
	ll n ; 
	cin>>n ; 
	ll ans = 0 ;
	for(ll  i = 1 ; i<=n;i++){
		if(!(i%3==0) && !(i%5==0)){
			ans +=  i;
		}
	}
	cout<<ans<<endl;

}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3680
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    string s;
    cin>>s;
    bool alph[26] = {};
    for(auto c: s) {
        alph[c-'a']=true;
    }
    char c='!';
    for(int i=0; i<26; ++i) {
        if(!alph[i]) {
           c = static_cast<char>('a'+i);
           cout<<c<<'\n';
           return 0;
        }
    }
    cout<<"None"<<'\n';
    return 0;
}

Measured memory_bytes: 512
n,k=map(int,input().split())
x=list(map(int,input().split()))

ans=10**9
for i in range(n-k+1):
  d=x[i+k-1]-x[i]
  d+=min(abs(x[i]),abs(x[i+k-1]))
  ans=min(ans,d)
print(ans)

Measured memory_bytes: 14224
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll n,a,b;
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if (!((a^b)&1)) printf("%lld\n",b-a>>1);
	else printf("%lld\n",min(a+b-2+1>>1,n-a+n-b+1>>1));
	return 0;
}

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


int main(){
	string s, t;
	cin >> s >> t;
	LL N;N = s.size();
	LL ans = 0;
	rep(i,N){
		if(s[i]!=t[i]) ++ans;
	}
	cout << ans << endl;
}












Measured memory_bytes: 3836
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iomanip>
#include<cstring>
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,b)  for(int i=0;i<(int)(b);i++)
#define Rep(i,n) for(int i=1;i<(int)(n);i++)
#define repp(i,a,b)  for(int i=a;i<=(int)(b);i++)
#define Repp(i,a,b)  for(int i=a;i>=(int)(b);i--)
typedef long long ll;
typedef long double ld;

using namespace std;

int main(){
    cs
    bool b=1;
    int k,t=0;cin>>k;
    vector<int> v(k);
    rep(i,k) cin>>v[i];
    Rep(i,k){
        if(v[i]<v[i-1]-1) {b=0;break;}
        else if(v[i]<v[i-1]) t++;
        else if(v[i]>v[i-1]) t=0;
        if(t>1) {b=0;break;}
    }
    if(b) cout<<"Yes";else cout<<"No";
}

Measured memory_bytes: 640
fun main() {
  val (n, d, a) = readLine()!!.split(' ').map { it.toInt() }

  val monsters = Array(n){ _ ->
    val (x, h) = readLine()!!.split(' ').map { it.toLong() }
    Pair(x, (h+a-1)/a)
  }
  monsters.sortBy { it.first }

  val change = LongArray(n+1){0}

  var ans = 0L
  var runningSum = 0L

  for (i in 0 until n){
    runningSum += change[i]
    val currHealth = monsters[i].second - runningSum

    if(currHealth <= 0) continue

    var l = i; var r = n-1
    var pos = -1
    while(l <= r){
      val mid = (r+l)/2
      if(monsters[mid].first <= monsters[i].first + 2L * d){
        pos = mid
        l = mid+1
      }else r = mid - 1
    }

    ans += currHealth
    runningSum += currHealth
    change[pos+1] -= currHealth
  }
  println(ans)
}

Measured memory_bytes: 78632
/*
*                                 Name : chaitanya
*
*                         Institute : ANITS,Visakhapatnam
*   "Don't regret anything you do, because in the end it makes you who you are."
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#include<sstream>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
using namespace std;

bool prime(int n)
{
  for (int i = 2; i < min(500000,n); ++i)
  {
    if(n%2 == 0)
    {
      return 0;
  }
}
return 1;
}
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
}
return res;
}
void debug_out(
    vector<string> __attribute__ ((unused)) args,
    __attribute__ ((unused)) int idx,
    __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

// 2+3+5+7+11+13
//   consecutivePrimes = (41) is also a prime
const int N = 100 * 10000 + 4;
vector <bool> isPrime(N,true);
vector <int> odd;
void  oddnum()
{
    for (int i = 1; i < N; i+=2 )
    {
        odd.pb(i);
    }
}
bool pall (int n)
{
    string s = to_string(n),r = "";
    r = string(s.rbegin(),s.rend());
    if (s == r)
        return true;
    else
        return false;

}
int main()
{

	// int x = -1, y = 10000;
	// double z = 0.2;
	// string s2 = "beginner1010";
	// long long b = 1LL << 60;B
	// // debug(x, y, z, s, b);
	// double aux = 1010.0;
	// string code = "code";

	// debug(code + "forces",-aux / 10 * 2.3);
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<int> v(N);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v[a]++;
    }
    vector<bool> div(N, true);
    for (int i = 1; i < N; i++) {
        if (v[i] == 0) continue;
        for (int j = i + i; j < N; j += i) {
            div[j] = false;
        }
    }
    int c = 0;
    for (int i = 0; i < N; i++) {
        if (v[i] == 1 && div[i]) {
            c++;
        }
    }
    cout << c;
}

Measured memory_bytes: 7472
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int n = sc.nextInt();
    long[] a = sc.nextLongArray(n);
    Map<Long, Long> count = new HashMap<>();
    for (int i = 0; i < n; i++) {
      count.merge(a[i], 1L, Long::sum);
    }
    Map<Long, Long> combinations = new HashMap<>();
    long sum = 0;
    for (long key : count.keySet()) {
      long c = count.get(key);
      sum += c * (c - 1L) / 2L;
      combinations.put(key, c * (c - 1L) / 2L);
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
      if (sb.length() > 0) sb.append("\n");
      long rest = count.get(a[i]) - 1L;
      long s = sum - combinations.get(a[i]);
      if (rest > 1L) s += rest * (rest - 1L) / 2L;
      sb.append(s);
    }
    System.out.println(sb.toString());
  }
}

Measured memory_bytes: 86676
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int y, m, d;
	char s1, s2;
	cin >> y >> s1 >> m >> s2 >> d;

	if(m<=4) cout << "Heisei" << endl;
	else cout << "TBD" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
queue <ll> a;
int k,num,b;
int main(){
	cin>>k;
	for(int i=1;i<=9;i++)
	
	{a.push(i),num++; if(num==k){
	 	cout<<i;return 0;
	 }
	} 
	while(!a.empty()){
	 ll b=a.front();
	 if(b%10!=0) a.push(b*10+b%10-1),num++; 
	 if(num==k){
	 	cout<<b*10+b%10-1;return 0;
	 }
	 a.push(b*10+b%10),num++;
	 if(num==k){
	 	cout<<b*10+b%10;return 0;
	 }
	 if(b%10!=9) a.push(b*10+b%10+1),num++;
	 if(num==k){
	 	cout<<b*10+b%10+1;return 0;
	 }
	 a.pop();
	
	}

	
   


	return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
#define For(i, j, k) for(register int i = j; i <= k; ++i)
#define Forr(i, j, k) for(register int i = j; i >= k; --i)
using namespace std;

namespace pb_ds {

    namespace io {
        const int MaxBuff = 1 << 16;
        const int Output = 1 << 22;
        char B[MaxBuff], *S = B, *T = B;
        #define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
        char Out[Output], *iter = Out;
        inline void flush() {
            fwrite(Out, 1, iter - Out, stdout);
            iter = Out;
        }
    }

    template<class Type> inline Type read() {
        using namespace io;
        register char ch; register Type ans = 0; register bool neg = 0;
        while(ch = getc(), (ch < '0' || ch > '9') && ch != '-')     ;
        ch == '-' ? neg = 1 : ans = ch - '0';
        while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';
        return neg ? -ans : ans;
    }

    template<class Type> inline void write(register Type x, register char ch = '\n') {
        using namespace io;
        if(!x) *iter++ = '0';
        else {
            if(x < 0) *iter++ = '-', x = -x;
            static int s[100]; register int t = 0;
            while(x) s[++t] = x % 10, x /= 10;
            while(t) *iter++ = '0' + s[t--];
        }
        *iter++ = ch;
    }
}

using namespace pb_ds;

long long f[1048575], sum[1048575], a[1048575];
int n, m, cnt;

int main() {
	a[++ cnt] = n = read<int>(), m = read<int>();
	For(i, 1, m) {
		long long x = read<long long>();
		for (;;) { if (*(a + cnt) < x) break; -- cnt; }
		*(a + (++ cnt)) = x;
	}

	*(sum + cnt) = 1;
	Forr(i, cnt, 2) {
		*(sum + i - 1) += (*(sum + i) * (*(a + i) / *(a + i - 1)));
		long long res = *(a + i) % *(a + i - 1);

		for (;;) {
			if (res == 0) break;
			int x = upper_bound(a + 1, a + 1 + cnt, res) - a - 1;
			if (x == 0) { *(f + res) += *(sum + i); break; }
			*(sum + x) += (res / *(a + x)) * (*(sum + i)), res %= *(a + x);
		}
	}
	*(f + *(a + 1)) = *(sum + 1);
	Forr(i, n - 1, 1) *(f + i) += *(f + i + 1);		
	For(i, 1, n) write(*(f + i), '\n');
	io::flush();
	return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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;}

int main(){
    int n;cin>>n;
    vl a(n),c;
    rep(i,n)cin>>a[i];
    ll r=1e18,l=0;
    while(r-l>1){
        ll m=(r+l)/2,b=m;
        for(int i=0;i<n;++i){
            b=b-b%a[i];
            if(b==0)break;
        }
        if(b<2){
            l=m;
        }
        else{
            r=m;
        }
    }
    ll R=1e18,L=0;
    while(R-L>1){
        ll m=(R+L)/2,b=m;
        for(int i=0;i<n;++i){
            b=b-b%a[i];
            if(b==0)break;
        }
        if(b<=2){
            L=m;
        }
        else{
            R=m;
        }
    }
    ll d=r,e=L;
    rep(i,n){
        d=d-d%a[i];
        e=e-e%a[i];
    }
    if(d==2&&e==2){
        cout<<r<<" "<<L<<endl;
    }
    else cout<<-1<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
//
// using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> p;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  for (int i = 1; i < 4; i++) {
    if(s[i] == s[i-1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //昇順
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順

int main(){
  ll n, x, tmp;
  cin >> n >> x;
  vector<ll> nums(n);
  rep_i(i, n){
    cin >> tmp;
    nums[i] = labs(tmp - x);
  }

  if (nums.size() == 1){
    cout << nums[0] << endl;
    return 0;
  }
  

  ll a;
  ll b;
  ll r = 1000;
  for (int i = 0; i < n - 1; i++){
    if(i == 0){a = nums[i];}
    b = nums[i+1];
    while (r != 0){
      // cout << b << endl;
      r = a%b;
      a = b;
      b = r;
    }
    // a = b;
    r = 1000;
  }
  cout << a << endl;

  // ll a = 273;
  // ll b = 390;
  // ll r = 1000;
  // while (r != 0){
  //   r = a%b;
  //   a = b;
  //   b = r;
  // }
  // cout << a << endl;
}

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

int main() {
  int a, b, c, d, L=0, R=0;
  cin >> a >> b >> c >> d;  

  L=a+b;
  R=c+d;
  
  if(L==R){
    cout << "Balanced" << endl;
  }else if(L>R){
    cout << "Left" << endl;
  }else{
    cout << "Right" << endl;
  }
}


Measured memory_bytes: 256
n = gets.chomp.to_i
ans = 0
testimony = Array.new(n).map{Array.new}
n.times do |i|
    a =  gets.chomp.to_i
    a.times do
        testimony[i] << gets.chomp.split(" ").map(&:to_i)
    end
end

[0, 1].repeated_permutation(n) do |bits|
    idx = 0
    flag = false
    bits.each do |bit|
        if bit == 1 then
            testimony[idx].each do |x, y|
                if bits[x-1] != y
                    flag = true
                    break
                end
            end
        end
        break if flag
        idx += 1
    end
    ans = bits.count(1) if !flag
end

puts ans

Measured memory_bytes: 2300
import sys
input = sys.stdin.readline
from itertools import accumulate

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

for tests in range(K):
    B=[0]*(N+1)
    for i in range(N):
        B[max(0,i-A[i])]+=1
        B[min(N,i+A[i]+1)]-=1

    A=list(accumulate(B))
    flag=1
    for i in range(N):
        if A[i]<N:
            flag=0
        A[i]=min(A[i],N)

    if flag:
        break
    #print(A)

print(*A[:N])

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




int N;
int A[3010];
vector<int> E[3010];
//-----------------------------------------------------------------
#define INF INT_MAX/2
bool dfs(int cu, int pa = 0) {
	for (int to : E[cu]) if (to != pa) {
		if (A[to] < A[cu] && !dfs(to, cu)) return true;
	}
	return false;
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 1, N + 1) cin >> A[i];
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		E[a].push_back(b);
		E[b].push_back(a);
	}

	vector<int> ans;
	rep(i, 1, N + 1) if (dfs(i)) ans.push_back(i);
	for (int i : ans) printf("%d ", i);
	cout << endl;
}

Measured memory_bytes: 384