akhauriyash/Code-Regression huggingface dataset:
from math import pow


n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))

d1 = d2 = d3 = dm = 0
for i in range(n):
    diff = abs(x[i] - y[i])
    d1 += diff
    d2 += diff ** 2
    d3 += diff ** 3
    dm = diff if dm < diff else dm

print("{:.5f}\n{:.5f}\n{:.5f}\n{:.5f}".format(d1, pow(d2, 1 / 2), pow(d3, 1 / 3), dm))



Measured memory_bytes: 5704
#include <iostream>
#define x 51000
using namespace std;
int main(){
	bool p[x];
	for(int i=2;i<x;i++) p[i] = true;
	for(int i=2;i<x;i++){
		if(not p[i]) continue;
		for(int j=2;j<=x/i;j++) p[i*j] = false;
	}
	int n;
	while(cin >> n){
		for(int i=n-1;i>1;i--){
			if(not p[i]) continue;
			cout << i << " ";
			break;
		}
		for(int i=n+1;i<x;i++){
			if(not p[i]) continue;
			cout << i << endl;
			break;
		}
	}
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n, C;
    cin >> n >> C;

    vector<vector<int64_t>> d(C, vector<int64_t>(C));
    for (auto i : irange(0L, C)) {
        for (auto j : irange(0L, C)) {
            cin >> d[i][j];
        }
    }

    array<vector<int64_t>, 3> c{vector<int64_t>(C), vector<int64_t>(C),
                                vector<int64_t>(C)};
    for (auto i : irange(0L, n)) {
        for (auto j : irange(0L, n)) {
            int64_t cc;
            cin >> cc;
            --cc;

            ++c[(i + j) % 3][cc];
        }
    }

    array<vector<int64_t>, 3> dis{vector<int64_t>(C), vector<int64_t>(C),
                                  vector<int64_t>(C)};
    for (auto i : irange(0L, 3L)) {
        for (auto j : irange(0L, C)) {
            for (auto k : irange(0L, C)) {
                dis[i][j] += d[k][j] * c[i][k];
            }
        }
    }

    int64_t ans = numeric_limits<int64_t>::max();
    for (auto c0 : irange(0L, C)) {
        for (auto c1 : irange(0L, C)) {
            if (c0 == c1) {
                continue;
            }
            for (auto c2 : irange(0L, C)) {
                if (c0 == c2 || c1 == c2) {
                    continue;
                }

                auto t = dis[0L][c0] + dis[1L][c1] + dis[2L][c2];
                ans = min(t, ans);
            }
        }
    }

    cout << ans << endl;
}

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


int main() {
  string s;
  cin >> s;
  int n = s.size();
  cout << s[0] << n-2 << s[n-1]<< endl; 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
		
int main() {
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++){
		if(s[i]=='1')s[i]='9';
		else if(s[i]=='9')s[i]='1';
	}
	cout<<s<<endl;
}



			
     

         
            


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

const int _ = 5003 , MOD = 1e9 + 7;
struct Edge{int end , upEd;}Ed[_ << 1];
int match[_] , N , cntEd , head[_];

void addEd(int a , int b){Ed[++cntEd] = (Edge){b , head[a]}; head[a] = cntEd;}

int sz[_] , dp[_][_] , tmp[_];
void dfs(int x , int p){
	dp[x][sz[x] = 1] = 1;
	for(int i = head[x] ; i ; i = Ed[i].upEd)
		if(Ed[i].end != p){
			int t = Ed[i].end; dfs(t , x); memset(tmp , 0 , sizeof(tmp));
			for(int j = 1 ; j <= sz[x] ; ++j)
				for(int k = 1 ; k <= sz[t] ; ++k){
					tmp[j + k] = (tmp[j + k] + 1ll * dp[x][j] * dp[t][k]) % MOD;
					tmp[j] = (tmp[j] + MOD - 1ll * dp[x][j] * dp[t][k] % MOD * match[k] % MOD) % MOD;
				}
			sz[x] += sz[t]; memcpy(dp[x] , tmp , sizeof(tmp));
		}
}

int main(){
	cin >> N;
	for(int i = 1 ; i < N ; ++i){int x , y; cin >> x >> y; addEd(x , y); addEd(y , x);}
	match[0] = 1; for(int i = 2 ; i <= N ; i += 2) match[i] = match[i - 2] * (i - 1ll) % MOD;
	dfs(1 , 0); int sum = 0;
	for(int i = 1 ; i <= N ; ++i) sum = (sum + 1ll * dp[1][i] * match[i]) % MOD;
	cout << sum; return 0;
}

Measured memory_bytes: 98560
#include <iostream>
#include <algorithm>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

int N, Y;

int main() {
  cin >> N >> Y;

  int x = -1, y = -1, z = -1;

  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N - i; ++j) {
      if (10000 * i + 5000 * j + 1000 * (N - i - j) == Y) {
        x = i, y = j, z = N - i - j;
        cout << x << " " << y << " " << z << endl;
        return 0;
      }
    }
  }

  cout << x << " " << y << " " << z << endl;

  return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;

