akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N,M;cin>>N>>M;
  vector<vector<bool>>S(M,vector<bool>(N));
  for(long i=0;i<M;i++){
    long k;cin>>k;for(long j=0;j<k;j++){
      long s;cin>>s;
      S[i][s-1]=1;
    }
  }
  vector<long>P(M);for(long i=0;i<M;i++)cin>>P[i];
  long ans=0;
  for(long i=0;i<(1<<N);i++){
    long b=i;
    vector<long>B(M,0);
    for(long j=0;j<N;j++){
      for(long k=0;k<M;k++)if(b%2&&S[k][j])B[k]++;
      b/=2;
    }
    bool ok=1;
    for(long j=0;j<M;j++)if(P[j]!=B[j]%2)ok=0;
    if(ok)ans++;
  }
  cout<<ans<<endl;
  
}

/*




*/

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

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

  for(int i=0;i<s.length()-1;i++){
    for(int j=i+1;j<s.length();j++){
      if(s[i] > s[j]){
	c = s[i];
	s[i] = s[j];
	s[j] = c;
      }
    }
  }
  for(int i=0;i<t.length()-1;i++){
    for(int j=i+1;j<t.length();j++){
      if(t[i] < t[j]){
	c = t[i];
	t[i] = t[j];
	t[j] = c;
      }
    }
  }

  if(s < t){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}


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

namespace MyProject
{
    class Program
    {
        static void Main(string[] args)
        {
#if Local
            var sw = new Stopwatch();
            sw.Start();
            Console.SetIn(new StreamReader("input.in"));
#endif

            var solver = new Solver();
            solver.Solve();
#if Local
            Console.WriteLine($"{sw.ElapsedMilliseconds}ms");
#endif
        }
    }

    class Solver
    {
        public void Solve()
        {
            var x = Console.ReadLine().Split().Select(elem => int.Parse(elem)).ToList();
            var answer = x.IndexOf(0) + 1;
            
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 28252
#include <bits/stdc++.h>
using namespace std;
     
int main() {
  int A, B;
  char op;
  int result;

  cin >> A >> op >> B;
  
  if(op == '+') result = A + B;
  if(op == '-') result = A - B;
  
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>

using namespace std;

#define MOD 1000000007
#define INF 2147483647
#define ll long long

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

	map<int, int> m;

	int res = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (m[a] == 0) {
			res += 1;
			m[a]++;
		} else if (m[a] == 1) {
			res -= 1;
			m[a]--;
		}
	}
	cout << res << endl;

	return (0);
}

Measured memory_bytes: 4864
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
Aend = []
Bstart = []
Ae_Bs = []
cnt = 0

for i in range(N):
    S = input().rstrip()
    if S[0]=='B' and S[-1] =='A':
        Ae_Bs.append(S)
    elif S[0] == 'B':
        Bstart.append(S)
    elif S[-1] == 'A':
        Aend.append(S)
    cnt += S.count('AB')

lAe_Bs = len(Ae_Bs)
lBstart = len(Bstart)
lAend = len(Aend)

if lAe_Bs >0:
    cnt += lAe_Bs -1
    
if lAe_Bs > 0 and lAend >0:
    cnt += 1
    lAend -=1
if lAe_Bs > 0 and lBstart>0:
    cnt +=1
    lBstart -=1

cnt += min(lAend,lBstart)

print(cnt)


Measured memory_bytes: 9784
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han
//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(lo i=1;i<=n;i++)
#define FOR1 for(lo i=1;i<=m;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 100005; 
const lo mod = 1000000007; 

lo n,m,b,a[li],k,flag;
lo cev;
string s;
vector<int> v;

void YES(int xxxx){
	if(xxxx==1)
		printf("YES\n");
	else cout<<"YES\n";
	exit(0);
}

void NO(int xxxx){
	if(xxxx==1)
		printf("NO\n");
	else cout<<"NO\n";
	exit(0);
}

int main(void){
	scanf("%lld %lld",&n,&m);
	n=n*3;
	n+=m;
	printf("%lld\n",n/2);
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int n, k;

  cin >> n >> k;

  ll ans = 0;

  ans += (ll)(n / k) * (n / k) * (n / k);

  if(k % 2 == 0) {
    n += k / 2;
    ans += (ll)(n / k) * (n / k) * (n / k);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int A = scanner.nextInt();
    int B = scanner.nextInt();
    if (A >= 13) {
      System.out.println(B);
    } else if (A >= 6) {
      System.out.println(B / 2);
    } else {
      System.out.println(0);
    }
  }
}


Measured memory_bytes: 21332
#include <bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if((i < b) ^ (j < a)) cout << 1;
            else cout << 0;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <bitset>
 
#define INPUT_FROM_FILE (0) 
#if INPUT_FROM_FILE
#include <fstream>
#endif

void seconds_to_ths(int seconds, int &t, int &h, int &s){
	t = seconds / 3600; seconds %= 3600;
	h = seconds / 60; seconds %= 60;
	s = seconds;
}

int main(int argc, char **argv){
	int T, H, S;

#if INPUT_FROM_FILE
	std::ifstream ifs("test.txt");
	//FILE *fp = fopen("test.txt", "r");
#endif

#if INPUT_FROM_FILE
	while(ifs >> T >> H >> S){
#else
	while(std::cin >> T >> H >> S){
#endif
		if(T == -1 && H == -1 && S == -1){ break; }
		int total_seconds = 120 * 60;
		int record_seconds = 3600 * T + 60 * H + S;
		int rem_seconds = total_seconds - record_seconds;
		int t, h, s;

		seconds_to_ths(rem_seconds, t, h, s);
		printf("%02d:%02d:%02d\n", t, h, s);
		seconds_to_ths(3 * rem_seconds, t, h, s);
		printf("%02d:%02d:%02d\n", t, h, s);
	}


 
#if INPUT_FROM_FILE
	//fclose(fp);
#endif
    return 0;
}


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

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

    int n;
    cin >> n;
    vector<tuple<int, int, int, ll>> z(n);
    rep(i, 0, n) {
        int w, s, v;
        cin >> w >> s >> v;
        z[i] = make_tuple(w + s, w, s, v);
    }
    sort(z.begin(), z.end());
    vector<vector<ll>> dp(n + 1, vector<ll>(20010, -1e18));
    dp[0][0] = 0;

    rep(i, 0, n) {
        dp[i + 1] = dp[i];
        int s = get<2>(z[i]), w = get<1>(z[i]);
        ll v = get<3>(z[i]);
        rep(j, 0, s + 1) {
            dp[i + 1][j + w] = max(dp[i + 1][j + w], dp[i][j] + v);
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;

    return 0;
}

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

int moze[25][25];
int dp[5000005];

const int MOD = 1000000007;

int add(int a, int b){
    return (a+b)%MOD;
}

int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> moze[i][j];
        }
    }
    dp[0] = 1;
    for(int mask=0; mask<(1<<n); mask++){
        int k = __builtin_popcount(mask);
        for(int j=0; j<n; j++){
            if(moze[j+1][k+1] && ((mask & (1<<j)) == 0)){
                dp[mask | (1<<j)] = add(dp[mask | (1<<j)], dp[mask]);
            }
        }
    }
    cout << dp[(1<<n)-1];
    return 0;
}


Measured memory_bytes: 10496
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    s=ii()
    X = [s]
    seen = set([s])
    for i in range(10**6+10):
        x = X[-1]
        if x % 2 == 0:
            y = x//2
        else:
            y = 3*x+1
        
