akhauriyash/Code-Regression huggingface dataset:
N = int(input())
S = list(input())
S_2 = S[:]
prev = 0
cnt = 0
new_str = []
for i in range(len(S)):
	if S[i] == '(':
		cnt += 1
	else:
		cnt -= 1

	if cnt < 0:
		S_2.insert(0,'(')
		cnt += 1


if cnt > 0:
	for i in range(cnt):
		S_2.append(')')

print(''.join(S_2))

Measured memory_bytes: 3064
//21171_somesh || asomesh999

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(long long i=a;i<b;i++)
#define io ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
long int mod=1000000007;

int main()
{
	io
	#ifdef SOMU
		clock_t startTime = clock();
		freopen("input.txt","r",stdin);
	#endif

	int a, b;
	cin >> a >> b;
	if (a <= 9 && b <= 9) {
		cout << a * b;
	} else {
		cout << -1;
	}

	#ifdef SOMU
		cerr << endl <<setprecision(20)<< double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;
	#endif
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define COUT(x) cout<<x<<"\n"

const ll INF = 1e18;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll GCD(VI v){ll a = v[0]; for (ll i = 1; i<SIZE(v); i++) {a = gcd(a, v[i]);} return a;}
ll LCM(VI v){ll a = v[0]; for (ll i = 1; i<SIZE(v); i++) {a = lcm(a, v[i]);} return a;}

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) {
	if(x == 0) return 0;
	return counter(x >> 1) + (x & 1);
}

void Main() {
	cin >> N;
	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		for(int j = 1; j <= A[i]; j++) {
			cin >> x[i][j] >> y[i][j];
		}
	}
	int ans = 0;
	for(int bits = 1; bits < (1 << N); bits++) {
		bool ok = true;
		for(int i = 1; i <= N; i++) {
			if(!(bits & (1 << (i-1)))) continue;
			for(int j = 1; j <= A[i]; j++) {
				if(((bits >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false;
			}
		}
		if(ok) ans = max(ans, counter(bits));
	}
	cout << ans << endl;
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int N, K;
    cin >> N >> K;
    unsigned int a[N], dp[K + 1][N];//intでは若干ケタが足らずWAが出る
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for(int j = 0; j < N; j++) {
        dp[0][j] = 1;
    }
    for(int i = 1; i <= K; i++) {
        if(i <= a[0]) {
            dp[i][0] = 1;
        } else {
            dp[i][0] = 0;
        }
        for(int j = 1; j < N; j++) {
            if(a[j] == 0) {
                dp[i][j] = dp[i][j - 1];
            } else {
                if(i <= a[j]) {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] ) % (1000000007);
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1 - a[j]][j - 1] + 1000000007) % (1000000007);
                }
            }
        }
    }
    cout << dp[K][N - 1] << endl;
    return 0;
}
 

Measured memory_bytes: 39296
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,l,r) for(int i=(l);i<(r);i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef long long ll;  //ll とdoubleは違う
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;  
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VII;   // VII a(n,vector<int>(m)) n * m 
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<ll, ll> > PS;
template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b){
    if (a < b){ a = b;return 1;}
    return 0;
}
template <class T, class U> //chmin(min,a)
bool chmin(T &a, U b){
    if (a > b){ a = b; return 1;}
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}
// g++ -std=c++11 prac.cpp 