public class Main{
	public static void main(String args[]) throws IOException {
		Scanner scan = new Scanner(System.in);
		int Ans = 0;
		int N = scan.nextInt();
		int[] P = new int[N];
		
		//標準入力からの格納
		for(int i = 0; i < N;i++) {
			P[i] = scan.nextInt();
		}
		
		for(int i = 0;i <= P[0];i++){
			//左端の処理
			int ans = i;
			
			int nextS = P[0] - i;
			
			//全体の処理
			for(int cursor = 0;cursor < N - 1;cursor++) {
				ans += nextS * 2;
				nextS = P[cursor + 1] - nextS;
				if(nextS < 0) {
					nextS = 0;
				}
			}
			
			//右端の処理
			if(nextS > 0) {
				ans += nextS;
			}
			
			if(i == 0 || Ans > ans) {
				Ans = ans;
			}
		}
		

		System.out.println(Ans);
		
		scan.close();
	}
}


Measured memory_bytes: 36092
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)

	s := getString()
	n := len(s)
	ans := 0
	for i := 0; i < n/2; i++ {
		if s[i] != s[n-1-i] {
			ans++
		}
	}
	out(ans)
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;
//const int INF=(1<<30);


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  REP(i,n)cin>>a[i];

  sort(ALL(a));
  cout << a[n-1] - a[0] << endl; 

}




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

void solve()
{
    long double a, b, h, m;
    cin >> a >> b >> h >> m;

    m += h*60;
    long double s = m*5.5;

    while(s-360>0)
    {
        s -= 360;
    }
    s *= PI/180.0;
    long double ans = sqrt(a*a+b*b-2*a*b*cos(min(s, 2*PI-s)));

    cout << fixed << showpoint;
    cout << setprecision(20);
    cout << ans << endl;
}


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


Measured memory_bytes: 4148
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    ll n;
    scanf("%lld", &n);
    for (ll i = floor(sqrt(n)); i >= 1; --i) if (n % i == 0) {
        printf("%lld\n", max(ll(floor(log10(i))), ll(floor(log10(n / i)))) + 1);
        return 0;
    }
    return 0;
}


Measured memory_bytes: 384
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int size = 0, value[100000], parents[100000];
bool ignore[100000], is_mark[100000], is_root[100000];

class union_find {
private:
	vector<int> uf;

public:
	union_find(int n) {
		uf.resize(n, -1);
	}

	inline int find(int x) {
		return uf[x] < 0 ? x : uf[x] = find(uf[x]);
	}

	inline void unite(int child, int parent) {
		uf[child] = find(parent);
	}

	inline bool same(int x, int y) {
		return find(x) == find(y);
	}
};

inline void push(int x) {
	value[size++] = x;
}

inline int pop() {
	return value[--size];
}

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

	for(int n, q; cin >> n >> q, n | q;) {
		for(int i = 1; i < n; ++i) {
			cin >> parents[i];
			--parents[i];
		}

		memset(is_root, false, sizeof(is_root));
		memset(ignore, false, sizeof(ignore));
		is_root[0] = true;

		for(int i = 0; i < q; ++i) {
			char ope;
			int v;
			cin >> ope >> v;
			push(--v);
			if(ope == 'Q')
				is_mark[i] = false;

			else {
				is_mark[i] = true;
				if(is_root[v])
					ignore[i] = true;
				else
					is_root[v] = true;
			}
		}

		union_find uf(n);
		for(int i = 1; i < n; ++i)
			if(!is_root[i])
				uf.unite(i, parents[i]);

		long long ans = 0;
		for(int i = q - 1; i >= 0; --i) {
			int v = pop();

			if(is_mark[i]) {
				if(!ignore[i])
					uf.unite(v, parents[v]);
			}
			else
				ans += uf.find(v) + 1;
		}

		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 2680
// 2020-08-31 21:49:12
// clang-format off
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

// clang-format on
void answer() {
  ll n, a, b;
  cin >> n >> a >> b;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];
  ll l = 0, r = 1e9;
  while (l + 1 < r) {
    ll x = (l + r) / 2;
    ll y = 0;
    rep(i, n) y += (max(0ll, h[i] - b * x) + a - b - 1) / (a - b);
    if (y <= x)
      r = x;
    else
      l = x;
  }
  cout << r << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 3988
N = int(input())

A = list(map(int, input().split()))

flag = 1
cnt = 0

while flag:
    flag = 0
    for j in range(1, N):
        if A[j] < A[j-1]:
            A[j], A[j-1] = A[j-1], A[j]
            cnt += 1
            flag = 1

print(' '.join(map(str,A)))
print(cnt)


Measured memory_bytes: 5600
while True:
	a,b,c=map(int,input().split())
	if a==-1 and b==-1 and c==-1:
		break
	elif a==-1 or b==-1:
		print("F")
	elif a+b >= 80:
		print("A")
	elif a+b>=65:
		print("B")
	elif a+b>=50 or c>=50:
		print("C")
	elif a+b>=30:
		print("D")
	elif a+b<30:
		print("F")


Measured memory_bytes: 5592
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = n; i < 1000; i++) {
            if (i % 111 == 0) {
                System.out.println(i);
                return;
            }
        }
    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <limits>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
