akhauriyash/Code-Regression huggingface dataset:
import sys

def solve():
    n, a, b = map(int, sys.stdin.readline().split())
    h = [int(sys.stdin.readline().rstrip()) for i in range(n)]

    top = n * (max(h) + a - 1) // a
    btm = 0

    while top - btm > 1:
        mid = (top + btm) // 2

        if check(n, a, b, h, mid):
            top = mid
        else:
            btm = mid

    print(top)

def check(n, a, b, h, k):
    base = k * b
    dif = a - b
    cnt = 0

    for hi in h:
        if hi > base:
            cnt += (hi - base + dif - 1) // dif

            if cnt > k:
                return False

    return True

if __name__ == '__main__':
    solve()

Measured memory_bytes: 45404
s = list(map(int, list(str(input()))))
n = len(s)
ans = 0
for i in range(1 << n - 1):
    tmp = s[0]
    for j in range(n - 1):
        if (i >> j) & 1:
            ans += tmp
            tmp = s[j + 1]
        else:
            if j == 0:
                tmp = s[j] * 10 + s[j + 1]
            else:
                tmp = tmp * 10 + s[j + 1]
    ans += tmp
print(ans)


Measured memory_bytes: 3060
# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
used=[False for i in range(N)]
used[0]=True
p=1
L=[1]

for i in range(N+1):
    p=A[p-1]
    L.append(p)
    if used[p-1]:
        looper=p
        break
    used[p-1]=True

for i in range(len(L)):
    if L[-(2+i)]==looper:
        a=i+1
        b=len(L)-1-a
        break
if K>b:
    ans=L[b+(K-b)%a]
else:
    ans=L[K]

print(ans)

Measured memory_bytes: 32380
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf-8');
const N = parseInt(input);

for (let i = 1; i <= 9; ++i) {
  if (N % i !== 0) {
    continue;
  }
  if (N / i <= 9) {
    console.log('Yes');
    return;
  }
}
    
console.log('No');

Measured memory_bytes: 7372
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int i,k,n,m,max,idx = 0;
		n = sc.nextInt();
		m = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[m];
		int[] vote = new int[n];
		for(i = 0; i < n; i ++ ){
			a[i] = sc.nextInt();
			vote[i] = 0;
		}
		max = vote[0];
		for(k = 0; k < m; k ++ )b[k] = sc.nextInt();
		for(k = 0; k < m; k ++ ){
			for(i = 0; i < n; i ++ ){
				if(b[k] >= a[i]){
					vote[i] ++;
					break;
				}
			}
		}
		for(i = 0; i < n; i ++ ){
			if(max < vote[i]){
				max = vote[i];
				idx = i+1;
			}
		}
		System.out.println(idx);
		
	}

}

Measured memory_bytes: 33436
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	string s[105];
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
	}
	sort(s+1,s+1+n);
	for(int i=1;i<=n;i++)
	{
		cout<<s[i];
	}
}

Measured memory_bytes: 256
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10;

int main() {
	fast_cin();
	string s; cin >> s;
	int n = s.length() + 1;
	int p = 0;
	ll ans = 0;
	while (p < n - 1) {
		ll c1 = 0, c2 = 0;
		while (p < n - 1 and s[p] == '<') {
			++c1;
			++p;
		}
		while (p < n - 1 and s[p] == '>') {
			++c2;
			++p;
		}
		ans += max(c1, c2);
		ans += (c1 * (c1 - 1)) / 2;
		ans += (c2 * (c2 - 1)) / 2;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1172
use std::io;

fn main() {
    loop {
        let (h, w) = input();
        if (h, w) == (0, 0) {
            break;
        }

        for _ in 0..h {
            for _ in 0..w {
                print!("#");
            }
            println!("");
        }
        println!("");
    }
}

fn input() -> (i32, i32) {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    let mut iter = s.trim().split_whitespace();

    let a: i32 = iter.next().unwrap().parse().unwrap();
    let b: i32 = iter.next().unwrap().parse().unwrap();

    (a, b)
}



Measured memory_bytes: 5016
#include <bits/stdc++.h>
#include <cstdlib>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);

}
int main() {
    int kk;
    int ans = 0;
    cin >> kk;
    for (int i = 1; i <= kk; i++) {
       for (int j = 1; j <= kk; j++) {
           for (int k = 1; k <= kk; k++) {
               ans += gcd(gcd(i,j),k);
           }
       } 
    }
    
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 3620
from sys import exit
from itertools import accumulate,chain
n,*s=open(0).read().split()
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
    print("No")
    exit()
#pypyではinitialだめ
st=[[t_,min(accumulate(s_,lambda a,b: a+(1 if b=="(" else -1),initial=0))] for s_,t_ in zip(s,t)]

now=sum(map(lambda x:x[0],filter(lambda x:x[1]>=0,st)))
v=list(filter(lambda x:x[1]<0 and x[0]>=0,st))
w=list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)

for sub in chain(v,w):
    if now+sub[1]<0:
        print("No");exit()
    now+=sub[0]
print("Yes")


Measured memory_bytes: 119888
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  int m=0;
  int count=0;
  for(int i=0;i<n;i++)
  {
    if(a[i]==m+1)
    {
      m=a[i];
      count++;
    }
  }
  if(count==0)
  	cout<<-1<<endl;
  else
  	cout<<n-count<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
int x[10],i,j;
for(i=0;i<10;i++)
scanf("%d",&x[i]);
for(i=0;i<9;i++){
for(j=9;j>i;j--){
if(x[j-1]<x[j]){
int temp=x[j-1];
x[j-1]=x[j];
x[j]=temp;
}
}
}
for(i=0;i<3;i++)
printf("%d\n",x[i]);
return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define int long long
using namespace std;
using P=pair<int,int>;
using Graph=vector<vector<int>>;
using ll=long long;


ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}

