akhauriyash/Code-Regression huggingface dataset:
require 'set'

n, m, tax = gets.strip.split.map(&:to_i)
abc = readlines.map {|line| line.strip.split.map(&:to_i) }
abc = abc.map {|a, b, c| [a, b, -1*(c-tax)] }

# 特殊な隣接リストを構築
graph = Array.new(n+1) { [] }
r_graph = Array.new(n+1) { [] }
abc.each do |a, b, c|
  graph[a] << [b, c]
  r_graph[b] << [a, c]
end

# スタートとゴールから到達可能なノードを列挙
def reachable(graph, s)
  visit = Set.new
  visit.add(s)
  q=[s]
  until q.empty?
    u=q.shift
    graph[u].each do |n, _|
      next if visit.include?(n)
      visit << (n)
      q.push(n)
    end
  end
  visit
end

from_1 = reachable(graph, 1)
from_n = reachable(r_graph, n)

available_nodes = from_1 & from_n
available_roads = abc.select {|a, b, _| available_nodes.include?(a) || available_nodes.include?(b) }

# ベルマンフォードで経路探索、最短経路を算出
INF = 1 << 60
dist=Array.new(n+1, INF)
dist[1]=0
updated=false

available_nodes.each do
  updated=false
  available_roads.each do |from, to, cost|
    if dist[from] != INF && dist[to] > dist[from] + cost
      dist[to] = dist[from] + cost
      updated = true
    end
  end
  break unless updated
end

if updated
  p -1
  exit
end

#p abc
#p [from_1, from_n]
#p available_roads
#p dist
p [-1*dist[n], 0].max



Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
//size_t f = string::npos
//make pair

int main(){
      int a,b;cin >> a >> b;
      if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0)cout << "Possible";
      else cout << "Impossible";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static int x;
        
        static void Main(string[] args)
        {
            //[summary]B - Exponential
            x = int.Parse(Console.ReadLine());
            
            int sqrt = (int)Math.Sqrt(x);
            var pows = new List<int>() { 1 };
            
            for(int i = 2; i <= sqrt; i++)
            {
                int pow = GetMaxPower(i);
                pows.Add(pow);
            }
            
            Console.WriteLine(pows.Max());
        }
        
        static int GetMaxPower(int n)
        {
            int i = 2;
            int pow = (int)Math.Pow(n, i);
            
            while(pow <= x)
            {
                i++;
                pow = (int)Math.Pow(n, i);
            }
            
            if(pow <= x)
            {
                return pow;    
            }
            else
            {
                return (int)Math.Pow(n, i - 1);
            }
        }
        
        static List<int> ReadLine()
        {
            var line = Console.ReadLine();
            var array = line.Split(' ');

            return array.Select(x => int.Parse(x)).ToList();
        }
    }
}

Measured memory_bytes: 13268
def calculate(s, t):
    a = sorted(s)
    b = sorted(t,reverse=True)

    m = "".join(a)
    k = "".join(b)

    if m < k:
        print("Yes")
    else:
        print("No")


# s = 'yx'
# t = 'axy'
#
# s = 'ratcode'
# t = 'atlas'
#
# s = 'cd'
# t = 'abc'
#
# s = 'w'
# t = 'ww'

s = input()
t = input()
calculate(s, t)


Measured memory_bytes: 9104
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

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