constexpr lnt INF = 2e18;
/*-*/

template <typename T = lnt, T INF = std::numeric_limits<T>::max()>
struct Dinic
{
	struct Edge
	{
		int a,b; T c,f;
		Edge(int a, int b, T c) : a(a),b(b),c(c),f(0) {}
	};
	int n,m;
	std::vector<Edge> E;
	std::vector<std::vector<int> > G,Gf;
	Dinic(int n) : n(n),m(0),G(n),Gf(n) {}
	void add_edge(int i, int j, int c) {
		E.emplace_back(i,j,c);
		E.emplace_back(j,i,0);
		G[i].emplace_back(m++);
		G[j].emplace_back(m++);
	}
	bool bfs(int s, int t) {
		Gf.assign(n,std::vector<int>());
		std::queue<int> que; que.emplace(s);
		std::vector<int> dist(n,-1); dist[s]=0;
		while(!que.empty()) {
			int i=que.front(); que.pop();
			for(int to:G[i]) {
				if(dist[E[to].b]!=-1 || E[to].c==E[to].f) continue;
				dist[E[to].b]=dist[E[to].a]+1;
				que.emplace(E[to].b);
			}
		}
		if(dist[t]==-1) return false;
		for(int i=0;i<m;i++) {
			if(dist[E[i].a]+1!=dist[E[i].b] || E[i].c==E[i].f) continue;
			Gf[E[i].a].emplace_back(i);
		}
		return true;
	}
	T dfs(int i, T a_f, const int& t) {
		if(i==t || a_f==0) {
			return a_f;
		}
		T v_f=0;
		for(int to:Gf[i]) {
			T f=dfs(E[to].b,std::min(a_f-v_f,E[to].c-E[to].f),t);
			E[to].f+=f;
			E[to^1].f-=f;
			v_f+=f;
			if(a_f==v_f) break;
		}
		return v_f;
	}
	T flow(int s, int t) {
		T max_flow=0;
		while(bfs(s,t)) {
			T f = dfs(s,INF,t);
			if(f==0) break;
			max_flow+=f;
		}
		return max_flow;
	}
};

int main() {
	int h,w;
	std::cin >> h >> w;
	std::vector<std::string> g(h);
	rep(i,h) std::cin >> g[i];
	std::vector<std::vector<int> > X(h),Y(w);
	int sx,sy,tx,ty;
	rep(i,h) {
		rep(j,w) {
			if(g[i][j]=='o'||g[i][j]=='S'||g[i][j]=='T') {
				if(g[i][j]=='S') {
					sx=i; sy=j;
				}
				if(g[i][j]=='T') {
					tx=i; ty=j;
				}
				X[i].emplace_back(j);
				Y[j].emplace_back(i);
			}
		}
	}
	if(sx==tx||sy==ty) {
		print(-1);
		return 0;
	}
	auto enc = [&] (int i, int j) {
		return i*w+j;
	};
	debug(sx,sy,tx,ty);
	Dinic<int> flow(2*h*w);
	rep(i,h) {
		for(auto y1:X[i]) for(auto y2:X[i]) {
			if(y1==y2) continue;
			flow.add_edge(enc(i,y1),h*w+enc(i,y2),1);
		}
	}
	rep(i,w) {
		for(auto x1:Y[i]) for(auto x2:Y[i]) {
			if(x1==x2) continue;
			flow.add_edge(enc(x1,i),h*w+enc(x2,i),1);
		}
	}
	rep(i,h) rep(j,w) flow.add_edge(enc(i,j)+h*w,enc(i,j),1);
	print(flow.flow(enc(sx,sy),enc(tx,ty)+h*w));
}


Measured memory_bytes: 85084
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

#define LEN(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vpii = vector<pii>;

template<typename T, typename M = __gnu_pbds::null_type>
using ordered_set = __gnu_pbds::tree<T, M, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;

inline int fcmp(double x, double y)
{ return (x < y + EPS ? (x < y - EPS ? -1 : 0) : 1);}

struct segtree
{
    vector<ll> t;
    int n;
    segtree(int _n) : n(_n)
    {
        t.assign(4 * n, 0);
    }

    void update(int node, int l, int r, int p, ll v)
    {
        if(p < l || p > r) return;

        if(l == r)
        {
            t[node] = v;
            return;
        }

        int mid = (l + r) / 2;
        update(2 * node, l, mid, p, v);
        update(2 * node + 1, mid + 1, r, p, v);
        t[node] = max(t[2 * node], t[2 * node + 1]);
    }

    ll query(int node, int l, int r, int ql, int qr)
    {
        if(qr < l || ql > r) return 0;

        if(l >= ql && qr >= r)
            return t[node];

        int mid = (l + r) / 2;
        ll a = query(2 * node, l, mid, ql, qr);
        ll b = query(2 * node + 1, mid + 1, r, ql, qr);
        return max(a, b);
    }
};

const int N = 2e5 + 10;
int h[N], a[N], n;

int main()
{
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    
    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> h[i];

    ll ans = 0;

    segtree seg(n + 1);

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

        ll best = seg.query(1, 0, n, 0, h[i] - 1);
        ans = max(ans, best + a[i]);
        seg.update(1, 0, n, h[i], best + a[i]);
    }


    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <stdio.h>
