akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
inline double ABS(double a){return max(a,-a);}
struct Pt {
	double x, y;
	Pt() {}
	Pt(double x, double y) : x(x), y(y) {}
	Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
	Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
	Pt operator*(const Pt &a) const { return Pt(x * a.x - y * a.y, x * a.y + y * a.x); }
	Pt operator-() const { return Pt(-x, -y); }
	Pt operator*(const double &k) const { return Pt(x * k, y * k); }
	Pt operator/(const double &k) const { return Pt(x / k, y / k); }
	double ABS() const { return sqrt(x * x + y * y); }
	double abs2() const { return x * x + y * y; }
	double arg() const { return atan2(y, x); }
	double dot(const Pt &a) const { return x * a.x + y * a.y; }
	double det(const Pt &a) const { return x * a.y - y * a.x; }
};
double tri(const Pt &a, const Pt &b, const Pt &c) { return (b - a).det(c - a); }
double aCC(Pt a, double r, Pt b, double s) {
	double d = (a - b).ABS();
	if (sig(r - s - d) >= 0) return s * s * PI;
	if (sig(s - r - d) >= 0) return r * r * PI;
	if (sig(r + s - d) <= 0) return 0;
	double x = (d * d + r * r - s * s) / (d * 2);
	double h = sqrt(r * r - x * x);
	return r * r * atan2(h, x) + s * s * atan2(h, d - x) - d * h;
}
int main(){
	int a,b,c,d,e;
	while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&e),a){
		double r1=sqrt((double)c/PI);
		double r2=sqrt((double)d/PI);
		double L=0;
		double R=r1+r2;
		for(int i=0;i<100;i++){
			double M=(L+R)/2;
			double S=aCC(Pt(0,0),r1,Pt(M,0),r2);
			if(S>(double)e){	
				L=M;
			}else R=M;
		}
		bool flag=false;
		if(r1<r2){
			swap(r1,r2);
			flag=true;
		}
	//	printf("%f\n",L);
		if(max(r1*2,r2*2)>min((double)a,(double)b)){
			printf("impossible\n");continue;
		}
		Pt p1=Pt(r1,r1);
		Pt p2=Pt((double)a-r2,(double)b-r2);
		if((p1-p2).ABS()<L){
			printf("impossible\n");continue;
		}
		Pt p3=p1+(p2-p1)*L/(p2-p1).ABS();
		if(flag){
			swap(p1,p3);
			swap(r1,r2);
		}
		printf("%.12f %.12f %.12f %.12f %.12f %.12f\n",p1.x,p1.y,r1,p3.x,p3.y,r2);
	}
}