const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    
    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    int n, k;
    cin>>n>>k;
    vi as(n);
    rep(i, n) cin>>as[i];

    vector<vector<mint>> dp(n + 1, vector<mint>(k + 1));
    dp[0][0] = 1;
    rep(i, n) {
        mint s = 0;
        rep(j, k + 1) {
            s += dp[i][j];
            if (j > as[i]) s -= dp[i][j - as[i] - 1];
            dp[i + 1][j] += s;
        }
    }
    cout<<dp[n][k]<<endl;;
}

Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define rep(i,n); for(int i = 0;i < (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> state;
long double pi = acos(-1);
const int INF = 1001001001;


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
char changeS(char alpha){
  if(0x41 <= alpha and alpha <= 0x5A)return (alpha + 0x20);
  else if(0x61 <= alpha and alpha <= 0x7A)return (alpha - 0x20);
  return alpha;
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }
int ceil(int a,int b){
  // a/bの切り上げを考える
  return (a+b-1)/b;
}



int main(){ 
  string s;
  cin >> s;
  rep(i,3)cout << s[i];
  cout << endl;
}



Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string S;
    int one=0;
    int zero=0;
    cin >> S;
    for(int i=0; i<S.size(); i++){
        if(S.at(i)=='0'){
            zero++;
        }
        if(S.at(i)=='1'){
            one++;
        }
    }
    if(zero<=one){
        cout << zero*2 << endl;
    }
    else{
        cout << one*2 << endl;
    }
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N;
    cin >> N;
    vector<string> V;
    bool ans = true;
    for ( int i = 0; i < N; i++ ) {
        string s;
        cin >> s;
        if ( V.size() > 0 ) {
            string a;
            a = V.back();
            if ( a[a.length()-1] != s[0] ) { ans = false; }

            for ( int j = 0; j < V.size(); j++ ) {
                if ( s == V[j] ) { ans = false; }
            }
        }
        V.push_back(s);

    }

    cout << ( ans ? "Yes" : "No" ) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
    int N; cin>>N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin>>A[i];
    }
    ll ans=1ll;
    vector<ll> cnt(100010,0);
    for (int i = 0; i < N; ++i) {
        int tmp=A[i];
        if(tmp==0){
            if(cnt[0]>=3){ cout<<0<<endl; return 0;}
            (ans*=3ll-cnt[0])%=MOD;
            ++cnt[tmp];
        }else{
            if(cnt[tmp-1]==0||cnt[tmp-1]==cnt[tmp]||cnt[tmp]==3) { cout<<0<<endl; return 0;}
            (ans*=cnt[tmp-1]-cnt[tmp])%=MOD;
            ++cnt[tmp];
        }

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


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

    vector<int>sum(N);
    for(int i=0;i<N;i++){
        int count=0;
        while(1){
            if (vec.at(i)%2==0){
                vec.at(i)=vec.at(i)/2;
                count++;
            }
            else break;
        }
        sum.at(i)=count;
    }
    sort(sum.begin(),sum.end());
    cout<<sum.at(0)<<endl;
}


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

int main(){
  string s;
  cin >> s;
  if(s == "hi"){
    cout << "Yes" << endl;
  }
   else if(s == "hihi"){
    cout << "Yes" << endl;
  }
  else if(s == "hihihi"){
    cout << "Yes" << endl;
  }
  else if(s == "hihihihi"){
    cout << "Yes" << endl;
  }
  
  else if(s == "hihihihihi"){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

using namespace std;

int main() {
  int N, M;
  cin >> N;
  cin >> M;
  
  int votes = 0;
  vector <int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    votes += A[i];
  }
  
  int cnt = 0;
  for (int i = 0; i < N; ++i) {
    if (A[i] >= votes / (float)(4 * M)) cnt++;
  }
  
  if (cnt >= M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
int a[2][105];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=2;i++){
		for(int j=1;j<=n;j++){
			a[i][j]+=max(a[i-1][j],a[i][j-1]);
		}
	}
	cout<<a[2][n]<<endl;
	return 0;
}

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

from sys import stdin


def main():
    x = int(stdin.readline())

    money = 100
    year = 0

    while True:
        money += int(money * 0.01)
        year += 1
        if money >= x:
            break
    print(year)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9164
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace __gnu_pbds;
using namespace std;
/*
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
*/
#define ull unsigned long long int
#define ll long long int
#define ld long double
#define MAX 1000000007
//1e9+7
#define pll pair<ll,ll>
#define pii pair<int,int>
#define piii pair<int,pii>
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FO ifstream fin("a.in");ofstream fout("a.out");
#define TEST int testcase;cin>>testcase;while(testcase--)
#define FTEST int testcase;fin>>testcase;while(testcase--)
#define all(x) (x).begin(),(x).end()
#define mset0(x) memset((x), 0, sizeof((x)));
#define mset1(x) memset((x), -1, sizeof((x)));
#define endl "\n"
#define plll pair<ll,pll>
#define plii pair<ll,pii>
#define no {cout<<"no"<<endl;return;}
#define yes {cout<<"yes"<<endl;}

const int maxn=1e6;
//const int mod=998244353;
typedef tree<ll,null_type,less<ll>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int arr[maxn];
ll power(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%MAX;
        b/=2;
        a=(a*a)%MAX;
    }
    return(ans);
}

void solve(){
    ll N;cin>>N;
    ll no_zero=power(9,N);
    ll no_nine=power(9,N);
    ll total=power(10,N);
    ll no_both=power(8,N);
    ll ans=(no_nine+no_zero)%MAX;
    ans=(ans-no_both+MAX)%MAX;
    total=(total-ans+MAX)%MAX;
    cout<<total;



    return;

}

int main(){
    IO


    //TEST
    solve();


}



Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;

struct LowestCommonAncestor {
  int n, h;
  vector<vector<int>> g, par;
  vector<int> dep;

  LowestCommonAncestor(int sz) {
    n = sz; h = 1;
    g.resize(n), dep.resize(n);
    while ((1 << h) <= n) h++;
    par.assign(h, vector<int>(n, -1));
  }

  void add_edge(int u, int v) {
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }

  void dfs(int u, int p, int depth) {
    par[0][u] = p;
    dep[u] = depth;
    for (auto v : g[u]) {
      if (v == p) continue;
      dfs(v, u, depth + 1);
    }
  }

  void build(int root = 0) {
    dfs(root, -1, 0);
    for (int i = 0; i + 1 < h; i++) {
      for (int j = 0; j < n; j++) {
        if (par[i][j] != -1) par[i+1][j] = par[i][par[i][j]];
        else par[i+1][j] = -1;
      }
    }
  }

  int query(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    for (int i = h-1; i >= 0; i--) {
      if ( ((dep[v] - dep[u]) >> i) & 1) v = par[i][v];
    }
    if (u == v) return u;
    for (int i = h-1; i >= 0; i--) {
      if (par[i][u] != par[i][v]) {
        u = par[i][u];
        v = par[i][v];
      }
    }
    return par[0][u];
  }
};

int main(){ 
  int n;
  cin >> n;
  LowestCommonAncestor lca(n);
  rep(i,n) {
    int k;
    cin >> k;
    rep(j,k) {
      int c; cin >> c;
      lca.add_edge(i, c);
    }
  }
  lca.build();
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    cout << lca.query(u, v) << endl;
  }
  return 0;
} 


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

