akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

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

const int maxn = 1e5 + 5;

int a[maxn];
int n;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    ll ans = 0;
    for(int i = 1;i <= n;i++){
        ans += a[i] / 2;
        if(a[i] & 1){
            if(i + 1 <= n and a[i + 1] > 0){
                a[i + 1]--;
                ans++;
            }
        } 
    }
    cout << ans << endl;
    return 0;
}


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

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

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

const int INF = 100000000;
const ll LINF = 1e18+5;

int main() {
    ll H, A;
    cin >> H >> A;
    cout << (H-1)/A + 1 << endl;
    return 0;
}

Measured memory_bytes: 256
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
pub fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}
}

use input::*;

fn main() {
    let n: usize;
    input!(n);
    let s = str2vec(&input_line_str());
    let mut ecount_right = 0;
    let mut wcount_left = 0;
    for z in &s {
        if *z == 'E' {
            ecount_right += 1;
        }
    }

    let mut ans = 999999;

    for z in 0..n+1 {
        ans = std::cmp::min(wcount_left + ecount_right, ans);

        if z == n{
            break;
        }
        if s[z] == 'W' {
            wcount_left += 1;
        } else {
            ecount_right -= 1;
        }
    }
    p(ans);
}

Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S,T;
  cin >> S >> T;
  
  int N;
  N=S.size();
  
  int changer = 0;
  for(int i=0;i<N;i++){
    if(S.at(i) != T.at(i)){
      changer ++;
    }
  }
  
  cout << changer << endl;
}

Measured memory_bytes: 3896
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a, b, k ;
  cin >> a >> b >> k ;
  if(a>=k){
    cout << a-k <<" " <<b <<endl ;
  }
  else{
    cout << 0 <<" " <<max((ll)0,b+a-k) <<endl ;
  }
  
  
  
  return 0 ;
}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <stdio.h>
#include <ctype.h>

using namespace std;

