akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 虫の目、一個ずつheapへ
X, Y, Z, K = lr()
A = lr(); A.sort(reverse=True)
B = lr(); B.sort(reverse=True)
C = lr(); C.sort(reverse=True)

ma = A[0] + B[0] + C[0]
heap = [(-ma, (0, 0, 0))]
used = set()
for _ in range(K):
    result, place = heappop(heap)
    print(-result)
    i, j, k = place
    p = (i+1, j, k)
    if i + 1 < len(A) and p not in used:
        val = A[i+1] + B[j] + C[k]
        used.add(p)
        heappush(heap, (-val, p))
    p = (i, j+1, k)
    if j + 1 < len(B) and p not in used:
        val = A[i] + B[j+1] + C[k]
        used.add(p)
        heappush(heap, (-val, p))
    p = (i, j, k+1)
    if k + 1 < len(C) and p not in used:
        val = A[i] + B[j] + C[k+1]
        used.add(p)
        heappush(heap, (-val, p))

# 26


Measured memory_bytes: 4840
n,k=map(int,input().split())
l=list(map(int,input().split()))
tmp=0
for i in range(1,n):
    if l[i-1]+l[i]>=k:
        tmp=i
        break
if tmp==0:
    print("Impossible")
else:
    print("Possible")
    for i in range(1,tmp):
        print(i)
    for i in range(n-1,tmp,-1):
        print(i)
    print(tmp)

Measured memory_bytes: 14060
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include<climits>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

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


int N,T,A,H[1010];
int ans,i, j;
int main(){
    scanf("%d%d%d",&N,&T,&A);
    fornum(i,0,N){
        scanf("%d", &H[i]);
    }
    float min=1000000;
    fornum(i,0,N){
        float t = (float)T-(float)H[i] * 0.006;
        t = (t < A) ? A - t : t - A;
        if(t<min){
            min = t;
            ans = i;
        }
    }
    printf("%d\n", ans + 1);

    return 0;
}

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

void solve() {
	map<char, int> alphabets;
	string s; cin >> s;

	rep(i, s.size()) {
		alphabets[s[i]]++;
	}

	bool beautiful = true;
	for (auto & it : alphabets) {
		if (it.second % 2 != 0) {
			beautiful = false;
			break;
		}
	}

	cout << (beautiful ? "Yes" : "No") << endl;

}

int main(void) {
	solve();
	return 0;
}

Measured memory_bytes: 256
#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)
//#define int long long

vector<long long> binomial_coefficient(long long N){
    const long long MOD = 998244353;
    vector<long long> fac;
    vector<long long> facIE;
    vector<long long> comb;
    for(int i=0;i<=N;i++){
        if(i==0){
            fac.push_back(1);
        }else{
            fac.push_back(i*fac[i-1]%MOD);
        }
    }
    for(int i=0;i<=N;i++){
        long long r=1,b=fac[i],e=MOD-2;
        while(e){
            if(e&1){
                r=(r*b)%MOD;
            }
            b=(b*b)%MOD;
            e >>=1;
        }
        facIE.push_back(r);
    }
    for(int i=0;i<=N;i++){
        long long r=fac[N];
        r = (r*facIE[i])%MOD;
        r = (r*facIE[N-i])%MOD;
        comb.push_back(r);
    }
    return comb;
}



signed main(void){
    long long N,A,B,K;
    cin >> N >> A >> B >> K;
    vector<long long> nC;
    nC = binomial_coefficient(N);
    
    const long long MOD = 998244353;
    long long Ans=0;
    
    //REP(i,N+1){cout << nC[i] << " ";}cout << endl;
    
    REP(i,N+1){
        long long b=K-A*i;
        if(b>=0 && b%B==0 && b/B<=N){
            b/=B;
            Ans+=nC[i]*nC[b];
            Ans%=MOD;
        }
    }
    cout << Ans << endl;
    return 0;
}


Measured memory_bytes: 15084
//copied
#include <bits/stdc++.h>
int n, Li[1005], Mv[5005], Sum;
std::vector<int> g[1005];
std::bitset<5005> v;

int main() {
	scanf("%d", &n);
	for (int i = 2, u; i <= n; ++i)
		scanf("%d", &u), g[u].push_back(i);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &Li[i]);
	for (int i, x = n; x >= 1; --x) {
		v = 1, Sum = 0;
		for (int y : g[x])
			v = (v << Li[y]) | (v << Mv[y]), Sum += Li[y] + Mv[y];
		for (i = Li[x]; i >= 0 && !v[i]; --i)
			;
		std::string mystring = v.to_string<char, std::string::traits_type,
				std::string::allocator_type>();

//		std::cout << x << ' ' << i << ": " << mystring << ' '<<Li[x] << ' ' << Mv[x]
//				<< '\n';
		if (i == -1)
			return puts("IMPOSSIBLE"), 0;
		Mv[x] = Sum - i;
	}
	return puts("POSSIBLE"), 0;
}


Measured memory_bytes: 3728
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
 
int N;
int a[222222];
 