        X.append(y)
        if y in seen:
            print(i+2)
            # print(X)
            exit()

        seen.add(y)
    
    assert False




        





if __name__ == "__main__":
    main()

Measured memory_bytes: 61492
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,ans;
int d[20][20];
int g[(1<<15)+5];
int f[(1<<15)+5][20];
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int q=read(),w=read(),e=read();
        d[q][w]=e;
        d[w][q]=e;
        ans+=e;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(d[i][j])
            {
                for(int S=0;S<(1<<n);S++)
                {
                    if(((S>>(i-1))&1)&&((S>>(j-1))&1))  g[S]+=d[i][j];
                }
            }
        }
    }
    memset(f,-1,sizeof(f));
    f[1][1]=0;
    for(int S=0;S<(1<<n);S++)
    {
        for(int i=1;i<=n;i++)
        {
            if(f[S][i]==-1)  continue;
            for(int j=1;j<=n;j++)
            {
                if(!((S>>(j-1))&1)&&d[i][j])  f[S|(1<<(j-1))][j]=max(f[S|(1<<(j-1))][j],f[S][i]+d[i][j]);  
            }
            int O=(((1<<n)-1)^S);
            for(int j=O;j;j=((j-1)&O))
            {
                if(j)
                {
                    f[S|j][i]=max(f[S|j][i],f[S][i]+g[j|(1<<(i-1))]);
                }
            }
        }
    }
    printf("%d\n",ans-f[(1<<n)-1][n]);
    return 0;
}

Measured memory_bytes: 2944
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>

const int MAXN=1e6;

struct Edge{
	int next,to,from;
}edge[MAXN<<1];

int cnt,head[MAXN];
int n,k,dep[MAXN],res;
int ans=1e9;

int min(int a,int b) { return a>b ? b : a; }

void Add_Edge(int u,int v) {
	edge[++cnt]=(Edge){head[u],v,u};
	head[u]=cnt;
}

void dfs(int x,int fa) {
	for(int i=head[x];i;i=edge[i].next) {
		int v=edge[i].to;
		if(v==fa) continue ;
		dep[v]=dep[x]+1;
		dfs(v,x);
		if(dep[x]>=k/2) res++;
	}
}