int main () {
    double b[10];
    double v1,v2;
    
    while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&b[0],&b[1],&b[2],&b[3],&b[4],&b[5],&b[6],&b[7],&b[8],&b[9],&v1,&v2)!=EOF){
        double l = b[0]+b[1]+b[2]+b[3]+b[4]+b[5]+b[6]+b[7]+b[8]+b[9];
        double t = l/(v1+v2);
        double l1 = t*v1;
        for(int i=0; i<10; i++){
            l1-=b[i];
            if(l1<=0){
                cout<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1228
/*-----rk_98-----*/
#include<bits/stdc++.h>
#define fast() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define mod 1000000007
#define eps 1e-9
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
using namespace std;
vector<vector<ll> > adj;
ll n;
ll memo[(ll)1e5 + 2][2];
bool vis[(ll)1e5 + 5] = {0};
pair<ll,ll> dfs(ll u)
{
	vis[u] = 1;
	pair<ll,ll> ans = {1,1};
	for( ll i =0 ; i<adj[u].size() ; i++)
	{
		if(vis[adj[u][i]] == 0)
		{
			pair<ll,ll> temp = dfs( adj[u][i] );
			ans.ff *= (temp.ff+ temp.ss);
			ans.ss *=temp.ff;
			ans.ff %= mod;
			ans.ss %= mod;
		}
	}
	// memo[u][0] = ans.ff;
	// memo[u][1] = ans.ss;
	return ans;
}
int main()
{
    //fast();
    memset(memo,-1,sizeof memo );
    cin>>n;
    adj.resize(n+2);
    for( ll i=0 ;i< n-1 ; i++)
    {
    	ll a,b;
    	cin>>a>>b;
    	adj[a].pb(b);
    	adj[b].pb(a);
    }
    pair<ll,ll> ans =dfs(1);
    cout<<(ans.ff + ans.ss) % mod<<endl;
}


Measured memory_bytes: 11520
import sys
input = sys.stdin.readline
def print_ans(ar, k):
    """Test Case
    >>> print_ans([1, 2, 4, 8, 9], 15)
    Yay!
    >>> print_ans([15,18,26,35,36],18)
    :(
    """
    flg = False
    for i in range(4):
        for j in range(i+1,5):
            if ar[j] -ar[i] > k:
                flg = True
                break
        if flg:
            break
    if flg:
        print(":(")
    else:
        print("Yay!")


if __name__ == '__main__':
    ar = [ int(input().rstrip()) for _ in range(5)]
    k = int(input().rstrip())
    print_ans(ar, k)




Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#define LEN 100005

typedef struct pp {
  char name[100];
  int t;
} P;

int head, tail, n;
P Q[LEN];

void enqueue(P x)
{
  Q[tail] = x;
  tail = (tail+1)%LEN;
}

P dequeue(void)
{
  P x;
  x = Q[head];
  head = (head+1)%LEN;
  return x;
}

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

int main()
{
  int elaps, c, i, q;
  P u;

  elaps = 0;
  
  scanf("%d %d",&n,&q);

  for(i=1;i<=n;i++){
    scanf("%s",Q[i].name);
    scanf("%d",&Q[i].t);
  }

  head = 1;
  tail = n+1;

  while(head!=tail){
    u = dequeue();
    c = min(q,u.t);
    u.t -= c;
    elaps += c;
    if(u.t>0) enqueue(u);
    else printf("%s %d\n",u.name,elaps);
  }

  return 0;

}








Measured memory_bytes: 11864
#include<bits/stdc++.h>
using namespace std;
int INF=1e9;
int R,C;
 
char s[128][20];
int len[128];
int dp[2][(1<<16)];
 
int main(){
  scanf("%d %d",&R,&C);
  for(int i=0;i<R;i++){
    scanf("%s",s[i]);
    len[i]=strlen(s[i]);
  }
   
 
  fill( (int*)dp[0], (int*)dp[2], -INF);
  dp[0][0]=0;
 
  int ai=1,bi=0;
  int ans=0;
  for(int i=0;i<=R;i++){
 
     
    for(int j=0;j<C;j++){
 
      swap(ai,bi);

      for(int bit=0;bit<(1<<C);bit++)dp[bi][bit]=-INF;
      
      for(int bit=0;bit<(1<<C);bit++){
        if(dp[ai][bit]==-INF)continue;
 
        if(i>0 && j==0 && __builtin_popcount(bit) != len[i-1])continue;
        if(i==R&&j==0)ans=max(ans,dp[ai][bit]);
         
        if(i==R)continue;
        int a=0,b=0,cost=dp[ai][bit];
        for(int k=0;k<C-j;k++)a+=(bit>>k&1);
        for(int k=C-j;k<C;k++)b+=(bit>>k&1);
         
        int nbit=bit>>1;
        dp[bi][nbit]=max(dp[bi][nbit],cost);
         
 
        if(b==len[i])continue;
         
        int flg=0;
        if(bit&1 && s[i][b]==s[i-1][len[i-1]-a])flg++;
        if(bit>>(C-1)&1)
          if(b>0&&s[i][b-1]==s[i][b])flg++;
         
        nbit=(bit|(1<<C))>>1;
        dp[bi][nbit]=max(dp[bi][nbit],cost+flg);
   
      }
    }
  }
  cout<<ans*2<<endl;
       
  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int h,w,k; cin >> h >> w >> k;
  vector<vector<char>> c(h, vector<char>(w));
  rep(i,h) {
    rep(j,w){
      cin >> c[i][j];
    }
  }

  int res = 0;
  rep(hmask,(1 << h)) {
    rep(wmask,(1 << w)) {
      int cnt = 0;
      rep(i,h) {
	rep(j,w) {
	  if(((hmask >> i) & 1) || ((wmask >> j) & 1)) continue;
	  if(c[i][j] == '#') cnt++;
	}
      }
      if(cnt == k) res++;
    }
  }


  cout << res << "\n";

  return 0;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mp make_pair
#define ll long long
#define all(x) x.begin(), x.end()
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define pdd pair< double, double >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 2010
#define inf 1e14
#define mod 1000000007

int main()
{

    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    bool tf=0;
    for(int i=1; i <= 100; i++)
    {

        ll x = a*i;
        if(x%b==c) tf=1;
    }
    if(tf) printf("YES\n");
    else printf("NO\n");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define vll vector<ll>
#define mod(n) n % 1000000007
#define sp << " "
#define precision(n) cout << fixed << setprecision(n);
#define startTime time_t start, end;time(&start);
#define endTime time(&end);double tt = double(end-start);cout<<"Time taken : "<<fixed<<tt<<setprecision(5);cout <<" sec"<< endl;
 
using namespace std; 

int main() { 
    IOS;
    string s, t;
    cin >> s >> t;
    vector<vll> dp(3001, vll(3001, 0));
    for (int i = 1; i <= s.length(); i++) {
    	for (int j = 1; j <= t.length(); j++) {
    		if (s[i - 1] == t[j - 1]) {
    			dp[i][j] = dp[i - 1][j - 1] + 1;
    		} else {
    			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    		}
    	}
    }
    ll a = s.length(), b = t.length();
    string ans;
    while (a > 0 && b > 0) {
    	if (s[a - 1] == t[b - 1]) {
    		ans = s[a - 1] + ans;
    		a--; b--;
    	} else {
    		if (dp[a - 1][b] < dp[a][b - 1]) b--; 
    		else a--;
    	}
    }
    cout << ans << endl;
}   

Measured memory_bytes: 70784
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main = getLine >> readLine >>= print . solve 

solve :: [Int] -> Int
solve = count 0 . zip [1..]
    where
        count acc ((i, x) : y : zs)
            | i == x = count (acc + 1) zs
            | otherwise = count acc $ y : zs
        count acc ((i, x) : _)
            | i == x = acc + 1
            | otherwise = acc
        count acc _ = acc

readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 2172
n , m = map(int,input().split())
war = [[] for i in range(n-1)]
for i in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    war[a].append(b)
utan = n
ans = 0
for i in reversed(range(n-1)):
    for j in war[i]:
        if utan >= j:
            ans += 1
            utan = i
            break
print(ans)
    

Measured memory_bytes: 22636
N = int(input())
H = list(map(int,input().split()))

output = 0
count = 0

for i in range(N-1):
    now = H[i]
    if H[i+1] <= H[i]:
        count += 1
    else:
        count = 0
    if count > output:
        output = count

print(output)

Measured memory_bytes: 14228
#include <cstdio>
using namespace std;

int n;
int p;

int main() {
  while (1) {
    int nums[50] = {0};

    scanf("%d%d", &n, &p);
    if (n == 0 && p == 0) return 0;

    int defp = p;
    int idx = 0;
    while (1) {
      if (p > 0) {
        nums[idx]++;
        p--;
        if (nums[idx] == defp) break;
      } else {
        p = nums[idx];
        nums[idx] = 0;
      }

      idx = (idx+1)%n;
    }

    printf("%d\n", idx);
  }
}

Measured memory_bytes: 2684
from collections import Counter 
from collections import defaultdict
from collections import deque
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))


s=input()

for i in range(1,len(s)):
    if s[i]==s[i-1]:
        print("Bad")
        exit()

print("Good")


Measured memory_bytes: 12496
const solve = (n, ms) => {
  let rest = ms.sort((a, b) => a - b).concat()
  while (rest.length > 1) {
    let next = []
    let m = rest[0]
    next.push(m)
    for (var i = 1; i < rest.length; i++) {
      let b = rest[i] % m
      if (b == 0) {
        continue
      } else {
        next.push(b)
      }
    }
    rest = next.sort((a, b) => a - b)
  }
  return rest[0]
}
const main = (input) => {
  const [n, ms] = input.split("\n")

  return solve(n, ms.split(" ").map(Number))
}

if (process.env.NODE_ENV !== "test") {
  const input = require("fs").readFileSync("/dev/stdin", "utf8")
  console.log(main(input.trim()))
}


Measured memory_bytes: 28736
a,b,m = map(int,input().split())
al = list(map(int,input().split()))
bl = list(map(int,input().split()))
disc = [[]]*m
for i in range(m):
  disc[i] = list(map(int,input().split()))
mina = 100000
minb = 100000
for i in range(a):
  mina = min(mina,al[i])
for i in range(b):
  minb = min(minb,bl[i])
total = mina+minb
for i in range(m):
  total = min(total,al[disc[i][0]-1]+bl[disc[i][1]-1]-disc[i][2])
print(total)

Measured memory_bytes: 38568
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[] = {1,0,-1,0};
int dy[] = {0,-1,0,1};
const int INF = 1001001001;

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

int main(){
    ll A,B;
    cin >> A >> B;
    ll x = gcd(A,B);

    set<ll> a;
    ll i = 2;
    while(x >= i*i){
        if(x%i == 0){
            x /= i;
            a.insert(i);
        }
        else{
            i++;
        }
    }
    a.insert(x);
    a.insert(1);
    cout << a.size() << endl;
}


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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;

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

    int happy = 0;
    happy += (x / 500) * 1000;
    happy += (x % 500 / 5) * 5;
    cout << happy << endl;

    return 0;
}


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

int main(){
    int s, c = 0;
    cin >> s;
    c = c + (s % 10);
    s = s / 10;
    c = c + (s % 10);
    s = s / 10;
    c = c + (s % 10);
    cout << c << endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m,cst,val;
    cin>>n>>m;
    vector<int>weight(n,0);
    vector<int>cost(n,0);
    
    vector<vector<long long>>dp(n+1,vector<long long>(100001,INT_MAX));
    for(int i=0;i<n;i++)
    {
        cin>>val>>cst;
        weight[i]=val;
        cost[i]=cst;
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=100000;j++)
        {
            if(j==0)
            dp[i][j]=0;
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=100000;j++)
        {
            
            if(j-cost[i-1]>=0)
            {
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-cost[i-1]]+weight[i-1]);
            }
            else 
            dp[i][j]=dp[i-1][j];
        }
    }
    long long ans=0;
    for(int i=1;i<=100000;i++)
    {
        if(dp[n][i]<=m)
        ans=i;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 80256
n, m = map(int,input().split())
a = list(int(input()) for _ in range(m))
dp = [[] for _ in range(n + 1)]
dp[0] = 1
# j = 0
if m == 0:
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    print(dp[n])
    exit()
if a[0] == 1:
    dp[1] = 0
    j = 1
else:
    dp[1] = 1
    j = 0
for i in range(2, n + 1):
    # print(i, dp)
    if j < m:
        if a[j]  == i:
            dp[i] = 0
            j += 1
            continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

Measured memory_bytes: 19884
#include <cstdio>
#include <iostream>
#include <cmath>

#define INF 1000000.0

using namespace std;

struct P{
	double x, y;
	P(double X=0.0, double Y=0.0){
		x = X;
		y = Y;
	} 
	P operator+( const P &in ){
		P tmp( x + in.x , y + in.y );
		return tmp;
	}
	P operator-( const P &in ){
		P tmp( x - in.x , y - in.y );
		return tmp;
	}
	P operator*( const double &in ){
		P tmp( x * in , y * in );
		return tmp;
	}
	double dot( const P &in ){
		return x * in.x + y * in.y;
	}
	double cross( const P &in ){
		return x * in.y - y * in.x;
	}
};


//交差しているか求める(どの3点も同直線上にない)
bool check(P a1, P a2, P b1, P b2){
	P va = a2 - a1, vb = b2 - b1;
	P v1 = b1 - a1, v2 = b2 - a2;

	if( ( va.cross( v1 ) * va.cross( v2 ) ) < 0.0 &&
		( vb.cross( v1 ) * vb.cross( v2 ) ) < 0.0 )
		return true;
	
	return false;
}

//2円の交点を求める(2円の中心の中点cからのベクトルvを返す(交点はc±v) )
void circlecross(P a, double ra, P b, double rb, P *p1, P *p2){

	double c = sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
	double r = (ra*ra - rb*rb + c*c ) / ( 2.0 * c*c );
	double e = c * r;
	double d = sqrt( ra*ra - e*e );
	
	P tmp;
	tmp.x = d * (a.y - b.y) / c;
	tmp.y = d * (b.x - a.x) / c;

	P cen = a * (1.0-r) + b * r;
	
	*p1 = cen + tmp;
	*p2 = cen - tmp;
}

int n;

int solve(){
	P c[100], p[101][2];
	double r[100];
	double dist[205][205];
	
	cin >> c[0].x >> c[0].y >> r[0];
	p[0][0] = c[0];
	p[0][1] = c[0];
	for(int i=1; i<n; i++){
		cin >> c[i].x >> c[i].y >> r[i];
		circlecross( c[i-1], r[i-1], c[i], r[i], &p[i][0], &p[i][1]);
	}
	p[n][0] = c[n-1];
	p[n][1] = c[n-1];

	//求める
	fill( dist[0], dist[0]+205*205, INF );
	for(int i=0; i<n*2; i++){
		for(int j=i+1; j<=n*2; j++){
			bool f=true;
			for(int k=i/2+1; k<j/2; k++){
				if( !check( p[i/2][i%2], p[j/2][j%2], p[k][0], p[k][1] ) )
					f = false;
			}
			if( f ){
				double x = p[i/2][i%2].x - p[j/2][j%2].x;
				double y = p[i/2][i%2].y - p[j/2][j%2].y;
				dist[i][j] = sqrt( x*x + y*y );
			}
		}
	}
	//最短経路
	for(int k=1; k<n*2; k++){
		for(int i=0; i<=n*2; i++){
			for(int j=0; j<=n*2; j++){
				dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
			}
		}
	}

	printf("%0.6f\n", dist[0][n*2] );
	
	return 0;
}

int main(){
	while( cin >> n, n ){
		solve();
	}
	return 0;
}

Measured memory_bytes: 1584
#include <stdio.h>
int main(void){
	int a=0,b=0,sum=0,n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a);
		if(a>=b){
			sum = sum+1;
			b = a;
		}
	}
	printf("%d\n",sum);
	return 0;
}

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