signed main(){
    cin>>N;
    rep(i,N)cin>>a[i];
 
    stack<int>S;
    int cnt=0;
    rep(i,N){
        while(S.size()&&S.top()>a[i])S.pop();
        if(S.size()&&S.top()==a[i])continue;
        S.push(a[i]);cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 5900
#include<bits/stdc++.h>
using namespace std;
int n,k;
double pw[100001],win;
int main()
{
	cin>>n>>k;
	pw[0]=1;
	for(int i=1;i<=n;i++)pw[i]=pw[i-1]*0.5;
	for(int i=1;i<=n;i++)
	{
		double pi=1.0/n;
		int cur=i;
		while(cur<k)cur*=2,pi*=0.5;
		win+=pi;
	}
	printf("%.10lf",win);
}

Measured memory_bytes: 1024
import numpy as np
H,W,K=map(int, input().split())
now=0
S=[]
for i in range(H):
    s=list(input())
    S.append(s)
ans=[[0]*W for _ in range(H)]
ans=np.array(ans)

for i in range(H):
    noberry=(not "#" in S[i])
    if not noberry:
        now+=1
    berrys=0
    for j in range(W):
        if noberry and i==H-1:
            ans[i,j]=ans[i-1,j]
            continue
        if noberry and i>=1 and (ans[i-1,:]).sum()!=0:
            ans[i,j]=ans[i-1,j]
            continue
    
        if not noberry:
            
            if S[i][j]==".":
                ans[i,j]=now
            else:
                berrys+=1
                if berrys>=2:
                    now+=1
                    ans[i,j]=now
            ans[:i+1,j][ans[:i+1,j]==0]=now
for a in ans:
    print(*a)


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

extern inline unsigned int xor128(void){
  static unsigned int x=123456789,y=362436069,z=521288629,w=88675123; 
  unsigned int t=x^(x<<11);
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8)); 
}

template <typename T>
class Treap{
public:
  Treap* l;
  Treap* r;
  int cnt;
  int pri;
  T value;
  Treap(){
  }
  Treap(T v){
    value=v;
    cnt=1;
    pri=xor128();
    l=r=NULL;
  }
};

template <typename T >
class Vectree{
private:

  int count(Treap<T>* t){ return !t ? 0:t->cnt; }

  Treap<T>* update(Treap<T>* t){
    t->cnt = count(t->l) + count(t->r) + 1;
    return t;
  }

  
  Treap<T>* merge(Treap<T>* l,Treap<T>* r){
    if( !l || !r ) return !l ? r : l;
    if( l->pri > r ->pri ){
      l->r = merge(l->r,r);
      return update(l);
    } else {
      r->l = merge(l,r->l);
      return update(r);
    }
  }

  typedef pair< Treap<T>* , Treap<T>* > pnn;
  pnn split(Treap<T>* t,int k){
    if( !t ) return pnn(NULL,NULL);
    if( k <= count(t->l) ){
      pnn s = split(t->l,k);
      t->l = s.second;
      return make_pair(s.first,update(t));
    } else {
      pnn s = split(t->r,k - count(t->l) - 1);
      t->r = s.first;
      return make_pair(update(t),s.second);
    }
  }
  
  int size_num;
  Treap<T> *root;
public:
  Vectree(){
    size_num=0;
    root=NULL;
  }
  
  int size();

  void push_back(T);
  void pop_back();
  void insert(int,T);
  void erase(int);

  void resize(int,T);
  void clear();
  
  T& operator [] (int x);
};


template <typename T>
int Vectree <T> :: size(){
  return size_num;
}



template <typename T>
void Vectree <T> :: erase(int index){
  auto p=split( root, index + 1 );
  auto q=split( p.first, index);
  root = merge(q.first,p.second);
  size_num--;
}

template <typename T>
void Vectree <T> :: insert(int index,T v){
  auto p=split( root, index );

  p.first = merge( p.first, new Treap<T>(v) );

  root = merge( p.first, p.second );
  size_num++;
}

template <typename T>
void Vectree <T> :: push_back(T v){
  insert( size_num, v );
}

template <typename T>
void Vectree <T> :: pop_back(){
  erase( size_num );
}

template <typename T>
void Vectree <T> :: resize(int n,T v){
  while( size() < n ){
    insert(0,v);
  }
}

template <typename T>
void Vectree <T> :: clear(){
  while( size() > 0 ){
    erase(0);
  }
}


template <typename T>
T& Vectree<T> :: operator [] (int x){
  auto p=split(root,x);
  auto q=split(p.second,1);
  root=merge(p.first, merge(q.first,q.second) );
  return q.first->value;
}


int main(){
  Vectree<int> t;


  int n;
  cin>>n;

  t.resize(n,0);
  
  for(int i=0;i<n;i++){
    cin>> t[i];
  }

  int ans=0;
  int m;
  cin>>m;
  
  for(int i=0;i<m;i++){
    int a;
    cin>>a;
    for(int j=0;j<n;j++)
      if(t[j]==a){
        ans++;
        break;
      }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3512
use std::io;

fn read_line() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s
}

macro_rules! from_line {
    ($($a:ident : $t:ty),+) => {
        $(let $a: $t;)+
        {
            let _line = read_line();
            let mut _it = _line.trim().split_whitespace();
            $($a = _it.next().unwrap().parse().unwrap();)+
                assert!(_it.next().is_none());
        }
    };
}

fn main() {
    let mut ret = false;
    from_line!(a: i32, b: i32, c: i32, d: i32);
    if (a - c).abs() <= d {
        ret = true;
    }
    else if (a - b).abs() <= d && (b - c).abs() <= d {
        ret = true;
    }
    else {
        ret = false;
    }
    if ret {
        println!("Yes");
    }
    else {
        println!("No");
    }
}


Measured memory_bytes: 4352
inpt = input().split(" ")

maxNum = inpt[0]

dislike = input().split(" ")
dislike = [int(a) for a in dislike]

likeArray = []

for i in range(0,10):
    if not i in dislike:
        likeArray.append(i)

ans = ""
flag = False
for c in maxNum:
    if flag :
        ans += str(min(likeArray))
    else:
        if int(c) in likeArray:
            ans += c
        elif len([a for a in likeArray if a > int(c)])>0:
            ans += str(min([a for a in likeArray if a > int(c)]))
            flag = True
        else:
            ans = str(min([a for a in likeArray if a > 0]))
            for i in range(0, len(maxNum)):
                ans += str(min(likeArray))
            break    
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 9999999999;
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
  T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }


int main() {
  int n,h; cin >>n >>h;
  vector<ll> attack(n),throws(n);
  rep(i, n) cin >>attack.at(i) >>throws.at(i);
  ll attackmax = 0;
  rep(i, n) chmax(attackmax, attack.at(i));
  vector<ll> throwThanAttackmax;
  rep(i, n) if (throws.at(i) > attackmax) throwThanAttackmax.push_back(throws.at(i));
  sort(all(throwThanAttackmax));
  reverse(all(throwThanAttackmax));

  int ans = 0;
  for (int i=0; i<throwThanAttackmax.size(); i++){
    h -= throwThanAttackmax.at(i);
    ans++;
    if (h <= 0) break;
  }
  if (h > 0) ans += (h + attackmax - 1) / attackmax;

  cout <<ans <<endl;
}

Measured memory_bytes: 2936
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
    ll a;
    cin>>a;
    int ans=0;
    ll r =100;
    while(r<a){
        r*=1.01;
        ans++;
    }
    cout<<ans<<endl;
    }

Measured memory_bytes: 3632
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
using namespace std;

const int mod=1000000007;
const int N=500005;

struct E{
	int to,next;
}mem[N<<1];
int n,num,fa,ans,cnt,m,top;
int f[N][19],p[N],dp[N][2],head[N],dfn[N],dep[N],q[N],st[N],b[2][3],tag[N];
vector<int> ped[N],lev[N];

int quickpow(int x,int y){
	int s=1;
	for (;y;y>>=1,x=1ll*x*x%mod)
		if (y&1) s=1ll*s*x%mod;
	return s;
}

void add(int x,int y){
	num++;
	mem[num].to=y; mem[num].next=head[x];
	head[x]=num;
}

void dfs1(int k,int pre){
	int u,j;
	dfn[k]=++cnt;
	for (j=head[k];j;j=mem[j].next){
		u=mem[j].to;
		if (u==pre) continue;
		dep[u]=dep[k]+1;
		dfs1(u,k);
	}
}

bool cmp(int a,int b){
	return dfn[a]<dfn[b];
}