vector<int> E[100100];
int saki[100100];
int keisan(int a) {
	if (saki[a] != -1) return saki[a];


}

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


	int N;
	cin >> N;
	int A[100001] = {};
	rep(i, N) {
		int a;
		cin >> a;
		A[a]++;		
	}
	ll kotae = 0;
	rep1(i, 100000) {
		kotae += A[i] * 1ll * i;
	}

	int Q;
	cin >> Q;

	rep(i, Q) {
		int b, c;
		cin >> b >> c;

		ll tmp = A[b];
		A[b] = 0;
		A[c] += tmp;

		kotae += tmp * (c - b);
		co(kotae);
	}





	Would you please return 0;
}

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

#define int long long
#define DEBUG(x) cerr <<#x<<":"<<x<<endl;
#define DEBUG2(x, y) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<endl;
#define DEBUG3(x, y, z) cerr <<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl;
#define DEBUGVC(x) cerr <<#x<<": "; for(auto a:x) cerr << a <<" "; cerr << endl;
#define DEBUGMP(x) cerr <<#x<<":"<<endl; for(auto a:x) cerr << a.first <<" "<< a.second << endl;
#define MAX_N (1000006)
#define INF (1LL << 60)
const int MOD = (int)1e9+7;


signed main(){
    while (true) {
        int n;
        cin >> n;
        if (n==0) { break; }
        vector<int> v;
        for(int i=0; i<n; i++) {
            int p;
            cin >> p;
            v.push_back(p);
        }
        sort(v.begin(),v.end());
        int sum = 0;
        for(int i=1; i<n-1; i++) {
            sum += v[i];
        }
        cout << sum/(n-2) << endl;
    }
}


Measured memory_bytes: 3124
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-6;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

lint lcm(lint a, lint b) {
    return (a / gcd(a, b)) * b;
}

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int c1x, c1y, c1r, c2x, c2y, c2r;
    cin >> c1x >> c1y >> c1r >> c2x >> c2y >> c2r;
    double dist = sqrt((c1x - c2x) * (c1x - c2x) + (c1y - c2y) * (c1y - c2y));
    if(dist > c1r + c2r){
        cout << 4 << endl;
    }
    else if(abs(dist - c1r - c2r) < EPS){
        cout << 3 << endl;
    }
    else if(abs(dist + c1r - c2r) < EPS || (abs(dist + c2r - c1r) < EPS)){
        cout << 1 << endl;
    }
    else if(c1r > dist + c2r || c2r > dist + c1r){
        cout << 0 << endl;
    }
    else {
        cout << 2 << endl;
    }
    return 0;
}


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

typedef long long ll;
#define mod 1000000007
#define pb push_back
#define mk make_pair
#define precise(x) cout<<fixed<<setprecision(12)<<x
#define test cout<<"#";

const ll inf = 1e18L + 2;
ll dp[100001][2];
ll solve(ll s, ll constraint, ll e, vector<ll> adj[])
{
	if(dp[s][constraint]!=-1)
		return dp[s][constraint];
	ll ans = 0, w1 = 1;
	for(auto u: adj[s])
	{
		if(u!=e)
		{
			w1 = (w1*solve(u,0,s,adj))%mod;
		}
	}
	ans+=w1;
	w1 = 1;
	if(!constraint)
	{
		for(auto u: adj[s])
		{
			if(u!=e)
			{
				w1 = (w1*solve(u,1,s,adj))%mod;
			}
		}
		ans+=w1;
		ans=ans%mod;
	}
	
	return dp[s][constraint] = ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin>>n;
	vector<ll> adj[n];
	memset(dp, -1, sizeof(dp));
	for(ll x = 0; x < n-1; x++)
	{
		ll a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	cout<<solve(0,0,-1,adj);
}

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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;


int main(){
  ll n;
  cin >> n;
  vector<ll> v(n);
  rep(i, n) cin >> v[i];


  sort(all(v));


  double x = v[0];
  rep1(i, n-1){
    x += v[i];
    x /= 2.0;
  }

  cout << x << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

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

    vector<vector<ll>> fr(n,vector<ll>(0));
    vector<vector<ll>> bl(n,vector<ll>(0));

    rep(i,m){
        //fr
        ll a,b; cin >> a >> b;
        a--; b--;
        fr.at(a).push_back(b);
        fr.at(b).push_back(a);
    }

    rep(i,k){
        //bl
        ll c,d; cin >> c >> d;
        c--; d--;
        bl.at(c).push_back(d);
        bl.at(d).push_back(c);     
    }

    vector<ll> cls(n,-1);

    vector<ll> ans(n,0);
    ll groupnum = 0;
    for(int i=0;i<n;i++){
        if(cls.at(i)!=-1) continue;        
        stack<ll> q;
        vector<ll> s2(0);
        cls.at(i) = groupnum;
        s2.push_back(i);
        q.push(i);
        while(q.size()){
            ll x = q.top();
            q.pop();
            for(auto y:fr.at(x)){
                if(cls.at(y)!=-1) continue;
                s2.push_back(y);
                q.push(y);
                cls.at(y) = groupnum;
            }
        }
      
        
        //for(auto y:s2) cout << y << " "; cout << endl;
        
        for(auto y:s2){
            ll count = 0;
            ll ygroup = cls.at(y);
            for(auto ff:fr.at(y)){
                if(cls.at(ff)==ygroup) count++;
            }
            for(auto bb:bl.at(y)){
                if(cls.at(bb)==ygroup) count++;
            }
            ans.at(y) = (ll)s2.size() - 1 - count;            
        }
        groupnum++;
    }

    rep(i,n){
        cout << ans.at(i) << endl;
    }
}


Measured memory_bytes: 15732
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class D
{
	public static void Main()
	{
		int N = Int32.Parse(Console.ReadLine());
		string[] args = Console.ReadLine().Split(' ');
		int ans = 0;
		int numContErr = 0;
		for(int i = 1; i <= N; i++)
		{
			int p = Int32.Parse(args[i-1]);
			if(p == i)
			{
				numContErr++;
			}
			else
			{
				ans += (numContErr + 1)/2;  // ceiling(numContErr/2)
				numContErr = 0;
			}
		}
		ans += (numContErr + 1)/2;  // ceiling(numContErr/2)
		Console.WriteLine(ans);
	}
}





Measured memory_bytes: 16480
#include <iostream>
using namespace std;
 
struct Card{
    char suit;
    int value;
}; 
 
void bubble(struct Card A[],int n){
    for(int i=0;i<n;i++){
        for(int j=n-1;j>i;j--){
            if(A[j].value<A[j-1].value){
                Card t=A[j];
                A[j] = A[j-1];
                A[j-1] = t;
            }
        }
    }
}
 
void selection(struct Card A[],int n){
    int minj=0;
        for(int i=0;i<n;i++){
            minj=i;
            for(int j=i;j<n;j++){
                if(A[j].value<A[minj].value){
                    minj=j;
                }
            }
                Card t = A[i];
                    A[i]= A[minj];
                    A[minj] = t;
        }
}
 
bool isStabel(struct Card C1[],struct Card C2[],int n){
    for(int i=0;i<n;i++){
        if(C1[i].suit!=C2[i].suit)
        return false;
    }
    return true;
}
 
void print(struct Card A[],int n){
    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<A[i].suit<<A[i].value; 
    }
    cout<<endl;
}
 
