akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <iterator>
#include <set>
#include <queue>
#include <bitset>
#include <cassert>

using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const long long MOD = 1000000007;

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int main() {

    int N;
    cin >> N;

    vector<ll> dp(N + 1, INF);
    dp[0] = 0;

    for (int i = 0; i < N; ++i) {
        chmin(dp[i + 1], dp[i] + 1);
        ll s = 6;
        while (s <= N) {
            if (i + s <= N) {
                chmin(dp[i + s], dp[i] + 1);
            }
            s *= 6;
        }
        ll n = 9;
        while (n <= N) {
            if (i + n <= N) {
                chmin(dp[i + n], dp[i] + 1);
            }
            n *= 9;
        }
    }

    cout << dp[N] << endl;

    return 0;
}

Measured memory_bytes: 3888
#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
int main(){
	int N,Q,A[100001];
	ll sum=0;
	ll cnt[100001]={};
	scan(N);
	rep(i,N){
		scan(A[i]);
		cnt[A[i]]++;
		sum+=A[i];
	}
	scan(Q);
	rep(i,Q){
		ll B,C;
		scan(B>>C);
		sum+=(C-B)*cnt[B];
		prin(sum);
		cnt[C]+=cnt[B];
		cnt[B]=0;
	}

	return 0;
}


Measured memory_bytes: 4696
import sys
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
s = input()
pass_list = list(map(lambda x: str(x).zfill(3), range(1000)))
res = 0

for p in pass_list:
    
    ptr = 0
    one = False
    two = False
    three = False
    
    for i in range(len(s)):
        if(s[i] == p[0]):
            ptr = i
            one = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[1]):
            ptr = i
            two = True
            break
    
    for i in range(ptr+1, len(s)):
        if(s[i] == p[2]):
            ptr = i
            three = True
            break
    
    if(one and two and three): res += 1

print(res)

Measured memory_bytes: 44124
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> x(m);
  rep(i,m) {
    cin >> x[i];
  }

  if (n >= m) {
    cout << 0 << endl;
    return 0;
  }

  sorti(x);
  vector<ll> sum;
  for (int i = 0; i < m-1; ++i) {
    sum.push_back(x[i+1] - x[i]);
  }

  sorti(sum);
  int aa = n - 1;
  ll ans = 0;
  for (int i = 0; i < sum.size() - aa; ++i) {
    ans += sum[i];
  }

  cout << ans << endl;
}


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

int main() {
    ll n;
    cin>>n;
    vector<ll> p(n),q(n);
    rep(i,n){
        cin>>p[i];
        q[i]=p[i];
    }
    sort(p.begin(),p.end());
    ll cnt=0;
    rep(i,n){
        if(p[i]!=q[i])cnt++;
    }
    if(cnt<=2){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}


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

int q, mas[10][10], dy[] = {1, 1, 2}, dx[] = {0, 1, 0};
int draw[][5][5] = {
    {{0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}},
    {{0, 0, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}},
    {{0, 0, 1, 0, 0}, {0, 1, 1, 1, 0}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 0}, {0, 0, 1, 0, 0}},
};

bool check(int y, int x, int w) {
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      if (mas[y + i][x + j - 2] - draw[w][i][j] < 0) return false;
    }
  }
  return true;
}

void paint(int y, int x, int w) {
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      mas[y + i][x + j - 2] -= draw[w][i][j];
    }
  }
}

void repaint(int y, int x, int w) {
  for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
      mas[y + i][x + j - 2] += draw[w][i][j];
    }
  }
}

bool dfs(int y = 0, int x = 0, int n = q) {
  if (n < 0) return false;
  if (y == 10) return n == 0;
  if (mas[y][x] == 0) return dfs(y + (x == 9), (x + 1) % 10, n);
  for (int i = 0; i < 3; i++) {
    if (!check(y, x, i)) continue;
    paint(y, x, i);
    if (dfs(y, x, n - 1)) {
      cout << x + (i == 1) << " " << y + 1 + (i == 2) << " " << i + 1 << endl;
      return true;
    }
    repaint(y, x, i);
  }
  return false;
}

int main() {
  cin >> q;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> mas[i][j];
    }
  }

  dfs();
}

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

int main(){
	unordered_map<int, int> T;
	int n;
	cin >> n;

	rep(i, n){
		int tmp;
		scanf("%d", &tmp);
		if(T.find(tmp) != T.end()){
			T[tmp] = T[tmp] + 1;
		}else{
			T[tmp] = 1;
		}
	}

	int cnt = 0;
	
	for (auto tmp2 : T){
		if(tmp2.first <= tmp2.second){
			cnt += tmp2.second - tmp2.first;
		}else{
			cnt += tmp2.second;
		}
	}	

	cout << cnt << endl;
}


Measured memory_bytes: 4260
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
////////////////////////////