int main() {
	scanf("%d%d",&n,&k);
	for(int i=1,x,y;i<=n-1;i++) {
		scanf("%d%d",&x,&y),Add_Edge(x,y),Add_Edge(y,x);
	}
	
	if(k&1) {
		for(int i=1;i<=n;i++) {
			for(int j=head[i];j;j=edge[j].next) {
				res=0;
				std:: memset(dep,0,sizeof(dep));
				dfs(i,edge[j].to);
				std:: memset(dep,0,sizeof(dep));
				dfs(edge[j].to,i);
				ans=min(ans,res);
			}
		}
	} else {
		for(int i=1;i<=n;i++) {
			std:: memset(dep,0,sizeof(dep));
			res=0;
			dfs(i,0);
			//std:: cout<<res<<" "; 
			ans=min(ans,res);
		}
	}
	
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 6528
fun main(args: Array<String>) {
    val (N, Q) = listOfInt()
    val G = Array<MutableList<Int>>(N) { mutableListOf<Int>() }
    val Y = Array<MutableList<Int>>(N) { mutableListOf<Int>() }
    val C = Array<Int>(N) { 0 }
    repeat(N - 1) {
        val (a, b) = listOfInt(-1)
        G[a].add(b)
        Y[b].add(a)
    }
    repeat(Q) {
        val (p, x) = listOfInt()
        C[p -  1] += x
    }
    for (n in 1 until N) C[n] += C[Y[n].first()]
    println(C.joinToString(separator = " "))
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }


Measured memory_bytes: 157792
n ,m = map(int, input().split())
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
if max(L) <= min(R):
    print(min(R) - max(L) + 1)
else:
    print(0)

Measured memory_bytes: 10996
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = INF+7;
const ll LINF = 1e18;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define VI vector<int>
#define VII vector<vector<int>>
#define all(v) v.begin(),v.end()
#define MP make_pair
#define pb(n) push_back(n)

int dp[3][110];

int main(){
    int N; cin>>N;
    vector<vector<int>> A(3,vector<int>(N+1));
    rep(i,2)rep(j,N) cin>>A[i+1][j+1];

    for(int i=1;i<=2;++i){
        for(int j=1;j<=N;++j){
           dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + A[i][j];
        }
    }
    cout<<dp[2][N]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

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

    ll a, b, c;
    cin >> a >> b >> c;
    if (a == b && b == c) {
        cout << "No" << endl;
        return 0;
    }
    if (a != b && b != c && c != a) {
        cout << "No" << endl;
        return 0;
    }
    
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 100100100;


int main(){
  int n;
  cin >> n;
  vector<int> a(n+1);
  rep(i,n+1){
    if(i==0) {a[i]=0; continue;}
    cin >> a[i];
  }

  int tot = 0;
  rep(i,n+1){
    int add;
    if(i==n) add = abs(a[0]-a[i]);
    else add = abs(a[i]-a[i+1]);
    tot += add;
  }


  for(int i = 1; i < n+1; i++){
    int del;
    int add;
    if(i == n){
      del = abs(a[n-1]-a[n])+abs(a[n]-a[0]);
      add = abs(a[n-1]-a[0]);
    }
    else{
      del = abs(a[i-1]-a[i])+abs(a[i]-a[i+1]);
      add = abs(a[i-1]-a[i+1]);
    }

    cout << tot + add - del << endl;
  }

  
}


Measured memory_bytes: 3752
#include <vector>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

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

    if (n == 1) return 0;

    vector<int> h;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        h.push_back(x);
    }

    // dp[i] is the minimum cost to get to i
    vector<int> dp (n, 0);
    dp[0] = 0; dp[1] = abs(h[1] - h[0]);

    for (int i = 2; i < n; i++)
    {
        dp[i] =    min(dp[i-1] + abs(h[i-1] - h[i]),
                      dp[i-2] + abs(h[i-2] - h[i]));
    }

    cout << dp[n-1];

    return 0;
}

Measured memory_bytes: 1144
#include <cstdio>
#include <climits>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int n;
int p[801];
int d[801];

int memo[801][801];
int memo_b[801][801];

// to, dist
vector<pair<int, int> > edge[801];

int cost(int e, int f);
int cost_back(int e, int f);

int cost(int e, int f) {
    if (memo[e][f] != -1) {
        return memo[e][f];
    }

    vector<int> b; // cost_back
    vector<int> c; // cost

    for (int i = 0; i < (int)edge[e].size(); i++) {
        int to = edge[e][i].first;
        int dist = edge[e][i].second;

        if (to == f) { continue; }

        int r = cost_back(to, e);
        if (r == 0) {
            b.push_back(dist);
        } else {
            b.push_back(r + dist * 3);
        }

        c.push_back(cost(to, e) + dist * 2);
    }

    int b_sum = 0;
    for (int i = 0; i < (int)b.size(); i++) { b_sum += b[i]; }

    // printf("b_sum: %d, b.size(): %d\n", b_sum, b.size());

    int r = b_sum;
    if (b.size() == 0) { r = 0; }
    for (int i = 0; i < (int)b.size(); i++) {
        r = min(r, b_sum - b[i] + c[i]);
    }

    memo[e][f] = r;
    return r;
}

int cost_back(int e, int f) {
    if (memo_b[e][f] != -1) {
        return memo_b[e][f];
    }

    int s = 0;

    for (int i = 0; i < (int)edge[e].size(); i++) {
        int to = edge[e][i].first;
        int dist = edge[e][i].second;

        if (to == f) { continue; }

        int r = cost_back(to, e);
        if (r == 0) { // 'to' is a leaf
            s += dist;
        } else {
            s += r + dist * 3;
        }
    }

    memo_b[e][f] = s;
    return s;
}

int solve() {
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, cost(i, -1));
    }
    return ans;
}

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

        if (!n) { break; }

        for (int i = 2; i <= n; i++) { scanf("%d", &p[i]); }
        for (int i = 2; i <= n; i++) { scanf("%d", &d[i]); }

        for (int i = 0; i < 801; i++) {
            edge[i].clear();
            for (int j = 0; j < 801; j++) {
                memo[i][j] = -1;
                memo_b[i][j] = -1;
            }
        }

        for (int i = 2; i <= n; i++) {
            int f = i;
            int t = p[i];
            int c = d[i];
            edge[f].push_back(make_pair(t, c));
            edge[t].push_back(make_pair(f, c));
        }

#if 0
        for (int i = 1; i <= n; i++) {
            printf("%d:", i);
            for (unsigned j = 0; j < edge[i].size(); j++) {
                printf(" (%d,%d)", edge[i][j].first, edge[i][j].second);
            }
            printf("\n");
        }
#endif

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

Measured memory_bytes: 6292
N, M = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
mod = 10**9+7
x = 0
y = 0
for i in range(N):
    x += (-N+1+2*i)*X[i]
    x %= mod
for i in range(M):
    y += (-M+1+2*i)*Y[i]
    y %= mod
