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

template<class T> struct LowestCommonAncestor {
    using Graph = vector<vector<pair<int, T>>>;
    const T t_inf = numeric_limits<T>::max();
    pair<T, int> id = make_pair(t_inf, INT_MAX);
    int n;
    vector<pair<T, int>> data;
    vector<int> idx;
    
    LowestCommonAncestor(Graph G, int s = 0) : idx(G.size(), -1), n(1) {
        vector<pair<T, int>> p;
        EulerTour(G, s, s, 0, p);
        int sz = p.size();
        for (int i = sz-1; i >= 0; i--) idx[p[i].second] = i;
        while (n < sz) { n *= 2; }
        data.resize(2*n-1, id);
        for (int i = 0; i < sz; i++) data[i+n-1] = p[i];
        for (int i = n-2; i >= 0; i--) data[i] = min(data[i*2+1], data[i*2+2]);
    }
    void EulerTour(const Graph &G, int now, int par, T dep, vector<pair<T, int>> &path) {
        path.emplace_back(dep, now);
        for (auto nxt : G[now]) if (nxt.first != par) {
            EulerTour(G, nxt.first, now, dep+nxt.second, path);
            path.emplace_back(dep, now);
        }
    }
    
    pair<T, int> query (int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return id;
        if (a <= l && r <= b) return data[k];
        pair<T, int> vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        pair<T, int> vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
    
    int ancestor (int a, int b) {
        int l = min(idx[a], idx[b]), r = max(idx[a], idx[b]);
        return query(l, r).second;
    }
    
    T distance(int a, int b) {
        int l = min(idx[a], idx[b]), r = max(idx[a], idx[b]);
        T an = query(l, r + 1).first;
        T d1 = data[idx[a]+n-1].first, d2 = data[idx[b]+n-1].first;
        return (d1 + d2 - an*2);
    }
};

int main() {
    int n, q, k;
    cin >> n;
    vector<vector<pair<int, long long>>> g(n);
    for (int i = 0; i < n-1; i++) {
        int a, b; long long c;
        cin >> a >> b >> c; a--; b--;
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    cin >> q >> k;
    LowestCommonAncestor<long long> lca(g, --k);
    
    while (q--) {
        int a, b; cin >> a >> b; a--; b--;
        long long ans = lca.distance(a, k) + lca.distance(k, b);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 29936
<?php
$inputs = explode(" ", file_get_contents("php://stdin"));
$inputs = array_map(intval, $inputs);
list($a, $b) = $inputs;

if ($a === $b) {
  echo "Draw";
} else if (($a !== 1 && $a < $b) || $b == 1) {
  echo "Bob";
} else {
  echo "Alice";
}

Measured memory_bytes: 3576
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
  
N = int(input())

arr = factorization(N)
cdic = {}
for ar in arr:
  cdic[ar[0]] = 1
  sum = 1
  while sum+cdic[ar[0]]+1 <= ar[1]:
    #print(cdic[ar[0]], sum)
    sum += cdic[ar[0]]+1
    cdic[ar[0]] += 1
ans = 0
for c in cdic.values():
  ans += c

if N == 1:
  print(0)
else:
  print(ans)

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

using ll = long long;

constexpr int M = 1e9 + 7;

int solve(string A, string C) {
    int const n = A.size();
    int const m = C.size();
    reverse(A.begin(), A.end());
    reverse(C.begin(), C.end());
    vector<vector<int>> match(m + 1, vector<int>(10));
    for(int d = 0; d <= 9; ++d) {
        char ch = '0' + d;
        for(int i = 0; i <= m; ++i) {
            int len = 0;
            for(int j = min(i + 1, m); j >= 1; --j) {
                if(C.substr(0, j) == C.substr(i - j + 1, j - 1) + ch) {
                    len = j;
                    break;
                }
            }
            match[i][d] = len;
        }
    }
    vector<vector<int>> dp(m + 1, vector<int>(2));
    vector<vector<int>> dp0(m + 1, vector<int>(2)); // leading zero
    vector<vector<vector<int>>> dp2(n + 1, vector<vector<int>>(2, vector<int>(2)));
    dp[0][0] = 1;
    int res = 0;
    for(int i = 0; i < n; ++i) {
        vector<vector<int>> nxt(m + 1, vector<int>(2)), nxt0(m + 1, vector<int>(2));
        for(int k = 0; k < 2; ++k) {
            for(int d = 0; d <= 9; ++d) {
                char ch = '0' + d;
                bool nk = k && ch == A[i] || ch > A[i];
                if(d == 0) {
                    (dp2[i + 1][nk][1] += dp2[i][k][0]) %= M;
                    (dp2[i + 1][nk][1] += dp2[i][k][1]) %= M;
                } else {
                    (dp2[i + 1][nk][0] += dp2[i][k][0]) %= M;
                    (dp2[i + 1][nk][0] += dp2[i][k][1]) %= M;
                }
            }
        }
        for(int j = 0; j <= m; ++j) {
            for(int k = 0; k < 2; ++k) {
                for(int d = 0; d <= 9; ++d) {
                    char ch = '0' + d;
                    bool nk = k && ch == A[i] || ch > A[i];
                    int nj = match[j][d];
                    if(d == 0) {
                        (nxt0[nj][nk] += dp[j][k]) %= M;
                        (nxt0[nj][nk] += dp0[j][k]) %= M;
                    } else {
                        (nxt[nj][nk] += dp[j][k]) %= M;
                        (nxt[nj][nk] += dp0[j][k]) %= M;
                    }
                }
            }
        }
        (dp2[i + 1][0][0] += nxt[m][0]) %= M;
        (dp2[i + 1][0][1] += nxt0[m][0]) %= M;
        (dp2[i + 1][1][0] += nxt[m][1]) %= M;
        (dp2[i + 1][1][1] += nxt0[m][1]) %= M;
        dp = move(nxt);
        dp0 = move(nxt0);
    }

    for(int i = 1; i <= n; ++i) {
        (res += dp2[i][0][0]) %= M;
        if(i != n) {
            (res += dp2[i][1][0]) %= M;
        }
    }
    if(C == "0") {
        (res += 1) % M;
    }
    return res;
}

string decrement(string A) {
    for(int i = A.size() - 1; i >= 0; --i) {
        if(A[i] > '0') {
            A[i]--;
            break;
        } else {
            A[i] = '9';
        }
    }
    if(A[0] == '0' && A.size() > 1) {
        return A.substr(1);
    } else {
        return A;
    }
}

int main() {
    string A, B, C;
    cin >> A >> B >> C;
    if(A != "0") {
        cout << (solve(B, C) - solve(decrement(A), C) + M) % M << endl;
    } else {
        cout << solve(B, C) << endl;
    }
}


Measured memory_bytes: 4632
from collections import defaultdict
import math

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    while b > 0:
        a, b = b, a % b
    return a

def sieve_of_eratosthenes(n):
    sieve = list(range(n+1))
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] < i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve

def factorize_by_sieve(x, sieve):
    factor = defaultdict(int)
    while sieve[x] != x:
        factor[sieve[x]] += 1
        x //= sieve[x]
    factor[x] += 1
    return factor

n = int(input())
a_list = list(map(int, input().split()))

sieve = sieve_of_eratosthenes(max(a_list))
pairwise = True
setwise = True
primes = set()
x = a_list[0]
for a in a_list:
    x = gcd(x, a)
    if pairwise and a != 1:
        factor = set(factorize_by_sieve(a, sieve).keys())
        pairwise = primes.isdisjoint(factor)
        primes |= factor

if pairwise:
    print("pairwise coprime")
elif x == 1:
    print("setwise coprime")
else:
    print("not coprime")

Measured memory_bytes: 201592
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int R,C;
pl val[MX][2], ori = {0,0};
vpi adj[MX][2];
ll mn = 0, mx = INF;

void dfs(int x, int y, pl z) {
    if (val[x][y] != ori) {
        if (val[x][y] != z) {
            cout << "No";
            exit(0);
        }
        return;
    }
    val[x][y] = z;
    if (z.f > 0) mn = max(mn,-z.s);
    else mx = min(mx,z.s);
    for (auto a: adj[x][y]) dfs(a.f,y^1,{-z.f,a.s-z.s});
}

void solve(int x, int y) {
    mn = 0, mx = INF;
    dfs(x,y,{1,0});
    if (mn > mx) {
        cout << "No";
        exit(0);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> R >> C;
    
    int N; cin >> N;
    F0R(i,N) {
        int r,c,a; cin >> r >> c >> a;
        adj[r][0].pb({c,a});
        adj[c][1].pb({r,a});
    }
    FOR(i,1,R+1) if (val[i][0] == ori) solve(i,0);
    FOR(i,1,C+1) if (val[i][1] == ori) solve(i,1);
    cout << "Yes";
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS

Measured memory_bytes: 15872
N = int(input())
As = [int(i) for i in input().split()]
Bs = [int(i) for i in input().split()]
Cs = [int(i) for i in input().split()]

ans = 0
prev = -1
for a in As:
    ans += Bs[a-1]
    if prev + 1 == a:
        ans += Cs[prev-1]
    prev = a

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
 
#define rep(i, n) for (ll i=0;i<(n); i++)
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; }
#define ALL(x) (x).begin(),(x).end()
 
using namespace std;
//using ll=long long;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pi;

const long double PI=3.14159265358979323846;

ll h,w;
ll ans;
//vector<char> masu;

template<class T> bool contain(const std::string& s, const T& v) {
   return s.find(v) != std::string::npos;
}


int main(){
  ll h,w,d;
  cin>>h>>w>>d;

  vector<pi> a(h*w+1);

  ll tmp;
  rep(i, h*w){
    cin >> tmp;
    ll ww = (i+1)%w;
    ll hh = (i+1)/w+1;
    if(ww==0) {
      ww=w;
      hh--;
    }
    
    a[tmp] = make_pair(hh, ww);
  }
  vector<ll> S(h*w+1+d);
  S[0] = 0;

  rep(i, d+1){
    S[i] = 0;
  }

  rep(i,h*w+1){
    ll j = i+1;
    if(j+d>h*w) break;
    S[j+d] = S[j] + abs(a[j+d].first-a[j].first) + abs(a[j+d].second-a[j].second) ;
}
  ll q,l,r;
  cin >>q;
  rep(i, q){
    cin >> l >>r;
    cout <<S[r]-S[l]<<endl;
  }
  
}


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

int N,K;
long ans;
vector<vector<int>> v(100005);
stack<int> s;
vector<bool> red(100005,1);

void dfs(){
  if(s.empty()==0){
    int a=s.top();
    if(v.at(a).size()==0){
      s.pop();
    }
    else{
      if(red.at(v.at(a).back())){
        s.push(v.at(a).back());
        red.at(v.at(a).back())=0;
        ans*=K-v.at(a).size();
        ans%=1000000007;
        v.at(a).pop_back();
      }
      else if(v.at(a).size()>1){
        swap(v.at(a).back(),v.at(a).front());
      }
      else{
        v.at(a).pop_back();
      }
    }
    dfs();
  }
}

int main(){
  cin >> N >> K;
  for(int i=0; i<N-1; i++){
    int a,b;
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  
  int a=0;
  for(int i=1; i<=N; i++){
    if(v[i].size()>=K){
      a=1;
      break;
    }
  }
  
  if(a){
    cout << 0 << endl;
  }
  else{
    s.push(1);
    red.at(1)=0;
    ans=K;
    dfs();
    cout << ans << endl;
  }
}

Measured memory_bytes: 6136
{-# LANGUAGE BangPatterns #-}

import qualified Data.Vector.Unboxed as V
import Data.Array.IArray (listArray, accumArray, (!))
import Data.Array.MArray
import Data.Array.ST (STUArray, runSTUArray)
import Data.Array.Unboxed (UArray)
import Data.List (sortOn, sortBy, unfoldr, partition)
import Data.Char (isSpace)
import Control.Monad.ST (ST)
import Control.Monad.Trans.State (StateT(..))
import qualified Data.ByteString.Char8 as B

import Debug.Trace (trace)

-- utility functions

tr x = trace (show x) x

--   Input functions
readInt = B.readInt . B.dropWhile isSpace

readInts :: Int -> B.ByteString -> [Int]
readInts n = take n . unfoldr readInt

readIntsV :: Int -> B.ByteString -> V.Vector Int
readIntsV n = V.unfoldrN n readInt

readIntsA :: Int -> B.ByteString -> UArray Int Int
readIntsA n bs = runSTUArray $ do
  arr <- newArray_ (0,n-1)
  go arr 0 bs
  return arr
  where
    go :: STUArray s Int Int -> Int -> B.ByteString -> ST s ()
    go arr i bs
      | i==n = return ()
      | otherwise = do
        let Just (x,bs') = readInt bs
        writeArray arr i x
        go arr (i+1) bs'

readTsV :: Int -> B.ByteString -> V.Vector (Int,Int)
readTsV n = V.unfoldrN n $ runStateT ((,) <$> StateT readInt <*> StateT readInt)

readTs :: Int -> B.ByteString -> [(Int,Int)]
readTs n = take n . unfoldr readT where
  readT = runStateT ((,) <$> StateT readInt <*> StateT readInt)

-- main

bti :: Bool -> Int
bti = fromEnum 

solv :: String -> Int
solv s = minimum $ go (head s) (tail s) ini where
  !ini = length . filter (=='E') . tail $ s
  go !leader    []   !n = [n]
  go !leader !(x:xs) !n = n : go x xs n' where
    !n' = n - (bti$x=='E') + (bti$leader=='W')

main = do
  getLine
  s <- getLine
  print $ solv s


Measured memory_bytes: 16764
from collections import deque

d = deque()
n = int(input())
for _ in range(n):
    q = list(map(int,input().split()))
    if q[0] == 0:
        if q[1] == 0:d.appendleft(int(q[2]))
        else        :d.append(int(q[2]))
    if q[0] == 1:
        print (d[int(q[1])])
    if q[0] == 2:
        if q[1]==0:d.popleft()
        else      :d.pop()



Measured memory_bytes: 21980
fn main() {
    let v = read_vec::<i32>();
    let a = v[0];
    let b = v[1];

    let x = a + b;
    let y = a - b;
    let z = a * b;

    println!("{}", std::cmp::max(x, std::cmp::max(y, z)));
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <stdio.h>

int main()
{   
    long i,n,j,k,y;
    scanf("%ld%ld",&n,&y);
        for(i=0;i<=n;i++){
            for(j=0;j<=n-i;j++){
                for(k=0;k<=n-i-j;k++){
                    if(i*10000+j*5000+k*1000==y&&i+j+k==n){
                        printf("%ld %ld %ld",i,j,k);
                        return 0;
                    }
                }
            }    
        }
    printf("-1 -1 -1");
    return 0;
}


Measured memory_bytes: 128
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int GCD(int a,int b)
{
  int r, tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
/*ユークリッドの互除法*/
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


int Svec(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}


/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  int n;
  cin>>n;
  vector<long long int> v(n),w;
  rep(i,n) cin>>v[i];
  rep(i,n){
    int cnt=0;
    while(v[i]%2==0 && v[i]!=0){
      cnt++;
      v[i]/=2;
    }
    w.push_back(cnt);
  }
  long long int a=0,b=0,c=0;
  rep(i,w.size()){
    if(w[i]==0){
      a++;
    }else if(w[i]==1){
      b++;
    }else{
      c++;
    }
  }
  if(b==0){
    if(a-c<=1){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }else if(b==1){
    if(a+1-c<=1){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }else{
    if(a+1-c<=1){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
  }
}

Measured memory_bytes: 2168
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7

sq_sum_a = sum(a)**2
sum_sq_a = sum(map(lambda x: x**2, a))

sum_cross = (sq_sum_a - sum_sq_a) // 2
ans = sum_cross % mod

print(ans)

Measured memory_bytes: 94196
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; ++i)
#define MAX 1e3+50
using namespace std;
typedef pair<int, int> P;


int main() {
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(n-1));
    rep(i,n) {
        rep(j, n-1) {
            cin >> a[i][j];
            a[i][j]--;
        }
        reverse(a[i].begin(), a[i].end());
    }
    vector<P> q;
    auto check = [&](int i) {   // lambda
        if (a[i].size() == 0) return;
        int j = a[i].back();
        if (a[j].size() == 0) return;
        if (a[j].back() == i) {
            if (i > j) swap(i, j);
            q.push_back(P(i,j));
        }
    };
    rep(i,n) {
        check(i);
    }
    int day = 0;
    while (q.size() > 0) {
        day++;
        sort(q.begin(), q.end());
        q.erase(unique(q.begin(), q.end()), q.end());
        vector<P> prevQ; swap(prevQ, q);
        for (P p : prevQ) {
            int i = p.first, j = p.second;
            a[i].pop_back();
            a[j].pop_back();
            check(i);
            check(j);
        }
    }
    rep(i, n) {
        if (a[i].size() != 0) {
            puts("-1");
            return 0;
        }
    }
    cout << day << endl;
    return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std ;
 int main(){
   	int a,b ;
 	cin >> a >> b ;
	if ((a+b)%2==1){
    	cout << (a+b+1)/2 << endl ;
    } else {
    	cout <<(a+b)/2 <<endl ;
    }  
   	return 0;
 }

Measured memory_bytes: 256
#n=int(input())
#n,m=map(int,input().split())
#a=list(map(int,input()))
#ab=[list(map(int,input().split())) for _ in range(n)]
#s=input()
s=int(input())
mod=pow(10,9)+7
ans=0

# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,s+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)


# 長さkの数列の個数
for k in range(1,s//3+1):
  sk=s-k*3
  tmp=cmb(sk+k-1,k-1,mod)
  ans+=tmp
  ans%=mod
print(ans)

Measured memory_bytes: 65428
/* h-ex9_1
   Ohshima */

#include <stdio.h>
#include <stdlib.h>
//スタックに格納するデータの最大数
#define SIZE 11

//スタックの定義
typedef struct stack{
  int size;
  int count;
  char data[SIZE + 1]; //topの初期位置を考慮
  char *top;
}stack;

//スタックの初期化
void initialize_stack(stack *stk){
  stk->count = 0;
  stk->size = SIZE;
  stk->top = &(stk->data[SIZE]);
}

//データの追加
void push(stack *stk, char elem){
  if(stk->count >= stk->size){
    fprintf(stderr, "Error: stack overflow. (x=%c)\n", elem);
    exit(1);
  }else{
    stk->top--;
    *(stk->top) = elem;
    stk->count++;
  }
}

//データの取り出し
void pop(stack *stk){
  if(stk->count <= 0){
    fprintf(stdout, "Error: stack underflow.\n");
    exit(1);
  }else{
    stk->top++;
    stk->count--;
  }
}

int main(void){
  stack stk;
  char tmp;
  int i;
  //スタックを初期化（ポインタ渡しで関数にわたすこと）
  initialize_stack(&stk);
  //1文字ずつ標準入力から受け取り以下を実行
  while(scanf("%c", &tmp) != EOF){
    //B以外の文字のときスタックにデータを追加
    if(tmp != 'B'){
      push(&stk, tmp);
    }else{
      //Bがきた場合、文字列が空でないならデータを取り出す
      if(stk.count > 0){
        pop(&stk);
      }
    }
  }
  //最後に、スタックに残っている文字を古いものから1文字ずつ出力
  for(i = 0; stk.count-- > 0; i++){
    putchar(stk.data[SIZE - 1 - i]);
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 1576
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

    def find(self, x):
        if x == self.par[x]:
            return self.par[x]
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        if self.same(x, y):
            return
        xr = self.find(x)
        yr = self.find(y)
        if self.size[xr] > self.size[yr]:
            xr, yr = yr, xr
        self.size[yr] = self.size[xr] + self.size[yr]
        self.par[xr] = yr


def submit():
    n, m = map(int, input().split())
    plist = list(map(int, input().split()))
    
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x, y)

    groups = {}
    for i in range(1, n + 1):
        r = uf.find(i)
        if r not in groups.keys():
            groups[r] = {i}
        else:
            groups[r].add(i)

    ans = 0
    for group in groups.values():
        for g in group:
            if plist[g - 1] in group:
                ans += 1
    print(ans)


submit()

Measured memory_bytes: 45020
#include <iostream>
using namespace std;
int main(){
	char d[200001];
	cin >> d;
	int i = 0;
	int sum=0;
	while (d[i] != '\0') {
		sum += d[i] - '0';
		i++;
	}
	if (sum % 9 == 0) cout << "Yes";
	else cout << "No";

}

Measured memory_bytes: 3824
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (long long i = 0; i < (long long)(n); ++i)
using P = pair<long long, long long>;

long long M;
long long m;
long long a[200000];
long long N, K;
long long ob;


bool isOk(long long key) {
  long long cnt = 0;
  if(key <= 0) {
    rep(i, N-1) {
      if(a[i] == 0) {
        cnt += N-1-i;
        continue;
      }
      if(a[i] < 0) {
        long long k = key / a[i];
        long long temp = upper_bound(a+i+1, a+N, k) - (a+i+1);
        cnt += temp;
      } else {
        long long k = key / a[i];
        long long temp = (a+N) - lower_bound(a+i+1, a+N, k);
        cnt += temp;
      }
    }
  } else {
    rep(i, N-1) {
      if(a[i] == 0) {
        continue;
      }
      if(a[i] < 0) {
        long long k = (key-1) / a[i];
        long long temp = lower_bound(a+i+1, a+N, k) - (a+i+1);
        cnt += temp;
      } else {
        long long k = (key-1) / a[i];
        long long temp = (a+N) - upper_bound(a+i+1, a+N, k);
        cnt += temp;
      }
    }
  }
  // cout << cnt << endl;
  if(cnt <= ob) return true;
  else return false;
}

long long upper_search(long long M, long long m) {
  long long r = M+1;
  long long l = m-1;
  // cout << "init " << r << " " << l << endl;
  while(r - l > 1) {
    long long half = (r+l) / 2;
    if(isOk(half)) r = half;
    else l = half;
    // cout << l << " " << r << " " << half << endl;
  }
  return r;
}

int main() {
  cin >> N >> K;
  ob = N * (N-1) / 2 - K;
  rep(i, N) {
    cin >> a[i];
  }
  sort(a, a+N);
  long long M = max(a[0]*a[1], a[N-1]*a[N-2]);
  long long m = min(a[0]*a[1], a[N-1]*a[0]);
  long long ans = upper_search(M, m) - 1;
  // cout << m << " " << M << endl;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5180
#!/usr/bin/env python
# -*- coding: utf-8 -*-


S = list(map(int,input().split()))
N,K=S[0],S[1]

p = 0

# 出た目がNから順に評価
# K<100000 なので、2^16まで
for i in range(N,0,-1):
    if i >= K:
        p += 1/N
    elif K/2 <= i < K:
        p += 1/N/2
    elif K/2**2 <= i < K/2:
        p += 1/N/2**2
    elif K/2**3 <= i < K/2**2:
        p += 1/N/2**3
    elif K/2**4 <= i < K/2**3:
        p += 1/N/2**4
    elif K/2**5 <= i < K/2**4:
        p += 1/N/2**5
    elif K/2**6 <= i < K/2**5:
        p += 1/N/2**6
    elif K/2**7 <= i < K/2**6:
        p += 1/N/2**7
    elif K/2**8 <= i < K/2**7:
        p += 1/N/2**8
    elif K/2**9 <= i < K/2**8:
        p += 1/N/2**9
    elif K/2**10 <= i < K/2**9:
        p += 1/N/2**10
    elif K/2**11 <= i < K/2**10:
        p += 1/N/2**11
    elif K/2**12 <= i < K/2**11:
        p += 1/N/2**12
    elif K/2**13 <= i < K/2**12:
        p += 1/N/2**13
    elif K/2**14 <= i < K/2**13:
        p += 1/N/2**14
    elif K/2**15 <= i < K/2**14:
        p += 1/N/2**15
    elif K/2**16 <= i < K/2**15:
        p += 1/N/2**16
    elif K/2**17 <= i < K/2**16:
        p += 1/N/2**17

print(p)


Measured memory_bytes: 3064
#include <stdio.h>

#define MAX_RANK 14

int main() {
    int spades[MAX_RANK];
    int hearts[MAX_RANK];
    int clubs[MAX_RANK];
    int diamonds[MAX_RANK];

    int n;
    char suit;
    int rank;
    char c;

    for (int i=1; i<MAX_RANK; ++i) {
        spades[i] = 0;
    }
    for (int i=1; i<MAX_RANK; ++i) {
        hearts[i] = 0;
    }
    for (int i=1; i<MAX_RANK; ++i) {
        clubs[i] = 0;
    }
    for (int i=1; i<MAX_RANK; ++i) {
        diamonds[i] = 0;
    }

    scanf("%d", &n);
    scanf("%c", &c);
    for (int i=0; i<n; ++i) {
        scanf("%c %d", &suit, &rank);
        if (suit == 'S') {
            spades[rank] = 1;
        } else if (suit == 'H') {
            hearts[rank] = 1;
        } else if (suit == 'C') {
            clubs[rank] = 1;
        } else if (suit == 'D') {
            diamonds[rank] = 1;
        }
        scanf("%c", &c);
    }

    for (int i=1; i<MAX_RANK; ++i) {
        if (spades[i] == 0) {
            printf("S %d\n", i);
        }
    }
    for (int i=1; i<MAX_RANK; ++i) {
        if (hearts[i] == 0) {
            printf("H %d\n", i);
        }
    }
    for (int i=1; i<MAX_RANK; ++i) {
        if (clubs[i] == 0) {
            printf("C %d\n", i);
        }
    }
    for (int i=1; i<MAX_RANK; ++i) {
        if (diamonds[i] == 0) {
            printf("D %d\n", i);
        }
    }

    return 0;
}



Measured memory_bytes: 2148
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int ans=-1e9,n,a[101][10],b[101][10],c[10];
int main(){
  cin>>n;
  r(i,n)r(j,10)cin>>a[i][j];
  r(i,n)r(j,11)cin>>b[i][j];
  for(int i=1;i<(1<<10);i++){
    memset(c,0,sizeof(c));
    r(j,10)if((1<<j)&i)c[j]=1;
    int sum=0;
    r(j,n){
      int x=0;
      r(k,10)if(a[j][k]&&c[k])x++;
      sum+=b[j][x];
    }
    //if(sum==0)cout<<i<<endl;
    ans=max(ans,sum);
  }
  cout<<ans<<endl;
}

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

using ll = long long;

ll a[200010];

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

    int n;cin>>n;
    ll xo=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        xo^=a[i];
    }

    for(int i=0;i<n;i++)
    {   
        ll ans=xo^a[i];
        cout<<ans<<" ";
    }

    cout<<"\n";

    return 0;
}


Measured memory_bytes: 5100
N  = int(input())
dp = [[0]*3 for _ in range(N+1)]

for n in range(1,N+1):
  a, b, c = map(int,input().split())
  dp[n][0] = max(dp[n-1][1], dp[n-1][2]) + a
  dp[n][1] = max(dp[n-1][0], dp[n-1][2]) + b
  dp[n][2] = max(dp[n-1][0], dp[n-1][1]) + c
print(max(dp[N]))
  

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define gap ' '
#define L(i) ((i) - (&i))

const ll inf = 1e9 + 7;
const int MAXN = 2 * 1e5 + 10;

	
int main(){		
	int n; cin >> n;
	ll k = 1000;
	while(k < n){
		k+=1000;
	}
	cout << k - n << endl;


	return 0;
}


Measured memory_bytes: 3560
from collections import Counter
from collections import deque
from functools import reduce
from operator import mul
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def COMBINATION(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    o = reduce(mul, range(n, n - r, -1))
    u = reduce(mul, range(1, r + 1))
    return o // u
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n, d = MI()
x = [LI() for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i+1, n):
        a = [(x[i][k] - x[j][k]) ** 2 for k in range(d)]
        if (sum(a) ** 0.5).is_integer():
            ans += 1
print(ans)




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

int main(){
    int a, b;
    char op;
    cin >> a >> op >> b;
    cout << (op == '+' ? a+b : a-b) << endl;
}


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

using namespace std;

int main () {
  int n;
  cin >> n;
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    int a;
    cin>> a;
    if (a % 2 == 1) cnt++;
  }
  
  if (cnt % 2 == 1) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
  return 0;
}

Measured memory_bytes: 764
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
const int N=105;
int b[N],n,a[N];
std::vector<int> ans;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=n;i;i--) {
        int p=-1;
        for(int j=1;j<=i;j++) if(a[j]==j) {
            p=j;
        }
        if(p==-1) return !printf("-1");
        int cnt=0;
        for(int j=1;j<p;j++) b[++cnt]=a[j];
        for(int j=p+1;j<=i;j++) b[++cnt]=a[j];
        for(int j=1;j<=cnt;j++) a[j]=b[j];
        ans.push_back(p);
    }
    reverse(ans.begin(),ans.end());
    for(int v:ans) printf("%d\n",v);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>


using namespace std;

//const long long int mod = 1e9+7;
const long long int MAXN = 1e5;

int main()
{
	long long int n,a[MAXN] = {0},x;

	cin >> n >> x;

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

	long long int cnt = 0;

	for(int i = 1; i < n; i++)
	{
		if (a[i-1]+a[i] > x)
		{
			long long int s = a[i-1] + a[i] - x;
			if (a[i] - s < 0)
			{
				a[i] = 0;
				a[i-1] -= s - a[i];
				cnt += s;
			}else
			{
				a[i] -= s;
				cnt += s;
			}
		}
	}

	cout << cnt << endl;

	return 0;
}
	

Measured memory_bytes: 1024
n = int(input())
a =[ -float('inf') ] * n
b = list(map(int, input().split()))
a[0] = b[0]
a[n-1] = b[n-2]
for i in range(1, n-1):
  a[i] = min(b[i-1], b[i])
print(sum(a))

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

#ifdef DEBUG
#include "../include/debug.hpp"
#else
#define debug(...) 42
#define rdfile(...) 42
#endif

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // rdfile("_input.txt");

    int N;
    cin >> N;
    if (N % 2 == 1) N *= 2;
    cout << N << endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

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

func main() {
	defer stdout.Flush()
	s := []byte(readString())
	ans := math.MaxInt32
	for c := byte('a'); c <= 'z'; c++ {
		ans = min(ans, solve(s[:], c))
	}
	println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func solve(t []byte, c byte) int {
	res := 0
	tmp := 0
	for _, d := range t {
		if d == c {
			res = max(res, tmp)
			tmp = 0
		} else {
			tmp++
		}
	}
	res = max(res, tmp)
	return res
}

func solve_(t []byte, c byte) int {
	n := len(t)
	s := make([]byte, n)
	copy(s, t)
	var count int
	j := n
	for j > 0 {
		eprintln(string(c), count, string(s[:j]))
		finished := true
		for i := 0; i < j; i++ {
			if s[i] != c {
				finished = false
			}
		}
		if finished {
			break
		}

		count++
		j--
		for i := 0; i < j; i++ {
			if s[i+1] == c {
				s[i] = c
			}
		}
	}
	eprintln(string(c), count)
	return count
}

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


Measured memory_bytes: 640
/*
title:

url:
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <queue>
#include <limits>
#include <string>
#include <utility>
#include <cstring>
#include <map>
#include <cmath>
#include <iterator>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define INF 1000000007

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

int main()
{
    int n;
    cin >> n;
    int data[2][n];
    REP(i, 2)
    {
        REP(j, n)
        {
            cin >> data[i][j];
        }
    }

    int ans[n];

    //iはいつ下に降りるか
    REP(i, n)
    {
        ans[i] = 0;
        for (int j = 0; j <= i; j++)
        {
            ans[i] += data[0][j];
        }
        for (int j = i; j < n; j++)
        {
            ans[i] += data[1][j];
        }
    }

    cout << *max_element(ans, ans + n) << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
mod = 10**9+7

if N > 1:
    memo[2] = 2

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if N > 1 and memo[1] == None and memo[2] != None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

if memo[N] == None:
    print(0)
else:
    print(memo[N]%mod)


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

int main() {
    ll a;
    int b, c;

    cin >> a;
    scanf("%d.%d", &b, &c);

    ll ans = a * b * 100 + a * c;
    cout << ans / 100 << endl;

    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> lr(N);
  for (int i=0; i<N; i++) cin >> lr.at(i).first >> lr.at(i).second;
  int ans = 0;
  for (int i=0; i<N; i++) ans += lr.at(i).second-lr.at(i).first+1;
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int r = sc.nextInt();
		int D = sc.nextInt();
		int x = sc.nextInt();

		int[] X = new int[11];
		X[0] = x;

		for(int i=0;i<10;i++) {
			X[i+1]=r*X[i] -D;


		}
		for(int i=0;i<10;i++) {
			System.out.println(X[i+1]);
		}

	}

}


Measured memory_bytes: 21460
#include<bits/stdc++.h>
#define int long long
int n,tot,ans,a[100];
inline void exgcd(int a,int b,int &x,int &y) {
	if(!b) {
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
inline int solve(int a,int b) {
	int x,y;
	exgcd(a,b,x,y);
	x=(x%b+b)%b;
	if(!x)x=b;
	y=(1-a*x)/b;
	y=-y;
	if(y<=0) return n;
	return a*x;
}
signed main() {
	std::cin>>n,ans=2*n;
	if(n==1) return puts("1"),0;
	n=n*2;
	int tmp=n;
	for(int i=2; i*i<=tmp; ++i) {
		if(tmp%i==0) {
			++tot,a[tot]=1;
			while(tmp%i==0) tmp/=i,a[tot]*=i;
		}
	}
	if(tmp) a[++tot]=tmp;
	for(int up=0; up<(1<<tot)-1; ++up) {
		int x=1,y=1;
		for(int j=0; j<tot; ++j)
			if(up>>j&1)x*=a[j+1];
			else y*=a[j+1];
		ans=std::min(ans,std::min(solve(x,y),solve(y,x)));
	}
	std::cout<<ans-1<<'\n';
	return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define ll          long long int
#define uu          first
#define vv          second
#define pii         pair<int,int>
#define pll         pair<ll,ll>
#define INF         1e9
#define fastRead    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

const int MAX = 1e6 + 6;
int main()
{
    fastRead;
    
    int n;
    ll ans = 0;
    cin>>n;
    for(int i =1 ; i <=n ; i++ ) {
        ll tmp = 1LL*i *(n-i+1);
        ans += tmp;
    }
    
    for(int i = 1 ; i < n ; i++ ) {
        int u, v;
        cin>>u>>v;
        
        if(u > v) swap(u, v);
        
        ll tmp = 1LL*u * (n -v + 1);
        ans -= tmp;
    }
    cout<<ans<<'\n';
    return 0;
    
}

Measured memory_bytes: 3620
# transformation.py
def originalPrint(text,start,end):
    print(text[start: end])
    
def originalReverse(text,start,end):
    head = (text[:start])
    target = (text[start:end])
    sliced = target
    reversed_text = sliced[::-1]
    tail = text[end:]
    # print(head+reversed_text+tail)
    text = head+reversed_text+tail
    return text
    
def orignalReplace(text,start,end, replace_text):
    head = (text[:start])
    tail = text[end:]
    # print(head+replace_text+tail)
    text = head+replace_text+tail
    return text

text = input()
num = int(input())

for i in range(num):
    order_info = input().split()
    order = order_info[0]
    start = int(order_info[1])
    end = int(order_info[2]) + 1
    if order == 'print':
        originalPrint(text, start, end)
    elif order == 'reverse':
        text = originalReverse(text, start, end)
    elif order == 'replace':
        replace_text = order_info[3]
        text = orignalReplace(text, start, end,replace_text)
    


Measured memory_bytes: 5616
#include <stdio.h>
int main()
{
  int a,b,t;
  int x;
  scanf("%d %d %d",&a,&b,&t);
  if(a>=1 && a<=20 && b>=1 && b<=20 && t>=1 && t<=20){
  	x = (t+0.5)/a;
    printf("%d\n",x*b);
  }
  return 0;
}
  
  

Measured memory_bytes: 128
#include <stdio.h>
int abs(int n){
		if(n<0){
		return -1*n;}else
		return n;}
int main(void)
{int N,A,M,B,x,i,a,b,c,l,m,tmp;
	scanf("%d%d%d",&a,&b,&c);
if((b-a)==(c-b)){
	printf("YES");}
	else
	printf("NO");


	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 998244353;
long long INF = 1000000000000000;

typedef long long ll;

int main(void) {
  int n; cin >> n;
  cout << n * (n - 1) / 2 - n / 2 << endl;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (i + j + 2 == n + 1 - n % 2) continue;
      cout << i + 1 << " " << j + 1 << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAX 200000000000

int main() {
  long long n,k;
  scanf("%llu %llu", &n, &k);
  long long X[n];
  for (long long i=0; i<n; i++) {
    scanf("%llu", &X[i]);
  }

  long long res = MAX;

  for (long long i=0; i<=n-k; i++) {
    if (X[i]<0 && X[i+k-1]<0) {
      res = min(res, abs(X[i]));
    }
    if (X[i]<0 && X[i+k-1]>=0) {
      long long p = min(abs(X[i]), abs(X[i+k-1]));
      res = min(res, abs(X[i])+abs(X[i+k-1])+p);
    }
    if (X[i]>=0 && X[i+k-1]>=0) {
      res = min(res, abs(X[i+k-1]));
    }
  }

  printf("%llu\n", res);

  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;

const int OO = (int) 2e9;
const double eps = 1e-9;

const int N = 500005;

int n;
string a;
int dp[N];
int nxt[N];

int calc(int idx) {
	if (idx >= n) {
		return 0;
	}
	int &ret = dp[idx];
	if (ret != -1)
		return ret;
	int j = nxt[idx];
	if (a[idx] == '0')
		return ret = calc(j + 1);
	ret = calc(j + 1);
	if (idx != j)
		ret = max(ret, calc(j));
	if (a[j + 1] == '0' && a[j + 2] == '1') {
		ret = max(ret, calc(j + 3) + (j - idx + 1));
	}
	if (a[idx] == '1' && a[idx + 1] == '0' && a[idx + 2] == '1') {
		int k = nxt[idx + 2];
		ret = max(ret, calc(k + 1) + (k - idx - 1));
		ret = max(ret, calc(k) + (k - idx - 2));
	}
	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
//	freopen("in.txt", "rt", stdin);
//	freopen("out.txt", "wt", stdout);
#endif
	cin >> n >> a;
	nxt[n - 1] = n - 1;
	for (int i = n - 2; i >= 0; i--) {
		nxt[i] = i;
		if (a[i] == a[i + 1])
			nxt[i] = nxt[i + 1];
	}
	MMS(dp, -1);
	cout << calc(0) << endl;
	return 0;
}


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

using namespace std;
int n;
int a[105];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    double ans=1.0*(a[1]+a[2])/2.0;
    for(int i=3;i<=n;i++)
    {
        ans=1.0*(ans+a[i])/2.0;
    }
    printf("%.10f",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector <vector<int>> G;
long long f[100100] , dp[100100][2] , MOD = 1000000007; //0 alb 1 negru;

void dfs(int x)
{
    f[x] = 1;
    long long p0 = 1;
    long long p1 = 1;
    for (int y : G[x])
        if(!f[y])
        {
            dfs(y);
            (p0 *= (dp[y][0] + dp[y][1])) %= MOD;
            (p1 *= dp[y][0]) %= MOD;
        }
    dp[x][0] = p0 % MOD;
    dp[x][1] = p1 % MOD;
}
int main()
{
    int n;
    cin >> n;
    G.resize(n+1);
    for (int i=0 ; i<n-1 ; i++)
    {
        int x , y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    cout << (dp[1][0] + dp[1][1]) % MOD;

    return 0;
}

Measured memory_bytes: 13568
function main(input){
  const args = input.split(' ');
  const R = parseInt(args[0], 10),
        G = parseInt(args[1], 10),
        B = parseInt(args[2], 10),
        N = parseInt(args[3], 10);
  
  var s = 0;
  var k = 0;
  for (var i = 0; i <= (N / R | 0); ++i){
    for (var j = 0; j <= (N / G | 0); ++j){
      k = ((N - i*R - j*G) / B) | 0;
      if (k >= 0 && i*R + j*G + k*B == N) ++s;
    }
  }
  console.log(s);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n];
	map<int,ll> m;
	ll sum=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		m[a[i]]++;
		sum+=a[i];
	}
	int q;
	cin>>q;
	int b,c;
	while(q--)
	{
		cin>>b>>c;
		sum-=b*m[b];
		m[c]+=m[b];
		sum+=m[b]*c;
		m[b]=0;
		cout<<sum<<"\n";
	}
	
	return 0;
}

Measured memory_bytes: 10000
N = int(input())
s = {}
for _ in range(N):
  a = "".join(sorted(input()))
  if a not in s:
    s[a] = 0
  else: s[a] += 1

import math
ans = 0
for v in s.values():
  if v < 2: ans += v
  if v > 1: ans += v*(v+1)//2
print(ans)

Measured memory_bytes: 17844
//#define MYDEBUG
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <queue>
#include <stack>

#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define umap unordered_map
using namespace std;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ",";
  }
  out << "]";
  return out;
}

ll a, b, c;
void solve() {
  cin >> a >> b >> c;
  ll x = a;
  for (int i = 0; i < 100000000; ++i) {
    if (x % b == c) {
      cout << "YES" << endl;
      return;
    } else {
      x += a;
    }
  }
  cout << "NO" << endl;
}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n)for(int i=0;i<(int)(n);i++)
#define PI 3.141592653589793
//vector < vector<int>>a(0, vector<int>(0));二次元配列宣言


int main()
{
	int h, n;
	cin >> h >> n;
	int i;
	vector<int>a(n);
	for (i = 0; i < n; i++)
	{
		cin >> a.at(i);
		h -= a.at(i);
		if (h <= 0)
		{
			break;
		}
	}
	if (h <= 0)
		cout << "Yes" << endl;
	else
		cout << "No"<<endl;

	
}

Measured memory_bytes: 3788