#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define ull unsigned long long
#define ll long long
#define sz(a) a.size()
#define all(s) s.begin(), s.end()
#define rall(s, n) s, s + n
#define x first
#define y second
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define pii pair <int, int>
#define pll pair <ll, ll>
#define INF 1000000000
#define mod 1000000007
#define reset(a, nilai) memset(a, nilai, sizeof(a))
using namespace std;

ll n, k;
int main () {
	IOS;
	
	cin >> n >> k;
	ll rem = n % k;
	cout << min(rem, k - rem) << endl;
	return 0;
}


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

signed main() {
	long long a, b, c;
	cin >> a >> b >> c;

	long long ans = 0;
	if (c >= a + b + 2)  cout << a + b + 1 + b << endl;
	else cout << b + c << endl;

	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;

struct Cow{
    ll k, l, r, mode;

    bool operator < (const Cow c) const {
        if(this->k == c.k){
            if(mode==1){
                return (this->r - this->l) < (c.r - c.l);
            }else{
                return (this->l - this->r) < (c.l - c.r);
            }
        }else{
            return this->k < c.k;
        }
    }

};

ll solve(vector<Cow> & ks, ll mode=0){
    ll ans = 0;
    if(ks.size()==0){
        return ans;
    }
    // cout << "##### start mod =" << mode << " #####" <<endl;
    sort(ks.begin(), ks.end());
    priority_queue<ll, vector<ll>, greater<ll>> PQ;
    // PQ.push(1);
    // PQ.push(10);
    // PQ.push(3);
    // cout << PQ.top()<< endl;
    // PQ.pop();
    // cout << PQ.top()<< endl;
    // exit(0);
    rep(i, ks.size()){
        // cout << "i=" << i << "ks[i].k,l,r=" << ks[i].k << "," << ks[i].l << "," << ks[i].r  << " ans=" << ans<<endl;
        auto this_c = ks[i];
        ll this_v;
        if(mode==0){
            this_v = this_c.l - this_c.r;
        }else{
            this_v = this_c.r - this_c.l;
        }
        if(this_c.k <= 0){
            continue;
        }
        if(PQ.size()<this_c.k){
            PQ.push(this_v);
            ans += this_v;
        }else{
            if(PQ.top()<this_v){
                ans -= PQ.top();
                PQ.pop();
                ans += this_v;
                PQ.push(this_v);
            }
        }
        // cout << "this ans = " << ans << " this_v=" << this_v <<endl;
    }

    return ans;

}


void Main(){
    ll T, N, K, L, R;
    sll(T);
    rep(i, T){
        sll(N);
        vector<Cow> ls;
        vector<Cow> rs;
        ll ans = 0;
        rep(i, N){
            cin >> K >> L >> R;
            if(L>=R){
                ls.emplace_back(Cow{K,L,R,0});
            }else{
                rs.emplace_back(Cow{N-K,L,R,1});
            }
            ans += min(L, R);
        }
        // cout << "base ans=" << ans <<endl;
        ans += solve(ls, 0);
        // cout << "base2 ans=" << ans <<endl;

        ans += solve(rs, 1);
        cout << ans <<endl;

        
    }

}

int main(){
    Main();
    // string S = "ksdfjl";
    // char v = S[3];
    // S[3] = 'a';
    // cout << S <<endl;
}

Measured memory_bytes: 10952
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=0
for i in range(n):
    aa=a[i]
    c+=min(a[i],b[i])
    a[i]=max(0,a[i]-b[i])
    if a[i]==0:
        c+=min(a[i+1],b[i]-aa)
        a[i+1]=max(0,a[i+1]+aa-b[i])
print(c)


Measured memory_bytes: 18396
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;



int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int p = 0;
  while (1) {
    if (p * (p - 1) == 2 * n) {
      break;
    }
    if (p * (p - 1) > 2 * n) {
      cout << "No" << endl;
      return 0;
    }
    p++;
  }
  vector<VI> ans(p);
  int cur = 1;
  REP(i, 0, p) {
    REP(j, 0, i) {
      ans[i].push_back(cur);
      ans[j].push_back(cur);
      cur++;
    }
  }
  cout << "Yes" << endl;
  cout << p << endl;
  REP(i, 0, p) {
    cout << ans[i].size();
    REP(j, 0, ans[i].size()) {
      cout << " " << ans[i][j];
    }
    cout << endl;
  }
}