int lca(int x,int y){
	int i;
	if (dep[x]<dep[y]) swap(x,y);
	for (i=18;i>=0;i--)
		if (dep[x]-dep[y]>=(1<<i)) x=f[x][i];
	if (x==y) return x;
	for (i=18;i>=0;i--)
		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

void init(){
	int i,j;
	for (i=1;i<=18;i++)
		for (j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];
}

void dfs2(int k,int pre){
	int u,j,now,last;
	if (!lev[k].size()){
		dp[k][0]=1;
		dp[k][1]=tag[k];
		return;
	}
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (u==pre) continue;
		dfs2(u,k);
	}
	now=0; last=1;
	b[0][0]=1; b[0][1]=tag[k]; b[0][2]=0;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (u==pre) continue;
		now^=1; last^=1;
		memset(b[now],0,sizeof(b[now]));
		b[now][2]=(1ll*b[last][1]*dp[u][1]%mod+1ll*b[last][2]*(dp[u][0]+dp[u][1])%mod)%mod;
		b[now][1]=(1ll*b[last][0]*dp[u][1]%mod+1ll*b[last][1]*dp[u][0]%mod)%mod;
		b[now][0]= 1ll*b[last][0]*dp[u][0]%mod;
	}
	dp[k][0]=(b[now][0]+b[now][2])%mod;
	dp[k][1]=b[now][1];
}

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int i,j,k;
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%d",&f[i][0]);
		add(f[i][0],i);
	}
	dfs1(0,-1);
	init();
	ans=quickpow(2,n);
	for (i=1;i<=n;i++) ped[dep[i]].push_back(i);
	for (i=1;i<=n;i++){
		cnt=0; m=0;
		for (j=0;j<ped[i].size();j++) p[++cnt]=ped[i][j];
		if (!cnt) break;
		sort(p+1,p+1+cnt,cmp);
		st[top=1]=0; q[++m]=0;
		for (j=1;j<=cnt;j++){
			fa=lca(p[j],st[top]);
			while (dep[st[top]]>dep[fa]){
				if (dep[st[top-1]]<dep[fa]){
					lev[fa].push_back(st[top]),st[top]=fa;
					q[++m]=fa;
				}
				else{
					lev[st[top-1]].push_back(st[top]);
					top--;
				}
			}
			if (st[top]!=p[j]){
				st[++top]=p[j];
				q[++m]=p[j];
			}
		}
		for (j=1;j<=cnt;j++) tag[p[j]]=1;
		while (--top) lev[st[top]].push_back(st[top+1]);
		dfs2(0,-1);
		ans=(ans+1ll*dp[0][1]*quickpow(2,n-cnt+1)%mod)%mod;
		for (j=1;j<=m;j++) lev[q[j]].clear(),dp[q[j]][0]=dp[q[j]][1]=0;
		for (j=1;j<=cnt;j++) tag[p[j]]=0;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 73216
#include <bits/stdc++.h>
using namespace std;
// int facctorialMethod(int k){
//     int sum = 1;
//     for (int i = 1; i <= k; ++i)
//     {
//         sum *= i;
//     }
//     return sum;
// }
int main(){
    int s,w;
    cin >> s >> w;
    if(s>w){
        cout << "safe" << endl;
    }
    else{
        cout << "unsafe" << endl;
    }
}

Measured memory_bytes: 3608
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int ans = 0;
        List<List<Integer>> sl = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; i++){
            sl.add(new ArrayList<Integer>());
        }
        int[] p = new int[m];
        for(int i = 0; i < m; i++){
            int k = sc.nextInt();
            for(int j = 0; j < k; j++){
                sl.get(sc.nextInt()-1).add(i);
            }
        }
        for(int i = 0; i < m; i++){
            p[i] = sc.nextInt();
        }
        int loops = (int)Math.pow(2,n);
        for(int i = 0; i < loops; i++){
            int[] tp = new int[m]; 
            for(int j = 0; j < n; j++){
                if(((i >> j) % 2) == 1){
                    List<Integer> tmp = sl.get(j);
                    for(int v:tmp){
                        tp[v]++;
                    }
                }
            }
            boolean bool = true;
            for(int j = 0; j < m; j++){
                if(tp[j]%2 != p[j]){
                    bool = false;
                    break;
                }
            }
            if(bool){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23764
/*input
6
0 6 7 6 7 0
*/
#include <bits/stdc++.h>
#define getcx getchar_unlocked
#define putcx putchar_unlocked
#define pb(x) push_back(x);
#define in(y) insert(y);
#define tt(t) while(t--)
#define itr ::iterator it;
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=a;i<(b);i++)
#define ff(n) for(int i=0;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define LLINF LLONG_MAX
using namespace std;
#define M 1000000007
#define pi acos(-1)

int main()
{
    int n;
    cin >> n;
    vi a(n),b;
    ff(n) cin>>a[i];

    if(n%2==0){
        vi ss,bs;
        for(int i=1;i<n;i+=2) ss.pb(a[i]);

        reverse(all(ss));

        for(int i=0;i<n;i+=2) bs.pb(a[i]);

        //reverse(all(bs));
        for(auto i:ss) cout<<i<<" ";

        for(auto i:bs) cout<<i<<" ";

    }
    else{
        vi ss,bs;
        for(int i=1;i<n;i+=2) ss.pb(a[i]);

        

        for(int i=0;i<n;i+=2) bs.pb(a[i]);
            reverse(all(bs));
        //reverse(all(bs));
        for(auto i:bs) cout<<i<<" ";

        for(auto i:ss) cout<<i<<" ";

    }
}


Measured memory_bytes: 3832
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

class Solution {
public:
    int solve(vector<int>& A) {
        int n = A.size();
        int res = 0;
        for (int i = n - 1; i >= 0; --i) {
            int cnt = 0;
            while (i - 1 >= 0 && A[i - 1] >= A[i]) {
                ++cnt;
                --i;
            }
            res = max(res, cnt);
        }
        return res;
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    Solution sol;
    cout << sol.solve(A) << "\n";

    return 0;
}

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

int main(int argc, char const *argv[])
{
  char c, x; cin >> c;
  cin >> x; if(c==x) {
    cout << "Bad" << endl;
    return 0;
  }
  c=x;
  cin >> x; if(c==x) {
    cout << "Bad" << endl;
    return 0;
  }
  c=x;
  cin >> x; if(c==x) {
    cout << "Bad" << endl;
    return 0;
  }
  cout << "Good" << endl;
  return 0;
}





Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include "queue"
#include <deque>
#include <stack>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include "fstream"
using namespace std;
#define PI acos(-1)
#define MOD 1000000007
#define pii pair<long long ,long long >
#define ll  long long int
#define loop(i,n) for(ll i=0;i<n;i++)
#define loop2(i,n) for(ll i = 1;i<=n;i+=1)
#define pb push_back
#define EPS 1e-8
inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
using namespace std;





int main()
{
//    freopen("/Users/ashish/Desktop/manic_moving.txt", "r", stdin);
//    freopen("/Users/ashish/Desktop/A-large-practice.out.txt", "w", stdout);
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll ans  = 0 ;
    ll curr = 0 ;
    loop(i,s.length())
    {
        if(s[i]=='I')
        {
            curr+=1;
            ans = max(ans,curr);
        }
        else{
            curr-=1;
            ans= max(ans,curr);
        }
    }
    cout<<ans<<endl;
    
    
    
    
    return 0;
}

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

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def check(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-1-i]:
            return False
    return True

def main():
    ans = 0
    n = ri()
    for i in range(1,n+1):
        if i%3 == 0 or i%5 == 0:
            continue
        ans += i
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long a, b, k;
	cin >> a >> b >> k;
	if (a > k)
		a -= k;
	else
 		b -= (k - a), a = 0;
	if (b < 0)
		b = 0;
	cout << a << ' ' << b << '\n';
  return 0;
}



Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getArray(N)
s = sorted(A)
alta = {}
for i in range(N):
    alta[s[i]] = i
A = [alta[i] for i in A]

"""
N <= 100000
O(NlogN)まで
1つとばし交換をたくさん行う
隣接とばしの最小回数は
N = 4
A = [2, 4, 3, 1]の場合最終形は
A = [1, 2, 3, 4]
バブルソートの交換回数
1, 2, 3の自分より左にある自分より大きいものの数

1, 3, 5...番目にあるものは1, 3, 5...番目にしかいけない
いくつ路線を変える必要があるか
"""

def counter(array):
    n = len(array)
    cnt = 0
    for i in range(n):
        if (array[i] % 2) ^ (i % 2):
            cnt += 1
    return cnt

print(counter(A) // 2)

Measured memory_bytes: 26308
N,M = map(int, input().split())
S=[list(map(int, input().split())) for _ in range(N)]
C=[list(map(int, input().split())) for _ in range(M)]
import sys
for st in S:
  n=-1
  z= sys.maxsize
  j=0
  for ch in C:
    mi = abs(st[0] - ch[0]) + abs(st[1] - ch[1])
    j+=1
    #print(z)
    if z > mi:
      z = mi
      n = j
  print(n)
      
    
  

Measured memory_bytes: 3064
char c[3];
int main(){
  c[0]=getchar();
  getchar();
  getchar();
  getchar();
  getchar();
  c[1]=getchar();
  getchar();
  getchar();
  getchar();
  getchar();
  c[2]=getchar();
  putchar(c[0]);
  putchar(c[1]);
  putchar(c[2]);
  putchar(10);
}


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

int main()
{
    std::ios_base::sync_with_stdio(0);
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    if (n%2 == 0 && std::equal(s.begin(), s.begin()+n/2, s.begin()+n/2)) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    return 0;
}

Measured memory_bytes: 256
alphabet = [chr(ord('a') + i) for i in range(26)]
s = list(input())
s = sorted(list(set(s)))
if len(s) == 26:
    print("None")
    exit()
for i in range(len(s)):
    if s[i] == alphabet[i]:
        pass
    else:
        print(alphabet[i])
        exit()
print(alphabet[i+1])
exit()

Measured memory_bytes: 3956
/* Coached by rainboy */
#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

long long fac(int n) {
	return n == 0 ? 1 : (fac(n - 1) * n) % MOD;
}

int main() {
	int n, m;

	scanf("%d%d", &n, &m);
	printf("%lld\n", abs(n - m) > 1 ? 0 : (fac(n) * fac(m) * (n == m ? 2 : 1)) % MOD);
	return 0;
}


Measured memory_bytes: 1664
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<time.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define INF ((1<<30)-1+(1<<30))
#define INFLL (1LL << 60)
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(n); ++i)
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; }