#include <list>

using namespace std;

//#define EPS (1e-10)
//
//struct Point{
//    Point(double _x = 0, double _y = 0){
//        x = _x;
//        y = _y;
//    }
//    double x;
//    double y;
//
//    Point operator + (Point p){
//        return Point(x + p.x, y+ p.y);
//    }
//
//    Point operator - (Point p){
//        return Point(x - p.x, y - p.y);
//    }
//
//    Point operator * (double a){
//        return Point(a * x, a * y);
//    }
//
//    Point operator / (double a){
//        return Point(x / a, y / a);
//    }
//
//    double abs(){
//        return sqrt(norm());
//    }
//
//    double norm(){
//        return x * x + y * y;
//    }
//
//    bool operator < (const Point &p) const{
//        return x!=p.x ? x < p.x : y < p.y;
//    }
//
//    bool operator == (const Point &p) const{
//        return fabs(x - p.x) && fabs(y - p.y) < EPS;
//    }
//
//};
//
//typedef Point Vector;
//
//double dot(Vector a, Vector b){
//    return a.x * b.x + a.y * b.y;
//}

int main() {

    string s; cin >> s;
    string t; cin >> t;

    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
    

    if(s < t){
        printf("Yes");
    }else{
        printf("No");
    }

    return 0;

}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        
        if (h == 1 || w == 1) {
            System.out.println(1);
            return;
        }
        
        long ans = (long) h * w;
        if (ans % 2 == 1) {
            ans++;
        }
        
        System.out.println(ans / 2);
    }
}


Measured memory_bytes: 21844
def resolve():
    N = int(input())
    # A = list(input().replace(" ", "")) -> WA
    A = input().split() # -> AC
    import collections
    counter = collections.Counter(A)
    if N % 2 == 1:
        if counter["0"] != 1:
            print("0")
            return
        for k, v in counter.items():
            if k == "0":
                continue
            if int(k) % 2 == 1:
                print("0")
                return
            if v != 2:
                print("0")
                return
    else:
        for k, v in counter.items():
            if int(k) % 2 == 0:
                print("0")
                return
            if v != 2:
                print("0")
                return
    
    print( (2**(N//2)) % (10**9+7) )




if '__main__' == __name__:
    resolve()



Measured memory_bytes: 15084
#include <bits/stdc++.h>
using namespace std;
#define modulo 998244353
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000000000000



int main(){
	
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	
	if(A+B>C+D){
		cout<<"Left"<<endl;
	}
	else if(A+B<C+D){
		cout<<"Right"<<endl;
	}
	else{
		cout<<"Balanced"<<endl;
	}
	
	
	
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
frontiers = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in frontiers.keys():
    frontiers[a] = min(frontiers[a], b)
  else:
    frontiers[a] = b

cuts = 0
frontier = 10**6

for i in range(1, n):
  if i in frontiers.keys():
    frontier = min(frontier, frontiers[i])
  if i + 1 == frontier:
    cuts += 1
    frontier = 10**6
    
print(cuts)


Measured memory_bytes: 17892
#include <array>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <limits>

using namespace std;

int64_t decode(int64_t target)
{
    constexpr static std::array<int64_t, 4> table = { 0, 3, 5, 7 };

    array<bool, 4> visited;
    fill(visited.begin(), visited.end(), false);

    int64_t v = 1;

    int64_t ans = 0;
    while (target > 0)
    {
        const int64_t digit = target % 4;
        target /= 4;
        ans += v * table[digit];
        v *= 10;
        visited[digit] = true;
    }
    if (!visited[0] && visited[1] && visited[2] && visited[3])
    {
        return ans;
    }
    else
    {
        return numeric_limits<int64_t>::max();
    }
}

int main()
{
    int64_t n;
    cin >> n;

    const int64_t target = pow<int64_t>(4, 10);
    int64_t counter = 0;
    for (int64_t i = 0; i < target; i++)
    {
        const int64_t number = decode(i);
        if (number <= n)
        {
            counter++;
        }
    }
    cout << counter << endl;
}

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

#define fi first
#define se second
#define pb push_back
#define int long long
#define all(x) (x).begin(), (x).end()

using LL = long long;
using LD = long double;
using pii = pair<int, int>;
using vii = vector<pii>;

const int INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

int32_t main() {
    //ios::sync_with_stdio(false); cin.tie(nullptr);

    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = a[n-1] - a[0];
    for (int i = 1; i < n; i++) {
    
        ans = min(ans, k - (a[i] - a[i - 1]));
    }   
    cout << ans;
}

Measured memory_bytes: 1792
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        System.out.println(lcm(a,b));
    }

    private static long lcm(long a, long b)
    {
        return a * (b / gcd(a, b));
    }

    private static long gcd(long a, long b)
    {
        while (b > 0)
        {
            long temp = b;
            b = a % b; // % is remainder
            a = temp;
        }
        return a;
    }

}



Measured memory_bytes: 25172
def func(s):
    n = len(s)//2
    left = s[:n]
    right = s[n:]
    if left == right:
        return True
    else:
        return False

s = list(input())
m = len(s)
for i in range(2,m,2):
    if func(s[:m-i]):
        print(m-i)
        break

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,m,n) for(int i=m;i<n;i++)
#define endre getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define INF 1000000007
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
signed main() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	rep(i, s.size()) {
		if (s[i] == '0')a++;
		else b++;
	}
	cout << min(a, b) * 2 << endl;
}