int main(){
    Card C1[100],C2[100];
    int n;
 
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>C1[i].suit>>C1[i].value;
    }
    for(int i=0;i<n;i++){
        C2[i]=C1[i];
    }
     
    bubble(C1,n);
    selection(C2,n);
     
    print(C1,n);
    cout<<"Stable"<<endl;
     
    print(C2,n);
    if(isStabel(C1,C2,n))
    cout<<"Stable"<<endl;
    else
    cout<<"Not stable"<<endl;
     
    return 0;
}

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

using namespace std;

main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	int nr1 = 0;
	
	for(int i = 1; i <= n; i++)
	{
		if(i & 1)
			nr1++;
	}
	
	cout << nr1 * 1.0 / n;
}

Measured memory_bytes: 892
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N = int(input())

#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass #sortされていない

ans = len(divisor(N-1))-1
b = divisor(N)
for bi in b:
    if bi == 1:
        continue
    a = N
    while a >= bi:
        if a%bi == 0:
            a = a//bi
        else:
            a = a%bi
    if a == 1:
        ans += 1
print(ans)


Measured memory_bytes: 9608
import itertools
import math

n = int(input())
li = list(itertools.permutations(range(1,n+1)))
a = []
for _ in range(n):
    a.append([int(x) for x in input().split()])
ans = 0
for i in li:
    for j in range(n-1):
        x = a[i[j]-1][0]-a[i[j+1]-1][0]
        y = a[i[j]-1][1]-a[i[j+1]-1][1]
        ans += math.sqrt(x**2+y**2)
x = 1
for i in range(1,n+1):
    x *= i
print(ans/x)

Measured memory_bytes: 7972
//itp1_topic2_d

#include<bits/stdc++.h>

using namespace std;

int main(){

	int W, H;

	cin>>W>>H;

	int x, y, r;

	cin>>x>>y>>r;

	if( x-r >= 0 && y-r >= 0 && x+r <= W && y+r <= H )

      cout<<"Yes"<<endl;

	else cout<<"No"<<endl;

	return 0;

}	


Measured memory_bytes: 3120
#include <stdio.h>

int main()
{
	double t,v,y;
	int n;
	
	while(scanf("%lf",&v)!=EOF){
		t=v/9.8;
		y=4.9*t*t;
		
		for(n=1;5*(n-1)<y;n++);
		printf("%d\n",n);
	}
	
	return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define type(a) typeid(a).name();
#define pop() pop_back()
#define push(n) push_back(n)
#define print(arr) cout << "[" ;for(unsigned int i=0;i<(unsigned int) arr.size();i++){ (i==arr.size()-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl
#define Arr(arr,l) cout << "[" ;for(unsigned int i=0;i<(unsigned int) l;i++){ (i==l-1)?cout << arr[i]:cout << arr[i] << ",";}cout << "]" << endl

int main(){
   int l;
   cin >> l;
   vector<int> n(l);
   for(int i=0;i<l;++i){
	  int w;
	  cin >> w;
	  n[i] = w;   
	}
	int counting=0;
	sort(n.begin(),n.end());
	for(int i=0;i<l-2;++i)
	 for(int m = i+1;m<l-1;++m){ 
	   for(int j=m+1;j<l;++j){
		  if(n[i]+n[m] > n[j]){
			counting ++;  
		  }else{
			break;  
		   }   
		}
	  }
	cout << counting;
}  

















Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int n;
  long long sum=0,max,min,a;
  cin >> n;
  REP(i,n){
    cin >> a;
    sum+=a;
    if(i==0){
      max=a;
      min=a;
    }
    if(max<a)
      max=a;
    if(min>a)
      min=a;
  }
  cout << min <<' '<< max <<' '<< sum << endl;
}