int main(){fastio
    cout<<"square1001"<<endl;
    
    return 0;
}



Measured memory_bytes: 3108
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int idx = -1;
    for(int i = 0; i < s.size(); i++) if(s[i] == '*') idx = i;
    int pos = idx - 1;
    map<char, int> mp;
    while(pos >= 0)
    {
        mp[s[pos]]++;
        pos--;
    }
    int left = abs(mp['('] - mp[')']);
    pos = idx + 1;
    map<char,int > mp2;
    while(pos < s.size())
    {
        mp2[s[pos]]++;
        pos++;
    }
    int right = abs(mp2['('] - mp2[')']);
    cout << right << endl;
    return 0;
}




Measured memory_bytes: 3228
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uld = unsigned long long;
using P = pair<int,int>;
ll MAX(ll a,ll b,ll c){return max(a,max(b,c));}
ll MIN(ll a,ll b,ll c){return min(a,min(b,c));}
const ll mod = 1e9+7;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
template<class T> inline bool chmax(T &a,T& b){if(a < b){a = b; return true;} else return false;}
template<class T> inline bool chmin(T &a,T& b){if(a > b){a = b; return true;} else return false;}
int main(){
    string s;
    cin >> s;
    int n = s.size();
    int count = 0;
    rep(i,n/2){
        if(s[i] != s[n-i-1]) count++;
    }
    cout << count << endl;
}

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a, b; cin >> a >> b;
	int m = (a + b);
	if (m & 1) {
		cout << "IMPOSSIBLE\n";
	} else {
		cout << m / 2 << '\n';
	}
}


Measured memory_bytes: 3484
ABK = list(map(int,input().split()))
A=ABK[0]
B=ABK[1]
K=ABK[2]
for i in range(K):
    if i%2==0:
        if A%2==0:
            A = A/2
        elif A%2==1:
            A = (A-1)/2
        B = B+A
    if i%2==1:
        if B%2==0:
            B = B/2
        elif B%2==1:
            B = (B-1)/2
        A = A+B
print(int(A),int(B))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
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; }

typedef struct {
    int to;
    ll cost;
} edge;

int main() {
    int N;
    scanf("%d", &N);
    vector<edge> tree[N];
    rep(i, N-1){
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        a--; b--;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    int Q, K;
    scanf("%d%d", &Q, &K);
    K--;
    stack<edge> s;
    s.push({K, 0});
    ll depth[N];
    rep(i, N) depth[i] = -1;
    while(!s.empty()){
        edge from = s.top();
        s.pop();
        depth[from.to] = (ll)from.cost;
        for(edge to : tree[from.to]){
            if(depth[to.to] == -1) s.push({to.to, to.cost + from.cost});
        }
    }
    rep(i, Q){
        int x, y;
        scanf("%d%d", &x, &y);
        x--, y--;
        printf("%lld\n", depth[x] + depth[y]);
    }

    return 0;
}


Measured memory_bytes: 10736
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
ll n;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	ll ans = 0;
	for (ll i = 1; i <= n; i++){
		ll x = n/i;
		ans += x*(x + 1)/2*i;
	}
	cout << ans << endl;
}

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

typedef long long ll;
const ll INF = 123456789012345;

int n, m;
int a[2010], b[2010];
ll c[2010];
ll dist[2010];

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[i]--;
    }

    for (int i = 0; i < n; i++){
        dist[i] = -INF;
    }
    dist[0] = 0;

    ll ans;
    for (int i = 0; i <= 2*n; i++){
        for (int j = 0; j < m; j++){
            dist[b[j]] = max(dist[b[j]], dist[a[j]] + c[j]);
        }
    }
    ans = dist[n-1];

    ll next;
    for (int i = 0; i <= 2*n; i++){
        for (int j = 0; j < m; j++){
            dist[b[j]] = max(dist[b[j]], dist[a[j]] + c[j]);
        }
    }
    next = dist[n-1];

    if (next != ans) {
        cout << "inf" << endl;
    } else {
        cout << ans << endl;
    }

}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int INF=12345678;
const int N=1<<16;

int dp[N];
int AND[16][3][7][7];
int OR[16][3][7][7]={};