Measured memory_bytes: 512
//
//  main.c
//  AIZU_ONLINE
//
//  Created by 郷田将 on 2018/02/07.
//  Copyright © 2018年 郷田将. All rights reserved.
//

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int a,b,c;
    int one,two,three;
    
    scanf("%d %d %d",&a,&b,&c);
    
    if(a>b && a>c)
    {
        one = a;
        if(b > c)
        {
            two = b;
            three = c;
        }
        else
        {
            two = c;
            three = b;
        }
    }
    else if(b > c)
    {
        one = b;
        if(c > a)
        {
            two = c;
            three = a;
        }
        else
        {
            two = a;
            three = c;
        }
    }
    else
    {
        one = c;
        if( a > b)
        {
            two = a;
            three = b;
        }
        else
        {
            two = b;
            three = a;
        }
    }
    
    printf("%d %d %d",three,two,one);
    printf("\n");
    
    return 0;
}



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

using namespace std;

int main(){
	int N,M;
	cin >> N >> M;
	long long int a,b;
	vector<pair<long long int,long long int>> pairs(N);

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

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

	long long int money=0;
	for(int i=0;i<N;i++){
		if(M>=pairs[i].second){
			M-=pairs[i].second;
			money+=pairs[i].first * pairs[i].second;
			if(M==0){
				cout << money << endl;
				return 0;
			}
		}else{
			money+=M*pairs[i].first;
			cout << money << endl;
			return 0;
		}
	}
	return 0;
}



Measured memory_bytes: 1792
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