Measured memory_bytes: 2304
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

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

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

  int n;
  cin >> n;
  int a[n], b[n], c[n - 1];
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  for(int i = 0; i < n - 1; i++) cin >> c[i];

  int sum = 0;
  for(int i = 0; i < n; i++){
    sum += b[a[i] - 1];
    if(i - 1 >= 0 && a[i - 1] + 1 == a[i]) sum += c[a[i - 1] - 1];
  }

  cout << sum << endl;

  return 0;
}



Measured memory_bytes: 384
import std.stdio;
import std.algorithm;
import std.math;
import std.conv;
import std.string;

T readNum(T)(){
  return readStr.to!T;
}

T[] readNums(T)(){
  return readStr.split.to!(T[]);
}

string readStr(){
  return readln.chomp;
}

void main(){
  auto s = readNums!int;
  auto n = s[0], x = s[1];

  auto l = readNums!int;

  int ret;
  int d;

  if(d <= x) ret++;
  foreach(i; l){
    d += i;
    if(d <= x) ret++;
  }

  writeln(ret);
}


Measured memory_bytes: 256
#include <stdio.h>

int		is_parindorm(char *str, int start, int end)
{
	while (start < end)
	{
		if (str[start] != str[end])
			return (0);
		start++;
		end--;
	}
	return (1);
}