int solve()
{
    int n;
    cin >>n;
    vector<int> h(n),w(n);
    rep(i,n) cin >>h[i] >>w[i];

    int c[4][4];
    rep(i,4)
    {
        string s;
        cin >>s;
        rep(j,4)
        {
            if(s[j]=='R') c[i][j]=0;
            else if(s[j]=='G') c[i][j]=1;
            else c[i][j]=2;
        }
    }

    #define IN(x,y) (0<=x && x<4 && 0<=y && y<4)
    rep(i,n)rep(col,3)for(int x=-3; x<=3; ++x)for(int y=-3; y<=3; ++y)
    {
        AND[i][col][x+3][y+3] = N-1;

        rep(dy,h[i])rep(dx,w[i])
        {
            int nx=x+dx, ny=y+dy;
            if(IN(nx,ny))
            {
                int shift = ny*4+nx;
                AND[i][col][x+3][y+3] -= 1<<shift;
                if(col == c[ny][nx]) OR[i][col][x+3][y+3] += 1<<shift;
            }
        }
    }

    fill(dp,dp+N,INF);
    dp[0]=0;
    queue<int> que;
    que.push(0);
    while(!que.empty())
    {
        int mask = que.front();
        que.pop();
        rep(i,n)rep(col,3)for(int x=-3; x<=3; ++x)for(int y=-3; y<=3; ++y)
        {
            int nmask = (mask&AND[i][col][x+3][y+3])|OR[i][col][x+3][y+3];

            if(dp[nmask] > dp[mask]+1)
            {
                que.push(nmask);
                dp[nmask] = dp[mask]+1;

                if(nmask == N-1) return dp[nmask];
            }
        }
    }

    assert(false);
}

int main()
{
    printf("%d\n", solve());
    return 0;
}

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

using namespace std;

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

    string s, t;
    cin >> s >> t;

    int n = s.size();
    for(int i = 0; i < n; i++)
    {
        if(s[i] != t[i])
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";

    return 0;
}


Measured memory_bytes: 3652
let m = 1000000007
let ( * ) a b = a * b mod m
let (-) a b = a - b + if a < b then m else 0
let p n r = Array.(init r ((-) n) |> fold_left ( * ) 1)
let rec f b n = if n <= 0 then 1 else let p = f b (n / 2) in p * p * if n mod 2 = 0 then 1 else b
let c n r = p n r * f (p r r) (m - 2)
let _ = Scanf.scanf "%d %d %d" @@ fun n a b -> f 2 n - 1 - c n a - c n b |> Printf.printf "%d\n"

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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll a, b, n;
	cin>>a>>b>>n;
	ll x = min(b-1, n);
	cout<<(a*x/b - a*(x/b))<<'\n';
	return 0;
}

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