print(x*y % mod)


Measured memory_bytes: 18624
/*Coded by::
    **Avinash Tiwary**
    **BE/10298/2015**
    **Production Engineer**
    **Producing <code>**
*/
#include<bits/stdc++.h>
#define buf ios_base::sync_with_stdio (0), cin.tie (0)
typedef long long ll;
typedef double dob;
#define MAX 50010
#define M5 200009
#define M6 2000009
#define M 1000000007
#define inf LLONG_MAX
using namespace std;
typedef vector<ll> V;
typedef queue<ll > Q;
typedef stack<ll> S;
typedef pair<ll,ll> P;
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
ll fac[M6],not_prime[M6];
ll power(ll x,ll n){
    if(n==0) return 1;
    /*while(n){
        if(n%2) x=(((x*x)%M)*x)%M; 
        else x=(x*x)%M;
        n/=2;
    }*/
    if(n%2 == 0) return power((x*x),n/2);
    else return (x*power((x*x),(n-1)/2));
}
void fact(){
    fac[0]=1;
    for(ll i=1;i<M6;i++) fac[i]=(i*fac[i-1])%M;
}
void sieve(){
    not_prime[1]=1; not_prime[0]=1;
    for(ll p=2;p*p<M6;p++){
        if(!not_prime[p]){
            for(ll i=p*2;i<=M6;i+=p) not_prime[i]=1;
        }
    }
}
ll modi(ll a, ll m){
    ll m0 = m, t, q; ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1){  q = a / m; t = m; m = a % m, a = t;t = x0;x0 = x1 - q * x0; x1 = t;}
    if (x1 < 0) x1 += m0;return x1;
}
ll n,m,vis[M6];
V g[M5];
/*ll solve(ll sor,ll des){
	if(sor==des) return 1;
	else return 0;
	if(dp[sor][des]!=-1) return dp[sor][des];
	ll i,ans=0;
	for(i=1;i<=n;i++){
		if(connect[i][des]){
			ans+=solve(n,i); ans%=M;
		}
	}
	return dp[sor][des]=ans;
}*/
int main(){
    //buf; 
    //fact();
    //sieve()
    ll i,j,k,l,test,flag,ans,x,y; string s;
    //cin>>test;
    test=1;
    while(test--){
    	cin>>s;
    	s[3]='8';
cout<<s;

	}
    return 0;
}

Measured memory_bytes: 6400
#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

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); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

vector<PII> g[100010];
int d[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n, m, s, t;
	cin >> n >> m >> s >> t;
	s--, t--;
	REP(i, m) {
		int a, b, c, dd;
		cin >> a >> b >> c >> dd;
		a--, b--, c--;
		g[a].PB({b, dd});
		g[b].PB({a, dd});
		g[b].PB({c, dd});
		g[c].PB({b, dd});
		g[c].PB({a, dd});
		g[a].PB({c, dd});
	}
	
	REP(i, n) d[i] = LLINF;
	d[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> que;
	que.push({d[s], s});
	
	while(que.size()) {
		PII p = que.top(); que.pop();
		//cout << p << endl;
		if(p.first > d[p.second]) continue;
		for(PII i: g[p.second]) {
			if(d[i.first] > d[p.second] + i.second) {
				d[i.first] = d[p.second] + i.second;
				que.push({d[i.first], i.first});
			}
		}
	}
	
	cout << d[t] << endl;

  return 0;
}



Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int dp[100005][3];
int zeros[100005];
int ones[100005];
int twos[100005];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>zeros[i]>>ones[i]>>twos[i];
    }

    for(int index=1;index<=n;index++)
    {
        dp[index][0] = max(dp[index][0],max(dp[index-1][1],dp[index-1][2])+zeros[index]);
        dp[index][1] = max(dp[index][1],max(dp[index-1][0],dp[index-1][2])+ones[index]);
        dp[index][2] = max(dp[index][2],max(dp[index-1][1],dp[index-1][0])+twos[index]);
    }
    cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;



}













Measured memory_bytes: 5936
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=1000010;

ll n;
ll dp[maxn];
ll a[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[1]=0;
    dp[0]=0;
    dp[2]=abs(a[2]-a[1]);
    for(int i=3;i<=n;i++)
    {
        dp[i]=min(dp[i-2]+abs(a[i]-a[i-2]),dp[i-1]+abs(a[i]-a[i-1]));

    }
    cout<<dp[n];
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

Measured memory_bytes: 5120
import heapq
from collections import deque
n,k = map(int,input().split())
v=list(map(int,input().split()))
 
res = 0 # 答え
for i in range(k+1): # 左から宝石を取り出す回数
    for j in range(k+1-i): # 右から宝石を取り出す回数
        d = deque(v) # 宝石の詰まったDeque
        num = 0 # 個々の試行によるスコア
        a = [] # heapsort用のlist
 
        cnt = 0 # 繰り返し試行、forループの代わり
        while cnt<i and len(d):
            x = d.popleft() # dequeの左端から宝石を取り出す
            heapq.heappush(a,x) # 得られたスコアを追加
            num += x # 暫定スコアを更新
            cnt += 1
        cnt = 0
        while cnt<j and len(d):
            x = d.pop()
            heapq.heappush(a,x)
            num += x
            cnt += 1
 
        sub = k-i-j # 最大試行回数から使用済み試行回数を引く
        while sub > 0 and len(a): # 残試行回数cntとスコア列aの長さが1以上の時
            y = heapq.heappop(a) # スコアが最も小さい宝石を除く
            if y <= 0: # 除いた宝石のスコアがマイナスなら
                num -= y # 最終的なスコアもマイナスにする、プラスなら取り除かなかったことにする
            sub -= 1
        
        res = max(res,num)
print(res)

Measured memory_bytes: 3316
//#pragma GCC optimize ("O3,unrolled-loops")
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
	fastio
	int n;
	cin >> n;
	double p[n];
	for(auto &x : p) cin >> x;
	double dp[n][n+1]; //Ends with which, how many heads
	memset(dp,0,sizeof dp);
	dp[0][0] = 1-p[0], dp[0][1] = p[0];
	for(int i = 1;i < n;i++){
		for(int j = 0;j <= i+1;j++){
			dp[i][j] += dp[i-1][j] * (1-p[i]);
			dp[i][j] += dp[i-1][j-1] * p[i];
		}
	}
	double ans = 0;
	for(int i = n/2+n%2; i <= n;i++){
		ans += dp[n-1][i];
	}
	cout << fixed << setprecision(10) << ans << "\n";
}