int		main()
{
	char	str[100];
	int		N, mid1, mid2, r;

	r = scanf("%s\n", str);
	if (r == -1)
		return (0);
	N = 0;
	while ('a' <= str[N] && str[N] <= 'z')
		N++;
	N--;
	mid1 = (N - 1) / 2;
	mid2 = (N + 3) / 2;
	if (is_parindorm(str, 0, mid1) && is_parindorm(str, mid2, N) && is_parindorm(str, 0, N))
		printf("Yes\n");
	else
		printf("No\n");
	return (0);
}


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

int main() {

    int H, W;
    cin >> H >> W;

    vector<string> line;

    for (int i = 0; i < H; i++) {
        string s;
        cin >> s;
        line.push_back(s);
    }

    string bar;
    for (int i = 0; i < W + 2; i++) {
        bar += "#";
    }

    cout << bar << endl;

    for (int i = 0; i < H; i++) {
        string s;
        s = "#" + line.at(i) + "#";
        cout << s << endl;

    }

    cout << bar << endl;

}


Measured memory_bytes: 3620
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// to container
template <class C>
void input(C &c)
{
    for_each(c.begin(), c.end(), [](auto &i) { cin >> i; });
}

// to number, string
template <class T>
T input()
{
    T data;
    cin >> data;
    return data;
}

