akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main() {
    int W, H, x, y, r;
    cin >> W >> H >> x >> y >> r;
    
    if (W >= x + r && H >= y + r && x >= r && y >= r) {
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3116
class Dice:
    def __init__(self):
        self.u=1
        self.w=2
        self.s=3
        self.e=4
        self.n=5
        self.d=6
        self.dic={"W":0,"S":1,"E":2,"N":3}
    
    def __init__(self,u,w,s,e,n,d):
        self.u=u
        self.w=w
        self.s=s
        self.e=e
        self.n=n
        self.d=d
        self.dic={"W":0,"S":1,"E":2,"N":3}

    def rot(self,way):
        if isinstance(way,str):
            way=self.dic[way]

        if(way==0):
            c=self.u
            self.u=self.e
            self.e=self.d
            self.d=self.w
            self.w=c
        elif way==1:
            c=self.u
            self.u=self.n
            self.n=self.d
            self.d=self.s
            self.s=c
        elif way==2:
            c=self.u
            self.u=self.w
            self.w=self.d
            self.d=self.e
            self.e=c

import random
u,s,e,w,n,d=map(int,input().split())
dice=Dice(u,w,s,e,n,d)
u,s,e,w,n,d=map(int,input().split())
dice_b=Dice(u,w,s,e,n,d)
ok=False
for i in range (1000):
    dice.rot(random.randint(0,3))
    if(dice.u==dice_b.u and dice.d==dice_b.d and dice.w==dice_b.w and dice.s==dice_b.s and dice.e==dice_b.e and dice.n==dice_b.n):
        ok=True
if ok:
    print('Yes')
else :
    print('No')

Measured memory_bytes: 11788
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define base 31
#define MOD 1e9+7
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORs(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define __FOR(i, a, b, k) for(int i = a; i <= b; i+= k)
#define __REP(i, a, b, k) for(int i = a; i < b; i+= k)
#define pb push_back
#define _io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair <int, int> ii;
typedef vector <ii> vii;
#define fi first
#define se second
#define mp make_pair
#define N  100
int n,a[N],b[N],c[N],res;
void nhap(){
	cin>>n;
	FOR(i,1,n) cin>>a[i];
	FOR(i,1,n) cin>>b[i];
	FOR(i,1,n-1) cin>>c[i];
}
int main(){
	
	_io;
	nhap();
	res=0;
	FOR(i,1,n){
			res+=b[a[i]];
			if (a[i]-a[i-1]==1) res+=c[a[i]-1];
	}
	cout<<res;
}



Measured memory_bytes: 256
#include <iostream>
#define ull unsigned long long
using namespace std;
ull X,Y;
int main()
{
	cin >> X >> Y;
	if(X == 1 && Y == 1)
	{
		cout << 1 << endl;
		return 0;
	}
	ull ret = 0;

	while(X <= Y)
	{
		ret+=1;
		X<<=1;
	}
	cout << ret << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);

        final int s = sc.nextInt();

        List<Integer> l = new ArrayList<>();
        l.add(s);
        
        int idx = 0;
        while (true) {
            int a = f(l.get(idx));
            if (l.contains(a)) {
                System.out.println(idx+2);
                break;
            }
            l.add(a);
            idx++;
        }
    }

    private static int f(final int n) {
        return n % 2 == 0 ? n / 2 : 3 * n + 1;
    }
}


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

int main()
{
    int num,load;
    cin >> num >> load;
    int town[51]={};
    int A,B;
    for(int i=0;i<load;i++){
        cin >> A >> B;
        town[A]++;
        town[B]++;
    }
    for(int i=1;i<=num;i++){
        cout << town[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#pragma once
#include <stdio.h>
#include <sstream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <limits>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define bit(x,v) ((ll)x << v)

const ll INF = 1000000007;
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int pr[100010];
void uini(int n) {
	for (size_t i = 0; i <= n; i++)
	{
		pr[i] = i;
	}
}

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

bool unit(int x, int y) {
	int px = parent(x);
	int py = parent(y);

	if (px == py) return false;
	if (px < py) {
		pr[py] = px;
	}
	else {
		pr[px] = py;
	}
	return true;
}

// res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n)
vector<vector<int> > calcNext(const string& S) {
	int n = (int)S.size();
	vector<vector<int> > res(n + 1, vector<int>(26, n));
	for (int i = n - 1; i >= 0; --i) {
		for (int j = 0; j < 26; ++j) res[i][j] = res[i + 1][j];
		res[i][S[i] - 'a'] = i;
	}
	return res;
}
// mod 1000000007 の世界で a += b する関数
void add(long long& a, long long b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
struct edge {
	int to;
	ll cost;
	edge(int to,ll cost) : to(to),cost(cost){}

};
vector<edge> es[100010];
int x[100010], y[100010];
ll d[100010];
void dija(int s) {
	fill(d, d + 100010, INF * INF);
	d[s] = 0;
	priority_queue<pll, vector<pll>, greater<pll>> q;
	q.push(pll(0, s));
	while (!q.empty())
	{
		pll p = q.top();
		q.pop();
		if (p.first > d[p.second]) continue;
		for (auto it : es[p.second]) {
			if (d[it.to] > d[p.second] + it.cost) {
				d[it.to] = d[p.second] + it.cost;
				q.push(pll(d[it.to],it.to));
			}
		}
	}
}
void solv() {
	int n;
	cin >> n;
	for (size_t i = 0; i < n - 1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		es[a].push_back(edge(b, c));
		es[b].push_back(edge(a, c));
	}
	int q, k;
	cin >> q >> k;
	for (size_t i = 0; i < q; i++)
	{
		cin >> x[i] >> y[i];
	}

	dija(k);

	for (size_t i = 0; i < q; i++)
	{
		cout << (d[x[i]] + d[y[i]]) << endl;
	}
}

int main() {
	//COMinit();
	solv();

	return 0;
}


Measured memory_bytes: 12144
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n;
  cin >> n;
  int ans = 0;
  int m = 0;
  rep (i, n) {
    int tmp;
    cin >> tmp;
    m = max(m, tmp);
    ans += tmp;
  }
  P(ans - m + m /2);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807/2;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
string s;
bool t[30000][10];
bool tt[30000][100];
bool ttt[1000];
int main(){
	cin>>n;
	cin>>s;
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<10;j++){
			t[i][j]=t[i+1][j];
		}
		t[i][s[i+1]-'0']=1;
	}
	for(int i=n-2;i>=0;i--){
		for(int j=0;j<100;j++)tt[i][j]=tt[i+1][j];
		for(int k=0;k<10;k++){
			if(t[i+1][k]){
				tt[i][k+(s[i+1]-'0')*10]=1;
				//cout<<9<<endl;
			}
		}
	}
	for(int i=n-3;i>=0;i--){
		for(int j=0;j<100;j++){
			if(tt[i][j]){
				ttt[(s[i]-'0')*100+j]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<1000;i++){
		if(ttt[i])ans++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3584
<?php
error_reporting(0);
//$X = explode(" ",trim(fgets(STDIN)));
$N = trim(fgets(STDIN));
$a = explode(" ",trim(fgets(STDIN)));
//list($X,$K) = explode(" ",trim(fgets(STDIN)));
rsort($a);
$alice = 0;
$bob = 0;
foreach($a as $k => $v) {
  if (($k % 2)==1) {
    $bob += $v;
  }
  else {
    $alice += $v;
  }
}
printf("%d\n",$alice-$bob);

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

using namespace std;

typedef long long ll;

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

const int MAXN = 2031;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	
	int n;
	cin >> n;
	int k;

	vector<pair<int, int>> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first;
		a[i].second = i + 1;
	}
	
	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++)
	{
		cout << a[i].second << " ";
	}

    return 0;
}


Measured memory_bytes: 1664
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
x=sum(b)
for i in range(len(a)-1):
  if a[i+1]-a[i]==1:
    d=a[i]
    x+=c[d-1]
print(x)


Measured memory_bytes: 3060
/*
 * c.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  for (;;) {
    int x, y;
    cin >> x >> y;
    if (x == 0 && y == 0) break;

    if (x > y) swap(x, y);
    printf("%d %d\n", x, y);
  }

  return 0;
}

Measured memory_bytes: 1144
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
char in[10];
int main(){
	int a;scanf("%d",&a);
	int ret=0;
	int v=0;
	for(int i=0;i<a;i++){
		int p,q;scanf("%d%d",&p,&q);
		if(v<p){
			v=p;
			ret=p+q;
		}
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
//#include "/Users/student/Documents/Sublime/stdc++.h"

typedef long long ll;

using namespace std;

ll a,b,c;



int main() {
//    freopen("input.in", "r", stdin);
//    freopen("output.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> c;
    if(a+b+c > 21){
        cout << "bust";
    }
    else{
        cout << "win";
    }

}

Measured memory_bytes: 256
#include <stdio.h>

int main() {

	int X = 0;

	scanf("%d", &X);

	if (-40 <= X <= 40)
	{
		if (X >= 30)
		{
			printf("Yes");
		}
		if (X < 30)
		{
			printf("No");
		}
	}

	return 0;
}

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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

    cout << max(0, min(B,D) - max(A,C) ) << endl;
}


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

#define what_is(x) cerr << #x << " is " << x << endl;
#define what_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << e << ' '; cerr << '\n'; //vector, set
#define what_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << x[i] << ' '; cerr <<  '\n'; //n first element of array
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define cerr_pair(x) '{' << x.st << ", " << x.nd << '}'
#define pwhat_is(x) cerr << #x << " is " << cerr_pair(x) << endl;
#define pwhat_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << cerr_pair(e) << ' '; cerr << '\n'; //vector, set
#define pwhat_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << cerr_pair(x[i]) << ' '; cerr <<  '\n'; //n first element of array
#define endl '\n'
// #define int long long

typedef pair<int,int> pii;
const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n, m;
vector<int> g[3*N];
int s, t;
bool vis[3*N];
int dis[3*N];

int32_t main()
{
	IOS
	//freopen("input.txt", "r", stdin);
	cin >> n >> m;
	while(m--){
		int u, v; cin >> u >> v; 
		u--; v--;
		g[u].push_back(v+n);
		g[u+n].push_back(v+2*n);
		g[u+2*n].push_back(v);
	}
	cin >> s >> t; s--; t--;
	dis[s] = 0;
	queue<int> q;
	vis[s] = true;
	q.push(s);
	while(!q.empty()){
		int v = q.front(); q.pop();
		for(auto u:g[v]){
			if (vis[u]) continue;
			vis[u] = true;
			dis[u] = dis[v] + 1;
			q.push(u);
		}
	}
	if (!vis[t]) cout << "-1\n";
	else cout << dis[t]/3 << endl;

	
	return 0;
}


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

void solve(int N, vector<int> B)
{
    int res = 0;
    res += B.at(0);
    for (int i = 0; i < N - 2; i++)
    {
        res += min(B.at(i), B.at(i + 1));
    }
    res += B.at(N - 2);
    cout << res << endl;
}

int main()
{
    int N;
    cin >> N;
    vector<int> B(N-1);
    for(int i = 0; i < N-1; i++) {
        cin >> B.at(i);
    }
    solve(N, move(B));
    return 0;
}


Measured memory_bytes: 3604
import itertools
N = int(input())
P = tuple([int(_) for _ in input().split()])
Q = tuple([int(_) for _ in input().split()])
n = [int(i) for i in range(1, N + 1)]
jun = list(itertools.permutations(n, N))

p = jun.index(P) + 1
q = jun.index(Q) + 1

print(abs(p - q))

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

int main(){
    int N,K; cin >> N >> K;
    if((N-1)%(K-1) == 0){
        cout << (N-1)/(K-1) << endl;
    }else{
        cout << (N-1)/(K-1) + 1 << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define maxn 300010
#define maxint 0x7fffffff/2
using namespace std;
int n;
int t[maxn];
int main() {
	cin>>n;
	for(int i=2; i<=n; i++) {
		int x;
		cin>>x;
		t[x]++;
	}
	for(int i=1; i<=n; i++) {
		cout<<t[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 4416
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define MAX_C 1000000001

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<set<int>> num(10, set<int>());
  for(int i = 0; i < n; i++) {
    int p = (int)(s[i] - '0');
    num[p].insert(i);
  }

  int cnt = 0;
  for (int i = 0; i < 1000; i++) {
    int index = -1;
    int a, b, c;
    c = i % 10;
    b = (i % 100 - c) / 10;
    a = i / 100;

    auto it = num[a].upper_bound(index);
    if (it == num[a].end()) continue;
    index = (int)(*it);
    it = num[b].upper_bound(index);
    if (it == num[b].end()) continue;
    index = (int)(*it);
    it = num[c].upper_bound(index);
    if (it == num[c].end()) continue;
    cnt++;
  }

  cout << cnt << endl;
}


Measured memory_bytes: 1664
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007
N = int(input())
d = defaultdict(int)
zeros = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        d[(a, b)] += 1


ans = 1
free = 0
keys = sorted(d.keys())
for a, b in keys:
    n = d[(a, b)]
    if a != 0 and b != 0:
        if b > 0:
            if (b, -a) in d:
                m = d[(b, -a)]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
            else:
                free += n
        else:
            if (-b, a) not in d:
                free += n
x, y, z = d[(0, 1)], d[(1, 0)], d[(0, -1)]
ans = ans * (pow(2, x + z, MOD) + pow(2, y, MOD) - 1) % MOD
ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)


Measured memory_bytes: 117816
package main

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

func main() {
  sc := bufio.NewScanner(os.Stdin)
  sc.Split(bufio.ScanWords)

  sc.Scan()
  n, e := strconv.Atoi(sc.Text())
  if e != nil {
    panic(e)
  }

  a := make([]int, n)

  for i := 0; i < n; i++ {
    sc.Scan()
    v, e := strconv.Atoi(sc.Text())
    if e != nil {
      panic(e)
    }
    a[i] = v
  }

  sort.Sort(sort.IntSlice(a))

  for i := a[1]; i > 0; i-- {
    j := 0
    miss := 0
    for j = 0; j < n; j++ {
      if a[j] % i > 0 {
        miss++
        if miss == 2 {
          break
        }
      }
    }
    if j == n {
      fmt.Println(i)
      os.Exit(0)
    }
  }
}


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

using namespace std;

int main() {
	unsigned int x;
	cin >> x;
	
	vector<long long> p;
	p.push_back(0);
	
	int cnt = 0;
	for (int i = 0; i < 150; ++i) {
		++cnt;
		p.push_back(pow(cnt, 5));
	}
	
	int a, b;
	bool ok = false;
	for (int i = 0; i < 150 && !ok; ++i) {
		for (int j = -150; j < 150 && !ok; ++j) {
			if (j < 0) {
				ok = (p[i] + p[j * -1] == x);
			} else {
				ok = (p[i] - p[j] == x);
			}
			
			if (ok) {
				a = i;
				b = j;
			}
		}
	}
	
	cout << a << " " << b << endl;
}

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

int main() {
  string s; cin>>s; int n=s.size();
  int t[n]; for(int i=0;i<n;i++) t[i]=s[i]-'0';
  int k; cin>>k;
  
  int dp[n+1][k+1][2]; fill(dp[0][0], dp[n+1][0], 0); dp[0][0][1] = 1;
  for(int i=0;i<n;i++) {
    for(int j=0;j<=k;j++) {
      for(int m=0;m<2;m++) {
        int C = m?t[i]-1:9;
        for(int c=0;c<=C;c++) {
          //cout<<"("<<c<<": "<<i<<" "<<j<<" "<<m<<") "<<i+1<<" "<<j+(c!=0)<<" "<<0<<" "<<dp[i][j][m]<<endl;
          if (j+(c!=0) <= k) dp[i+1][j+(c!=0)][0] += dp[i][j][m];
        }
        if (m&&(j+(t[i]!=0) <= k)) dp[i+1][j+(t[i]!=0)][m] = dp[i][j][m];
      }
    }
  }
  
  /*
  for(int i=0;i<=n;i++) {
    for(int j=0;j<=k;j++) {
      cout<<dp[i][j][0]<<" ";
    } cout<<endl;
  } cout<<endl;
  
  for(int i=0;i<=n;i++) {
    for(int j=0;j<=k;j++) {
      cout<<dp[i][j][1]<<" ";
    } cout<<endl;
  } cout<<endl;*/
  
  cout<<dp[n][k][0]+dp[n][k][1]<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
bool  vis[300005];
int main() {
     ios::sync_with_stdio(false);
  cin.tie(0);
ll n;
cin>>n;
ll r=n%10;
if(r==2||r==4||r==5||r==7||r==9)
cout<<"hon"<<endl;
else if(r==0||r==1||r==6||r==8)
cout<<"pon"<<endl;
else
cout<<"bon"<<endl;
}

Measured memory_bytes: 3644
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"unicode"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	a := nextInt()
	_ = nextInt()
	s := nextStr()

	ok := true

	for i := 0; i < len(s); i++ {
		if i == a {
			if s[i] != '-' {
				ok = false
				break
			}
		} else {
			//if (s[i] < '0') || (s[i] > '9') {
			if !isDigit(s[i]) {
				ok = false
				break
			}
		}

	}

	if ok == true {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

func isDigit(a byte) bool {
	return unicode.IsDigit(rune(a))
}

// ---- readfunc
func scanInit() {
	const cap = 64 * 1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
<?php

fscanf(STDIN, '%d %d %d %d', $N, $A, $B, $C);
$list = [];
for ($i = 1; $i <= $N; ++$i) {
    $list[] = (int)trim(fgets(STDIN));
}

function dfs($cur, $a, $b, $c) {
    global $N, $A, $B, $C, $list;
    
    if ($cur === $N) {
        if (min($a, $b, $c) > 0) {
            return abs($A - $a) + abs($B - $b) + abs($C - $c) - 30;
        } else {
            return INF;
        }
    }
    
    $ret0 = dfs($cur + 1, $a, $b, $c); //A、B、Cどれにも使わない場合
    $ret1 = dfs($cur + 1, $a + $list[$cur], $b, $c) + 10; //Aに使う場合
    $ret2 = dfs($cur + 1, $a, $b + $list[$cur], $c) + 10; //Bに使う場合
    $ret3 = dfs($cur + 1, $a, $b, $c + $list[$cur]) + 10; //Cに使う場合
    
    return min($ret0, $ret1, $ret2, $ret3);
}

echo dfs(0, 0, 0, 0);


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

#define ll long long 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin (),(x).end()
#define f(i, a, b) for (int i=a; i<(signed)(b); ++i)
#define pc __builtin_popcount // counts number of 1's in bin(num)

const double pi = 2*acos(0.0);
//__gcd(n1, n2);
//cout << fixed;
//cout << setprecision(6); //fixes # of dp



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);
	
    int h, a;
    cin >> h >> a;
    if(h%a == 0){
        cout << h/a;
    } else{
        cout << h/a + 1;
    }
}








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

int main () {
  int r, D, x, ans[10];
  cin >> r >> D >> x;
  
  ans[0] = r*x-D;
  for (int i = 1; i < 10; i++) {
    ans[i] = r*ans[i-1]-D;
  }
  for (int i = 0; i < 10; i++) {
    cout << ans[i] << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

int main() {
    std::string str;
    std::cin >> str;

    int cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        cnt += str[i] - '0';
    }

    std::printf("%s\n", cnt % 9 == 0 ? "Yes" : "No");

    return 0;
}


Measured memory_bytes: 3488
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<string> b(N);
    for(int i=0; i<N;++i){
        cin >> b.at(i);
    }


int M;
cin >> M;
vector<string> r(M);
for(int i=0;i<M; ++i){
    cin >>r.at(i);
}

int ans=0;//しっかり０で定義しないとくらべられない
for(int i=0;i<N;++i){
    int tmp=1;//毎回TMPが１になってANWERとたたかってる
    for(int j=i+1;j<N;++j){
        if(b.at(i) == b.at(j)) ++tmp;
    }
    for(int j=0; j<M;++j){
        if(b.at(i)==r.at(j)) --tmp;
    }
    if(ans<tmp) {ans=tmp;}
}
cout << ans <<endl;
    
  
    


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//define
#define int long long
#define vint vector<int>
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
#define pb() push_back()
#define mod 100000007
#define elif else if
#define str string
//main
signed main(){
  int N,M,O,Q,count=0,count2=0,count3=0;
  cin>>N>>M;
  N-(M*2)<0?cout<<0<<endl:cout<<N-(M*2)<<endl;
}


Measured memory_bytes: 256
len = gets.to_i
nums = gets.split.map(&:to_i)
cnt = 0
0.upto(len-1) do |i|
  (len-1).downto(i+1) do |j|
    if nums[j] < nums[j-1]
      nums[j], nums[j-1] = nums[j-1], nums[j]
      cnt += 1
    end
  end
end
puts nums * ' '
puts cnt

Measured memory_bytes: 6104
from collections import defaultdict, Counter
N, M = map(int, input().split())
X = list(map(int, input().split()))
C = Counter(X)
D = defaultdict(int)
E = defaultdict(int)
for k, v in C.items():
    D[k%M] += v
    E[k%M] += v//2

ans = D[0] // 2

for i in range(1, M):
    j = M - i
    if i < j:
        x = min(D[i], D[j])
        y = min((D[i] - x)//2, E[i]) + min((D[j] - x)//2, E[j])
        ans += x + y
    elif i == j:
        ans += D[i] //2
    else:
        break

print(ans)

Measured memory_bytes: 35932
import sys
sys.setrecursionlimit(20000000)


def dfs(node, distance):
    for next_node, edge_size in G[node]:
        if ans[next_node] == -1:
            ans[next_node] = ((distance+edge_size) % 2)
            dfs(next_node, distance+edge_size)


N = int(input())

G = [[] for i in range(N)]
for i in range(N-1):
    u, v, w = map(int, input().split())
    G[u-1].append([v-1, w])
    G[v-1].append([u-1, w])

ans = [-1]*N
dfs(0, 0)
print(*ans, sep='\n')

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<pair<int,int>> vp;

#define pb push_back
#define mp make_pair

const int INF = INT_MAX;

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

	int a, ans;
	scanf("%d", &a);
	ans = a + pow(a,2) + pow(a,3);
	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 4212
#include <iostream>
#include <vector>
using namespace std;
int AINT[800005];
int dp[200005];
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        AINT[nod]=dp[st];
        return ;
    }
    int mid=(st+dr)/2;
    build(nod*2,st,mid);
    build(nod*2+1,mid+1,dr);
    AINT[nod]=min(AINT[2*nod],AINT[2*nod+1]);
}
void u(int nod,int st,int dr,int pos,int val)
{
    if(dr<pos||st>pos)return ;
    if(st==dr){AINT[nod]=val;return ;}
    int mid=(st+dr)/2;
    u(nod*2,st,mid,pos,val);
    u(nod*2+1,mid+1,dr,pos,val);
    AINT[nod]=min(AINT[2*nod],AINT[2*nod+1]);
}
int q(int nod,int st,int dr,int S,int D)
{
    if(dr<S||st>D)return 1<<30;
    if(S<=st&&dr<=D)return AINT[nod];
    int mid=(st+dr)/2;
    return min(q(nod*2,st,mid,S,D),q(nod*2+1,mid+1,dr,S,D));
}
int N,Q;
vector<int> V[200005];
int B[200005],rez;
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
        {cin>>B[i];rez+=!B[i];}
    cin>>Q;
    for(int i=1;i<=Q;i++)
    {
        int x,y;
        cin>>x>>y;
        V[x].push_back(y);
    }
    for(int i=1;i<=N+1;i++)dp[i]=1<<30;
    build(1,0,N+1);
    for(int i=0;i<N;i++)
    {
        vector<int> updates;
        for(auto it:V[i+1])
        {
            dp[it+1]=min(dp[it+1],q(1,0,N+1,i,it+1));
            updates.push_back(it+1);
        }
        dp[i+1]=min(dp[i],dp[i+1])+(B[i+1] ? 1:-1);updates.push_back(i+1);
        dp[i]=1<<30;updates.push_back(i);
        for(auto it:updates)
            u(1,0,N+1,it,dp[it]);
    }
    rez+=min(dp[N+1],dp[N]);
    cout<<rez;
    return 0;
}


Measured memory_bytes: 14464
#include <iostream>
#include<stdio.h>
#include<algorithm>

#define N 1000//1000000000

using namespace std;

int more(int a,int b){
    if(a>b) return a;
    else return b;
}


int main(void){
    // Your code here!
    int L[N]={0};
 
    int n;
 int tmp1;
 int tmp2=0;
int k=0;    
    scanf("%d",&n);
    for(int i=0; i<n; i++) scanf("%d",&L[i]);
 
 for(int i=0; i<n-2; i++){
 for(int j=i+1; j<n-1; j++){
 for( k=j+1; k<n; k++){
   //tmp1=more( L[i],L[j] );
   //tmp1=more( tmp1,L[k] );
   if( L[i]==L[j] ) continue;
   if( L[i]==L[k] ) continue;
   if( L[k]==L[j] ) continue;
   if( L[k]<L[i]+L[j] && L[j]<L[i]+L[k] && L[i]<L[k]+L[j] ) tmp2++;    //if( tmp1<L[i]+L[j]+L[k]-tmp1 &&  ) tmp2++;//if( tmp1<L[i]+L[j]+L[k]-tmp1 ) tmp2++;
   //if(k==n-1) break;
 }
    //if(k==n-1) break;
 }
    //if(k==n-1) break;
 }
 
    
    printf("%d\n",tmp2);
    return 0;

    
}





Measured memory_bytes: 3864
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

int main(){
    ll a;
    cin >> a;
    double b;
    cin >> b;
    int c = b*100+0.5;
    cout << c*a/100 << endl;
    return 0;
}

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

signed main () {
	int a, b, c, d, e, f, raa = 0, rbb = 0, rcc = 0, rdd = 0, maxdn = 0, maxdd = 0;
	cin >> a >> b >> c >> d >> e >> f;
	for (int iaa = 0; iaa * a * 100 <= f; ++iaa){
		for (int ibb = 0; ibb * b * 100 <= f; ++ibb){
			for (int icc = 0; icc * c <= f; ++icc){
				for (int idd = 0; idd * d <= f; ++idd){
					if (iaa * a * 100 + ibb * b * 100 + icc * c + idd * d <= f){
						if ((iaa * a + ibb * b) * e >= (icc * c + idd * d)){
							if ((iaa * a + ibb * b) * maxdn <= (icc * c + idd * d) * maxdd){
								maxdn = (icc * c + idd * d);
								maxdd = (iaa * a + ibb * b);
								raa = iaa;
								rbb = ibb;
								rcc = icc;
								rdd = idd;
							}
						}
					}
				}		
			}		
		}		
	}
	cout << (raa * a * 100 + rbb * b * 100 + rcc * c + rdd * d) << " " << (rcc * c + rdd * d) << '\n';
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	M1, D1 = inputMap()
	M2, D2 = inputMap()

	if M1 != M2:
		print(1)
	else:
		print(0)


if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>

using namespace std;

int main() {

    long long n, m;
    cin >> n >> m;

    vector<long int> a(n);
    double ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        ans += a[i];
    }
    ans /=  4 * m;

    int tmp = 0;
    for (int i = 0; i < n; i++){
            if (a[i] >= ans) {
                tmp++;
            }
    }

    if (tmp >= m) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int a, b;

    scanf("%d%d", &a, &b);
    if (a < b) {
        printf("a < b\n");
    } else if (a > b){
        printf("a > b\n");
    } else {
        printf("a == b\n");
    }

    return 0;
}


Measured memory_bytes: 2096
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

static class CodeJam
{
    class PriorityQueue<T>
    {
        private readonly List<T> m_list;
        private readonly Func<T, T, int> m_compare;
        private int m_count;
        public PriorityQueue(int capacity, Func<T, T, int> compare)
        {
            m_list = new List<T>(capacity);
            m_compare = compare;
            m_count = 0;
        }
        private int Add(T value)
        {
            if (m_count == m_list.Count)
            {
                m_list.Add(value);
            }
            else
            {
                m_list[m_count] = value;
            }
            return m_count++;
        }
        private void Swap(int a, int b)
        {
            T tmp = m_list[a];
            m_list[a] = m_list[b];
            m_list[b] = tmp;
        }
        public void Enqueue(T value)
        {
            int c = Add(value);
            while (c > 0)
            {
                int p = (c - 1) / 2;
                if (m_compare(m_list[c], m_list[p]) < 0) { Swap(p, c); } else { break; }
                c = p;
            }
        }
        public T Dequeue()
        {
            T value = m_list[0];
            m_list[0] = m_list[--m_count];
            int p = 0;
            while (true)
            {
                int c1 = p * 2 + 1;
                int c2 = p * 2 + 2;
                if (c1 >= m_count) { break; }
                int c = (c2 >= m_count || m_compare(m_list[c1], m_list[c2]) < 0) ? c1 : c2;
                if (m_compare(m_list[c], m_list[p]) < 0) { Swap(p, c); } else { break; }
                p = c;
            }
            return value;
        }
        public int Count { get { return m_count; } }
    }

    struct Work
    {
        public readonly int A;
        public readonly int B;
        public Work(string[] args)
        {
            A = int.Parse(args[0]);
            B = int.Parse(args[1]);
        }
    }

    static int Solve(int N, int M, Work[] works)
    {
        var q = new PriorityQueue<Work>(N, (x, y) => (y.B.CompareTo(x.B)));
        Array.Sort(works, (x, y) => (x.A.CompareTo(y.A)));
        int i = 0;
        int sum = 0;
        for (int a = 1; a <= M; ++a)
        {
            while (i < works.Length && works[i].A == a) { q.Enqueue(works[i++]); }
            if (q.Count > 0) { sum += q.Dequeue().B; }
        }
        return sum;
    }

    static void Main(string[] args)
    {
        int[] V = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int N = V[0], M = V[1];
        var works = new Work[N];
        for (int i = 0; i < N; ++i) { works[i] = new Work(Console.ReadLine().Split()); }
        Console.WriteLine(Solve(N, M, works));
    }
}


Measured memory_bytes: 17544
N = int(input())
X = list(map(int,input().split()))

X_sort = sorted(X)

mid_r = X_sort[N//2]
mid_l = X_sort[N//2-1]

for i in range(N):
    if X[i] <= mid_l:
        print(mid_r)
    else:
        print(mid_l)

Measured memory_bytes: 26180
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
#include<complex>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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




const ll INF = 1e9;


/******************************************************************************************/


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

	

	int a, b, p, q, r;
	cin >> a >> b >> p >> q >> r;

	cout << (q * a + r * b + p * b) / (double)(q + r) << endl;


	return 0;
}



Measured memory_bytes: 3256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

struct UnionFind {
	vector<int> par, siz;
	UnionFind(int n): par(n), siz(n, 1) {
		rep(i,n) par[i] = i;
	}
	int find(int x) {
		return par[x] == x ? x: par[x] = find(par[x]);
	}
	bool unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}
	bool issame(int x, int y) {
		return find(x) == find(y);
	}
};

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	rep(i,n) {
		cin >> v[i];
		v[i]--;
	}
	UnionFind uf(n);
	rep(i,k) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		uf.unite(v[a], v[b]);
	}
	int ans = 0;
	rep(i,n) {
		if (uf.issame(i,v[i])) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 4188
#include <stdio.h>

int main() {
	int x, a, b;
	scanf("%d %d %d", &x, &a, &b);
	
if(x > a && x > b){
	if(x - a > x - b){
		printf("B");
	}else{
		printf("A");
	}
}else if(x > a && x < b){
	if(x - a > b - x){
		printf("B");
	}else{
		printf("A");
	}
}else if(x < a && x > b){
	if(a - x > x - b){
		printf("B");
	}else{
		printf("A");
	}
}else if(x < a && x < b){
	if(a - x > b - x){
		printf("B");
	}else{
		printf("A");
	}
}
	
	return 0;
}

Measured memory_bytes: 1620
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

int *buildFail(char *p) {
  int m = strlen(p);
  int *fail = new int[m+1];
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}
int match(char *t, char *p, int *fail) {
  int n = strlen(t), m = strlen(p);
  int count = 0;
  for (int i = 0, k = 0; i < n; ++i) {
    while (k >= 0 && p[k] != t[i]) k = fail[k];
    if (++k >= m) {
      ++count; // match at t[i-m+1 .. i]
      k = fail[k];
    }
  }
  return count;
}

int main(){
	int n,m;
	char in[1000010];
	char str[1000010];
	
	while(scanf("%d",&n),n!=0){
		scanf("%d %s",&m,in);
		for(int i=1; i<=2*n+1; i+=2){
			str[i-1] = 'I';
			str[i] = 'O';
		}
		str[2*n+1] = 0;
		//puts(str);
		printf("%d\n",match(in,str,buildFail(str)));
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll modpow(ll n,ll k){
  if(k == 1){
    return n;
  }else if(k == 0){
    return 1;
  }else if(k%2==0){
    ll memo = modpow(n,k/2)%MOD;
    return memo*memo%MOD;
  }else{
    return n * modpow(n,k-1)%MOD;
  }
}

int main(){

  int n;
  cin>>n;
  int a[n];
  REP(i,n){
    cin>>a[i];
  }
  int LGCD[n];
  int RGCD[n];
  LGCD[0] = a[0];
  RGCD[n-1] = a[n-1];
  for(int i=1;i<n;i++){
    LGCD[i] = gcd(LGCD[i-1],a[i]);
    RGCD[n-1-i] = gcd(RGCD[n-i],a[n-1-i]);
  }

  int ans = 0;
  REP(i,n){
    if(i==0){
      ans = max(ans,RGCD[1]);
    }else if(i==n-1){
      ans = max(ans,LGCD[n-2]);
    }else{
      ans = max(ans,gcd(LGCD[i-1],RGCD[i+1]));
    }
  }

  cout<<ans<<endl;

 

  return 0;
}

Measured memory_bytes: 1408
H, W = map(int, input().split(' '))

S = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j, sij in enumerate(input()):
        S[i][j] = sij

flag = True

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            if 0 <= i-1 and S[i-1][j] == '#' or 0 <= j-1 and S[i][j-1] == '#' or j+1 < W and S[i][j+1] == '#' or i+1 < H and S[i+1][j] == '#':
                continue
            else:
                flag= False
                break
    if flag == False:
        break

if flag:
    print('Yes')
else:
    print('No')


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

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

	ll ans = 0;
	ll n,k;
	cin>>n>>k;
	
	if(n == 1){
		cout<<k<<endl;
		return 0;
	}
		
	ans  = k;
	ans *=  (ll)pow((k-1),(n-1));
	cout<<ans<<endl; 
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define MOD (1000000007)
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pb push_back

#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

ll keta(ll n){
  string s = to_string(n);
  ll num = s.size();
  return num;
}

const ll INF = 1LL << 60;

const int dh[4] = {1,0,-1,0};
const int dw[4] = {0,1,0,-1};

struct Edge{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w){}
};
using Graph = vector<vector<Edge>>;
using P = pair<ll, int>;

const int MAX = 5e5;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
  if(n >= MAX){
    ll tmp = 1;
    rep(i,k){
      tmp *= (n-i);
      tmp %= MOD;
    }
    return tmp*finv[k]%MOD;
  }

  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll POW(ll x, ll n){
  ll ret = 1;
  while(0 < n){
    if(n%2 == 0){
      x = x*x%MOD;
      n = n >> 1;
    }
    else{
      ret = ret*x%MOD;
      n--;
    }
  }
  return ret;
}

int main(){
  int n,Q; cin >> n >> Q;
  vector<tuple<int,int,int>> a;
  rep(i,n) {
    int s,t,x; cin>>s>>t>>x;
    a.pb(make_tuple(x,s-x,t-x));
  }
  sort(all(a));
  set<pii> s;
  rep(q,Q) {
    int d; cin >> d;
    s.insert(pii(d,q));
  }

  vi ans(Q,-1);
  rep(i,n) {
    int x,l,r;
    tie(x,l,r) = a[i];
    auto it = s.lower_bound(pii(l,1));
    while(it != s.end()){
      if(it->first >= r) break;
      ans[it->second] = x;
      s.erase(it++);
    }
  }

  rep(q,Q) cout << ans[q] << endl;
}


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

using namespace std;

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

  vector<int> st(n);
  vector<int> go(n);
  st[0]=1; go[n-1]=1;
  for(int i=0;i<n;++i){
    if(st[i])
      for(int j=d[i]/10;j>0;--j)
	if(i+j<n) {
	  if(st[i+j]) break;
	  st[i+j]=1;
	}
    if(go[n-(i+1)])
      for(int j=d[n-(i+1)]/10;j>0;--j)
	if(n-(i+j+1)>=0){
	  if(go[n-(i+j+1)]) break;
	  go[n-(i+j+1)]=1;
	}
    if(st[n-1] && go[0]) break;
  }
  
  if(st[n-1] && go[0]) cout << "yes";
  else cout << "no";
  cout <<endl;
  
  return 0;
}



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

using namespace std;

int main(){
    int l, r;
    cin >> l >> r;
    set<int> rem;
    for(int i = l; i <= r && rem.size() < 2019; i++) rem.insert(i % 2019);
    vector<int> remm;
    for(int i: rem) remm.push_back(i);
    int res = 2018;
    for(int i = 0; i < remm.size(); i++){
        for(int j = i + 1; j < remm.size(); j++){
            res = min(res, (remm[i] * remm[j]) % 2019);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

int main() {
  int n, m; cin >> n >> m;
  int result = (n-1) * (m-1);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
a = [input() for i in range(H)]
a = [i for i in a if '#' in i]

sharp = []
for i in range(W):
    flg = 0
    for j in range(len(a)):
        if a[j][i] == '#':
            flg = 1
    if flg == 1:
        sharp.append(i)

for i in range(len(a)):
    ans = ''
    for j in sharp:
        ans += a[i][j]
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
ll GCD(ll a,ll b){return b?GCD(b,a%b):a;}
ll LCM(ll a,ll b){return (a*b)/GCD(a,b);}
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(a + b, min(b + c, a + c)) << endl;
}


Measured memory_bytes: 764
n = int(input())

p = list(map(float,input().split()))

#dp[n][n]

dp = [[0 for i in range(n+1)] for j in range(n+1)]

dp[0][0]=1.0

for i in range(1,n+1):
  for j in range(0,n+1):
    if j==0:
      dp[i][j] = (1.0 - p[i-1])* dp[i-1][j]
    else:
      dp[i][j] = p[i-1] * dp[i-1][j-1] + (1.0 - p[i-1])* dp[i-1][j]
      
res = 0.0      
for i in range(n//2+1,n+1):
  res += dp[n][i]
  
  
print(res)

Measured memory_bytes: 259848
#include <iostream>

using namespace std;

int xp1, yp1, xp2, yp2, xp3, yp3, xk, yk, xs, ys;

bool side(int a, int b, int c, int d, int x, int y) {
  if (a == c)
    return x-a > 0;
  double p = (d - b) / (double)(c - a), q = b - p * a;
  return y > p * x + q;
}

bool inside_triangle(int x, int y) {
  return
    side(xp1, yp1, xp2, yp2, x, y) == side(xp1, yp1, xp2, yp2, xp3, yp3)
    && side(xp1, yp1, xp3, yp3, x, y) == side(xp1, yp1, xp3, yp3, xp2, yp2)
    && side(xp3, yp3, xp2, yp2, x, y) == side(xp3, yp3, xp2, yp2, xp1, yp1);
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> xp1 >> yp1 >> xp2 >> yp2 >> xp3 >> yp3 >> xk >> yk >> xs >> ys;
    if (inside_triangle(xk, yk) ^ inside_triangle(xs, ys))
      cout << "OK" << endl;
    else
      cout << "NG" << endl;
  }
  return 0;
}

Measured memory_bytes: 864
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 100005;

int n;
vector<int>e[maxn];

int dfs(int x){
  if(e[x].size()==0)return 0;
  vector<int>v;
  for(int i=0;i<e[x].size();i++){
    v.push_back(dfs(e[x][i]));
  }
  sort(v.begin(),v.end());
  int ret = v[0] + v.size();
  for(int i=0;i<v.size();i++)ret=max(ret,v[i]+int(v.size())-i);
  //cout<<x<<" : "<<ret<<endl;
  return ret;
}

int main() {
//  freopen("in.cpp","r",stdin);
  cin>>n;
  for(int i=2;i<=n;i++){
    int x;
    cin>>x;
    e[x].push_back(i);
  }
  cout<<dfs(1)<<endl;
  return 0;
}


Measured memory_bytes: 13568
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int a, b;
//vector<int> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> a>>b;
    if(min(a,b)==1&&max(a,b)==2){
        cout<<3<<"\n";
    }
    else if(min(a,b)==1&&max(a,b)==3){
        cout<<2<<"\n";
    }
    else{
        cout<<1<<"\n";
    }
}



Measured memory_bytes: 256