//最小公倍数ダヨン
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

bool root(string s){
    int n=s.length();
    if(n==2){
        if(s[0]==s[1]){
            return true;
        }
        else return false;
    }
    if(n==3){
        if(s[0]==s[2]){
            return true;
        }
        else return false;
    }
 
    return false;
}
 


signed main(){
    int h,w,k; cin>>h>>w>>k;

    vector<vector<char>> grid(h,vector<char>(w));

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>grid[i][j];
        }
    }    

    int ans=0;

    for(int tmp=0;tmp<(1<<h);tmp++){
        for(int wide=0;wide<(1<<w);wide++){
            bitset<6> high(tmp);
            bitset<6> width(wide);
            int res=0;
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    if(grid[i][j]=='.') continue;
                    if(high.test(i)==1 || width.test(j)==1) continue;
                    else res++;
                }
            }
            if(res==k) ans++;
        }
    }

    cout<<ans<<endl;
}   

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;

  pair<pair<int,int>,int> p[M];
  for(int i=0;i<M;i++){
    cin >> p[i].first.first >> p[i].first.second;
    p[i].second = i;
  }

  sort(p,p+M);

  /*for(int i=0;i<M;i++){
    cout << p[i].first.first << " ";
    cout << p[i].first.second << " ";
    cout << p[i].second << endl;
  }*/

  int id[M];
  id[0]=1;
  for(int i=1;i<M;i++){
    if(p[i].first.first != p[i-1].first.first){
      id[i]=1;
    }else{
      id[i]=id[i-1]+1;
    }
  }

  pair<int,pair<int,int> > pp[M];
  for(int i=0;i<M;i++){
    pp[i].first = p[i].second;
    pp[i].second.first = p[i].first.first;
    pp[i].second.second = id[i];
  }


  sort(pp,pp+M);

  for(int i=0;i<M;i++){
    printf("%06d%06d\n",pp[i].second.first,pp[i].second.second);
  }
  return 0;
}

Measured memory_bytes: 4224
N = int(input())
W = list(map(int,input().split()))
Wleft = sum(W)
Wright = 0
i = N-1
absmin = 0
while Wleft > Wright:
  Wleft -= W[i]
  Wright += W[i]
  proabsmin = absmin*-1
  absmin = Wright - Wleft
  # print(i,Wright,Wleft)
  i -= 1

absmin = min([proabsmin,absmin])
print(absmin)

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

int main()
{
 int k;
 cin>>k;
  string S =  "ACL";
  string R;
  for(int i=1;i<=k;i++)
  {
    R = R + S;
  }
  cout<<R<<endl;
  return 0;
}

Measured memory_bytes: 3576
package main

import (
	"fmt"
)

func solve(a, b, c, x, coin int) int {
	if a < 0 || b < 0 || c < 0 || x < 0 {
		return 0
	}
	if x == 0 {
		return 1
	}

	switch coin {
	case 500:
		return solve(a-1, b, c, x-500, 500) + solve(a, b-1, c, x-100, 100) + solve(a, b, c-1, x-50, 50)
	case 100:
		return solve(a, b-1, c, x-100, 100) + solve(a, b, c-1, x-50, 50)
	case 50:
		return solve(a, b, c-1, x-50, 50)
	}
	return 0
}

func main() {

	var x, a, b, c int

	fmt.Scan(&a) // 500
	fmt.Scan(&b) // 100
	fmt.Scan(&c) // 50
	fmt.Scan(&x)
	
	fmt.Println(solve(a,b,c,x,500))

}

Measured memory_bytes: 512
import sys
sys.setrecursionlimit(10**6)

n = int(input())
h = list(map(int, input().split()))
# dp = [[None] * 10**6 for _ in range(n)]
dp = [None] * (n+1)

# Return the smallest cost to reach the idx
def solve(idx):
    if dp[idx] is not None:
        return dp[idx]

    if idx == 1:
        dp[idx] = abs(h[idx] - h[idx - 1])
    elif idx == 0:
        dp[idx] = 0
    else:
        # jump from idx - 1
        c1 = solve(idx - 1) + abs(h[idx] - h[idx - 1])

        # jump from idx - 2
        c2 = solve(idx - 2) + abs(h[idx] - h[idx - 2])

        dp[idx] = min(c1, c2)

    return dp[idx]

ans = solve(n-1)

print(ans)