int main()
{
    ll A = input<ll>(), B = input<ll>(), C = input<ll>();

    ll res = 0;
    while (true)
    {
        if (A % 2 != 0 || B % 2 != 0 || C % 2 != 0)
        {
            break;
        }

        if (A == B && B == C)
        {
            cout << -1 << endl;
            return 0;
        }

        ll tmpA = A, tmpB = B, tmpC = C;
        A = (tmpB / 2) + (tmpC / 2);
        B = (tmpA / 2) + (tmpC / 2);
        C = (tmpA / 2) + (tmpB / 2);
        res++;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <complex>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,C,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
const long double EPS = 1e-9;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>S;
    N = S.size();
    T = "";
    rep(i,N){
        if(i&1) continue;
        T.push_back(S[i]);
    }
    cout<<T<<endl;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ITP1_9_B
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var cards = Console.ReadLine();
                if (cards == "-")
                {
                    return;
                }

                var times = 0;
                {
                    var input = Console.ReadLine();
                    times = int.Parse(input);
                }

                var startIndex = 0;
                for (var i = 0; i < times; ++i)
                {
                    var input = Console.ReadLine();
                    var splitIndex = int.Parse(input);

                    startIndex = (startIndex + splitIndex) % cards.Length;
                }

                for (var h = 0; h < cards.Length; ++h)
                {
                    var index = (startIndex + h) % cards.Length;
                    Console.Write(cards[index]);
                }
                Console.WriteLine();
                    //cards = cards.Substring(splitIndex) + cards.Substring(0, splitIndex);

                //Console.WriteLine(cards);
            }
        }
    }
}

Measured memory_bytes: 5280
using System;
class Program{
  static void Main(string[] args){
    int n = int.Parse(Console.ReadLine());
    int ans = 0;
    string[] pstring = Console.ReadLine().Split(' ');
    string[] qstring = Console.ReadLine().Split(' ');
    int[] p = new int[n];
    int[] q = new int[n];
    for (int i = 0; i < n; i++) {
      p[i] = int.Parse(pstring[i]);
      q[i] = int.Parse(qstring[i]);
    }
    int pnum = 0;
    int qnum = 0;
    bool[] pused = new bool[n];
    bool[] qused = new bool[n];
    for (int i = 0; i < n; i++) {
      int factnum = fact(n - 1 - i);
      int pweight = p[i] - 1;
      int qweight = q[i] - 1;
      for (int j = 0; j < p[i]; j++) {
        if (pused[j]) {
          pweight--;
        }
      }
      for (int j = 0; j < q[i]; j++) {
        if (qused[j]) {
          qweight--;
        }
      }
      pused[p[i] - 1] = true;
      qused[q[i] - 1] = true;
      pnum += factnum * pweight;
      qnum += factnum * qweight;
    }
    Console.WriteLine(Math.Abs(pnum-qnum));
  }
  
  static int fact(int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) {
      ans *= i;
    }
    return ans;
  }
}


Measured memory_bytes: 11092
#include<iostream>
using namespace std;
int main()
{
	int n,a;
	cin>>n;
	a=n%10;
	if(a==2||a==4||a==5||a==7||a==9) cout<<"hon"<<endl;
	else if(a==0||a==1||a==6||a==8) cout<<"pon"<<endl;
	else if(a==3) cout<<"bon"<<endl;
	return 0;
}

Measured memory_bytes: 3592
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		try (Scanner scan = new Scanner(System.in)) {
 
			int N = scan.nextInt();
			int K = scan.nextInt()+1;
 			int[] A = new int[N];
			
			for(int i=0; i<N; i++) {
				A[i] = scan.nextInt();
			}
			
          int[] dp = new int[K];
          
          for(int i=1; i<K; i++) {
            for(int j=0; j<N; j++) {
              int num = i-A[j];
              if(num >= 0 && dp[num]==0) {
               dp[i] = 1;
               break; 
              }
            }
          }
          
          if(dp[K-1]==1) {
            System.out.println("First");
          } else {
            System.out.println("Second");
          }
			
		}
	}
}

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

int main(){
  ll n;
  cin>>n;
  ll logn=floor(log2(n));
  vector<ll> x(n);
  rep(i,n)cin>>x[i];
  ll l,q;
  cin>>l>>q;
  vector<vector<ll>> next(n,vector<ll>(logn+1));
  rep(i,n){
    next[i][0]=upper_bound(x.begin(), x.end(), x[i]+l)-1-x.begin();
  }
  rep(k,logn){
    rep(i,n){
      next[i][k+1]=next[next[i][k]][k];
    }
  }
  rep(i,q){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    if(a>b)swap(a,b);
    ll ans=0;
    ll now=a;
    for(int k=logn;k>=0;k--){
      if(next[now][k]<b){
        now=next[now][k];
        ans+=(1<<k);
      }
    }
    cout<<ans+1<<endl;
  }
}



Measured memory_bytes: 19584
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
//const ll MOD = 13ll;
//const ll MOD=(ll)998244353;
const ll INF=(ll)1e18+10;
const double PI = 2.0*acos(0);
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int ca){
    string s[2]; cin>>s[0]>>s[1];

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            if(s[i][j]!=s[1-i][2-j]){
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<"YES"<<endl;

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int ar[100005];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		ar[i]=n;
	}
	for (int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		ar[a]=min(ar[a],b-a);
	}
	int ans=0;
	int car=n;
	for (int i=1;i<=n;i++){
		if (car==0){
			ans++;
			car=n;
		}
		car=min(car,ar[i]);
		car--;
	}
	printf ("%d\n",ans);
}

Measured memory_bytes: 640
#include <iostream>
#include <string> 
#include <vector> 
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include<math.h>
using namespace std;

//#define int long long
#define endl "\n"
#define fir first
#define sec second
#define fro front
#define m_p make_pair
#define mod 1000000007
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define all(v)  v.begin(),v.end()
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
using namespace std;

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}