Measured memory_bytes: 74064
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <string>
#pragma warning(disable : 4996)

#define MAX_N 25

struct Node {
	int id;
	int parent;
	int left;
	int right;
	int depth;
	int hight;
	Node() : id(-1), parent(-1), depth(-1), left(-1), right(-1), hight(-1) {}
};

Node nodes[MAX_N];

Node *GetRoot(int n) {
	for (int i = 0; i < n; ++i) {
		if (nodes[i].parent == -1) {
			return &nodes[i];
		}
	}
	return NULL;
}
int CalcDHr(Node *n, int depth) {
	n->depth = depth;
	int md = n->depth;
	if (n->left != -1) {
		Node *l = &nodes[n->left];
		int cd = CalcDHr(l, depth+1);
		if (md < cd) md = cd;
	}
	if (n->right != -1) {
		Node *r = &nodes[n->right];
		int cd = CalcDHr(r, depth+1);
		if (md < cd) md = cd;
	}
	n->hight = md - n->depth;
	return md;
}
void CalcDH(int n) {
	Node *root = GetRoot(n);
	CalcDHr(root, 0);
}
void Preorder(Node *node) {
	printf(" %d", node->id);
	if(node->left != -1) Preorder(&nodes[node->left]);
	if(node->right != -1) Preorder(&nodes[node->right]);
}
void Inorder(Node *node) {
	if (node->left != -1) Inorder(&nodes[node->left]);
	printf(" %d", node->id);
	if (node->right != -1) Inorder(&nodes[node->right]);
}
void Postorder(Node *node) {
	if (node->left != -1) Postorder(&nodes[node->left]);
	if (node->right != -1) Postorder(&nodes[node->right]);
	printf(" %d", node->id);
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int id;
		int left;
		int right;
		scanf("%d %d %d", &id, &left, &right);
		nodes[id].id = id;
		nodes[id].left = left;
		if (left >= 0) {
			nodes[left].parent = id;
		}
		nodes[id].right = right;
		if (right >= 0) {
			nodes[right].parent = id;
		}
	}
	Node *root = GetRoot(n);
	printf("Preorder\n");
	Preorder(root);
	printf("\n");
	printf("Inorder\n");
	Inorder(root);
	printf("\n");
	printf("Postorder\n");
	Postorder(root);
	printf("\n");
	return 0;
}


Measured memory_bytes: 2720
#include <iostream>
#include <vector>
#include <cmath>