int main()
{
	int N, M, K; cin >> N >> M >> K;
	vector<ll> A(N + 1, 0);
	vector<ll> B(M + 1, 0);
	rep(i, N) {
		int a; cin >> a;
		A[i + 1] = A[i] + a;
	}
	rep(i, M) {
		int b; cin >> b;
			B[i + 1] = B[i] + b;
	}
	int iA = upper_bound(A.begin(), A.end(), K) - A.begin() - 1;
	int iB = upper_bound(B.begin(), B.end(), K) - B.begin() - 1;

	int ans = 0;
	int ib = 1;
	ll tm = A[iA];
	for (int ia = iA; ia >= 0; --ia) {
		while (ib <= iB && tm + B[ib] - B[ib - 1] <= K) {
			tm = tm + B[ib] - B[ib - 1];
			++ib;
		}
		ans = max(ans, ia + ib - 1);
		if (ia) tm = tm - A[ia] + A[ia - 1];
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 5936
object Main {
  def main(args: Array[String]): Unit = {
    solve
  }

  def solve(): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt()
    val x = sc.nextLong()

    val a = new Array[Long](n + 1)
    val p = new Array[Long](n + 1)
    a(0) = 1
    p(0) = 1
    for (i <- 1 until n + 1) {
      a(i) = 2 * a(i - 1) + 3
      p(i) = 2 * p(i - 1) + 1
    }

    def f(n: Int, x: Long): Long = {
      if (n == 0) {
        if (x == 0) 0L else 1L
      } else if (x == 1) {
        0L
      } else if (1 < x && x <= 1 + a(n - 1)) {
        f(n - 1, x - 1)
      } else if (x == 2 + a(n - 1)) {
        p(n - 1) + 1
      } else if (2 + a(n - 1) < x && x <= 2 + 2 * a(n - 1)) {
        p(n - 1) + 1 + f(n - 1, x - 2 - a(n - 1))
      } else {
        2 * p(n - 1) + 1
      }
    }

    println(f(n, x))

  }
}


Measured memory_bytes: 27204
package main

import (
	"fmt"
)

func main() {
	var n, m, s int
	fmt.Scan(&n, &m)
	for k := 0; k <= n; k++ {
		v := ModCombination(n, k)
		v = v * ModPermutation(m, k) % Mod
		v = v * ModPermutation(m-k, n-k) % Mod
		v = v * ModPermutation(m-k, n-k) % Mod
		if k%2 == 1 {
			v = Mod - v
		}
		s = (s + v) % Mod
	}
	fmt.Println(s)
}

const Mod = int(1e9) + 7

func ModPermutation(n, r int) int { return fac[n] * finv[n-r] % Mod }
func ModCombination(n, k int) int { return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod }

var fac, finv, inv []int

func init() {
	const MAX = 5 * 1e5
	fac, finv, inv = make([]int, MAX+1), make([]int, MAX+1), make([]int, MAX+1)
	fac[0], fac[1], finv[0], finv[1], inv[1] = 1, 1, 1, 1, 1
	for i := 2; i <= MAX; i++ {
		fac[i] = fac[i-1] * i % Mod
		inv[i] = Mod - inv[Mod%i]*(Mod/i)%Mod
		finv[i] = finv[i-1] * inv[i] % Mod
	}
}


Measured memory_bytes: 14016
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
queue<int> q;
set<int> s;

int main() {
    int n,m;cin >> n >> m;
    vector<vector<int>> p(n);
    vector<set<int>> ps(n);
    for(int i = 0; i < m; i++) {
        int a,b;cin >> a >> b;
        a--;b--;
        if(!ps[a].count(b)){
            p[a].push_back(b);
            ps[a].insert(b);
        }
        if(!ps[b].count(a)){
            p[b].push_back(a);
            ps[b].insert(a);
        }
    }
    
    for(int i = 0; i < n; i++) {
        s.insert(i);
    }
    int ans=0;
    while(!s.empty()){
        int x=*begin(s);
        s.erase(x);
        int e=1;
        for(int i = 0; i < p[x].size(); i++) {
            if(s.count(p.at(x).at(i))){
                q.push(p.at(x).at(i));
                s.erase(p.at(x).at(i));
            }
        }
        while(!q.empty()){
            int y=q.front();
            q.pop();
            if(s.count(y)){
            s.erase(y);
            }
            e++;
            for(int i = 0; i < p[y].size(); i++) {
                if(s.count(p.at(y).at(i))){
                    q.push(p.at(y).at(i));
                    s.erase(p.at(y).at(i));
                }
            }
        }
        ans = max(ans,e);
    }
    cout << ans << endl;
}


Measured memory_bytes: 51816
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> a(H, vector<char>(W));
    rep(i, H) rep(j, W) cin >> a[i][j];
    
    vector<vector<int>> ans(H, vector<int>(W, 0));
    int c = 0;
    rep(i, H) rep(j, W) {
        if (a[i][j] == '#') {
            ++c;
            ans[i][j] = c;
        }
    }
    rep(k, H) rep(i, H - 1) rep(j, W) {
        if (ans[i][j] == 0) ans[i][j] = ans[i + 1][j];
    }
    rep(k, H) REP(i, H) rep(j, W) {
        if (ans[i][j] == 0) ans[i][j] = ans[i - 1][j];
    }
    rep(k, W) rep(i, H) rep(j, W - 1) {
        if (ans[i][j] == 0) ans[i][j] = ans[i][j + 1];
    }
    rep(k, H) rep(i, H) REP(j, W) {
        if (ans[i][j] == 0) ans[i][j] = ans[i][j - 1];
    }
    rep(i, H) rep(j, W) {
        cout << ans[i][j];
        if (j == W - 1) cout << endl;
        else cout << " ";
    }
    return 0;
}