int main(){
    ll x,y,z=0,n,m=0,k,ans=0,h,w,sum=0,Max=-1e9-1,cnt=0,Min=1e9+1;
    string s,t,u;
    bool ok=true;
    cin >> n >> x >> y;
    VL a(n); 

    rep(i,n){
        cin >> a[i];
    }

    rep(i,n-1){
        if((a[i+1]-a[i])*x < y){
            ans += (a[i+1]-a[i])*x;
        }
        else{
            ans += y;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define two(a) (1<<(a))
#define LINF (1ll<<61)
#define EPS (1e-14)
#define Lshift(a,b) ((a)<<(b))
#define Rshift(a,b) ((a)>>(b))
#define rep(a,b) for(a=0 ; a<b ; a++)
#define xrep(a,b,c) for(a=b ; a<c ; a++)
#define INF (1<<29)
#define sz(a) int(a.size())
#define mset(x) memset(x, 0, sizeof(x))
#define swap(a,b) ( (a^=b) , (b^=a) , (a^=b) )
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5]|=1<<(x&31))
#define maxL (10000000>>5)+1
#define mod 1000000007
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define si set<int>
#define pb push_back
typedef long long ll;
using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, i;

    cin >> n;
    vector<ll> l(n);
    rep(i, n) {
        cin >> l[i];
    }

    ll ans(0);
    ll j, k;
    rep(i, n) xrep(j, i+1, n) xrep(k, j+1, n) {
        ll a = l[i];
        ll b = l[j];
        ll c = l[k];
        if (a == b || b == c || a == c) continue;
        if (a + b > c && b + c > a && a + c > b) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3660
/*==============================================*\
ID:          shahidul_brur
 
Name:     Md. Shahidul Islam
Study:      CSE, BRUR
Address:  Rangpur, Bangladesh
 
 mail: shahidul.cse.brur@gmail.com
 FB  : fb.com/shahidul.brur
 Blog: shahidul-brur.blogspot.com(in Bengali),
       shahidul-brur-en.blogspot.com(in English)
\*===============================================*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz size()
#define all(a)  a.begin(), a.end()
#define mem(a, b)     memset(a, b, sizeof(a))
#define f0(i,b) for(int i=0;i<(b);i++)
#define f1(i,b) for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
 
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};

const double pi = acos(-1.0);
const double eps = 1e-6;
const int mod = (int)1e9+7;
const int maxn = (int)2e5+5;
const int logn = 20;
int n, a[maxn];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>n;
    f1(i,n) cin>>a[i];
    multiset<int> seq;
    f1(i,n)
    {
        if(seq.size()==0 || *seq.begin()>=a[i]){
            seq.insert(a[i]);
            continue;
        }
        auto it = seq.lower_bound(a[i]);
        --it;
        int les = *it;
        seq.erase(it);
        seq.insert(a[i]);
    }
    cout << seq.size() << "\n";
    return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL
using ll = long long;
template<typename T>
using vec = vector<T>;
using P = pair<ll, ll>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
	fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[51][52];

int main(){
	IOS;
	ll n, x;
	cin >> n >> x;
	if(n == 2){
		dump(x == 2 ? "Yes\n1\n2\n3" : "No");
	}
	else {
		if(x < 2 || x > 2 * n - 2){
			dump("No");
			return 0;
		}
		dump("Yes");
		deque<ll> q;
		vec<bool> used(2 * n,false);
		q.push_back(x);
		q.push_back(x - 1);
		q.push_front(x + 1);
		if(x != 2 * n - 2)q.push_back(x + 2);
		if(x != 2)q.push_front(x - 2);
		for(int i = x - 2;i <= x + 2;i++)used[i] = true;
		bool f = true;
		if(x == 2 * n - 2)f = false;
		for(int i = 1;i <= 2 * n - 1;i++){
			if(used[i])continue;
			if(f){
				q.push_front(i);
				f = false;
			}
			else { 
				q.push_back(i);
				f = true;
			}
		}
		ll m = q.size();
		REP(i,m)dump(q[i]);
	}
}

Measured memory_bytes: 3200
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
const int mod = 1000000007;

// auto mod int
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;} 

mint choose(int a, int b){
    //aCb
    mint x = 1, y = 1;
    for (int i = 1; i <= b; i++) {
        x *= (a - i + 1);
        y *= i;
    }
    return x / y;
}


int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    mint ans = mint(2).pow(n) - 1;
    ans -= choose(n, a);
    ans -= choose(n, b);
    cout << ans.x << endl;

    return 0;
}

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

int main()
{
  int64_t N, K, ans = 0;
  cin >> N >> K;
  vector<int64_t> P(N);
  for (int i = 0; i < N; i++)
  {
    cin >> P.at(i);
  }
  sort(P.begin(), P.end());
  for (int i = 0; i < K; i++)
  {
    ans += P.at(i);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3556
#include<bits/stdc++.h>
using namespace std;
bitset<2000002>f;
int n,i,x,s;
int main(){
    scanf("%d",&n),f[0]=1;
    for (;n--;){
        scanf("%d",&x),s+=x;
        f|=f<<x;
    }
    for (i=(s+1)/2;i<=s;i++)
        if (f[i]) return printf("%d",i),0;
}

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

long long p(int a, int n)
{
    if (n == 1) return a;
    return a * p(a, n - 1);
}
int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> mod(k, 0);
    for (int i = 1; i <= n; i++) mod[i % k]++;

    long long cnt = 0;
    if (k % 2) {
        cnt += p(mod[0], 3);
    }
    else {
        cnt += p(mod[0], 3);
        cnt += p(mod[k / 2], 3);
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std ;
#define An setprecision(16) 
#define MAX_N 100
#define MAX_V 100
#define MAX_K 100000
#define INF 100000000
#define pi 3.14159265358979323846264338327950
int main(){
    int X;
    cin >> X;
    if(X<=599)cout << 8<<endl;
    else if(X<=799)cout << 7<<endl;
    else if(X<=999)cout << 6<<endl;
    else if(X<=1199)cout << 5<<endl;
    else if(X<=1399)cout << 4<<endl;
    else if(X<=1599)cout << 3<<endl;
    else if(X<=1799)cout << 2<<endl;
    else if(X<=1999)cout << 1 <<endl;
}

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

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

	if(A + B >= K) {
		cout << min(A, K) << endl;
	} else {
		cout << A - (K - (A+B)) << endl;
	}
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define int long long

const int N = 2008;
const int INF = 1e18 + 293;

int n;
vector<int> a;
vector<int> ind;
int dp[N][N];

int calc(int i, int j) {
	if (dp[i][j] == -INF) {
		int who = i + j - 1;
		if (i > 0) {
			dp[i][j] = max(dp[i][j], abs((i - 1) - ind[who]) * a[ind[who]] + calc(i - 1, j));
		}
		if (j > 0) {
			dp[i][j] = max(dp[i][j], abs((n - j) - ind[who]) * a[ind[who]] + calc(i, j - 1));
		}
	}
	return dp[i][j];
}

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dp[i][j] = -INF;
		}
	}
	dp[0][0] = 0;

	cin >> n;
	a.resize(n);
	for (auto &t : a) {
		cin >> t;
	}
	ind.resize(n);
	iota(ind.begin(), ind.end(), 0);
	sort(ind.rbegin(), ind.rend(), [&](int i, int j) {
		return a[i] < a[j];
	});
	// for (int i = 0; i < n; i++) {
	// 	cerr << ind[i] << ' '; 
	// }
	// cerr << endl;
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		ans = max(ans, calc(i, n - i));
	}
	cout << ans << endl;
}


Measured memory_bytes: 34788
N = int(input())
T, A = map(int, input().split())
H = map(int, input().split())

dif = 1000
loc = 1
for i in H:
    a = abs(A-(T-i*0.006))
    if a < dif:
        dif = a
        ans = loc
    loc += 1

print(ans)


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

int main() {
    string s, t;
    cin >> s >> t;

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

Measured memory_bytes: 3620
#include<iostream>
#include <string>
#include<vector>
typedef long long ll;

using namespace std;
int main()
{
	int n,m,x,y;
	cin >> n>>m>>x>>y;
	vector<int> xs(n);
	vector<int> ys(m);
	for (int i = 0; i < n; i++) {
		cin >> xs[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> ys[i];
	}

	int max_x = x;
	int min_y = y;

	for (int i = 0; i < n; i++) {
		if(xs[i]>max_x) max_x=xs[i];
	}
	for (int i = 0; i < m; i++) {
		if (ys[i] < min_y) min_y=ys[i];
	}

	string kotae;
	if (max_x < min_y) {
		kotae = "No War";
	}
	else {
		kotae = "War";
	}

	cout << kotae;
	return 0;
}

Measured memory_bytes: 256
l,r=map(int,input().split())
s=[]
if ((r//2019)!=(l//2019)):
    a=0
    s.append(a)
elif((r-l!=1)):
    for i in range(l,r-1):
        for j in range(i+1,r+1):
            #print(i,j)
            a=(i*j)%2019
            #print(a)
            s.append(a)
            if (a==0):
                break
else:
    a=(l*r)%2019
    s.append(a)
print(min(s))



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

typedef long long int in;

int main() 
{
	in n,k;
	cin>>n>>k;
	
	in a[n],i,j,dp[n];
	
	for(i=0;i<n;++i)
	{
	    cin>>a[i];
	    dp[i]=1e15;
	}
	
	dp[0]=0;
	
	for(i=1;i<n;++i)
	{
	    for(j=1;j<=k;++j)
	    if(i-j>=0)
	    dp[i]=min(dp[i],abs(a[i]-a[i-j])+dp[i-j]);
	    
	    //cout<<dp[i]<<" ";
	}
	
	cout<<dp[n-1];
	
	return 0;
}

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  cout << (a+b+c<22?"win":"bust") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main(){
    int n;
    cin>>n;
    vi ar(n);
    for(int i=0;i<n;i++){
        cin>>ar[i];
    }
    vi dp(n,0);
    dp[n-2]=abs(ar[n-1]-ar[n-2]);
    for(int i=n-3;i>=0;i--){
        dp[i]=min( abs(ar[i]-ar[i+1]) + dp[i+1] , abs(ar[i]-ar[i+2]) + dp[i+2] ) ;
    }
    cout<<dp[0]<<"\n";
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define all(c) begin(c),end(c)
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
using ll = long long;
using vi = vector<int>; using vs = vector<string>;
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

vs S; int N; int id;
int dfs(int depth)
{
	id++;

	//cout << id << " " << depth << endl;
	if (S[id][depth] == '+')
	{
		int ret = 0;
		while (id + 1 < N)
		{
			if (depth < S[id + 1].size() && S[id + 1][depth] == '.')ret += dfs(depth + 1);
			else break;
		}
		return ret;
	}
	else if (S[id][depth] == '*')
	{
		int ret = 1;
		while (id + 1 < N)
		{
			if (depth < S[id + 1].size() && S[id + 1][depth] == '.')ret *= dfs(depth + 1);
			else break;
		}
		return ret;
	}
	else
	{
		return S[id][depth] - '0';
	}
}

void solve()
{
	while (cin >> N, N)
	{
		S = vs(N);
		for (int i = 0; i < N; i++)
		{
			cin >> S[i];
		}
		id = -1;
		cout << dfs(0) << endl;
	}
}


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


Measured memory_bytes: 3120
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <cmath>
#include <numeric>
#include <functional>
#include <stack>
#include <iomanip>
#include <map>
#include <cstdio>

int main() {
	long long n;

	std::cin >> n;

	std::vector<long long> v(n);

	for (size_t i = 0; i < n; i++)
	{
		std::cin >> v[i];
	}

	long long min_helth = 10000000000000000LL;
	int ans = 0;

	for (size_t i = 0; i < 100; i++)
	{
		long long sum = 0;
		for (size_t j = 0; j < v.size(); j++)
		{
			sum += (i - v[j]) * (i - v[j]);
		}
		if (sum < min_helth) {
			min_helth = sum;
			ans = i;
		}
	}

	std::cout << min_helth << std::endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60

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

	string S; cin >> S;
	int ans = 0;

	// 奇数回目にg
	for (int i = 0; i < S.size(); i += 2) {
		if (S[i] == 'p') ans--;
	}

    //偶数回目にp
	for (int i = 1; i < S.size(); i += 2) {
		if (S[i] == 'g') ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640
from operator import mul
from functools import reduce

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


a = int(input())

b = [0 for i in range(15)]
j = 0
c = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
d = [0 for i in range(101)]
p = 0
pp = 0
g = 0
gg = 0
ggg = 0
co = 0
for i in range(1,101):
  k = i
  while True:
    if k % c[j] == 0 and k >= c[j]:
      b[j] += 1
      k //= c[j]
    else:
      j += 1
      if j == 15:
        j = 0
        break
  for k in range(15):
    if b[k] >= 74:
      g += 1
    if b[k] >= 24:
      gg += 1
    if b[k] >= 14:
      ggg += 1
    if b[k] >= 4:
      p += 1
    if b[k] >= 2:
      pp += 1
  if i >= 10:
    d[i] = cmb(p, 2)*cmb((pp-2), 1) + cmb(g, 1) + cmb(gg, 1)*cmb((pp-1), 1) + cmb(ggg, 1)*cmb((p-1), 1)
  p = 0
  pp = 0
  g = 0
  gg = 0
  ggg = 0
print(d[a])

Measured memory_bytes: 3572
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 998244353
#define F first
#define S second
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)

bool isPowerOfTwo(int n)
{
   if(n==0)
   return false;

   return (ceil(log2(n)) == floor(log2(n)));
}
int power(int x, unsigned int y)
{
    if (y == 0)
        return 1;
    else if (y % 2 == 0)
        return power(x, y / 2) * power(x, y / 2);
    else
        return x * power(x, y / 2) * power(x, y / 2);
}
signed main()
{
   int a,b;
   cin>>a>>b;
   int x=min(a,b);
   int y=max(a,b);
   int ans=0;
   while(y--)
   {
       ans+=power(10,y);
   }
   cout<<x*ans<<endl;
    }



Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
	static void Main()
	{
		int n = int.Parse(Console.ReadLine());
		string[] input = Console.ReadLine().Split(' ');
		long a = long.Parse(input[0]);
		long b = long.Parse(input[1]);
    long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
    long answer = long.MaxValue;
    long[] answers = new long[3];

    for(int i = 0; i < n; i++)
    {
      if(nums[i] <= a) answers[0]++;
      else if(nums[i] <= b) answers[1]++;
      else answers[2]++;
    }

    answer = Math.Min(answers[0], answers[1]);
    answer = Math.Min(answer, answers[2]);
		
		Console.WriteLine(answer);
	}
}

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

int main(){
    string S;
    cin >> S;
    int ans = 700;
    for (int i = 0; i < 3; i++)
    {
        if(S[i] == 'o') ans += 100;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    while(1){
        int n;
        cin>>n;
        if(n=='\0')break;
        int d[6]={500,100,50,10,5,1};
        int A=1000-n;
        int ans=0;
        for(int i=0;i<6;i++){
            int x=A/d[i];
            A-=x*d[i];
            ans+=x;
        }
        cout<<ans<<endl;
    }
    return 0;
}



Measured memory_bytes: 2988
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<queue>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  ll A, B;
  char op;
  cin >> A >> op >> B;
  if (op == '+') cout << A+B << endl;
  else cout << A-B << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <random>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0)
{ v = vector<T>(n+o); for (lli i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (lli i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct Edge {
  lli to, cost;
  Edge(lli to=0, lli cost=0) : to(to), cost(cost) {}
};

lli n, q, k;
vector<Edge> e[100010];
lli dist[100010];
int main() {
  cin >> n;
  for (lli i=0; i<n-1; ++i) {
    lli a, b, c; cin >> a >> b >> c;
    e[a].emplace_back(b, c);
    e[b].emplace_back(a, c);
  }
  cin >> q >> k;

  fill(begin(dist), end(dist), -1);
  using P = pair<lli, lli>;
  priority_queue<P, vector<P>, greater<P>> pq;
  pq.emplace(0, k);

  while (!pq.empty()) {
    auto p = pq.top(); pq.pop();
    lli cost = p.first, vtx = p.second;
    if (dist[vtx] >= 0) continue;
    dist[vtx] = cost;
    for (Edge& f : e[vtx]) {
      pq.emplace(cost + f.cost, f.to);
    }
  }
  cerr << "ready\n";

  for (lli i=0; i<q; ++i) {
    lli x, y; cin >> x >> y;
    cout << dist[x] + dist[y] << '\n';
  }
  return 0;
}


Measured memory_bytes: 11120
#include <iostream>
#include <set>

#define maxN 100010

int main()
{
	std::set< std::pair<int, int> > set;
	int up[maxN] = { 0 }, down[maxN] = { 0 }, ss[maxN], ts[maxN], cs[maxN], max = 0, n, c, count = 0;
	
	std::cin >> n >> c;
	for (int i = 0; i < n; ++i)
	{
		std::cin >> ss[i] >> ts[i] >> cs[i];
		
		set.insert(std::make_pair(ts[i], cs[i]));
	}
	
	for (int i = 0; i < n; ++i)
	{
		if (set.count(std::make_pair(ss[i], cs[i])))
		{
			--down[ss[i]];
			--up[ss[i]];
		}
		
		++up[ss[i]];
		++down[ts[i]];
	}
	for (int i = 0; i <= 100000; ++i)
	{
		count += up[i];
		max = std::max(max, count);
		count -= down[i];
	}
	
	std::cout << max;
}

Measured memory_bytes: 6912
while True:
    a,b = map(int, input().split())
    if a==0 and b==0: break
    for i in range(a):
        for j in range(b):
            if (i+1) % 2 != 0:
                if (j+1) % 2 != 0:
                    print("#", end='')
                else:
                    print(".",end='')
            else:
                if (j+1) % 2 == 0:
                    print("#", end='')
                else:
                    print(".",end='')
        print("")
    print("")


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	for(;;++n){
		if(n/100==n/10%10&&n/10%10==n%10)break;
	}
	cout<<n<<"\n"s;
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.141592653589793238462643383279;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

long long gcd(long long x, long long y){return x % y == 0 ? y : gcd(y, x%y);}

int main(void){
    int T; cin >> T;
    REP(_,T){
        ll A,B,C,D; cin >> A >> B >> C >> D;
        if(A < B) cout << "No" << en;
        else if(B <= A && D < B) cout << "No" << en;
        else if(B <= A && B <= D && B <= C) cout << "Yes" << en;
        else{
            ll g = gcd(B,D);
            cout << (B-g+A%g <= C ? "Yes" : "No") << en;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

	if (n % 10 == 9 || n / 10 == 9) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}


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

int main()
{
  string S;
  cin >> S;
  if (S[0] != S[1] || S[1] != S[2])
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
# coding: utf-8

# https://atcoder.jp/contests/abc118


def main():
    N, M = map(int, input().split())
    k_a = [None] * N
    for i in range(N):
        k_a[i] = list(map(int, input().split()))
    
    food = [0] * (M+1)
    for i in range(N):
        for j in range(1, k_a[i][0]+1):
            food[k_a[i][j]] += 1
    
    ans = 0
    for m in range(1, M+1):
        if food[m] == N:
            ans += 1
    
    return ans


print(main())


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

int main() {

    int n;
    cin >> n;
    map<int,int> boss;

    rep(i,n) boss[i] = 0;

    for(int i = 0; i < n-1; i++){
        int tmp;
        cin >> tmp;
        boss[tmp-1] += 1;
    }

    for( auto i = boss.begin(); i != boss.end() ; ++i ) {
        cout << i->second << endl;
    }

    return 0;
}   

Measured memory_bytes: 12976
#include "bits/stdc++.h"
using namespace std ;

#define timesaver ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

typedef long long ll ;
typedef long double ldb ;

#define mp make_pair
#define pb push_back
#define F first
#define S second
#define nl '\n'

#define all( x ) x.begin(),x.end() 
#define sz( x ) ( int )( x ).size( )
#define mem( a, val ) memset(a, val, sizeof( a ) )
#define deci( x ) cout<<fixed<<setprecision( x );
#define bitcount( x ) __builtin_popcountll( x )

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

const int MAX = 2*1000*1000 + 10 ;
const ll INF = 1e18 ;
const int MOD = 1e9 + 7 ;

ll exp( ll x, ll y ){
    ll ans = 1 ;
    while(y){
        if(y&1)
            ans = (ans*x)%MOD ;
        x = (x*x)%MOD ;
        y>>=1 ;
    }
    return ans ;
}

void sol( ){
    ll n ;
    cin >> n ;
    ll ans = (exp( 10, n ) - exp(9, n )  + MOD ) % MOD ;
    ans = ( ans - exp(9,n) + MOD ) % MOD ;
    ans = ( ans + exp(8,n) )%MOD ;
    cout << ans << nl ;
}

signed main( ){
  timesaver ;
//  int t = 1 ; cin >> t ; while(t--)
  {
      sol( );
  }
}

Measured memory_bytes: 3660
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int N;
ll a[300000];
set<pair<ll,int>> A, B, Bl;
ll Asum = 0, Bsum = 0;

signed main(){
    cin >> N;
    rep(i, 3*N){
        cin >> a[i];
        if(i < N){
            Asum += a[i];
            A.insert({ a[i],i });
        }
        else B.insert({ a[i],i });
    }

    auto itr = B.begin();
    rep(j, N){
        Bsum += itr->first;
        itr++;
    }
    rep(j, N){
        Bl.insert(*prev(B.end()));
        B.erase(prev(B.end()));
    }

    ll ans = Asum - Bsum;
    rep(i, N){
        Asum += a[N+i];
        A.insert({ a[N+i], N+i });
        Asum -= A.begin()->first;
        A.erase(A.begin());
        if(Bl.count({ a[N+i], N+i })){
            Bl.erase({ a[N+i], N+i });
        }
        else{
            Bsum -= a[N+i];
            B.erase({ a[N+i],N+i });
            Bsum += Bl.begin()->first;
            B.insert(*Bl.begin());
            Bl.erase(Bl.begin());
        }
        ans = max(ans, Asum-Bsum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 24728
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a0=int(input())
if a0!=0:
    print(-1)
    exit()
ab=0
ans=0
for i in range(n-1):
    a=int(input())
    if a==ab+1:
        ans+=1
    elif a>ab+1:
        print(-1)
        exit()
    else:
        ans+=a
    ab=a
print(ans)

Measured memory_bytes: 75796
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [None]*n
b = [None]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())
    
ab = [(a[i]+b[i], i) for i in range(n)]
ab.sort(reverse=True)
takahashi = 0
aoki = 0
for i in range(n):
    if i%2==0:
        takahashi += a[ab[i][1]]
    else:
        aoki += b[ab[i][1]]
print(takahashi-aoki)

Measured memory_bytes: 87112
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
using namespace std;

using VI = vector <int> ;
using VVI = vector <VI> ;

void group(VVI& adja, VVI& groups, VI& colors, int now, int color) {

    colors[now] = color;
    groups[color].push_back(now);

    for (int i = 0; i < adja[now].size(); ++i) {
        int nextv = adja[now][i];

        if (colors[nextv] == -1) {
            group(adja, groups, colors, nextv, (color+1)%2);
        }
    }
}

void color(VI& res, VI& set1, VI& set2) {
    int N = res.size();
    vector <int> cnt(3);
    vector <int> maxVal(3);
    cnt[0] = 3;
    cnt[1] = 1;
    cnt[2] = 2;

    maxVal[0] = N/3 * 3;
    maxVal[1] = (N-1)/3 * 3 + 1;
    maxVal[2] = (N-2)/3 * 3 + 2;

    if (set1.size() <= N/3) {
        for (int i = 0; i < set1.size(); ++i) {
            res[set1[i]] = cnt[0];
            cnt[0] += 3;
        }

        int idx = 0;
        for (int i = 0; i < 3; ++i) {
            while (cnt[i] <= maxVal[i]) {
                res[set2[idx++]] = cnt[i];
                cnt[i] += 3;
            }
        }
    } else {
        vector <int> idx(2);
        // #mod 2 <= #mod 1, and |set1| <= |set2|

        while (cnt[2] <= maxVal[2]) {
            res[set1[idx[0]++]] = cnt[2];
            cnt[2] += 3;
        }

        while (cnt[1] <= maxVal[1]) {
            res[set2[idx[1]++]] = cnt[1];
            cnt[1] += 3;
        }

        while (idx[0] < set1.size()) {
            res[set1[idx[0]++]] = cnt[0];
            cnt[0] += 3;
        }

        while (idx[1] < set2.size()) {
            res[set2[idx[1]++]] = cnt[0];
            cnt[0] += 3;
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);

    VVI adja(N);
    VVI groups(2);
    VI colors(N, -1);
    VI res(N);

    int root = 0;

    for (int i = 1; i < N; ++i) {
        int f;
        int t;
        scanf("%d %d", &f, &t);
        --f;
        --t;

        adja[f].push_back(t);
        adja[t].push_back(f);
    }

    group(adja, groups, colors, root, 0);

    if (groups[0].size() < groups[1].size()) {
        color(res, groups[0], groups[1]);
    } else {
        color(res, groups[1], groups[0]);
    }

    cout << res[0];
    for (int i = 1; i < res.size(); ++i) {
        cout << " " << res[i] ;
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 23032
nlist = []

n = gets.to_i
nlist = gets.split.map(&:to_i)

max = 0
for i in 0...nlist.length do
    for j in 1...nlist.length do
        work = (nlist[i] - nlist[j]).abs
        if work > max
            max = work
        end
    end
end

p max


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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    ll N;
    cin >> N;
    vector<Pll> b, c, d;
    ll sum = 0;
    for (ll i = 0; i < N; i++) {
        string s;
        cin >> s;

        ll n = (ll)s.size();

        ll curl = 0, curr = 0;
        ll mnl = 0, mnr = 0;

        for (ll i = 0; i < n; i++) {
            if (s[i] == '(') {
                ++curl;
            }
            else {
                --curl;
            }
            mnl = min(mnl, curl);
        }

        for (ll i = n - 1; i >= 0; i--) {
            if (s[i] == ')') {
                ++curr;
            }
            else {
                --curr;
            }
            mnr = min(mnr, curr);
        }

        if (curl > 0) {
            b.emplace_back(mnl, curl);
        }
        else if (curl == 0) {
            c.emplace_back(mnl, curl);
        }
        else {
            d.emplace_back(mnr, curr);
        }

        sum += curl;
    }

    if (sum != 0) {
        cout << "No\n";
        return;
    }

    sort(b.begin(), b.end(), greater<Pll>());
    sort(c.begin(), c.end());
    sort(d.begin(), d.end(), greater<Pll>());

    bool ok = true;

    ll cur = 0;
    for (auto [m, d] : b) {
        if (cur + m < 0) {
            ok = false;
            break;
        }
        cur += d;
    }

    if (!c.empty()) {
        if (cur + c[0].first < 0) {
            ok = false;
        }
    }

    cur = 0;
    for (auto [m, d] : d) {
        if (cur + m < 0) {
            ok = false;
            break;
        }
        cur += d;
    }

    cout << (ok ? "Yes\n" : "No\n");
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 19048
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	string s;
	cin >> s;
	int start = -1, finish = 0;
	REP(i, s.size()) {
		if (s[i] == 'A'&&start==-1) {
			start = i;
		}
		if (s[i] == 'Z'&&i>finish) {
			finish = i;
		}
	}
	cout << finish - start + 1 << endl;
	return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 510, mo = 1000000007 ;
using namespace std ;

int n, m, col, e, ter[N], nxt[N], lnk[N], id[N], cnt, top, ans, d[N] ;
bool vis[N], ins[N], h[N] ;
int dfn[N], low[N], st[N] ;
struct edge {
	int x, y ; 
} E[N] ;

int gcd(int x, int y) {
	return (y ? gcd(y, x % y) : x) ;
}

void add(int x, int y, int z) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e, id[e] = z ;
}

inline int INP(int x) {
	if (!h[x]) {
		h[x] = true ;
		d[++ d[0]] = x ;
		return 1 ;
	}
	return 0 ;
}

inline void OUP() {
	rep(i, 1, d[0]) {
		h[d[i]] = false ;
	}
}

inline int mul(int a, int b) {
	int ans = 1, w = a % mo ;
	for ( ; b; b /= 2) {
		if (b & 1) ans = (ll) ans * w % mo ;
		w = (ll) w * w % mo ;
	}
	return ans ;
} 

inline int calc_cir(int x) {
	int res = 0 ; 
	rep(i, 0, x - 1) {
		res = (res + mul(col, gcd(i, x))) % mo ;
	}
	res = (ll) res * mul(x, mo - 2) % mo ;
	return res ;
}

inline int C(int x, int y) {
	int res = 1 ;
	rep(i, 2, x) res = (ll) res * i % mo ;
	rep(i, 2, y) res = (ll) res * mul(i, mo - 2) % mo ;
	rep(i, 2, x - y) res = (ll) res * mul(i, mo - 2) % mo ;
	return res ;
}

inline int calc_u(int x) {
	return C(col + x - 1, col - 1) ;
}

void dfs(int p, int las) {
	dfn[p] = low[p] = ++ cnt ;
	for (int i = lnk[p]; i; i = nxt[i]) {
		if (!dfn[ter[i]]) {
			st[++ top] = id[i], ins[id[i]] = true, vis[id[i]] = false ;
			dfs(ter[i], p) ;
			low[p] = min(low[p], low[ter[i]]) ;
			if (low[ter[i]] >= dfn[p]) {
				int poi = 0, ed = 0 ;
				d[0] = 0 ;
				for ( ; ; ) {
					poi += INP(E[st[top]].x) ;
					poi += INP(E[st[top]].y) ;
					++ ed ;
					ins[st[top]] = false ;
					-- top ;
					if (st[top + 1] == id[i]) break ;
				}
				OUP() ;
				if (poi == ed) ans = (ll) ans * calc_cir(ed) % mo ;
					else ans = (ll) ans * calc_u(ed) % mo ;
			}
		} else {
			if (vis[id[i]]) {
				vis[id[i]] = false ;
				st[++ top] = id[i] ;
				ins[id[i]] = true ;
			}
			low[p] = min(low[p], dfn[ter[i]]) ;
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &col) ;
	int x, y ;
	rep(i, 1, m) {
		scanf("%d%d", &x, &y) ;
		add(x, y, i), add(y, x, i) ;
		E[i].x = x, E[i].y = y ;
	}
	memset(vis, true, sizeof(vis)) ;
	memset(ins, false, sizeof(ins)) ;
	ans = 1 ;
	cnt = top = 0 ;
	rep(i, 1, n) if (!dfn[i]) {
		dfs(i, 0) ;
	}
	printf("%d\n", (ans + mo) % mo) ;
	return 0 ; 
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    string s;
    int n,c=1;
    cin>>n>>s;
    if(n&1)
        c=0;
    for(int i=0;i<n/2;i++)
        if(s[i]!=s[n/2+i]){
            c=0;break;}
    if(c==1 && n!=1)
        cout<<"Yes";
    else cout<<"No";
}


Measured memory_bytes: 256
def calcs(x,y,ax,ay,bx,by) ((ax-x)*(by-y)-(bx-x)*(ay-y))/2.0 end
def inpf() a=gets.chomp.split(" ").map(&:to_f)end
def inps() a=gets.chomp.split(" ")end  
def copy(a) Marshal.load(Marshal.dump(a)) end
def factorial(n)(n < 2)? 1 : (2..n).inject(:*) end
def scount(a) b=na(a.max+1);a.each{|n|b[n]+=1};return b end
def na(n,d=0) Array.new(n,d)end
def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end
def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end
def bit(n) n.to_s(2).split("").map(&:to_i) end
def inp() a=gets.chomp.split(" ").map(&:to_i)end
class Uf
  def initialize(n)
    @r = na(n+1)
    @a = (0...n).to_a
  end
  def uf(x)
    return x if (@a[x] == x)
    @a[x] = uf(@a[x])
  end
  def add(x,p)
    root  = uf(x)
    connect  = uf(p)
    return if root == connect
    if @r[root] > @r[connect]
      @a[connect] = root
    elsif @r[root] == @r[connect]
      @a[connect] = root
      @r[root] += 1
    else
      @a[root] = connect
    end
  end
  def ufj(x,p)
    return uf(x) == uf(p) 
  end
end
n,m = inp
p = inp
t=[]
m.times do
  t.push(inp)
end
uf = Uf.new(n+1)
t.each do |tt|
  uf.add(tt[0],tt[1])
end
ans = 0
i = 0
p.each do |d|
  i+=1
  ans+=1 if uf.ufj(d,i)
end
 p ans

Measured memory_bytes: 19548
hws = []
while True:
    hw = list(map(int,input().split()[:2]))
    if hw[0] == hw[1] == 0:
        break
    hws.append(hw)

for hw in hws:
    for height in range(hw[0]):
        for width in range(hw[1]):
            print('#',end='')
        print()
    print()


Measured memory_bytes: 7008
#include <iostream>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL n;
    cin >> n;
    vector<vector<LL>> a_bin(n+1,vector<LL>(20, 0));
    vector<LL> a(n);
    for(LL i=0; i<n; i++){
        cin >> a[i];
    }
    LL tmp;
    for(LL i=1; i<=n; i++){
        tmp=a[i-1];
        for(LL j=0; j<20; j++){
            a_bin[i][j]=tmp%2;
            a_bin[i][j]+=a_bin[i-1][j];
            tmp/=2;
        }
    }

    LL end_point=1;
    LL ans=0;
    for(LL i=0; i<=n; i++){
        while(true){
            bool is_ok=true;
            for(LL j=0; j<20; j++){
                if(a_bin[end_point][j]-a_bin[i][j]>1){
                    is_ok=false;
                }
            }
            //cout << is_ok << " " << i << " " << end_point << endl;
            if(is_ok==false){
                ans+=(end_point-1-i);
                //cout << ans << endl;
                //if(end_point==n){
                //    ans+=1;
                //}
                //cout << ans << endl;
                break;
            }else if(end_point==n){
                ans+=end_point-i;
                //cout << ans << endl;
                break;
            }else{
                end_point++;
            }
        }
        //if(end_point>n){
        //    break;
        //}            
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 43876
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
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; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main(){
    int N;cin >> N;
    int C;cin >> C;
    vector<vector<int>> D(C,vector<int>(C,0));
    vector<vector<int>> c(N,vector<int>(N,0));

    rep(i,C)rep(j,C)cin >> D[i][j];
    rep(i,N)rep(j,N)cin >> c[i][j],c[i][j]--;

    // 前処理
    vector<vector<int>> sum(3,vector<int>(C,0));
    rep(k,C)rep(i,N)rep(j,N)sum[(i+j)%3][k] += D[c[i][j]][k];

    // クエリ
    LL ans = INF;
    rep(i,C)rep(j,C)rep(k,C){
        LL tmp = 0;
        if(i == j)continue;
        if(i == k)continue;
        if(j == k)continue;
        tmp += sum[0][i] + sum[1][j] + sum[2][k];
        ans = min(ans,tmp);
    }

    cout << ans << endl;


}



Measured memory_bytes: 1280
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>

using namespace std;

template<typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}

int Parity(const vector<int> &a, const vector<int>& deg2, int n) {
  int result = 0;
  for (int i = 0; i < n; ++i) {
    int nomD3 = deg2[n - 1];
    int denD3 = deg2[i] + deg2[n - 1 - i];
    
    assert(nomD3 >= denD3);

    if (nomD3 > denD3) {
      continue;
    }

    result = (result + a[i]) % 2;
  }

  return result;
}

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    char c;
    do { 
      scanf("%c", &c);
    } while (!isdigit(c));
    a[i] = c - '0';
    a[i]--;
  }

  vector<int> deg2(n);

  for (int i = 1; i < n; ++i) {
    deg2[i] = deg2[i - 1];
    int tmp = i;
    while (tmp % 2 == 0) {
      deg2[i]++;
      tmp /= 2;
    }
  }

  if (Parity(a, deg2, n) == 1) {
    cout << 1 << endl;
    return 0;
  }

  bool haveOne = false;
  for (int x : a) {
    if (x == 1) {
      haveOne = true;
    }
  }

  if (haveOne) {
    cout << 0 << endl;
    return 0;
  }

  for (int i = 0; i < n; ++i) {
    a[i] /= 2;
  }

  cout << Parity(a, deg2, n) * 2 << endl;

  return 0;
}


Measured memory_bytes: 8064