akhauriyash/Code-Regression huggingface dataset:
class NullNode():
    def __init__(self):
        self.id = None

null_node = NullNode()
class Node():
    def __init__(self, id):
        global null_node
        self.id = id
        self.parent = null_node
        self.left = null_node
        self.right =  null_node

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

import sys


n = int(sys.stdin.readline())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        out = ' ' + ' '.join(inorder_list)
        print(out)
        out = ' ' + ' '.join(preorder_list)
        print(out)




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

int N;
int a[10000];
int count=0;
int main() {
  cin >> N ;
  for (int i =0;i<N;i++){
      cin >> a[i] ;
      while (a[i]%2==0){
       count++;
       a[i] /=2;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
char s[100005];
int main(){
	int biaoji=0;
	scs(s+1);
	int n=strlen(s+1);
	rep(i,1,n)if(s[i]!=s[n+1-i])biaoji=1;
	rep(i,1,(n-1)/2)if(s[i]!=s[(n-1)/2+1-i])biaoji=1;
	rep(i,(n+3)/2,n)if(s[i]!=s[n+(n+3)/2-i])biaoji=1;
	if(biaoji==1)pf("No\n");
	else pf("Yes\n");	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {putchar('-');x = -x;}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int g[105][105];
int a[105],b[105],c[105],d[105],N,matk[105];
bool vis[105];
bool match(int u) {
    for(int i = 1 ; i <= 100 ; ++i) {
	if(g[u][i] && !vis[i]) {
	    vis[i] = 1;
	    if(!matk[i] || match(matk[i])) {
		matk[i] = u;
		return true;
	    }
	}
    }
    return false;
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) {read(a[i]);read(b[i]);}
    for(int i = 1 ; i <= N ; ++i) {read(c[i]);read(d[i]);}
    for(int i = 1 ; i <= N ; ++i) {
	for(int j = 1 ; j <= N ; ++j) {
	    if(a[i] < c[j] && b[i] < d[j]) g[i][j] = 1;
	}
    }
    int ans = 0;
    for(int i = 1 ; i <= N ; ++i) {
	memset(vis,0,sizeof(vis));
	if(match(i)) ++ans;
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}


Measured memory_bytes: 256
N,X=map(int,input().split())
L=[int(x)for x in input().split()]

count=0
D=0
n=0
for i in range(0,N):
    n+=1
    if(D>X):
        break
    else:
        count+=1
        D=D+L[i]
    
if(n==N and D<=X):
    count+=1
print(count)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
public class Program {
    public static void Main() {
        string[] str = Console.ReadLine().Split(' ');
        int A = int.Parse(str[0]);
        int B = int.Parse(str[1]);
        int C = int.Parse(str[2]);

        if((B+C)>A){
            Console.WriteLine((B+C)-A);
        } else {
            Console.WriteLine(0);
        }
    }
}

Measured memory_bytes: 11092
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ll p,q,a,n;
/*
 gcd : 最大公約数
 lcm : 最小公倍数
 */
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }

ll rec(ll x,ll P,ll Q,ll dep){
    ll ret = 0;
    if(p*Q == P*q) return 1;
    if(p*Q < P*q) return 0;
    if(dep == n) return 0;
    for(ll X = x; X*Q <= a; X++){
        ret += rec(X,P*X+Q,Q*X,dep+1);
    }
    return ret;
}
ll solve(){
    ll res = 0;
    res = rec(1,0,1,0);
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    while(cin >> p >> q >> a >> n,p){
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
#define int long long

vector<int> g[100001];

int dp[100001][2];
const int mod = 1e9+7;

int mul(int a,int b){
	return (a*b)%mod;
}


pair<int,int> dfs(int a, int parent) {
    int all_white = 1; // means: my vertex can be painted black
    int sth_is_black = 0;
    for(int b : g[a]) {
        if(b != parent) {
            pair<int,int> p = dfs(b, a);
            // p.first is the number of ways to color the subtree
            // such that 'b' is black
            int memo_all_white = all_white;
            all_white = mul(all_white, p.second);
            sth_is_black = (mul(memo_all_white, p.first)
                + mul(sth_is_black, p.first + p.second)) % mod;
        }
    }
    return make_pair(all_white, (all_white + sth_is_black) % mod);
}

signed main(){

	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		g[x-1].push_back(y-1);
		g[y-1].push_back(x-1);
	}
	memset(dp,0,sizeof dp);
	pair<int,int> ans=dfs(0,-1);

	cout<<(ans.first+ans.second)%mod<<endl;

}

Measured memory_bytes: 14208
#include<stdio.h>
int main(void) {
	int K, A, B;
	scanf("%d\n", &K);
	scanf("%d %d", &A, &B);
	if (B - A >= K) {
		printf("OK");
		return 0;
	}
	if ((A-1) / K == B / K - 1) {
		printf("OK");
	}
	else printf("NG");

	return 0;
}


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

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    long c=0;
    for (int i = 0; i < n; ++i) {
        if(a[i]%2==1){
            cout<<"first"<<endl;
            return 0;
        }
    }
    cout<<"second"<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(long i=(long)(m) ; i < (long) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x 2.0)
// vector<vector<int>> data(i, vector<int>(j))
// vector<vector<vector<char>>> data(N, vector<vector<char>>(3, vector<char>(3)))


int main() {
  long c;
  long ans;
  string str;
  bool flag = false,five = false;
  cin >> str;
  int size = str.size();
  reverse(str.begin(), str.end());
  rep(i,size){
    c = str.at(i) - '0';
    if(flag){
      c++;
    }
    if(c>5){
      ans += 10-c;
      flag = true;
      five = false;
    }else if(c==5){
      if(i != size-1){
        if(str.at(i+1)-'0'>4){
          flag = true;
        }else{
        flag = false;
        }
      }else{
        flag = false;
      }
      ans += 5;
    }else{
      ans += c;
      flag = false;
      five = false;
    }
  }
  if(flag){ans++;}
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1412
#include<stdio.h>
#include<stdlib.h>

int func(int num);

int main() {
    int n = 0;
    int i,start=1000;
    int a[100]={0};
    //int max[100]={0};//極大
    //int min[100]={0};//極小
    int trend[100]={0};//1か-1

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
        scanf("%d",&(a[i]));
    }
    //初期トレンドを探る
    int point=1;
    int nt=0;
    while(point<=n) {

        if (a[0] < a[point]) {
            trend[0] = -1;
            nt=1;
            break;
        } else if (a[0] > a[point]) {
            trend[0] = 1;
            nt=-1;
            break;
        } else point++;
    }
    if(nt==0)//ずっと株価が同じだｄった
    {
        printf("%d",start);
        return 0;
    }

    for(i=1;i<n;i++)
    {
        if(a[i-1]<a[i])//上昇トレンド
        {
            if(nt==-1)
            {
                trend[i-1]=-1;
                nt=1;
            }
        }
        else if(a[i-1]>a[i])//下降トレンド
        {
            if(nt==1)
            {
                trend[i-1]=1;
                nt=-1;
            }
        }

        if(i==n-1&&nt==1)trend[n-1]=1;
    }

    int lasttrend=0;

    for(i=0;i<n;i++)
    {
        if(trend[i]==1)lasttrend=i;
    }

    long long int kabu=0;
    long long int money=(long long int)start;
    for(i=0;i<=lasttrend;i++)
    {
        if(trend[i]==-1)
        {
            kabu+=(money/(long long int)a[i]);
            money=(money%(long long int)a[i]);
        }
        else if(trend[i]==1)
        {
            money+=(kabu*(long long int)a[i]);
            kabu=0;
        }
        //printf("%d ",money);
    }
    /*
    printf("\n");
    for(i=0;i<n;i++)
    {
        printf("%d ",trend[i]);
    }
     */
    printf("%lld",money);
}

Measured memory_bytes: 1732
//g++ -std=c++14 test.cpp -o test.out
//入出力：http://kaitei.net/cpp/iostream/
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int N;
string S,T;
string ans="";

void solve(){
	for(int i=0;i<N;i++){
		ans.append(1,S[i]);
		ans.append(1,T[i]);
	}
}

int main(){
	cin >> N;
	cin >> S >> T;

	solve();

	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
  private static int solve(char[] cs) {
    int n = cs.length;
    int count = 0;
    for (int i = 0; i < n / 2; i++) {
      if (cs[i] != cs[n - i - 1]) {
        count++;
      }
    }
    return count;
  }
  
  private static void execute(ContestReader reader, PrintWriter out) {
    char[] cs = reader.nextCharArray();
    out.println(solve(cs));
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 22356
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    int counter=1;
    int MAX=1;
    cin>>N;
    int MASU[N+1];
    
    for(int i=0;i<N;i++)
    {
        cin>>MASU[i];
    }

    MASU[N]=0;
    for(int i=0;i<N;i++)
    {
        if(MASU[i]==1&&MASU[i+1]==1)
        {
            counter++;
        }
        else if(MASU[i]==1&&MASU[i+1]==0)
        {
            counter++;
            if(MAX<counter)
            {
                MAX=counter;
            }
            counter=1;
        }
    }

    cout<<MAX<<endl;
}


Measured memory_bytes: 3116
#include<iostream>
using namespace std;
int main(){
  long long h,w,ans=0;
  cin >> h >> w;
  if(h==1 || w==1){
    ans=1;
  }
  else{
    if(h%2==0 || w%2==0){
      ans=(h*w)/2;
    }
    else{
      ans=(h*w)/2 + 1;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
# a: 総数hiki， b: 足の数
a, b = map(int, input().split())

# かめiひき
for i in range(a+1):
  total = 4*i + 2*(a-i)
  if total == b:
    ans = 'Yes'
    break
  else:
    ans = 'No'

print(ans)

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

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

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

	int apos,bpos,cnt = 0;

	do{
		if(a == c) apos = cnt;
		if(b == c) bpos = cnt;
		cnt++;
	}while(next_permutation(c.begin(), c.end()));

	cout<<abs(apos-bpos)<<endl;	
}

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

int N;

int main() {
    cin >> N;
    int cnt = 0, a;
    for (int i=1; i<=N; i++) {
        cin >> a;
        if (i % 2 != 0 && a % 2 != 0) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int M = 0;
    cin>>M;
    for (int m = 0; m < M; m++) {
        string data = "";
        cin>>data;
        map<string,int> trains;
        trains[data] = 1;
        for (int i = 1; i < data.size(); i++) {
            string l1 = data.substr(0, i);
            string r1 = data.substr(i, data.size()-i);
            string l2 = l1;
            string r2 = r1;
            reverse(l2.begin(), l2.end());
            reverse(r2.begin(), r2.end());

            trains[l1+r2] = 1;
            trains[l2+r1] = 1;
            trains[l2+r2] = 1;
            trains[r1+l1] = 1;
            trains[r1+l2] = 1;
            trains[r2+l1] = 1;
            trains[r2+l2] = 1;
        }
        cout<<trains.size()<<endl;
    }
}

Measured memory_bytes: 3276
#include<bits/stdc++.h>
#define LL long long 
using namespace std;

const int MOD = 1e9+7;
const int MAX = 1e6+10;
const int INF = 0x3fffffff;
bool a[MAX];

int C(int a,int b){
    if(a<b) return 0;
    else return a/b+C(a/b,b);
}
void init(){
    memset(a,true,sizeof(a));
    a[0]=a[1]=false;
    for(int i=2;i<=MAX;i++){
        if(a[i]){
            for(int j=i+i;j<MAX;j+=i){
                a[j]=false;
            }
        }
    }
}
int main(){
    int n;
    init();
    while(scanf("%d",&n)!=EOF){
        LL sum=1;
        int i=2;
        while(i<=n){
            if(a[i]){
                sum=sum*(LL)(C(n,i)+1)%MOD;
            }
            i++;
        } 
        printf("%lld\n",sum);
    }

    return 0;
}

Measured memory_bytes: 1280
#include<iostream>
using namespace std;
int main()
{
  int a,b;
  cin >> a >> b;

  if (a>b)
    cout <<"a > b"<<endl;
    else if (a<b)
        cout <<"a < b"<<endl;
    else if (a==b)
        cout <<"a == b"<<endl;
    return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
#define int long long

inline void addEdge(vector<int> adj[], int u, int v) {
	adj[u].push_back(v);
}

void dfs(int i, vector<int> adj[], vector<int> &dp, vector<int> &vis) {
	vis[i] = 1;

	for (int j = 0; j < adj[i].size(); ++j) {
		if (!vis[adj[i][j]])
			dfs(adj[i][j], adj, dp, vis);

		dp[i] = max(dp[i], 1 + dp[adj[i][j]]);
	}
}

int32_t main() {
	int n, m;
	cin >> n >> m;

	vector<int> adj[n + 1];
	vector<int> dp(n + 1);
	vector<int> vis(n + 1);

	int a, b;
	for (int i = 0; i < m; ++i) {
		cin >> a >> b;
		addEdge(adj, a, b);
	}

	for (int i = 1; i <= n; ++i)
		if (!vis[i])
			dfs(i, adj, dp, vis);

	cout << *max_element(dp.begin(), dp.end()) << "\n";

	return 0;
}


Measured memory_bytes: 10752
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <stdio.h>
using namespace std;

int a, b, ans;

int main() {
	
	cin >> a >> b;

	if (a < b) {
		ans += b;
		b--;
	}
	else {
		ans += a;
		a--;
	}
	if (a < b) {
		ans += b;
		b--;
	}
	else {
		ans += a;
		a--;
	}

	cout << ans << endl;

	return 0;
}



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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,U,V; cin>>n>>U>>V;
    vector<vi> adj(n+1);
    rep(i,n-1){
        int a,b; cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    queue<int> Q;
    vi dist(n+1, -1);
    dist[V] = 0;
    Q.push(V);
    while(Q.size()){
        int v = Q.front(); Q.pop();
        for(auto u:adj[v]){
            if (dist[u]==-1){
                dist[u] = dist[v]+1;
                Q.push(u);
            }
        }
    }
    vi Tdist(n+1, -1);
    Tdist[U] = 0;
    Q.push(U);
    while(Q.size()){
        int v = Q.front(); Q.pop();
        for(auto u:adj[v]){
            if (Tdist[u]==-1){
                Tdist[u] = Tdist[v]+1;
                Q.push(u);
            }
        }
    }
    int ans=-1;
    FOR(i,1,n){
        if (adj[i].size()==1 && dist[i]>Tdist[i]){
            ans = max(ans, dist[i]);
        }
    }
    ans--;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 6656
N = int(input())
A = input()
B = input()
C = input()

base = []
for i in range(N):
    if (A[i] == B[i]):
        base.append(A[i])
    elif A[i] == C[i]:
        base.append(A[i])
    elif B[i] == C[i]:
        base.append(B[i])
    else:
        base.append(A[i])

def count(X):
    counter = 0
    for i in range(N):
        if X[i] != base[i]:
            counter += 1
    return counter

print(count(A)+count(B)+count(C))

Measured memory_bytes: 3064
require 'set'

S=gets.chomp
T=gets.chomp

used = Set.new
to = {}
from = {}
(?a..?z).each do |c|
  to[c] = c
  from[c] = c
end
S.chars.zip(T.chars).each do |s, t|
  if to[s] == t
    used << t
    next
  end
  if used.include?(to[s]) || used.include?(t)
    puts :No
    exit
  end
  used << t
  ts, ft = to[s], from[t]
  fts = from[ts]
  to[fts], from[t]  = t,  fts
  to[ft],  from[ts] = ts, ft
end
puts :Yes


Measured memory_bytes: 32600
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define ABS(a) (((a) >= 0) ? (a) : -(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define RFOR(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define NINTH_POWER_OF_TEN 1000000000
#define LL_INF (numeric_limits<long long>::max()/2)
#define int long long

typedef long long ll;
typedef pair<int, int> Pair;

const int kMaxN = 200000;

int N;
int P[kMaxN+1];
int ans = LL_INF;

signed main() {
  cin >> N;
  FOR(i, 1, N) { cin >> P[i]; }

  unordered_map<int, int> h;
  int a[N+1], b[N+1];
  FOR(i, 1, N) { a[i] = 0; b[i] = 0; }
  FOR(i, 1, N) { h[P[i]] = i; }
  FOR(i, 1, N) {
    if (P[i] == N) { continue; }
    int ni = h[P[i]+1];
    if (ni > i) { a[ni] = a[i]+1; }
  }
  RFOR(i, N, 1) {
    if (P[i] == 1) { continue; }
    int ni = h[P[i]-1];
    if (ni < i) { b[ni] = b[i]+1; }
  }

  FOR(i, 1, N) {
    ans = MIN(ans, N-1-a[i]-b[i]);
  }

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


Measured memory_bytes: 13128
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>

int dp[13][2][2][2][2];
int main(){
  std::string S;
  std::cin >> S;
  int n = S.length();
  std::vector<int > a(n+3);
  for (int i=0; i<n; i++){
    a[i] = int(S[i])-int('0');
  }
  dp[0][0][0][0][0]=1;
  for (int i=0; i<n; i++){
    for (int j=0; j<2; j++){
      for (int k=0; k<2; k++){
        for (int l=0; l<2; l++){
          if (dp[i][j][k][l][1]!=0){
            dp[i+1][1][k][l][1]+=dp[i][j][k][l][1];
            dp[i+1][j][1][l][1]+=dp[i][j][k][l][1];
            dp[i+1][j][k][1][1]+=dp[i][j][k][l][1];
          }
          if (dp[i][j][k][l][0]!=0){
            if (a[i]>3){
              dp[i+1][1][k][l][1]+=dp[i][j][k][l][0];
            } else if (a[i]==3){
              dp[i+1][1][k][l][0]+=dp[i][j][k][l][0];
              //printf("dp[%d][1][%d][%d][0]++\n",i+1,k,l);
            }
            if (a[i]>5){
              dp[i+1][j][1][l][1]+=dp[i][j][k][l][0];
            } else if (a[i]==5){
              dp[i+1][j][1][l][0]+=dp[i][j][k][l][0];
            }
            if (a[i]>7){
              dp[i+1][j][k][1][1]+=dp[i][j][k][l][0];
            } else if (a[i]==7){
              dp[i+1][j][k][1][0]+=dp[i][j][k][l][0];
            }

          }
        }
      }
    }
  }
  int ans = dp[n][1][1][1][1]+dp[n][1][1][1][0];
  //printf("%d\n", ans);
  if (n>3){
    for (int i=3; i<=n-1; i++){
      ans += pow(3, i)-3*pow(2,i)+3;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
import sys


def input():
    return sys.stdin.readline().strip()


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

    ans = [K - A[i] + A[i - 1] for i in range(1, N)]
    print(min(min(ans), A[-1] - A[0]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 25840
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define y1 zzz
#define fi first
#define se second
#define PII pair<int,int>
#define PII2 pair<int,PII >
#define PII3 pair<PII,int >
#define PII4 pair<PII,PII >
#define all(x) (x).begin(),(x).end()
#define pb push_back
int n,a,b;
void solve()
{
    cin>>a>>b;
    for(int i=1;i<=100000;i++)
    {
        if(i*8/100==a&&i*10/100==b)
        {
            cout<<i;
            return;
        }
    }
    cout<<-1;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("STRWC.inp","r",stdin);
    //freopen("STRWC.out","w",stdout);
    //int t;cin>>t;while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();
        int X = sc.nextInt();

        int sum = X;

        for (int i = 0; i < N; i++) {
            int A_n = sc.nextInt();
            sum += ((D - 1) / A_n) + 1;
        }

        System.out.println(sum);
    }
}


Measured memory_bytes: 21716
#include <stdio.h>
#include <stdlib.h>

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

    int taste[N];
    for (int i = 0; i < N; i++){
        taste[i] = L + i;
    }

    int SUM = 0;
    for (int i = 0; i < N; i++){
        SUM += taste[i];
    }

    int DIF = abs(SUM - (SUM - taste[0]));
    int ans = SUM - taste[0];

    for (int i = 1; i < N; i++){
        int x = SUM - taste[i];
        if (abs(SUM - x) < DIF){
            DIF = abs(SUM - x);
            ans = x;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 128
i = list(map(int, input().split())) #s_1 s_2を分割して取得し、sに値を入れる

ws = i[0]
cs1 = i[1]
cs2 = i[1]
t = i[2]
n = 1
while ws > cs1:
    n += 1
    cs1 += cs2
tt = n * t
print(tt)


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

int main() {
  ll N;
  cin >> N;
  if (N % 2 == 1) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  N /= 2;
  while (1) {
    N /= 5;
    if (N == 0) break;
    ans += N;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3580
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
u = set(s) | set(t)
l = []

for i in u:
    cnt = 0
    for j in s:
        if i == j:
            cnt += 1
    for j in t:
        if i == j:
            cnt -= 1
    l.append(cnt)

print(max(0, max(l)))

Measured memory_bytes: 3064
X,Y = map(int,input().split())
whole = []
for i in range(X):
  now = input()
  if now == '.' * Y:
    pass
  else:
    add = []
    for i in range(Y):
      if now[i] == '.':
        add.append(0)
      else:
        add.append(1)
    whole.append(add)
j = 0
while j < len(whole[0]):
  for i in range(len(whole)):
    if whole[i][j] == 1:
      j += 1
      break
  else:
    for i in range(len(whole)):
      del whole[i][j]
for i in range(len(whole)):
  now = whole[i]
  ans = ''
  for j in range(len(now)):
    if now[j] == 0:
      ans += '.'
    else:
      ans += '#'
  print(ans)

Measured memory_bytes: 3188
package main

import (
	"fmt"
)

func main() {
	var a string
	var b string
	fmt.Scan(&a)
	fmt.Scan(&b)

	count := len([]rune(a))
	result := 0
	for i := 0; i < count; i++ {
		if a[i] != b[i] {
			result++
		}
	}
	fmt.Println(result)
}


Measured memory_bytes: 4492
def calc_pow(a, n, mod):
    rev_bin_n_str = bin(n)[2:][::-1]
    val = 1
    base_a = a
    for b in rev_bin_n_str:
        if b == '1':
            val *= base_a
            val %= mod
        base_a *= base_a
        base_a %= mod
    return val


def ext_euc(a, b):
    # return (x, y, gcd(a, b)) such that ax + by = gcd(a, b)
    # assumed a > b
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    if a > mod:
        x, _, _ = ext_euc(a, mod)
    else:
        _, x, _ = ext_euc(mod, a)
    return x % mod


def calc_comb(n, k, mod):
    if k > n / 2:
        return calc_comb(n, n - k, mod)
    comb = 1
    for i in range(k):
        comb *= (n - i)
        comb %= mod
        comb *= mod_inv((k - i), mod)
        comb %= mod
    return comb


def main():
    MOD = 10**9 + 7
    n, a, b = list(map(int, input().split(' ')))
    ans = calc_pow(2, n, MOD) - calc_comb(n, a, MOD) - calc_comb(n, b, MOD) - 1
    print(ans % MOD)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, l;
    cin >> n >> m >> l;
    int a[n][m], b[m][l];
    long long int c[n][l];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < l; j++) {
            cin >> b[i][j];
        }
    }
    long long int sum;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < l; j++) {
            sum = 0;
            for(int k = 0; k < m; k++) {
                sum += a[i][k] * b[k][j];
            }
            c[i][j] = sum;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < l; j++) {
            if(j == 0) cout << c[i][j];
            else cout << " " << c[i][j];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3156
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
#define range(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) range(i,0,n)
const ll INF=1e10;
#define pb push_back

int main(){
    int n,m; cin >> n >> m;
    char ch; //コンマを読み捨てるための変数
    vint a(m),b(m),c(m),d(m);
    vector<vll> K(n+1,vll(n+1,INF));
    rep(i,m){
        int a,b; cin >> a >> ch >> b >> ch;
        cin >> K[a][b] >> ch >> K[b][a];
    }
    int s,g,v,p; cin >> s >> ch >> g >> ch >>  v >> ch >> p;

    range(k,1,n+1) range(i,1,n+1) range(j,1,n+1){
        if(K[i][j]>K[i][k]+K[k][j]){
            K[i][j]=K[i][k]+K[k][j];
        }
    }
    cout << v-p-K[s][g]-K[g][s] << endl;
}



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

int n,k,s,ans,sum;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> n >> k >> s,n){
        ans=0;
        for (int bit=0;bit<(1<<n);++bit){
            if (__builtin_popcount(bit)!=k) continue;
            sum=0;
            for (int i=0;i<n;++i){
                if (bit&1<<i) sum+=i+1;
            }
            if (sum==s) ++ans;
        }
        cout << ans << '\n';
    }
}


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

int main(){
  int v, e;
  cin >> v >> e;
  vector<int> g[v];
  vector<int> h(v);
  rep(i,e){
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    h[b]++;
  }
  queue<int> que;
  rep(i,v) if(h[i] == 0) que.push(i);
  vector<int> ans;
  while(!que.empty()) {
    int p = que.front(); que.pop();
    ans.push_back(p);
    for(auto i : g[p]) {
      h[i]--;
      if(h[i] == 0) que.push(i);
    }
  }
  rep(i,v) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 3824
n,k=map(int,input().split())
if k>(n-2)*(n-1)//2:
	print(-1)
	exit()
elif k==(n-2)*(n-1)//2:
	print(n-1)
	for i in range(n-1):
		print(1,i+2)
	exit()
ans=[]
for i in range(n-1):
	ans.append((1,i+2))
cnt=(n-2)*(n-1)//2
a=2
b=3
while cnt>k:
	cnt-=1
	ans.append((a,b))
	b+=1
	if b==n+1:
		b=a+2
		a+=1
print(len(ans))
for x in ans:
	print(*x)

Measured memory_bytes: 3992
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
string S, T;

void input() {
  cin>>N>>K;
  cin>>S;
  ;

} 

vector<int> V;

void solve() {
  V.resize(N);
  // char R='R',L='L';
  // string s1="LRRL",s2="RLLR",s3="LRLRRL",s4="RLRLLR",

  rep(i,0,N-1){
    if (S[i]=='R')V[i]=1;
    else V[i]=0;
  }

  int cnt=0;
  int prv=-1;

  int state=0;
  int cntk=0;

//debugv(V);
  rep(i,0,N-1){
    if (cntk>=K)break;
    if(i==0){
      prv=V[i];continue;
    }
  //  debug(i);debug(state);


    if (state==0){
      if (prv != V[i]){
   //     debug(i);
        state=1;
        cnt=1;
        prv=V[i];
        continue;
      }
      else {
        prv=V[i];
        continue;
        }
    }
    else if (state==1){
      if (prv==V[i]){
        cnt++;
        prv=V[i];
        continue;
      }
      else {
        state=0;
        rrep(k,i-1,i-cnt){
          V[k]=!V[k];
        }
     //   cout<<"written"<<endl;
    //    debugv(V);
        prv=V[i];
        cnt=0;
        cntk++;
        continue;
      }
    }
  }

   // debugv(V);


  int ans = 0;
  int prv2=V[0];
  rep(i,1,N-1){
    if (prv2==V[i]){
      ans++;
    }
    prv2=V[i];
  }
  if (cntk<K){
    ans = N-1;
  }
  cout<<ans<<endl;



  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rep(n) for(int i = 0; i < n; i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;

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

    vector<int> h(n), dp(n);

    for(int & x : h)
        cin>>x;

    dp[1] = abs(h[1] - h[0]);

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

    cout<<dp[n-1]<<endl;

    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
    #define ll long long int
    using namespace std;
    int main(){
        ll a,b,c,t,ans=0;
            cin>>a>>b>>c;
            if(b==0)cout<<0<<endl;
            else {
                ll x=a/(c+b);
                ll y=a%(c+b);
                if(y==0)ans=b*x;
                else {
                        ll mot=x*(b+c);
                        ll z=a-mot;
                    if(z>=b)ans=(b*x)+b;
                    else ans=(b*x)+z;
                }
                cout<<ans<<endl;
            }
    return 0;
    }


Measured memory_bytes: 256
#pragma GCC optimize "O3"

#define F first
#define S second
#define G0(x) get<0>(x)
#define G1(x) get<1>(x)
#define G2(x) get<2>(x)

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef tuple<int, int, int> PIII;

constexpr int N = 3000, M = 300, INF = INT_MAX;

int n, m, cap, dis[2*N+2], tmp_dis[2*N+2];
unordered_map<string, int> sid;
vector<PII> adj[2*N+2];
bool is_lpg[2*N+2];

inline void init() {
  sid.clear();
  cap *= 10;
  memset(is_lpg, 0, sizeof(is_lpg));
}
inline int solve() {
  init();
  string s0, s1;
  cin >> s0 >> s1;
  sid.emplace(s0, 0);
  adj[0].clear();
  sid.emplace(s1, 1);
  adj[1].clear();
  for(int i = 0; i<n; ++i) {
    int d;
    cin >> s0 >> s1 >> d;
    if(!sid.count(s0)) {
      adj[sid.size()].clear();
      sid.emplace(s0, sid.size());
    }
    if(!sid.count(s1)) {
      adj[sid.size()].clear();
      sid.emplace(s1, sid.size());
    }
    int id0 = sid[s0], id1 = sid[s1];
    adj[id0].emplace_back(id1, d);
    adj[id1].emplace_back(id0, d);
  }
  is_lpg[0] = is_lpg[1] = true;
  for(int i = 0; i<m; ++i) {
    cin >> s0;
    is_lpg[sid[s0]] = true;
  }
  int mid = sid.size();
  fill(dis, dis+mid, INF);
  priority_queue<PII, vector<PII>, greater<PII>> pq0;
  pq0.emplace(0, 0);
  while(!pq0.empty()) {
    PII nxt0 = pq0.top(); pq0.pop();
    fill(tmp_dis, tmp_dis+mid, INF);
    tmp_dis[nxt0.S] = nxt0.F;
    priority_queue<PIII, vector<PIII>, greater<PIII>> pq1;
    pq1.emplace(nxt0.F, cap, nxt0.S);
    while(!pq1.empty()) {
      PIII nxt1 = pq1.top(); pq1.pop();
      for(auto &v : adj[G2(nxt1)])
        if(G1(nxt1) >= v.S && G0(nxt1) + v.S < tmp_dis[v.F]) {
          tmp_dis[v.F] = G0(nxt1) + v.S;
          pq1.emplace(tmp_dis[v.F], G1(nxt1)-v.S, v.F);
        }
    }
    for(int i = 0; i<mid; ++i)
      if(is_lpg[i] && tmp_dis[i] < dis[i]) {
        dis[i] = tmp_dis[i];
        pq0.emplace(dis[i], i);
      }
  }
  return (dis[1] == INF) ? -1 : dis[1];
}
int main() {
  while(scanf("%d %d %d", &n, &m, &cap) == 3 && n)
    printf("%d\n", solve());
}

Measured memory_bytes: 4460
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

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

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

int main(){
  int n;
  cin >> n;
  int c[n];
  rep(i,n)cin >> c[i];
  sort(c,c+n);
  mint ans = 0;
  mint s = mint(2).pow(n-1);
  mint dif = s/2;
  rep(i,n){
    ans += s*c[n-1-i];
    s += dif;
  }
  ans *= mint(2).pow(n);
  cout << ans << endl;
}

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

int main() {
	long long N, M, V, P;
	vector<long long> A;
	vector<long long> SUM;
	cin >> N >> M >> V >> P;
	A.resize(N);
	SUM.resize(N + 1);
	SUM[0] = 0;
	for (int i = 0; i < N; i++) cin >> A[i];
	sort(A.begin(), A.end(), greater<long long>());
	for (int i = 0; i < N; i++) SUM[i + 1] = SUM[i] + A[i];
	long long L = 0, R = N;
	while (R - L > 1) {
		long long MID = (L + R) / 2;
		if (MID <= P - 1) {
			L = MID;
			continue;
		}
		if (A[MID] + M < A[P - 1]) {
			R = MID;
			continue;
		}
		long long COUNT = SUM[MID] - SUM[P - 1];
		long long X = max(0LL, V - (N - MID) - (P - 1));
		COUNT += X * M;
		long long Y = max(0LL, MID - (P - 1));
		long long MAX;
		if (COUNT % Y == 0) MAX = COUNT / Y;
		else MAX = COUNT / Y + 1;
		if (A[MID] + M < MAX) R = MID;
		else L = MID;
	}
	cout << R << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define INF 1000000000000
#define MOD 10000007
#define PI 3.14159265359
#define dij priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>
typedef long long ll;
//

int main(){
    int n;cin>>n;
    vector<ll> v(n);
    rep(i,n){
        cin>>v[i];
    }
    ll ans=0;
    ll ch=v[0];
    rep(i,n-1){
        if(v[i+1]>=ch){
            ch=v[i+1];
        }else{
            ans+=ch-v[i+1];
            v[i+1]=ch;
            
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4832
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;

int main() {
    int N;
    cin >> N;
    static int cnt[5];
    char c[5] = {'M', 'A', 'R', 'C', 'H'};
    for(int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        for(int j = 0; j < 5; ++j)
            if(S[0] == c[j])
                cnt[j]++;
    }
    ll ans = 0;
    for(int i = 0; i < 5; ++i)
        for(int j = 1; i + j < 5; ++j)
            for(int k = 1; i + j + k < 5; ++k)
                ans += (ll)cnt[i] * cnt[i + j] * cnt[i + j + k];
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            int c = 0;
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (consum(i, j) == n) {
                        c ++;
                    }
                }
            }
            System.out.println(c);
        }
    }

    public static int consum(int a, int b) {
        return (b * (b + 1) - a * (a + 1))/ 2;
    }
}

Measured memory_bytes: 26704
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int W,H,N,ans=0;
    cin>>W>>H>>N;
    int x,y,befx,befy;
    cin>>x>>y;
    for(int i=1;i<N;i++){
        befx=x,befy=y;
        cin>>x>>y;
        if((befx<x&&befy<y)||(befx>x&&befy>y))ans+=max(max(befx,x)-min(befx,x),max(befy,y)-min(befy,y));
        else ans+=max(befx,x)-min(befx,x)+max(befy,y)-min(befy,y);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
    ll n;
    std::cin >> n;
    vector<ll> h(n);
    for (int i = 0; i < n; i++) {
        std::cin >> h[i];
    }
    ll res = 0;
    ll cnt = 0;
    for (int i = 1; i < n; i++) {
        if(h[i-1] >= h[i]){
            cnt++;
            res = max(res,cnt);
        }else{
            cnt = 0;
        }
    }
    
    std::cout << res << std::endl;
    
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
/*
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
*/
#define int long long
#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define showp(n) cerr<<n.fs<<", "<<n.sc<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", "}cerr<<endl

#define yes printf("Yes\n")
#define no printf("No\n")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using ull=unsigned long long;
using vi=vector<int>;
using pint=pair<int,int>;

const int INF=1LL<<55;

int tf;
int ans=0;

void solve(){
    ans = 0;
    int t;
    int i=1;
    while(true){
        t=pow(i,3);
        if(t>tf) break;
        ans=max(ans,t);
        i++;
    }
    int maxA=i;
    i=1;
    while(true){
        t=i*(i+1)*(i+2)/6;
        if(t>tf) break;
        ans=max(ans,t);
        i++;
    }
    int maxB=i;
    rep(i,maxA){
        rep(j,maxB){
            t=pow(i,3)+j*(j+1)*(j+2)/6;
            if(t>tf) break;
            ans=max(ans,t);
        }
    }
    cout<<ans<<endl;
    return;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int i=1;
    int t;
    
    while(cin>>tf,tf){
        solve();
    }

    return 0;
}


Measured memory_bytes: 3352
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
using namespace std;

int main() {
	int n;
	string s, t;

	cin >> n >> s >> t;

	string ans = "";
	for (int i = 0; i < s.size(); i++) {
		ans.push_back(s[i]);
		ans.push_back(t[i]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import heapq
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
v = list(map(int, input().split()))
myheap = []

for i in range(N):
	heapq.heappush(myheap, v[i])

for i in range(N - 1):
	a = heapq.heappop(myheap)
	b = heapq.heappop(myheap)
	heapq.heappush(myheap, (a + b) / 2)
	
print(myheap[0])


Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s=in.nextLine();//.toString();
        int len = s.length();
        for(int i=0,j=len/2-1;i<j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                System.out.println("No");
                return;
            }
        }
        for(int i=len/2+1,j=len-1;i<j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                System.out.println("No");
                return;
            }
        }
        for(int i=0,j=len-1;i<j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");

    }
}


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

int main(void) {
	int n;
	cin >> n;
	if (n < 10) {
		cout<< n;
	}
	else if (n < 100) {
		cout << 9;
	}
	else if(n<1000){
		cout << n - 90;
	} else if(n<10000){
		cout << 909;
	}
	else if (n < 100000) {
		cout << n - 90 - 9000;
	}
	else{
		cout << 90909;
	}
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

//Popularity Estimation
public class Main{

	class R implements Comparable<R>{
		String name;
		int p;
		public R(String name) {
			this.name = name;
		}
		public int compareTo(R o) {
			return p==o.p?name.compareTo(o.name):p-o.p;
		}
	}
	
	void run(){
		Scanner sc =  new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			R[] r = new R[n];
			boolean[][] u = new boolean[n][30];
			int[] num = new int[30];
			for(int i=0;i<n;i++){
				r[i] = new R(sc.next());
				int m = sc.nextInt();
				while(m--!=0){
					int d = sc.nextInt();
					u[i][d] = true;
					num[d]++;
				}
			}
			for(int i=0;i<n;i++){
				for(int j=0;j<30;j++){
					if(u[i][j]){
						r[i].p += n-num[j]+1;
					}
				}
			}
			Arrays.sort(r);
			System.out.println(r[0].p+" "+r[0].name);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 12000