Measured memory_bytes: 1168
module Main where

import Control.Monad
import Data.List
import Data.List.Split
import Data.Array.IO
import qualified Data.Vector as V

main :: IO ()
main = do
  s <- getLine
  print $ (maximum . map length . splitWhen (\i -> elem i "ACGT" == False)) s

solve :: [Int] -> [Int]
solve [x] = [0]
solve (a:b:cs) = b - a : (solve (b:cs))

getInt :: IO Int
getInt = read <$> getLine

getInts :: IO [Int]
getInts = map read . words <$> getLine

getIntLines :: Int -> IO [Int]
getIntLines i = replicateM i getInt

getStrLines :: Int -> IO [String]
getStrLines i = replicateM i getLine


Measured memory_bytes: 380
import sys

def main():
	n, q = map(int, sys.stdin.readline().split())
	c = list(map(int, sys.stdin.readline().split()))
	fenwick = [0] * n
	
	def add(i, v):
		while i < n:
			fenwick[i] += v
			i = (i | (i + 1))
	
	def get(r):
		res = 0
		while r >= 0:
			res += fenwick[r]
			r = (r & (r + 1)) - 1
		return res
	
	def get_seg(l, r):
		return get(r) - get(l - 1)
		
	by_r = [[] for i in range(n)]
	for t in range(q):
		l, r = map(int, sys.stdin.readline().split())
		l, r = l - 1, r - 1
		by_r[r].append((l, t))
	last_ent = [-1] * (n + 1)
	ans = [0] * q
	for r in range(n):
		p = last_ent[c[r]]
		if p != -1:
			add(p, -1)	
		last_ent[c[r]] = r
		add(r, 1)
		for quer in by_r[r]:
			l, num = quer
			ans[num] = get_seg(l, r)
	print('\n'.join([str(x) for x in ans]))
	
main()



Measured memory_bytes: 221940
N, M, K = map(int, input().split())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]

time = 0
maxBooks = 0

for i in range(N):
  if K - time >= A[i]:
    time += A[i]
    maxBooks += 1
  else:
    break

A_count = maxBooks - 1
nowBooks = maxBooks

for i in range(M):
  time += B[i]
  nowBooks += 1
  
  while K < time:
    if A_count < 0:
      nowBooks = 0
      break
    time -= A[A_count]
    A_count -= 1
    nowBooks -= 1
      
  if maxBooks < nowBooks:
    maxBooks = nowBooks
    
print(maxBooks)

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

#define rep(i, x, n) for (int i = x; i < n; i++)
typedef long long ll;

const int INF = 1e9 + 7;

using namespace std;

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

	int n;
	string s1, s2;
	cin >> n >> s1 >> s2;

	ll res = 0;
	int st = 0;
	int now; // 0:rectangle, 1:square
	if (s1[st] == s2[st]) {
		res += 3;
		st++;
		now = 0;
	} else {
		res += 6;
		st += 2;
		now = 1;
	}

	rep (i, st, n) {
		if (s1[i] == s2[i]) {
			if (now == 0)
				res = res * 2 % INF;
			else
				res = res * 1 % INF;
			now = 0;
		} else {
			if (now == 0)
				res = res * 2 % INF;
			else
				res = res * 3 % INF;
			i += 1;
			now = 1;
		}
	}

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


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
int n, w[1<<18], B[1<<18], E[1<<18], Res[1<<18];
vector<int>G[1 << 18], H[1 << 18], U[(1 << 18) + 1];
priority_queue<pii>PQ;
int main() {
	int i, a, j;
	scanf("%d", &n);
	for (i = 0; i < (1 << n); i++) {
		scanf("%d", &a);
		int s = 0;
		for (j = 0; j < n; j++) {
			s += ((i >> j) & 1) << (n - 1 - j);
		}
		w[s] = a;
	}
	for (i = 0; i < (1 << n); i++) {
		if (w[i])B[i] = E[i] = w[i];
		else B[i] = 1, E[i] = (1 << n);
		for (j = 0; j < n; j++) {
			if ((i >> j) & 1) {
				G[i ^ (1 << j)].push_back(i);
				H[i].push_back(i ^ (1 << j));
			}
		}
	}
	for (i = 0; i < (1 << n); i++) {
		for (auto &x : G[i]) {
			B[x] = max(B[i] + 1, B[x]);
		}
	}
	for (i = (1 << n) - 1; i >= 0; i--) {
		for (auto &x : H[i]) {
			E[x] = min(E[i] - 1, E[x]);
		}
	}
	for (i = 0; i < (1 << n); i++)U[B[i]].push_back(i);
	for (i = 1; i <= (1 << n); i++) {
		for (auto &t : U[i]) {
			PQ.push({ -E[t],t });
		}
		if (PQ.empty()) {
			puts("NO");
			return 0;
		}
		pii tp = PQ.top();
		if (-tp.first < i) {
			puts("NO");
			return 0;
		}
		Res[tp.second] = i;
		PQ.pop();
	}
	puts("YES");
	for (i = 0; i < (1 << n); i++)printf("%d ", Res[i]);
}