Measured memory_bytes: 93720
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int m=a-b;

    if(m>c)
    {
        cout<<0<<endl;
    }
    else
    {
        cout<<c-m<<endl;
    }
    exit(0);
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int x,flag=0;
    cin>>x;
    std::deque<int> deq{105,104,103,102,101,100};
    for (int i=0;i<6;i++) {
        if (x%deq[i]==0) {
            cout<<1<<endl;
            flag=1;
            break;
        } else {
            int tmp=x/deq[i];
            for (int j=tmp;j>=1;j--) {
                for (int k=i+1;k<6;k++) {
                    if ((x-deq[i]*j)%deq[k]==0) {
                        cout<<1<<endl;
                        flag=1;
                        break;
                    }
                }
                if (flag==1) {
                    break;
                }
            }
        }
        if (flag==1) {
            break;
        }
    }
    if (flag==0) {
        cout<<0<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
int main()
{
    int E;
    std::cin >> E;

    int a = (E / 1000) % 10;
    int b = (E / 100) % 10;
    int c = (E / 10) % 10;
    int d = (E / 1) % 10;

    std::vector<std::vector<int>> P = {{1, 1, 1}, {1, 1, -1}, {1, -1, 1}, {1, -1, -1}, {-1, 1, 1}, {-1, 1, -1}, {-1, -1, 1}, {-1, -1, -1}};
    std::array<char, 3> op = {};
    for (int i = 0; i < 8; ++i) {
        if (a + P[i][0] * b + P[i][1] * c + P[i][2] * d == 7) {
            for (int j = 0; j < 3; ++j) {
                if (P[i][j] == 1) {
                    op[j] = '+';
                } else {
                    op[j] = '-';
                }
            }
        }
    }
    std::cout << a << op[0] << b << op[1] << c << op[2] << d << "=7" << std::endl;
    return 0;
}

Measured memory_bytes: 3628
s = input()
l = s[0:2]
r = s[2:]
a = int(l)
b = int(r)
if (0 == a or a>12 )and (b >0 and b <13):
    print('YYMM')
elif (a>0 and a<13) and (b ==0 or b>12):
    print('MMYY')
elif (a>0 and a<13) and (b>0 and b <13):
    print('AMBIGUOUS')
else:
    print('NA')

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

public class Main {
    void run() {
        while (true) {
            int N = readInt();
            if (N == 0) break;
            ArrayList<Rank> ranks = new ArrayList<Rank>();
            for (int i = 0; i < N; i++) {
                int id = readInt();
                int univ = readInt();
                int solve = readInt();
                int penalty = readInt();
                ranks.add(new Rank(id, univ, solve, penalty));
            }
            Collections.sort(ranks);
            HashMap<Integer, Integer> univCount = new HashMap<Integer, Integer>();
            int assign = 0;
            for (int i = 0; i < N; i++) {
                Rank r = ranks.get(i);
                Integer uao = univCount.get(r.univ);
                int ua = uao != null ? uao : 0;
                if ((assign < 10 && ua < 3) ||
                        (assign < 20 && ua < 2) ||
                        (assign < 26 && ua < 1)) {
                    sysout.println(r.id);
                    assign++;
                    univCount.put(r.univ, ua + 1);
                }
            }
        }
    }

    class Rank implements Comparable<Rank> {
        int id;
        int univ;
        int solve;
        int penalty;

        public Rank(int id, int univ, int solve, int penalty) {
            this.id = id;
            this.univ = univ;
            this.solve = solve;
            this.penalty = penalty;
        }

        @Override
        public int compareTo(Rank o) {
            if (solve != o.solve) return o.solve - solve;
            if (penalty != o.penalty) return penalty - o.penalty;
            return id - o.id;
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

    // flush automatically iff you call `println` or `printf` or `format`.
    PrintWriter sysout = new PrintWriter(System.out, true);

    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer buffer = new StringTokenizer("");

    String read() {
        if (!buffer.hasMoreTokens()) {
            try {
                buffer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return buffer.nextToken();
    }

    int readInt() {
        return Integer.parseInt(read());
    }

    long readLong() {
        return Long.parseLong(read());
    }

    double readDouble() {
        return Double.parseDouble(read());
    }

    String readLine() {
        buffer = new StringTokenizer("");
        try {
            return in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

Measured memory_bytes: 17844
import fractions

A, B, C, D = map(int, input().split())

def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

CD = lcm(C,D)
A -= 1
ans = (B - A) - (B//C - A//C) - (B//D - A//D) + (B//CD - A//CD)

print(ans)

Measured memory_bytes: 5344
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,u,v,ans=0;cin>>n;
  rep(i,n) ans+=(i+1)*(n-i);
  rep(i,n-1) {
    cin>>u>>v;
    if(u>v) swap(u,v);
    ans-=u*(n-v+1);
  }
  print(ans);
  return 0;
}

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

int in(void){
    int i;scanf("%d",&i);
    return i;
}
long long llin(void){
    long long i;scanf("%lld",&i);
    return i;
}
double din(void){
    double i;scanf("%lf",&i);
    return i;
}
void chin(char s[]){
    scanf("%s",s);
}
void print(int a){
    printf("%d\n",a);
}
void llprint(long long a){
    printf("%lld\n",a);
}
void dprint(double a){
    printf("%.10f\n",a);
}
void print2(int a,int b){
    printf("%d %d\n",a,b);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a<b?a:b;
}
int cmp(const void *a,const void *b){
    return *(TYPE *)a-*(TYPE *)b;
}
int cmp_r(const void *a,const void *b){
    return *(TYPE *)b-*(TYPE *)a;
}
int char_cmp(const void *a,const void *b){
    return strcmp((char *)a,(char *)b);
}
int char_cmp_r(const void *a,const void *b){
    return strcmp((char *)b,(char *)a);
}
void swap(int *a,int *b){
    int t=*a;
    *a=*b;
    *b=t;
}
long long gcd(long long x,long long y){
    return x%y?gcd(y,x%y):y;
}
long long lcm(long long x,long long y){
    return x/gcd(x,y)*y;
}

// write codes below this
// when you use 'sort',
// make sure TYPE macro is correct

int main(void){
    int n=in(),i,a[100000],c4=0,co=0;
    rep(i,n){
        a[i]=in();
        c4+=!(a[i]%4);
        co+=a[i]%2;
    }
    puts(co<=c4||co==c4+1&&n-co-c4==0?"Yes":"No");
    return 0;
}


Measured memory_bytes: 128
H, W = map(int, input().split())
D = []
for i in range(10):
  Cs = list(map(int, input().split()))
  D.append(Cs)
for k in range(10):
  for i in range(10):
    for j in range(10):
      D[i][j] = min(D[i][j], D[i][k]+D[k][j])
#print(D)
r = 0
for i in range(H):
  As = list(map(int, input().split()))
  for j in range(W):
    A = As[j]
    if A < 0:
      continue
    r += D[A][1]
print(r)


Measured memory_bytes: 3064
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
const int  INF=10e7;

typedef  pair<int,int> P;


int main(){
     string a,b,c;
     cin>>a>>b>>c;
     int i=0,j=0,k=0;
     int te=1;
     while(1){
          
          if(te==1){
               if(i==a.size()){
                    cout<<"A"<<endl;
                    break;
               }
                      

               if(a[i]=='a')te=1;
               else if(a[i]=='b')te=2;
               else te=3;
            ++i;
          }
          if(te==2){
               if(j==b.size()){
                    cout<<"B"<<endl;
                    break;
               }
                              
               if(b[j]=='a')te=1;
               else if(b[j]=='b')te=2;
               else te=3;
            ++j;
          } 
          if(te==3){
               if(k==c.size()){
                    cout<<"C"<<endl;
                    break;
               }
               

               if(c[k]=='a')te=1;
               else if(c[k]=='b')te=2;
               else te=3;
            ++k;
          }

     }


     
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
constexpr ll MOD = 998244353LL;
template <typename T>
constexpr T gcd(const T a, const T b) { return (b != 0) ? gcd(b, a % b) : a; }
int main()
{
    int N;
    std::cin >> N;
    std::vector<ll> a(N);
    for (int i = 0; i < N; i++) { std::cin >> a[i]; }
    std::sort(a.begin(), a.end());
    ll ans = 1;
    for (ll i = 0; i < N; i++) { (ans *= gcd(a[i], i)) %= MOD; }
    std::cout << ans << std::endl;
    return 0;
}


Measured memory_bytes: 1024
def C(x, y):
    z = 1
    for i in range(x, x-y, -1):
        z *= i
    for i in range(y, 1, -1):
        z //= i
    return z
def H(x, y):
    return C(x+y-1, y) % 1000000007
n, m = list(map(int, input().split()))
p = 2
prime_factorization = []
while p * p <= m:
    count = 0
    while m % p == 0:
        m //= p
        count += 1
    if count > 0:
        prime_factorization.append(count)
    p += 1
if m > 1:
    prime_factorization.append(1)
ans = 1
for r in prime_factorization:
    ans *= H(n, r)
print(ans % 1000000007)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e5 + 5 ;
int n , a , b ;
int num = 0 ;
int head[maxn] ;
int d[maxn][2] ;
bool leaf[maxn] ;
struct edge
{
	int v ;
	int next ;
} e[maxn << 1] ;
void add_edge(int u , int v)
{
	e[num].v = v ;
	e[num].next = head[u] ;
	head[u] = num ++ ;
}
void dfs(int u , int fa , int f)
{
	bool flag = 0 ;
	for(int i = head[u] ; i != -1 ; i = e[i].next)
	{
		int v = e[i].v ;
		if(v == fa)  continue ;
		d[v][f] = d[u][f] + 1 ;
		dfs(v , u , f) ;
		flag = 1 ;
	}
	if(!flag && f)  leaf[u] = 1 ;  
}
int main()
{
	memset(head , -1 , sizeof(head)) ;
	memset(leaf , 0 , sizeof(leaf)) ;
	scanf("%d%d%d" , &n , &a , &b) ;
	for(int i = 1 ; i <= n - 1 ; i ++)
	{
		int u , v ;
		scanf("%d%d" , &u , &v) ;
		add_edge(u , v) ;
		add_edge(v , u) ;
	}
	d[a][0] = 0 ;
	dfs(a , a , 0) ;
	d[b][1] = 0 ;
	dfs(b , b , 1) ;
	int ans = 0 ;
 	for(int i = 1 ; i <= n ; i ++)
	{
		if(!leaf[i])  continue ;
		if(d[i][0] < d[i][1])
		   ans = max(ans , d[i][1] - 1) ;
	}
	printf("%d\n" , ans) ;
}

Measured memory_bytes: 9472
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
long n,i;
double x1,y1,x2,y2,x3,y3,x,y,r,a1,b1,c1,a2,b2,c2;
cin>>n;
for(i=0;i<n;i++){
cin>>x1>>y1>>x2>>y2>>x3>>y3;
a1=(x2-x1)*2;
b1=(y2-y1)*2;
c1=x1*x1-x2*x2+y1*y1-y2*y2;
a2=(x3-x1)*2;
b2=(y3-y1)*2;
c2=x1*x1-x3*x3+y1*y1-y3*y3;
x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
y=(c1*a2-c2*a1)/(a1*b2-a2*b1);
r=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
printf("%.3f %.3f %.3f\n",x,y,r);
}
return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define p_b push_back
#define e_b emplace_back
#define m_p make_pair
#define m_t make_tuple

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> vec(n);

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

	ll c=0;

	for (int i = 0; i < n-1; i++) {
		if (vec[i] > vec[i + 1]) {
			c += vec[i] - vec[i + 1];
			vec[i + 1] += vec[i] - vec[i + 1];
		}
	}
	cout << c << endl;

	return 0;
}

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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<P, vector<P>, greater<P>> PQ_ASK;
const int mod = 1000000007;


int main() {

    map<string, int> strs;

    int n;
    cin >> n;
    rep(i, n) {
        string s;
        cin >> s;
        strs[s]++;
    }

    int m;
    cin >> m;
    rep(i, m) {
        string t;
        cin >> t;
        strs[t]--;
    }

    int mx = 0;
    for (auto e : strs) {
        cmax(mx, e.second);
    }

    cout << mx << endl;

}

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

int main() {
  int n;cin>>n;
  ll cnt=1,mod=1e9+7;
  for(int i=1;i<=n;i++){
    cnt*=i;
    cnt%=mod;
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 3608
import java.util.Scanner;


public class Main{

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		
		//System.out.println(pow(m,n));
		System.out.println(pow(m,n,1000000007));
	}

	static long pow(long m, long n) {
		long res = 1L;
		while (n>0L) {
			if ((n&1L)==1L)
				res *= m;
			m *= m;
			n=n>>1;
		}
		return res;
	}
	
	static long pow(long m, long n, long mod) {
		long res = 1;
		while (n>0L) {
			if ((n&1L)==1L)
				res = (res*m)%mod;
			m = (m*m)%mod;
			n=n>>1;
		}
		return res;
	}
	
}

Measured memory_bytes: 26332
#include <stdio.h>
#include <string.h>

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

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

	int i, j, k;
	int dp_old[3];
	memset(dp_old, 0, 3*sizeof(int));
	for (i = 0; i < n; i++) {
		int values[3];
		for (j = 0; j < 3; j++) scanf("%d", &values[j]);

		int dp_current[3];
		memset(dp_current, 0, 3*sizeof(int));
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				if (j != k) {
					dp_current[k] = max(dp_current[k], dp_old[j] + values[k]);
				}
			}
		}
		memcpy(dp_old, dp_current, 3*sizeof(int));
	}
	
	printf("%d\n", max(max(dp_old[0], dp_old[1]), dp_old[2]));
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
using namespace std;
using ll = long long;


int main() {
	int n, a, b; cin >> n >> a >> b;
	cout << min(b, a*n) << endl;
	return 0;
}

Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        s: String,
    }

    let mut count = {
        let r = s.match_indices("R").count();
        let g = s.match_indices("G").count();
        let b = s.match_indices("B").count();
        r * g * b
    };

    let s: Vec<char> = s.chars().collect();
    for i in 0..n - 2 {
        for j in i..n - 1 {
            let k = 2 * j - i;
            if k >= n {
                break;
            }

            if s[i] != s[j] && s[i] != s[k] && s[j] != s[k] {
                count -= 1;
            }
        }
    }

    println!("{}", count);
}


Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

ll mpow(ll x, ll n) {
  ll ans=1;
  while(n>0) {
    if(n&1) {
      ans=ans*x%mod;
    }
    x=x*x%mod;
    n>>=1;
  }
  return ans;
}

int main() {
  ll n,k;
  cin >> n >> k;
  vector<pll> a(n);
  vec p,m;
  ll z=0;
  for(ll i=0;i<n;i++) {
    ll tmp;
    cin >> tmp;
    ll f=0;
    if(tmp>0) f=1;
    else if(tmp<0) f=-1;
    a[i]={abs(tmp),f};
    if(f==1) {
      p.push_back(abs(tmp));
    }
    else if(f==-1) {
      m.push_back(abs(tmp));
    }
    else z++;
  }
  sort(p.rbegin(),p.rend());
  sort(m.rbegin(),m.rend());
  sort(a.rbegin(),a.rend());
  ll ans=1;
  ll idp=0,idm=0;
  for(ll i=0;i<k;i++) {
    ans=ans*a[i].first%mod;
    if(a[i].second==1) {
      idp++;
    }
    if(a[i].second==-1) {
      idm++;
    }
  }
  if(ans==0) {
    cout << ans << endl;
    return 0;
  }
  if(idm%2) {
    if(idm<m.size()&&idp) {
      if(idp<p.size()) {
        if(m[idm]*m[idm-1]>p[idp]*p[idp-1]) {
          ans=ans*mpow(p[idp-1],mod-2)%mod*m[idm]%mod;
        }
        else {
          ans=ans*mpow(m[idm-1],mod-2)%mod*p[idp]%mod;
        }
        cout << ans << endl;
      }
      else {
        ans=ans*mpow(p[idp-1],mod-2)%mod*m[idm]%mod;
        cout << ans << endl;
      }
    }
    else {
      if(idp<p.size()) {
        ans=ans*mpow(m[idm-1],mod-2)%mod*p[idp]%mod;
        cout << ans << endl;
      }
      else {
        if(z) {
          cout << 0 << endl;
        }
        else {
          ans=1;
          sort(a.begin(),a.end());
          for(ll i=0;i<k;i++) {
            ans=ans*a[i].first%mod;
          }
          ans=(mod-ans)%mod;
          cout << ans << endl;
        }
      }
    }
  }
  else {
    cout << ans << endl;
  }
}

Measured memory_bytes: 8464
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//解説みてます

ll dp[2002];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = 0;
	char c;
	while ((c = getchar_unlocked()) >= '0') N = N * 10 + c - '0';
	ll A[2000];
	rep(i, N) {
		int a = 0;
		while ((c = getchar_unlocked()) >= '0') a = a * 10 + c - '0';
		A[i] = ll(a) << 30 | i;
	}
	sort(A, A + N);
	const ll m = (1ll << 30) - 1;
	for (int i = N - 1; i >= 0; i--) {
		int a = A[i] & m;
		ll aa = A[i] >> 30;

		for (int j = N - i - 1; j >= 0; j--) {
			if (dp[j + 1] < dp[j] + abs(a - j) * aa) dp[j + 1] = dp[j] + abs(a - j) * aa;
			dp[j] += abs(a - j - i) * aa;
		}
	}
	ll kotae = 0;
	rep(i, N + 1) if (kotae < dp[i]) kotae = dp[i];

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1636
import sys
def 解():
    iN = int(sys.stdin.readline())
    aT = [int(_) for _ in sys.stdin.readlines()]
    #公倍数を求めるだけ
    def fgcd(a,b):
        while b:
            a,b = b, a%b
        return a

    lcm = aT[0]
    for a in aT[1:]:
        lcm = lcm * a // fgcd(lcm,a)
    print(lcm)
解()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
//const ll mod=1e9+7;
const ll mod=998244353;
const ll inf=5e15;

struct query{
  ll type;//0=empty, 1=add-sum ,2=set-max
  ll value;
  query(ll a=0,ll b=0):type(a),value(b) {}
};

ll INF=(1LL<<60);

struct segtree{
  ll SIZE;
  vector<query> s;
  vector<ll> t;// sum-add
  vector<ll> u;// max-set

  segtree(ll n=1){
    SIZE=1;
    while(SIZE<n)SIZE*=2;
    s.clear();
    t.clear();
    u.clear();
    s.resize(SIZE*2, query());
    t.resize(SIZE*2, 0);
    u.resize(SIZE*2, 0);
  }
  
  void func(ll k,ll l,ll r,query q){
    if(q.type==1){
      if(s[k].type==0)s[k]=q;
      else s[k].value+=q.value;
      t[k]+=q.value*(r-l);
      u[k]+=q.value;
    }
    if(q.type==2){
      s[k]=q;
      t[k]=q.value*(r-l);
      u[k]=q.value;
    }
  }

  void compute(ll k,ll l,ll r){
    query q=s[k];
    s[k]=query();
    if(q.type==0||r-l==1)return;
    ll m=(l+r)/2;
    func(k*2+1,l,m,q);
    func(k*2+2,m,r,q);
  }

  void Update(ll a,ll b,query x,ll k,ll l,ll r){
    if(b<=l || r<=a)return;
    compute(k,l,r);
    if(a<=l && r<=b){
      func(k,l,r,x);
    }else{
      ll m=(l+r)/2;
      Update(a,b,x,k*2+1,l,m);
      Update(a,b,x,k*2+2,m,r);
      t[k]=t[k*2+1]+t[k*2+2];
      u[k]=max(u[k*2+1],u[k*2+2]);
    }
  }

  ll Dfs(ll type,ll a,ll b,ll k,ll l,ll r){
    if(b<=l || r<=a){
      if(type==1)return 0; //add
      if(type==2)return -inf; // max
    }
    compute(k,l,r);
    if(a<=l && r<=b){
      if(type==1)return t[k];
      if(type==2)return u[k];
    }else{
      ll m=(l+r)/2;
      ll lv=Dfs(type,a,b,k*2+1,l,m);
      ll rv=Dfs(type,a,b,k*2+2,m,r);
      if(type==1)return lv+rv; // add
      if(type==2)return max(lv,rv); // max
    }
  }

  void Add(ll a,ll b,ll x){
    Update(a,b,query(1,x), 0,0,SIZE);
  }
  void Set(ll a,ll b,ll x){
    Update(a,b,query(2,x), 0,0,SIZE);
  }
  ll Getsum(ll a,ll b){
    return Dfs(1,a,b, 0,0,SIZE);
  }

  ll Getmax(ll a,ll b){
    return Dfs(2,a,b, 0,0,SIZE);
  }
  
};

int main() {
  ll n;
  cin >> n;
  vector<pll> a(n);
  vector<pll> b(n);
  for(ll i=0;i<n;i++) {
    ll x,d;
    cin >> x >> d;
    a[i]={x,d};
    b[i]={x,x+d};
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  segtree d(n+10);
  d.Set(0,n+1,-inf);
  vec dp(n+1);
  dp[0]=1;
  for(ll i=0;i<n;i++) {
    ll x=a[n-i-1].first+a[n-i-1].second;
    ll y=b[n-i-1].second;
    if(x!=y) {
      cout << -1 << endl;
      return 0;
    }
    ll it=upper_bound(a.begin(),a.end(),pll(x,0))-a.begin();
    d.Set(n-i-1,n-i,it);
    d.Set(n-i-1,n-i,d.Getmax(n-i-1,it));
    ll id=n-d.Getmax(n-i-1,n-i);
    (dp[i+1]=dp[i]+dp[id])%=mod;
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 24448
import math

A, B = map(int, input().split())


low_A = int(math.floor(A / 0.08))
up_A = int(math.floor((A + 1) / 0.08)) - 1


low_B = int(math.floor(B / 0.1))
up_B = int(math.floor((B + 1) / 0.1)) - 1


for i in range(low_B, up_A + 1):
    x = int(i * 0.08)
    y = int(i * 0.1)

    if x == A and y == B:
        print(i)
        exit()

print(-1)


Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	N, A, B := ReadInt(), ReadInt(), ReadInt()
	P := ReadInts(N)
	sort.Ints(P)
	var x, y, z int
	for _, p := range P {
		if p <= A {
			x++
		} else if A+1 <= p && p <= B {
			y++
		} else {
			z++
		}
	}
	fmt.Println(Min(x, y, z))
}

func Min(xs ...int) int {
	min := xs[0]
	for _, x := range xs[1:] {
		if min > x {
			min = x
		}
	}
	return min
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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

int main() {
  int ans;
  int a, b;
  string  op;
  cin >> a >> op >> b;
  if(op=="+"){
    ans = a + b;
  }else if(op =="-"){
    ans = a - b;
  }
  cout << ans << endl;
}


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

int main(){
  string S;
  cin>>S;
  
  if((S.at(5)=='0')&&(S.at(6)<='4')){
    cout<<"Heisei"<<endl;
    return 0;
  }
  cout<<"TBD"<<endl;
  return 0;
}
    

Measured memory_bytes: 256
import java.util.*;

import static java.lang.System.*;

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

        long[] x = new long[N];
        long[] y = new long[N];
        long[] z = new long[N];
        for (int i = 0; i < N; i++) {
            x[i] = sc.nextLong();
            y[i] = sc.nextLong();
            z[i] = sc.nextLong();
        }

        // 綺麗さ、美味しさ、人気度でそれぞれ正負の最大化を行うパターン(8通り)を探索して、
        // その中で最大値となるものが答え
        long ans = Long.MIN_VALUE;
        for(int i = 0; i < 1<<3; i++){
            Long[] values = new Long[N];
            for(int j = 0; j < N; j++){
                values[j] = add(x[j], (i>>2 & 1) == 1) +
                        add(y[j], (i>>1 & 1) == 1) +
                        add(z[j], (i>>0 & 1) == 1);
            }
            Arrays.sort(values, Collections.reverseOrder());

            long ans_tmp = 0;
            for(int j = 0; j < M; j ++){
                ans_tmp += values[j];
            }

            ans = Math.max(ans, ans_tmp);
        }

        out.println(ans);
    }

    public static long add(long a, boolean isMaximumPlus) {
        if(isMaximumPlus){ return a; }
        return -a;
    }
}


Measured memory_bytes: 28096
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())

N,K = LI()
D = [str(i) for i in input().split()]


def main():
    ans = N
    while True:
        for i in range(K):
            # print(list(str(ans)))
            if D[i] in list(str(ans)):
                # print(ans)
                ans += 1
                # ans += 10**max((len(str(ans))-list(str(ans)).index(D[i])-1),0)
                break
            if i == K - 1:
                return ans

print(main())


Measured memory_bytes: 5460
import java.io.*;
import java.util.StringTokenizer;
import java.util.HashSet;

public class Main {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int k = Integer.parseInt(br.readLine());

        HashSet<Long> hash = new HashSet<Long>();
        long val = 0;
        for(int i=1;;i++){
            val = ((val * 10) + 7) % k;
            if(val == 0){
                bw.write(i+"");
                break;
            }
            if(hash.contains(val)){
                bw.write("-1");
                break;
            }
            hash.add(val);
        }

        bw.flush();
        bw.close();
        br.close();
    }
}


Measured memory_bytes: 133756
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N := ReadInt()
	d := ReadInts(N)
	sum := 0
	for i := 0; i < N-1; i++ {
		for j := i + 1; j < N; j++ {
			sum += d[i] * d[j]
		}
	}
	fmt.Println(sum)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 1848
/*
2020-05-05
atcoder ABC
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

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

    if(A >= K){
        ans = K;
    } else if(A + B >= K){
        ans = A;
    } else {
        ans = A - (K - (A + B));
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
void solve(){
    
       int n;cin>>n;
       int arr[n]; 
       for(int i=0;i<n;i++) cin>>arr[i];
        long long  sum=0;
      for(int i=1;i<n;i++){
            if(arr[i]<arr[i-1])
            {
               sum+=arr[i-1]-arr[i];
               arr[i]=arr[i-1];
            }
      }
      cout<<sum<<endl;
      }

int main() {
   #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif

 ios_base::sync_with_stdio(0);
 cin.tie(0);

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

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

 return 0;
}


Measured memory_bytes: 4396
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<map>
using namespace std;
typedef pair<int,int> P;
#define Y first
#define X second
int main(){
  int m,n;
  cin >> m >> n;
  string st[600];
  int i,j,k;
  for(i=0;i<m;i++) cin >> st[i];
  bool alp[26]={};
  vector<P> v[26];
  P p;
  for(i=0;i<m;i++){
    for(j=0;j<n;j++){
      if(st[i][j]!='.') {
	alp[st[i][j]-'A']=true;
	p.Y=i;p.X=j;
	v[st[i][j]-'A'].push_back(p);
      }
    }
  }
  //cout << "x" << endl;
  bool f=true,e;
  int ans=0;
  while(f){
    f=false;
    for(k=0;k<26;k++){
      if(!alp[k]) continue;
      if(v[k][0].X==v[k][1].X){
	if(abs(v[k][0].Y-v[k][1].Y)<2) continue;
	e=true;
	for(i=min(v[k][0].Y,v[k][1].Y)+1;i<max(v[k][0].Y,v[k][1].Y);i++){
	  if(st[i][v[k][0].X]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
      }else if(v[k][0].Y==v[k][1].Y){
	if(abs(v[k][0].X-v[k][1].X)<2) continue;
	e=true;
	for(i=min(v[k][0].X,v[k][1].X)+1;i<max(v[k][0].X,v[k][1].X);i++){
	  if(st[v[k][0].Y][i]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
      }else if((v[k][0].X-v[k][1].X)*(v[k][0].Y-v[k][1].Y)>0){
	if(v[k][0].X>v[k][1].X) swap(v[k][0],v[k][1]);
	e=true;
	for(i=v[k][0].X+1;i<=v[k][1].X;i++){
	  if(st[v[k][0].Y][i]!='.') e=false;
	}
	for(i=v[k][0].Y;i<v[k][1].Y;i++){
	  if(st[i][v[k][1].X]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
	e=true;
	for(i=v[k][0].Y+1;i<=v[k][1].Y;i++){
	  if(st[i][v[k][0].X]!='.') e=false;
	}
	for(i=v[k][0].X;i<v[k][1].X;i++){
	  if(st[v[k][1].Y][i]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
      }else{
	if(v[k][0].X>v[k][1].X) swap(v[k][0],v[k][1]);
	e=true;
	for(i=v[k][0].X+1;i<=v[k][1].X;i++){
	  if(st[v[k][0].Y][i]!='.') e=false;
	}
	for(i=v[k][0].Y;i>v[k][1].Y;i--){
	  if(st[i][v[k][1].X]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
	e=true;
	for(i=v[k][0].Y-1;i>=v[k][1].Y;i--){
	  if(st[i][v[k][0].X]!='.') e=false;
	}
	for(i=v[k][0].X;i<v[k][1].X;i++){
	  if(st[v[k][1].Y][i]!='.') e=false;
	}
	if(e){
	  st[v[k][0].Y][v[k][0].X]='.';
	  st[v[k][1].Y][v[k][1].X]='.';
	  alp[k]=false;
	  ans++;f=true;
	  break;
	}
      }
    }
    //for(i=0;i<m;i++) cout << st[i] << endl; cout << endl;
  }
  //for(i=0;i<m;i++) cout << st[i] << endl;
  cout << ans*2 << endl;
  return 0;
}

Measured memory_bytes: 1480
def f(a)
  count = 1
  greaterp = nil
  a.inject{|r, n|
    next r if r == n
    if greaterp.nil?
      greaterp = r > n
    end
    # p [greaterp, r, n, count]
    if greaterp
      if r < n
        greaterp = nil
        count += 1
      end
    else
      if r > n
        greaterp = nil
        count += 1
      end
    end
    n
  }
  count
end

N = gets.to_i
A = gets.split.map(&:to_i)
puts f(A)


Measured memory_bytes: 8452
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define NUM 100
 
int main()
{
   static long i,j,k,l;
   int mid;
   int end;
   int re;
   char grade[NUM];
   for(i=0;;i++) {
      cin >> mid >> end >> re;
      if(mid == -1 && end == -1 && re == -1)
         break;
      int sum = mid + end;
      if(mid == -1 || end == -1)
         grade[i] = 'F';
      else if(sum >= 80)
         grade[i] = 'A';
      else if(sum >= 65)
         grade[i] = 'B';
      else if(sum >= 50)
         grade[i] = 'C';
      else if(sum >= 30 && re >= 50)
         grade[i] = 'C';
      else if(sum >= 30)
         grade[i] = 'D';
      else
         grade[i] = 'F';
   }
   for(j=0;j<i;j++)
      cout << grade[j] << endl;
 
   return 0;
}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////
template<typename T>
struct edge {
  int to, from;T cost;
  edge(int to) : from(-1), to(to), cost(-1) {}
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};
template<typename T>
using edges = vector<edge<T>>;
template<typename T>
using graph = vector<edges<T>>;
template<typename T>
using matrix = vector<vector<T>>;

template<typename T>
bool compByCost(const edge<T>& left, const edge<T>& right){
  return left.cost < right.cost; 
}

template<typename T>
vector<vector<T>> warshall(matrix<T> &g){
  vector<vector<T>> dist(g.size());
  rep(i,g.size()){
    dist[i].resize(g.size());
    rep(j,g.size())dist[i][j] = (i == j ? 0 : g[i][j]);
  }
  rep(k,g.size()){
    rep(i,g.size()){
      rep(j,g.size()){
        if(dist[i][k] == INF || dist[k][j] == INF)continue;
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }
  return dist;
}

#define warshall warshall<int>// matの初期化でINFを詰めておく



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

int n,a;
signed main(){
  cin>>n;a = 0;
  rep(i,n){
    int b;cin>>b;
    a |= b;
  }
  rep(i,INF){
    if(a&1){
      cout << i << endl;return 0;
    }else a = a>>1;
  }
}


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

int main(){
    bool res[1001] = {};
    int a, b, N;
    bool ans = false;

    cin >> a >> b;
    for(int i=a;i<b;i++)
        res[i] = true;

    cin >> N;
    for(int i=0;i<N;i++){
        int s, f;
        cin >> s >> f;
        for(int j=s;j<f;j++){
            if(res[j])
                ans = true;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3128
#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(int x = (l);x<=(u);x++)
#define RREP(x,l,u) for(int x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 200010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,cnt,ans;

int A[maxn],B[maxn],C[maxn],D[maxn],fa[maxn];

map<int,int> E;

int find(int i){return fa[i]==i?i:fa[i]=find(fa[i]);}

void Work(){
	sort(C+1,C+n+2);sort(D+1,D+n+2);
	REP(i,1,n+1)if(C[i]!=D[i]){
		puts("-1");
		exit(0);
	}
	bool ok=1;
	REP(i,1,n)if(A[i]!=B[i])ok=0;
	if(ok){
		puts("0");
		return;
	}
	REP(i,1,n)if(A[i]!=B[i]){
		ans++;
		if(!E[A[i]])E[A[i]]=++cnt;
		if(!E[B[i]])E[B[i]]=++cnt;
	}
	if(!E[A[n+1]])E[A[n+1]]=++cnt;
	if(!E[B[n+1]])E[B[n+1]]=++cnt;
	REP(i,1,cnt)fa[i]=i;
	REP(i,1,n)if(A[i]!=B[i])fa[find(E[A[i]])]=find(E[B[i]]);
	REP(i,1,cnt)if(find(i)==i)ans++;
	iout(ans-1);
}

void Init(){
	read(n);
	REP(i,1,n)read(A[i]);
	REP(i,1,n)read(B[i]);
	REP(i,1,n)A[n+1]^=A[i],B[n+1]^=B[i];
	REP(i,1,n+1)C[i]=A[i],D[i]=B[i];
}

int main(){
	Init();
	Work();
	return 0;
}


Measured memory_bytes: 8448