Measured memory_bytes: 1280
#include <stdio.h>

int C[10001],D[10001];

int main()
{
  int n,i,basho=0;

  scanf("%d",&n);

  int A[n],B[n],maxA=0;

  for(i=0;i<n;i++)
    {
      scanf("%d",&A[i]);
      C[A[i]]++;
    }
  
  for(i=0;i<10001;i++)
    {
      basho+=C[i];
      D[i]=basho-1;
    }

  for(i=0;i<n;i++)
    {
      B[ D[A[i]] ]=A[i];
      D[A[i]]--;
    }

  for(i=0;i<n-1;i++)printf("%d ",B[i]);
  printf("%d\n",B[n-1]);

      
  return 0;
}



Measured memory_bytes: 17432
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define For(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
#define debug(x) cerr << x << endl
#define Complex complex<double>
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int main() {
    ll n,k;
    cin >> n >> k;
    ll sum=-(n+1)*(n+2)*(2*n+3)/6+(n+1)*(n+1)*(n+2)/2+(k-1)*k*(2*k-1)/6-(n+1)*(k-1)*k/2+n-k+2;
    sum%=mod;
    cout << sum;
    
}



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

typedef long long ll;

using namespace std;

const int mod = 998244353, maxn = 1*1000*1000+10, maxm = 500*1000+10;
ll f[maxn * 2], rf[maxn * 2], ans, tmp;
int n, m;

ll power(int a, int b, int m)
{
	if (b == 0)
		return 1 % m;
	ll c = power(a, b / 2, m);
	if (b & 1)
		return (((c * c) % m) * a) % m;
	return (c * c) % m;
}

ll c(int a, int b)
{
	if (a < b || a < 0 || b < 0)
		return 0;
	return (((f[a] * rf[b]) % mod) * rf[a - b]) % mod;
}

int main()
{
	cin >> n >> m;
	f[0] = rf[0] = 1;
	for (int i = 1; i < maxn * 2; i++)
	{
		f[i] = (f[i - 1] * i) % mod;
		rf[i] = power(f[i], mod - 2, mod);
	}
	for (int i = 0; i <= min(n, m); i++)
	{
		if ((m * 3 - i) & 1)
			continue;
		tmp = c(n, i);
		ans += tmp * c(n - 1 + (m * 3 - i) / 2, n - 1);
		ans %= mod;
		tmp *= n;
		tmp %= mod;
		tmp *= c(n - 2 + (m - i) / 2, n - 1);
		tmp %= mod;
		ans += mod - tmp;
		ans %= mod;
		tmp = c(n - 1, i - 1) * n;
		tmp %= mod;
		tmp *= c(n - 2 + (m - i) / 2, n - 2);
		tmp %= mod;
		ans += mod - tmp;
		ans %= mod;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 31488
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;
int main(){
	int n;
	
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++)		cin>>v[i];
	sort(v.begin(), v.end());
	float sum = v[0]+v[1];
	for (int i = 2; i < n; i++){
		sum += v[i] * pow(2, i - 1);
	}

	cout << sum / pow(2, n - 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    string s;
    cin >> s;
    bool flag = true;
    rep(i, 1, 3)
    {
        if (!(s[i] == s[i - 1]))
        {
            flag = false;
        }
    }
    if (flag)
    {
        Yes(0);
    }
    else
    {
        Yes(1);
    }
}

Measured memory_bytes: 256
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#include <bits/stdc++.h>   
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n;
string s;

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n >> s;
   for (int i = 0; i < sz (s); i ++) {
      int t = s[i] - 'A';
      t += n;
      if (t >= 26) t -= 26;
      cout << char (t + 'A');
   }
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 256
n,q = (int(i) for i in input().split())
s = input()
query = [0]*(n+1)
point = [0]*(n+1)
ct = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    ct += 1
    point[i] = -1 
  query[i+1] = ct
query[i+2] = ct  
#print(point)
    
for i in range(q):
  l,r = (int(i) for i in input().split())
  ans = query[r]-query[l-1]
  ans += point[r-1]
  print(ans)
 

Measured memory_bytes: 54616
n,m= gets.split.map(&:to_i)
array = gets.split.map(&:to_i)
array.sort!
divid = []
(m-1).times do |i|
  divid[i] = array[i+1] - array[i]
end
sum = 0
divid.sort!
if n>=m
  puts 0
elsif
  (m-n).times do |i|
    sum += divid[i]
  end
  puts sum
end


Measured memory_bytes: 9840
//56
#include<iostream>
#include<map>
#include<vector>
#include<string>

using namespace std;

string stob(string s){
  string r;
  for(int i=0;i<s.size();i++){
    string t[]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    for(int j=0;j<8;j++){
      if(t[j].find(s[i])!=string::npos){
	r+=j+2+'0';
      }
    }
  }
  return r;
}

map<string,vector<string> > m;

void dfs(string s,string t){
  if(s.empty()){
    cout<<t.substr(0,t.size()-1)<<'.'<<endl;
  }else{
    for(int i=0;i<s.size();i++){
      string k=s.substr(0,i+1);
      if(m.count(k)){
	for(int l=0;l<m[k].size();l++){
	  dfs(s.substr(i+1),t+m[k][l]+' ');
	}
      }
    }
  }
}

int main(){
  for(int n;cin>>n,n;){
    m.clear();
    while(n--){
      string s;
      cin>>s;
      m[stob(s)].push_back(s);
    }
    string d;
    cin>>d;
    dfs(d,"");
    cout<<"--"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1292
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def calc(p,x):
    return p*(100+x)//100


while True:
    r,n = inpl()
    if r == 0:
        break
    else:
        heights = defaultdict(int)
        ans = INF
        for _ in range(n):
            xl,xr,h = inpl()
            heights[xl+0.1] = max(heights[xl+0.1],h)
            heights[xr-0.1] = max(heights[xr-0.1],h)
            for x in range(xl+1,xr):
                heights[x-0.1] = max(heights[x-0.1],h)
                heights[x+0.1] = max(heights[x+0.1],h)

        for x in range(-23,23):
            h = min(heights[x-0.1],heights[x+0.1])
            #print(x,h)
            if r > abs(x):
                tmp = h - (r**2-x**2)**(1/2)
                ans = min(ans,tmp+r)
        print(ans)



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

int main() {
  int N;
  cin >> N;
  
  vector<int> H(N);
  for( int i = 0; i < N; i++ ){
    cin >> H.at(i);
  }
  
  for( int i = 0; i < N-1; i++ ){
    if( H.at(i) >= H.at(i+1) ){ //もし右のマスのほうが小さいか同じ大きさで
      if( H.at(i) - H.at(i+1) > 1 ){ //差が1以上だったら
        cout << "No" << endl;
        return 0;
      }else if( H.at(i) - H.at(i+1) == 1 ){ //差が1だったら
        H.at(i)--;
      }else if( H.at(i) == H.at(i+1) ){ //差が同じで
        if( i == 0 ) H.at(i)--;
        else{ // i!=0で
          if( H.at(i-1) != H.at(i) ){
            H.at(i)--;
          }
        }
      }
    }
  }
  
  for( int i = 0; i < N-1; i++ ){
    if( H.at(i) > H.at(i+1) ){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <iomanip>
#include <queue>
#include <deque>
#include <sstream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <map>
#include <utility>
using namespace std;

#define s(n) scanf("%d",&n)
#define sc(n) scanf("%c",&n)
#define ss(n) scanf("%s",&n)
#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795


int main() {
	string s;
	cin >> s;
	int n = s.length();
	for(int i = 2; i < n; i+= 2) {
		int plus = (n-i)/2;
		bool good = true;
		for(int j = 0; j < plus; j++) {
			if(s.at(j) != s.at(j+plus)) {
				good = false;
				break;
			}
		}
		if(good) {
			cout << n-i;
			return 0;
		}
	}
	cout << 0;
	return 0;
}



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

#define N 100003

int n, q;
int parent[N];

int root(int x) {
  if(x != parent[x]) x = parent[x] = root(parent[x]);
  return x;
}

void unite(int x, int y) {
  int px = root(x), py = root(y);
  if(px < py) {
    parent[py] = px;
  } else {
    parent[px] = py;
  }
}

int same(int x, int y) {
  return root(x) == root(y);
}

int main() {
  cin >> n >> q;
  for(int i=0; i<n; ++i) parent[i] = i;

  for(int i=0; i<q; ++i) {
    int com, x, y;
    cin >> com >> x >> y;
    if(com == 0) {
      unite(x, y);
    } else {
      cout << same(x, y) << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define qwq (cerr<<"qwq"<<endl)
#define orz(x) (cerr<<#x": "<<x<<endl)
#define orzarr(a,n) {cerr<<#a": "; repeat(__,0,n)cerr<<(a)[__]<<" "; cerr<<endl;}
#define orzeach(a) {cerr<<#a": "; for(auto __:a)cerr<<__<<" "; cerr<<endl;}
#define fi first
#define se second
typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;}
typedef double lf; typedef long double llf; const lf err=1e-11; const lf pi=acos(-1); lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;} template<typename T> T sqr(const T &x){return x*x;}
typedef pair<int,int> pii; template<typename A,typename B> ostream &operator<<(ostream &o,const pair<A,B> &x){return o<<'('<<x.fi<<','<<x.se<<')';}
//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=200010;
const int mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
//#define int ll
int n,m;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	ll a=read(),b=read();
	cout<<a*(a-1)/2+b*(b-1)/2<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int n;
    ll V;
    cin >> n >> V;
    ll a[n], b[n], c[n], d[n];
    rep(i,n)cin >> a[i];
    rep(i,n)cin >> b[i];
    rep(i,n)cin >> c[i];
    rep(i,n)cin >> d[i];

    map<ll,ll> mp;
    rep(i,n)rep(j,n)mp[a[i]+b[j]]++;

    ll ans = 0;

    rep(i,n){
        rep(j,n){
            ll tmp = V - (c[i] + d[j]);
            ans += mp[tmp];
        }
    }

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



Measured memory_bytes: 128092
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define rep2(x,from,to) for(long long (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 1000000000000000
int c;
int d;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a==b)cout<<"Yay!"<<endl;
    else
    {
        c=min(a,b);
        d=max(a,b)-c+1;
        if(16-a-b>=d)
        {
            cout<<"Yay!"<<endl;
        }
        else cout<<":("<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
A,B,C,K = (int(x) for x in input().split())
s = 0
d = (2*(10**10))
while True:
    if A <= K:
        s += (1*A)
        K = K - A
        A = d
    elif A != d and A > K:
        s = 1*K
        break
    elif A == d and B <= K:
        s = s
        K = K - B
        B = d
    elif A == d and  B != d and B > K:
        pass
        break
    elif A == d and B == d and C <= K:
        s -= (1*C)
        C = d
        break
    elif A == d and B == d and C != d and C > K:
        s -= (1*K)
        break
print(s)


Measured memory_bytes: 9164
def c_base_minus2_number(N):
    def negaternary(i):
        if i == 0:
            digits = ['0']
        else:
            digits = []
            while i != 0:
                i, remainder = divmod(i, -2)
                if remainder < 0:
                    i, remainder = i + 1, remainder + 2
                digits.append(str(remainder))
        return ''.join(digits[::-1])

    ans = negaternary(N)
    return ans

N = int(input())
print(c_base_minus2_number(N))

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

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

int main()
{
  const long long INF = 1LL << 60;
  
  long long dp [100150];
  
  for ( int i = 0; i < 100150; ++i ) dp[i] = INF;
  
  int n;
  cin >> n;
    
  int k;
  cin >> k;
  
  int h[100150];
  for ( int i = 0; i < 100150; ++i ) cin >> h[i];
  
  dp[0] = 0;

  for ( int i = 0; i < n; ++i )
  {
    for ( int j = 1; j <= k; j++ )
    {
      chmin( dp[i+j], dp[i] + abs( h[i] - h[i+j] ) );
    }
  }
  
  cout << dp[n-1] << endl;
  
  //for ( int i = 0; i < n; i++ ) cout << dp[i] << endl;
  
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define 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++)
#define VREP(it, v) for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
typedef pair<ll,ll> pi;
typedef vector<ll> vi;

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename K, typename V>
using pbds_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
ll r, c, k, a, b, vv;
ll grid[3005][3005];
ll memo[3005][3005][3];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> r >> c >> k;
	REP(i, 0, k){
		cin >> a >> b >> vv;
		grid[a - 1][b - 1] = vv;
		//v[a - 1].PB(b - 1, vv);
	}
	for (ll y = c - 1; y >= 0; y--){
		for (ll x = r - 1; x >= 0; x--){
			for (ll z = 0; z <= 3; z++){
				if (x == r - 1 && y == c - 1){
					if (z == 0){
						memo[x][y][z] = 0;
						continue;
					}
					if (grid[r - 1][c - 1] == 0){
						memo[x][y][z] = 0;
						continue;
					}
					memo[x][y][z] = grid[r - 1][c - 1];
					continue;
				}
				ll ans = 0;
				if (z == 0 || grid[x][y] == 0){
					if (y + 1 < c) ans = max(ans, memo[x][y + 1][z]);
					if (x + 1 < r) ans = max(ans, memo[x + 1][y][3]);
					memo[x][y][z] = ans;
					continue;
				}
				
				if (grid[x][y] != 0 && z > 0){
					if (x + 1 < r) ans = max(ans, grid[x][y] + memo[x + 1][y][3]);
					if (y + 1 < c) ans = max(ans, grid[x][y] + memo[x][y + 1][z - 1]);
					if (y + 1 < c) ans = max(ans, memo[x][y + 1][z]);
					if (x + 1 < r) ans = max(ans, memo[x + 1][y][3]);
				}
				memo[x][y][z] = ans;
				continue;
			}
		}
	}
	cout << memo[0][0][3] << endl;
}

//cout.flush()
//cout << fixed << setprecision(9) << x << endl;

Measured memory_bytes: 285232