Measured memory_bytes: 66816
import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        
        int[] count = new int[26];//count[0]<->'a',...count[25]<->'z'
        
        for(int h=0;h<H;h++){
        	String line = sc.next();
        	for(int w=0;w<W;w++) count[(line.charAt(w)-'a')]++;
        }
        
        boolean ans = true;
        if(H%2==0 && W%2==0){//all chars should appear 4*k times
        	for(int i=0;i<26;i++){
        	    if(count[i]%4!=0) ans=false;
        	}
        }
        else if(H%2!=0 && W%2!=0){
        	int oddChars = 0;
        	int oddTimes2Chars = 0;
        	for(int i=0;i<26;i++){
        	    if(count[i]%2!=0) oddChars++;
        	    else if(count[i]%4!=0) oddTimes2Chars++;
        	}
        	ans = (oddChars<=1) && (oddTimes2Chars<=H/2+W/2);
        }
        else if(H%2==0 && W%2!=0){
        	int oddChars = 0;
        	int oddTimes2Chars = 0;
        	for(int i=0;i<26;i++){
        	    if(count[i]%2!=0) oddChars++;
        	    else if(count[i]%4!=0) oddTimes2Chars++;
        	}
        	ans = (oddChars==0) && (oddTimes2Chars<=H/2);
        }
        else{
        	int oddChars = 0;
        	int oddTimes2Chars = 0;
        	for(int i=0;i<26;i++){
        	    if(count[i]%2!=0) oddChars++;
        	    else if(count[i]%4!=0) oddTimes2Chars++;
        	}
        	ans = (oddChars==0) && (oddTimes2Chars<=W/2);
        }
        if(ans) System.out.println("Yes");
        else System.out.println("No");
    }
}

Measured memory_bytes: 23764
#define _USE_MATH_DEFINES
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int a[4]={0};
bool b[4]={0};
int c[4]={0};
string o[3]={" + "," - "," * "};
bool find_flag=0;

int cal(int x, int y, int z){
	switch(z){
	case 0:
		return x+y;
	case 1:
		return x-y;
	case 2:
		return x*y;
	}
	return 0;
}

void r(int n){
	if(n==4){
		int o1=0, o2=0, o3=0;
		while(1){
			//cout<<o1<<" "<<o2<<" "<<o3<<endl;
			if(o3==3){
				o2++;
				o3=0;
			}
			if(o2==3){
				o1++;
				o2=0;
			}
			if(cal(cal(cal(c[0],c[1],o1),c[2],o2),c[3],o3)==10){
				cout << "((("<<c[0]<<o[o1]<<c[1]<<")"<<o[o2]<<c[2]<<")"<<o[o3]<<c[3]<<")"<<endl;
				find_flag=1;
				return;
			//}else if(cal(cal(c[0],cal(c[1],c[2],o2),o1),c[3],o3)==10){
			}else if(cal(cal(c[0],cal(c[1],c[2],o2),o1),c[3],o3)==10){
				cout << "(("<<c[0]<<o[o1]<<"("<<c[1]<<o[o2]<<c[2]<<"))"<<o[o3]<<c[3]<<")"<<endl;
				find_flag=1;
				return;
			//}else if(cal(c[0],cal(c[1],cal(c[2],c[3],o3),o2),o1)==10){
			}else if(cal(c[0],cal(cal(c[1],c[2],o2),c[3],o3),o1)==10){
				cout << "("<<c[0]<<o[o1]<<"(("<<c[1]<<o[o2]<<c[2]<<")"<<o[o3]<<c[3]<<"))"<<endl;
				find_flag=1;
				return;
			}else if(cal(cal(c[0],c[1],o1),cal(c[2],c[3],o3),o2)==10){
				cout << "(("<<c[0]<<o[o1]<<c[1]<<")"<<o[o2]<<"("<<c[2]<<o[o3]<<c[3]<<"))"<<endl;
				find_flag=1;
				return;
			}
			o3++;
			if(o1==2 && o2==2 && o3==3){
				return;
			}
		}
	}
	for(int i=0;i<4&&!find_flag;i++){
		if(b[i]==0){
			b[i]=1;
			c[n]=a[i];
			r(n+1);
			b[i]=0;
		}
	}
}

