akhauriyash/Code-Regression huggingface dataset:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = Counter(A)
ans = sum(A)
for b, c in X:
    v = ctr[b]
    ans = ans - b * v + c * v
    ctr[b] -= v
    ctr[c] += v
    print(ans)


Measured memory_bytes: 105912
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "No" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

int BE(int b,int e){
    int r=1;
    while(e){
        if(e&1){
            r=(r*b)%MOD;
        }
        b=(b*b)%MOD;
        e >>=1;
    }
    return r;
}

vector<int> fact_norm,fact_inv;
void fact_inverse(int N){
    REP(i,N+1){
        fact_norm.push_back(1);
        fact_inv.push_back(1);
    }
    for(int i=1;i<=N;i++){
        fact_norm[i]=(fact_norm[i-1]*i)%MOD;
    }
    for(int i=0;i<=N;i++){
        fact_inv[i]=BE(fact_norm[i],MOD-2);
    }
}

int Perm(int n,int r){
    if(n<r)return 0;
    int R=1;
    R*=fact_norm[n];R%=MOD;
    R*=fact_inv[n-r];R%=MOD;
    return R;
}


signed main(void){
    int N,K;
    int a[114514],b[114514];
    cin >> N >> K;
    REP(i,N-1){
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
    }
    int child[114514]={};
    int parent[114514]={};
    
    vector<int> G[114514];
    REP(i,N-1){
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    bool visited[114514]={};
    queue<int> Q;
    Q.push(0);
    parent[0]=-1;
    
    while(!Q.empty()){
        int q=Q.front();
        Q.pop();
        if(visited[q])continue;
        visited[q]=true;
        
        REP(i,G[q].size()){
            if(!visited[G[q][i]]){
                Q.push(G[q][i]);
                parent[G[q][i]]=q;
                child[q]++;
            }
        }
    }
    
    REP(i,N){
        visited[i]=false;
    }
    Q.push(0);
    
    int Ans=K;
    fact_inverse(114514);
    /*REP(i,N){cout << fact_norm[i] << " ";}cout << endl;
    REP(i,N){cout << (fact_norm[i]*fact_inv[i])%MOD << " ";}cout << endl;*/
    
    while(!Q.empty()){
        int q=Q.front();
        Q.pop();
        if(visited[q])continue;
        visited[q]=true;
        
        if(parent[q]==-1){
            Ans*=Perm(K-1,child[q]);
            Ans%=MOD;
        }else{
            Ans*=Perm(K-2,child[q]);
            Ans%=MOD;
        }
        //cout << q MM Ans << endl;
        
        REP(i,G[q].size()){
            if(!visited[G[q][i]]){
                Q.push(G[q][i]);
            }
        }
    }
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 13684
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin >> s;
	if (s <= "2019/04/30")
		cout << "Heisei\n";
	else
		cout << "TBD\n";
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		b,c,h,i,j,k,l,m,n,x,y;
	ll		ans = 0;
	string	s;
	cin >> n;
	vector<ll>	a(n+1),t(n+1);
	for(i=0;i<n;i++) cin >> a[i];
	for(i=0;i<n;i++) t[i+1] = t[i] + a[i];
	//for(i=0;i<=n;i++) cout << a[i] << ' ' << t[i] << endl;
	for(i=0;i<n-1;i++) {
		ans += a[i]*((t[n] - t[i+1]) % 1000000007) % 1000000007;
		ans %= 1000000007;
		//cout << ans << endl;
	}

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


Measured memory_bytes: 6428
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}

int w,h;
vs s;
bool ans;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

bool in(int a,int b){
    if(a < 0 || a >= h || b < 0 || b >= w)return false;
    return true;
}

pair<double,double> f(int x, int y){
    double cnt = 0, sum = 0;
    char c = s[x][y];
    vp v;
    queue<pii> q;
    q.push(pii(x,y));
    while(q.size()){
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        rep(i,4){
            int nx = a+dx[i];
            int ny = b+dy[i];
            if(!in(nx,ny))continue;
            if(s[nx][ny] == c){
                s[nx][ny] = '*';
                v.push_back(pii(nx,ny));
                q.push(pii(nx,ny));
            }
        }
    }
    sort(all(v));
    rep(i,v.size())s[v[i].first][v[i].second] = c;

    rep(i,v.size()){
        int a = v[i].first, b = v[i].second;
        if(a && s[a-1][b] != '.' && s[a-1][b] != c){
            pair<double,double> ret = f(a-1,b);
            cnt += ret.first;
            sum += ret.second;
        }
    }

    int l = w, r = 0;
    cnt += v.size();
    rep(i,v.size()){
        int a = v[i].first, b = v[i].second;
        sum += b + 0.5;
        if(v[3].first < h-1 && s[a+1][b] != '.' && s[a+1][b] != c){
            l = min(l, b);
            r = max(r, b);
        }
        if(v[3].first == h-1 && a == h-1){
            l = min(l, b);
            r = max(r, b);
        }
    }
    r++;
    if(cnt*l >= sum || sum >= cnt*r){
        ans = false;
    }
    rep(i,v.size())s[v[i].first][v[i].second] = '.';
    return pair<double,double>(cnt,sum);
}

signed main(void) {
    while(cin >> w >> h, h){
        ans = true;
        s = vs(h);
        rep(i,h)cin >> s[i];
        rep(j,w)if(s[h-1][j] != '.'){
            f(h-1,j);
        }
        if(ans)cout << "STABLE" << endl;
        else cout << "UNSTABLE" << endl;
    }

}



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

int main() {
  int64_t n, k, s = 0;
  cin >> n >> k;
  priority_queue<int64_t> p;
  for(int i = 0; i < n; i++){
    int64_t a;
    cin >> a;
    p.push(a);
  }
  for(int i = 0; i < k; i++){
    p.push(p.top()/2);
    p.pop();
  }
  while(p.size() > 0){
    s += p.top();
    p.pop();
  }
  cout << s << endl;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int PS(int x, int y) {
 int c=1;
  rep(i,y) {
    c *=x;
  }
  return c;
}
int main() {
  int N;
  cin >>N;
  vector<int> vec(N);
  rep(i,N) {
cin >>vec.at(i);
  }
  int x=vec.at(0);
  int count=0;
repl(i,0,N) {
  if(vec.at(i)<=x) {
    count++;
    x=min(x,vec.at(i));
  }
  
}
  
  
  cout<<count<<endl;
}
   
  
 

Measured memory_bytes: 1024
(* O(n) *)
open Array
open Scanf
let n, q = scanf " %d %d" @@ fun a b -> a, b
let s = Scanf.scanf " %s" @@ fun s -> s
let lrs = init q @@ fun _ -> scanf " %d %d" @@ fun a b -> a - 1, b - 1
let sums = make (n + 1) 0
let _ =
  String.iteri (fun i c -> sums.(i + 1) <- sums.(i) + if c = 'A' && i + 1 < n && s.[i + 1] = 'C' then 1 else 0) s;
  iter (fun (l, r) -> Printf.printf "%d\n" @@ sums.(r) - sums.(l)) lrs

Measured memory_bytes: 8448
#include <stdio.h>

int main(){
  int x,y;
  while(scanf("%d%d",&x,&y)){
    if(x==0 && y==0){
      break;
    }else if(x<y){
      printf("%d %d\n",x,y);
    }else{
      printf("%d %d\n",y,x);
    }
  }
  return 0;
}

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

using namespace std;

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

    int ans = 0;
    while(n--) {

        double x,y;
        cin >> x >> y;
        if(d >= sqrt(x * x + y * y)) ans++;
    }
    cout << ans << "\n";
    return 0;
}


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

int main(){
  int n;
  cin>>n;
  int l  = n/100;
  int r =n%100;

  if(1<=l && l<=12){
  	if(1<=r && r<=12) cout<<"AMBIGUOUS";
    else cout<<"MMYY";
  }
  else{
  	if(1<=r && r<=12) cout<<"YYMM";
    else cout<<"NA";
  }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

a = []
b = []
for i in range(n):
    a.append(ab[i][0])
    b.append(ab[i][1])

import numpy as np

a_argsort = np.argsort(a)
counter_m = 0
counter_money = 0
for i in range(n):
    idx = a_argsort[i]
    _b = b[idx]
    _a = a[idx]
    if counter_m + _b >= m:
        buy = m - counter_m
        counter_money += buy * _a
        break
    else:
        counter_m += _b
        counter_money += _a * _b

print(counter_money)


Measured memory_bytes: 39548
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = sorted(li())

if A[-1] < sum(A[:N-1]):
    print('Yes')
else:
    print('No')



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

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
#define SZ(x) ((int)(x).size())

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const i64 mod = (i64)1e9 + 7;
i64 n, a, b;

i64 quickmod(i64 a, i64 b, i64 c) {
    i64 ans = 1;
    while(b) {
        if(b & 1) {
            ans = (ans * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    return ans;
}
i64 cc(i64 x, i64 y) {
	i64 tmp = 1;
	for (i64 i = x; i >= x - y + 1; --i) tmp = tmp * i % mod;
	for (i64 i = 1; i <= y; ++i) tmp = tmp * quickmod(i, mod - 2, mod) % mod;
	return tmp;
}


int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFIN
    freopen("input.txt", "r", stdin);
#endif

    cin >> n >> a >> b;
    i64 ans = quickmod(2, n, mod) - 1 - cc(n, a) - cc(n, b);
    ans = (ans % mod + mod) % mod;
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<ll, ll>
#define PP pair<P,P>
using namespace std;

int main(){
    char a; cin >> a;
    char ans;
    if(a=='A') ans='T';
    if(a=='T') ans='A';
    if(a=='G') ans='C';
    if(a=='C') ans='G';
    cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())
r = []

for i in range(0,a+1):
  for j in range(0,b+1):
    for k in range(0,c+1):
      r.append(500*i + 100*j + 50*k)

print(r.count(x))

Measured memory_bytes: 48368
from bisect import bisect_left
N,A,B=map(int,input().split())
inf,mod=float("inf"),10**9+7
S=[int(input()) for i in range(N)]
St_A=[0]*N
St_B=[0]*N
J_A,J_B=[0],[0]
for i in range(N):
  St_A[i]=bisect_left(S,S[i]+A)-1
  St_B[i]=bisect_left(S,S[i]+B)-1
  J_A.append(J_A[-1]+int(St_A[i]!=i))
  J_B.append(J_B[-1]+int(St_B[i]!=i))
  
#print(St_A,St_B)
#print(J_A,J_B)

dp_A=[0]*N
dp_B=[0]*N
dp_A[-1],dp_B[-1]=1,1
for i in range(N-1)[::-1]:
  if St_A[i]==i:
    dp_A[i]=(dp_A[i+1]+dp_B[i+1])%mod
  else:
    if J_B[St_A[i]]-J_B[i+1]==0:
      dp_A[i]=dp_B[St_A[i]]
    else:
      dp_A[i]=0
  if St_B[i]==i:
    dp_B[i]=(dp_A[i+1]+dp_B[i+1])%mod
  else:
    if J_A[St_B[i]]-J_A[i+1]==0:
      dp_B[i]=dp_A[St_B[i]]
    else:
      dp_B[i]=0
#print(dp_A)
#print(dp_B)
print((dp_A[0]+dp_B[0])%mod)

Measured memory_bytes: 72152
/*@author hussein zayed ;
    ___  ___
   |\  \|\  \
   \ \  \_\  \
    \ \   ___ \USSEIN
     \ \  \\ \ \
      \ \__\\ \_\
       \|__| \|__|
****************************************
*/

#include <bits/stdc++.h>
using namespace std;
#define fr for(int i=0;i<n;++i)
#define fr1 for(int i=1;i<=n;++i)
#define cinA for(int i=0;i<n;++i){cin>>arr[i];}
#define cinA1 for(int i=1;i<=n;++i){cin>>arr[i];}
#define coutA for(int i=0;i<n;++i){cout<<arr[i]<<" ";}
#define ll long long
#define lnarray sizeof(arr)/sizeof(*arr)
#define vi vector<int>
#define vs vector<string>
void Fast()
{
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}
inline int RD()
{
    int i ;
    cin>>i;
    return i;
}

inline float RF()
{
    float i ;
    cin>>i;
    return i;
}

inline double RDO()
{
    double i ;
    cin>>i;
    return i;
}

inline string RS()
{
    string i ;
    cin>>i;
    return i;
}

inline ll RLL()
{
    ll i ;
    cin>>i;
    return i;
}

int cm[200000];

ll sumSet(ll n)
{
    return (1ll*n*(n+1))/2;
}
string s;


bool isPrime(int n)
{
    if(n==1)
        return false;
    for(int i=2; i*i<=n; ++i)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int sumDigit(int n){
int sum =0;
  while (n != 0)
    {
        sum+= + n % 10;
        n = n / 10;
    }
    return sum;
}

ll power2(int n){
  ll ans=(1<<n);
  return ans;
}

ll sumpow2(ll n){
 ll sum=(n*(n+1)*(2*n-1))/6;
 return sum;
}
char arr[101][101];
int main(){
    Fast();
//freopen("output.txt" , "w" , stdout);
//freopen("wall.in" , "r" , stdin);

  ll n=RLL(),m=RLL();
  ll ans;
  if (n- m/ 2 >= 0) {
    ans = m / 2;
  } else {
    ans = n + (m- 2 * n) / 4;
  }
  cout << ans;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
  char a[4],b[4];
  scanf("%s %s",&a,&b);
  if((a[0]==b[2])&&(a[1]==b[1])&&(a[2]==b[0]))
    printf("YES");
  else
    printf("NO");
  
  return 0;
}


Measured memory_bytes: 2072
N,M = map(int,input().split())

for i in range(M):
  a,b = map(int,input().split())
  if(i == 0): a_Max,b_Min = a,b
  else: 
    a_Max = max(a_Max,a)
    b_Min = min(b_Min,b)
    
ans = b_Min - a_Max + 1 
if(ans <= 0): ans = 0 
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <limits.h>
#include <math.h>
#include <utility>
#include <algorithm>
using namespace std;
 
#define mod 1000000007
#define ll long long
#define tc int t; cin >> t; for(int tt = 1; tt <= t; tt++)
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ERR
#ifdef ERR
#define deb(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define deb(...)
#endif

// Dirty Fix
// #define int long long


ll power(ll a,ll b){
    ll res = 1;
    while(b > 0){
        if(b & 1){
            res = ((res % mod) * (a % mod)) % mod;
        }
        b = b >> 1;
        a = ((a % mod) * (a % mod)) % mod; 
    }
    return res;
}

signed main(void)
{
    ios;
    #ifndef ONLINE_JUDGE
      //  freopen("../in.txt","r",stdin);
    #endif
    int n,w;
    cin >> n >> w;
    vector<pair<long long,long long>> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].first >> a[i].second;
    }
    vector<ll> dp(w + 1);
    for(int i = 0; i < n; i++){
        for(int j = w; j >= 0; j--){
            if(j >= a[i].first)
                dp[j] = max(dp[j],a[i].second + dp[j - a[i].first]);
        }
    }
    cout << dp[w] << endl;
    return 0;
}

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

int main()
{
	long long n, k;
	cin >> n >> k;

	long long ret;
	if (n <= k) {
		ret = k - n;
		ret = min(ret, k - ret);
	}
	else {
		ret = n % k;
		ret = min(ret, k - ret);
	}
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
	/*入力*/
	int N,Max=0;
	cin >> N;
	int A[2][N];
	for(int i=0;i<N;i++)cin >> A[0][i];
	for(int i=0;i<N;i++)cin >> A[1][i];
	
	/*最大値全探索*/
	for(int i=0;i<N;i++){
		int Sum=0;
		for(int j=0;j<=i;j++)Sum+=A[0][j];
		for(int k=i;k<N;k++)Sum+=A[1][k];
		if(Sum>Max)Max=Sum;
	}
	cout << Max << endl;
	return 0;
}

Measured memory_bytes: 256
/**
 *    author:  otera    
**/
#include<iostream>
#include<string> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm> 
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n;
vector<vector<int>> g;

int dfs(int v, int p) {
    int res = 0;
    for(int nv: g[v]) {
        if(nv == p) continue;
        res ^= (dfs(nv, v) + 1);
    }
    return res;
}

void solve() {
	cin >> n;
    g.assign(n, vector<int>());
    rep(i, n - 1) {
        int u, v; cin >> u >> v;
        -- u, -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int tot = dfs(0, -1);
    if(tot == 0) {
        cout << "Bob" << endl;
    } else {
        cout << "Alice" << endl;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 13480
#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

def max_index(lst):
	index = -1
	value = -float("inf")
	for i, vi in enumerate(lst):
		if value < vi:
			value = vi
			index = i
	return index


def main():
	log = Logger(0)
	day_length = int(sys.stdin.readline())
	down_happy = list(map(int, sys.stdin.readline().split()))
	daily_happy = [[] for i in range(day_length)]
	contests_kind = 26
	for i in range(day_length):
		si = list(map(int, sys.stdin.readline().split()))
		for j in range(contests_kind):
			daily_happy[i].append(si[j])
	happy = 0
	last_contest_days = [0]*contests_kind
	for day in range(day_length):
		best_contest = 0
		max_add_happy = -float("inf")
		for contest in range(contests_kind):
			add_happy = 0
			add_happy += daily_happy[day][contest]
			last_contest_days[contest] = day + 1
			for i in range(contests_kind):
				add_happy -= down_happy[i] * (day + 1 - last_contest_days[i])
			if max_add_happy < add_happy:
				max_add_happy = add_happy
				best_contest = contest
		print(best_contest + 1)
		happy += max_add_happy
	log.print(happy)





main()

Measured memory_bytes: 71440
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
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;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    vector<ll>A(N);
    rep(i,N)cin>>A[i];
    ll ans=0;
    ll flag=0;
    while(1){
        rep(i,N){
            if(A[i]%2==0){
                A[i]/=2;
                
            }else{
                flag=1;
                break;
            }
        }
        if(flag==1) break;
        ans++;
        
    }
    cout << ans << endl;


    return 0;
    

}

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

int main(){
    int n;
    scanf("%d",&n);
    vector<int> vec(n);
    for(int i=0;i<n;i++){
        scanf("%d",&vec[i]);
    }
    int mini=vec[0],s=vec[1]-vec[0];
    for(int i=1;i<n;i++){
        mini=min(mini,vec[i-1]);
        s=max(s,vec[i]-mini);
    }
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 3568
// https://atcoder.jp/contests/abc090/tasks/abc090_b
#include <bits/stdc++.h>
using namespace std;

#define rep(i, m, n) for (int i = m; i < (int)(n); i++)

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

  int sum = 0;
  rep(i, A, B + 1) {
    string s = to_string(i);
    if ((s[0] == s[4]) && (s[1] == s[3])) sum++;
  }

  cout << sum;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define mp1(a,b,c) P1(a,P(b,c))
#define pque(a) priority_queue<a>
#define rpque(a) priority_queue<a,vector<a>,greater<a>>

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
const int kaijou[10]={1,1,2,6,24,120,720,5040,40320,362880};

int main(){
	while(1){
		int a,b,c;
		int n;
		int x[1002],y[1002],z[1002],w[1002];
		
		scanf("%d%d%d",&a,&b,&c); if(a == 0 && b == 0 && c == 0)break;
		scanf("%d",&n);
		rep(i,n){
			scanf("%d%d%d%d",&x[i],&y[i],&z[i],&w[i]);
		}
		
		int ret[310];
		rep(i,310){
			ret[i] = 2;
		}
		
		rep(i,n){
			if(w[i] == 1){
				ret[x[i]] = 1;
				ret[y[i]] = 1;
				ret[z[i]] = 1;
			}
		}
		
		bool updata = true;
		while(updata){
			updata = false;
			rep(i,n){
				if(w[i] == 0){
					if(ret[x[i]] == 1 && ret[y[i]] == 1 && ret[z[i]] != 0){
						ret[z[i]] = 0;
						updata = true;
					}
					if(ret[y[i]] == 1 && ret[z[i]] == 1 && ret[x[i]] != 0){
						ret[x[i]] = 0;
						updata = true;
					}
					if(ret[z[i]] == 1 && ret[x[i]] == 1 && ret[y[i]] != 0){
						ret[y[i]] = 0;
						updata = true;
					}
				}
			}
		}
		
		rep1(i,a+b+c){
			printf("%d\n",ret[i]);
		}
	}
}
	
	

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

namespace ConsoleApp2
{
	class Program
	{
		static void Main(string[] args)
		{
			var data = Console.ReadLine();
			var table = new int['z'+1];
			for (int i = 0; i < table.Length; i++)
			{
				table[i] = 0;
			}
			for (int i = 0; i < data.Length; i++)
			{
				if (table[data[i]] == 0) table[data[i]] = 1;
				else
				{
					Console.WriteLine("no");
					return;
				}
			}
			Console.WriteLine("yes");
		}
	}
}

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


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


a, b = 1, 1
for i in range(n):
    a = b
    b = lcm(a, int(input()))
print(b)


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<ll> a;
    for (int i = 0; i < n; i++) {
        ll tmpa;
        cin >> tmpa;
        a.push_back(tmpa);
    }

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

    for (int i = 0; i < n - 1; i++) {
        if (a[i] - a[i + 1] == 0) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

}


Measured memory_bytes: 2420
import math
ans = math.inf
n = int(input())
c = list(map(int, input().split()))
acm = [0]*(n+1)
for i, v in enumerate(c, 1):
    acm[i] += acm[i-1] + v

s, a = 0, acm[n]
for i in range(1, n):
    s = acm[i]
    ans = min(ans, abs((a-s)-s))

print(ans)

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

int main(){
	string s;
  cin>>s;
  for(int i=0;i<s.size()-1;i++){
  	if(s[i]==s[i+1]){
    	cout<<i+1<<" "<<i+2;
      return 0;
    }
  }
  for(int i=0;i<s.size()-2;i++){
  	if(s[i]==s[i+2]){
    	cout<<i+1<<" "<<i+3;
      return 0;
    }
  }
  cout<<"-1 -1";
}

Measured memory_bytes: 512
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
h = LI()+[0]
ans = 0
while 1:
    if max(h)==0:
        break
    ans += 1
    for i in range(N+1):
        if h[i]>0 and h[i+1]==0:
            h[i] -= 1
            break
        h[i] = max(h[i]-1,0)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <stdio.h>
 
using namespace std;
 
#define int long long
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(i, a) for (auto &i: (a))
#define sz(x) (int)(x).size()
#define all(v) (v).begin(), (v).end()
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
int dp[100005][4];
// int maxsummerpoints(int days, int a[],int b[],int c[]){
//     if(days ==0||user==0){
//         return 0;
//     }
//     if( dp[days][user]!=0){
//         return dp[days][user];
//     }
//     int op1 = a[days-1]+maxsummerpoints(days-1,a,b,c);
//     int op2 = b[days-1]+maxsummerpoints(days-1,a,b,c);
//     int op3 = c[days-1]+maxsummerpoints(days-1,a,b,c);
//     int best= max(op1,max(op2,op3));
//     return dp[days]=best;
    
// }
void solve();
signed main () {
    clock_t beg = clock();
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif 
    int t=1; 
    // cin >> t;    
    int tt = t;
    while (t--) {

        int n;
        cin>>n;
        int a[n],b[n],c[n];

        rep(i,0,n){
            cin>>a[i]>>b[i]>>c[i];
        }
        memset(dp,0,sizeof(dp));
        // for( int i=1;i<=n;i++){
        //     cout<<dp[i]<<" ";
        // }
        // cout<<endl;
        dp[1][1]=a[0];
        dp[1][2]=b[0];
        dp[1][3]=c[0];
        for(int i=2;i<=n;i++){
            dp[i][1]= a[i-1]+max(dp[i-1][2],dp[i-1][3]);
            dp[i][2]= b[i-1]+max(dp[i-1][1],dp[i-1][3]);
            dp[i][3]= c[i-1]+max(dp[i-1][1],dp[i-1][2]);
        }
        int ans=INT_MIN;
        for(int i=1;i<=3;i++){
            ans = max( ans,dp[n][i]);
        }
        cout<<ans<<endl;
        // cout<<maxsummerpoints(n,a,b,c)<<endl;

    }
    // cerr << "\nExecution time: " << (clock() - beg) / 1000 << '\n';
    return 0;
}


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

using namespace std;

int main() {

	string s;
	cin >> s;

	if (s[0] == 'A') {
		int counter = 0;
		for (int i = 2; i < s.size() - 1;i++) {
			if (s[i] == 'C') { counter++; }
		}
		if (counter == 1) {
			if((s[1]>='a' && s[1]<='z')
				&& (s[s.size()-1] >= 'a' && s[s.size()-1] <= 'z')) {
				cout << "AC" << endl;
				return 0;
			}
		}
	}
	cout << "WA" << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
po = []
ne = []
for i in range(N):
    if A[i] < 0:
        ne.append(A[i])

A = list(map(abs,A))
A.sort()
if len(ne) != 0:
    if len(ne) % 2 == 0:
        print(sum(A))
    else:
        print(sum(A)-2*A[0])
else:
    print(sum(A))

Measured memory_bytes: 14412
/**
 *    author:  tourist
 *    created: 11.11.2017 15:40:33       
**/
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class flow_graph {
  public:
  static constexpr T eps = (T) 1e-9;

  struct edge {
    int from;
    int to;
    T c;
    T f;
  };

  vector< vector<int> > g;
  vector<edge> edges;
  vector<int> ptr;
  vector<int> d;
  vector<int> q;
  int n;
  int st, fin;
  T flow;
   
  flow_graph(int n, int st, int fin) : n(n), st(st), fin(fin) {
    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    ptr.resize(n);
    d.resize(n);
    q.resize(n);
    flow = 0;
  }

  void clear_flow() {
    for (const edge &e : edges) {
      e.f = 0;
    }
    flow = 0;
  }
   
  void add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    g[from].push_back(edges.size());
    edges.push_back({from, to, forward_cap, 0});
    g[to].push_back(edges.size());
    edges.push_back({to, from, backward_cap, 0});
  }

  bool expath() {
    fill(d.begin(), d.end(), -1);
    q[0] = fin;
    d[fin] = 0;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (int id : g[i]) {
        const edge &e = edges[id];
        const edge &back = edges[id ^ 1];
        if (back.c - back.f > eps && d[e.to] == -1) {
          d[e.to] = d[i] + 1;
          if (e.to == st) {
            return true;
          }
          q[end++] = e.to;
        }
      }
    }
    return false;
  }
   
  T dfs(int v, T w) {
    if (v == fin) {
      return w;
    }
    int &j = ptr[v];
    while (j >= 0) {
      int id = g[v][j];
      const edge &e = edges[id];
      if (e.c - e.f > eps && d[e.to] == d[v] - 1) {
        T t = dfs(e.to, min(e.c - e.f, w));
        if (t > eps) {
          edges[id].f += t;
          edges[id ^ 1].f -= t;
          return t;
        }
      }
      j--;
    }
    return 0;
  }

  T max_flow() {
    while (expath()) {
      for (int i = 0; i < n; i++) {
        ptr[i] = (int) g[i].size() - 1;
      }
      T big_add = 0;
      while (true) {
        T add = dfs(st, numeric_limits<T>::max());
        if (add <= eps) {
          break;
        }
        big_add += add;
      }
      if (big_add <= eps) {
        break;
      }
      flow += big_add;
    }
    return flow;
  }

  vector<bool> min_cut() {
    max_flow();
    vector<bool> ret(n);
    for (int i = 0; i < n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};

int main() {
  int n;
  scanf("%d", &n);
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  const int inf = (int) 1e9;
  flow_graph<long long> g(n + 2, 0, n + 1);
  for (int i = 1; i <= n; i++) {
    g.add(0, i, -a[i] + inf, 0);
    g.add(i, n + 1, inf, 0);
  }
  const long long infll = (long long) 1e18;
  for (int i = 1; i <= n; i++) {
    for (int j = i + i; j <= n; j += i) {
      g.add(i, j, infll, 0);
    }
  }
  long long ans = g.max_flow();
  ans -= (long long) inf * n;
  cout << -ans << endl;
  return 0;
}


Measured memory_bytes: 384
/*  -*- coding: utf-8 -*-
 *
 * 2982.cc: Expensive Function
 */

#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() {
  int s, t, p, q, m, y;
  scanf("%d%d%d%d%d%d", &s, &t, &p, &q, &m, &y); 

  printf("%d\n", t ^ s ^ y);
  return 0;
}



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

int main(){
  vector<int> a(3);
  rep(i,3) cin >>a[i];
  sort(a.begin(), a.end());
  vector<int> b(3);
  b={5, 5, 7};
  if(a == b) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}



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

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

    priority_queue<ll, std::vector<int> > que;
    ll a;
    for(int i = 0; i < n; i++){
        cin >> a;
        que.push(a);
    }

    for(int j = 0; j < m; j++){
        ll b = que.top();
        que.pop();
        b /= 2;
        que.push(b);
    }

    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += que.top();
        que.pop();
    }

    cout << ans << endl;
}

Measured memory_bytes: 892
mod = 10**9 + 7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)

b = pow(2, 2*n-2, mod)
a = 2 * b % mod

ans = 0
for i in range(n):
    ans += c[i] * (a + i * b)
    ans %= mod

print(ans)

Measured memory_bytes: 87500
# frozen_string_literal: true

# Generated by AtcoderGreedy on 2018-05-05
# ABC096 C
# Your code here
$h, $w = gets.chomp.split(' ').map(&:to_i)

$c = []
$h.times do
  $c << gets.chomp.split('')
end

$h.times do |i|
  $w.times do |j|
    next if $c[i][j] == '.'
    $stuck = [[i, j]]
    count = 0

    until $stuck.empty?
      y, x = $stuck.pop

      next if $c[y][x] == '.'

      count += 1

      $c[y][x] = '.'

      $stuck << [y - 1, x] if y - 1 >= 0
      $stuck << [y + 1, x] if y + 1 < $h
      $stuck << [y, x + 1] if x + 1 < $w
      $stuck << [y, x - 1] if x - 1 >= 0
    end

    if count == 1
      puts 'No'
      exit(0)
    end
  end
end

puts 'Yes'


Measured memory_bytes: 2172
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MXN 100010

int n,
	a[MXN];

/*
[Discretization] by.YXH_XianYu
void Discretization(int a[], int n);
	a[] : Array that will be Modified
	n   : the Length of Array a
This function can discretize a[]. 
(It can't Remove duplicate elements)
 */
struct Sort{
		int va,no;
	}s[MXN];
bool sortComp(Sort a, Sort b){
	return a.va<b.va;
}
void Discretization(int a[], int n){
	
	for(int i=1;i<=n;i++)
		s[i].va=a[i],
		s[i].no=i;
	std::sort(s+1,s+n+1,sortComp);
	for(int i=1;i<=n;i++)
		a[s[i].no]=i;
	return;
}



int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	Discretization(a,n);
	int ans=0;
	for(int i=1;i<=n;i++)
		if( (a[i]-i)&1 )
			ans++;
	printf("%d\n",ans/2);
	//system("pause");
	return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	int a, b;
	cin >> a >> b;
	if (a%2 != 0 && b%2 != 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}



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

using namespace std;
#define ll  long long
#define ld  long double

#define endl '\n'
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int MAXN = 1e5 + 5;
string h;
int a, b, k;

ll fastPow(ll x, ll b) {
    if (b == 0)
        return 1;
    else if (!(b & 1)) {
        return fastPow(x * x, b / 2);
    } else
        return x * fastPow(x * x, (b - 1) / 2);
}

//__builtin_popcount ();
ll arr[MAXN],ok1[MAXN],pre[MAXN],pre1[MAXN];

int main() {
    FAST
ll n,a,b;
    cin>>n>>a>>b;
    ll ans=a+b;
    cout<<(n/ans)*a+min(n%ans,a)<<endl;
    return 0;
}

Measured memory_bytes: 256
def main():

    score_list = []
    while True:
        m, f, r = map(int, input().split())
        if [m, f, r] == [-1, -1, -1]: break
        score_list.append([m, f, r])
    
    for item in score_list:
        [m, f, r] = item
        total = m + f
        if [m, f, r] == [-1, -1, -1]: break
        elif m == -1 or f == -1:
            result = 'F'
        elif total < 30:
            result = 'F'
        elif total < 50:
            if r >= 50:
                result = 'C'
            else:
                result = 'D'
        elif total < 65:
            result = 'C'
        elif total < 80:
            result = 'B'
        else:
            result = 'A'
        print(result)

main()

Measured memory_bytes: 7724
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<queue>
#include <climits>
const int mod = 1e9 + 7;
const int INF = 1e9;
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int N;
long long h[100010];

long long dp[100010];

int main() {
    int N; cin >> N;
    for (int i = 0; i < N; ++i) cin >> h[i];

    for (int i = 0; i < 100010; ++i) dp[i] = INF;

    dp[0] = 0;

    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    cout << dp[N-1] ;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int F[100][10];
int P[100][11];

int main() {
	int N;
	cin >> N;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 10; j++) {
			cin >> F[i][j];
		}
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 11; j++) {
			cin >> P[i][j];
		}
	}

	ll ans = -1e9;
	for(int bit = 1; bit < 1 << 10; bit++) {
		int c[100] = { 0 };
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 10; j++) {
				if(bit >> j & 1 && F[i][j]) c[i]++;
			}
		}
		ll sum = 0;
		for(int i = 0; i < N; i++) {
			sum += P[i][c[i]];
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))
answer = [[0] * W] * H
# True_answer = []
input_list = []
for i in range(1, N+1):
    for _ in range(a[i-1]):
        input_list.append(i)

for i in range(H):
    for j in range(W):
        if i % 2 == 0:
            # print('2')
            answer[i][j] = input_list[W * i + j]
            # print(answer[0], answer[1], answer[2])
        else:
            # print('not2')
            answer[i][W-j-1] = input_list[W * i + j]
            # print(answer)
        if (j+1) % W == 0:
            # True_answer[i] += answer[i]
            print(*answer[i])



# print(input_list)
# print(answer)
# print(True_answer)


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

const int maxn=5005;
const int mod=1e9+7;
int n,m;
int f[maxn],sf[maxn],pw2[maxn],ipw2[maxn];

int main(){
	scanf("%d%d",&n,&m);
	pw2[0]=ipw2[0]=1;
	for(int i=1;i<=m;i++){
		pw2[i]=2LL*pw2[i-1]%mod;
		ipw2[i]=1LL*ipw2[i-1]*(mod+1)/2%mod;
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(!i)f[j]=1;
			else f[j]=(1LL*f[j]*(j+1)+(j>=2?1LL*sf[j-2]*pw2[j-2]:0))%mod;
		}
		for(int j=0;j<=m;j++)
			sf[j]=((!j?0:sf[j-1])+1LL*f[j+1]*ipw2[j]%mod*(j+1))%mod;
	}
	printf("%d\n",f[m]);
	return 0; 
} 

Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,m,i,j,k,o,p;
    scanf("%lld %lld",&n,&m);
    k=n-(m*2);
    if(k<0){k=0;}
    printf("%lld\n",k);




    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main() {
    unsigned long long A,B,K;

    std::cin >> A >> B >> K;

    while(1){
        if(A<K){
            K -= A;
            A = 0;
        }
        else{//A => K
            A -= K;
            K = 0;
            break;
        }

        if(B<K){
            K -= B;
            B = 0;
        }
        else{//B => K
            B -= K;
            K = 0;
            break;
        }
        break;
    }
    
    std::cout << A << " " << B << std::endl;

    return 0;
}

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