int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res* a% mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}
int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}


int main() {
	int a, b, c,d,e,f;
	cin >> a >> b >> c;
	e = min(a, min(b, c));
	a -= e;
	b -= e;
	c -= e;
	e = max(a, max(b, c));
	f = 3 * e - a - b - c;
	d = f / 2;
	if (f % 2 == 1) {
		d += 2;
	}
	cout << d << endl;
}



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

#define rep_(v, f, l) for (int v = (f), v##_ = (l); v < v##_; ++v)
#define rep(v, n) rep_(v, 0, n)
#define lep(v, n) rep_(v, 1, n + 1)
#define rrep_(v, f, l) for (int v = (l), v##_ = (f); v >= v##_; --v)
#define rrep(v, n) rrep_(v, 0, n - 1)
#define rlep(v, n) rrep_(v, 1, n)
#define show_a(a, size) rep(a##_it, size) std::cout << a[a##_it] << " \n"[a##_it == a##_it_ - 1];
#define show_v(v) show_a(v, v.size())
#define eachv(v, i) rep(i, v.size())
#define reachv(v, i) rrep(i, v.size())
#define debug(x) std::cerr << #x << " = " << x << "\n";

using namespace std;

typedef long long int lint;

static inline int in(){ int x; scanf("%d", &x); return x; }
static inline lint inl(){ lint x; scanf("%lld", &x); return x; }

int main()
{
    int L, A, B, C, D;
    L = in();
    A = in();
    B = in();
    C = in();
    D = in();
    printf("%d\n", L - max((A + C - 1) / C, (B + D - 1) / D));
    return (0);
}