Measured memory_bytes: 1160
import sys
sys.setrecursionlimit(1000000)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        # 親の番号 根なら要素数(負の数)

    def find(self, x):
        """木の根を求める"""
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """xとyの属する集合を併合"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

N , M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
AB.reverse()
ans = [N * (N - 1) // 2]
for A, B in AB:
    if uf.same(A - 1, B - 1):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1] - uf.size(A - 1) * uf.size(B - 1))
    uf.unite(A - 1, B - 1)

for a in ans[:-1][::-1]:
    print(a)


Measured memory_bytes: 35420
from sys import stdin
N = int(stdin.readline().rstrip())
s_data = stdin.readline().rstrip().split()
height = [int(itr) for itr in s_data]
ans = 1
for h in range(0,N):
    if h == 0:
        continue
    if height[h] >= max(height[:h]):
        ans += 1
print(ans)

Measured memory_bytes: 3064
K,A,B = map(int,input().split())
if B-A-2 <= 0:
  print(K+1)
  exit()

if K-1 < A:
  print(K+1)
  exit()
  
K -= (A-1)
num = K//2
nokori = K%2
#print(K,num,nokori)
ans = A+num*(B-A)+nokori
print(ans)

Measured memory_bytes: 9188
FB = (1..10000).map{|x|a=[[:Fizz][x%3],[:Buzz][x%5]]*'';a==''?x.to_s: a}
loop do
  m, n = gets.split.map(&:to_i)
  break if m == 0
  ret = Array.new(m){|i|i+1}
  FB[0,n].zip(n.times.map{gets.chomp}).map.with_index{|(a,b),i| i if a!=b}.compact.unshift(0).each_cons(2).each_with_object([]).with_index{|(a,arr),i| arr << (a[1]-a[0])%(m-i)}[0,m-1].reduce(0){|s,t| ret.slice!(t=(s+t)%ret.size); t-1}
  puts ret.join(' ')
end

Measured memory_bytes: 10984
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let mut values: Vec<usize> = Vec::with_capacity(n);
    for _i in 0..n {
        values.push(iterator.next().unwrap().parse().unwrap());
    }

    values.sort_by(|a,b| b.cmp(a));
    let mut ans: f64 = values.pop().unwrap() as f64;
    for _i in 0..(n-1) {
        ans = (ans + values.pop().unwrap() as f64) / 2.0;
    }

    return format!("{:.10}", ans);
}

#[test]
fn test() {
    println!(
        "{}",
        solve(
            r"2
3 4"
        )
    );
    println!(
        "{}",
        solve(
            r"3
500 300 200"
        )
    );
    println!(
        "{}",
        solve(
            r"5
138 138 138 138 138"
        )
    );
}


Measured memory_bytes: 4352
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
def getint():
    a = input()
    a = int(a)
    return a
def main(n,x):
    ans = 10000000
    for i in range(100):
        sumup = 0
        for j in range(n):
            sumup = sumup + (x[j] -i)*(x[j]-i)
        if sumup < ans:
            ans = sumup
    return ans
        
n = getint()
x = listint()
ans = main(n,x)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f80 = __float80;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define pb push_back
#define rng(a) a.begin(),a.end()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define sz(x) (i64)(x).size()
#define bit(n) (1LL<<(n))
#define fi first
#define se second
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
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;}

i64 pow_mod(i64 n, i64 k, i64 m){
  i64 r = 1;
  for(;k;k>>=1){
    if(k&1) r=(r*n)%m;
    n=(n*n)%m;
  }
  return r;
}

struct uf{
  private:
    vi par, rank, size;
  public:
    uf(i64 n){ init(n); }
    void init(i64 n){
      par.resize(n);
      rank.resize(n,0);
      size.resize(n,1);
      rep(i,n) par[i] = i;
    }
    i64 root(i64 x){
      if(par[x] == x) return x;
      return par[x] = root(par[x]);
    }
    bool same(i64 x, i64 y){ return root(x) == root(y); }
    void unite(i64 x, i64 y){
      x = root(x), y = root(y);
      if(x==y) return;
      if(rank[x]==rank[y]) rank[x]++;
      if(rank[x]<rank[y]) swap(x,y);
      par[y] = x;
      size[x] += size[y];
    }
    i64 num(i64 x){ return size[root(x)]; }
};

void Main()
{
  i64 n,m;
  cin >> n >> m;
  cout << (n*(n-1)/2)+(m*(m-1)/2) << endl;

}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl


int main() {
    ll n,cnt=0, i=1;
    cin >> n;

    for(ll i = 1; i <= n; i++){
        if(i % 3 != 0 && i % 5 != 0){
            cnt += i;
        }
    }
    cout << cnt << endl;

    return 0;
}

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

  ll sum = 0;
  for (int i=1; i<=n; i++) {
    if (i % 3 == 0 && i % 5 == 0) continue;
    if (i % 3 == 0) continue;
    if (i % 5 == 0) continue;
    sum += i;
  }

  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(10 ** 5)

def find(parent, i):
  t = parent[i]
  if t < 0:
    return i
  t = find(parent, t)
  parent[i] = t
  return t

def unite(parent, i, j):
  i = find(parent, i)
  j = find(parent, j)
  if i == j:
    return
  parent[j] += parent[i]
  parent[i] = j

n, m = map(int, input().split())
parent = [-1] * n
inconvenience = n * (n - 1) // 2
result = []
for a, b in reversed([[int(c) - 1 for c in input().split()] for _ in range(m)]):
  result.append(inconvenience)
  pa, pb = find(parent, a), find(parent, b)
  if pa != pb:
    inconvenience -= parent[pa] * parent[pb]
  unite(parent, a, b)
for i in reversed(result):
  print(i)


Measured memory_bytes: 39280
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int main(){
    int a,b;
    cin >> a >> b;
    if(max(a,b)>8){
        cout <<":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }
}

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

// Loops
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define _rrep(i, n) rrepi(i, n, 0)
#define rrepi(i, a, b) for (int i = int(a) - 1; i >= int(b); --i)

#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(xi, x) for (auto &&xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)

// typedef
template <class T> using vec = vector<T>;
using ll = long long;
using vi = vec<ll>;
using vvi = vec<vi>;
using vvvi = vec<vvi>;
using pii = pair<ll, ll>;

// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define mp make_pair

// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase(unique(all(v)), v.end())
#define perm(c)                                                                \
  sort(all(c));                                                                \
  for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))

template <class T> pair<T, size_t> max(vector<T> &x) {
  auto it = max_element(all(x));
  return mp(*it, it - x.begin());
}
template <class T> pair<T, size_t> min(vector<T> &x) {
  auto it = min_element(all(x));
  return mp(*it, it - x.begin());
}

template <class T> inline bool chmax(T &maxval, const T &newval) {
  if (maxval < newval) {
    maxval = newval;
    return 1;
  }
  return 0;
}
template <class T> inline bool chmin(T &minval, const T &newval) {
  if (minval > newval) {
    minval = newval;
    return 1;
  }
  return 0;
}

// Utilities
// Grid world utilities
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
#define inside(H, W, y, x) 0 <= (x) && (x) < (W) && 0 <= (y) && (y) < (H)

// Debug
#ifdef LOCAL
#include "dump.hpp"
#define debug(x) cerr << #x << ": " << x << '\n'
#else
#define dump(...)
#define debug(x)
#endif

// Yes or No
void yesno(bool ok, string yes = "Yes", string no = "No") {
  cout << (ok ? yes : no) << endl;
}

// Paste snippets here!!

//

void solve(long long N, std::vector<long long> A) {
  vi buka(N,0);
  rep(i,N-1){
    buka[A[i]-1]++;
  }
  rep(i,N){
    cout << buka[i] << endl;
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false); // Magic for faster cin
  cout.precision(12);
  long long N;
  std::cin >> N;
  std::vector<long long> A(N - 2 + 1);
  for (int i = 0; i < N - 2 + 1; i++) {
    std::cin >> A[i];
  }
  solve(N, std::move(A));
  return 0;
}


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

int main()
{
	ios_base::sync_with_stdio(false);	
	cin.tie(NULL);
	int arr[3][3]={0};
	int n=3;
	for(int i=0;i<3;++i)
	{
	for(int j=0;j<3;++j)
	{
		cin>>arr[i][j];
	}
	}
	int t{0};
	cin>>t;
	while(t)
	{
		int num{0};
		cin>>num;
		for(int i=0;i<n;++i)
		{
			for(int j=0;j<n;++j)
			{
				if(arr[i][j]==num)
				arr[i][j]=-1;
			}
		}
		--t;
	}
	int flag=0;
	if(arr[0][0]==-1 and arr[0][1]==-1 and arr[0][2]==-1)
	flag=1;
	if(arr[1][0]==-1 and arr[1][1]==-1 and arr[1][2]==-1)
	flag=1;
	if(arr[2][0]==-1 and arr[2][1]==-1 and arr[2][2]==-1)
	flag=1;
	
	if(arr[0][0]==-1 and arr[1][0]==-1 and arr[2][0]==-1)
	flag=1;
	if(arr[0][1]==-1 and arr[1][1]==-1 and arr[2][1]==-1)
	flag=1;
	if(arr[0][2]==-1 and arr[1][2]==-1 and arr[2][2]==-1)
	flag=1;
	
	if(arr[0][0]==-1 and arr[1][1]==-1 and arr[2][2]==-1)
	flag=1;
	
	if(arr[0][2]==-1 and arr[1][1]==-1 and arr[2][0]==-1)
	flag=1;
	
	if(flag==0)
	cout<<"No\n";
	else
	cout<<"Yes\n";
	return 0;
}

Measured memory_bytes: 256
package main

import (
        "bufio"
        "fmt"
        "math/big"
        "os"
        "strconv"
        "strings"
)

var sc = bufio.NewScanner(os.Stdin)

func readInt() int              { return readIntArray()[0] }
func readInt2() (int, int)      { a := readIntArray(); return a[0], a[1] }
func readInt3() (int, int, int) { a := readIntArray(); return a[0], a[1], a[2] }
func readIntArray() []int {
        a := make([]int, 0, 1000)
        sc.Scan()
        for _, v := range strings.Split(sc.Text(), " ") {
                vv, _ := strconv.Atoi(v)
                a = append(a, vv)
        }
        return a
}
func readString() string        { return readStringArray()[0] }
func readStringArray() []string { sc.Scan(); return strings.Split(sc.Text(), " ") }

func main() {
        n := big.NewInt(int64(0))
        n.SetString(readString(), 10)

        if n.Cmp(big.NewInt(int64(10))) == -1 {
                fmt.Println(0)
                return
        }

        m := big.NewInt(int64(0))
        if m.Mod(n, big.NewInt(int64(2))).Cmp(big.NewInt(int64(0))) != 0 {
                fmt.Println(0)
                return
        }

        base := big.NewInt(int64(10))
        count := big.NewInt(int64(0))
        for i := 0; i < 10000000; i++ {
                tmp := new(big.Int)
                tmp.Div(n, base)
                if tmp.Cmp(big.NewInt(int64(0))) == 0 {
                        break
                }
                count.Add(count, tmp)
                base.Mul(base, big.NewInt(int64(5)))
        }

        fmt.Println(count)

}



Measured memory_bytes: 640
#include<iostream>
using namespace std;
const int maxn = 200000+5;
int A[maxn];
int main(){
    int N,K;
    cin >> N >> K;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(i>=K){
            if(A[i]<=A[i-K]){
                cout << "No" << endl;
            }
            else{
                cout << "Yes" << endl;
            }
        }
    }
}

Measured memory_bytes: 4412
#include <stdio.h>
#include <math.h>

int main()
{
    int N, K, i;
    double ans = 0;
    scanf("%d%d", &N, &K);
    for(i=1; i<=N; i++)
    {
        int j=i, n=0;
        while(j<K){j*=2;n++;}
        ans += ((1.0/N) * pow(0.5, n));
    }
    printf("%.16lf", ans);
    return 0;
}


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

int a[100009], dp[100009];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(i == 2) dp[i] = dp[i - 1] + abs(a[i] - a[i - 1]);
        else if(i > 2) dp[i] = min((dp[i - 1] + abs(a[i] - a[i - 1])), (dp[i - 2] + abs(a[i] - a[i - 2])));
    }
    cout << dp[n] << endl;
}



Measured memory_bytes: 1024
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  while(true){
	int N, M, A; cin >> N >> M >> A; if(N ==0) break;
	vector<PII> amida[1001];
	REP(i,M){
	  int h, a, b; 
	  cin >> h >> a >> b;
	  amida[h].PB(MP(a,b));
	}

	for(int h=1000;h>=0;--h){
	  for(auto& pii:amida[h]){
		if(pii.first == A){
		  A = pii.second;
		  break;
		}
		else if(pii.second == A){
		  A = pii.first;
		  break;
		}
	  }
	}
	cout << A << endl;
  }
  return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(std::string O, std::string E){
    REP(i, O.size()){
        cout << O[i];
        if(i+1 <= E.size()) cout << E[i];
    }

    cout << endl;
}

int main(){
    std::string O;
    std::cin >> O;
    std::string E;
    std::cin >> E;
    solve(O, E);
    return 0;
}



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

int main()
{
    int N;
    cin>>N;
    vector<long long> A(N);
    for (long long &a: A)
        cin>>a;

    int d = N%2==0 ? 2 : 3;
    vector<vector<long long>> T(d, vector<long long>(N/2, -1000000000000000LL));
    for (int i=0; i<d; i++)
        T[i][0] = A[i];
    for (int i=1; i<N/2; i++)
        for (int j=0; j<d; j++)
            for (int k=0; k<=j; k++)
                T[j][i] = max(T[j][i], T[k][i-1]+A[2*i+j]);
    long long ans = -1000000000000000LL;
    for (int i=0; i<d; i++)
        ans = max(ans, T[i][N/2-1]);
    cout<<ans<<endl;
}


Measured memory_bytes: 7572
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
int t[MAXN], v[MAXN], ans = 0, tmp[MAXN];
int miB[MAXN], miF[MAXN], mi[MAXN];

int main() {
	int n; ni(n); mem(miB, 0x3f), mem(miF, 0x3f);
	nai(t, n); nai(v, n); mem(mi, 0x3f);
	for (int i = 0; i < n; i++) t[i] *= 2, v[i] *= 2;
	for (int i = 1; i < n; i++) t[i] += t[i-1];
	for (int i = 1; i < n; i++) miB[t[i-1]] = v[i];
	miB[t[n-1]] = 0;
	for (int i = t[n-1]-1; ~i; i--) miB[i] = min(miB[i], miB[i+1]+1);
	for (int i = 0; i < n; i++) miF[t[i]] = v[i];
	miF[0] = 0;
	for (int i = 1; i <= t[n-1]; i++) miF[i] = min(miF[i], miF[i-1]+1);
	for (int i = 0; i < n; i++)
		for (int j = !i?0:t[i-1]; j <= t[i]; j++)
			mi[j] = min(mi[j], v[i]), tmp[j] = mi[j];
	for (int i = 0; i <= t[n-1]; i++) mi[i] = min(mi[i], min(miF[i],miB[i]));
	for (int i = 0; i < t[n-1]; i++) ans += (mi[i+1]+mi[i]);
	printf("%.20f\n", (double)ans/8.);
    return 0;
}


Measured memory_bytes: 16640
n,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

sum=0
for i in range(n):
    if(a[i]>x):
        temp=a[i]-x
        a[i]-=temp
        sum+=temp
    if(i>0):
        temp=a[i]+a[i-1]
        if(x<temp):
            a[i]-=temp-x
            sum+=temp-x
print(sum)

Measured memory_bytes: 14152
s=input()
ans=0
l=[]
c=1
now=s[0]
for i in s[1:]:
    if i==now:
        c+=1
    else:
        l.append(c)
        ans+=c*(c+1)//2
        now=i
        c=1
l.append(c)
ans+=c*(c+1)//2
if s[0]=="<":
    for i in range(len(l)//2):
       ans-=min(l[2*i],l[2*i+1])
else:
    for i in range((len(l)-1)//2):
       ans-=min(l[2*i+1],l[2*i+2])
print(ans)

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef set<int> si;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vi v(n);
    for (auto &i : v)
        cin >> i;
    int res = 0;
    for (;;)
    {
        for (auto &i : v)
        {
            if (i & 1)
                return cout << res << endl, 0;
            i >>= 1;
        }
        res++;
    }
}

Measured memory_bytes: 256
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
t = [INT() for i in range(n)]
ans = t[0]

for x in t:
        ans = ans*x//gcd(ans, x)
print(ans)

Measured memory_bytes: 10144
X, Y, Z, K= map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
B=list(map(int,input().split()))
B.sort(reverse=True)
C=list(map(int,input().split()))
C.sort(reverse=True)

ABC=[]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1)<=K:
                ABC.append(A[i] + B[j] + C[k])
            else:
                break

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

Measured memory_bytes: 8708
package main
import "fmt"

func main(){
	var N int;
	var ans, cnt int;
	fmt.Scan(&N);	
	
	for i := 1;i <= N;i=i+2 {
		for j := 1;j <= i;j++ {
			if i % j == 0 { cnt++; }
		}
		if cnt == 8{ ans++ }
		cnt = 0;
	}

	fmt.Printf("%d\n",ans);
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
	int a, b, c;
	int ls = 0;
	int diamond = 0;
	
	while (scanf("%d%*c%d%*c%d", &a, &b, &c) != EOF){
		if ((a * a) + (b * b) == c * c) ls++;
		else if (a == b) diamond++;
	}
	printf("%d\n%d\n", ls, diamond);
	
	return (0);
}

Measured memory_bytes: 0
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Diagnostics;
using System.Text;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
using static System.Math;


class P
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(int.Parse).ToArray();
        char[][] map = Enumerable.Repeat(0, hw[0]).Select(_ => Console.ReadLine().ToArray()).ToArray();
        int x = 0;
        int y = 0;
        while (x < hw[1] && y < hw[0])
        {
            map[y][x] = '.';
            if (y + 1 < hw[0] && map[y + 1][x] == '#') y++;
            else if (x + 1 < hw[1] && map[y][x + 1] == '#') x++;
            else break;
        }
        if (x == hw[1] - 1 && y == hw[0] - 1 && map.All(xe => xe.All(ye => ye == '.'))) Console.WriteLine("Possible");
        else Console.WriteLine("Impossible");
    }
}

Measured memory_bytes: 13524
#include <iostream>
#include <string>
#include <vector>

using namespace std;


int main()
{
	int N, A, B;

	cin >> N;

	if (N == 1) {
		cout << "Hello World";
	}
	else {
		cin >> A >> B;
		cout << A + B;
	}


	return 0;
}



Measured memory_bytes: 256
#include<cmath>
#include<string>
#include<fstream>
#include<iostream>
#define MAX(a,b) (a>b? a:b)
#define MIN(a,b) (a>b? b:a)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define lint long long int 
using namespace std;

int main(){
	int N,A,B;
	cin >> N >> A >> B;
	int cnt=0;
	int m=0;
	rep(n,N+1){
		m=n%10+(n%100-n%10)/10+(n%1000-n%100)/100+(n%10000-n%1000)/1000;
		if(n==10000) m++;
		if(m>=A&&m<=B) cnt+=n;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
N, K = (int(i) for i in input().split())  
h = np.array([int(i) for i in input().split()])

dp = np.empty(N, dtype='int')

for i in range(N):
  if i == 0:
    dp[i] = 0
  elif i - K < 0:
    dp[i] = np.min(np.abs(h[i] - h[:i]) + dp[:i])
  else:
    dp[i] = np.min(np.abs(h[i] - h[i-K:i]) + dp[i-K:i])

print(dp[N-1])

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


int main(){
    int s, f, b;
    cin >> s;
    f = s/100;
    b = s%100;
    if (b > 0 && b < 13 && f > 0 && f < 13) cout <<"AMBIGUOUS";
    else if (b > 0 && b < 13) cout << "YYMM";
    else if (f > 0 && f < 13) cout << "MMYY";
    else cout << "NA";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define mFOR(i, a, b) for (int i = a; i > b; i--)
#define MP make_pair
#define PB push_back
#define N 1000007
#define INF 1000000000
using namespace std;

typedef long long ll;

int main()
{
    int s, tmp;
    cin >> s;
    vector<int> v;
    v.push_back(s);
    tmp = s;
    FOR(i, 1, N)
    {
        if (tmp % 2 == 0)
            tmp = tmp / 2;
        else
            tmp = tmp * 3 + 1;
        if (binary_search(v.begin(), v.end(), tmp))
        {
            cout << i + 1 << "\n";
            break;
        }
        v.push_back(tmp);
        sort(v.begin(), v.end());
    }
    return 0;
}

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

#define REP(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define REPS(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define RREP(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define RREPS(i, n) for (int i = ((int)(n)); i > 0; i--)
#define IREP(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define IREPS(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVISORT(v) sort(v.begin(), v.end(), greater<int>());
#define ALL(v) v.begin(), v.end()
#define MP(n, m) make_pair(n, m);
#define COUT(d) cout<<std::setprecision(10)<<d<<endl;
#define CIN(n) getline(cin,n);

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using ll = long long;
using ul = unsigned long;

typedef long long ll;

template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

const int mod=1e9+7;

struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  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 {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};

mint c[4005][4005];
void init() {
  c[0][0] = 1;
  for (int i = 0; i <= 4000; i++) {
    for (int j = 0; j <= i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
}
mint comb(int n, int k) {
  return c[n][k];
}

bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }

    return true;
}

map<ll, ll> primeFact(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n]++;
  return res;
}

void printv(VI& v){
  REP(i,v.size()) cout << v[i] << " ";
  cout << endl;
}

int vtotal(VI& v){
  int total=0;
  REP(i,v.size()) total+=v[i];
  return total;
}

int main()
{
  cin.tie( 0 );
  ios::sync_with_stdio( false );
	
  //init(); // mint初期化
  string s;
  cin>>s;
  int n=s.size();
  int ans=0;
  int count=0;
  REP(i,n){
    if(s[i]!='A'&&s[i]!='C'&&s[i]!='G'&&s[i]!='T'){
        if(ans<count)ans=count;
        count=0;
        continue;
    }
    count++;
  }
  if(ans<count)ans=count;
  cout<<ans<<endl;
  return 0;
}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;
#define debug(x) cerr << #x << ": " << (x) << "\n";

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

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;
};

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

  int x, y;
  cin >> x >> y;
  int a, b, c;
  cin >> a >> b >> c;
  vl X(a), Y(b), Z(c);
  ll p;
  rep(i, 0, a) {
    cin >> X[i];
  }
  rep(i, 0, b) {
    cin >> Y[i];
  }
  rep(i, 0, c) {
    cin >> Z[i];
  }


  sort(All(X));
  reverse(All(X));
  sort(All(Y));
  reverse(All(Y));
  sort(All(Z));
  reverse(All(Z));

  vi vec;
  rep(i, 0, x) {
    vec.pb(X[i]);
  }
  rep(i, 0, y) {
    vec.pb(Y[i]);
  }

  rep(i, 0, c) {
    vec.pb(Z[i]);
  }

  sort(All(vec));
  reverse(All(vec));
  ll ans = 0ll;
  rep(i, 0, x+y) {
    ans += vec[i];
  }

  cout << ans << endl;



  return 0;
};


Measured memory_bytes: 4852
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast","no-stack-protector","unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;
#define F(i,L,R) for(int i=L;i<R;++i)
#define FE(i,L,R) for(int i=L;i<=R;++i)
#define getI(a) scanf("%d", &a)
#define getII(a,b) scanf("%d%d", &a, &b)
#define getIII(a,b,c) scanf("%d%d%d", &a, &b, &c)
#define VgetI(n) int (n); scanf("%d",&(n))
#define VgetII(n,m) int (n),(m); scanf("%d %d",&(n),&(m))
#define VgetIII(n,m,k) int (n),(m),(k); scanf("%d %d %d",&(n),&(m),&(k))
#define debug(x) cout<<(#x)<<"="<<x<<"\n";
#define qq cout<<"QQ\n";
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
#define ll long long
#define INF 2000000000
bool isPalin(string s){
	for(int i=0,j=s.length()-1;i<s.length()-1;i++,j--){
		if(s[i]!=s[j]) return 0;
	}
	return 1;
}
int main(){
	string s;
	while(cin>>s){
		bool ok=1;
		int n=s.length();
		ok&=isPalin(s);
		string a=s.substr(0,(n-1)/2);
		ok&=isPalin(a);
		a=s.substr((n+3)/2-1);
		ok&=isPalin(a);
		puts(ok?"Yes":"No");
	}
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long a = Math.round(Math.pow(x, 0.5));
		while (x % a != 0) {
			a--;
		}
		long b = x / a;
		System.out.println((b + a - 2));
		sc.close();
	}
}

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

int main(){
  int N , K ; 
  cin >> N >> K ; 
  vector<double> P(N+1) ; 
  pair<int , int > C ; 
  int T = 0 ; 
  int j = 1 ; 
  C.first = 0 ; 
  C.second = 0 ; 
  for(int i = 1 ; i <= N ; i++) {
    cin >> P.at(i) ; 
    T += P.at(i) ; 
    if(i > K ){
      T -= P.at(i - K) ; 
    }    
    if(T > C.second){
      C.second = T ; //
      C.first = i ; //K個の和が一番大きいのはi-K~iまでのK項
    }
    j++ ; 
  }
  
  //cout << C.first << " " << C.second << endl ; 
  
  double ans = 0 ; 
  
  for(int i = C.first - K +1 ; i  <=  C.first  ; i++){
    //cout << P.at(i) << endl ; 
    ans += P.at(i)*(P.at(i)+1)/(P.at(i)*2) ; 
  }
  cout << fixed << setprecision(11) << ans << endl ; 
  
}

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

using namespace std;

const int N = 1e5  +7;

int v[N];

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(v, v + n);
    if (n&1)
        return cout << 0, 0;
    cout << v[n / 2] - v[n / 2 - 1];
    return 0;
}


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

int main(){
int N;
int a=0;
while(true){
cin >> N;
if(N==0){
break;
}
vector<int> A(N+1);
A.at(0)=1;
A.at(1)=1;
if(N>1){
A.at(2)=2;
}
for(int i=3;i<N+1;i++){
A.at(i)=A.at(i-1)+A.at(i-2)+A.at(i-3);
}
cout << (A.at(N)-1)/3650+1 << endl;
}  
} 


Measured memory_bytes: 3008
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
# gcd
from fractions import gcd
# 切り上げ，切り捨て
from math import ceil, floor, sqrt
# リストの真のコピー（変更が伝播しない）
from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
from collections import Counter
import math
from functools import reduce
sys.setrecursionlimit(200000)
# input関係の定義
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print("debug: ", x, file=sys.stderr)
# template


# fin = open('in_1.txt', 'r')
# sys.stdin = fin
# # local only


def solve(N: int, D: int, X: "List[List[int]]"):
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            tmp = sum([(X[i][t] - X[j][t]) ** 2 for t in range(D)])
            for _i in range(int(sqrt(tmp)) - 2, int(sqrt(tmp)) + 2):
                if _i * _i == tmp:
                    ans += 1
                    break
    print(ans)


def iterate_tokens():
    for line in sys.stdin:
        for word in line.split():
            yield word


def main():
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    X = [[int(next(tokens)) for _ in range(D)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, D, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 66156
#include<stdio.h>

int main() {

	int A, B, C;

	scanf("%d %d %d", &A, &B, &C);

	if (B - A >= 1 && (B > C && C > A)) {
		printf("Yes");
	}

	else if (B - A <= 0 && (A > C && C > B)) {
			printf("Yes");	
	}

	else printf("No");

	return 0;

}

Measured memory_bytes: 128
object Main{
  class Edge(val from:Int,val to:Int,val cost:Long){}

  // v:????????°
  // s:?§????
  // graph:??£??\?????????
  def dijkstra(v:Int,s:Int,graph:Array[Array[Edge]],inf:Long= Long.MaxValue / 10) : Array[Long] = {
    val d : Array[Long] = Array.fill(v)(inf)
    val que = new scala.collection.mutable.PriorityQueue[Tuple2[Long,Int]]()(Ordering.Tuple2[Long,Int].reverse)
    que += Tuple2(0,s)
    d(s) = 0
    while(que.nonEmpty){
      val (cost,node) = que.dequeue
      if(d(node) >= cost){
        for(e <- graph(node)){
          if(d(e.to) > d(node)+e.cost){
            d(e.to) = d(node)+e.cost
            que+=Tuple2(d(e.to),e.to)
          }
        }
      }
    }
    return d
  }

  def main(args : Array[String]){
    val inf = Long.MaxValue / 10
    val sc = new java.util.Scanner(System.in)
    val v,e,r = sc.nextInt
    val g : Array[Array[Edge]] = Array.fill(v)(Array.empty)

    for(i <- 0 to e-1){
      val s,t,d = sc.nextInt
      g(s) :+= new Edge(s,t,d)
    }

    val res = dijkstra(v,r,g,inf)
    res.foreach(x => if(x==inf) println("INF") else println(x))
  }
}

Measured memory_bytes: 484944
#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(){
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    ll nowt,nowa;
    rep(i,n){
        ll t,a;
        cin >> t >> a;
        if(i == 0){
            nowt = t;
            nowa = a;
        }else{
            ll n1 = (t+nowt-1)/t, n2 = (a+nowa-1)/a;
            n1 = max(n1,n2);
            n2 = max(n1,n2);
            nowt = n1 * t;
            nowa = n2 * a;
        }
    }
    cout << nowt + nowa << endl;
    return 0;
}

Measured memory_bytes: 3568
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

void ye() {
    cout << "Yes" << endl;
}
void no() {
    cout << "No" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vi a(n);
    bool zero = true;
    set<int> se;
    rep(i, n) {
        cin >> a[i];
        if(a[i]) zero = false;
        se.insert(a[i]);
    }

    if(zero) {
        ye();
        return 0;
    }

    map<int, int> mp;
    rep(i, n) {
        mp[a[i]]++;
    }
    if(n%3) {
        no();
        return 0;
    }
    int h = n/3;
    vi all;
    for(P x:mp) {
        rep(i, x.second/h) {
            all.push_back(x.first);
        }
    }

    if(all.size() == 3 and (all[0]^all[1]^all[2]) == 0) {
        ye();
    } else {
        no();
    }
}

Measured memory_bytes: 10692
N,L= map(int,input().split())
aji = []
for i in range(1,N+1):
    aji.append(L+i-1)
if min(aji) >= 0:
    aji.pop(aji.index(min(aji)))
elif max(aji) <=0:
    aji.pop(aji.index(max(aji)))
else:
    aji.pop(aji.index(min(aji,key=abs)))
print(sum(aji))


Measured memory_bytes: 3060
a, b, c, d, e, f = map(int, input().split())

num = int(input())

def dice1(x):
    if x == b:
        return c
    elif x == c:
        return e
    elif x == d:
        return b
    else:
        return d

def dice2(x):
    if x == a:
        return d
    elif x == c:
        return a
    elif x == d:
        return f
    else:
        return c

def dice3(x):
    if x == a:
        return b
    elif x == b:
        return f
    elif x == e:
        return a
    else:
        return e

def dice4(x):
    if x == a:
        return e
    elif x == b:
        return a
    elif x == e:
        return f
    else:
        return b

def dice5(x):
    if x == a:
        return c
    elif x == c:
        return f
    elif x == d:
        return a
    else:
        return d

def dice6(x):
    if x == b:
        return d
    elif x == c:
        return b
    elif x == d:
        return e
    else:
        return c

for i in range(num):
    j, k = map(int, input().split())
    if j == a:
        print(dice1(k))
    elif j == b:
        print(dice2(k))
    elif j == c:
        print(dice3(k))
    elif j == d:
        print(dice4(k))
    elif j == e:
        print(dice5(k))
    else:
        print(dice6(k))




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

n, x = list(map(int, input().split()))
list = list(map(int, input().split()))
list = [abs(i - x) for i in list]
min = min(list)
for num in list:
    min = gcd(min, num)
print(min)

Measured memory_bytes: 15020
#include <bits/stdc++.h> 
#include <chrono>
using namespace std;
 
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
 
 
//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<long, long> PLL;
 
//container util
//------------------------------------------
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define ALL(a)  (a).begin(),(a).end()
//constant
//--------------------------------------------
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
 
int main(){
    int N;
    cin>>N;
    vector<PII>pi;
    REP(i,N)FOR(j,i+1,N){
        pi.PB(MP(i+1,j+1));
    }
    set<PII>ext;
    if(N%2==0){
        for(int i=1;i<=N/2;i++){
            ext.insert(MP(i,N-i+1));
        }
    }else{
        for(int i=1;i<=(N-1)/2;i++){
            ext.insert(MP(i,N-i));
        }
    }
    cout<<SZ(pi)-SZ(ext)<<endl;
    REP(i,SZ(pi))if(ext.find(pi[i])==ext.end()){
        cout<<pi[i].first<<" "<<pi[i].second<<endl;
    }

    return 0;
}

Measured memory_bytes: 384
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse = True)
i = 0
a = 0
b = 0
while i < n: 
    a = a +l[i]
    i += 2
i = 1
while i < n:
    b = b +l[i]
    i += 2
print(a -b)

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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] p2 = Console.ReadLine().Split(' ');
            int N = int.Parse(p2[0]);
            int K = int.Parse(p2[1]);
            string[] As = Console.ReadLine().Split(' ');
            int[] A = new int[N];
            int[] T = new int[N];
            int[] L = new int[N];
            for (var i = 0; i < N; i++)
            {
                A[i] = int.Parse(As[i]);
            }
            for (var i = 0; i < N; i++)
            {
                for (var j = 0; j < N; j++)
                {
                    if (A[j] < A[i])
                    {
                        if (j < i) L[i]++;
                        T[i]++;
                    }
                }
            }
            long ans = 0;
            long it = (long)(K + 1) * K / 2;
            it = it % 1000000007;
            for (var i = 0; i < N; i++)
            {
                long add = ((it * T[i]) % 1000000007 + 1000000007) - ((long)K * L[i]) % 1000000007;
                ans += add%1000000007;
                ans = ans%1000000007;
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13140
use proconio::input;

fn main() {
    input! {
        n : i64,
        k : i64,
    };
    let m = 1000000007;
    let mut res = 0;
    let mut low : i64 = 0;
    let mut high : i64 = 0;
    for i in 0..=n+1 {
        if i >= k {
            res = (res + high + m - low + 1) % m;
        }
        low += i;
        high += n - i;
    }
    println!("{}", res);
}


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

int main(){
	int N,ans=1;
	cin>>N;
	int H[N];
	for(int i=0;i<N;i++){
		cin>>H[i];
	}
	for(int i=1;i<N;i++){
		for(int j=0;j<i;j++){
			if(H[i]<H[j]){break;}
			if(j==i-1){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

LR = []
for _ in range(M):
    l, r = map(int, input().split())
    LR.append((l, r))
    
cards = LR[:]

import sys
INT_MAX = sys.maxsize

left_id = 0
right_id = INT_MAX
for l, r in cards:
    left_id = max(left_id, l)
    right_id = min(right_id, r)
    
if left_id <= right_id:
    ans = right_id + 1 - left_id
else:
    ans = 0
print(ans)

Measured memory_bytes: 53208
n, a, b = [int(x) for x in input().split()]

ans = 0
for i in range(1, n+1):
    s = str(i)
    ss = 0
    for k in range(len(s)):
        ss += int(s[k])
    if a<=ss<=b:
        ans += int(s)
print(ans)

Measured memory_bytes: 3060