int main(){
    int N;
    cin >> N;
    map<long long int, long long int> m;
    for(int i = 0; i < N; i++){
        long long int a;
        cin >> a;
        m[a] += 1;
    }
    if(m.size() == 1 && m.find(0) != m.end()){
        cout << "Yes" << endl;
        return 0;
    }
    if(N % 3 != 0){
        cout << "No" << endl;
        return 0;
    }
    if(m.size() == 2 && m.find(0) != m.end() && m[0] == N / 3){
        cout << "Yes" << endl;
        return 0;
    }
    if(m.size() == 3){
        vector<long long int> v;
        for(auto x : m){
            v.push_back(x.first);
            if(x.second != N / 3){
                cout << "No" << endl;
                return 0;
            }
        }
        if((v[0] ^ v[1]) == v[2]){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
        return 0;
    }
    cout << "No" << endl;
    return 0;
}

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

using namespace std;

int pow(int x, int n){
    if (n==0) return 1;
    if (n==1) return x;
    int half = pow(x, n/2);
    if (n%2==0){
        return half * half;
    }else{//n%2==1
        return half * half * x;
    }
}

int main(){
    int X;
    cin >> X;
    for(int A=-118; A<=119; A++){
        for(int B=-119; B<=118; B++){
            if (pow(A,5) - pow(B,5)==X){
                cout << A << " " << B << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3592
import itertools

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
P_t = tuple(P)
Q_t = tuple(Q)

li = []
for i in range(N):
    li.append(i+1)
l2 = list(itertools.permutations(li))

gap = abs(l2.index(P_t) - l2.index(Q_t))
print(gap)


Measured memory_bytes: 8052
K = int(input())

a = 1
b = 0

def snk(n):
    s = 0
    for i in str(n):
        s += int(i)
    return(n/s)
    
count = 0
while True:
    print(a)
    count += 1
    if snk(a + 10 ** b) > snk(a + 10 ** (b + 1)):
        b += 1
    a += 10 ** b
    if count == K:
        break

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

int main(){
  ll N, M;
  cin >> N >> M;
  
  priority_queue<ll> que;
  for(int i=0; i<N; i++){
    ll A; cin >> A;
    que.push(A);
  }
  
  for(int i=0; i<M; i++){
    ll b = que.top(); que.pop();
    que.push(b/2);
  }
  
  ll res = 0;
  while(!que.empty()) res += que.top(), que.pop();
  cout << res << endl;
  
  return 0;
}


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

typedef long long ll;
ll n, k, s;
int main()
{
	int i;
	cin >> n >> k;
	for (i = k + 1; i <= n; i++)
		s += n / i * (i - k) + max(0LL, (n % i > 0) * (n % i - max(0LL, k - 1)));
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    ll x = n;
    if(n>=b-1) x = b-1;
    ll ans = (a*(x%b)-a*(x%b)%b)/b;
    cout<<ans<<endl;
    return 0;
}

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

public class Main {
    static long mod = (long)1e9+7;
    public static void main(String[] args) {

        FastScanner sc = new FastScanner();
        int h = sc.nextInt();
        int w = sc.nextInt();
        long[][] dp = new long[h+1][w+1];
        char ch[][] = new char[h][w];
        for(int i = 0; i<h;i++){
            ch[i] = sc.next().toCharArray();
        }

        for(int i = 0; i<h; i++)
            if(ch[i][0]=='#')
                break;
            else
                dp[i][0] = 1;

        for (int i = 0; i < w; i++)
            if (ch[0][i] == '#')
                break;
            else
                dp[0][i] = 1;

        for(int i = 1;i<h;i++){
            for(int j = 1; j<w;j++){
                if(ch[i][j]=='#')
                    dp[i][j]=0;
                else    
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                dp[i][j]%=mod;
            }
        }
        System.out.println(dp[h-1][w-1]);
    }

    static final Random random = new Random();

    static void sort(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int val = random.nextInt(n);
            int cur = a[i];
            a[i] = a[val];
            a[val] = cur;
        }
        Arrays.sort(a);
    }

    static void sortl(long[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int val = random.nextInt(n);
            long cur = a[i];
            a[i] = a[val];
            a[val] = cur;
        }
        Arrays.sort(a);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}


Measured memory_bytes: 49236
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;

const int maxn=1e5+5;
struct node{
    long long a,b;
};

bool cmp (node x,node y){
    return x. a< y.a;
}

int main() {
   long long n,k,temp=0;
   cin >> n >> k;
   struct node s[maxn];
   //unsigned long long a,b;
   for(long long i=1; i <= n; i++) {
       scanf("%lld%lld",&s[i].a,&s[i].b);
       //scanf("%lld%lld",&a,&b);
       //temp+=b;
       //if(temp >= k)
           //break;
   }
   sort(s+1,s+1+n,cmp);
   int i;
   for(i=1;i <= n; i++){
       temp+=s[i].b;
       if(temp >= k)
           break;
   }
   cout << s[i].a << endl;
   //sort(s+1,s+1+n,cmp);
   return 0;
}

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

#define ll long long
#define ull unsigned long long
#define mii make_pair<int, int>
#define mll make_pair<ll, ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define all(v) (v).begin(), (v).end()

ofstream out("debug.txt");

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

    int ac = 0, wa = 0, tle = 0, re = 0;
    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; ++i)
    {
        cin >> s;
        if (s == "AC")
            ac++;
        else if (s == "WA")
            wa++;
        else if (s == "TLE")
            tle++;
        else
            re++;
    }
    cout << "AC x " << ac << '\n'
         << "WA x " << wa << '\n'
         << "TLE x " << tle << '\n'
         << "RE x " << re << '\n';
}

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

//https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(int a = 0;a < n;a++)
#define repi(a,b,n) for(int a = b;a < n;a++)

const ull mod = (ull)1e9 + 7;

int main(void)
{
	ll n;
	cin >> n;
	vector<ll> vs(n);
	rep(i, n)cin >> vs[i];
	ll p = vs[0];
	ll c = 1;
	for (int i = 1; i < n; i++) {
		if (vs[i] <= p) {
			c++;
			p = vs[i];
		}
	}
	cout << c << endl;
	return 0;
}


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

int main(){
  int H,W;
  cin >> H >> W;
  vector<vector<bool>> V(H,vector<bool>(W,false));
  for(int i=0;i<H;i++){
    string s;
    cin >> s;
    for(int j=0;j<W;j++){
      if(s[j]=='#') V[i][j] = true;
    }
  }
  
  vector<vector<int>> A(H,vector<int>(W,10000));
  if(V[0][0]==true) A[0][0] = 1;
  else A[0][0] = 0;
  for(int i=1;i<=H+W-2;i++){
    for(int x=0;x<=i;x++){
      int y = i-x;
      if(x>=H || y>=W) continue;
      
      if(x!=0){
        int n=0;
        if(V[x-1][y]==false && V[x][y]==true) n++;
        A[x][y] = min(A[x][y],A[x-1][y]+n);
      }
      if(y!=0){
        int n=0;
        if(V[x][y-1]==false && V[x][y]==true) n++;
        A[x][y] = min(A[x][y],A[x][y-1]+n);
      }
    }
  }
  
  cout << A[H-1][W-1] << endl;
  return 0;
}


Measured memory_bytes: 256
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.sort()
y.sort()
if((X < x[-1] + 1 <= Y) and (X < y[0] <= Y) and (x[-1] + 1 <= y[0])):
    print("No War")
else:
    print("War")

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

bool f(char ch){
  if(ch=='a')return true;
  if(ch=='i')return true;
  if(ch=='u')return true;
  if(ch=='e')return true;
  if(ch=='o')return true;
  return false;
}

int n;
string t[50];

bool check(int k){
  map<string,bool> mp;
  for(int i=0;i<n;i++){
    string s=t[i];
    string tmp="";
    for(int j=0;j<(int)s.size();j++){
      if(j==0 || f(s[j-1])){
        tmp.push_back(s[j]);
      }
    }
    if((int)tmp.size()>k){
      tmp=tmp.substr(0,k);
    }
    if(mp[tmp])return false;
    mp[tmp]=true;
  }
  return true;
}

int solve(){
  for(int i=1;i<=50;i++)
    if(check(i))return i;
  return -1;
}

int main(){
  while(1){
    cin>>n;
    if(n==0)break;
    for(int i=0;i<n;i++){
      cin>>t[i];
    }
    cout<<solve()<<endl;
  }
  return 0;
}

Measured memory_bytes: 1240
import java.util.*;

public class Main{
  public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
   int a = sc.nextInt();
   int b = sc.nextInt();
   int c = sc.nextInt();
   int k = sc.nextInt();
   int max = a;
   int maxindex = 0;
   int[] num = new int[]{a, b, c};
    for(int i = 1; i < num.length; i++){
      int j = num[i];
      if(max < num[i]){
        max = j;
        maxindex = i;
      }
    }
    for (int i = 0; i < k; i++ ) {
      max = max * 2;
    }
    if(maxindex == 0){
      System.out.println(max + b + c);
    }else if(maxindex == 1){
      System.out.println(a + max + c);
    }else{
      System.out.println(a + b + max);
    }
  }
}


Measured memory_bytes: 21716
#include <iostream>

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }
    bool operator<(const ModInt& b) const { return val < b.val; }
    bool operator<=(const ModInt& b) const { return val <= b.val; }
    bool operator>(const ModInt& b) const { return val > b.val; }
    bool operator>=(const ModInt& b) const { return val >= b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept {
        lint v;
        is >> v;
        x = v;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1000000007;
using mint = ModInt<MOD>;

void solve() {
    int n;
    std::cin >> n;
    std::cout << mint(10).pow(n) - mint(9).pow(n) * 2 + mint(8).pow(n) << "\n";
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3644
if __name__ == '__main__':
    while 1:
        w,h = list(map(int,input().strip().split()))
        if w == h ==0:break
        imap = [list(map(int,input().strip().split())) for _ in range(h)]
        visited = []
        count = 0
        for j in range(h):
            for i in range(w):
                stack =[]
                if not (j,i) in visited and imap[j][i] == 1:
                    count +=1
                    stack.append((j,i))
                    visited.append(((j,i)))
                while len(stack) !=0:
                    y,x = stack.pop()
                    if y>0 and imap[y-1][x] == 1 and not (y-1,x) in visited:
                        visited.append((y-1,x))
                        stack.append((y-1,x))
                    if x>0 and imap[y][x-1] == 1 and not (y,x-1) in visited:
                        visited.append(((y,x-1)))
                        stack.append((y,x-1))
                    if y>0 and x>0 and imap[y-1][x-1] == 1 and not (y-1,x-1) in visited:
                        visited.append((y-1,x-1))
                        stack.append((y-1,x-1))
                    if y>0 and x<w-1 and imap[y-1][x+1] ==1 and not (y-1, x+1) in visited:
                        visited.append((y-1, x+1))
                        stack.append((y-1, x+1))
                    if y <h-1 and x>0 and imap[y+1][x-1] ==1 and not (y+1,x-1) in visited:
                        visited.append((y+1,x-1))
                        stack.append((y+1,x-1))
                    if y < h-1 and x < w-1 and imap[y+1][x+1] ==1and not (y+1,x+1) in visited:
                        visited.append((y+1,x+1))
                        stack.append((y+1,x+1))
                    if y < h-1 and imap[y+1][x]== 1 and not (y+1,x) in visited:
                        visited.append((y+1,x))
                        stack.append((y+1,x))
                    if x < w-1 and imap[y][x+1] == 1 and not (y,x+1) in visited:
                        visited.append((y,x+1))
                        stack.append((y,x+1))
        print(count)

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

int main() {
	vector<int> a(3), b(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(begin(a), end(a));
	int m = 0;
	while (a[0] % 2 == 0 && a[1] % 2 == 0 && a[2] % 2 == 0) {
		m++;
		b[0] = (a[1] + a[2]) / 2;
		b[1] = (a[2] + a[0]) / 2;
		b[2] = (a[0] + a[1]) / 2;
		sort(begin(b), end(b));
		if (equal(cbegin(a), cend(a), cbegin(b))) {
			m = -1;
			break;
		}
		a = b;
	}
	cout << m << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=1e5+10;
struct t{
    int m;
    int s;
    void operator +=(const t &a){
        m+=a.m;
        s+=a.s;
        pull();
        return ;
    }
    void pull(){
        m+=s/60;
        s%=60;
        return ;
    }
    void in(){
        scanf("%d%d",&m,&s);
        return ;
    }
};
t a[N];
int f[N];
bool cmp(const int &l,const int &r){return a[l].m==a[r].m?a[l].s<a[r].s:a[l].m<a[r].m;}
int main(){
    int n,s[N];
    t temp;
    while(true){
        scanf("%d",&n);
        if(n==0)return 0;
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
            f[i]=i;
            a[i].in();
            for(int j=0;j<3;j++){
                temp.in();
                a[i]+=temp;
            }
        }
        sort(f,f+n,cmp);
        printf("%d\n%d\n%d\n",s[f[0]],s[f[1]],s[f[n-2]]);
    }
}


Measured memory_bytes: 2792
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;
const int INF=1001001001;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  string s;
  cin>>s;
  int n=s.size();
  stack<char>k;
  for(int i=0;i<n;i++){
    if(k.empty()){k.push(s[i]);}
    else if(s[i]=='T'&&k.top()=='S'){k.pop();}
    else{k.push(s[i]);}
  }
  cout<<k.size()<<endl;
  return 0;  
}

Measured memory_bytes: 3812
#include <iostream>

using namespace std;

int main(){
	int w,h,x,y,r;
	cin>>w>>h>>x>>y>>r;
	if (x>=r && x<=w-r && y>=r && y<=h-r){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
/*
 KUNAL RAUT (ZUKONIT14)  :- "DO WHAT YOU LIKE!"
 -PICT,PUNE! :)
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
#define mod9 1000000009
#define pi 3.1415926535
#define MAXN 1000001
#define N 1000001
#define MAX2N 1*1000 + 10
#define all(v) v.begin(), v.end()
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define forci(p,n) for(ll i=p;i<(ll)n;i++)
#define forcj(p,n) for(ll j=p;j<(ll)n;j++)
#define bolt ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a) __builtin_popcount(a)
#define test ll t;cin>>t;while(t--)
ll zero=0;
ll one=1;
ll gcd(ll a,ll b){    if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) {    return (a/gcd(a,b)*b);}
ll expo(ll x, ll y) {ll res=1;x=x%mod;while(y>0){if(y&1)res=(1ll*res*x)%mod;
    y=y>>1;x=(1ll*x*x)%mod;} return res;}
ll ncr(ll n,ll r){ ll res=1; if(r>n-r)r=n-r; for(ll i=0;i<r;i++) {  res*=n-i;  res/=i+1; } return res;}
ll max(ll a,ll b){return (a>b)?a:b;}
bool prime(ll n){ll i;for(i=2;i<=sqrt(n);i++){if(n%i==0)return false;}return true;}
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b)
{   if(a.second == b.second)
    return a.first < b.first;
    return (a.second < b.second);}

//https://www.youtube.com/watch?v=WTJSt4wP2ME

ll rr[]={0,1,1,1,0,-1,-1,-1,};
ll cc[]={1,1,0,-1,-1,-1,0,1};

signed main()
{
    bolt;
    string s,t;cin>>s>>t;
    ll dp[s.length()+5][t.length()+5];ms(dp,0);
    ll n=s.length(),m=t.length();
    forci(1,s.length()+1)
    {
        forcj(1,t.length()+1)
        {
            if(s[i-1]==t[j-1])  //matches
                dp[i][j]=dp[i-1][j-1]+1;
            else        //doesnt matches
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    ll val=dp[n][m];
    string ans;
    ll i=n,j=m;
    while(i&&j)
    {
        if(dp[i][j]!=max(dp[i-1][j],dp[i][j-1]))
        {
            ans.pb(s[i-1]);i--;j--;
        }
        else
        {
            if(dp[i][j]==dp[i-1][j])
                i--;
            else
                j--;
        }
    }
    reverse(all(ans));
    cout<<ans;
}

Measured memory_bytes: 74140
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

S = input()

x = defaultdict(int)
for s in S:
	x[s] = 1
if x["N"] == x["S"] and x["W"] == x["E"]:
	print("Yes")
else:
	print("No")


Measured memory_bytes: 5712
#include <stdio.h>
#include <stdlib.h>

int main(){
  unsigned long long sum = 0;
  char n[200000];
  if(scanf("%s",&n)<1){
    exit(1);
  }
  //printf("%s\n",n);
  for(int i = 0; i < 200000;i++){
    if(n[i]<'0' || '9'<n[i]){
      break;
    }
    //printf("n[i]: %c\n",n[i]);
    sum += n[i] -'0';
    //printf("sum: %d\n",sum);
  }
  //printf("sum: %d\n",sum);
  if(sum%9==0){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0; 
}

Measured memory_bytes: 1844
#include "bits/stdc++.h"

typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define REP(i,n) for (int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
 
using namespace std;
int h[501][501] = {0};
int H[501][501] = {0};

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

    REP(i,m){
        int a,b;
        cin >> a >> b;
        h[a][b]++;
    }

    for(int j = 1;j <= n;j++) for(int i = 1;i <= n;i++)  H[i][j] = H[i-1][j] + h[i][j];

    REP(i,q){
        int a,b,ans = 0;
        cin >> a >> b;

        for(int j = a; j <= b;j++){
            ans += H[b][j] - H[a-1][j];
        }
        cout << ans << endl;

    }
    
    return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;

int main(){
    int N, M; cin >> N >> M;
    int cnt = 0;
    double su = 0.0;
    vector<int>A(N);
    rep(i, N){
      cin >> A[i];
      su = su + A[i];
    }
    sort(A.rbegin(), A.rend());
    rep(j, M){
      if(A[j]<(double)su/(4*M)){
        cout << "No" << endl;
        return 0;
      }
    }
    cout << "Yes" << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> l(n);
  for(int i=0; i<n; i++) {
    cin >> l[i];
  }
  int ans = 0;
  for(int i=0; i<n; i++) {
    for(int j=i+1; j<n; j++) {
      ans += l[i]*l[j];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624