Measured memory_bytes: 1188
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
long long gcd(long long x, long long y)
{
    return y == 0 ? x : gcd(y, x % y);
}
int main()
{
    //ios::sync_with_stdio(false);
    long long a,b;
    scanf("%lld %lld",&a,&b);
    long long t = gcd(a, b);
    long long cnt = 1;
    long long lim = t;
    for(long long i = 2;i * i <= t;i++)
    {
        if(t % i == 0)
        {
            cnt++;
            while(t % i == 0)
            {
                t = t / i;

            }
        }
    }
    if(t > 1)
        cnt++;
    printf("%d\n",cnt);
    return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,fa[100010];
set<int> r[100010],b[100010];
queue<pair<int,int> > q;
int find(int x)
{
	if (fa[x]!=x)
	{
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		b[x].insert(y);
		b[y].insert(x);
	}
	for (int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		r[x].insert(y);
		r[y].insert(x);
		if (b[x].find(y)!=b[x].end())
		{
			q.push(make_pair(x,y));
		}
	}
	int cnt=0;
	while (!q.empty())
	{
		cnt++;
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		x=find(x);
		y=find(y);
		if (b[x].size()+r[x].size()>b[y].size()+r[y].size())
		{
			swap(x,y);
		}
		fa[x]=y;
		b[x].erase(y);
		b[y].erase(x);
		r[x].erase(y);
		r[y].erase(x);
		for (auto v:b[x])
		{
			if (r[y].find(v)!=r[y].end())
			{
				q.push(make_pair(y,v));
			}
		}
		for (auto v:r[x])
		{
			if (b[y].find(v)!=b[y].end())
			{
				q.push(make_pair(y,v));
			}
			r[v].erase(x);
			r[v].insert(y);
			r[y].insert(v);
		}
		r[x].clear();
		for (auto v:b[x])
		{
			b[v].erase(x);
			b[v].insert(y);
			b[y].insert(v);
		}
		b[x].clear();
	}
	if (cnt==n-1)
	{
		puts("YES");
	}
	else
	{
		puts("NO");
	}
    return 0;
}
//流水淡，碧天长，红尘一刹风乱，吹的散紫薇花瓣，吹不散因缘红线。

Measured memory_bytes: 29184
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

ll dp[110000][2];//dp[i][j]=j flag i桁 (a+b==lか） a+b==a^b 
int main(){cout<<fixed<<setprecision(20);
		   //桁dp?
           //1なら
           string s;
           cin>>s;
           int n=s.size();
           dp[0][0]=1;
           rep(i,1,n+1){
             int g=s[i-1]-'0';
             //0>0
             if(g==0){
               dp[i][0]+=dp[i-1][0];
             }
             else{
               dp[i][0]+=dp[i-1][0]*2;
             }
             //0>1
             //g==1
             //i桁め^が0
             if(g==1)dp[i][1]+=dp[i-1][0];
             //1>1
             dp[i][1]+=dp[i-1][1]*3;
             rep(j,0,2)dp[i][j]%=inf;
             //cout<<dp[i][1]<<endl;
           }
           cout<<(dp[n][0]+dp[n][1])%inf<<endl;
}

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

int main(){
    ll n, m; cin >> n >> m;
    vector<vector<ll> > lis(n, vector<ll>(2, 0));
    for(int i = 0; i < n; i++){
        cin >> lis[i][0] >> lis[i][1];
    }
    sort(lis.begin(), lis.end(), [](auto &x, auto &y){return x[0] < y[0];});
    ll ans = 0;
    int i = 0;
    while(m > 0){
        ans += lis[i][0] * min(m, lis[i][1]);
        m -= lis[i][1];
        i++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define mx 100000
#define pb push_back
#define siz(v) v.size();
typedef unsigned long  ull;
typedef long long  ll;
using namespace std;

int main()
{
 	ios_base::sync_with_stdio(0);
 	cin.tie(0); cin.tie(0);
	
	ll A,B,C;
	ll K;
	cin>>A>>B;
	cin>>C>>K;
	
	if (K<=A+B){
		if (A>K)
			cout<<K<<"\n";
		else
			cout<<A<<"\n";
	}
		
	else {
		cout<<A-(K-(A+B))<<"\n";
	}
	






 return 0;
 }


Measured memory_bytes: 3640
# coding: utf-8

a,b,c,x,y = map(int,input().split())

ans = min(a*x+b*y, a*x+c*2*y, b*y+c*2*x)

if x <= y:
    u = c*x*2+b*(y-x)
else:
    u = c*y*2+a*(x-y)
v = c*2*(max(x,y))
ans = min(ans,u,v)
print(ans)

Measured memory_bytes: 9168
import java.io.*;

public class Main{
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int a = Integer.parseInt(str[0]);
        int b = Integer.parseInt(str[1]);
        int c = Integer.parseInt(str[2]);
        int count = 0;

        for(; a <= b; a++){
            if( c % a == 0 )count++;
        }
        System.out.println(count);
    }
}

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

int main() {

    int N, K;
    cin >> N >> K;

    vector<int> A(N);
    int max = 0;
    int min = 1;
    int count;

    for(int i = 0; i < N; i++){
        cin >> A.at(i);
        if(max < A.at(i)){
            max = A.at(i);
        }
    }

    int answer = (max + min) / 2;

    while(1){

        count = 0;
        for(int i = 0; i < N; i++){ // すべての丸太の長さをanswer以下にするために必要な切断回数を求める
            if(A.at(i) % answer == 0){
                count += (A.at(i) / answer) - 1;
            }else{
                count += (A.at(i) / answer);
            }
        }

        if(count <= K){ // 条件を満たしており、もっと短いところを探索
            max = answer;
            answer = (min + max) / 2;
            if(max == min){
                break;
            }
        }else{ // 条件を満たしておらず、もっと長いところを探索
            min = answer + 1;
            answer = (max + min) / 2;
            if(max == min){
                break;
            }
        }

    }

    cout << answer << endl;

}

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

int main() {

  int n;
  cin >> n;
  vector<int> next(n);
  vector<int> flag(n,0);

  for(int i = 0; i < n; i++){
      cin >> next.at(i);
  }
  
  int curr = next.at(0);
  flag.at(0) = 1;
  int ans = 1;
  while(1){

       if( flag.at(curr-1) == 1 ){
         ans = -1;
         break;
       }else if( curr == 2 ){
         break;
       }else{
          flag.at(curr-1) = 1;
          curr = next.at(curr-1);
          ans++;
       }
         
  }

  cout << ans << endl;

}



Measured memory_bytes: 1024
n = int(input())
l = input().split()

count = 0
for i in range(0, n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if l[i] == l[j] or l[j] == l[k] or l[i] == l[k]:
        # break
        # continue
        pass
      elif int(l[i]) + int(l[j]) > int(l[k]) and int(l[i]) + int(l[k]) > int(l[j]) and int(l[j]) + int(l[k]) > int(l[i]):
        count += 1
        pass
      else:
        pass

print(count)

Measured memory_bytes: 9212
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    int n;
    cin >> n;
    int a[n];
    rep(i,n)a[i] = 0;
    rep(i,n-1){
        int x;
        cin >> x;
        a[x-1] += 1;
    }
    rep(i,n)cout << a[i] << endl;
    return 0;
}

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

using namespace std;

int main(){
  string s;
  getline(cin,s);
  int i=0;
  for(int j=0;j<s.size();j++){
    if(s[j]=='+'){
      i+=1;
    }else{
      i-=1;
    }
  }
  cout<<i;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdlib.h>
#include <cmath>
using namespace std;
typedef long long ll;
ll mod=1000000007;

int main(){
    int N; cin>>N;
    vector<ll> d(N);
    for(int i=0;i<N;i++) cin>>d.at(i);

    sort(d.begin(),d.end());
    ll K=d.at(N-1);
    ll half=K/2;
    //cout<<half<<endl;
    ll ans;
    ll RIGHT,LEFT;
    //if(half<0) ans=d.at(0);
    
        auto itr=lower_bound(d.begin(),d.end(),half);
        
        RIGHT=*itr;
        if(itr!=d.begin()) itr--; 
        LEFT=*itr;
    

    if(abs(RIGHT*2-K)>=abs(LEFT*2-K)) ans=LEFT;
    else ans=RIGHT;
    cout<<K<<' '<<ans<<endl;

}

Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long people = sc.nextLong() - 1;
		int num = 5;
		long carry[] = new long[num];
		for(int i = 0; i < num; i ++) {
			carry[i] = sc.nextLong();
		}
		Arrays.sort(carry);
		System.out.println(people / carry[0] + 5);
	}
}

Measured memory_bytes: 23124