using namespace std;

int main(int argc, const char * argv[]) {
    char b;
    cin >> b;
    if(b=='A')cout << 'T' << endl;
    else if(b=='C')cout << 'G' << endl;
    else if(b=='G')cout << 'C' << endl;
    else cout << 'A' << endl;
    return 0;
}


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

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);
		int n=in.nextInt(),taro=0,hanako=0;
		
		for(int i=0;i<n;i++) {
			String str1=in.next(),str2=in.next();
			if(str1.compareTo(str2)>0)taro+=3;
			else if(str1.compareTo(str2)<0)hanako+=3;
			else {
				taro++; hanako++;
			}
		}
		out.println(taro+" "+hanako);
		out.flush();
	}

}



Measured memory_bytes: 29388
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>

using namespace std;

void solve();

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

void solve() {
    string s;
    cin >> s;
    cout << "2018" << s.substr(4,s.length()) << endl;

}

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

int N, W;
vector<int> val(101, 0);
vector<int> wei(101, 0);
vector<int> dp(10001, 0);

int main(void){
    
    cin >> N >> W;
    for(int i = 0; i < N; ++i) cin >> val[i] >> wei[i];
    for(int i = 0; i < N; ++i) for(int w = W; w >= wei[i]; --w) dp[w] = max(dp[w], dp[w - wei[i]] + val[i]);
    cout << dp[W] << endl;
    
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int N; cin >> N;
  vector<int> T(N); rep(i,N) cin >> T[i];
  int M; cin >> M;
  vector<pair<int, int>> PX(M);
  int p, x;
  rep(i,M){
    cin >> p >> x;
    p--;
    PX[i] = {p,x};
  }
  rep(i,M){
    int time = 0;
    rep(j,N){
      if(j == PX[i].first) time += PX[i].second;
      else time += T[j];
    }
    cout << time << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    a = list(map(int, input().split()))

    bl = 1
    for i in range(N):
        if a[i] == bl:
            bl += 1

    if bl == 1:
        print('-1')
    else:
        print(N - bl + 1)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 72220
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define EB(X) emplace_back(X)
#define REP(i,a) for(int i=0;i<(a);++i)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
#define VI vector<int>;
#define PI 3.14159265358979323846

using namespace std;
int MOD = 1000000007;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  char c = s[0];
  char ret;
  if( c >= 'A' && c <= 'Z' ) ret = 'A';
  else ret = 'a';
  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 3608
#include <bits/stdc++.h>
#include<math.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 10000000000000000

int main (){
    int n ;
    cin >> n ;
    string s ;
    cin >> s ;
    int numr = 0 ;
    int numw = 0 ;
    int ans = 200001; 
    rep(i, n){
        if(s[i] == 'R'){
            numr++ ;
        }
    }
    ans = min(ans, max(numr,numw)) ;
    rep(i, n){

        if(s[i] == 'W'){
            numw++ ;
        }
        else{
            numr-- ;
        }
        ans = min(ans, max(numr,numw)) ;
    }
    cout << ans << endl ;
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MOD 1000000007

string str,str1,str2;
int ans;
int a,b;
int n;
int A[105];
int main(){
  cin >> n;
  for(int i = 0; i < n-1; i++){
    cin >> a;
    A[i] = a;
  }
  for(int i = 0; i < n-1; i++){
    a = A[i];
    if(i==0){
      ans += a;
      continue;
    }
    b = A[i-1];
    ans += min(a,b);
  }
  ans += A[n-2];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <string.h>
#include<stdio.h>
int main()
{
    int a,b;
    char s[100];
  
  // 文字列の入力
    scanf("%s",s);
    int i=0;
  while(s[i] != '\0'){
    s[i] = 'x';
	i++;
  }
    
    // 出力
    printf("%s",s);//printf("%c",s[0])//文字一つ分のみを出力

    return 0;
}

Measured memory_bytes: 128