int main(){
	int d,t,s; cin>>d>>t>>s;
	int r=(d+s-1)/s;
	if(r<=t) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

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

int main(){
    int N;
    cin >>N;
    int P[N];
    for(int i=0;i<N;i++) cin >>P[i];
    int minp = P[0];
    int count = 0;
    for(int i=0;i<N;i++){
        if(minp>=P[i]){
            count ++;
            minp = P[i];
        }
    }
    cout << count <<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define p (int)(1e9 + 7)

int MOD(int a){
	return (a %= p) >= 0 ? a : a + p;
}

int fact(int N){
	static vector<int> _fact(1, 1);
	for(int i = _fact.size(); i <= N; i++){
		_fact.push_back(MOD(i * _fact[i - 1]));
	}
	return _fact[N];
}
 
int fact_inv(int N){
	static vector<int> inv(2, 1), _fact_inv(2, 1);
	for(int i = inv.size(); i <= N; i++){
		inv.push_back(MOD(-(p / i) * inv[p % i]));
		_fact_inv.push_back(MOD(inv[i] * _fact_inv[i - 1]));
	}
	return _fact_inv[N];
}
 
int combination(int N, int k){
	if(k < 0 || N < k || N < 0) return 0;
	else return MOD(fact(N) * MOD(fact_inv(N - k) * fact_inv(k)));
}

signed main(){
	int X, Y;
	scanf("%lld%lld", &X, &Y);
	if((2 * X - Y) % 3 != 0 || (2 * Y - X) % 3 != 0){
		printf("0\n");
		return 0;
	}
	int x = (2 * X - Y) / 3;
	int y = (2 * Y - X) / 3;
	if(x < 0 || y < 0){
		printf("0\n");
		return 0;
	}
	printf("%lld\n", combination(x + y, x));
	return 0;
}

Measured memory_bytes: 19816
#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int, int> m;
int minCost(int curr, int n, int k, vector<int> &h)
{
    if (curr == n - 1)
        return 0;

    if (m.find(curr) != m.end())
        return m[curr];

    int cost = INT_MAX;

    for (int i = 1; i <= k; i++)
    {
        if (curr + i < n)
        {
            cost = min(cost, abs(h[curr] - h[curr + i]) + minCost(curr + i, n, k, h));
        }
    }
    m[curr] = cost;
    return cost;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++)
        cin >> h[i];

    m.clear();

    vector<int> dp(n, 0);
    for (int i = 1; i < n; i++)
    {
        dp[i] = INT_MAX;
        for (int j = i - 1; j >= 0 && j >= i - k; j--)
        {
            if (dp[i] > dp[j] + abs(h[j] - h[i]))
                dp[i] = dp[j] + abs(h[j] - h[i]);
        }
    }
    cout << dp[n-1];
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
//#define int long long

signed main(){
    string s; cin >> s;
    rep(i,3) if(s[i]=='1') s[i] = '0';
    rep(i,3) if(s[i]=='9') s[i] = '1';
    rep(i,3) if(s[i]=='0') s[i] = '9';
    cout << s << endl;
}

Measured memory_bytes: 384
def solve(string):
    a, b = map(int, string.split())
    count = 0
    for i in range(a, b + 1):
        i = str(i)
        l = len(str(i))
        if i[:(l + 1) // 2] == i[l // 2:][::-1]:
            count += 1
    return str(count)


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 2940
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int p,q,d,r,rrr[1000000][3];
int i,from,count,set;

int main(){
	while(scanf("%d %d",&p,&q)!=EOF){
		set++;count=0;
		while(1){
			p*=10;
			d=p/q;
			r=p%q;
			if(r>0 && rrr[r][2]!=set){
				printf("%d",d);
				rrr[r][2]=set;
				rrr[r][1]=d;
				rrr[r][0]=count;
				p=r;
			}
			else{
				from=rrr[r][0];
				if(rrr[r][1]==d){
					count--;
				}
				else {
					from++;
					printf("%d",d);
				}
				printf("\n");
				break;
			}
			count++;
		}
		if(r>0){
			for(i=0;i<=count;i++)printf("%c",i>=from ? '^' : ' ');
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 5064
S = input()
T = input()

if not S.islower or not T.islower:
    print('No')

if 1 <= len(S) <= 10 and len(T) == len(S) + 1:
    if S == T[0:len(S)]:
        print('Yes')
    else:
        print('No')
else:
    print('No')

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

int main(void){
  string o, e;
  cin >> o >> e;

  string ans;
  int i = 0;
  
  while (i < e.length()) {
    cout << o[i] << e[i];
    i++;
  }
  if (o.length() > e.length()) {
  	cout << o[i];
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int[] Solve(int N, int K, int S)
        {
            var ans = new int[N];
            int T = (S == 1) ? 2 : S - 1;
            for (int i = 0; i < K; ++i) { ans[i] = S; }
            for (int i = K; i < N; ++i) { ans[i] = T; }
            return ans;
        }

        static void Main(string[] args)
        {
            var V = ReadInts();
            Console.WriteLine(string.Join(" ", Solve(V[0], V[1], V[2])));
        }
    }
}


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

int n, m;
vector<int> edge[200004];
int visited[200004];
void makeEdge(int a, int b){
	edge[a].push_back(b);
	edge[b].push_back(a);
}
void dfs(int here){
	visited[here] = true;
	for(int there : edge[here])
		if(!visited[there])
			dfs(there);
}
int main() {
	cin>>n>>m;
	int x, y, z;
	for(int i = 0;i<m;i++){
		cin>>x>>y>>z;
		if(z%2){
			makeEdge(x,y+100000);
			makeEdge(y,x+100000);
		}
		else{
			makeEdge(x, y);
			makeEdge(x+100000,y+100000);
		}
	}
	memset(visited,0,sizeof(visited));
	int cnt = 0;
	for(int i = 1;i<=n;i++)
		if(!visited[i] && !visited[i+100000]){
			dfs(i);
			cnt++;
		}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 15104
#include <cstdio>
using namespace std;
int main(){
    int h, w, n;
    scanf("%d%d%d", &h, &w, &n);
    int maxs = h > w ? h : w;
    int res = n / maxs;
    if(res * maxs < n) res ++;
    printf("%d\n", res);
    return 0;
}


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

using namespace std;
typedef long long LL;

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(M);
  rep(i,M) cin >> A[i];
  int sum=0;
  rep(i,M) sum+=A[i];
  if(N>=sum) cout << N-sum << endl;
  else cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 3632
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

#define REP(i,a,b) for(int i=a; i<=b; i++)

#define MOD 1000000007

void solve(int test_case) {
	int a,b,c;
	cin>>a>>b>>c;
	cout<<min(a*b,c);
	
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3596
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;

void solve() {
  int n, m;
  cin >> n >> m;
  map<int, int> dp;
  while(n--) {
    int x;
    cin >> x;
    dp[x]++;
  }
  while(m--) {
    int amt, val;
    cin >> amt >> val;
    while(amt && dp.begin()->first < val) {
      int use = min(amt, dp.begin()->second);
      dp[val] += use;
      dp[dp.begin()->first] -= use;
      if(dp[dp.begin()->first] == 0) {
        dp.erase(dp.begin());
      }
      amt -= use;
    }
  }
  ll ret = 0;
  for(auto x: dp) {
    ret += x.first * (ll) x.second;
  }
  cout << ret << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
  solve();
}


Measured memory_bytes: 4992
n = int(input())
import numpy as np
abc = np.array([[int(x) for x in input().split()] for y in range(n)],dtype=int)
dp = np.zeros((n,3),dtype=int)
dp[0] = abc[0]
for p in range(1,n):
    dp[p][0] = max(dp[p-1][1],dp[p-1][2]) + abc[p][0]
    dp[p][1] = max(dp[p-1][0],dp[p-1][2]) + abc[p][1]
    dp[p][2] = max(dp[p-1][0],dp[p-1][1]) + abc[p][2]
print(max(dp[n-1]))

Measured memory_bytes: 35552
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
# precise but slow
# from math import floor
# from fractions import Fraction
# a, b = input().split()
# a = int(a)
# b = Fraction(b)
# print(floor(a * b))
# fast but only decimal fixed point
import sys,collections
from math import floor
from decimal import Decimal
N = int(sys.stdin.readline())
a = tuple(sys.stdin.readline().rstrip() for _ in range(N)) # multi line with single param
a = [int(Decimal(e)*1000000000) for e in a]

d = collections.defaultdict(int)
for e in a:#200 000
    b = e
    t = 0
    while b != 0 and b % 2 == 0:
        t += 1
        b = b//2
    b = e
    f = 0
    while b != 0 and b % 5 == 0:
        f += 1
        b = b//5
    d[(min(f,18),min(t,18))] += 1

ret = 0
for ft1,v1 in d.items():
    for ft2,v2 in d.items():
        f1,t1 = ft1
        f2,t2 = ft2
        if ft1 < ft2:
            continue
        if f1+f2 >= 18 and t1+t2 >= 18:
            if ft1 == ft2:
                ret += (v1*(v2-1))//2
            else:
                ret += v1*v2
print(ret)


Measured memory_bytes: 286192
#include<bits/stdc++.h>
#define rep(i,f,n) for(ll i=(f); (i) < (n); i++)
#define repe(i,f,n) for(ll i=(f); (i) <= (n); i++)
using namespace std;
using ll = long long;
#define MOD (ll)1000000007
#define PI 3.14159265359
#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
//#define P pair<ll, ll>
//printf("%.10f\n")
//cout << fixed << setprecision(10);
template<class T> inline bool chmax(T& a, T b){if (a < b) { a = b; return true; } return false;}
template<class T> inline bool chmin(T& a, T b){if (a > b) { a = b; return true; } return false;}
ll INF = 1e+18;
int iINF = 1e9;

int
main()
{

  int N, M; cin >> N >> M;
  if(M % N == 0){
    cout << M / N << endl;
    return 0;
  }
  int maxi = 1;
  rep(i, 1, M/N){
    int d = i;
    if((M - (d * (N - 1))) % d == 0) maxi = i;
  }

  cout << maxi << endl;

}




Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n) ; i++)
#define rrep(i,n) for(int i = n-1; i >= 0 ; i--)
typedef long long ll;
constexpr auto INFI = 2147483647;
const ll INFL = 9223372036854775807;

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

    int ans;
    ans = 1000 - n%1000;
    if (ans == 1000) {
        ans = 0;
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <string>
 
using namespace std;
 
short dp[2048][2048];
short same[2048][2048];

int main()
{
    char s1[2048], s2[2048];
     
    while (scanf("%s", s1) == 1){
        int len = strlen(s1);
		for (int i = 0; s1[i]; i++) s2[len - i - 1] = s1[i];
         
        memset(dp, 0, sizeof(dp));
         
        for (int i = 1; i <= len; i++){
            for (int j = 1; j <= len; j++){
                if (s1[i - 1] == s2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
					same[i][j] = 0;
				}
                else {
                    if (dp[i - 1][j] > dp[i][j - 1]){
						same[i][j] = -1;
						dp[i][j] = dp[i - 1][j];
                    }
					else {
						same[i][j] = 1;
						dp[i][j] = dp[i][j - 1];
					}
				}
            }
        }
		
		for (int i = len, j = len; i && j;){
			if (!same[i][j]){
				printf("%c", s1[i - 1]);
				i--; j--;
			}
			else {
				same[i][j] < 0 ? (i--) : (j--);
			}
		}
		printf("\n");
    }
     
    return (0);
}

Measured memory_bytes: 17332
import copy
n=int(input())
a=[0]+list(map(int,input().split()))
b=copy.copy(a)
psum=0
nsum=0
sum1=0
sum2=0
for i in range(1,n+1):
    if i%2!=0:
        psum+=max([0,1-sum1-a[i]])
        a[i]+=max([0,1-sum1-a[i]])
        sum1+=a[i]
    else:
        psum+=max([0,1+sum1+a[i]])
        a[i]-=max([0,1+sum1+a[i]])
        sum1+=a[i]
for i in range(1,n+1):
    if i%2!=0:
        nsum+=max([0,1+sum2+b[i]])
        b[i]-=max([0,1+sum2+b[i]])
        sum2+=b[i]
    else:
        nsum+=max([0,1-sum2-b[i]])
        b[i]+=max([0,1-sum2-b[i]])
        sum2+=b[i]

print(min([psum,nsum]))


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

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define rep(i, x, y) for(decltype(y) i = (x) - ((x) > (y)); i != (y) - ((x) > (y)); i += 1 - 2 * ((x) > (y)))
#define trav(i,a) for(auto& (i) : (a))
#define all(a) (a).begin(),(a).end()
#define sz(a) int((a).size())
#define clr(a,x) memset((a),(x),sizeof(a)) // array (0,-1)
#define dbg(x) cerr << "STDERR => " << __LINE__ << ": " << #x << " = " << (x) << "  :(\n";
#define pb push_back
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline void cpuTime() { cerr << "cpu time : " << double(clock())/CLOCKS_PER_SEC << "\n"; return; }
using ll = long long;
using ull = unsigned long long;
using F = float;
using D = double;
using vi = vector<int>;
using pii = pair<int,int>;



void solve(){

    string s;
    cin >> s;

    int a = 0, b = 0;
    rep(i,0,3){
        if(s[i] == 'A') ++a;
        else ++b;
    }

    if(!a || !b) cout << "No\n";
    else cout << "Yes\n";
    return;
}

/*
 read the question carefully ( what're the exact constraints? )
 look out for SPECIAL CASES (n=1?) and OVERFLOW (ll vs int?) ARRAY OUT OF BOUNDS
 Check datatypes
*/
int main(){

    fast_io;
    int t=1;
    // cin >> t;

    while(t--){
        solve();
    }

    cpuTime();
return 0;
}


Measured memory_bytes: 384
from collections import Counter

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

S1 = Counter()
S2 = Counter()
for i,a in enumerate(A):
  S1[i+1+a] += 1
  S2[(i+1)-a] += 1

res = 0
for k,v in S1.items():
  if S2[k] > 0:
    res += v*S2[k]

print(res)


Measured memory_bytes: 132776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
#define INF (1<<30)
#define LINF (1ll<<60ll)
#define MOD 1000000007
#define pb(a) push_back(a)
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload4(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)
#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)
#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))
#define d(a) cerr<<#a<<":"<<a<<endl
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl


int main(){
    int n,a,b;
    cin>>n>>a>>b;
    cout<<min(a,b)<<' '<<max(0,a+b-n)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <string>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)a, i##_len=(b); i<i##_len; i++)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define int long long
using namespace std;
using P = pair<int, int>;
using ll = long long;
const ll INF = LLONG_MAX/3;
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct UnionFind{
	std::vector<int> par,siz;
	void init(int n){
		par.resize(n);
		for(int i=0;i<n;i++)par[i]=i;
		siz.resize(n,1);
	}
	UnionFind(int n){
		init(n);
	}
	int root(int n){
		if(par[n]==n)return n;
		else return par[n]=root(par[n]);
	}
	bool issame(int x,int y){
		return (root(x)==root(y));
	}
	bool marge(int a,int b){
		if(issame(a,b))return false;
		else{
			a=root(a),b=root(b);
			if(siz[a]<siz[b])swap(a,b);
			siz[a]+=siz[b];
			par[a]=par[b];
			return true;
		}
	}
	int size(int n){
		return siz[root(n)];
	}
};

long long gcd(long long a,long long b){
    if(b==0)return a;
    return gcd(b,a%b);
}
long long lcm(long long i,long long j){
    return i*(j/gcd(i,j));
}

signed main(){
	int n=50;
	int k;
	cin>>k;
	int a=k/50;
	vector<int> ans;
	rep(i,50)ans.push_back(49+a);
	rep(i,k%50){
		sort(ans.begin(),ans.end());
		ans[0]+=50;
		rep(j,1,50)ans[j]--;
	}
	cout<<n<<endl;
	rep(i,n)cout<<ans[i]<<" ";
	cout<<endl;
}


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

int main() {
  int N, K;
  int sum = 0;
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if (x < (K - x)) {
      sum += 2 * x;
    }
    else {
      sum += 2 * (K - x);
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    string s;
    ll k;
    cin >> s >> k;
    int index;
    if(s.size()>=k) {
        rep(i,k){
            if(s[i]!='1') {
                index = i;
                goto fin;
            }
        }
        cout << "1" << endl;
    }
    else{
        rep(i,s.size()){
            if(s[i]!='1') {
                index = i;
                break;
            }
        }
fin:
        cout << s[index] << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;

//cin.tie(0);
//ios::sync_with_stdio(false);

signed main(){
    ll n,k,ans;cin>>n>>k;
    if(k==1){cout<<1<<endl; return 0;}

    vector<PL> po(n);
    vector<ll> x(n),y(n);
    rep(i,n){
        cin>>x[i]>>y[i];
        po[i].fi=x[i];
        po[i].se=y[i];
    }
    
    sort(all(x));sort(all(y));
    
    ans=(x[n-1]-x[0])*(y[n-1]-y[0]);

    for(int lx=0;lx < n;lx++)
    {
        for(int rx=lx+1;rx < n;rx++)
        {
            for(int dy=0;dy < n;dy++)
            {  
                for(int uy=dy+1;uy < n;uy++)
                {  
                    int cnt=0;
                    for(int i=0;i < n;i++)
                    {
                        if(x[lx]<=po[i].fi && po[i].fi<=x[rx] && y[dy]<=po[i].se && po[i].se<=y[uy]){
                            cnt++;
                        }
                    }

                    if(cnt>k-1)ans=min(ans,(x[rx]-x[lx])*(y[uy]-y[dy]));
                }
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
N = int(input())
T = []

for i in range(N):
    A,B = map(int,input().split())
    T.append([B,A])
T.sort()
now = 0

for i in range(N):
    if now + T[i][1] > T[i][0]:
        print("No")
        sys.exit()
    else:
        now += T[i][1]

print("Yes")

Measured memory_bytes: 76376
#include <stdio.h>

#include <limits.h>   

int main() {    

int i, n, a;    

int min=INT_MAX, max=INT_MIN;    

long long sum=0;    

scanf("%d", &n);     

for(i=0; i<n; i++) {         

scanf("%d", &a);         

if(a<min) min=a;         

if(max<a) max=a;        

sum+=a;    

}     

printf("%d %d %lld\n", min, max, sum);    

return 0;

}

Measured memory_bytes: 600
import java.util.*;

class Main{
    final static long mod = 1000000007;
    //
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int e = Math.min(b,d) - Math.max(a,c);
        if(e >= 0) System.out.println(e);
        else System.out.println(0);
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef vector<ll> vll;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll k, t;
        in >> k >> t;
        vll a(t);
        ll ma = 0;
        for (int i = 0; i < t; i++) {
            in >> a[i];
            ma = max(ma, a[i]);
        }
        out << max(0LL, ma - (k - ma) - 1LL) << '\n';
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;
inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}


 main()

{
    fast
    int n;
    set<int>s;
    cin>>n;
    int yo=n-1;
    for(int i=1;i*i<=yo;i++)
    {
         if(yo%i==0)
         {
             s.insert(i);
             s.insert(yo/i);
         }
    }
    vector<pi>div;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            int x=i;
            int y=n/i;
            div.pb(mp(x,y));
        }
    }
    int sz=div.size();
    f(i,0,sz-1)
    {
        int x=div[i].fi;
        int y=div[i].si;
        while(x%y==0 && x>=1)
        {
            x=x/y;
        }
        if(x%y==1)s.insert(y);
        x=div[i].si;
        y=div[i].fi;
         while(x%y==0 && x>=1)
        {
            x=x/y;
        }
        if(x%y==1)s.insert(y);

    }
    cout<<s.size()<<endl;
    return 0;

}













Measured memory_bytes: 384
#include <stdio.h>
 
int main(void)
{
    int num;
    double w, t, bmi;
     
     
    while (scanf("%d,%lf,%lf", &num, &w, &t) != EOF){
         
        bmi = w / (t * t);
         
        if (bmi >= 25){
            printf("%d\n", num);
        }
    }
    return (0);
}

Measured memory_bytes: 628
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

void main() {
    int n;
    scan(n);
    auto a = readln.split.to!(long[]);
    auto ans = min(solve(n, a, 1), solve(n, a, -1));
    writeln(ans);
}

int sign(long x) {
    return x > 0 ? 1 : x < 0 ? -1 : 0;
}

long solve(int n, long[] a, int pm) {
    long as;
    long res;

    foreach (i; 0 .. n) {
        as += a[i];
        if (sign(as) != pm) {
            res += abs(as - pm);
            as = pm;

        }

        pm *= -1;
    }

    return res;
}

void scan(T...)(ref T args) {
    auto line = readln.split; // @suppress(dscanner.suspicious.unmodified)
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args)
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 5952
# -*- coding: utf-8 -*-
from collections import deque

from sys import setrecursionlimit

setrecursionlimit(1000000)

INF = float("inf")
# Input#
# n = int(input())
n, m = map(int, input().split())
# a = list(map(int, input().split()))

d = deque()
d_tmp = deque()
x = [-1]
y = [[-1] for _ in range((n + 1))]

for _ in [0] * m:
    x_in, y_in = map(int, input().split())
    #    x.append(x_in)
    y[x_in].append(y_in)
    d.append((x_in, y_in))

memo = [-1] * (n + 1)
ans = -1


def dp(i):
    global ans
    if memo[i] == -1:
        ret = 0
        for x_in in y[i][1:]:
            tmp = dp(x_in) + 1
            if tmp > ret:
                ret = tmp
        memo[i] = ret
        if ret > ans:
            ans = ret
        return ret
    else:
        return memo[i]


for i, _ in d:
    if memo[i] == -1:
        dp(i)

print("{}".format(ans))


Measured memory_bytes: 166084
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define ull unsigned long long
#define REP(i, n) for(int i=0; i<n; i++)

int main(){
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    float w;
    float s;
    float ws;
    float ans_ws = 100*A;
    float ans_s = 0;
    float max_l = 0;
    REP(a,31)
        REP(b,31){
            if(a == 0 && b == 0) continue;
            if(a+b > 30) break;
            REP(c,3001)
                REP(d,3001){
                    //if(c == 0 && d == 0) continue;
                    w = 100*A*a + 100*B*b;
                    s = C*c + D*d;
                    ws = w+s;
                    if(ws > F) break;
                    //printf("ws:%f, s:%f, L:%f\n", ws, s, 100*s/w);
                    if(s*100 > E*w) break;        
                    if(100*s/ws > max_l){
                        max_l = 100*s/ws;
                        ans_s = s;
                        ans_ws = ws;
                    }
                }

        }
    
    cout << ans_ws << " " << ans_s << endl;
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>  
#include <stdbool.h>   
#define inf (INT_MAX-1)
#define INF 9223372036854775807;
#define PI 3.14159265358979323846;
#define EPS 1e-10
#define sq(n) ((n)*(n))
#define rep(i,n) for(i=0;i<n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
/*
#define sort(a,n) qsort(a,n,sizeof(TYPE),cmp)
#define sort_r(a,n) qsort(a,n,sizeof(TYPE),cmp_r)
*/
#define chsort(s,n) qsort(s,n,sizeof(char),cmp)
#define chsort_r(s,n) qsort(s,n,sizeof(char),char_cmp_r)
#define TYPE long long
#define ll long long
#define MEMSET(a) memset(a,0,sizeof(a))
#define MEMSET_U(a) memset(a,-1,sizeof(a))
#define bool    _Bool
const int mod = (int)1e09 + 7;

//#define DEBUG1
//#define DEBUG2
//#define DEBUGF
#define DUMMY

int in(void) { int i; scanf("%d", &i); return i; }
long long llin(void) { long long i; scanf("%lld", &i); return i; }
double din(void) { double i; scanf("%lf", &i); return i; }
void chin(char s[]) { scanf("%s", s); }

void print(int a) { printf("%d\n", a); }
void llprint(long long a) { printf("%lld\n", a); }
void dprint(double a) { printf("%.10f\n", a); }
void print2(int a, int b) { printf("%d %d\n", a, b); }
int Max(int a, int b) { if (a > b) { return a; }return b; }
int Min(int a, int b) { if (a < b) { return a; }return b; }
long long llmax(long long a, long long b) { return a > b ? a : b; }
long long llmin(long long a, long long b) { return a < b ? a : b; }
double dmax(double a, double b) { return a > b ? a : b; }
double dmin(double a, double b) { return a < b ? a : b; }
//long long llmax(long long a, long long b) { return a > b ? a : b; }
//long long llmin(long long a, long long b) { return a < b ? a : b; }
//double dmax(double a, double b) { return a > b ? a : b; }
int cmp(const void *a, const void *b) { return *(TYPE *)a - *(TYPE *)b; }
int cmp_r(const void *a, const void *b) { return *(TYPE *)b - *(TYPE *)a; }
int char_cmp(const void *a, const void *b) { return strcmp((char *)a, (char *)b); }
int char_cmp_r(const void *a, const void *b) { return strcmp((char *)b, (char *)a); }
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }



int main() {
	int sx, sy, tx, ty;
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);

	int dx = (tx - sx);
	int dy = (ty - sy);

	//path1
	for (int i = 0; i < dx; i++) { printf("R"); }
	for (int i = 0; i < dy; i++) { printf("U"); }
	//path2
	for (int i = 0; i < dx; i++) { printf("L"); }
	for (int i = 0; i < dy; i++) { printf("D"); }
	//path3
	printf("D");
	for (int i = 0; i < dx+1; i++) { printf("R"); }
	for (int i = 0; i < dy+1; i++) { printf("U"); }
	printf("L");
	//path4
	printf("U");
	for (int i = 0; i < dx + 1; i++) { printf("L"); }
	for (int i = 0; i < dy + 1; i++) { printf("D"); }
	printf("R");
	printf("\n");

#ifdef DEBUGF
	getch();
#endif
	return 0;
}

Measured memory_bytes: 128