int main(int argc, char *argv[])
{
  unsigned int n, d;
  unsigned int s;
  unsigned long p, q, r;
  int res;

  std::cin >> n >> d;
  s = n * d;

  std::vector<int> x(s);
  for (int i=0; i<n; ++i) {
    for (int j=0; j<d; ++j) {
      std::cin >> x.at(i*d + j);
    }
  }

  res = 0;
  for (int i=0; i<n-1; ++i) {
    for (int j=i+1; j<n; ++j) {
      p = 0;
      for (int k=0; k<d; ++k) {
        p += (x.at(i*d+k) - x.at(j*d+k)) * (x.at(i*d+k) - x.at(j*d+k));
      }
      q = (unsigned long)sqrt(p);
      r = q * q;
      if (p == r) {
        ++res;
      }
    }
  }
  std::cout << res << std::endl;

  return 0;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(ll i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

signed main()
{
    int a, b;
    cin >> a >> b;
    int ans = max({a+b, a-b, a*b});
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
x, n = [int(x) for x in input().split()]
ps = [int(x) for x in input().split()]

best = 100000000
ret = x

if n:
	mn = min(ps)
	mx = max(ps)
	s = set(ps)
	for i in range(mn, mx+1):
		if i not in s:
			d = abs(x-i)
			if d < best:
				best = d
				ret = i
	if ret == x:
		up = abs(mx + 1 - x)
		down = abs(mn - 1 - x)
		ret = mn-1 if down <= up else mx+1
	if x not in s:
		ret = x

print(ret)



Measured memory_bytes: 9152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9+7
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 long long int gcd(long long int m,long long int n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
long long int lcm(long long int number1,long long int number2){
	return number1 * number2 / gcd(number1,number2);	

}

vector<ll>date;
ll N;

void dfs(ll a,ll b,ll c,ll d){
  
  if(d>N){
return;
  }

  
 
  
  if(a>0&&b>0&&c>0){
    date.push_back(d);
  }
  
  dfs(a+1,b,c,d*10+7);
  dfs(a,b+1,c,d*10+5);
  dfs(a,b,c+1,d*10+3);// ll m=のやつはdfsを生成しているわけではない？
  
}
  
  
  
  
int main(){
  
  cin>>N;
  
 //resize()する必要なし？

  
  dfs(0,0,0,0);
  
  cout<<date.size()<<endl;
}
  

Measured memory_bytes: 640
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
V s,z;
main(){
	int i,j,n,m,a,b,c,t;
	for(;scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&t),n;){
		V x(n*n);
		V e(n*n);
		z.resize(n*n);
		s.resize(n);
		x[0]=b;
		x[1]=c;
		e[0]=1;
		for(i=1;i<n-1;i++){
			x[i*n+i-1]=a;
			x[i*n+i]=b;
			x[i*n+i+1]=c;
			e[i*n+i]=1;
		}
		x[i*n+i-1]=a;
		x[i*n+i]=b;
		e[i*n+i]=1;
		for(;t;t>>=1){
			const V &_x=e;
			const V &_y=x;
			if(t&1){
				for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(_x[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
				e=z;
			}
			for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(_y[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
			x=z;
		}
		for(i=0;i<n;i++)scanf("%d",&s[i]);
		const V &r=e;
		for(i=0;i<n-1;i++)printf("%d ",(r[slice(i*n,n,1)]*s).sum()%m);
		printf("%d\n",(r[slice(i*n,n,1)]*s).sum()%m);
	}
}

Measured memory_bytes: 1084
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int main(void)
{
    int N; cin >> N;
    int ans1[N], ans2[N];
    int ans = 0;
    rep(i ,N) cin >> ans1[i] >> ans2[i];
    rep(i ,N) ans += ans2[i] - ans1[i] + 1;

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

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int n;
vector<Int> a;
vector<Int> ans;
Int mx, mn;
set<int> maxs, mins;
bool ok[1100];

Int min_initial(Int from, Int to)
{
    auto aa = a;
    vector<int> used(n, 0);
    for (int i = from; i < to; i++) {
        if (used[ans[i]])
            return n;
        used[ans[i]] = 1;
        aa[ans[i]]++;
    }

    Int tmpmx = *max_element(aa.begin(), aa.end());
    Int tmpmn = *min_element(aa.begin(), aa.end());
    if (tmpmn * 2 < tmpmx)
        return n;
    if (tmpmn * 2 > tmpmx) {
        for (int i = 0; i < n; i++)
            if (!used[i])
                return i;
        return n;
    }
    Int max_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (aa[i] == tmpmx)
            max_cnt++;
    }

    for (int i = from; i < to; i++) {
        if (aa[ans[i]] == tmpmx)
            max_cnt--;
        if (aa[ans[i]] == tmpmn) {
            if (max_cnt != 0)
                return n;
        }
    }

    for (int i = 0; i < n; i++) {
        if (aa[i] == 0)
            continue;
        if (used[i])
            continue;
        if (max_cnt == 0 && !used[i])
            return i;
        if (max_cnt > 0 && aa[i] != tmpmn && !used[i])
            return i;
    }
    return ans[from];
}

int main()
{
    Int as = 0;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        as += a[i];
    }

    Int mx = *max_element(a.begin(), a.end());
    Int mn = *min_element(a.begin(), a.end());
    if (mn * 2 < mx) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i < as; i++) {
        Int nxt = n;
        for (int j = max(0ll, i - n + 1); j <= i; j++) {
            nxt = min(nxt, min_initial(j, i));
            if (!ok[j])
                break;
        }

        a[nxt]--;
        ans.push_back(nxt);
        if (ans.size() >= n) {
            set<int> hoge;
            for (int j = 0; j < n; j++) {
                hoge.insert(ans[ans.size() - 1 - j]);
            }
            if (hoge.size() == n) {
                for (int j = 0; j < n; j++)
                    ok[ans.size() - 1 - j] = true;
            }
        }
    }

    for (auto elem : ans)
        cout << elem + 1 << " ";
    cout << endl;

    return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(a))
using namespace std;
const int mo=1000000007;
int n,k,ans,a[2005];
int main(){
	scanf("%d%d",&n,&k);
	For(i,1,n) scanf("%d",&a[i]);
	For(i,1,n) For(j,i+1,n)
		if (a[i]<a[j]) ans=(ans+1ll*k*(k-1)/2)%mo;
		else if (a[i]>a[j]) ans=(ans+1ll*k*(k+1)/2)%mo; 
	printf("%d\n",ans);
} 

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

using namespace std;

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

int main() {
    int a, b;
    cin >> a >> b;
    if((a+b) % 2 == 0) {
        cout << ((a + b) / 2) << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}


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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define mod 1000000007LL

#define IN freopen("C.in","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(i=a ; i<=b ; i++)
#define DBG pf("Hi\n")
#define INF 1000000000
#define i64 long long int
#define eps (1e-8)
#define xx first
#define yy second
#define ln 17
#define off 2

using namespace __gnu_pbds;
using namespace std ;

typedef tree< i64, null_type, less<i64>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef pair<i64, i64> pii;

#define maxn 300005

int col[maxn] ;
int c[maxn] ;
vector <int> g[maxn] , e[maxn] ;
int d[maxn] ;

char s[maxn] ;

int main()
{
    int n , m ;

    scanf("%d %d",&n,&m) ;

    for(int i=1 ; i<=n ; i++) scanf("%d",&d[i]) ;

    for(int i=1 ; i<=m ; i++)
    {
        int u , v ;
        scanf("%d %d",&u,&v) ;
        g[u].pb(v) ; e[u].pb(i) ;
        g[v].pb(u) ; e[v].pb(i) ;
    }

    for(int i=1 ; i<=n ; i++)
    {
        int mn = d[ g[i][0] ] ;
        for(int j=1 ; j<g[i].size() ; j++)
        {
            mn = min( mn , d[ g[i][j] ] ) ;
        }
        if( mn > d[i] )
        {
            printf("-1\n") ;
            return 0 ;
        }
    }

    vector < pair<int,int> > vp ;

    for(int i=1 ; i<=n ; i++) vp.pb( mp( d[i] , i ) ) ;

    sort( vp.begin() , vp.end() ) ;

    memset(col,-1,sizeof(col)) ;

    for(int i=0 ; i<vp.size() ; i++)
    {
        int u = vp[i].yy ;
        if( col[u]!=-1 ) continue ;
        int fl = 0 ;
        for(int j=0 ; j<g[u].size() ; j++)
        {
            int v = g[u][j] ;
            if( col[v]!=-1 )
            {
                fl = 1 ;
                col[u] = (col[v]^1) ;
                c[ e[u][j] ] = d[u] ;
                break ;
            }
        }
        if(fl==0){

            col[u] = 0 ;
            for(int j=0 ; j<g[u].size() ; j++)
            {
                int v = g[u][j] ;
                if( d[u] == d[v] )
                {
                    col[v] = 1 ;
                    c[ e[u][j] ] = d[u] ;
                    break ;
                }
            }
        }
    }

    for(int i=1; i<=m; i++)
    {
        if( c[i] == 0 ) c[i] = INF ;
    }

    for(int i=0 ; i<n ; i++)
    {
        if( col[i+1] == 0 ) s[i] = 'W' ;
        else s[i] = 'B' ;
    }

    s[n] = '\0' ;

    printf("%s\n",s) ;

    for(int i=1 ; i<=m ; i++) printf("%d\n",c[i]) ;

    return 0 ;
}


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

const int MAXN = 500010;
char buf[MAXN]; int n, l, r, ans;
void add() {
	++buf[r = n - 1]; ++ans;
	while (buf[r] == '9' + 1) buf[r] -= 10, ++buf[--r];
	l = std::min(l, r);
	while (buf[l] == '0') ++l;
}
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	std::cin >> buf; n = strlen(buf);
	while (l < n) {
		r = l;
		while (r < n - 1 && buf[r + 1] >= buf[r]) ++r;
		if (r == n - 1) { ++ans; break; }
		int tr = r, tl;
		while (r > l && buf[r] == buf[r - 1]) --r;
		tl = r;
		do {
			while (l <= tl) buf[l] = '0', ++l; ++tl;
			add();
			if (r <= tr) break;
			while (tr < n - 1 && buf[tr + 1] == buf[tr]) ++tr;
			if (tr == n - 1 || buf[tr + 1] > buf[tr]) break;
		} while (tl <= tr);
	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long int

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int cnt[4] = {1, 0, 0, 0};
    int N, W;
    cin >> N >> W;
    int w0;
    cin >> w0;
    int v[5][N];
    fill(v[0], v[4], 0);
    cin >> v[0][0];
    for (int i = 1; i < N; i++) {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        v[tmp1 - w0][i] = tmp2;
        cnt[tmp1 - w0]++;
        //cout << "cnt[" << tmp1-w0 << "] = " << cnt[tmp1 - w0] << endl;    
    }
    rep(i, 4) {
        sort(v[i], v[i] + N, greater<int>()); 
    }
    rep(i, 4) {
        rep(j, N-1) {
            v[i][j+1] += v[i][j];
        }
    }
    rep(k, 4){
        rep(i, cnt[0]) {
           //dump(v[k][i]);
        }
    }


    int ans = 0;
    rep(i, N+1) {
        rep(j, N+1) {
            rep(k, N+1) {
                rep(l, N+1) {
                    //dump(W);
                    //dump(i*w0 + j*(w0+1)+ k*(w0+2) + l*(w0+3));
                    if (W >= i*w0 + j*(w0+1)+ k*(w0+2) + l*(w0+3)) {
                        //dump(ans);
                        int tmp = 0;
                        if (i != 0) tmp += v[0][i-1];
                        if (j != 0) tmp += v[1][j-1];
                        if (k != 0) tmp += v[2][k-1];
                        if (l != 0) tmp += v[3][l-1];                    
                        ans = max(ans, tmp);
                    } else break;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().decode("utf-8").rstrip()
sp = [int(h == "p") for h in S]


def solve():
    g = p = 0
    score = 0
    for is_p in sp:
        if g == p:
            hand = 0
            g += 1
        else:
            hand = 1
            p += 1
        if hand > is_p:
            score += 1
        elif hand < is_p:
            score -= 1
    return score


if __name__ == "__main__":
    print(solve())


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

int main(){
  int n,m,p;
  while(1){
    cin>>n>>m>>p;
    if(n==0)return 0;
    int sum=0;
    int a;
    for(int i=0;i<n;i++){
      int tmp;
      cin>>tmp;
      if(i==m-1)a=tmp;
      sum+=tmp;
    }
    int sumM=sum*100;
    if(a==0){
      cout << 0 << endl;
    }else{
      cout << (sumM*(100-p)/100)/a << endl;
    }
  }
  return 0;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = int(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = int(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = int(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = int(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = int(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = (1 << 30) - 1;
const long long LLINF = 1LL << 61;
const long long MOD = 1000000007LL;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int cnt = 0;

void dfs(int v, int prev, vector<lint> &ans, const vector<lint> &c, const vector< vector<int> > &g){
    ans[v] = c[cnt++];
    for(auto e : g[v]){
        if(e != prev){
            dfs(e, v, ans, c, g);
        }
    }
    return;
}

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

    int n;
    cin >> n;

    vector< vector<int> > g(n);
    vector< P > v;
    rep(i, n - 1){
        int a, b;
        cin >> a >> b;
        g[--a].emplace_back(--b);
        g[b].emplace_back(a);
        v.emplace_back(a, b);
    }

    vector<lint> c(n);
    rep(i, n){
        cin >> c[i];
    }
    SORT_INV(c);

    vector<lint> ans(n);
    dfs(0, -1, ans, c, g);

    lint sum = 0;
    rep(i, v.size()){
        sum += min(ans[v[i].first], ans[v[i].second]);
    }

    cout << sum << endl;
    rep(i, n){
        cout << ans[i];
        if(i < n - 1){
            cout << " ";
        }else{
            cout << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1920
import numpy as np
import itertools
n,m,x=map(int,input().split())
a=[]
b=[0]*m
skill=np.array([b])
ans=[]
money=0
for _ in range(n):
    a.append(list(map(int,input().split())))
for i in range(1,n+1):
    for j in itertools.combinations(range(1,n+1),i):
        for k in range(len(j)):
            money+=a[j[k]-1][0]
            skill+=np.array([a[j[k]-1][1:m+1]])
        if all([i>=x for i in skill[0]]):
            ans.append(money)
        money=0
        skill=np.array([b])
if len(ans)==0:
    print(-1)
else:
    print(min(ans))

Measured memory_bytes: 27344
def LI():
    return list(map(int, input().split()))


N, P = LI()
A = LI()
gu = 0
ki = 0
for i in range(N):
    if A[i] % 2 == 0:
        gu += 1
    else:
        ki += 1


if ki == 0:
    if P == 0:
        ans = 2**N
    else:
        ans = 0
else:
    ans = 2**(N-1)
print(ans)

Measured memory_bytes: 8948
#include <iostream>
using namespace std;
int main(void){
    int x,y;
    cin >> x >> y;
    while (x!=0||y!=0){
        
          if (x<y) {
            cout << x <<" "<< y << endl;
        } else{
            cout << y<<" "<< x << endl;
        }
  cin >> x >> y;  }
    return 0;
}



Measured memory_bytes: 3088
#include<stdio.h>
#define MAX 36
struct Card{
  char suit;
  char value;
};
int main()
{
  struct Card a1[MAX],a2[MAX],tmp;
  int i,j,tmp2;
  int min,x,kt=1;
  char y,tmp1;
  scanf("%d%c",&x,&y);
  for(i=0;i<x;i++)
    {
      scanf("%c%c%c",&a1[i].suit,&a1[i].value,&y);
      a2[i] = a1[i];
    }

  for(i=0;i<x;i++)
    {
      for(j=x-1;j>i;j--)
	{
	  if(a1[j].value < a1[j-1].value)
	    {
	      tmp = a1[j];
	      a1[j] = a1[j-1];
	      a1[j-1] = tmp;
	    }
	}
    }

  for(i=0;i<x;i++)
    {
      min = i;
      for(j=i;j<x;j++)
	{
	  if(a2[j].value < a2[min].value)
	    {
	      min = j;
	    }
	}
      if(i!=min)
	{
	  tmp = a2[i];
	  a2[i] = a2[min];
	  a2[min] = tmp;
	}
    }
  for(i=0;i<x;i++)
    {
      printf("%c%c",a1[i].suit,a1[i].value);
      if(i != x-1)
	{
	  printf(" ");
	}
      else printf("\n");
    }
  printf("Stable\n");
 for(i=0;i<x;i++)
    {
      printf("%c%c",a2[i].suit,a2[i].value);
      if(i != x-1)
	{
	  printf(" ");
	}
      else printf("\n");
    }
 for(i=0;i<x;i++)
   {
     if(a1[i].suit != a2[i].suit)
       {
	 printf("Not stable\n");
	 kt = 0;
	 break;
       }
   }
 if(kt==1)
   {
     printf("Stable\n");
   }
 return 0;
}

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

vector<int> operator^(const vector<int> &a, const vector<int> &b) {
    vector<int> res((int)a.size());
    for (int i = 0; i < (int)a.size(); ++i)
        res[i] = (a[i] ^ b[i]);
    return res;
}

bool operator<(const vector<int> &a, const vector<int> &b) {
    for (int i = 0; i < (int)a.size(); ++i) {
        if (a[i] == b[i]) continue;
        return a[i] < b[i];
    }
    return false;
}

const int mod = 998244353;

int main() {
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            scanf("%d", &a[i][j]);
    }
    vector<vector<int>> basis;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)basis.size(); ++j)
            a[i] = min(a[i], a[i] ^ basis[j]);
        if (count(a[i].begin(), a[i].end(), 1) > 0)
            basis.push_back(a[i]);
    }
    int way = 1;
    for (int i = 0; i < n - (int)basis.size(); ++i)
        way = way * 2 % mod;
    int ans = 1;
    for (int i = 0; i < n; ++i)
        ans = ans * 2 % mod;
    ans = (ans + mod - way) % mod;
    int mult = 1;
    for (int i = 0; i < m - 1; ++i) 
        mult = mult * 2 % mod;
    printf("%d\n", ans * 1ll * mult % mod);
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

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

  bool f = true;
  do {
    s.pop_back();
    int n = s.size();
    if(n%2 == 0) {
      string x = s.substr(0, n/2);
      string y = s.substr(n/2);
      if(x == y) f = false;
    }
  } while(f);

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

Measured memory_bytes: 256