int main(){

	while(cin >> a[0] >> a[1] >> a[2] >> a[3]){
		if(a[0]==0 && a[1]==0 && a[2]==0 && a[3]==0){
			break;
		}
		find_flag=0;
		r(0);
		if(!find_flag){
			cout << 0 << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,ans=0;
string s;
int32_t main(){
CODE_START;
cin >> s;
cin >> s;
cout<<"A"<<s[0]<<"C";
return 0;}



Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
    int x,i=1;
    while (1) {
        scanf("%d", &x);
        if (x == 0)break;
        printf("Case %d: %d\n", i,x);
        i++;
        
    }
    return 0;
}


Measured memory_bytes: 2060
#include<bits/stdc++.h>
#define ll  long long
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define pb push_back
#define Max(x,y,z) max(x,max(y,z))
#define f first
#define s second
#define lbd lower_bound
#define sz(x)       (ll)x.size()
#define pi 3.1415926536
#define mod 1000000007
using namespace std;
void solve()
{
    ll n,m,k,x,y,res=0,l,cnt=0,sum=0,z,sum1=0,cnt1=0,h,res1,cnt2=0;
   cin>>n>>m;
   vector<pair<ll,ll>> v;
   rep(i,0,n)
   {
       cin>>x>>y;
       v.pb({x,y});
   }
   sort(v.begin(),v.end());
   rep(i,0,n)
   {   if(v[i].s>m)
        {
            sum+=(v[i].f*m);
            m=0;
        }
       else if(v[i].s<=m)
       {
           sum+=(v[i].f)*(v[i].s);
           m-=v[i].s;
       }
       if(m==0)
        break;
   }
   cout<<sum;


}
int main()
{   speed_up
    ll t;
   // cin>>t;
    t=1;
    while(t--)
        solve();
}


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

using namespace std;


int main(){
    int n,ans=0;
    string name,s;
    cin>>n>>name;
    for(int i=0;i<n;++i){
        cin>>s;
        bool flag=false;
        for(int j=0;j<s.size();++j){
            if(s[j]!=name[0]) continue;
            for(int k=1;k*(name.size()-1)+j<s.size();++k){
                for(int l=1;l<name.size();++l){
                    if(s[j+k*l]!=name[l]) break;
                    if(l==name.size()-1){
                        ++ans;flag=true;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
	int N;
	cin >> N;
	std::vector<int> ds;
	
	int Num=N, i=0, a, b;
	do{
		b = N;
		N /= 10;
		a = b - 10*N;
		ds.push_back(a);
		i++;
	}while(N >= 10);
	ds.push_back(N);
	int count = i;
	
	int sum=0;
	for(i=0; i<=count; i++){
		sum += ds[i];
	}
	
	if(Num%sum==0)	cout << "Yes" << endl;
	else		cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <stack>

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimmize("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define mkt make_tuple
#define no {cout << "-1\n"; return;}

void solve() {
    string s, t;
    cin >> s >> t;
    int ans = t.size();
    for (int i = 0; i + t.size() <= s.size(); ++i) {
        int cur = 0;
        for (int j = i; j < i + t.size(); ++j)
            cur += s[j] != t[j - i];
        ans = min(cur, ans);
    }
    cout << ans;
}

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

Measured memory_bytes: 3664
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
import itertools
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,M = LMIIS()
    edges = defaultdict(list)
    for i in range(M):
        a,b = LMIIS()
        edges[a].append(b)
        edges[b].append(a)
    ans = 0
    for l in itertools.permutations(range(2,N+1), N-1):
        prev = 1
        for v in l:
            if v in edges[prev]:
                prev = v
            else:
                break
        else:
            ans += 1
    print(ans)




if __name__ == '__main__':
    main()

Measured memory_bytes: 68352
/*
[abc099] A - ABD
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

int N;

string solve() { return (N < 1000) ? "ABC" : "ABD"; }

int main() {
    cin >> N;

    cout << solve() << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        long ans = 0;
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        for (int i = 0; i < n - 1; i++) {
            long tmp2 = (i + 1) / 2;
            long tmp = a[n - 1 - ((i + 1) / 2)];
            ans += tmp;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 60428
#include<stdio.h>

int main()
{
	int n, *a, *b, c[10001];
	scanf("%d", &n);
	a = new int[n];
	b = new int[n];
	for (int i = 0; i < 10001; i++)
		c[i] = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", a + i);
		c[a[i]]++;
	}
	for (int i = 1; i < 10001; i++)
		c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--)
	{
		b[c[a[i]] - 1] = a[i];
		c[a[i]]--;
	}

	for (int i = 0; i < n; i++)
	{
		if (i)
			printf(" ");
		printf("%d", b[i]);
	}
printf("\n");

	delete[] a;
	delete[] b;

	return 0;
}


Measured memory_bytes: 17952
N, x = map(int, input().split())
l = list(map(int, input().split()))
l.append(0)
hiku_sum = 0
# print(l)
for i in range(N):
    l_sum = l[i] + l[i + 1]
    if l_sum > x:
        hiku_min = l_sum - x
        hiku_sum += hiku_min
        if l[i + 1] >= hiku_min:
            l[i + 1] -= hiku_min
        else:
            l[i] -= hiku_min - l[i + 1]
            l[i + 1] = 0
print(hiku_sum)

Measured memory_bytes: 14548
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define x first
#define y second

namespace fu
{
	const int N=55;
	typedef std::pair<int,int> pii;
	typedef long long ll;

	inline void check_min(ll a,ll &b){if(a<b)b=a;}

	bool cmp(pii A,pii B){return A.y==B.y?A.x<B.x:A.y<B.y;}

	pii s[N],t[N];
	int n,k,tot;
	ll ans;
	void initialize()
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
			scanf("%d%d",&s[i].x,&s[i].y);
		std::sort(s+1,s+n+1);
	}

	ll calc()
	{
		std::sort(t+1,t+tot+1,cmp);

		int L=1,R=1,cnt=1;
		ll ret=2147483647;
		for(;L<=tot && R<=tot;)
		{
			while(R<=tot && cnt<k)R++,cnt++;
			if(cnt>=k && R<=tot)check_min((ll)t[R].y-t[L].y,ret);
			L++,cnt--;
		}

//		printf(":%d\n",ret);
		return ret;
	}
	void solve()
	{
		initialize();
		ans=9223372036854775807ll;
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
			{
				tot=0;
				for(int x=i;x<=j;x++)
					t[++tot]=s[x];
				ll tmp=calc();
				if(tmp<2147483647)check_min(tmp*(s[j].x-s[i].x),ans);
			}
		printf("%lld\n",ans);
	}
}
int main()
{
	fu::solve();
	return 0;
}


Measured memory_bytes: 256
class Dice:
    def __init__(self,t,f,r,l,b,u):
        self.t=t
        self.f=f
        self.r=r
        self.l=l
        self.b=b
        self.u=u
    def roll(self,i):
        if d=='S':
            key=self.t
            self.t=self.b
            self.b=self.u
            self.u=self.f
            self.f=key
        elif d=='E':
            key=self.t
            self.t=self.l
            self.l=self.u
            self.u=self.r
            self.r=key
        elif d=='N':
            key=self.t
            self.t=self.f
            self.f=self.u
            self.u=self.b
            self.b=key
        else:
            key=self.t
            self.t=self.r
            self.r=self.u
            self.u=self.l
            self.l=key
t,f,r,l,b,u=map(int,input().split())
a=list(input())
dice=Dice(t,f,r,l,b,u)
for d in a:
    dice.roll(d)
print(dice.t)


Measured memory_bytes: 5608
<?php
while ($line = fgets(STDIN)) {
   $array[] = trim($line);
}
$array[0] = 999999999999999999999999999999999999;
$count =0;
sort($array);
$moti = min($array);
  for($i=0; $i<count($array); $i++){
    if($moti != $array[$i] && $moti < $array[$i]){
      $moti = $array[$i];
      $count = $count+1;
    }
  }
echo $count;
echo "\n";
?>

Measured memory_bytes: 16228
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define FOR1(i, n) FOR(i, 1, n+1)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));

#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl
#define dv(name, value) cerr << (name) << " is " << (value) << endl
#define da(v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl


signed main(){
  int N = 5;
  int sum = 0;
  vector<int> inputs(N);
  REP(x, N){
    cin >> inputs.at(x);
    sum += inputs.at(x);
  }

  vector<int> amaris(N);
  REP(x, N) {
    amaris.at(x) = 10 - (inputs.at(x) % 10 ? inputs.at(x) % 10 : 10);
  }
  sort(amaris.begin(), amaris.end());

  REP(x, N-1) sum += amaris.at(x);

  cout << sum << endl;
}


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

using namespace std;

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

    int N;
    cin >> N;

    vector<int> a(N), b(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

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

    reverse(b.begin(), b.end());
    int c = -1, l = 0, r = N-1;
    for (int i = 0; i < N; ++i) {
        if (a[i] == b[i]) {
            c = b[i];
            l = i;
            break;
        }
    }

    if (c == -1) {
        cout << "Yes" << endl;
        copy(b.begin(), b.end(), ostream_iterator<int>(cout, " "));
        return 0;
    }

    for (int i = N-1; i >= 0; --i) {
        if (a[i] == c && b[i] == c) {
            r = i;
            break;
        }  
    }

    for (int i = 0; i < N; ++i) {
        if (a[i] != c && b[i] != c && l <= r) {
            swap(b[i],b[l]);
            ++l;
        }
    }

    if (l <= r) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        copy(b.begin(), b.end(), ostream_iterator<int>(cout, " "));
    }
}

Measured memory_bytes: 4764
#include<iostream>
#include<string>
#include<cmath>
using namespace std;

int main() {
	string s;
	cin >> s;
	int a = 0, b = 0, c = 0, n = s.size();
	for (int i = 0; i < n; i++) {
		if (s[i] == 'a')a++;
		else if (s[i] == 'b')b++;
		else c++;
	}
	if (abs(a - b) <= 1 && abs(b - c) <= 1 && abs(c - a) <= 1)cout << "YES" << endl;
	else cout << "NO" << endl;
}

Measured memory_bytes: 512
from sys import stdin
from collections import deque
import heapq

def read_graph(n):
    A = [ [] for _ in range(n) ]
    for _ in range(n):
        line = deque(stdin.readline().strip().split())
        u = line.popleft()
        line.popleft()
        for l, k in enumerate(line):
            if l % 2 == 0:
                v = k
            else:
                A[int(u)].append((int(v), int(k)))
    return A

def dijkstra(n, A, s):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[s] = 0
    pq = []

    heapq.heappush(pq, (s, 0))

    while pq:
        costu, u = heapq.heappop(pq)
        color[u] = 'BLACK'

        if d[u] < costu:
            continue

        for v, costv in A[u]:
            if color[v] != 'BLACK':
                if d[u] + costv < d[v]:
                    d[v] = d[u] + costv
                    color[v] = 'GRAY'
                    heapq.heappush(pq, (d[v], v))
    return d

n = int(input())
A = read_graph(n)
for i, k in enumerate(dijkstra(n, A, 0)):
    print(i, k)


Measured memory_bytes: 68456